6.3.1.2 Fitness-Biased Selection Things get somewhat more interesting if we assume that in the initial population there is a genotype, say x, whose tness is unique and maximal. In this case one can show that, if selection favors higher tness, then an innite-population parent-selection-only EA will converge to a population consisting of the single genotype x. Stated another way, starting from any initial population P (0), the population trajectory P (t) converges to the simplex vertex < 0, 0, ..., 1, 0, 0, ..., 0 > that corresponds to x. The only dierence that a particular selection algorithm makes is in the speed of convergence. Under the same conditions, nite-population models also converge to a homogeneous xed point. However, that xed point is often not the same as the corresponding innitepopulation model since it is possible for x to disappear from the population due to the drift eects analyzed in the previous section. 123 124

CHAPTER 6. EVOLUTIONARY COMPUTATION THEORY 80 e c n e g r e v n o C 75 70 t n o P d e x F i i 65 60 Uniform stochastic selection t a s s e n t i 55 F n o i t a u p o P e g a r e v A l 50 45 40 35 30 0 50 100 150 200 250 Parent=Offspring Population Size Figure 6.2: Average xed-point tness for stochastic-uniform parent selection in a nonoverlapping-generation EA with m = n and no reproductive variation. This suggests a natural way to compare and contrast dierent selection algorithms: by studying which homogeneous populations they cause an EA to converge to, and by characterizing the time required to converge to a homogeneous population (see, for example, Goldberg and Deb (1990) and Back (1996)). For simplicity, these analyses assume an initial population containing m distinct genotypes in equal 1/m proportions and, in addition, that one of the genotypes has a unique, maximal tness. The results are summarized in the following sections.

Truncation Selection Truncation selection is intuitively one of the strongest (most elitist) forms of selection in that only the k most t individuals are selected from a pool of individuals of size r > k, the most extreme case being when k = 1. Within the selected set of k individuals, there is no further selection dierential. All are equally likely to be used. When truncation selection is used for parent selection, then k < m individuals are selected for breeding purposes. Within the selected set of k individuals, there is no further selection dierential. All individuals are equally likely to be used.

With an innite-population model, the top k/m proportion of the population P(t) is selected and replicated m/k times to create population P(t+1). If we then focus on the proportion of the population taken up by the best genotype, it starts in generation 0 at 1/m, and then increases each generation by a factor of m/k. So, at generation i, its proportion i is 1 m ( m . The expected takeover time is then given by the smallest value of i for which k ) i m. Solving this for i yields i (cid:6) ceiling(((log m) / (log(m/k))). m ( m 1 k )