Mumbai University > Computer Engineering > Sem 7 > Soft Computing

Marks: 10 Marks

Year: Dec 2015

Selection:

The chromosomes are selected from the population to be parents for crossover. The problem is how to select these chromosomes. According to Darwin's theory of evolution the best ones survive to create new offspring. There are many methods in selecting the best chromosomes. Examples are roulette wheel selection, Boltzman selection, tournament selection, rank selection, steady state selection and some others.

1. Roulette Wheel Selection

Parents are selected according to their fitness. The better the chromosomes are, the more chances to be selected they have. Imagine a roulette wheel where all the chromosomes in the population are placed. The size of the section in the roulete wheel is proportional to the value of the fitness function of every chromosome - the bigger the value is, the larger the section is. See the following digrm for an example.

A marble is thrown in the roulette wheel and the chromosome where it stops is selected. Clearly, the chromosomes with bigger fitness value will be selected more times. This process can be described by the following algorithm. [Sum] Calculate the sum of all chromosome fitnesses in population - sum S. [Select] Generate random number from the interval (0,S) - r. [Loop] Go through the population and sum the fitnesses from 0 - sum s. When the sum s is greater then r, stop and return the chromosome where you are. Of course, the step 1 is performed only once for each population.

2. Rank Selection

The previous type of selection will have problems when they are big differences between the fitness values. For example, if the best chromosome fitness is 90% of the sum of all fitnesses then the other chromosomes will have very few chances to be selected. Rank selection ranks the population first and then every chromosome receives fitness value determined by this ranking. The worst will have the fitness 1, the second worst 2 etc. and the best will have fitness N (number of chromosomes in population). see in following digram, how the situation changes after changing fitness to the numbers determined by the ranking.

Situation before ranking (graph of fitnesses)

Situation after ranking (graph of order numbers)

Now all the chromosomes have a chance to be selected. However this method can lead to slower convergence, because the best chromosomes do not differ so much from other ones.

3. Steady-State Selection:

This is not a particular method of selecting parents. The main idea of this type of selecting to the new population is that a big part of chromosomes can survive to next generation.

The stady-state selection GA works in the following way. In every generation a few good (with higher fitness) chromosomes are selected for creating new offspring. Then some bad (with lower fitness) chromosomes are removed and the new offspring is placed in their place. The rest of population survives to new generation.

4. Elitism:

When creating a new population by crossover and mutation, we have a big chance, that we will loose the best chromosome.

Elitism is the name of the method that first copies the best chromosome (or few best chromosomes) to the new population. The rest of the population is constructed in ways described above. Elitism can rapidly increase the performance of GA, because it prevents a loss of the best found solution.

Encoding:

Encoding of chromosomes is the first question to ask when starting to solve a problem with GA. Encoding depends on the problem heavily.

1. Binary Encoding:

Binary encoding is the most common one, mainly because the first research of GA used this type of encoding and because of its relative simplicity.

In binary encoding, every chromosome is a string of bits - 0 or 1.

Chromosome A 101100101100101011100101

Chromosome B 111111100000110000011111

Example of chromosomes with binary encoding

Binary encoding gives many possible chromosomes even with a small number of alleles. On the other hand, this encoding is often not natural for many problems and sometimes corrections must be made after crossover and/or mutation.

Example of Problem: Knapsack problem

The problem: There are things with given value and size. The knapsack has given capacity. Select things to maximize the value of things in knapsack, but do not extend knapsack capacity.

Encoding: Each bit says, whether the corresponding thing is in knapsack.

2. Permutation Encoding

Permutation encoding can be used in ordering problems, such as travelling salesman problem or task ordering problem.

In permutation encoding, every chromosome is a string of numbers that represent a position in a sequence.

Chromosome A 1 5 3 2 6 4 7 9 8

Chromosome B 8 5 6 7 2 3 1 4 9

Example of chromosomes with permutation encoding

Permutation encoding is useful for ordering problems. For some types of crossover and mutation corrections must be made to leave the chromosome consistent (i.e. have real sequence in it) for some problems.

Example of Problem: Travelling salesman problem (TSP) The problem: There are cities and given distances between them. Travelling salesman has to visit all of them, but he does not want to travel more than necessary. Find a sequence of cities with a minimal travelled distance.

Encoding: Chromosome describes the order of cities, in which the salesman will visit them.

3. Value Encoding

Direct value encoding can be used in problems where some more complicated values such as real numbers are used. Use of binary encoding for this type of problems would be difficult.

In the value encoding, every chromosome is a sequence of some values. Values can be anything connected to the problem, such as (real) numbers, chars or any objects.

Chromosome A 1.2324 5.3243 0.4556 2.3293 2.4545

Chromosome B ABDJEIFJDHDIERJFDLDFLFEGT

Chromosome C (back), (back), (right), (forward), (left)

Example of chromosomes with value encoding

Value encoding is a good choice for some special problems. However, for this encoding it is often necessary to develop some new crossover and mutation specific for the problem. Example of Problem: Finding weights for a neural network

The problem: A neural network is given with defined architecture. Find weights between neurons in the neural network to get the desired output from the network.

Encoding: Real values in chromosomes represent weights in the neural network.

4. Tree Encoding

Tree encoding is used mainly for evolving programs or expressions, i.e. for genetic programming. In the tree encoding every chromosome is a tree of some objects, such as functions or commands in programming language.

Chromosome A

Chromosome B

Tree encoding is useful for evolving programs or any other structures that can be encoded in trees. Programing language LISP is often used for this purpose, since programs in LISP are represented directly in the form of tree and can be easily parsed as a tree, so the crossover and mutation can be done relatively easily.

Example of Problem: Finding a function that would approximate given pairs of values The problem: Input and output values are given. The task is to find a function that will give the best outputs (i.e. the closest to the wanted ones) for all inputs.

Encoding: Chromosome are functions represented in a tree.

Crossover:

Crossover and mutation are two basic operators of GA. Performance of GA depends on them very much. The type and implementation of operators depends on the encoding and also on the problem.

1. Single point crossover - one crossover point is selected, binary string from the beginning of the chromosome to the crossover point is copied from the first parent, the rest is copied from the other parent

11001011+11011111 = 11001111

2. Two point crossover - two crossover points are selected, binary string from the beginning of the chromosome to the first crossover point is copied from the first parent, the part from the first to the second crossover point is copied from the other parent and the rest is copied from the first parent again

11001011 + 11011111 = 11011111

3. Uniform crossover - bits are randomly copied from the first or from the second parent

11001011 + 11011101 = 11011111

4. Arithmetic crossover - some arithmetic operation is performed to make a new offspring

11001011 + 11011111 = 11001001 (AND)

5. Tree crossover -

one crossover point is selected in both parents, parents are divided in that point and the parts below crossover points are exchanged to produce new offspring.

Mutation

1. Bit inversion:

Selected bits are inverted

11001001 => 10001001

2. Order changing -

Two numbers are selected and exchanged

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

3. Adding:

a small number (for real value encoding) - a small number is added to (or subtracted from) selected values

(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)

4. Changing operator, number -

Selected nodes are changed: