Journal of the American Water Resources Association: Real coded genetic algorithm optimization of lo

ABSTRACT: An optimization and simulation model holds promise as an efficient and robust method for long term reservoir operation, an increasingly important facet of managing water resources. Recently, genetic algorithms have been demonstrated to be highly effective optimization methods. According to previous studies, a real coded genetic algorithm (RGA) has many advantages over a binary coded genetic algorithm. Accordingly, this work applies an RGA to obtain the 10-day (the traditional period of reservoir operation in Taiwan) operating rule curves for the proposed reservoir system. The RGA is combined with an effective and flexible scheme for coding the reservoir rule curves and applied to an important reservoir in Taiwan, considering a water reservoir development scenario to the year 2021. Each rule curve is evaluated using a complex simulation model to determine a performance index for a given flow series. The process of generating and evaluating decision parameters is repeated until no further improvement in performance is obtained. Many experiments were performed to determine the suitable RGA components, including macro evolutionary (ME) selection and blend-[alpha] crossover. Macro evolution (ME) can be applied to prevent the premature problem of the conventional selection scheme of genetic algorithm. The purpose of adjusting [alpha] of a crossover scheme is to determine the exploratory or exploitative degree of various subpopulations. The appropriate rule curve searched by an RGA can minimize the water deficit and maintain the high water level of the reservoir. The results also show that the most promising RGA for this problem consists of these revised operators significantly improves the performance of a system. It is also very efficient for optimizing other highly nonlinear systems.

(KEY TERMS: long term reservoir operation; real coded genetic algorithm; rule curves; macro evolutionary selection; blend-[alpha] crossover.)

INTRODUCTION

The operation of a reservoir system is a complex decision making process involving many variables and objectives, as well as considerable risk and uncertainty (Oliveira and Loucks, 1997). Fixed rules governing the operation of a reservoir system are commonly presented in the form of graphs or tables (Wurbs, 1996). An optimal operating procedure is needed for the purposes of planning of a complex water resources system. Finding the optimal operating rules of a reservoir system for planning purposes has been a major area of study. Operating rule curves are used in managing most reservoirs in Taiwan. These curves primarily guide the release of the reservoir system according to the current storage level and the time of year. Existing policies may need to be modified if demand changes, sediment effects occur, or new facilities such as water treatment plants are installed.

The need for an efficient optimization method to reevaluate the system is obvious since the many currently used operating rule curves have been developed from experience and/or from trial and error simulation. Traditional optimization techniques including linear programming (LP) and dynamic programming (DP) have been used to solve the reservoir operation problems. Yeh (1985) presents a comprehensive in-depth state-of-the-art review of reservoir operation models, with a strong emphasis on optimization techniques. Generalized computer codes are available for solving LP problems, but the strict linear form of LP does limit its applicability (Wurbs, 1993). Nonlinear properties of a problem can be readily reflected in a DP formulation. However, the usefulness of DP for multireservoir systems is limited by the huge demand that it can place on computational resources. The choice of methods depends on the characteristics of the reservoir system being considered, on the availability of data, and on the objectives and constraints specified. Most of these models, however, are valid only for simplified reservoir systems. Genetic algorithms (GAs) have received much attention for their potential use as optimization techniques for complex systems.

In the reservoir operation system fields, GAs have been demonstrated as powerful optimization approaches, but there are few references to them in the literature. In one study, Esat and Hall (1994) applied a GA to a four-reservoir problem. They concluded that GAs have potential in water resources optimization and that significant savings could be achieved in both memory and execution times. Oliveira and Loucks (1997) used GAs to develop operating policies for multireservoir systems and concluded that GAs are practical and robust methods that could lead to effective operating policies. Chang and Chen (1988) applied a real coded GA for rule based flood control reservoir management. The results show that the real coded GA performed better in terms of efficiency and precision than the binary coded GA. Wardlaw and Sharif (1999) demonstrated that using GAs can provide a robust and acceptable solution for a four-reservoir deterministic problem. Further, they could acquire the known global optimum. Sharif and Wardlaw (2000) presented multireservoir systems optimization using GAs. By comparing discrete differential dynamic programming (DDDP) they found that GA results are very close to the optimum, and the technique appears to be robust.

GAs may be set up in many ways, but as yet there is little guidance in the literature on the type of formulation most appropriate for reservoir operations. In this paper we address that gap by considering the application of real coded genetic algorithms (RGAs) to a complex actual reservoir water supply according to the rule curves of the reservoir, including hydropower simulation. The objective is to show GAs could deal easily with nonlinear problems and are shown to be very robust optimization tools. First of all, we have to determine the decision parameters that could generate a set of rule curves. Then, each rule curve is evaluated using a complex simulation model to compute a water shortage index for a given historical flow series. Several experiments are designed to choose the appropriate RGA components, including roulette, tournament, macro evolutionary (ME) selection, and linear, flat, blend-[alpha] crossover. The cycle of evolution is repeated until a desired termination criterion is reached. This criterion can be set by the number of evolution cycles (computational runs), the variation of individuals between different generations, or a predefined value of fitness.

GENETIC ALGORITHMS

The need for solving optimization problems arises in almost every field. As a consequence, many analytic and numerical optimization techniques have been developed. However, many functions, such as discontinuous, nondifferentiable, nonconvex, or multimodal functions, are beyond analytical methods and present profound difficulties for numerical techniques. Moreover, traditional optimization techniques depend highly on a deterministic relationship between the model's parameters and its performance. To date, these techniques have been unable to optimize the performance of complex systems. Consequently, new and more robust optimization techniques capable of handling such problems are needed.

Interest is growing in solving optimization problems. The genetic algorithm (GA) is one of the most promising techniques in that domain and has received a great deal of attention with regard to optimizing complex systems. The GA is essentially a Darwinian natural selection process that combines an artificial survival of the fittest with natural genetic operators (Holland, 1975). Through the genetic evolution method, an optimal solution can be found and represented by the final winner of the genetic evolution.

The GA is an iterative procedure that maintains a population of individuals that are candidate solutions to a specific domain. During each generation, the individuals in the current population are rated for their effective evaluations, and a new population of candidate solutions is formed using specific genetic operators such as reproduction, crossover, and mutation (Grefenstette, 1986). Goldberg (1989) and Davis (1991) reviewed many important applications of GAs.

Several researchers have found that RGAs have advantages over binary coded GAs (Wright, 1991; Eshelman and Schaffer, 1992). The reproduction operator may be implemented in algorithmic form in a number of ways, such as roulette selection (Goldberg 1989), tournament selection (Goldberg and Deb 1991; Chen 2003), and macro evolutionary (ME) selection (Marin and Sole 1999). Three well known methods for implementing the crossover scheme are linear crossover (Wright, 1991), flat crossover (Radcliffe, 1990, unpublished Ph.D., dissertation, University of Edinburgh, Edinburgh, United Kingdom), and BLX-0.5 crossover (Eshelman and Schaffer, 1992).

APPLICATION TO RESERVOIR OPERATION OPTIMIZATION

The area of study is the Fei-Tsui Reservoir, which was completed more than 16 years ago, and the proposed water treatment plant at Kan-Yuan, which will be installed in 2021. The purpose of this paper is to demonstrate application of the RGA approach in the optimization of the rule curves of this reservoir.

System Description

The Fei-Tsui Reservoir, which was completed in 1985 and has an efficient storage capacity of 359*10^sup 6^ m^sup 3^, is one of the major storage reservoirs in northern Taiwan. The hydropower plant at Fei-Tsui has a generating capacity of 70 MW. It is a multipurpose reservoir for flood control, hydroelectric power generation, and water supply. The primary water use in the basin is potable water for the city of Taipei. A system schematic water supply network is shown in Figure 1. There are four inflow points, one reservoir (with power plant), three water treatment plants, one diversion, and four merger points to connect the flow net of this system.

Input Data

The historic inflow, definition of the system configuration, reservoir properties, and other data used in this study included the operating rules, streamflows, and water demand targets of the system. To evaluate the long term reservoir operating performance, we used 10-day inflow data for 41 years, or a total of 1,476 data records. The water requirement in future development scenarios is adopted to represent the requirement for the simulation period. The 10-day water supply demand target of Fei-Tsui Reservoir in year 2021 is shown in Figure 2. It is demonstrated that the average of this target is 49.2 cms.

Simulation Method

The purpose of the simulation model in this paper is to recreate the 10-day operations of the Fei-Tsui Reservoir by following its rule curve. The operating rule defines the release within each year as a function of existing storage level and overall release target amounts. The rule curve of Fei-Tsui Reservoir, which consists of three curves, is shown in Figure 3. The 10-day operations are described as the following four operating rules (see Figure3).

1. When the water level is above the upper limit, hydropower generation should be maximized to keep the water level at the upper limit.

2. When the water level is between the upper and lower limits, all operations, including public water and hydropower generation, are operating under normal conditions, but hydropower should be generated, at most, six hours per day.

3. When the water level is between lower and critical limits, public water can be supplied as usual, but hydropower generation is halted.

4. When the water level is below critical limits, public water supply must be reduced.

Parameters Coding

Applying RGA to water resources problems, chromosomes may be generated that fail to meet system constraints. Therefore, each generated chromosome must be checked against such system constraints. Binary strings are the common encoding schemes, but real strings are more efficient. Because the range of a parameter is a real number, it does not have to encode as a bit string. There are three curves - the upper limit, lower limit, and critical limit. Each curve is composed of six decision variables, which are coded in a real string. The lower limit defines the hydropower generation, and the critical limit determines whether to cut back the water for public use. To maintain the function of flood control, the upper limit curve will not be changed, so the total number of decision variables is 12 (i.e., six for the lower limit and six for the critical limit curve). The details of these variables are described in Table 1 and Figure 3. By doing this, each chromosome is a real valued vector x = (x^sub 1^, x^sub 2^,...x^sub 12^) [epsilon] R^sup 12^ (the decision variable of a rule curve).

The coding of parameters may vary according to the nature of the problem itself. An appropriate number of parameters, 12, that could describe the whole decision space are presented in this paper.

Experiments Using RGAs

The entire procedure of this study is in two parts the simulation model and the optimization model. Combining these two parts to search the best set of rule curves is an important task. The optimization model using RGA could generate a set of rule curves (i.e., 12 decision variables), and the simulation model programming could use these decision variables to calculate their fitness function values. The repetition of these two steps is necessary to produce the required number of generations.

Two experimental procedures for choosing the proper selection and crossover schemes entailed three selection schemes - ME, roulette, and tournament and three crossover schemes - linear, flat, and BLX-0.5.

RESULTS AND DISCUSSION

The experimental results show that the RGA converges quickly and reaches an optimal solution where the objective value is close to the theoretical minimum point. Several experiments were discussed in which the ME selection and BLX-0.5 crossover could obtain the best results.

Although the results of ME selection were not good at the beginning, it was shown that ultimately its results became better than the other two selection schemes (see Figure 4). In standard GA, the selection operator like roulette selection chooses individuals with a probability proportional to their relative fitness, but this can lead to "premature convergence." In ME, large extinctions can generate coherent population responses that are very different from the slow Darwinian dynamics of a classical GA. Further, the population of candidate solutions/species might be understood in terms of an ecological system with connections among different species, instead of just a number of independent entities with a given assigned fitness value. The biological model of macroevolution simulates the dynamics of species extinction and diversification for large time scales. These dynamics are based on the relation between species and the links that are constructed between each species at each generation to determine whether the species could be alive.

The BLX-0.5 crossover could make the best performance among all the cases (see Figure 5). Crossover is a technique that takes two parent chromosomes and produces two child chromosomes. Crossover operator of the real coded GA is mimicking the k-point crossover of binary coded GA, which considers offspring of some perturbations from the values of their parents. A weakness with this crossover approach is that any offspring may be much worse than either parent. There are three methods - linear, flat or blend crossover - for solving this problem. Blend crossover (BLX-[alpha]) uniformly picks values that lie between two points that contain the two parents, but they may extend equally on either side determined by a userspecified GA-parameter [alpha]. The function of adjusting is to achieve the exploratory or exploitative degree of different subpopulations. Only when [alpha] = 0.5 is a balanced relationship reached between convergence (exploitation) and divergence (exploration). The probability that a gene will lie in the exploitation interval is then equal to the probability that it will lie in an exploration interval (Chen, 2003, unpublished manuscript).

Figure 6 indicates that the optimal lower limit is above that of the original rule curve and the critical limit is below that of the original rule curve. Table 2 presents the optimal values of the variables. The results reveal that the shortage index of the optimal solution equals zero and the average water level of the reservoir is higher than those obtained following the original rule curve. Table 3 displays these comparisons, including the average water level of the reservoir and the water deficit, deficit water. These results demonstrate that the higher lower limit could increase the hydropower efficiency about 1.8 percent and the lower critical limit could decrease the deficit of water release, or shortage index, to zero. Therefore, the optimal parameters of rule curve generated from RGAs are reasonable and efficient.

The RGA has specific advantages in the context of reservoir systems optimization. First, discretization of decision space and initial trial state trajectories are not required. Second, decomposing complex reservoir systems into successive approximation based approaches is not to be needed. Third, discontinuous and complex objective functions are acceptable. Finally, complex simulation models can be coupled to evaluate the fitness function of the reservoir system.

CONCLUSIONS

This study proposes a real coded genetic algorithm (RGA) combined with the simulation model and demonstrates that it can be used efficiently to optimize the operating rule curves of a major reservoir system in Taiwan. These operating rule curves define long term target storage levels and target release. They can be used to help system operators make decisions. In particular, means of determining the decision parameters that could represent a set of rule curves were considered. The results show that the release could optimize the objective function for a specified inflow and initial storage level.

In this study, solutions very close to the optimum were achieved within 200 generations with a population of 100. A real value representation incorporating ME selection and BLX-0.5 crossover is found to produce the best results. The new rule curve, optimized by RGA, can maintain a higher water level of the reservoir and a lower water deficit than could the original rule curve.

The method is not limited by the type of the objective function. In contrast to various conventional optimization algorithms, the objective function need not be differentiable or continuous. Since the GA uses a simulation model to evaluate each generated rule curve, no restrictions apply to the definition of the operating policy. Besides, a significant advantage of the GA approach is that no initial trial release policy must be imposed. The algorithm of parallel structures used in this study may help to reduce the number of computations and evaluations.

1Paper No. 02063of the Journal of the American Water Resources Association. Discussions are open until April 1, 2004.

LITERATURE CITED

Chang, F. J. and L. Chen, 1998. Real-Coded Genetic Algorithm for Rule-Based Flood Control Reservoir Management. Water Resources Management 12:185-198.

Chen, L., 2003. A Study of Applying Genetic Programming to Reservoir Trophic State Evaluation Using Remote Sensor Data. International Journal of Remote Sensing 24(11):2265-2275.

Davis, L., 1991. Hybridization and Numerical Representation. In: Handbook of Genetic Algorithms, L. Davis (Editor). Van Nostrand Reinhold, United Kingdom, pp. 61-71.

Esat, V. and M. J. Hall, 1994. Water Resources System Optimization Using Genetic Algorithms. In: Proc. of the First International Conference on Hydroinformatics, Balkema, Rotterdam, The Netherlands, pp. 225-231.

Eshelman, L. J. and J. D. Schaffer, 1992. Real-Coded Genetic Algorithms and Interval-Schemata. In: Proceedings of the Fifth International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, California, pp. 187-202.

Goldberg, D. E., 1989. Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley, Reading, Massachusetts.

Goldberg, D. E. and K. Deb, 1991. A Comparative Analysis of Selection Schemes Used in Genetic Algorithms. In: Foundations of Genetic Algorithms, G. Rawlins (Editor). Morgan Kaufmann, San Mateo, California, pp. 69-93.

Grefenstette, J. J., 1986. Optimization of Control Parameters for Genetic Algorithms. IEEE Transactions on System, Man, and Cybernetics, SMC-16(1): 122-128.

Holland, J. H., 1975. Adaptation in Natural and Artificial Systems. The University of Michigan Press, Ann Arbor, Michigan.

Marin, J. and R. Sole, 1999. Macroevolutionary Algorithms: A New Optimization Method on Fitness Landscapes. IEEE Transactions on Evolutionary Computation 3(4):272-285.

Oliveira, R. and D. P. Loucks, 1997. Operating Rules for Multireservoir Systems. Water Resour. Res. 33(4):839-852.

Sharif, M. and R. Wardlaw, 2000. Multireservoir System Optimization Using Genetic Algorithms: Case Study. J. Comp. in Civ. Engrg., ASCE 14(4):255-263.

Wardlaw, R. and M. Sharif, 1999. Evaluation of Genetic Algorithms for Optimal Reservoir System Operation. J. Water Resources Planning and Management, ASCE 125(l):25-33.

Wright, A., 1991. Genetic Algorithms for Real Parameter Optimization. In: Foundations of Genetic Algorithms, G. J. E. Rawlins (Editor). Morgan Kaufmann, San Mateo, California, pp. 205218.

Wurbs, R. A., 1993. Reservoir-System Simulation and Optimization Models. J. Water Resources Planning and Management, ASCE 119(4):455-472.

Wurbs, R. A., 1996. Modeling and Analysis of Reservoir System Operations. Prentice Hall, Englewood Cliffs, New Jersey.

Yeh, W. W.-G., 1985. Reservoir Management and Operation Models: A State-of-the-Art Review, Water Resources Research 21(12): 1797-1818.

Li Chen2

Chen, Li, 2003. Real Coded Genetic Algorithm Optimization of Long Term Reservoir Operation. Journal of the American Water Resources Association (JAWRA) 39(5):1157-1165.

2Associate Professor, Department of Civil Engineering, Chung Hua University, No. 707, Sec. 2, WuFu Road, Hsinchu, Taiwan 300, Republic of China (E-Mail: lichen@chu.edu.tw).