Top (2010) 18: 303–320 DOI 10.1007/s11750-010-0154-8 O R I G I N A L PA P E R

Evaluation of the genetic algorithm parameters on the optimization performance: a case study on pump-and-treat remediation design Gamze Güngör-Demirci · Ay¸segül Aksoy

Received: 2 August 2010 / Accepted: 3 August 2010 / Published online: 26 August 2010 © Sociedad de Estadística e Investigación Operativa 2010

Abstract In this study, the impacts of different crossover and encoding schemes on the performance of a genetic algorithm (GA) in finding optimal pump-and-treat (P&T) remediation designs are investigated. For this purpose, binary and Gray encodings of the decision variables are tested. Uniform and two-point crossover schemes are evaluated for two different crossover probabilities. Analysis is performed for two P&T system optimization scenarios. Results show that uniform crossover operator with Gray encoding outperforms the other alternatives for the complex problem with higher number of decision variables. On the other hand, when a simpler problem, which had a lower number of decision variables, is solved, the efficiency of GA is independent of the encoding and crossover schemes. Keywords Optimization · Genetic algorithms · Uniform crossover · Two-point crossover · Binary coding · Gray coding Mathematics Subject Classification (2000) 90B90 · 90C27 1 Introduction Genetic algorithm (GA) is one of the methods used for combinatorial optimization. It is a probabilistic search that mimics the natural selection mechanism (Holland 1975). In this method, differentiability and/or convexity of the objective functions are not required. Different from the traditional optimization methods, the search is from a G. Güngör-Demirci · A. Aksoy () Department of Environmental Engineering, Middle East Technical University, ˙Inönü Bulvarı, 06531 Ankara, Turkey e-mail: [email protected] Present address: G. Güngör-Demirci Department of Environmental Engineering, Kocaeli University, Kocaeli 41380, Turkey

304

G. Güngör-Demirci, A. Aksoy

population of points instead of a single one. Despite that a globally optimum solution is not guaranteed, near optimal solutions are generated robustly (Weck et al. 1999). These favorable qualities facilitate the employment of GAs for large-scale and complex environmental optimization problems such as finding the optimal pump-andtreat (P&T) remediation designs. The objective functions for these systems constitute discontinuous, nonlinear and non-convex cost functions (McKinney and Lin 1994; Liu et al. 2000; Zheng and Wang 2002; Aksoy and Culver 2004; Chan Hilton and Culver 2005). Even though GAs have been widely used, selection and quantification of GA parameters can be critical for the outcome of optimization, especially for real life problems. Moreover, the actual performance of a particular algorithm can be dependent on the complexity of the problem solved. For a given problem, some experimentation with the GA parameters (population size, crossover type and probability, encoding scheme, etc.) may be required to increase the efficiency of the algorithm. In this study, the effects of crossover scheme and encoding of the decision variables on the performance of a GA for optimal P&T remediation designs are analyzed. In P&T, contaminated groundwater is extracted from the aquifer via pumping wells. Subsequently, withdrawn water is treated aboveground using various treatment methodologies. Treated water is then injected back into the aquifer or discharged into a receiving water body. P&T is one of the extensively applied aquifer remediation methods. However, mainly as a result of long operation times, significant costs are associated with it. The capital costs for 32 contaminated sites are reported to range from $290,000 to $19,000,000. The annual operating costs for these sites range from $110,000 to $4,600,000 (USEPA 2001). Given these rates, even small percentages of savings would be meaningful. Therefore, the effort to improve the performance of any search method in the optimal design of P&T is worthwhile. In literature, there are studies investigating the effect of crossover scheme on GA performance. However, there is no consensus on the advantages or disadvantages of using a specific kind of operator, since each may perform better for certain problems and may lead to poor results for the others (Dumitrescu et al. 2000). Vekaria and Clack (1998) investigate the performance of two-point and uniform crossover operators on L-SAT problems and deceptive trap functions. They state that uniform and two-point crossover operators work equally well. Nevertheless, the number of evaluations to reach the best solution is lower for two-point crossover. Guyaguler and Horne (2000) compare two-point and uniform crossover operators in optimizing the placement of oil production wells. The string length and the population size are 10 bits and 12, respectively. They show that the ratios of the runs that resulted in the correct optimum well locations are the same both for uniform and two-point crossover schemes. Yet, the number of iterations required to reach the optimum solution is slightly higher for uniform crossover. De Jong and Spears (1992) show that performances of twopoint crossover and uniform crossover are dependent on the population size for a 6th order hyperplane. On a 30 bit problem with 6 peaks, two-point crossover has a better efficiency than the uniform crossover for the large population size (1000). On the other hand, the opposite is true for the small population size (20). They indicate the tendency for faster convergence for small populations. This is attributed to higher disruption provided through uniform crossover which enhances the exploration of the search space. Conversely, disruption is less beneficial for larger populations, since the

Evaluation of the genetic algorithm parameters on the optimization

305

convergence rate is slower. De Jong and Spears (1992) state that an offspring can be created with uniform crossover anywhere in the space, but two-point crossover is restricted to smaller subsets. Fang and Ball (2007) compare one-point, two-point and uniform crossover operators for the calibration of spatially variable control parameters associated with a complex, multidimensional, physically distributed catchment modeling system. Each control parameter is represented by a real-coded gene, and the string length is 168. Uniform crossover is declared superior to both one-point and two-point crossover schemes in the crossover probability range of 0.6 to 1.0. Wardlaw and Sharif (1999) investigate the performance of one-point, two-point and uniform crossover operators for the optimization of a reservoir system operation, which is a deterministic, nonlinear and finite horizon problem. The string length is 144. According to their results, uniform crossover exhibits better performance in reaching the optimal solution. This is attributed to the enhanced diversity supplied in the population in comparison to one-point and two-point crossover operators. Selection of the encoding scheme is another aspect in GA efficiency adjustment. According to Hollstien (1971), Gray encoding may be preferable over binary encoding, since the bitwise representation of adjacent integers differs only by one bit. He also states that the solution is disrupted less by a single mutation in Gray encoding. In an experimental study, Bethke (1981) improves the performance of GA by use of Gray encoding. He computes the optimal solution for a nonlinear objective function using the decision variables encoded in 32-bit long strings. Caruana and Schaffer (1988) highlight better or equivalent performance with Gray encoding compared to binary encoding for six different test functions. In a reservoir system operation-optimization problem, Wardlaw and Sharif (1999) show more erratic progress towards better fitness when binary representation is used for the decision variables compared to Gray encoding. However, in terms of finding the optimum solution, both binary and Gray encodings reach the same solution. Nevertheless, binary encoding is faster than Gray encoding in terms of computational time. Andre et al. (2001) compare binary and Gray encoding for 21 different functions including Camelback, Branin, Hartman, etc. The number of decision variables ranges from 1 to 20 for these functions. The results show that convergence rate increases for Gray encoding. Nevertheless, the homogeneity of the population, which causes convergence to a local optimum, is not altered. According to Haupt and Haupt (1998), Gray encoding is not advantageous. It actually slows down the GA operation. In a numerical study employed on a Markov model, Chakraborty and Janikow (2003) reveal an insignificant difference between the performances of different encoding schemes. As described above, the impacts of encoding and crossover schemes on the efficiency of GA optimization can vary according to the problem studied. In this study, the outcome of optimization for different GA parameter combinations is analyzed for two different optimal P&T design scenarios. The first scenario aims at determining the best P&T policy with minimum system cost by optimizing the location of the pumping wells and the pumping rate. The second and the simpler one intends to find the optimal remediation time for a fixed pumping policy (i.e. pre-specified pumping well locations and pumping rates) that would possess the minimum cost. Although similar functions are used in objective functions and constraints, the complexities of the design problems are different due to different types and numbers of decision variables and pumping scheduling used for different scenarios. These also change the

306

G. Güngör-Demirci, A. Aksoy

characteristics of the solution space due to the nature of the objective function as will be presented in the next section. Binary and Gray encodings are considered along with uniform and two-point crossovers which will be described in the next section. For each crossover scheme, two different crossover probability values are evaluated. The next section provides the description of the GA methodology, crossover and encoding schemes along with the detailed definition of P&T remediation design scenarios and the optimization models. Then, the results are given and discussed in the results and discussion section. Finally, conclusions obtained from this study are provided in the last section.

2 Methodology The simulation–optimization approach is employed in order to determine the best remediation policy for the clean up of a contaminated aquifer. In this approach, a groundwater flow and contaminant transport simulation model is linked with a GA library. GA assigns the values to the decision variables, which are then sent to the simulation model as inputs. The simulation model quantifies the state variables using the decision variables and other inputs. Subsequently, state variables are conveyed to the GA in order to evaluate the fitness of a string based on the objective function. In this study, PGAPack, the GA library developed by Levine (1996) is utilized in linkage with BIO2D-KE, a groundwater flow and contaminant transport model (Culver et al. 1996; Earles 1996). In the mode PGAPack is used, GA starts with the generation of an initial population of strings randomly. Each string represents a set of decision variables, a candidate solution to the optimization problem. The fitness of each string in the initial population is evaluated based on the objective function and the constraints. Strings with higher fitness values have higher probabilities of being selected in creation of new strings. Elitism is used such that a given number of best strings in the population are copied to the next generation without being subject to any GA operators. The rest of the members of the next generation are determined through selection, crossover and mutation. For selection, tournament method is used. In this approach, two strings are selected randomly and the one with the better fitness value is copied to the temporary mating pool. Following the selection of strings to constitute the mating pool, crossover is applied with a certain crossover probability. Crossover operator is applied to exchange information between two strings, which results in generation of two new strings. The probability of two-point crossover is defined as the probability that a selected string will undergo crossover. For uniform crossover, on the other hand, it is the probability of a bit being selected from the first parent string (Levine 1996). The strings which do not undergo crossover become the members of the next generation without any modification, providing mutation operation is not employed due to the small mutation probability. If mutation is applied, the value of a randomly selected bit on a randomly selected string is altered to provide diversity in the population. Following this stage, generation of the strings for the next generation is complete. The cycle of evaluation, selection, crossover, and mutation continues until a stopping criterion is met. The flowchart of the simulation–optimization scheme is provided in Fig. 1.

Evaluation of the genetic algorithm parameters on the optimization

307

Fig. 1 Flowchart of the simulation–optimization scheme

In this study, two-point and uniform crossovers are tested as the crossover schemes. Two-point crossover is an enhancement over one-point crossover in terms of supplying diversity in the population. Providing that a template identifying the similarities at certain bit positions among strings is referred to as the schema (Holland 1975), one-point crossover may not combine all possible schemas in search. Moreover, one-point crossover may destroy the schemas with long defining lengths (Mitchell 1996). This situation is called “positional bias” by Eshelman et al. (1989). Two-point crossover, on the other hand, may have less probability of breaking the schemas with long defining lengths and higher probability of combining more schemas. However, it is not free from positional bias. Conversely, uniform crossover provides no positional bias. Yet, uniform crossover may be computationally intensive (Mitchell 1996; Ashlock 2000).

308

G. Güngör-Demirci, A. Aksoy

Fig. 2 Schematic representation of (a) two-point crossover (b) uniform crossover

In two-point crossover, two locations are determined on parent strings and the bits between these crossover sites are exchanged (Fig. 2a). In uniform crossover, each bit position of the two parent strings are considered for information swapping based on a randomly generated crossover mask. If the mask value for the corresponding bit location in the string is 1, then the bits of the parent strings are not swapped. However, if it is 0, the bits at the corresponding locations are exchanged (Chipperfield 1997). An example application is depicted in Fig. 2b. In representation of the decision variables, binary and Gray encoding schemes are used. The strings composed of series of 1s and 0s should be converted into real or integer values that can be processed by the simulation–optimization model. The translation of a binary string into a real value is established as follows xy = xymin + j

(xymax − xymin ) 2ky − 1

j = 0, . . . , 2ky − 1

(1)

where ky is the length of the string for decision variable y, xy is the value of the decision variable y, xymax is the maximum value the decision variable y can take, xymin is the minimum value the decision variable y can take, and j is the integer indicating the j th possible value for the decision variable y. Equation (1) is applicable both for binary and Gray encodings, however the way integer j is defined is different. In binary encoding, a binary string is decoded into an integer according to j=

k 

bi 2i−1

  j ∈ 0, 2ky − 1

(2)

i=1

where bi is the value of the ith bit and k is the string length. In this method, binary representations of two numbers may be dissimilar although they are contiguous in their decimal representations. For example, 7 and 8 are two consecutive integers but their four-bit binary representations are 0111 and 1000, respectively. Gray encoding uses a different, and may be a preferable mapping (Reeves and Rowe 2003). Encoding is established by reflecting the bits. Reflection is done by listing the original bits in reverse order and then coupling the reversed bits to the original ones. Then, a binary 0 and a binary 1 are added as the first bits of the original and the reflected bits, respectively (Wilf 1989). The schematic demonstration of this process is given in Fig. 3. As

Evaluation of the genetic algorithm parameters on the optimization

309

Fig. 3 The schematic representation of mapping of strings to define successive numbers in Gray encoding Table 1 Binary and Gray representations of integers from 0 to 15 (Wilf 1989)

m

Binary encoding

Gray encoding

M

Binary encoding

Gray encoding

0

0000

0000

8

1000

1100

1

0001

0001

9

1001

1101

2

0010

0011

10

1010

1111

3

0011

0010

11

1011

1110

4

0100

0110

12

1100

1010

5

0101

0111

13

1101

1011

6

0110

0101

14

1110

1001

7

0111

0100

15

1111

1000

a result of this mapping procedure, only one bit changes between subsequent numbers. Further details about Gray encoding can be found in Wilf (1989). Table 1 shows an example representation of integers from 0 to 15 with both binary and Gray encoding representations. Gray encoding is known to overcome the problem of “Hamming cliffs” which is observed in binary encoding. The distance between two strings is measured by Hamming distance, which can simply be defined as the number of bits that differ. The Hamming distance is always one in Gray encoding. This means that if two successive integers are represented bitwise, there will be a single bit that would be different. However, for binary encoding, there are Hamming cliffs where several bits can change in binary representations of two successive integer values. Even complementary bits can represent adjacent integers. For example, binary representations of 7 (0111) and 8 (1000) are complements of each other (Mathias and Whitley 1994; Rowe et al. 2004; Chakraborty and Janikow 2003). The impacts of crossover and decision variable encoding schemes on the performance of GA optimization in finding the optimal P&T remediation designs are analyzed for two different scenarios. These scenarios are employed to remediate a 2-dimensional hypothetical confined aquifer contaminated with tetrachloroethene (PCE), as given in Fig. 4. The aquifer is 300 m by 300 m. It is divided into 1600 square elements and 1681 grid points for numerical simulations. Aquifer is assumed to be heterogeneous in hydraulic conductivity (K), a parameter representing the ability to transmit water. In this study, nine K-fields are considered. All of these fields have the

310

G. Güngör-Demirci, A. Aksoy

Fig. 4 The aquifer, contaminant plume and candidate well locations for the first P&T design scenario (grey and black shaded circles) and pre-specified well locations for the second design scenario (black shaded circles only). Dark grey triangle shows the location of the contamination source

same average K. However, they differ in variances (0.2500, 0.7225 and 1.3225) and correlation lengths (15, 22.5 and 30 m) of the spatially variable K values. The fields are labeled K1 to K9. K1 represents the K-field having the smallest variance and the shortest correlation length. Although K variance is the same, correlation length increases from K1 to K3. K4 to K6 and K7 to K9 have the medium and highest K variance values, respectively. Similarly, correlation lengths of the spatially distributed K values increase from K4 to K6 and from K7 to K9 for the given K variances. Further details about the heterogeneity conditions in K are not given since they are not crucial for the aim of this study. However, it should be noted that one can expect to have different optimal designs due to different heterogeneity conditions in K-fields. The objective function in the optimization model used for the first P&T remediation design scenario aims to minimize the capital and operational costs of the system while satisfying the system constraints. The optimization model is adapted from Aksoy and Culver (2004). Granulated activated carbon (GAC) adsorption technology is used to remove PCE from the withdrawn groundwater. The decision variables are the locations of the pumping wells and the pumping rate. 25 candidate well locations (both grey and black shaded circles in Fig. 4) are used. Wells that are selected as active are assumed to pump at the same rate. The pumping rate is represented by the first 6 bits in a GA string. The next 25 bits are the pointers that specify whether a candidate well is active or not. If a pointer value is “1”, then that well is active, pumping at the rate given by the first 6 bits of the GA string. The remediation period is fixed and 1260 days for all K-fields. Among the system constraints are the upper bounds on the maximum aqueous and total (aqueous and sorbed) PCE concentrations in the aquifer at the end of the remediation time. Upper bound on the maximum allowable hydraulic head decline is another constraint. For the first P&T design scenario, the upper and lower bounds for the pumping rate are enforced through decision variable encoding such that the pumping rate is allowed to take values within the range defined by the relevant constraint.

Evaluation of the genetic algorithm parameters on the optimization

311

Similarly, in the second P&T design scenario, the goal of the optimization model is to minimize the capital and operational costs of the remediation system while satisfying the system constraints. In the optimization model, the length of the remediation period is the only decision variable. The locations of the active wells are pre-specified (black shaded circles in Fig. 4). Each of these wells pumps at a fixed rate of 25 m3 /day. The remediation period is represented by 10 bits. The first 9 bits of the string is the remediation time itself. The 10th bit is a multiplier. If it is 0, the remediation time represented by the first 9 bits is multiplied by 1. If it is 1, then the remediation time is multiplied by 2. In the second P&T design scenario, the constraints are on the maximum allowable aqueous and total PCE concentrations as well as on the allowable decline in head at the end of the remediation time. The constraints on upper and lower bounds for the remediation period are enforced through decision variable encoding. Given the above brief definition about the design scenarios employed, the general optimization model can be given:   ST E   Gcarbon,t + Gcapwell,e + Gcaptreat × [1 + Pen] (3) Minimize Gpump + Qz ,Iz or tm

t=1

e=1

where Gpump = 0.00038tm

E    Qe (71.5 − he )

(4)

e=1

Gcarbon,t = 0.042ts (Ct )0.52 Qtot Gcapwell,e = 5543Iz (de )0.299 Gcaptreat = 100,000 integer[0.0005Qtot + 0.5] Qtot =

E 

(5) (6) (7) (8)

Qe

e=1

Ct =

  E Ce,t0 − Ce,t1 1  Qe Qtot 2

(9)

e=1



equation (13)

Pen =

ωb νb

(10)

b=equation (11)

subject to ∗

= 1 mg/L Caq max ≤ Caq ∗

∗ Ctot max ≤ Ctot = Caq (Kd ρb + n) = 0.852 mg/(L aquifer)

(12)

Max|ho,gp − hf,gp | ≤ 15 m gp = 1, . . . , GP

(13)

0.0 ≤ Qe ≤ 8L/s

(14)

z∈Z

(only for the first scenario)

(11)

312

G. Güngör-Demirci, A. Aksoy

1 ≤ tm ≤ 7156 days (only for the second scenario)

(15)

where Gpump is the pumping operational cost for management period tm ($), Gcarbon,t is the operational cost of GAC treatment facility during simulation time step t ($), Gcapwell,e is the capital and installation costs for well e ($), Gcaptreat is the capital cost of GAC adsorbers ($), E is the total number of active pumping wells (–), ST is the total number of simulation time steps (–), tm is the length of management period (days), Qe is the volumetric pumping rate at active well e (L/s), he is the hydraulic head relative to well depth at the end of management period tm at pumping well e (m), ts is the length of simulation time step (days), de is the depth of well e (m), Ct is the weighted average influent concentration to adsorbers for simulation time step t (mg/L), Qtot is the total pumping rate during management period tm (L/s), Ce,t0 is the aqueous contaminant concentration at pumping well e at the beginning of simulation time step t (mg/L), Ce,t1 is the aqueous contaminant concentration at pumping well e at the end of simulation time step t (mg/L), Iz is the pointer (=1 if well is active, =0 if well is inactive), GP is the number of grid points (–), ho,gp is the initial ∗ is the aquehead at grid point gp (m), hf,gp is the final head at grid point gp (m), Caq ∗ ous concentration goal (mg/L), Ctot is the total concentration goal (mg/L of aquifer), Caq max is the maximum aqueous concentration in aquifer at the end of management period tm (mg/L), Ctot max is the maximum total concentration in aquifer at the end of management period tm (mg/L of aquifer), Kd is the equilibrium distribution coefficient (assumed as 0.36) (cm3 /g), ρb is the dry bulk density of porous media (assumed as 1.81) (g/cm3 ), n is the porosity (assumed as 0.2) (–), Pen is the total penalty due to violations on constraints defined by (11)–(13), ωb is the constraint weight on bth constraint, and νb is the constraint violation on bth constraint. As given in (3), the objective function includes nonlinear and discontinuous terms. Actually, this makes the use of exact optimization methods infeasible for the cases studied in this study. For the handling of constraint violations, the multiplicative penalty method is used (Chan Hilton and Culver 2000). This approach is a robust method for constraint enforcement in GA applications for groundwater remediation problems. In this method, a penalty factor (10) is calculated in proportion to the magnitudes of violations (νb ) in constraints. Actual cost is then multiplied by this factor. If there are no constraint violations, then the total cost of the potential policy is equal to the true value of the evaluation cost function. Otherwise, the cost will be increased by a factor of (1 + Pen) as shown in (3). In this study, the constraint weights for the constraint (ωb ) are taken as 50. In GA search for the optimum P&T designs for both design scenarios, the population size is chosen as 120. The total string length for both scenarios is 31. Therefore, although not all of the bits are utilized in encoding of the decision variables for the second design scenario, optimization results are compared for the same string length. In PGAPack, the default crossover probabilities are 0.85 and 0.5 for two-point and uniform crossovers, respectively. In this study, these default values are used. In addition, crossover probability values are exchanged and 0.85 and 0.5 are tested for uniform and two-point crossovers, respectively. The mutation probability is 0.03. GA run is terminated when there is no change in the best evaluation value in 30 consecutive generations. Multiple runs with different initial random populations are executed for each K-field (K1 to K9). These are called the replicate runs.

Evaluation of the genetic algorithm parameters on the optimization

313

3 Results and discussion In complex engineering problems, the best solution obtained through optimization is generally regarded as the “optimum” solution. This is due to the fact that, for such problems, mostly conditional, discontinuous, nonlinear and non-convex functions may be of concern. This may complicate convergence to global optimum. In this regard, the solution obtained through GA optimization in each run will be referred to as the optimum solution. However, since the aim of this study is to investigate the performance of GA for different GA parameters, the actual global optimum solution for a specific K-field is critical for the evaluation of the goodness of the results. Therefore, global optimum P&T policies are determined using exhaustive trial-and-error where the starting points for search are the optimal GA solutions to the corresponding cases as well as the other possible designs for the first design scenario. Results obtained by GA optimization for different GA parameters and initial populations of strings are compared against the global optimum values. For comparison an F value is defined which indicates the ratio of the best value obtained within replicates to the global optimum for a specific K-field. The efficiency of GA for different GA parameters is also evaluated by the repeatability of the outcome for a K-field or checking the variation in optimal results obtained in replicate GA runs. In these replicate runs for a specific K-field, the only difference is the initial populations of strings. All other assumptions are the same. The variations within the replicate runs are additionally defined by the relative errors (Andre et al. 2001). For a given K-field, first, the relative error for each individual run (within replicates) is calculated using (16). Then the average of relative errors for the replicates is determined and established as the average relative error for each K-field (K1 to K9). Erel =

S − Sglobal Sglobal

(16)

where Erel is the relative error, S is the optimal solution obtained through GA optimization in a run, and Sglobal is the global optimum solution. The last criterion used to assess the efficiency of GA optimization for P&T remediation design is the convergence rate. This is defined both by the CPU time of the run and the number of generations required to reach the optimum solution. The runs are executed on Intel Xeon 5110 processors having 1.6 Ghz frequency. 3.1 First design scenario—optimization with respect to pumping wells Runs are executed for binary encoding using different crossover probabilities and schemes. Each run is repeated 5 times using different initial populations. Regardless of the crossover probabilities tested in this study, uniform crossover in combination with Gray encoding outperforms the others. For this combination, 49% of the total 45 runs for all K-fields end up with the global optimum solutions for the crossover probability of 0.85. For the crossover probability of 0.5, this quantity is 51%. It is possible to reach the global optimum solutions within respective five replicates for all K-fields using uniform crossover with Gray encoding. This is shown by the F values in Fig. 5. However, this is not the case for the other crossover and decision variable

314

G. Güngör-Demirci, A. Aksoy

Fig. 5 F (the ratio of the best value obtained within replicates to the global optimum) values for different K-fields for the first design scenario

encoding combinations. For example, two-point crossover with binary encoding and 0.5 crossover probability are not sufficient to converge to the optimum solutions in any of the K-fields (Fig. 5). For the crossover probability of 0.85, it is possible to attain the global optimums in 4 out of 9 K-fields. Therefore, for two-point crossover with binary encoding, the crossover probability of 0.85 results in a better efficiency in terms of the number of runs reaching the global optimums compared to the crossover probability of 0.5. This indicates that the crossover probability of 0.5 is not sufficient to explore the search space and the algorithm is not able to move away from the local optimum points, when two-point crossover and binary encoding are employed given the other GA parameter values used in the study. When all K-fields are considered, 29% of the total 45 runs end up at the global optimums for the crossover probability of 0.85. This value is 0% for the crossover probability of 0.5. When two-point crossover with crossover probability of 0.85 is tested for Gray encoding, in only 2 of 9 Kfields the global optimums are obtained within the respective replicates. In overall runs for all fields, just 4% of 45 runs reach the global optimums. Therefore, in this context, Gray encoding deteriorates the performance of GA for two-point crossover. Uniform crossover and binary encoding combination has intermediate performance compared to two-point crossover with binary encoding and uniform crossover with Gray encoding. For the crossover probabilities of 0.85 and 0.5, global optimum values are obtained for 6 and 5 K-fields, respectively. In overall, in 22% and 20% of the total 45 runs, global optimums are reached for the crossover probabilities of 0.85 and 0.5, respectively. Figure 6 shows the average, minimum and maximum of five replicate runs executed for each of the 9 different K-fields for different decision variable encoding alternatives, crossover schemes and crossover probability values. In this figure, the difference between the minimum and the maximum remediation costs shows the ex-

Evaluation of the genetic algorithm parameters on the optimization

315

Fig. 6 The average, minimum and maximum P&T remediation costs for five replicate runs for different K-fields for the first design scenario Table 2 Average of Erel (%) of 5 replicate runs for 9 different K-fields for the first design scenario K-fields

TP (0.85) /Bin

TP (0.5) /Bin

Uni (0.85) /Bin

Uni (0.5) /Bin

TP (0.85) /Gr

Uni (0.85) /Gr

Uni (0.5) /Gr

K1

0.3

14.6

10.4

5.3

2.5

0.3

2.8

K2

0.8

12.0

7.4

0.8

9.4

0.0

0.2

K3

0.0

13.5

9.8

0.2

3.6

2.1

1.2

K4

11.8

12.1

11.3

6.9

3.2

4.0

2.8

K5

3.2

12.9

6.4

11.9

7.6

0.4

0.8 0.4

K6

1.9

9.8

4.8

4.8

3.0

0.9

K7

8.0

12.7

11.5

12.6

8.8

3.6

4.1

K8

12.2

13.6

4.9

10.4

3.9

1.6

0.1

K9

7.7

21.0

14.5

9.6

15.5

12.4

6.6

AVG

5.1

13.6

9.0

6.9

6.4

2.8

2.1

tent of variation in the optimal results when different initial population of strings are considered. Table 2 summarizes the relative error in each run with respect to the global optimum. In Fig. 6, when all K-fields are considered, the average variation in optimal remediation costs achieved within five replicates is $8,127 for the combination of binary encoding and two-point crossover with a crossover probability of 0.85. The second and third rankings for the average variations in the optimal costs within replicates are for the crossover probabilities of 0.5 and 0.85, respectively, for uniform crossover with Gray encoding. The respective values are $9,847 and $10,303. The worst difference is $23,656 for binary encoding in combination with uniform crossover with the crossover probability of 0.85. Yet, these values alone are not conclusive in terms of the efficiency of a certain GA parameters combination. For example, replicates for a certain set of GA parameters may end up in the same local optimum which would result in a variation of $0. In fact, when Table 2 is exam-

316

G. Güngör-Demirci, A. Aksoy

Fig. 7 Average CPU times and the average number of generations realized to reach the optimum solutions (for all runs of all K-fields) for the first design scenario

ined, it is noticed that the minimum average Erel values (2.1% and 2.8%) are for uniform crossover with Gray encoding. For two-point crossover with the crossover probability of 0.85, Gray encoding increases the average Erel to 6.4%. The highest average Erel (13.6%) is for the combination of two-point crossover, binary encoding, and crossover probability of 0.5. The next highest average Erel quantities (9.0% and 6.9%) are for the GA parameter sets constituting of uniform crossover and binary encoding with different crossover probabilities. Figure 7 depicts the average CPU time and the average number of GA generations required to reach the optimum solution in all runs conducted for specific combinations of GA parameters. It should be noted that the CPU times can be high due to BIO2D-KE, the contaminant transport simulation model linked with PGAPack, in which the simulation time step is 1 day. In general, the uniform crossover consumes more CPU time compared to two-point crossover regardless of the encoding and crossover probability. This observation is in line with the observation of Ashlock (2000). However, in return of higher CPU time consumed for runs, a higher percentage of the total runs with a specific combination of GA parameters end up in the global optimum solutions. For example, only an average of 23.7 hours of CPU is spent for runs with two-point crossover, crossover probability of 0.5, and binary encoding. Yet, all of the runs finalize at the local optimum points. With the crossover probability of 0.5, GA cannot jump into another search region for the mutation rate and stopping criterion applied. The highest CPU hours are employed for uniform crossover with Gray encoding. On the average, 54.9 and 51.4 hours are required for the crossover probabilities of 0.85 and 0.5, respectively. For these cases, 22 and 23 of the runs (out of 45) converge to the global optimum values. The number of generations required to reach the optimal solutions are in agreement with the CPU times. In general, compared to two-point crossover, uniform crossover requires higher number of GA generations to reach the optimal solutions. Two-point crossover, binary encoding and the crossover probability of 0.5 converge in an average of 13.5 generations for all K-fields. Yet, none of the final points are the global optima. For uniform crossover, Andre et al. (2001) and Sharma and Irwin (2003) report that the use of Gray encoding increases the convergence rate of GA in terms of less

Evaluation of the genetic algorithm parameters on the optimization

317

Fig. 8 Variation in the optimal remediation costs within three replicate runs for different K-fields for the second design scenario

number of evaluations required for the optimal solution. Hamming cliffs problem can be eliminated with Gray encoding which significantly alters the number of local optima (Mathias and Whitley 1994). On the other hand, Haupt and Haupt (1998) state that Gray encoding slows down the GA optimization. Compared to two-point crossover, uniform crossover can put the features together without considering their relative locations on the string. This ability can offset the disruptive behavior of uniform crossover on the good features of the population (Dumitrescu et al. 2000; Mitchell 1996). In our study, we show that Gray encoding and uniform crossover demand higher CPU time, but in return, it is possible to obtain the global optimum with higher possibility. 3.2 The second design scenario—optimization with respect to management time Since the second design scenario is simpler in terms of the number and variety of the decision variables, 3 replicate runs are conducted for each GA parameter set and each K-field. For the second design scenario, comparison is made for different encoding and crossover schemes. However, only a single crossover probability value is chosen for each crossover type. These values are 0.85 and 0.5 for two-point and uniform crossovers, respectively, based on the results of the first design scenario. In general, for the simpler optimization problem, relative to the first design scenario, both crossover schemes perform equally well with either binary or Gray encoding. It is possible to reach the global optimum values for all K-fields except K1. Yet, for K1, the difference between the best management time and the global optimum is only 1 day, which is negligible compared to 3459 days. Figure 8 shows the variations in the remediation costs for each K-field within the three replicates of a given set of crossover and encoding schemes. Except for uniform crossover for K6, the variations among the remediation costs are either negligibly small or do not exist. This indicates

318

G. Güngör-Demirci, A. Aksoy

Fig. 9 Average CPU times and the generation numbers realized to reach the optimum solutions (including all runs for all K-fields) for the second design scenario

that both encoding and crossover types are successful in finding the global optimum solution within three replicates in general. Figure 9 depicts the efficiency of algorithms in terms of both the CPU time spent during the runs and the number of generations required to reach the optimum solutions. For all four different combinations of crossover and encoding types, the average simulation time is almost the same showing that none of the crossover and encoding schemes provided an advantage over the other in terms of the convergence rate, despite slightly higher generation numbers required for Gray encoding. All of these results show that, for the simpler problem, any of the four options can be used and the optimization result will be insensitive to the GA parameters tested in this study. 4 Conclusions In this study, the impacts of crossover and encoding schemes on the performance of GA optimization for P&T remediation system designs are studied. In general GA applications, there are no straightforward rules in literature to determine which crossover alternative, encoding scheme and crossover probability should be used for the most efficient execution of search for optimal solution. In this study, it is shown that the choice of these parameters can be crucial for complex P&T remediation design problems that are associated with high number of decision variables, such as the selection of well locations and pumping rates. For the P&T remediation system design scenarios evaluated in this study, it is shown that uniform crossover and Gray encoding combination exhibit the best performance in terms of reaching the global optimum value, despite longer computational time. In real life applications, such as designing the remediation systems, obtaining the solution in a reasonable time is a concern. However, GA parameter combinations that require longer computational effort should not be overlooked, since they may lead in obtaining better solutions. This in turn, may supply significant savings in capital and operational costs of remediation that can reach millions of dollars for a contaminated site. However, for simpler problems with small number of decision variables, the sensitivity of the optimization efficiency to different GA parameters may not be that significant.

Evaluation of the genetic algorithm parameters on the optimization

319

Acknowledgements This study was financially supported by the State Planning Agency (Grant No: BAP-08-11-DPT2002K120510-DK17). The computational resources for this research are provided by The Scientific and Technological Research Council of Turkey (TUBITAK) through TR-Grid e Infrastructure Project in which Middle East Technical University is a hosting institution (http://www.grid.org.tr).

References Aksoy A, Culver TB (2004) Impact of physical and chemical heterogeneities on aquifer remediation design. J Water Resour Plan Manag 130:311–320 Andre J, Siarry P, Dognon T (2001) An improvement of the standard genetic algorithm fighting premature convergence in continuous optimization. Adv Eng Softw 32:49–60 Ashlock D (2000) Evolutionary computation for modeling and optimization. Springer, New York Bethke AD (1981) Genetic algorithms as function optimizers. Dissertation, Univ of Michigan Caruana RA, Schaffer JD (1988) Representation and hidden bias: Gray vs. binary coding for genetic algorithms. In: Laird J (ed) Proceedings of the 5th international conference on machine learning. University of Michigan, Ann Arbor, pp 153–161 Chakraborty UK, Janikow CZ (2003) An analysis of Gray versus binary encoding in genetic search. Inf Sci 156:253–269 Chan Hilton AB, Culver TB (2000) Constraint handling for genetic algorithms in optimal remediation design. J Water Resour Plan Manag 126:128–137 Chan Hilton AB, Culver TB (2005) Groundwater remediation design under uncertainty using genetic algorithms. J Water Resour Plan Manag 131:25–34 Chipperfield A (1997) Introduction to genetic algorithms. In: Zalzala AMS, Fleming PJ (eds) Genetic algorithms in engineering systems. IEE control engineering series, vol 55. The Institution of Electrical Engineers, Stevenage, pp 1–45 Culver TB, Earles TA, Gray JP (1996) Numerical modeling of in situ bioremediation with sorption kinetics. DAAL03-91-C-0034; TCN95-066, US Army Research Office, North Carolina De Jong KA, Spears WM (1992) A formal analysis of the role of multi-point crossover in genetic algorithms. Ann Math Artif Intell 5:1–26 Dumitrescu D, Lazzerini B, Jain LC, Dumitrescu A (2000) International series of computational intelligence, evolutionary computation. CRC Press, Boca Raton Earles TA (1996) Modeling rate limited sorption. Dissertation, Univ of Virginia Eshelman LJ, Caruana R, Schaffer JD (1989) Biases in the crossover landscape. In: Schaffer JD (ed) Proceedings of the 3rd international conference on genetic algorithms, George Mason University, Fairfax, pp 10–19 Fang T, Ball JE (2007) Evaluation of spatially variable control parameters in a complex catchment modelling system: a genetic algorithm application. J Hydroinform 9:163–173 Guyaguler B, Horne R (2000) Optimization of well placement. J Energy Resour Technol 122:64–70 Haupt RL, Haupt SE (1998) Practical genetic algorithms. Wiley, New York Holland JH (1975) Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. University of Michigan Press, Ann Arbor Hollstien RB (1971) Artificial genetic adaptation in computer control systems. Diss Abstr Int B 32:1510 Levine D (1996) Users guide to the PGAPack parallel genetic algorithm library. ANL-95/18, Argonne National Laboratory, Argonne Liu W, Medina M, Thomann W Jr, Piver WT, Jacobs TL (2000) Optimization of intermittent pumping schedules for aquifer remediation using genetic algorithm. J Am Water Resour Assoc 36:1335–1348 Mathias KE, Whitley LD (1994) Transforming the search space with Gray coding. In: Proceedings of the 1st IEEE international conference on evolutionary computation. IEEE Press, New York, pp 513–518 McKinney DC, Lin MD (1994) Genetic algorithm solution of groundwater management models. Water Resour Res 30:1897–1906 Mitchell M (1996) An introduction to genetic algorithms. MIT Press, Cambridge Reeves CR, Rowe JE (2003) Genetic algorithms: principles and perspectives, a guide to GA theory. Kluwer Academic, Dordrecht Rowe J, Whitley D, Barbulescu L, Watson JP (2004) Properties of Gray and binary representations. Evol Comput 12:47–76 Sharma SK, Irwin GW (2003) Fuzzy coding of genetic algorithms. IEEE Trans Evol Comput 7:344–355

320

G. Güngör-Demirci, A. Aksoy

US Environmental Protection Agency (USEPA) (2001) Cost analyses for selected groundwater cleanup projects: pump and treat systems and permeable reactive barriers. Solid Waste and Emergency Response, EPA-542-R-00-013 Vekaria K, Clack C (1998) Selective crossover in genetic algorithms: an empirical study. In: Eiben AE, Bäck T, Schoenauer M, Schwefel HP (eds) Proceedings of the 5th conference on parallel problem solving from nature. Springer, Berlin, pp 438–447 Wardlaw R, Sharif M (1999) Evaluation of genetic algorithms for optimal reservoir operation. J Water Resour Plan Manag 125:2533 Weck B, Karr CL, Freeman LM (1999) Gauss-Legendre integration using genetic algorithms. In: Karr CL, Freeman LM (eds) International series of computational intelligence, industrial applications of genetic algorithms. CRC Press, Boca Raton, pp 243–256 Wilf HS (1989) Combinatorial algorithms: an update. CBMS-NSF regional conference series in applied mathematics, vol 55. Society of Industrial and Applied Mathematics, Philadelphia Zheng C, Wang P (2002) A field demonstration of the simulation optimization approach for remediation system design. Ground Water 40:258–265