(Brest State Technical University 2006 Fall Semester: Course Practice)

Contemporary Intelligent Information Technology

Akira Imada (e-mail akira@bstu.by)

This document is still under construction and was lastly modified on December 14, 2010

1 All One Problem

In order to study what will be going on under the computational evolution, let’s start very simple experiment.

We now evolve binary chromosomes. We start with the initial population with, say, 100 binary chromosomes with, say, 40 genes, – all created at random. The fitness is the number of “1” in chromosome — the more the better. That is our target is all-one-chromosome.

Try a standard evolution with (i) one-point-crossover and (ii) uniform-crossover, with mutation rate being 1/N where N is the number of genes in one chromosome.

Algorithm 1 (All-One-Problem)

1. Create, say, 100 binary-chromosomes at random where the number of gene is 40.

2. Fitness is the number of “1” in one chromosome – the more the better.

3. Select 2 chromosomes at random from the better half of the population of 100 chromosomes.

4. Create a child chromosome by a crossover.

· Compare two performances one with one-point-crossover and the other with uniform-crossover.

5. Give the child a mutation with a probability of 1/40 = 0.025.

6. Repeat from 2. to 5. 40 times and create the next generation.

7. Repeat 6. until the fitness value reaches 40.

8. Show the result:

(1) Desplay the best chromosome in each generation from generation to generation.

(2) Desplay the best-fitness vs. generation and average-fitness vs. generation.

2 The Simplest Test Function — Sphere Model

The first task of this practice is to obtain the minimul value of a multi-dimensional function.

To be more specific, we now assume that we have the following function defined in a 20-dimensional space:

y = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + ⋯ + x_{20}^{2}.  (1)

Then obtain which point of (x_{1}, x_{2}, x_{3}, ⋯, x_{20}) gives a minimum value of y and how much is the value of minimum y. Now, try the following algorithm.

Algorithm 2 (The minimization of the simplest high-D function)

1. Create, say, 100 chromosomes at random.

· The number of gene is 20.

Thus our chromosomes here have the form (x_{1}, x_{2}, x_{3}, ⋯, x_{20}).

· Assume here each of x_{i} takes the continuous value from −1 to 1, that is

−1 < x_{i} < 1.

2. Calculate fitness value by y = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + ⋯ + x_{20}^{2}. Note that the smaller the better.

3. Select 2 chromosomes at random from the better half of the population of 100 chromosomes.

4. Create a child chromosome by a crossover.

5. Give the child a mutation

6. Repeat from 2. to 5. 100 times and create the next generation.

7. Repeat 6. until the fitness value reaches 0.

Then the question is as follows.

Excersize 1 (Obtaining the global minimum)

(1) Plot the average fitness value of all the 100 chromosomes versus generation. (2) Also plot the minimum fitness value of each generation.

3 A little more tricky function

Let’s try a little more tricky function. for example, the one called Rastrigin’s Function.

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

Dimensionality n is arbitorary, but to see how its graph look like, see the Figure when n = 1.

Figure 1: A 2-D version of Rastrigin function

Excersize 2 (Obtaining the global minimum)

(0) Try in the case of n = 20. (1) Plot the average fitness value versus generation. (2) Also plot the minimum fitness value of each generation. (3) Make an experiment with different value of mutation rate.

4 2-D Functioon

We now try a 2-D Function in order to observe what will be going on under an evolution. Let’s try to find the minimum point of the following function as an example.

y = x^{4} − 5x^{3} − 6x^{2} + 8x + 15

The graph looks like when x ∈ [−2, 5]

Figure 2: Yet another test function: y = x^{4} − 5x^{3} − 6x^{2} + 8x + 15 with x ∈ [−2, 5].

How you design chromosome to solve this problem?

In the previous problem, the number of genes is n if the function is difiened on n dimensional space. Then our chromosome here has only one gene? How, on earth, we crossover two chromosomes?

The answer is, we use binary chromosome. In the above example, ...

5 Neural Networks for XOR

Assuming McCulloch-Pitts neurons which take the state 1 or 0, the output Y of the neuron which receives weighted-sum of the signals X_{i} from other N neurons is usually specified as:

Y = sgn(∑_{i=1}^{N} w_{i}X_{i} − θ),

where sgn(x) = 1 if x ≥ 0 and 0 otherwise, and w_{i} and θ are called weight and threshold, respectively. Here, we assume neurons take binary state but -1 or 1, instead of 0 or 1. Hence the equation is modified as

Y = 2 · sgn(∑_{i=1}^{N} w_{i}X_{i} − θ) − 1.

6 Neural Network for Even-n-Parity

Even-n-Parity is a boolean function to check whether number of 1 of n-bit binary is even or not.

We now assume n = 4 for the sake of simplisity. Again our binary made up of −1 and 1 instead of 0 and 1 for a convenience. Hence, as in previous section, transfer function is

y_{i} = 2 · sgn(∑_{j=1}^{N} w_{ij}x_{j} − θ_{j}) − 1,

where y_{i} is output of neuron-i, w_{ij} is weight of the synapse from neuron-j to neuron-i, x_{j} is state of neuron-j, θ is threashold of neuron-j, and N is the number of neurons connected to neuron-i. We assmue here θ_{j} = 0.5 for all j.

\begin{matrix}x_{1} & x_{2} & x_{3} & x_{4} & y \\ −1 & −1 & −1 & −1 & +1 \\ −1 & −1 & −1 & +1 & −1 \\ −1 & −1 & +1 & −1 & −1 \\ −1 & −1 & +1 & +1 & +1 \\ −1 & +1 & −1 & −1 & +1 \\ −1 & +1 & −1 & +1 & −1 \\ −1 & +1 & +1 & −1 & −1 \\ −1 & +1 & +1 & +1 & +1 \\ +1 & −1 & −1 & −1 & +1 \\ +1 & −1 & −1 & +1 & −1 \\ +1 & −1 & +1 & −1 & −1 \\ +1 & −1 & +1 & +1 & +1 \\ +1 & +1 & −1 & −1 & +1 \\ +1 & +1 & −1 & +1 & −1 \\ +1 & +1 & +1 & −1 & −1 \\ +1 & +1 & +1 & +1 & +1 \end{matrix}

We now exploit a feedfoward Neural Network with 4 input neurons, 4 hidden neurons, and one output neurons. So, we have 20 synapsis and as such our chromosome has 20 genes. Create 100 chromosomes with random weight from −1 to 1. Fitness evaluation is by counting the correct answer after giving all the possible 16 cases of 4 inputs, one by one. Then evolve the population.

Excersize 3 (Neural Network for Even-4-Parity)

(1) Plot the average fitness in the population as a function of generation. (2) Plot the maximum fitness in the population as a function of generation. (3) Demonstrate the finally obtained neural network by giving 4 inputs from keybord.

7 Navigoation in gridworld

Assume now that we want to make an agent, or a robot, in a gridworld, a possible chromosome can be made up of integer gene from 1 to 4 where 1, 2, 3, and 4 correspond to one cell movement of the agent to north, south, east and west. Take a look at the below as an example.

Figure 3: An example of chromosome and the trace of the robot whose has this chromosome.

Search for a path of maximum Manhattan distance

. Starting with the center of a huge 2-dimensional gridworld, a robot navigate following its chromosome. The length of the chromosome is 40 for example. That is, the robot explore the gridworld with 40 steps.

At the beginning, robots explore with random walk because its chromosome is given at random.

Some robot would just explore around the starting points. Think of the robot, for example, whose chromosome is

(1212121212121212121212121212121212121212)

The goal is to find a robot who reaches to the point with the maximum (40) Manhattan distance from the starting point.

Search for a path to the goal with minimum Manhattan distance

In this problem, the point robots start with, and the goal they should reach are prespecified.

The goal is to find a robot who reaches the goal with the minimum Manhattan distance. Sea the Figure below as an example.

Figure 4: In the grid-world of 96 starting from (24,24) a robot walks aiming the goal at (72,72) of which the robot had no a-priori information. Left: The path of minimum length among 100 trials by random walk. Right: Minimal path the robot found after an evolutionary learning as shown in Fig. 3. (Marginal area is omitted.)

8 Traveling Salesperson Promblem (TSP)

Assuming N cities all of whose cordinate are given, Traveling Salse-person Problem (TSP) is a problem in which a sales-person should visit all of these cities once but only once with its goal being to look for the shortest tour.

We now take a look at 4 cities – A, B, C, and D – as a simplest example. We now assume the cities location are given as follows, for instance.

(x, y)
A (0.83, 7.79)
B (3.28, 8.32)
C (1.52, 4.48)
D (7.65, 3.46)

Then the Eucledean distances between all possible pair of cities are calculated using a formula:

r_{ij} = \sqrt{(x_{i} − x_{j})^{2} + (y_{i} − y_{j})^{2}}  (2)

where r_{ij} is the distance between city i and city j and (x_{i}, y_{i}) and (x_{j}, y_{j}) are coordinate of city i and city j, respectively. The distances are:

A  B  C  D
A 0.000 2.505 3.382 8.074
B 2.505 0.000 4.232 6.539
C 3.382 4.232 0.000 6.214
D 8.074 6.539 6.214 0.000

Figure 5: An example of 4 cities and a possible tour therein.

All possible routes in this example are

(A-B-C-D-A), (A-B-D-C-A), (A-C-B-D-A), (A-C-D-B-A), (A-D-B-C-A), and (A-D-C-B-A).

Notice here that lengths of a pair of tours is identical such as a pair (A-B-C-D-A) and (A-D-C-B-A). That is, we have 3!/2 = 3 routes in total in this example. Let’s see now one root A-C-B-D-A out of them, in the map shown in Figure 5. The length of the tour in the figure is

r_{A−C−B−D−A} = 3.382 + 4.232 + 6.539 + 8.074 = 22.227

In the same way, we can calculate the other two route. That is, r_{A−B−D−C−A} = 2.505 + 6.539 + 6.214 + 3.382 = 15.640

r_{A−B−C−D−A} = 2.505 + 4.232 + 6.214 + 8.074 = 21.025

So, the tour of minimum length is A-B-D-C-A (or A-C-D-B-A). But what if we have larger number of cities? Now you know even in case of 10 cities, we have 9!/2 = 181, 440 possible differnt route. Do you want calculate those distances of all the possible tour? Of course not! Further more, what about 1000 cities, for example? Then let’s apply our evolutionary algorithm. Note that, however, chromosomes like

(B D C)

for tour A-B-D-C-A and

(D C B)

for tour A-D-C-B-A, would not work, because possible child after one-point crossover by cutting between 1st and 2nd genes will be

(B C B) and (D D C)

would not be feasible, because both are not a leagal tour – visits one city twice neglecting one city. Then a possible design of chromosome is as follows.

Step-1. Set i = 1.

Step-2. If i-th gene is n then n-th city in the list is the city to be currently visited. Step-3. Remove the city from the list. Step-4. Set i = i + 1 and repeat Step-2 to Step-4 while i < n.

For example, when the list of cities besides the starting city A is {B, C, D} chromosome: (121) is the tour:

A-B-D-C-A.

Note that genes can be any integer and mutation might be by simply replacing a gene with another random integer. The probability might be 1/number-of-genes (you may change the ratio as an experiment, of course.)

Excersize 4 (TSP)

(1) Create 14 cities by assign random coordinate (x_{i}, y_{i}).

(2) Calculate the distance between all the possible two cities.

(3) Then evolve them until the total distance of tour converges one value.

(4) Repeat (3) until fitness value (= total distance of tour) converges a value.

Results you should show me.

• Coordinates of All the cities.

• Matric of distance between any 2 cities.

• Graphic of the location of all the cities and the shortest tour.

9 Knapsack Problem

We now assume n items whose i-th item has weight w_{i} and profit p_{i}, then we pick up x_{i} of the i-th item i = 1, 2, ⋯, n and x_{i} is non-negative integer. The goal is to maximizes

∑_{i=1}^{n} x_{i}p_{i}.  (3)

such that

∑_{i=1}^{n} x_{i}w_{i} < C  (4)

where C is the capacity of the knapsack.

GA implementation is quite simple. Our chromosomes are in the form

(x_{1}x_{2}x_{3} ⋯ x_{n})  (5)

with each x_{i} being the number of the i-th items to be in the knapsack.

Kill infeasible chromosomes

One important aspect is if a chromosome does not fulfill the condition of Eq.(4), simply kill the choromosome and repeat the procedure which resulted in the infeasible child chromosome (cross-over, mutation, or whatever.) untill creating a feasible child chromosome.

Excersize 5 (Knapsack Problem) Assumming the size of knapsack is, say, 60.

(1) Create, say, 100 items, by giving each of whose price p_{i} and size w_{i} at random, both raging from 0 to 1. For example:

item price size
1st 0.37 0.62
2nd 0.52 0.45
3rd 0.95 0.38
⋯  · · · · · ·
100th 0.72 0.32

(2) Creat 40 chromosomes each of which has 100 integer genes, like

(5, 7, 13, ⋯ 2)

which means five 1st items, seven 2nd items 13 3rd items, ⋯, two 100th items.

(3) Try to check by replace with one item with price being 0.99 and size being 0.01 Imagine this item is like diamonds small and precious. Hence all items should converge this one. And then replace all items with price being 0.01 and size being 0.01 In this case you know clearly the results.

(4) Try evolution and plot maximum fitness vs. generation, as well as average fitness vs. generation

(5) Visualize the inside of the knapsack.

10 Sammon Mapping by GA

Here we learn about Sammon Mapping. Sammon Mapping is a mapping a set of points a in high-dimensional space to the 2-dimensional space with the distance relation being preserved as much as possible, or equivalently, the distances in the n-dimensional space are approximated by distances in the 2-dimensional distance with a minimal error.

This method was proposed in 1980’s as an optimization problem to which they approached by Operations Research technique suchas Steepest Descend, which is not so simple. Here, on the other hand, we employ Evolutionary Computatins which is quite simple. Let’s see now what is the original Sammon Mapping look like.

Algorithm (Sammon Mapping)

1. Assume N points are given in the n-D space.

2. Calculate distance matrix R (N × N) whose i-j element is the Euclidean distance between the i-th and j-th point.

3. Also think of a tentative N points in the 2-D space that are located at random at the beginning.

4. The distance matrix Q is calculated in the same way as R.

5. Then the error matrix P = R − Q is defined.

6. Search for the locations of N points in the 2-D space that minimizes the sum of element P.

This is an optimization problem which we now can solve quite simply by using EC. That is, by creating N points in 2-D space each of which corresponding N points in the n-D space with the distance relation being preserved as much as possible, or equivalently, such that the n-D distances are approximated by 2-D distances with a minimal error.

In an actual GA implementation of Sammon Mapping, chromosomes might be made up of n genes each of which corrisonds to x−y coordinate of a candidate solution of n optimally distributed points in 2-dimensional space. Uniform crossover is employed and from time to time mutation is given by replacing one gene with other random x − y coordinate. See the Figure 2. See also the Figure bellow. Examples in 49^{2} = 2401 dimensional space:

Figure 6: A chromosome representation and uniform crossover

Figure 7: Six Examples of Mapping from 2401-dimensional space to the 2-dimensional space. Further explanations are shown in the text.

11 Multi Modal Genetic Algorithms – When we have multipul meaningful solution?

11.1 Target Functions

Assuming our goal is maximization, that is, we want to know when y takes the maximum value and for which x, we try two test functions.

y = sin^{6}(5πx)  (6)

and

y = −2((x − 0.2)/0.8)^{2} sin^{6}(5πx)  (7)

Now take a look what do these two function look like.

Figure 8: A multi-peak 2-D function and its variation

11.2 Two Algorithms

Here, we have two algorithms for the current purpose of finding multiple solutions at a run.

11.2.1 Fitness Sharing Fitness of each individual is derated by an amount related to the number of similar individuals in the population. That is, shared fitness F_{s}(i) of the individual i is

F_{s}(i) = \frac{F (i)}{∑_{j=1}^{μ} s(d_{ij})}

where F (i) is fitness of individual i; d_{ij} is distance between individual i and j; Typically d_{ij} is Hamming distance if in genotypic space Euclidean distance if in phenotypic space and s(·) is called sharing function and defined as:

s(d_{ij}) = \{ \begin{matrix}1 − (d_{ij}/σshare)^{α} & if d_{ij} < σshare \\ 0 & otherwise \end{matrix}

where σshare is interpreted as size of niche, and α determines the shape of the function. The denominator is called niche count. You see shape dependency of s(d_{ij}) on α in Figure 11.2.2.

Figure 9: A shape dependency of s(d_{ij}) on α.

To be short (not so short though): Similar individual should share fitness. The number of individuals that can stay around any one of peaks (niche) is limited. The number of individuals stay near any peak will theoretically be proportional to the hight of the peak

11.2.2 Deterministic Crowding

If the parents will be replaced or not with their childeren will be determined under a criteria of the distance between parents and children.

Algorithm Assuming crossover, mutation and fitness function are already defiened 1. Choose two parents, p_{1} and p_{2}, at random, with no parent being chosen more than

once.

2. Produce two children, c′_{1} and c′_{2}.

3. Mutate the children yielding c_{1} and c_{2}, with a crossover.

4. Replace parent with child as follows:

- IF d(p_{1}, c_{1}) + d(p_{2}, c_{2}) > d(p_{1}, c_{2}) + d(p_{2}, c_{1})

∗ IF f(c_{1}) > f(p_{1}) THEN replace p_{1} with c_{1}

∗ IF f(c_{2}) > f(p_{2}) THEN replace p_{2} with c_{2}

- ELSE

∗ IF f(c_{2}) > f(p_{1}) THEN replace p_{1} with c_{2}

∗ IF f(c_{1}) > f(p_{2}) THEN replace p_{2} with c_{1}

where d(ζ_{1}, ζ_{2}) is the Hamming distance between two points (ζ_{1}, ζ_{2}) in pattern configuration space. The process of producing child is repeated until all the population have taken part in the process. Then the cycle of reconstructing a new population and restarting the search is repeated until all the global optima are found or a set maximum number of generation has been reached.

Hopefully the following two figures would help you understand why.

Figure 10: Two cases of parents-children’s distance relation.

11.3 Results you should show.

Hopefully you apply two algorithms to each of two test functions. Besides fitnessgeneration graph, as usual, you try visualize how your individual change their location as generation goes.

That is to say, show all points of individuals in, say, every 20 generations in order to see how theyconverge to the peaks.

12 Multi Objective Genetic Algorithm (MOGA)

So far we have learned how to get the possible solution(s) which fulfills one objective function for the problem, that is, the goal is maximize the fitness function. In real world problem, however, we have usually multiple objectives or criteria to be fulfilled simultaneously.

Those objectives sometimes conflict with each other. Like “time” and “money”: The more we want to earn money, the less time to spent the money; or “reliability” of the product and “cost” to produce it in a manufactural factory. Or, suppose an Opera Company trys to employ one Soprano singer. The criteria is voice, beauty-or-not), slim-or-not, languagecapability (Italian, German, etc). However God tend not to give us two talents at a time, alas.

Then, first of all, when we have multiple objective function, we must define an important concept of parate optimal or equvalently non-dominated solution.

Definition (Parate Optimal or Non-dominated Solution) A candidate solution is called a non-dominated iff there is no ohter better solution w.r.t. all the objectives.

To be more specific, assume we have n objective functions;

f_{1}(x), f_{2}(x), f_{3}(x), ⋯ f_{n}(x)

where x is a candidate solution. Now if a new candidate solution y improves all the objetives for x, i.e.,

f_{i}(y) > f_{i}(x) for ∀i

we say

“y dominate x.”

When no such y exists, we say

“x is non-dominated” or “Parete Optimum.”

A toy example: We now assume the two objective functions as follows.

\{ \begin{matrix}f_{1}(x) = x^{2} \\ f_{2}(x) = (x − 2)^{2} \end{matrix}

· x=0 is optimum w.r.t. f_{1} but not so good w.r.t. f_{2}.

· x=2 is optimum w.r.t. f_{2} but not so good w.r.t. f_{1}.

· Any other point in between is a compromise or trade-off and is a Pareto-optimum.

· But the solution x=3, e.g., is not a Pareto-optimum since this point is not better than the solution x = 2 w.r.t. either objective.

· If we plot in the f_{1}-f_{2} space, an increase in f_{1} in some reagion means a decrease in f_{2}, or vice versa which implys that the solutions in the region are Parete optimum, while in other region an increase in f_{1} make f_{2} increas (decrease). See Figure ??. This f_{1}-f_{2} space is called a Trade-off Space.

We now take a look at a typical implemetation of MOGA.

Algorithm (A Multi Objective GA)

1. Initialize the population.

2. Select individuals uniformly from population.

3. Perform crossover and mutation to create a child.

4. Calculate the rank of the new child.

5. Find the individual in the entire population that is most similar to the child. Replace that individual with the new child if the child’s ranking is better, or if the child dominates it. ^{1}

6. Update the ranking of the population if the child has been inserted.

7. Perform steps 2-6 according to the population size.

8. If the stop criterion is not met go to step 2 and start a new generation.

Excersize 6 (Parate Optimal Solutions) Try the algorithm above with two objective functions y = (x − 2)^{2} and y = (x − 4)^{2}. Then show the possibly parate optimum solutions you found.

1Step 5 implies that the new child is only inserted into the population if it dominates the most similar individual, or if it has a lower ranking, i.e. a lower degree of dominance.

The restricted replacement strategy also constitutes an extreme form of elitism, as the only way of replacing a non-dominated individual is to create a child that dominates it.

The similarity of two individuals is measured using a distance function.

13 Evolving both structure and weight of Neural Network

We have such an algorithm called NeuroEvolution of Augmenting Topologies (NEAT)^{2} We now summerise the method by paraphrasing the original paper by Stanley and Mikikkulainen (2002).

Each gene is made up of (1) inovation number (2) connection from which neuron (3) to which neuron and enable (ON) or disable (OFF).

A population of chromosomes are created at random initially. When created this first generation, genes of each chromosome is assigned an integer from left to right as 1, 2, 3, .... This is called ’inovation number’ for some reason. Then selecting two parents according to fitness value; give mutation with a small probability, and crossover these two parents, which produce one child. By repeating this procedure, the next generation is created.

Now let’s see how we mutate and how we crossover.

13.1 mutation

We have two different mutations. From one gene to the next, mutate or not mutate are determined at random with a low probability. If to be mutated, which of the followin two is used also at random.

• Add connection mutation

– A single new connection gene with a random weight is added connecting two previously unconnected neurons.

• Add neuron mutation

– An existing connection is split and the new neuron placed where the old connection used to be.

– The old connection is disabled and two new connections are added to the chromosome.

– The new connection leading into the new neuron receives a weight of 1, and the new connection leading out receives the same weight as the old connection.

In the future, whenever these chromosomes mate, the offspring will inherit the same innovation numbers on each gene; innovation numbers are never changed. Thus, the historical origin of every gene in the system is known throughout evolution.

2K. O. Stanley and R. Miikkulainen (2002) “Evolving Neural Networks through Augmenting Topologies.” Evolutionary Computation, Vol. 10, pp. 99-127.

Figure 11: Two types of mutation in NEAT. (Re-drawed the figure in Stanley et al.)

13.2 crossover

the genes in both chromosomes with the same innovation numbers are lined up. These genes are called matching genes. Genes that do not match are either disjoint or excess, depending on whether they occur within or outside the range of the other parent ’ s innovation numbers.

the genes in both chromosomes with the same innovation numbers are lined up. These genes are called matching genes. Genes that do not match are either disjoint or excess, depending on whether they occur within or outside the range of the other parent’s innovation numbers.

Excersize 7 (Evolving structure of NN) To make it simple, fitness is the number of gene.

(Practice – Contemporary Intelligent Information Techniques) 24 Figure 12: A crossover in NEAT. (Re-drawed the figure in Stanley et al.)