Genetic Algorithm - History

INTRODUCTION:

Genetic algorithms are computerized search and optimization algorithm based on the mechanics of natural genetics and natural selection. Professor John Holland of the University of Michigan, Ann Arbor envisaged the concept of these algorithms in the mid-sixties and published his seminal work (Holland, 1975). Thereafter, a number of his students and other researchers have contributed to developing this field. To date, most of the GA studies are available through few books (Davis,1991; Goldberg,1989 ; Holland, 1975; Michalewicz,1992) and through a number of international conference proceeding ( Below and Booker ,1991; Forrest, 1993; Grefensette , 1985, 1987;Rawlins, 1991; Schaffer, 1989 ; Whitely , 1993). GA’s are fundamentally different than classical optimization algorithms.

Coding a GA

dLet us consider a minimization problem

eg: f(x) = x^2 + 5(x) + 6

since it's a quadratic equation, it has got 2 solutions....lets say an x1 and x2.

This problem is subjected to a constraint x(l) <= x(i) <= x(u) i = 1, 2… N , where l and u specify the upper and lower limits and i specifies the no of solutions.

Step 1:

Choose a coding o represent problem parameters, a selection operator, a crossover operator, and a mutation operator. Choose population size, n, crossover probability, and mutation probability, . Initialize a random population of strings of size. Choose a maximum allowable generation number t_max. Set t=0.

To know about choosing GA parameters Click here

Step 2:

Evaluate each string in the population.

To know about evaluation Click here

Step 3:

If no of generations is exceeded or other termination criteria are satisfied, terminate.

Step 4:

Perform reproduction on the population.

Step 5:

Perform crossover on random pairs of strings.

To know about cross over, Click here

Step 6:

Perform mutation on every string.

To know about mutation, Click here

Step 7:

Evaluate strings in the new population. Set t= t+1 and go to step 3

Mutation in a GA

•
Create a neighborhood point of the current point – to achieve local search.

• Mutation is an arbitrary change in a situation. Sometimes it is used to prevent the algorithm from getting stuck.

•Bit wise mutation operator mutate the string bit by bit.

Eg: 11010101 == 11011101

Cross Over in GA

In reproduction, good strings in a population are probabilistically assigned a large number of copies and a mating pool is formed. It is important to note that no new strings are formed in the reproduction phase. In the crossover operator, new strings are created by exchanging information among he strings of the matting pool. Many crossover operators exist in GA literature. In most crossover operators, two strings are picked from the matting pool at random and some portions of the strings are exchanged between the strings. A single-point crossover operator is performed by randomly choosing a crossing site along the string and by exchanging all bits on the right side of the crossing site as shown:

0 0 | 0 0 0 0 0 | 1 1 1

1 1 | 1 1 1 1 1 | 0 0 0

These two strings participating in the crossover operation are known as parent strings and the resulting strings are known as children strings. It is intuitive from this construction that good substrings from parent strings can be combined to form a better child string, if an appropriate site is chosen. Since the knowledge of an appropriate site is usually not known beforehand, a random site is often chosen. With a random site, the children strings produced may or may not have a combination of good substrings from he parent strings, depending on whether or not the crossing site falls in the appropriate place. But we don’t worry about this too much, because if good strings are created by crossover, there will be more copies of them in the next mating pool generated by the reproduction operator. But if good strings are not created by crossover, they will not survive too long, because reproduction will select against those strings in subsequent generation.

It is clear from this discussion that the effect of crossover may be detrimental or beneficial. Thus, in order to preserve some of the good strings that are already present in the mating pool, not all strings in the mating pool are used in crossover. When a crossover probability of is used, only 100 percent strings in the population are used in the crossover operation and 100(1-) percent of the population remains as hey are in the current population.

Eg: 11001|001 11001|101

00110|101 == 00110|001

Evalation of a GA-string

• In order to use GA’s to solve the above problem, variables x_i’s are first coded in some string structures.I used a binary coded GA.

eg: 11101 11100 corresponding to x1 and x2.

• Then we could find the values of x(i) using the linear mapping rule as follows:

x(i) = x(l) + [ ( ( x(u) - x(l) ) / ( 2^l - 1 ) ) *dv(s)].

where dv(s) is the decoded decimal value of the string.

• substitute the values of x(i) in the respective f(x).

• CALCULATE FITNESS FUNCTION

F(X) = 1/1+f(X)

• CALCULATE A = ACTUAL FITNESS/AVERAGE FITNESS(EXPECTED COUNT)

• CALCULATE PROBABILITY OF SELECTION (B) = EXPECTED COUNT/TOTAL NO OF CHROMOSOMES
  

• CALCULATE CUMULATIVE PROBABILITY (C).
  

• GENERATE RANDOM NO BETWEEN 0 AND 1 (D)

• DETERMINE THE INTERVAL WHERE THE RANDOM NUMBER

LIES E=l2.

• TRUE COUNT OF STRINGS TO BE

IN MATING POOL (F)

GA TABLE

Chosing GA parameters

The following are the parameters to GA:

• The Probability of Cross over (pc)
  
• The Probability of Mutation (pm)
  
• No of generations (n)
  
• String length (l)
  

1. 0.6<=pc<=0.9.
2. 0<=pm<=0.1.
3. It depends on your processors's speed. 100 is an optimal one.
4. Increase in l increases accuracy but decreases speed. 20 is an optimal value.

The reasons for choosing these values ll be discussed in the upcoming steps.