A Selective Improvement Technique for Fastening Neuro-Dynamic Programming in Water Resources Network Management. de Rigo, D.; Castelletti, A.; Rizzoli, A. E.; Soncini-Sessa, R.; and Weber, E. In Proceedings of the 16th IFAC World Congress, volume 38, of IFAC-PapersOnLine, pages 7–12. International Federation of Automatic Control (IFAC).
A Selective Improvement Technique for Fastening Neuro-Dynamic Programming in Water Resources Network Management [link]Paper  doi  abstract   bibtex   
An approach to the integrated water resources management based on Neuro-Dynamic Programming (NDP) with an improved technique for fastening its Artificial Neural Network (ANN) training phase will be presented. When dealing with networks of water resources, Stochastic Dynamic Programming provides an effective solution methodology but suffers from the so-called "curse of dimensionality", that rapidly leads to the problem intractability. NDP can sensibly mitigate this drawback by approximating the solution with ANNs. However in the real world applications NDP shows to be considerably slowed just by this ANN training phase. To overcome this limit a new training architecture (SIEVE: Selective Improvement by Evolutionary Variance Extinction) has been developed. In this paper this new approach is theoretically introduced and some preliminary results obtained on a real world case study are presented. [Excerpt] The problem of designing optimal management (and planning) procedures for networks of water resources (reservoirs and distribution networks) has attracted analysts since the pioneering work of Rippl [1883], towards the end of the XIX century. Its main difficult is the presence together of nonlinear dynamics, high coupling among the states of these systems (and thus among the anthropical controls influencing them), risk and uncertainty, and finally decision making with conflicting objectives. It is easily arguable that the introduction of multiple managing objectives - they may be conflicting each other, expressing the intrinsically conflicting nature of most of the decisional problems - involves the need for exploring the solution sensitivity with respect to several aggregations of the objectives (searching the widest consensus). Technically such exploration implies an expensive repetition of an optimization algorithm that can only achieve a solution for a single (aggregated) objective. It follows that the efficiency of this algorithm constitutes the very core of the problem, as also demonstrated by the wide number of pertaining publications available in the literature (see for instance Yakowitz [1982], Yeh [1985], Tejada-Guibert et al. [1993], Lamond and Boukhtouta [1997], and Soncini-Sessa et al.[2001]). Thanks to its flexibility in handling nonlinearity and high coupling among states, Dynamic Programming (DP) [Bellman and Dreyfus, 1959] has been frequently used in the area of water management. [\n] Nevertheless, its extraordinary flexibility implies a critical drawback: a dimensionality increase of the problem, i.e. an addition of reservoirs, generates an exponential increase in the time required to finding a solution. This problem, called by Bellman the ” curse of dimensionality”, highly limits the application of DP to real world water systems, consisting of more than two or three reservoirs: given its structural nature, it poses serious questions on the opportunity of using DP in the IWRM. [\n] Many authors approached the problem by weakening at least one between the high state coupling and the high non-linearity, thus narrowing the application fields. Only a few tried to include both in the problem formulation, thus preserving the generality of the solution. An interesting attempt in this sense, first explored by Bellman itself [1963], is to reduce the freedom degrees of the DP solution, by resorting to a fixed class of functional approximations. In 1996, Bertsekas and Tsitsiklis exposed a methodology, named Neuro-Dynamic Programming (NDP), using Artificial Neural Networks (ANNs) as functional approximator of the DP solution. The ANN valuable global approximation properties allow the exploration of the search-space discretisation grid with a lower resolution, thus reducing the time required by the solution of one-step of the Bellman equation (see eq. 6), without degrading the accuracy. However this important time reduction is partially lost in the training of the ANN as the dimensionality of the problem increases. In order to overcome this problem we developed an ad hoc algorithm (SIEVE: Selective Improvement by Evolutionary Variance Extinction) to increase the ANN training performances. [...] [\n] We will present the SIEVE (Selective Improvement by Evolutionary Variance Extinction) technique: an evolutionary algorithm with geometrical selection (sieving) and pseudo-genetic generation by adaptive decreasing variance perturbations. [The SIEVE core] The core of the SIEVE architecture is to use iteratively a selection (sieving upon an inverse geometrical series) of the best parameter vectors, reducing exponentially the number of parameter vectors surviving at the next iteration. We compensate this reduction with a geometrical extension of the computational resources dedicated to train each parameter vector (making so that each iteration uses the same amount of computations as the others), until the absolutely best vector passes the last sieve. [\n] After each sieving selection phase, the survived vectors are put before a generative phase in which some other vectors are generated from them by adding perturbing noise. The noise variance decreases increasing the iteration number, in order to preserve the best training result achieved from the last parameter vectors, therefore leaving the possibility to significantly perturb some vector (exploration of new areas of the parameter space). All the sieved parameter vectors and the new generated from them are then trained, and so one for each iteration. [...] [Conclusions] An approach to the integrated water resources management based on neuro-dynamic programming has been presented. Neuro-dynamic programming allows to reduce the amount of memory needed to store the Bellman functions during the solution of an optimal control problem. It also reduces the computation time when the state space, used as training pattern, is sampled with a coarser grid, while the ANN, which approximates the Bellman function, still manages to maintain a good approximation performance. The ANN training phase on NDP requires a relevant fraction of the computational time: we propose the SIEVE (Selective Improvement by Evolutionary Variance Extinction) technique in order to achieve better performances. The first results are promising, but there is space for more research, especially on the efficient sampling of the discretised state space, trying to obtain the most efficient approximation of the Bellman function.
@inproceedings{derigoSelectiveImprovementTechnique2005,
  title = {A Selective Improvement Technique for Fastening Neuro-Dynamic Programming in Water Resources Network Management},
  booktitle = {Proceedings of the 16th {{IFAC World Congress}}},
  author = {de Rigo, D. and Castelletti, A. and Rizzoli, A. E. and Soncini-Sessa, R. and Weber, E.},
  editor = {Źıtek, Pavel},
  date = {2005-07},
  volume = {38},
  pages = {7--12},
  publisher = {{International Federation of Automatic Control (IFAC)}},
  issn = {1474-6670},
  doi = {10.3182/20050703-6-cz-1902.02172},
  url = {http://mfkp.org/INRMM/article/10793225___to-archive},
  abstract = {An approach to the integrated water resources management based on Neuro-Dynamic Programming (NDP) with an improved technique for fastening its Artificial Neural Network (ANN) training phase will be presented. When dealing with networks of water resources, Stochastic Dynamic Programming provides an effective solution methodology but suffers from the so-called "curse of dimensionality", that rapidly leads to the problem intractability. NDP can sensibly mitigate this drawback by approximating the solution with ANNs. However in the real world applications NDP shows to be considerably slowed just by this ANN training phase. To overcome this limit a new training architecture (SIEVE: Selective Improvement by Evolutionary Variance Extinction) has been developed. In this paper this new approach is theoretically introduced and some preliminary results obtained on a real world case study are presented.

[Excerpt] The problem of designing optimal management (and planning) procedures for networks of water resources (reservoirs and distribution networks) has attracted analysts since the pioneering work of Rippl [1883], towards the end of the XIX century. Its main difficult is the presence together of nonlinear dynamics, high coupling among the states of these systems (and thus among the anthropical controls influencing them), risk and uncertainty, and finally decision making with conflicting objectives. It is easily arguable that the introduction of multiple managing objectives - they may be conflicting each other, expressing the intrinsically conflicting nature of most of the decisional problems - involves the need for exploring the solution sensitivity with respect to several aggregations of the objectives (searching the widest consensus). Technically such exploration implies an expensive repetition of an optimization algorithm that can only achieve a solution for a single (aggregated) objective. It follows that the efficiency of this algorithm constitutes the very core of the problem, as also demonstrated by the wide number of pertaining publications available in the literature (see for instance Yakowitz [1982], Yeh [1985], Tejada-Guibert et al. [1993], Lamond and Boukhtouta [1997], and Soncini-Sessa et al.[2001]). Thanks to its flexibility in handling nonlinearity and high coupling among states, Dynamic Programming (DP) [Bellman and Dreyfus, 1959] has been frequently used in the area of water management.

[\textbackslash n] Nevertheless, its extraordinary flexibility implies a critical drawback: a dimensionality increase of the problem, i.e. an addition of reservoirs, generates an exponential increase in the time required to finding a solution. This problem, called by Bellman the ” curse of dimensionality”, highly limits the application of DP to real world water systems, consisting of more than two or three reservoirs: given its structural nature, it poses serious questions on the opportunity of using DP in the IWRM. 

[\textbackslash n] Many authors approached the problem by weakening at least one between the high state coupling and the high non-linearity, thus narrowing the application fields. Only a few tried to include both in the problem formulation, thus preserving the generality of the solution. An interesting attempt in this sense, first explored by Bellman itself [1963], is to reduce the freedom degrees of the DP solution, by resorting to a fixed class of functional approximations. In 1996, Bertsekas and Tsitsiklis exposed a methodology, named Neuro-Dynamic Programming (NDP), using Artificial Neural Networks (ANNs) as functional approximator of the DP solution. The ANN valuable global approximation properties allow the exploration of the search-space discretisation grid with a lower resolution, thus reducing the time required by the solution of one-step of the Bellman equation (see eq. 6), without degrading the accuracy. However this important time reduction is partially lost in the training of the ANN as the dimensionality of the problem increases. In order to overcome this problem we developed an ad hoc algorithm (SIEVE: Selective Improvement by Evolutionary Variance Extinction) to increase the ANN training performances. [...]

[\textbackslash n] We will present the SIEVE (Selective Improvement by Evolutionary Variance Extinction) technique: an evolutionary algorithm with geometrical selection (sieving) and pseudo-genetic generation by adaptive decreasing variance perturbations. 

[The SIEVE core] The core of the SIEVE architecture is to use iteratively a selection (sieving upon an inverse geometrical series) of the best parameter vectors, reducing exponentially the number of parameter vectors surviving at the next iteration. We compensate this reduction with a geometrical extension of the computational resources dedicated to train each parameter vector (making so that each iteration uses the same amount of computations as the others), until the absolutely best vector passes the last sieve.

[\textbackslash n] After each sieving selection phase, the survived vectors are put before a generative phase in which some other vectors are generated from them by adding perturbing noise. The noise variance decreases increasing the iteration number, in order to preserve the best training result achieved from the last parameter vectors, therefore leaving the possibility to significantly perturb some vector (exploration of new areas of the parameter space). All the sieved parameter vectors and the new generated from them are then trained, and so one for each iteration. [...]

[Conclusions] An approach to the integrated water resources management based on neuro-dynamic programming has been presented. Neuro-dynamic programming allows to reduce the amount of memory needed to store the Bellman functions during the solution of an optimal control problem. It also reduces the computation time when the state space, used as training pattern, is sampled with a coarser grid, while the ANN, which approximates the Bellman function, still manages to maintain a good approximation performance. The ANN training phase on NDP requires a relevant fraction of the computational time: we propose the SIEVE (Selective Improvement by Evolutionary Variance Extinction) technique in order to achieve better performances. The first results are promising, but there is space for more research, especially on the efficient sampling of the discretised state space, trying to obtain the most efficient approximation of the Bellman function.},
  isbn = {978-3-902661-75-3},
  keywords = {*imported-from-citeulike-INRMM,~INRMM-MiD:c-10793225,~to-add-doi-URL,artificial-neural-networks,curse-of-dimensionality,evolutionary-techniques,featured-publication,genetic-algorithms,integrated-water-resources-management,mastrave-modelling-library,neuro-dynamic-programming,sieve,sieve-parameter-training-architecture},
  options = {useprefix=true},
  series = {{{IFAC}}-{{PapersOnLine}}},
  venue = {Prague, Czech Republic}
}
Downloads: 0