An Introduction to Evolutionary

Computation (September — December, 2006)

Akira Imada

(last modified on) November 27, 2007

1 What does GA look like?

We now assume to solve a problem which includes n variables. That is, our task is to determine an optimal set of n variables. Then we design GA as:

• Represent a series of x_{i} as a population of strings. Each of these strings is refered to as chromosome or sometimes called individual.

• Define a fitness evaluation by “How good is each individual?” Then we start an evolution as follows, expecting better solutions from generation to generation.

1. (Initialization) Generate an initial population of p individuals at random.

2. (Fitness Evaluation) Evaluate fitness of each chromosome and sort the chromosomes according to its fitness from the best to the worst.

3. (Selection) Select two chromosomes

– Here, from the best half of the population at random, which is called a Truncate

Selection.

4. (Reproduction) Produce a child by the following two operations:

– Uniform Crossover, for example

– Mutation

5. Create the next generation by repeating the steps from 3 to 4 n times.

6. Repeat the steps from 2 to 5 until (near) optimal solution is obtained.

2 How we select parents?

Hopefully, the better the fitness the more likely to be selected.

• Threee different versions of Selection.

⋆ Truncation Selection (Simplest of the three):

· Select parents from the best some-percentage of the population.

⋆ Roulette Wheel Selection (or Fitness Proportionate Selection):

· Select such that the probability to be selected is proportional to the fitness value.

For example,

To be more specific, sort the individual from low to high and calculate cumulative value of fitness as follows:

individual after sort cumulative value of fitness
#2  0.125
#3  0.250
#4  0.375
#5  0.625
#1  1.000

Then create a random number r from 0 to 1 if r < 0.125 then select #1, else if r < 0.250 then select #2 , else if r < 0.375 then select #3 and so on.

⋆ Tournament Selection

· Assume we have the original μ parents and their μ children. The fitness value of each of the 2μ individuals are compared to those of q individuals which are chosen randomly from the whole 2μ points at every time of the comparison Then the 2μ individuals are ranked according to the number of wins, and the best μ individuals survive (q-tournament selection).

Note that even the worst fitness individual have a chance to be selected under Roulette Selection however few it might be, while under Trancate Selection worse individual have no chance to be selected. Tornament Selection could also select a worse individual except for the worst q individuals. We can control the probability of selecting worse individual by changing q.

3 How parents produce a child?

3.1 Cross-over

So-called crossover is exproited for the reproduce children. Here, we see three different versions of crossover bellow.

3.2 Mutation

We should give a mutation to introduce new genes. This is to avoid for individuals in the population to be trapped into a local minimum. The probabability for mutation to occur is small — typically 1/number-of-genes. To be more specific,

If a randomly generated number from 0.0 to 1.0 is smaller than the mutation rate then mutate otherwise do nothing.

4 Commonly Used Test Functions:

— Let’s challange an already known so-

lution by a GA

Bellow we study two multi-dimensional test-functions whose location of the global minimum was already known. It is, therefore, useful to explore this test-function to learn how evolution works inside the PC.

4.1 Sphere model

Probably the simplest one is

y = ∑_{i=1}^{n} x_{i}^{2}  (1)

which is difined, for example, on each x_{i} ∈ [−5.12, 5.12] (i = 1, 2, ⋯, n). This function is an extention of well known y = x^{2} to its n-dimensional version. The unique global minimum is located on the Origin and no local minimum. Hence, this might be a good start to try a GA.

4.2 Shcwefel function

The function bellow is called Schwefel function and enormous amount of local minimum and the only unique global minimum at the Origin. Search for the global minimum when the function is difined on, say, x_{i} ∈ [−500, 500].

y = n ; ∑ ; i=1 (x_{i} sin(|x_{i}|))  (2)

You might try to explore this hyper-surface by setting n to 20, for example. Then the surface is defiened on 20-dimensional Eucledean space. If, however, you want to know the image of the hyper-surface, see a two dimensional version of this function. The graph of

y = x sin(|x|)  (3)

is shown in Figure 1.

4.3 The other Test Functions:

⋆ Rastrigin’s Function F_{6}:

y = nA + n ; ∑ ; i=1 (x_{i}^{2} − A cos(2πx_{i})), x_{i} ∈ [−5.12 − 5.12].

· Ruggedness might be controlled by modifying the value of A.

(Contemporary Intelligent Information Techniques) 6 Figure 1: A two-dimensional version of the Schwefel’s Function’s graph. · A two dimensional example (n = 1):

y = 3 + x^{2} − 3 cos(2πx).

Figure 2: A 2-D version of Rastrigin function

⋆ Griewangk’s Function F_{8}:

y = n ; ∑ ; i=1 x_{i}^{2}/4000 − n ; ∏ ; i=1 cos(x_{i}/\sqrt{i}) + 1, x_{i} ∈ [−600, 600].

· A two dimensional example:

y = x^{2}/4000 − cos x + 1.

⋆ Ackley’s Function F_{9}:

y = −20 n ; ∑ ; i=1 exp (−0.2\sqrt{x_{i}^{2}/n}) − exp (( n ; ∑ ; i=1 cos 2πx_{i})/n) + 20 + e,

x_{i} ∈ [−30, 30].

(Contemporary Intelligent Information Techniques) 7 Figure 3: A 2-D version of Griewangk function