Crossover operation

Step 1 First determine the number Pc pop size, of chromosome of the population which will crossover in the operation according to their crossover probability. 

Step 2 Select a random number r from the interval [0, 1], if r Pc, then select Vi as a parent. From i = 1 to pop size, repeat this process, then we get parents Vj, V3. .. of crossover algorithm. 

Step 3 Parents V[, V3. .. generated in Step 2 are paired randomly. With a random number X generated from the open interval (0, 1) crossover each pair of parents (Vj, Vj) according to the following equation. The crossover operators are shown in Table 4.1. This process generates two offspring Xand Y. 

In order to keep the optimal gene from being destroyed, we improve the above crossover operator inspired by genetic algorithm. If the fitness of new crossover individuals X or Y is not worse than that of the original individuals V or V, then they replace the original individual V or V, otherwise the original individuals are reserved. 

Use stochastic simulation technology to check whether the descendant chromosomes are feasible. 

---

Crossover, which is also called recombijiation, follows the idea that aji offspring in natiu c always holds genes from both its parents. Accordingly, the genetic crossover operator takes parts of two parent chromosomes to create a new offspring. 

The crossover operator is applied to the selected pairs of parents with a probability a typical value being 0.8 (i.e. there is an 80% chance that any of the p/2 pairs will actually undergo this type of recombination). Following the crossover phase mutation is appUed to all individuals in the population. Here, each bit may be inverted (0 to 1 and vice versa) with a probability P. The mutation operator is usually assigned a low probability (e.g. 0.01). 

Figure 11.11 shows examples of the three basic genetic operations of reproduction, crossover and mutation, as applied to a population of 8-bit chromosomes. Reproduction makes a set of identical copies of a given chromosome, where the number of copies depends on the chromosome s fitness (see below). The crossover operator exchanges subparts of two chromosomes, where the position of the crossover is randomly selected, and is thus a crude facsimile of biological sexual recombination between two single-chromosome organisms. The mutation operator randomly flips one or more bits in the chromosome, where the bit positions are randomly chosen. 

Step 4 Randomly pairing up the chromosomes in the new population, apply the genetic crossover operator to each pair. That is, randomly select a bit-position, say k, for each pair of chromosomes, say and and replace this pair with two new pairs - and - constructed via genetic < rossover C, consists of the first k bits of C,i, and the last N — k) bits of and C, consists of the first k bits of and the last N — k) bits of. ... 

Init Pop Initial Fitness Exp/ Copies Actual Copies Mating Pop Crossover Operation Mutation Operation New Fitness... 

Next, we randomly pair up the new chromosomes, and perform the genetic crossover operation at randomly selected bit-positions -- chromosomes C and C4 exchange their last three bits, C2 and Cg exchange their last four bits, and C3 and C5 exchange their last bit ... 

A lower bound on the overall effect of crossover, which can both create and destroy instances of a given schema, can be estimated by calculating the probability, Pc S), that crossover leaves a schema S unaltered. Let be the probability that the crossover operation will be applied to a string. Since a schema S will be destroyed by crossover if the operation is applied anywhere within its defining length, the probability that S will be destroyed is equal to Pc x 6 S)/ K — 1), where 6 S) is the defining length of S. Hence, the probability of survival ps = 1 — PcS S)/ K — 1), and equation 11.9 takes the updated form ... 

The progress of the GA depends on the values of several parameters that must be set by the user these include the population size, the mutation rate, and the crossover rate. Choosing the values of these parameters is not the only decision to be made at the start of a run, however. There are tactical decisions to be made about the type of selection method, the type of crossover operator, and the possible use of other techniques to make the algorithm as effective as possible. The choice of values for these parameters and type of crossover or selection can make the difference between a calculation that is no better (or worse) than a conventional calculation and one that is successful. In this section, we consider how to choose parameters to run a successful GA and start with a look at tactics. 

Action by the crossover operator that brings together two promising segments. 

Two-dimensional (or indeed n-dimensional) GA strings can be handled in the usual way, with an n-dimensional chunk of the strings being swapped by the crossover operator rather than a linear segment. However, care must then be taken to ensure that wraparound is applied in all n dimensions, not just one. (See also Problem 2 at the end of this chapter.)... 

In evolutionary strategies, a parent string produces X offspring the fittest of the 1 + X individuals is selected to be the single parent for the next generation of offspring. There is no crossover operator in evolutionary strategies, only mutation. 

The crossover operation replaces some of the elements in each parent solution with those in the other. For example, in one-point crossover, with parents PI and P2 represented by real-valued vectors, and with the crossover point after the third component, the parents and offspring are as shown here for a five-variable problem ... 

Table 10.10 shows the performance of the evolutionary solver on this problem in eight runs, starting from an initial point of zero. The first seven runs used the iteration limits shown, but the eighth stopped when the default time limit of 100 seconds was reached. For the same number of iterations, different final objective function values are obtained in each run because of the random mechanisms used in the mutation and crossover operations and the randomly chosen initial population. The best value of 811.21 is not obtained in the run that uses the most iterations or computing time, but in the run that was stopped after 10,000 iterations. This final value differs from the true optimal value of 839.11 by 3.32%, a significant difference, and the final values of the decision variables are quite different from the optimal values shown in Table 10.9. 

These results were obtained by coupling a genetic algorithm for descriptor and calculation parameter (PC, bins) selection to PCA-based partitioning. In these calculations, descriptors were chosen from a pool of approx 150 different ones, and both the number of PCs and bins were allowed to vary from 1 to 15. An initial population of 300 chromosomes was randomly generated with initial bit occupancy of approx 15%. Rates for mutation and crossover operations were set to 5% and 25%, respectively. After PCA-based partitioning, scores were calculated for the following fitness function ... 

Conversely, a crossover operator is used based on confidence intervals. This operator uses information from the best individuals in the population. Moreover, the crossover operator is associated with the capacity of interpolation (exploration). This capacity is related to the belonging of a population parameter to a confidence interval. The crossover operator is also associated with the capacity of extrapolation (exploitation). To select the suitable parents for the next generation, the roulette wheel selection method is used. This method consists of a random selection in which the best quality individuals have more possibilities to be selected. In this way, the explained operators create new individuals that are added to the population. To produce the next generation, that extended population is reduced to its original size using the rank-space method. This selection procedure links fitness to both quality rank and diversity rank. Thus, it promotes not only the survival of individuals, which are extremely fit from the perspective of quality, but also the survival of those that are both quite fit and different from others. 

Fechner, U., and Schneider, G. (2007). Flux (2) comparison of molecular mutation and crossover operators for ligand-based de novo design. Journal of Chemical Information and Modeling 47, 656-667. 

Once mutation has been performed the fitter of parent and child is selected and the process repeats. There can, of course, be no possibility of applying a crossover operator when the complete population consists of just one solution, so mutation is the only genetic operator available. 

Fig. 6 The crossover operator in GP involves selecting two nodes at random, one in each parent, and exchanging the subtrees headed by each node...

---