Selection Strategies

<< Click to Display Table of Contents >>

Navigation:  Appendix A - Genetic Algorithm Internals and Advanced Topics >

Selection Strategies

Previous pageReturn to chapter overviewNext page

In Chapter 2 , we intentionally simplified the process of creating a new population generation.  Rather than having the population in each generation composed entirely of new individuals, we might want to pass some individuals from the previous population to the new one.  The number of these elite individuals is determined by the third argument called generation gap of the function SetStrategy. This argument determines the portion of the population that is renewed at each step.  Full renewal is denoted by 1, while evolution is suppressed by 0.  The number of individuals that will be left unchanged is given by the formula:

 

N_old_indiv = popul_size * (1 - gener_gap),

 

where N_old_indiv is the number of individuals left unchanged; popul_size is the size of a population; and gener_gap is the generation gap parameter.

 

The selection methods for the unchanged individuals may vary.  The first method is to select individuals just as they are selected for mating, i.e., the probability of an individual being selected is proportional to its fitness.  This method may be chosen by assigning the second argument of the SetStrategy function, the constant value PURE_SELECTION (as defined in GALIB32.BAS).

 

The second method is to select individuals strictly by their fitnesses.  This method is called the elitist strategy and the constant corresponding to this strategy is called ELITIST_SELECTION.  With this selection, the best individual is always passed to the next generation, while with pure selection there is only a higher probability of passing a more fit individual to the next generation.

 

Certain problems may arise when we select mates on the basis of their fitnesses.  Imagine a situation where one individual outperforms all others. In other words, its fitness significantly exceeds the mean value.  In the process of mating, this super-individual (stud?!?) will mate a great number of times with itself (this is not prohibited in genetic algorithms), and the offspring will be a direct copy of this mate (unless mutation occurs).  It would therefore be a good idea to somehow restrict the dynamic range of fitnesses.  The usual procedure is to recalculate fitnesses by the formula:

 

new_fit=a*old_fit+b,

 

where new_fit and old_fit are the new and the old values of fitness respectively, and constants a and b are determined on the condition that, after recalculation, the value of the mean fitness does not change, while the maximal fitness becomes S times greater than the mean one.  The ratio S is a parameter that can be changed by the user, and it is passed to the SetStrategy function in the fourth argument.  Usually values betwen 2.0 and 3.0 are used.