COMPARISON OF OPTIMIZATION ALGORITHMS IN PARAMETER CALIBRATION OF TANK MODEL

Joong H. Kim¹, Kyung R. Paik¹, Dong R. Lee², and Hyung S. Kim³

¹Assoc. Prof. and Grad. Assistant, Dept. of Civil Eng., Korea Univ., Seoul, S. Korea

²Senior Researcher, Korea Inst. of Construction Tech., Ilsan, Kyounggi, S. Korea

³Assist. Prof., Dept. of Civil Eng., Sunmoon Univ., Chunan, Chungnam, S. Korea

 

　

Abstract: Among various deterministic rainfall-runoff models, tank model is often preferred for its simplicity. On the other hand, it requires much time and effort to obtain better results owing to the calibration of too many parameters in the model. Therefore, the demand for applying automatic calibration method has been increased. In this study, three optimization algorithms are tested for the automatic calibration: one nonlinear programming algorithm (Powell’s method) and two meta-heuristic algorithms (Genetic Algorithm and Harmony Search). As a result, the two heuristic methods show a very good performance in the calibration compared to Powell’s method. Attempts have been made to improve the performance of HS (Harmony Search). The improved HS shows better calibration results than GA does in a given CPU time. The Harmony Search algorithm of this study contributes in solving the biggest problem in using tank models, parameter calibration.

 

Keywords: tank model, powell’s method, genetic algorithm, harmony search

There are many deterministic models that can simulate long-term runoffs, but most of them have complex structures and requires various observed data for calibration. Therefore, tank models are often preferred in practice since they require only the precipitation, runoff, and evapotranspiration data. The tank model which has a merit of simplicity in data requirement, however, has a drawback, in that it needs much time and effort to calibrate its too many model parameters.

Since the concept of tank models was first proposed, there have been many researches on parameter calibration of the tank models. Nagai and Kadoya applied three optimization algorithms of Powell’s method, DFP (Davidon, Fletcher and Powell) method, and QG (combined techniques of Quasi-linearization and Golden section) and proved the excellency of Powell’s method and DFP method in parameter identification in 1979. Kim, H. Y. and Park, S. W. (1986) evaluated parameter variations with watershed characteristic for six watersheds in Korea. In 1997, Cooper et al. investigated the performance of three optimization algorithms, that is, SA (Simulated Annealing), GA, and SCE (Shuffled Complex Evolution) for calibrating the tank model that contains only two tanks. Ministry of construction and transportation and KOWACO (Korea Water Resources Corporation) (1997) also published many reports about applying tank model to several major dam stations in Korea. Recently, KICT (Korea Institute of Construction Technology) (1999) adopted Powell’s method for parameter optimization in a tank model.

In this study, three optimization algorithms are tested for the automatic calibration: one nonlinear programming algorithm (Powell’s method) and two meta-heuristic algorithms (Genetic Algorithm and Harmony Search). For the proper comparison, sensitivity of optimization parameters of GA and HS that are thought to have great influence on performance of optimization are analyzed. And the best values for these optimization parameters are used in comparison.

Tank modes are intended for calculation of a runoff with the catchment area of a river substituted by a combination of a number of storage type model vessels, first introduced by Sugawara and Funiyuki (1956). It is a kind of deterministic, lumped, linear, continuous, and time-invariant model and it can be applied to flood analyses, too. In at least two studies comparing the performances of some of popular conceptual rainfall-runoff models, the tank model demonstrated its capability for modeling the hydrologic responses from a wide range of catchments (WMO, 1975; Franchini and Pacciani, 1991).

Tank model is composed of a few (usually 4) tanks laid vertically in series. The output from the top tank is considered as surface runoff, the output from the second tank as intermediate runoff, the output from the third tank as sub-base runoff and output from the fourth tank as baseflow. This model structure may be considered to correspond to the zonal structure of the surface and subsurface water. Similarly, the output from the bottom outlet of the top tank could be considered to correspond to infiltration. The outputs from the bottom outlets of the other tanks could be regarded as percolation.

Fig. 1  Schematic of tank model in this study.

There are some sorts of variety of the usual tank model. Although many side outlets in first tank can result in representing flood response more precisely, it makes more parameters to be calibrated. In Korea, the common purpose of tank model is to forecast long-term runoff. To build a practical model, a tank model with 4 tanks is introduced. First tank has two side outlets and the other tanks have one side outlet. This structure is the same as the tank model of KICT. Figure 1 shows the schematic of the tank model used in this study.

Powell’s method, the short name of the conjugate direction method proposed by Powell, is a kind of direct search method and has been applied to many engineering optimization problems for it was known as one of the most efficient method in unconstrained nonlinear optimizations. This technique is a modified or deflected gradient approach. If the function is quadratic in N variables, the procedure converges to the optimal solution in exactly N iterations. The method also gives good results for functions that are more complex than a quadratic form (Gue and Thomas, 1968). Powell’s method is much more efficient than steepest descent method. Furthermore, this method chooses successive directions without computation of the function’s gradient. This figure reduces the total computational burden drastically (Press et al., 1992). In spite of the above advantages the Powell’s method has, it has a typical drawback common in traditional NLP (Non-Linear Programming) algorithms. To get a good optimal solution, many initial starting points must be tried. Unfortunately it is practically impossible to locate the exact starting point for the global optimum.

GAs have been developed by John Holland, his colleagues, and his students at the University of Michigan. The primary monograph is Holland’s (1975) “Adaptation in Natural and Artificial Systems”. GAs are search algorithm based on the mechanics of natural selection and natural genetics. By abstracting nature’s adaptation algorithm of choice in artificial form we hope to achieve similar breadth of performance. In present times, GAs are known as very efficient heuristic algorithms, surmounting problems of traditional optimization algorithms, and are applied to many engineering problems, inclusive of water resources engineering. In this study, to reinforce the performance of GA, the strategies of multi-point crossover and reserving elite string are added to SGA (Simple Genetic Algorithm) in this study.

HS is a new heuristic algorithm, recently developed by Geem (2000) by mimicking the improvisation of music players. Musical performances seek a best state (fantastic harmony) determined by aesthetic estimation, as the optimization algorithms seek a best state (global optimum: minimum cost or maximum benefit or maximum efficiency) determined by objective function value.

There are two parameters introduced in HS, that is, HMCR and PAR (Pitch Adjusting Rate). HMCR is introduced to escape from local optima which can occur when all the parts of the global solution doesn’t exist initially in HM (Harmony Memory). PAR is adopted for improving solutions and escaping local optima. This option mimics the pitch adjustment of each instrument for tuning the ensemble. As newly developed algorithm, HS has much possibility to be improved. Various experiments are implemented to try to improve the performance of HS in this study.

The study area of this study is Daecheong dam basin, which occupies all but half of the Geum river basin with its catchment area of 4,134km². Daecheong multipurpose dam, located 150km above Geum river estuary, 16km north-east from Daejeon, and 16km south from Cheongju, was constructed in December, 1980. Meteorological data including evaporation are collected from 5 stations in Daecheong dam basin, that is, Daejeon, Cheongju, Jeonju, Boeun, and Geochang.

In the case of GAs or HS, there are optimization parameters; crossover probability, mutation probability, and population size are main optimization parameters in GAs, while HMCR, PAR, and harmony memory size are those in HS. Because these optimization parameters greatly influence the efficiency of optimization algorithms, precedent to comparison of optimization algorithms, sensitivity of these parameters are analyzed to find out best values for each optimization parameters for fair comparison. Sensitivity of optimization parameters are evaluated by SSQ (Sum of the Squares). Determined values of optimization parameters, analyzed above, are summarized in Table 1.

              Table 1  Analyzed optimization parameters

Three new strategies of roulette wheel selection, elimination of overlapping harmony, and special training of elite harmony are devised and evaluated to improve the HS’s performance. These strategies are evaluated by the criteria of SSQ in parameter calibration of the tank model. On the whole, elimination of overlapping harmony and special training of elite harmony enhance the performance of HS, while roulette wheel selection undermines the performance of HS in experiments. Two beneficial strategies of elimination of overlapping harmony and special training of elite harmony are simultaneously applied and named MHS. This combined strategy performs better than any other strategy of this study. Relative SSQ of MHS to simple HS is drawn in Figure 2.

MHS is compared with GA and Powell’s method. Initial values of parameters, required in Powell’s method, is set as the same as the recommended values by Ministry of construction and transportation et. al. (1999). SSQs of GA and MHS are quite smaller than that of Powell’s method. To check the properness of calibrated parameters, PEV (Percent Error in Volume)s of three techniques are compared. Though minimizing SSQ is selected as objective function, absolute values of PEV of three algorithms are proportional to the SSQs of these algorithms. Comparison of SSQ and PEV shows the superiority of heuristic algorithms, such as GA and HS, prior to traditional NLP algorithm (Powell’s method) in parameter calibration. This study shows GA or HS can be a reasonable choice for parameter calibration in tank model.

Objective function value of GA is a little better than that of MHS after 10,000 iterations. However, objective function value is not the only criteria to evaluate optimization algorithms. The most important goal of optimization is improvement (Goldberg, 1989). To answer to the question, how can we get to some good, “satisficing” (Simon, 1969) level of performance quickly, optimization algorithms evolved. Therefore, computation time is another important component to evaluate optimization algorithms. Until 10,000 iterations for GA and 10,000 and 30,000 iterations for HS and MHS, the computational time is recorded with PentiumⅡ 233Mhz CPU. Comparison of the computational time shows a relative superiority of HS and MHS. The average CPU time used by MHS is 74 seconds, only 5.75 % of GA’s computation time of 1,287 seconds. This significantly reduced computational time of MHS compared with GA up to the same iteration number of 10,000 is a big merit. MHS can optimize parameters up to more than 30,000 iterations in less CPU time than GA calculates for 10,000 iterations. The SSQ and PEV of MHS after 30,000 iterations are better than that of GA after 10,000 iterations.

Fig. 2  Relative SSQ of MHS

Fig. 3  Computational time to iterations

Powell’s method, the weakest algorithm in this comparison, has other drawbacks. First, initial values of parameters must be given. To decide initial values is another task for user of this model. Another problem, in fact, most serious problem of Powell’s method, is numerical dispersion. In this comparison, only 7 cases are succeeded to give results among 16 cases. These problems are, in a sense, common in traditional NLP algorithms. This handicap of Powell’s method supports another reason to select a heuristic algorithm, especially time-efficient MHS proposed in this study.

In this study various optimization algorithms are linked with a tank model to calibrate its 16 parameters. For the GA, crossover probability between 0.5 to 0.8, especially of 0.65, and low mutation probability of 0.01 produce good results whereas population size shows little correlation in performance. This characteristic is the same as previously proved properties in other applications of GAs by many researchers. For the HS, high HMCR, especially from 0.9 to 0.95, contributes excellent outputs, while PAR and harmony memory size show little correlation with improvement in performance. Geem(2000)’s previous sensitivity analysis of HMCR is confirmed in this study.

To enhance HS’s performance, three new strategies are devised and attempted in this study. Among these new strategies, two strategies of elimination of overlapping harmony and special training of elite harmony are recommended be used as supplemental algorithms of HS, while roulette wheel selection undermines the performance of HS.

Further, the superiority of heuristic algorithms, such as GA or HS, in parameter calibration of tank models is proved by a comparison with Powell’s method. Advantages of GA and HS over Powell’s method are: less erroneous parameter calibration, needlessness of setting initial values for the parameter values, and independence from numerical dispersions. Although GA gives slightly better results than MHS does in a same number of iteration, MHS performs surprisingly faster than GA in the same computing environment. In a given CPU time, MHS shows better calibration results than GA does for the tank model tested in this study.

Up to now, the biggest problem for using tank models in practice has been the parameter calibration. Well-trained engineer’s sense has been emphasized in parameter estimation. This study shows a possibility to avoid the problem by the application of heuristic algorithms, especially the Harmony Search algorithm.

Ministry of construction and transportation, KOWACO, and KICT (1999). Research about Optimization for Water Resources Planning (Ⅲ).