Crossover and Mutation

Simulated Binary Crossover (SBX) [Deb and Agrawal (1995)] operator for real valued variables is used to create two children from a pair of parents. 

The offsprings and are created from parents and by operating on one variable at a time as shown in Eq. (5.3), 

The Mutation operator used is the polynomial mutation operator defined by Deb and Goyal (1996). Each variable of y is obtained from a corresponding variable of x as given in Eq. (5.5). 

If the value of any of the variables calculated using crossover and mutation operators falls below the lower bound (or above the upper bound), the value of that variable is fixed at the lower bound (or the upper bound). 

---

The evolutionary process of a genetic algorithm is accomplished by genetic operators which translate the evolutionary concepts of selection, recombination or crossover, and mutation into data processing to solve an optimization problem dynamically. Possible solutions to the problem are coded as so-called artificial chromosomes, which are changed and adapted throughout the optimization process until an optimrun solution is obtained. 

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. 

Fig. 11.11 Schematic representation of the basic genetic operations of reproduction, crossover and mutation.

This basic difference equation - known as the Schema Theorem [holl92] - expresses the fact that the sample representation of schemas whose average fitness remains above average relative to the whole population increases exponentially over time. As it stands, however, this equation addresses only the reproduction operator, and ignores effects of both crossover and mutation. 

Finally, in order to also take into account the mutation operator, we note that the probability that a schema S survives under mutation is given by pu S) = (1 — Pm) where pm is the single-bit mutation probability and 0( S) is the number of fixed-bits (i.e. the order) or S. With this we can now express the Schema Theorem that (partially) respects the operations of reproduction, crossover and mutation ... 

Performing crossover and mutation. In addition to replication, crossover and mutation are also two effective ways to form a new population. Crossover manipulation is the combination of two ABS codes to form two new ABS codes. Mutation changes one or two elements, saying 0 to 1, or 1 to 0, of a selected ABS code. The crossover and mutation are performed probabilistically. The replication, crossover, and mutation processes are repeated until the termination criterion is reached. 

After crossover and mutation, discussed below in section 5.5.6, the strings are as shown in Table 5.3. 

The Strings from Generation 0, after Selection, Crossover, and Mutation... 

This string tells us that product 6 is to be made first, followed by product 1, then by 9, and so on no product is made more than once. The GA is a powerful means of finding the optimum order, but it is easy to see that the crossover and mutation operators may cause problems. Suppose that the strings... 

Hurme (1996) has used GA to solve the synthesis problem of the separation of mixture of hydrocarbons. He also compared GA with a pure random version in which the crossover and mutation operations were replaced by a procedure of random generation of new solutions. There was no difference during the first generations but it became significant after some generations. In this case GA reached the solution after ten generations with about 1100 different possible solutions, while the random version required tens of generations. GA seems to be both fast compared to random optimization and not too computationally intensive. 

Crossover and mutation conditions are usually randomized rules, which determine if these operators are to be applied in the current iteration. Crossover is commonly applied in most if not all iterations, whereas mutation is applied less frequently. 

Steps 4 through 6 are the scatter search counterparts to the crossover and mutation operators in genetic algorithms, and the reference set corresponds to the GA... 

Fig. 5. Representation of a genetic algorithm for the selection of descriptors for a QSAR model. The model is commonly referred to as a gene and is encoded with different descriptors. Two Parents creating two Children is a crossover of genetic information (descriptors). The genes of an individual can mutate, introducing random changes in the model. Crossover and mutation are can occur independent of each other.

Selecting the points for crossover and mutation according to a probability distribution, either uniform or skewed towards points at which the optimized function takes high values (the latter being a probabilistic expression of the survival-of-the-fittest principle). 

While most combinatorial researches reported up to now involve the use of GA, using the traditional crossover and mutation operators (e.g. WGS 1), it has also been proposed to design new operators for each specific application, to improve search efficiency by means of knowledge extraction [32]. Hence, new methods that combine ES with a knowledge extraction engine have been reported recently within the field of heterogeneous catalysis, such as mining association rules [12, 18, 30, 33] and neural networks [19, 29, 34]. 

GAs are probabilistic search methods based on the mechanics of natural selection and genetics. The basic idea in using a GA as an optimization method is to represent a population of possible solutions in a chromosome-type encoding, called strings, and evaluate these encoded solutions through simulated reproduction, crossover, and mutation to reach an optimal or near-optimal solution. The GA starts with the creation of an initial population of... 

---