• Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

Genetic algorithm

Extracts from this document...

Introduction

image00.jpg

Department of Computer Engineering

Subject: Applied Information Theory

Genetic algorithm

                                                                Done by: Dinara Sabazova

                                                                      Gaukhar Zharylgapkyzy

                                       2nd year student

                                       FIT, AC

                                                                       Checked by: Kaimov A.

      Senior lecturer

Almaty 2013

I. Introduction

First Words

Genetic algorithms are a part of evolutionary computing, which is a rapidly growing area of artificial intelligence.

As you can guess, genetic algorithms are inspired by Darwin's theory about evolution. Simply said, solution to a problem solved by genetic algorithms is evolved.

History

Idea of evolutionary computing was introduced in the 1960s by I. Rechenberg in his work "Evolution strategies" (Evolutionsstrategie in original). His idea was then developed by other researchers. Genetic Algorithms (GAs) were invented by John Holland and developed by him and his students and colleagues. This lead to Holland's book "Adaption in Natural and Artificial Systems" published in 1975.

In 1992 John Koza has used genetic algorithm to evolve programs to perform certain tasks. He called his method "genetic programming" (GP). LISP programs were used, because programs in this language can express in the form of a "parse tree", which is the object the GA works on.

II. Search Space

Search Space

If we are solving some problem, we are usually looking for some solution, which will be the best among others. The space of all feasible solutions (it means objects among those the desired solution is) is called search space (also state space). Each point in the search space represent one feasible solution. Each feasible solution can be "marked" by its value or fitness for the problem. We are looking for our solution, which is one point (or more) among feasible solutions - that is one point in the search space.

The looking for a solution is then equal to a looking for some extreme (minimum or maximum)

...read more.

Middle

Chromosome 1

11011 | 00100110110

Chromosome 2

11011 | 11000011110

Offspring 1

11011|11000011110

Offspring 2

11011 |00100110110

Mutation

After a crossover is performed, mutation take place. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be following:

Original offspring 1

1101111000011110

Original offspring 2

1101100100110110

Mutated offspring 1

1100111000011110

Mutated offspring 2

1101101100110110

V. Parameters of GA

Crossover and Mutation Probability

There are two basic parameters of GA - crossover probability and mutation probability.

Crossover probability says how often will be crossover performed. If there is no crossover, offspring is exact copy of parents. If there is a crossover, offspring is made from parts of parents' chromosome. If crossover probability is 100%, then all offspring is made by crossover. If it is 0%, whole new generation is made from exact copies of chromosomes from old population (but this does not mean that the new generation is the same!).
Crossover is made in hope that new chromosomes will have good parts of old chromosomes and maybe the new chromosomes will be better. However it is good to leave some part of population survive to next generation.

Mutation probability says how often will be parts of chromosome mutated. If there is no mutation, offspring is taken after crossover (or copy) without any change. If mutation is performed, part of chromosome is changed. If mutation probability is100%, whole chromosome is changed, if it is 0%, nothing is changed.
Mutation is made to prevent falling GA into local extreme, but it should not occur very often, because then GA will in fact change to 
random search.

There are also some other parameters of GA. One also important parameter is population size.

Population sizesays how many chromosomes are in population (in one generation). If there are too few chromosomes, GA have a few possibilities to perform crossover and only a small part of search space is explored. On the other hand, if there are too many chromosomes, GA slows down. Research shows that after some limit (which depends mainly on encoding and the problem) it is not useful to increase population size, because it does not make solving the problem faster.

VI. Selection

Introduction

As you already know from the GA outline, chromosomes are selected from the population to be parents to crossover. The problem is how to select these chromosomes. According to Darwin's evolution theory the best ones should survive and create new offspring. There are many methods how to select the best chromosomes, for example roulette wheel selection, Boltzman selection, tournament selection, rank selection, steady state selection and some others.

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 are placed all chromosomes in the population, every has its place big accordingly to its fitness function, like on the following picture.

image09.gif

Then a marble is thrown there and selects the chromosome. Chromosome with bigger fitness will be selected more times.

This can be simulated by following algorithm.

  1. [Sum] Calculate sum of all chromosome fitnesses in population - sum S.
  2. [Select] Generate random number from interval (0,S) - r.
  3. [Loop] Go through the population and sum fitnesses from 0 - sum s. When the sum s is greater then r, stop and return the chromosome where you are.

Of course, step 1 is performed only once for each population.

Rank Selection

The previous selection will have problems when the fitnesses differs very much. For example, if the best chromosome fitness is 90% of all the roulette wheel then the other chromosomes will have very few chances to be selected.

Rank selection first ranks the population and then every chromosome receives fitness from this ranking. The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population).

You can see in following picture, how the situation changes after changing fitness to order number.

image10.gif

Situation before ranking (graph of fitnesses)

image11.gif

Situation after ranking (graph of order numbers)

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


Steady-State Selection

This is not particular method of selecting parents. Main idea of this selection is that big part of chromosomes should survive to next generation.

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

Elitism

Idea of elitism has been already introduced. When creating new population by crossover and mutation, we have a big chance, that we will lose the best chromosome.

Elitism is name of method, which first copies the best chromosome (or a few best chromosomes) to new population. The rest is done in classical way. Elitism can very rapidly increase performance of GA, because it prevents losing the best found solution.

VII. Encoding

Introduction

Encoding of chromosomes is one of the problems, when you are starting to solve problem with GA. Encoding very depends on the problem.

In this chapter will be introduced some encodings, which have been already used with some success.

Binary Encoding

Binary encoding is the most common, mainly because first works about GA used this type of encoding.

Inbinary encodingevery chromosome is a string ofbits,0or1.

Chromosome A

101100101100101011100101

Chromosome B

111111100000110000011111

...read more.

Conclusion


Encoding:Chromosome are functions representedin a tree.

VIII. Crossover and Mutation

Introduction

Crossover and mutation are two basic operators of GA. Performance of GA very depends on them. Type and implementation of operators depends on encoding and also on a problem.

There are many ways how to do crossover and mutation. In this chapter are only some examples and suggestions how to do it for several encoding.

Binary Encoding

Crossover

Single point crossover - one crossover point is selected, binary string from beginning of chromosome to the crossover point is copied from one parent, the rest is copied from the second parent

image03.gif

11001011+11011111 = 11001111

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

image04.gif

11001011 + 11011111 = 11011111

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

image05.gif

11001011 + 11011101 = 11011111

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

image06.gif

11001011 + 11011111 = 11001001 (AND)

Mutation

Bit inversion - selected bits are inverted

image07.gif

11001001 =>  10001001


Permutation Encoding

Crossover

Single point crossover - one crossover point is selected, till this point the permutation is copied from the first parent, then the second parent is scanned and if the number is not yet in the offspring it is added
Note: there are more ways how to produce the rest after crossover point

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

Mutation

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)

Value Encoding

Crossover

All crossovers from binary encoding can be used

Mutation

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

(1.29  5.68  2.864.11  5.55) => (1.29  5.68  2.734.22  5.55)


Tree Encoding

Crossover

Tree crossover - in both parent one crossover point is selected, parents are divided in that point and exchange part below crossover point to produce new offspring

image08.gif

Mutation

Changing operator, number - selected nodes are changed

...read more.

This student written piece of work is one of many that can be found in our International Baccalaureate Maths section.

Found what you're looking for?

  • Start learning 29% faster today
  • 150,000+ documents available
  • Just £6.99 a month

Not the one? Search for your essay title...
  • Join over 1.2 million students every month
  • Accelerate your learning by 29%
  • Unlimited access from just £6.99 per month

See related essaysSee related essays

Related International Baccalaureate Maths essays

  1. Stellar Numbers. In this task geometric shapes which lead to special numbers ...

    the second difference is the constant therefore the formula for the nth term contains n2 as in the quadratic equation: ax2 + bx + c The value of 'a' is half the constant difference.

  2. Mathematics (EE): Alhazen's Problem

    First of all, the balls in question are randomly scattered on the table with no specific locations - in other words our solution would need to be generalized for any set of billiard balls. Second of all, the balls need to be treated as fixed points.

  1. The Population of Japan and Swaziland

    However, I will only illustrate the next two computations which are subsequently displayed using my GDC. Using years 1921 and 1927: I conclude, 1.01 is the approximate rate of change. Furthermore, from 1927 to 1936: 1.03 is the approximate rate of change.

  2. This essay will examine theoretical and experimental probability in relation to the Korean card ...

    simple observations and practical methods that have proved their value by successful use over a long period of time". (GendenkoB., SecklerB.) Also, it could be written as a quantitative measure of the degree of certainty of the observer or the relative frequency of occurrence of the even in a large

  1. Networks - Konigsberg Bridge Problem.

    At first, I didn't get the point of the nodes but I was wrong, the nodes are pretty much the focal point of the rule. Below are the networks, which were asked if traversable. The networks from letters a to k were traversable and the remaining weren't.

  2. Stopping Distances

    64b + c 6 = 1024a + 32b + c - 14 = 2304a + 48b + c 8 = 1280a + 16b 14 = 2304a + 48b + c - 24 = 4096a + 64b + c 10 = 1792a + 16b 8 = 1280a + 16b - 10

  • Over 160,000 pieces
    of student written work
  • Annotated by
    experienced teachers
  • Ideas and feedback to
    improve your own work