Heuristics: Genetic Algorithm 1

Introduction

The Genetic Algorithm (following GA) are genetic-based and are presumably search methods to examine mainly large areas, in order to use certain samples of a population (strings of DNA) to produce new samples. It is a binary nonlinear-optimization method. It uses heuristic iterations which in this case is a method of solution space search. The search idea of this heuristic is a stochastic one not a random one, using an evolutionary analogy, "survival of the fittest". In which the solutions (the population of random strings of 1`s and 0`s is being rated according to the quality of its result) are combined and create (hopefully) good or even better solutions. Therefore the fitness is an attribute, which is in the focus of the optimizer (e.g. Comparing people according to their body height or other criteria).

General Example

Let's assume we want to transport a very sensitive object from China to San Francisco. Therefore we have several options. We are not interested in the calculation of the transportation length. The only thing we are interested in, is the packaging. We have different materials (wood, steel, paperboard), thicknesses (1 mm- 20 mm), different types of fastening (taping, glueing,..) and so on. A possible solution would be represented in a string. For example

1011101010

We could now postulate that the first two numbers define the material, the third to fifth numbers defines the fastening technique and so on. So we define with that string a possible solution. Later a cost function could determine the lowest costs which are created out of the costs for material, fastening, transportation (steel is more expensive to transport than paperboard). With respect to the general costs we can now optimize by combining our cheapest solutions.

Now lets assume another possible solution is 1000000000.

Here we take two samples of a genetic code consisting of 1`s and 0`s and rate those samples according to the quality of it`s results, we take the two best samples to combine them in order to increase the quality of the genetic pool regarding a certain population. So if we assume that the two samples carrying the “best” or good enough genetic material, are the parents, simply by comparing their fitness, we aim to increase the quality of the genetic pool by combining them in order to get an offspring. This child, carrying the genetical information of the parents, is targeted to inherit a better genetical code. Now to illustrate this in a simple way, we will show you some methods to produce a child and of course the fundamental method of genetic algorithm, which is the crossover.

Crossover Variants

---

The 1-point crossover is the simplest form, in which the position is chosen randomly with the idea of generating new strings through recombination.

First Example 1-Point-Crossover

• Father: 1 1 0 1 0 0 0 1
• Mother: 0 0 0 0 1 0 0 1
• Child : 1 1 0 1 1 0 0 1

The offspring is the result of the combination of the two bold parts shown above. Which implies that the point for the crossover is between the colored parts. Important to mention is, that the crossover region is randomly chosen.

Second Example Partially-Matched Crossover (PMX)

• Mother: 9 8 4 5 6 7 1 3 2
• Father: 2 9 3 7 4 8 5 1 6
• Child : 2 9 3 8 6 7 1 5 4

First Step: The information of the parents is given in this situation. You choose a random part of the genetic string of the mother (green,671). This will be copied into the same position of the child. So that place regarding the child`s information is occupied. Second step: To inherit as much as possible parts from the genetic code from the father, we leave out the genetic information, which we already got from the mother (so eliminate 6,7 and 1 from the father).

Third step: Now we integrate the genetic code into the child. The not determined positions of the child will be filled with the information from the father (blue,293). The 7 is already in the genetic pool of the mother. So we need to fill the place with another information. We take the 8 from the father instead because it is the information placed at the position where the 7 (of the mother) is and so on (marked brown).

Third Example Order Crossover (OX)

• Mother: 2 3 4 1 5 6
• Father: 4 6 5 3 2 1
• Child : 4 6 3 1 5 2

This method is slightly different from the PMX-method.

First step: You choose a random pair of genetic information from the mother (red). This information is now copied at the same position into the child.

Second step: You try to place all information from the father into the child by transfer the genetic information of the father starting from the left side (465321) excluding the information we have already got from the mother (46_32_) and place them in chronological order (463__2, blue).

Fourth Example Cycle Crossover (CX)

• Mother: 1 2 3 4 5 6 7 8 9
• Father: 4 1 2 8 7 6 9 3 5
• Child: 1 2 3 4 7 6 9 8 5

First Step: Find the cycle that is defined by the corresponding positions of symbols between parents.

Second Step: Copy the symbols in the cycle to a child with positions corresponding to those of one parent.

Third Step: Determine the remaining symbols for the child by deleting those symbols that are already in the cycle from the other parent.

Fourth Step: Fulfill the child with the remaining symbols.

Mutation

---

The Mutation is a simple technique to create new genetic material. A mutant is created by manipulating its genetic code. The following example shows the mutation starting from a pool of 5 individuals (I).

Population Fitness (2^n, n placeholder for the variables, start with 2^0 at the right side)

Population	String	Fitness
I1:	1 0 0 0 0 0	32
I2:	1 1 0 0 0 0	48
I3:	1 0 1 1 0 0	44
I4:	1 0 0 0 0 1	33
I5:	0 1 0 0 1 0	18

By comparing the fitness of the individuals, we select the I2 and I3 because they have the highest/best results. Now these two individuals will be mated to produce an offspring. Initially we use the 1-point-crossover and afterwards the mutation.

Crossover Part 1 Fitness

Population	String	Fitness
I1:	1 1 0 0 0 0	48
I2:	1 0 1 1 0 0	44
IX1:	1 1 1 1 0 0	60

Mutation Part 1:

Population	String	Fitness
IX1:	1 1 1 1 0 0	60
IX2:	1 1 1 0 1 0	58

Crossover Part 2 Fitness

Population	String	Fitness
IX2:	1 1 1 0 1 0	58
IX1:	1 1 1 1 0 0	60
IX3:	1 1 1 0 0 0	56

Mutation 2:

Population	String	Fitness
IX3:	1 1 1 0 0 0	56
IX4:	1 1 0 0 0 1	49

Conclusion

According to John H. Holland "the genetic algorithm exploits the higher-payoff, or "target", regions of the solutions space, because successive generations of reproduction and crossover produce increasing numbers of strings in those regions. The algorithm favors the fittest strings as parents, and so above-average strings (which fall in target regions) will have more offspring in the next generation." This method allows to determine a bigger scope of potential solutions than do most other programs. Over time computers will be able to adapt and learn through experience and which will make such algorithms in the future able to imitate "perfectly" the nature and organisms.

References

• John H. Holland: Genetic Algorithm. Scientific American July 1992

• Mitchell, Melanie: an Introduction to Genetic Algorithm. Cambridge, MA: MIT Press (1996)

• A Tutorial by Erik D. Goodman: Introduction to Genetic Algorithms (2011)

• D.E. Goldberg and J.H. Holland: Guest Editorial - Genetic Algorithm and Machine Learning (1988)