Mutation operation

Step 1 First determine the number Pm pop size of chromosomes of the each mutation in population according to the mutation probability. 

Step 2 Random number r is generated in the interval [0,1]. If r Pm, then select Vi as a parent of the mutation. Repeat this process from i = 1 to pop size, and then we get the parents of the mutation operation. Each selected parent is marked as V = x, X2. x ). 

Step 3 Parent V = x, xi. x ) generated from Step 2 is mutated by Cauchy s method define a large enough number M and generate randomly a 

Step 4 Use stochastic simulation technology to check if the descendant chromosomes meet all constraints of the model. If chromosome V + M V/ is feasible, use chromosome X = V + M V/ to replace U If chromosome V + M V/ is not feasible, set M as a random number between 0 and M, then repeat Step 3 and so a new chromosome is generated. Check its feasibility. Repeat this process until all the chromosomes are feasible. Then go on with Step 5. 

Step 6 Calculate the objective value, and select the maximum as Vo- 

---

Figure 9-26 shows a typical GA run in a first step, the original population is created. For each chromosome the fitness is determined and a selection algorithm is applied to choose chromosomes for mating. These chromosomes are then subject to the crossover and the mutation operators, which finally yields a new generation of chromosomes. 

Selection alone cannot achieve an optimization towards the solution With mere scicction performed over a number of generations, one would get a population which comprises only the best chromosome of the original population. Therefore, an operator has to be applied which causes variance within the population, This is achieved by the application of genetic operators such as the crossover and the mutation operators. 

The mutation operator is the second commonly used operator, Mutation brings new traits into a chromosome. The mutation operator eauscs a loeai change in an artificial chromosome. 

Thus, if the chromosome is represented as a bit string, the mutation operator will change one bit in the string as illustrated in Figure 9-30. Usually, the mutation operator is applied with only a small probability. 

Figure 9-30, Mutation operator, which changes one bit in a chromosome,...

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. 

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

Table 11.3 One pass (read left to right) through the step.s of a basic genetic algorithm scheme to maximize the fitness function f x) = using a population of six 6-bit chromosomes. The crossover notation aina2) means that chromosomes Ca, and Ca2 exchange bits beyond the bit. The underlined bits in the Mutation Operation column are the only ones that have undergone random mutation. See text for other details.

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 ... 

The string is picked out by the mutation operator and mutated at position 6 (chosen at random) to give the new string... 

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. 

After a number of new solutions are produced by crossover (or more generally, recombination) and mutation operations, improved solutions must be incorporated into the population. The best solution found thus far is almost always retained. A common strategy replaces a certain fraction of the remaining individuals, either with improved offspring or with new individuals chosen to maintain diversity. Another strategy is tournament selection, in which new solutions and current population members compete in a tournament. Each solution competes with K other solutions, which may be randomly selected, and, in each pairwise comparison, the solution with best fitness value wins. If P is the population size, the P solutions with the most wins become the new population. 

When there are constraints, GAs face a fundamental difficulty, namely that many crossover or mutation operators rarely yield feasible offspring, even if the parents are feasible. This can lead to a population with an excessive number of infeasible solutions. To alleviate this problem, GAs often include a penalty function in/(see Section 8.4) to measure fitness. A value must be chosen for the penalty weight, however. If this is too small, the original problem of too many infeasible solutions remains, and if it is too large, the search tends to reject points with small infeasibilities, even if they are close to an optimal solution. 

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... 

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]. 

Several types of autocorrelation are often used for landscapes. In several important papers, Weinberger and Stadler consider both autocorrelation between adjacent points along a random walk in the landscape and autocorrelation between points a given Hamming distance apart independent of any walk [67,77,78,82,83], Both definitions yield similar information about the landscape and can be computed from one another for stationary landscapes. Other types of autocorrelation are based on neighborhoods defined by complex mutation operations such as crossover [45-49,85],... 

When cutting-and-pasting is complete, every individual in the new population is offered up as a candidate for mutation. In this problem our mutation operator will select a building block at random and replace it by a fresh block of randomly chosen design. 

---