Reproduction Phase, Crossover We think of crossover as mating in biological terms, which at a fundamental biological level involves the process of combining chromosomes. The crossover operation operates on the mating pool M(k). First, you specify the"crossover probability"P (usually chosen to be near one since when mating occurs in biological systems, genetic material is swapped between the parents ). The procedure for crossover consists of the following steps 1. Randomly pair off the individuals in the mating pool Mk)(i.e, form pairs to mate by the flip of a coin). If there are an odd number of individuals in M(k), then, for instance, simply take the last individual and pair it off with another individual who has already been paired of 2. Consider chromosome pair 0'and 0, that was formed in step 1 Generate a random number rE[O, 1] a)If r<P then cross over e/and 0. To cross over these chromosomes select at random a"cross site"and exchange all the digits to the right of the cross site of one string with those of the other. This process is pictured in Figure 4.5. In this example the cross site is position five on the string, and hence we swap the last eight digits between the two strings. Clearly, the cross site is a random number between one and the number of digits in the string minus one (b)If r>pe then we will not cross over; hence, we do not modify the strings, and we go to the mutation operation 011234 678910111213 Switch these two parts of the strings 012345678910111213 Cross site FIGURE 4.5 Crossover operation examples (c)Repeat step 2 for each pair of strings that is in Mk) As an example, suppose that s=10 and that in step I above we randomly pair off the chromosomes. Suppose that 0 and 0(=5, i=9)are paired off where 0=+2.9845 and 0=+1.9322 Suppose that Pe =0.9 and that when we randomly generate r we get r=0. 34. Hence, by step 2 we will cross over 0 and 0. According to step 2 we randomly pick the cross site Suppose that it is chosen to be position three on the string. In this case the strings that are produced by crossover are 63=+29322andb=+19845 Besides the fact that crossover helps to model the mating part of the evolution process, why lgorithm perform crossover? Basically, the crossover operation perturbs the parameters near good positions to try to find better solutions to the optimization problem. It tends to help perform a localized search around the more fit individuals(since on average the individuals in the mating pool at time k are more fit man the ones in the population at time k) Reproduction Phase, Mutation Like crossover, mutation modifies the mating pool (i.e, after selection has taken place). The operation of mutation is normally performed on the elements in the mating pool after crossover has been performed. The biological analog of our PDF文件使用" pdffactory Pro"试用版本创建ww. fineprint,com,cnReproduction Phase , Crossover We think of crossover as mating in biological terms, which at a fundamental biological level involves the process of combining chromosomes. The crossover operation operates on the mating pool M(k). First, you specify the "crossover probability" pc (usually chosen to be near one since when mating occurs in biological systems, genetic material is swapped between the parents). The procedure for crossover consists of the following steps: 1. Randomly pair off the individuals in the mating pool M(k) (i.e., form pairs to mate by the flip of a coin). If there are an odd number of individuals in M(k), then, for instance, simply take the last individual and pair it off with another individual who has already been paired off . 2. Consider chromosome pair j q and i q , that was formed in step 1. Generate a random number r Î[0,1]. (a) If r < pc then cross over j q and i q . To cross over these chromosomes select at random a "cross site" and exchange all the digits to the right of the cross site of one string with those of the other. This process is pictured in Figure 4.5. In this example the cross site is position five on the string, and hence we swap the last eight digits between the two strings. Clearly, the cross site is a random number between one and the number of digits in the string minus one. (b) If r > pc then we will not cross over; hence, we do not modify the strings, and we go to the mutation operation below. 1 2 3 4 5 6 789 10 11 12 13 1 2 3 4 5 6 7 8 9 10 11 12 13 Switch these two parts of the strings Cross site i q j q FIGURE 4.5 Crossover operation examples. (c) Repeat step 2 for each pair of strings that is in M(k). As an example, suppose that S = 10 and that in step 1 above we randomly pair off the chromosomes. Suppose that 5 9 q q and (j = 5, i = 9) are paired off where 5 q = +2.9845 and 9 q = +1.9322. Suppose that pc =0.9 and that when we randomly generate r we get r = 0.34. Hence, by step 2 we will cross over 5 9 q q and . According to step 2 we randomly pick the cross site. Suppose that it is chosen to be position three on the string. In this case the strings that are produced by crossover are 5 q = +2.9322 and 9 q = +1.9845. Besides the fact that crossover helps to model the mating part of the evolution process, why should the genetic algorithm perform crossover? Basically, the crossover operation perturbs the parameters near good positions to try to find better solutions to the optimization problem. It tends to help perform a localized search around the more fit individuals (since on average the individuals in the mating pool at time k are more fit man the ones in the population at time k). Reproduction Phase, Mutation Like crossover, mutation modifies the mating pool (i.e., after selection has taken place). The operation of mutation is normally performed on the elements in the mating pool after crossover has been performed. The biological analog of our PDF 文件使用 "pdfFactory Pro" 试用版本创建 www.fineprint.com.cn