http://cs.felk.cvut.cz/~xobitko/ga/ Genetic algorithms are inspired by Darwin's theory of evolution. Solution to a problem solved by genetic algorithms is evolved. Algorithm is started with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population. This is motivated by a hope, that the new population will be better than the old one. Solutions which are selected to form new solutions (offspring) are selected according to their fitness - the more suitable they are the more chances they have to reproduce. This is repeated until some condition (for example number of populations or improvement of the best solution) is satisfied. Example As you already know from the chapter about search space, problem solving can be often expressed as looking for extreme of a function. This is exactly what the problem shown here is. Some function is given and GA tries to find minimum of the function. Outline of the Basic Genetic Algorithm 1.[Start] Generate random population of n chromosomes (suitable solutions for the problem) 2.[Fitness] Evaluate the fitness f(x) of each chromosome x in the population 3.[New population] Create a new population by repeating following steps until the new population is complete 1.[Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected) Take the best solutions (elitism to new population) without crossover or mutation. Then weight the rest based proportional to fitness. 2.[Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents. 3.[Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome). 4.[Accepting] Place new offspring in a new population 4.[Replace] Use new generated population for a further run of algorithm 5.[Test] If the end condition is satisfied, stop, and return the best solution in current population 6.[Loop] Go to step 2 Encoding of a Chromosome The chromosome should in some way contain information about solution which it represents. The most used way of encoding is a binary string. The chromosome then could look like this: Chromosome 1 1101100100110110 Chromosome 2 1101111000011110 Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution. Or the whole string can represent a number - this has been used in the basic GA applet. Crossover After we have decided what encoding we will use, we can make a step to crossover. Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point point copy from a first parent and then everything after a crossover point copy from the second parent. You can have a crossover probability. 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 You can have a mutation probability. Example of Problem: Knapsack problem The problem: There are things with given value and size. The knapsack has given capacity. Select to maximize the value of things in knapsack, but do not extend knapsack capacity. Encoding: Each bit says, if the corresponding thing is in knapsack. 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 have to travel very much. Find a sequence of cities to minimize travelled distance. Encoding: Chromosome says order of cities, in which salesman will visit them.