A genetic algo is a variant of stochastic beam search in which successor states are generated by combining two parent states, rather than by modifying a single state. The analogy to natural selection is the same as in stochastic beam search, except now we are dealing with sexual rather than a sexual reproduction.

Like beam search, GAS begin with a set of K randomly generated states called the population. Each state or individual, is represented as a string over a finite alphabet – most commonly a string of Os and 1s.

Example: An 8 – queens state must specify the positions of 8 – queens, each in a column of 9 squares, and so requires $8 \times log_2 \ ^8 = 24$ bits. Alternatively, the state could be represented as 8 digits, each in the range from 1 to 8.

Figure 4.15 (a) shows a population of four 8 – digits strings representing 8 – queens states. The production of the next generation of states is shown in figure 4.15 (b) – (e). In (b), each state is rated by the evaluation function or (in GA terminology) the fitness function. A fitness function should return higher values for better states, so far the 8 – queens problem we use the number of non attacking pairs of queens, which has a value of 28 for a solution. The values of the four states are 24, 23, 20 and 11. In this particular variant of the genetic algo, the probability of being chosen for reproducing is directly proportional to the fitness score and the percentages are shown next to the raw scores. In (c), a random choice of two pairs is selected for reproduction, in accordance with the probabilities in (b). notice that one individual is selected twice and one not at all. Or each pair to be mated, a cross over point is randomly chosen from the positions in the string. In figure 4.15, the cross over points are after the third digit in the first pair an after the fifth digit in the second pair.

In (d), the offspring themselves are created by crossing over the parent strings at the crossover point.

Example: The first child of the first pair gets the first three digits from the first parent and the remaining digits from the second parent, whereas the second child gets the first three digits from the second parent and the rest from the first parent. The 8 – queens states involved in this reproduction step are shown in figure 4.16. The example illustrates the fact that, when two parent states are quite different, the crossover operation can produce a state that is a long way from either parent state. It is often the case that the population is quite diverse early on in the process, so crossover frequently takes large steps in the state space early in the search process and smaller steps later on when most individuals are quite similar.

Figure, The 8 - queen problems states corresponding to the 1st two parent in the figure (C) and the 1st off spring in figure (d). The shaded columns are lost in the crossover step and the unshaded columns are retained.

Finally, in (e), each location is subject to random mutation with small independent probability. One digit was mutated in the first, third and fourth offspring. In the 8 – queens problem this corresponds to choosing a queen at random and moving it to a random square in its column.

Figure 4.17 describes an algo, that implements all these steps.

an individual

function GENETIC – ALGORITHM (population, FITNESS-FN) returns

input. Population, a set of individuals

of an individuals

FITNESS-FN, a function that measures the fitness repeat

new_population $\leftarrow$ empty set

loop for i from 1 to SIZE (population) do

X $\leftarrow$ RANDOM-SELECTION (population, FITNESS-FN)

Y $\leftarrow$ RANDOM-SELECTION (population, FITNESS-FN)

child $\leftarrow$ REPRODUCE (X, Y)

if (small random probability) then child $\leftarrow$ MUTUATE (child)

add child to new_population

population $\leftarrow$ new_population

until some individuals is fit enough, or enough time has relapsed

return the best individual in population, according to FITNESS-FN.

Figure 4.17 Genetic Algo. The algo is the same as the one diagrammed in figure 4.15 with one variation in this more popular version, each mating of two parents produces only one offspring, not two.

Genetic Algo.

According to fitness, we perform selection.

Steps:

1] Initialize population.

2] Selection according to fitness.

3] Crossover between selected chromosomes.

4] Perform mutation.

5] Repeat cycle till the conditions or stop is true.