When implementing evolutionary algorithms (EAs), it is necessary to specify the method of parent selection, crossover and mutation, and control parameters such as population size and number of generations. These are discussed briefly below.
Parent Selection Schemes
One needs a method for identifying good parents to select for mating to produce the next generation. The following parental selection schemes have been predominantly used in the implementation of EAs:
1. Proportionate reproduction: in this scheme, individuals are chosen for birth in proportion to their fitness value. The probability that an individual from the ith class (having common fitness value fi) is chosen for selection in the t-th generation is:
where mjt is the number of individuals in the population at time t with fitness class j. Proportionate reproduction is usually implemented with a Monte Carlo or roulette wheel selection.
2. Ranking selection. In ranking selection, the population is sorted from best to worst. The number of copies that an individual should receive is given by an assignment function, and is proportional to the rank assignment of an individual.
3. Tournament selection. In tournament selection, a random number of individuals are chosen from the population (with or without replacement) and the best individual from this group is chosen as a parent for the next generation. This process is repeated until the mating pool is filled.
There are a variety of other selection methods including stochastic remainder and stochastic universal selection. For a comparative analysis of parental selection methods, see Goldberg and Deb [1991].
Control parameters
There have been a variety of studies on determining the best control parameter values to use for an EA, especially for genetic algorithms. The main problem is finding a set of control parameters which optimally balances exploration and exploitation: if crossover and mutation rates are very high, much of the space will be explored, but there is a high probability of losing good solutions and failing to exploit existing schema. Recommendations on control parameters can be found in Schaffer et al. [1989], Greffenstette [1986], and Koza [1992].
Schaffer et al. [1989] performed a detailed computational experiment to assess changes in the control parameters on the performance of genetic algorithms. They found that online average performance was sensitive to population size, mutation and crossover rates, and the number of crossover points used in mating. Two point crossover, where two crossover sites are picked at random and the intervening genetic material from parent 1 and parent 2 is switched between these sites, was mildly superior than one point crossover.
One area of concern using EAs is premature convergence of solutions. Premature convergence refers to a situation where most of the population members have similar bit strings without reaching the optimal point in the space. One way of preventing the loss of diversity is to not allow new strings that have a smaller Hamming distance than a specified value; however, this limits the searching of the EA. The methods to avoid premature convergence are fairly simple [Booker, 1987] and involve using two crossover points instead of one, introducing crossover more carefully so that it truly introduces variation (it is not useful to cross from two parents which are identical), and varying the crossover rate dynamically to compensate for the exploration/exploitation tradeoff. A common strategy is called incest prevention and involves a random mating of parents but only if their Hamming distance is above a certain threshold.
Problem Constraints
Evolutionary algorithms are often described as an unconstrained optimization method. Since most real world problems have constraints, these must be incorporated into the problem somehow. There are a variety of constraint implementation methods but these must be used with caution. For example, if one does not allow solutions which lead to constraint violations, it may lead to evaluation of many solutions before a feasible one is found, which can add significant computational time depending upon the amount of infeasibility in the space. Another technique for implementing method one is to modify the solution representation itself so as not to allow the creation of infeasible solutions. Repair algorithms or decoders are special operators which avoid the construction of illegal solutions. They may work reasonably well but are highly problem specific and may be computationally intensive to run. Additionally, they may destroy the inherent search properties of the EA or simulated annealing methods and may be difficult to implement. Penalty functions are more popular, but penalty functions combined with the objective are usually developed in an ad-hoc manner. Penalty functions may be linear, quadratic, logarithmic, etc. functions of the deviation of the constraints and/or the number of violated constraints. The performance of EAs will depend upon implementation of the constraints, as well as the choice of control parameter settings and parental selection scheme used.