Selection

It seems that the population diversity and the selective pressure are the two most im-portant factors in the genetic search [14]. They are strongly related, since an increase in the selective pressure decreases the population diversity and vice versa. If the population becomes too homogeneous the mutation will almost be the only factor causing variation in the population. Therefore, it is very important to make the right choice when determining a selection method for GA.

A selection mechanism is necessary when selecting individuals for both reproducing and surviving. A few methods are available and they all try to simulate the natural selection, where stronger individuals are more likely to reproduce than the weaker ones. Before discussing those methods, it is explained how the selective pressure influences the conver-gence of the algorithm,

Selective pressure

A common problem when applying GA, is a premature or rapid convergence. A con-vergence is a measurement of how fast the population improves. Too fast improvement

indicates that the weaker individuals are dropping out of the population too soon, i.e.

before they are able to pass their characteristics on. The selective pressure is a measure-ment of how often the top individuals are selected compared to the weaker ones. Strong selective pressure means that most of the time top individuals will be selected and weaker individuals will seldom be chosen. On the other hand, when the selective pressure is weak, the weaker individuals will have a greater chance of being selected.

p1 p2 p3

Figure 2.3 illustrates this for a population of five solutions with fitness values according to the size of its quadrangle. The y-axis shows the proba-bility for each solution of being chosen. The line sp1 shows a strong selective pressure, where the top solutions are much more likely to be cho-sen than the weaker ones and line sp2 shows weaker selective pressure where the difference between the probabilities of selecting the solu-tions is smaller.

Strong selective pressure encourages rapid con-vergence but, on the other hand, too weak se-lective pressure makes the search ineffective.

Therefore, it is critical to balance the selective

pressure and the population diversity to get as good solution as possible.

Roulette Wheel Method

Firstly, there is a proportional selection process called, the Roulette Wheel, which is a frequently used method. In section 2.2.3, it is explained how every individual is assigned a fitness value indicating its quality. In the roulette wheel method, the probability of choosing an individual is directly proportional to its fitness value.

Figure 2.4 illustrates the method in a simple way for a problem having five individuals in a population. Individual P1 has a fitness valuef1, P2 hasf2, etc. Considering a pin at the top of the wheel, one can imagine when spinning the wheel that it would most frequently point to individual P3 and that it in the fewest occasions would point to individual P4.

Consequently, the one with the largest fitness value becomes more likely to be selected as a parent than one with a small fitness value.

2.2 Genetic Algorithms 25

Figure 2.4: Roulette Wheel method.

The drawback of the Roulette Wheel Method is that it uses the fitness values directly.

That can cause some problems e.g. when a solution has a very small fitness value compared to the others, resulting in very low probability of being chosen. The ranking method in next chapter has a different approach.

Ranking

The second method is the Ranking method, which has been giving improving results [16]. It provides a sufficient selective pressure to all individuals by comparing relative goodness of the individuals instead of their actual fitness values. It has been argued that in order to obtain a good solution using GA, an adequate selective pressure has to be maintained on all the individuals by using a relative fitness measure [16]. Otherwise, if the population contains some very good individuals, they will early on become predominant in the population and cause a rapid convergence.

In Ranking, the individuals are sorted in ascending order according to their fitness. A function depending on the rank is used to select an individual. Thus it is actually selected proportionally to its rank instead of its fitness value as in the roulette wheel method. For instance, the selection could be based on the probability distribution below.

p(k) = 2k

M(M+ 1) (2.13)

The constantk denotes thekth individual in the rank andM is the size of the population.

The best individual (k = M) has a probability _M+1² of being selected and the worst individual (k = 1) has _M(M+1)² of being selected. The probabilities are proportional depending on the population size instead of fitness value.

The advantage of the Ranking method is that it is better able to control the selective pressure than the Roulette Wheel method. There are though also some drawbacks. The method disregards the relative evaluations of different solutions and all cases are treated uniformly, disregarding the magnitude of the problem.

Tournament Selection

The Tournament Selection is an efficient combination of selection and ranking methods.

A parent is selected by choosing the best individual from a set of individuals or a subgroup from the population. The steady-state algorithm on page 21 requires only two individuals for each parent in every iteration and a third one to be replaced by the offspring at the end of the iteration. The method is explained considering the steady-state algorithm.

At first, two subgroups of each S individuals are randomly selected, since two parents are needed. If k individuals of the population were changed in each iteration, the number of subgroups would be k. Each subgroup must contain at least two individuals, to enable a comparison between them. The size of the subgroups influences the selective pressure, i.e.

more individuals in the subgroups increase the selection pressure on the better individuals.

Within each subgroup, the individuals compete for selection like in a tournament. When selecting individuals for reproduction the best individual within each subgroup is selected.

On the other hand, the worst individual is chosen when the method is used to select a individual to leave the population. Then the worst individual will not be selected for reproduction and more importantly the best individual will never leave the population.

The Tournament Selection is the selection method that will be used in this project for both selection of individuals for reproduction and surviving. It combines the characteristics of the Roulette Wheel and the Ranking Method and is without the drawbacks of these methods have.