Heuristics: Genetic Algorithm 2

BACKGROUND INFORMATION

Generally genetic algorithms represent search heuristics that illustrates the process of natural evolution. Based on the functionality of natural selection and genetics genetic algorithms belong to the evolutionary algorithms. Moreover this kind of heuristics are allocated to the so called metaheuristic. In contrast to specific heuristics metaheuristics demonstrate more abstract procedures that use low-level heuristics in order to solve optimization problems.

POTENTIAL FIELDS OF APPLICATION

• Search problems

• Optimization problems

• Machine learning

• Adaptive rule-basis

The main purpose of the genetic algorithms is to generate useful solutions according to optimization and search problems, whereby their functionality is characterized by three essential features.

FUNCTIONALITY

The functionality of genetic algorithms can be differentiated into three major phases:

•SELECTION: This phase refers to the so called individuals that are characterized by their own and exceptional genes as well as a special adjustment to the environment. The extent of an individual’s adjustment to the environment can be in turn described as the so called fitness. During the first step a selection of a specified amount of elements from a beginning population occurs. Hereby the attention should be paid to the fact, that those elements which are characterized by a higher fitness even have a higher probability to be admitted.

•MUTATION: In connection with the genetic algorithms the mutation phase illustrates the process of how new individuals are generated from a random change of the parental units. Moreover the mutation is able to find potential solutions which couldn’t be generated through only the recombination.

•RECOMBINATION (CROSSOVER): The recombination leads to the creation of new gene and attribute combinations of elements from a now existing matepool. Thus a mixture of different attributes takes place.

As a consequence of the above mentioned results the following strengths and weaknesses of genetic algorithms can be stated.

STRENGHTS AND WEAKNESSES

•Genetic algorithms are characterized by a good functionality according to the search of the global optimum, because the searching process takes place in the whole solution place.

•Furthermore Genetic algorithms can be extended by genetic operators. Thereby the quality of the solution or the speed can be optimated.

•Simple implementation for complex problems.

For understanding GA and how they work, we have to introduce some new vacabulary:

individual =a strucuture, that represents a solution, consisting of genes

chromosome =equal to individual

gene =a bit of the binary representation of a solution

population =quantity of individuals, that became considered by an GA

parents =two chosen individuals of a population

crossing =combination of two genes from two chromosomes

mutation =modification of a chromosome

fitness =qualtity of a solution

generation =one iteration in the duration of the optimation

genotype =coded solution of a problem

phenotype =decoded solution of a problem

Basically the strucure of Genetic Algorithm is always the same presented below

1. produce an initial population of indivuals
2. evaluate the fitness of all individuals
3. WHILE termination condition not met DO
   1. select fitter individuals for reproduction
   2. recombine between individuals
   3. mutate individuals
   4. evaluate the fitness of the modified individuals
   5. generate a new population
4. END WHILE

Examples

We want to visit 6 cities and every city just once.

The distances between the cities are given in the following tableau.

We want to minimize the distance of our tour.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \begin{array}{|c||c|c|c|c|c|c|} \hline & 1 & 2 & 3 & 4 & 5 & 6\\ \hline \hline 1 & - & 4 & 2 & 10 & 8 & 7\\ \hline 2 & & - & 5 & 7 & 9 & 2\\ \hline 3 & & & - & 3 & 5 & 9\\ \hline 4 & & & & - & 1 & 5\\ \hline 5 & & & & & - & 4\\ \hline 6 & & & & & & -\\ \hline \end{array}

We have an initial parents generation given by the following three route alternatives:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \ \ 3-4-1-5-2-6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \ \ 2-6-3-1-4-5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \ \ 1-5-2-3-6-4

The reproduction rate of the parents´pool is 1/3. The reproduction rate of the children´s pool is 2/3.

The recombination takes place in the following (chosen randomly) order:

(1)->(2), (1)->(3), (3)->(2)

The algorithm stops after the second generation.

a) Partially-Matched Crossover (PMX)

The length of the sequence is given by 2.

(1)->(2)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \ \ 3-4-1-\color{red}5\color{black}-\color{red}2\color{black}-6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \ \ 2-6-3-\color{green}1\color{black}-\color{green}4\color{black}-5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (4) \ \ \color{green}4\color{black}-6-3-\color{red}5\color{black}-\color{red}2\color{black}-\color{green}1

The first recombination process [(1)->(2)] starts at gene 4 (randomly chosed). This means we cut out gene 4 and 5 of parent 1 (red marked).

So 5 becomes the 4th gene and 2 the 5h element of the child (red marked).

Now we have to take gene 4 and 5 of parent 2 (green marked).

The green marked 1 of parent 2 has to be placed under 5 of parent 2, because the green marked 1 of parent 2 stands below the 5 of parent 1.

The green marked 4 of parent 2 has to be placed under 2 of parent 2, because the green marked 4 of parent 2 stands below the 2 of parent 1.

At the end we have to fill up gene 2 and 3 of the child with gene 2 and 3 of parent 2 to get an new individual without a number twice.

(1)->(3)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \ \ \color{red}3\color{black}-\color{red}4\color{black}-1-5-2-6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \ \ \color{green}1\color{black}-\color{green}5\color{black}-2-3-6-4

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (5) \ \ \color{red}3\color{black}-\color{red}4\color{black}-2-\color{green}1\color{black}-6-\color{green}5

The second recombination process [(1)->(3)] starts at gene 1 (randomly chosed).

(3)->(2)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \ \ 1-\color{red}5\color{black}-\color{red}2\color{black}-3-6-4

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \ \ 2-\color{green}6\color{black}-\color{green}3\color{black}-1-4-5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (6) \ \ \color{green}3\color{black}-\color{red}5\color{black}-\color{red}2\color{black}-1-4-\color{green}6

The third recombination process [(3)->(2)] starts at gene 2 (randomly chosed).

Now we have to calculate the fitness of the parents and children.

Parent (1) : $f_{1}=3+10+8+9+2=32$

Parent (2) : $f_{2}=2+9+2+10+1=24$

Parent (3) : $f_{3}=8+9+5+9+5=36$

Child (4)  : $f_{4}=5+9+5+9+4=32$

Child (5)  : $f_{5}=3+9+4+7+4=27$

Child (6)  : $f_{6}=5+9+4+10+5=33$

The reproduction rate of the parents´ pool is 1/3. So we pick out parent 2, because we want to minimize the distance.

The reproduction rate of the childrens´ pool is 2/3. So we pick out Child 4 and 5.

So the second generation consists out of parent 2 and child 4 and 5.

b) Order Crossover (OX)

The length of the sequence is given by 2.

(1)->(2)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \ \ 3-4-1-\color{red}5\color{black}-\color{red}2\color{black}-6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \ \ 2-6-3-\color{green}1\color{black}-\color{green}4\color{black}-5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (4) \ \ \color{green}1\color{black}-6-3-\color{red}5\color{black}-\color{red}2\color{black}-\color{green}4

The first recombination process [(1)->(2)] starts at gene 4 (randomly chosed). This means we cut out gene 4 and 5 of parent 1 (red marked).

So 5 becomes the 4th gene and 2 the 5h element of the child (red marked).

Now we have to take gene 4 and 5 of parent 2 (green marked).

The green marked 1 of parent 2 has to be placed under 2 of parent 2, because the green marked 1 of parent 2 stands below the 5 of parent 1.

The green marked 4 of parent 2 has to be placed under 5 of parent 2, because the green marked 4 of parent 2 stands below the 2 of parent 1.

At the end we have to fill up gene 2 and 3 of the child with gene 2 and 3 of parent 2 to get an new individual without a number twice.

(1)->(3)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (1) \ \ \color{red}3\color{black}-\color{red}4\color{black}-1-5-2-6

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \ \ \color{green}1\color{black}-\color{green}5\color{black}-2-3-6-4

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (5) \ \ \color{red}3\color{black}-\color{red}4\color{black}-2-\color{green}5\color{black}-6-\color{green}1

The second recombination process [(1)->(3)] starts at gene 1 (randomly chosed).

(3)->(2)

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (3) \ \ 1-\color{red}5\color{black}-\color{red}2\color{black}-3-6-4

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (2) \ \ 2-\color{green}6\color{black}-\color{green}3\color{black}-1-4-5

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): (6) \ \ \color{green}6\color{black}-\color{red}5\color{black}-\color{red}2\color{black}-1-4-\color{green}3

The third recombination process [(3)->(2)] starts at gene 2 (randomly chosed).

Now we have to calculate the fitness of the parents and children.

Parent (1) : $f_{1}=3+10+8+9+2=32$

Parent (2) : $f_{2}=2+9+2+10+1=24$

Parent (3) : $f_{3}=8+9+5+9+5=36$

Child (4)  : $f_{4}=7+9+5+9+7=37$

Child (5)  : $f_{5}=3+9+9+7+7=35$

Child (6)  : $f_{6}=4+9+4+10+3=30$

The reproduction rate of the parents´ pool is 1/3. So we pick out parent 2, because we want to minimize the distance.

The reproduction rate of the childrens´ pool is 2/3. So we pick out Child 5 and 6.

So the second generation consists out of parent 2 and child 5 and 6.

The Maxone problem:

We want to maximize the number of ones in a string of L binary bits.

This may seem to trivial, cause we know already the answer, but however, we can think of it as maximazing the number of correct answers, each encoded by 1, to difficult questions:

Suppose l=10, n=6

Cause everey individual is encoded as a string of l binary bit, we can write for one

1=0000000001 (10 bits)

To get the initial population, we toss a fair coin 60 times:

$s_{1}=1111010101\qquad \color {red}f(s_{1})=7$

$s_{2}=0111000101\qquad \color {red}f(s_{2})=5$

$s_{3}=1110110101\qquad \color {red}f(s_{3})=7$

$s_{4}=0100010011\qquad \color {red}f(s_{4})=4$

$s_{5}=1110111101\qquad \color {red}f(s_{5})=8$

$s_{6}=0100110000\qquad \color {red}f(s_{6})=3$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \color{red}\sum_{i=1}^{6}f(s_i)=34

while f(s) is the fitness function

The new population after performing selection (suppose we apply a random generator and get this selection).

$s_{1}'=1111010101\quad (s_{1})$

$s_{2}'=1110110101\quad (s_{3})$

$s_{3}'=1110111101\quad (s_{5})$

$s_{4}'=0111000101\quad (s_{2})$

$s_{5}'=0100010011\quad (s_{4})$

$s_{6}'=1110111101\quad (s_{5})$

You can determine the probability for a crossover, for instance 0,6.

Thus we only perform a crossover for the pairs $(s_{1}',s_{2}')$ and $(s_{5}',s_{6}')$

Crossover-points: 2 and 5

Before crossover:

$s_{1}'=11\color {green}11010101\color {black}\qquad s_{5}'=01000\color {green}10011$

$s_{2}'=11\color {red}10110101\color {black}\qquad s_{6}'=11101\color {red}11101$

After crossover:

$s_{1}''=11\color {red}10110101\color {black}\qquad s_{5}''=01000\color {red}11101$

$s_{2}''=11\color {green}11010101\color {black}\qquad s_{6}''=11101\color {green}10011$

Before applying random mutation:

For each bit, that we are to copy to the new population, we allow a small probability of error, for instance 0,1.

$s_{1}''=11101\color {red}1\color {black}0101\qquad s_{2}''=1111\color {red}0\color {black}1010\color {red}1$

$s_{3}''=11101\color {red}1\color {black}11\color {red}0\color {black}1\qquad s_{4}''=0111000101$

$s_{5}''=0100011101\qquad s_{6}''=11101100\color {red}1\color {black}1$

After applying mutation (random) with updated fitness-values:

$s_{1}'''=11101\color {red}0\color {black}0101\qquad f(s_{1}''')=6$

$s_{2}'''=1111\color {red}1\color {black}1010\color {red}0\color {black}\qquad f(s_{2}''')=7$

$s_{3}'''=11101\color {red}0\color {black}11\color {red}1\color {black}1\qquad f(s_{3}''')=8$

$s_{4}'''=0111000101\qquad f(s_{4}''')=5$

$s_{5}'''=0100011101\qquad f(s_{5}''')=5$

$s_{6}'''=11101100\color {red}0\color {black}1\qquad f(s_{6}''')=6$

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=1}^{6}f(s_i''')=37

Improvement of 9 percent (fitness from 34 to 37)

You could repeat the algorithm, until a stopping criterion is met.

References

Nobal Niraula, Genetic Algorithm: http://de.slideshare.net/kancho/genetic-algorithm-by-example (download: 24.06.13)

Alfred Hermes, Heuristik: Genetischer Algorithmus am Beispiel des 0/1-Rucksackproblems: http://learntech.rwth-aachen.de/lehre/ss05/fdi/folien/VS11HTML/GenAlg.pdf (download: 24.06.13)

Operations Research Tutorial