Use of parallel deterministic dynamic programming and hierarchical adaptive genetic algorithm for reservoir operation optimization
Highlights
► ROO problem consists of many conflictive objectives to be optimized synchronously using constraint methods. ► DDP was applied to ROO problem with Parallel OpenMP complier. ► Improved AGA was applied to ROO problem in conjunction with hierarchy strategy. ► PDDP algorithm improved the computational efficiency and HAGA showed better convergence. ► HAGA with parallel model.
Introduction
The water resource crisis is increasingly becoming challenging and complicated, posing a dilemma for stakeholders desiring effective water allocation. Reservoir operation optimization (ROO) facilitates not only water resource allocation that yields maximum benefits with respect to multiple objectives in areas such as agriculture, energy, and industry but also rational water exploitation and hydropower generation. Moreover, for obtaining solutions to ROO problems, advanced computational technology and improved algorithms are used for enhancing the computation efficiency. ROO can be used for formulating, analyzing, and solving operation optimization problems in water resource planning (Loucks et al., 1981, Yeh, 1985).
Most methods used for ROO analysis involve conventional optimization algorithms and various metaheuristic algorithms. Over the past several decades, a wide range of methods have been proposed to solve ROO problems. Those reported to be effective are linear programming (LP) (Jabr, Coonick, & Cory, 2000), nonlinear programming (NLP) (Chen, 2007, Takriti and Krasenbrink, 1999), quadratic programming (QP) (Papageorgiou & Fraga, 2007), and Lagrangian relaxation (LR) (Hindi and Ghani, 1991, Keib et al., 1994). Dynamic programming (DP) is a powerful optimization technique that is applied to ROO and is considered to be a conventional optimization algorithm in reservoir operation. Among the traditional optimization techniques for reservoir operation, DP (Travers & Kaye, 1998) boasts high popularity. In other methods, there may be difficulties in finding the optimal solution. In the case of LP, the nonlinear and unsmooth characteristics of ROO problems are often ignored during linearization, generating large errors in the optimal operation. In NLP and QP, the objective function should be continuous and differentiable. Moreover, some approximations are necessary in the formulation when NLP and QP are used, and they may lead to inaccurate solutions when an continuous and differentiable objective function is used. In LR, Lagrange multipliers with updating strategy are used, and therefore, the method suffers from oscillations in the optimal result. In contrast, DP imposes no restrictions on the unsmooth and nonconvex nature of the ROO problem, which makes it superior. The ROO problem is a highly constrained nonlinear discrete dynamic optimization problem solved by complete enumeration with a DP solver.
The theory of DP, first used by Bellman in the early 1950s (Bellman, 1957), resulted in the principle of optimality. This principle is useful for solving problems with a separated monotonic criterion function. DP is a method for efficiently solving a broad range of searching and optimization problems. It involves the use of the principle of optimality in the optimal region, and a recursive algorithm for dividing a decision process into several interrelated stages in terms of time, space, etc. Generally, the major objective of the ROO problem at a hydropower station aims to maximize the total power generation by utilizing the limited water resource for future stages. The application of DP to ROO is popular since the problem has been formulated as a differential DP problem. The theory of DP for large-scale problems has been studied by Yakowitz (1982), who reviewed the use of the method for solving a water resource planning problem. DP models can be classified into two categories: stochastic dynamic programming models with uncertainty factors, and deterministic DP (DDP) models. For reservoir operating rule generation, Karamouz and Houck (1987) compared stochastic DP (SDP) and DDP with regression (DPR). They found that the DPR model performs better for large reservoirs with capacities exceeding 50% of the mean annual flow. DDP has also been applied to an ROO problem in which uncertain factor evaluation is not considered, and it may actually provide the optimal result. Although the DDP can solve the reservoir optimization problem, the high dimensionality of the problem poses difficulties and might not converge within a reasonable time, especially for large-scale hydropower systems. The practical limitation of DP is obvious as the number of possible decisions increases with the number of reservoirs. Further, the computational accuracy should be improved, which would result in a low computational efficiency. Therefore, the implementation of DDP in parallel, which would reduce the run-time, would significantly increase the efficiency of such parallel model.
Some hydraulic models, such as TRENT, CalTWiMS, TELEMAC, and RMA, use the message passing interface (MPI) (Gropp, Lusk, & Skjellum, 1994) and domain decomposition for simulations in parallel. Recently, the JFLOW diffusive wave model used graphics processing units (GPUs). However, these parallel tools hide a considerable amount of complexity. The computational strength of modern microprocessors has increased with the development of various commercial multi-threaded processors. Nowadays, the most popular parallel systems are based on shared memory. We can use the multi-threading feature of the hardware, which distinguishes these systems from traditional shared multi-processor systems, distributed memory systems, or hybrid distributed-shared memory systems. Consequently, increasing the thread-level parallelism becomes paramount for achieving the maximum potential performance from shared-memory multi-processor systems built with shared-memory threading processors. The parallel implementation of DDP involving complex data structures and memory allocation is used for ROO with a shared memory system that employs open multiprocessing (OpenMP). OpenMP (Chapman, Jost, & van der Pas, 2007) is a set of compiler directives with library routines that is used for creating an application program interface (API) for supporting multi-platform shared-memory parallel programming in FORTRAN, C, and C++ on all architectures, including UNIX and Windows NT platforms. Key advantages of OpenMP include easy implementation and the minimal recoding required for implementation in parallel. An OpenMP code can be developed on one platform and deployed on any other platform installing an OpenMP compiler. These parallel machines are built upon a set of processors that have access to a common memory by exchanging data between concurrent tasks without communicating with any processor and that communicate data by writing or reading shared data. We adopt a parallel DDP (PDDP) FORTRAN code that is implemented in parallel for ROO.
Owing to the lack of computational efficiency for ROO in the case of DP, modern heuristic stochastic search algorithms such as the genetic algorithm (GA) (Baskar et al., 2003, Chiang, 2007), evolutionary programming (EP) (Basu, 2004), simulated annealing (SA) (Basu, 2005), particle swarm optimization (PSO) (Cai, McKinney, & Lasdon, 2001), and the differential evolution algorithm (DE) have been extensively used to solve the ROO problem without ant restriction on the unsmooth and nonconvex characteristics of the problem. In recent decades, the GA has become widely used for the application of global optimization to ROO. Because of the increase in the complexity of ROO with the dimensionality, a large-scale ROO problem with an enormous number of variables and constraints must be decomposed into sub-problems to enhance the robustness of searching. Therefore, ROO problems can be alternatively solved by the GA. The genetic algorithm (Baskar et al., 2003) was formally introduced in the 1970s by John Holland (Holland, 1992). It has been proved to be effective in solving optimization and search problems in many fields of study (Chen, 1998, Goldberg, 1989, Karr, 1991, Kung and Chen, 1997, Lin, 1997). The GA is an adaptive heuristic search algorithm that mimics the principles laid down in Darwin’s theory of evolution and successively applies genetic operators such as selection, crossover (recombination), and mutation to iteratively improve the fitness of a population and reach the global optimum in the search space. It is one of the most promising algorithms, and the population-by-population method is the most important characteristic of the GA when compared to the point-to-point method of DP (Goldberg & Kuo, 1987). In recent decades, the GA has become popular for the application of global optimization to reservoir planning and management for scientific research and in the field of engineering (Cai et al., 2001, Chaves and Chang, 2008, Chen and Chang, 2007, Chen and Chang, 2009, Huang et al., 2002). However, the GA has not really been suitable for complex nonlinear problems like ROO problems.
The GA starts with a randomly generated initial population and improves the fitness of solutions through iterations by implementing operators such as scheme selection (reproduction), crossover, and mutation. A crossover operation leads to a mixture of chromosomes in the offspring without creating new allelic material. This can lead to slow convergence toward the same sub-optimal solution. Srinivas and Deb (1995) put forward the adaptive genetic algorithm (AGA) with adaptive crossover and mutation. The probabilities of crossover and mutation vary depending on the fitness values of the solutions, thus improving the convergence rate and robustness (Chen, Chen, & Chiang, 2009). Solutions with high fitness are preserved, while those with sub-average fitness are completely disrupted. However, the AGA is still challenging without the consideration of the initial population diversity. Preserving population diversity is crucial for a successful and efficient search of complex multimodal response surfaces. Lack of population diversity often results in convergence to a sub-optimal solution, whereas excessive diversity results in the inability to further refine solutions for closer approximation. As the number of decision variables increases in ROO problems, the search process becomes ineffective within the vast amount of GA chromosomes and results in slow evolution between consecutive generations. Consequently, the probability of converging to the optimal solution decreases sharply. In this paper, an improved AGA was proposed for solving ROO problems. We used the hierarchical structure of the archive scheme to change population diversity, and we proposed a hierarchical adaptive genetic algorithm (HAGA).
Failure to improve the efficiency of and remove the deficiency in the algorithm used for solving the ROO problem may lead to either excessive computation or unsatisfactory solutions. In this study, we also discussed the prime characteristics of ROO problems and a DDP algorithm with a parallel model. We also apply improved conventional and metaheuristic algorithms to ROO. A new parallel DDP (PDDP) approach incorporating both computational efficiency and optimal decisions was presented for the Three Gorges Project (TGP). An improved AGA (HAGA) incorporating optimal decisions was applied to the TGP, and the parallel model was also applied to HAGA. Moreover, outlines of PDDP and HAGA optimization techniques applied to ROO problems were presented (Fig. 1).
The remainder of this paper was organized as follows. Section 2 presented the formulation of the ROO problem. Section 3 explained the improved optimal algorithms. In Section 4, the application of the proposed optimal algorithm was shown and the results were presented. Finally, in Section 5, the results of the study were discussed and conclusions were provided.
Section snippets
Formulation of problems
ROO is aimed at maximizing water resource benefits by determining an optimal plan for a hydropower station over the operation period, while satisfying all kinds of physical and operational constraints. Generally, the objective function and associated constraints of the ROO problem can be formulated as follows.
Deterministic dynamic programming algorithm
Differential DDP can be used to solve the multistage optimization problem recursively. Dividing the reservoir operation into sub-operations on the basis of operation intervals, DDP yields an optimal solution to the whole problem by using the solutions for the sub-operations. The ROO problem can be solved by the following DDP steps described below.
Description of the Three Gorges Project (TGP)
Located in the middle of the Xiling Gorges, the Three Gorges Project (TGP) is one of the major water conservancy projects in China. The Yangtze River has a drainage area of 1.8 million square kilometers and includes agricultural and industrial terrain. It is the third largest river in the world and the largest river in China in terms of channel length and water flow. As the river flows east through the mountains, it encounters a narrow constriction at the Three Gorges of Qutang, Wu, and Xiling
Conclusions
The ROO problem consists of many conflicting objectives that must be optimized simultaneously under a series of equality and inequality constraints. The problem is difficult to solve efficiently not only because of its large scale but also because it is a multi-objective, dynamic, nonlinear, and constrained problem. A set in objective function space was identified using ɛ-constraint methods, and two objectives of the ROO problem were comprehensively optimized using a set of penalty items, to
Acknowledgement
The authors gratefully acknowledge the financial supports from National Key Basic Research Program of China under No. 2013CB036406.
References (38)
- et al.
Hybrid real coded genetic algorithm solution to economic dispatch problem
Computers & Electrical Engineering
(2003) An interactive fuzzy satisfying method based on evolutionary programming technique for multiobjective short-term hydrothermal scheduling
Electric Power Systems Research
(2004)A simulated annealing-based goal-attainment method for economic emission load dispatch of fixed head hydrothermal power systems
International Journal of Electrical Power & Energy Systems
(2005)- et al.
Solving nonlinear water management models using a combined genetic algorithm and linear programming approach
Advances in Water Resources
(2001) - et al.
Intelligent reservoir operation system based on evolving artificial neural networks
Advances in Water Resources
(2008) Economic dispatch: A direct search approach
Energy Conversion and Management
(2007)- et al.
Evolutionary artificial neural networks for hydrological systems forecasting
Journal of Hydrology
(2009) - et al.
GA-based modified adaptive fuzzy sliding mode controller for nonlinear systems
Expert Systems with Applications
(2009) Optimal economic emission dispatch of hydrothermal power systems
International Journal of Electrical Power & Energy Systems
(2007)- et al.
Dynamic economic dispatch for large-scale power systems: A Lagrangian relaxation approach
Electrical Power System Research
(1991)
An adaptive hybrid differential evolution algorithm for dynamic economic dispatch with valve-point effects
Expert Systems with Applications
A mixed integer quadratic programming formulation for the economic dispatch of generators with prohibited operating zones
Electrical Power System Research
A decomposition approach for the fuel constrained economic power-dispatch problem
European Journal of Operational Research
Dynamic programming
Using OpenMP: Portable shared memory parallel programming
Applying a real-coded multi-population genetic algorithm to multi-reservoir operation
Hydrological Processes
Multi-objective optimization-principle and case study
Cited by (56)
A LSTM-based approximate dynamic programming method for hydropower reservoir operation optimization
2023, Journal of Hydrology