(20 marks)
6. Describe a typical process of development of a genetic algorithm (GA) for solving a real world problem. Define the following basic concepts in GA: Crossover; Mutation; Population; Generation; and Run.
~~~ Development process ~~~
- Specify the problem, define the constraints and optimum criteria.
- Represent the problem domain as a chromosome.
- Define a fitness function to evaluate the chromosome’s performance.
- Construct the genetic operators.
- Run the GA and tune its parameters.
Crossover:
Crossover is an operation applied to two chromosomes, to generate their offspring. For some probablitity (commonly 0.7) called the crossover probability, two chromosomes are split at some random point in their bit string and the end parts are swaped with each other. This generates two new offspring. For those that aren’t crossed over the offspring are clones of the originals.
Mutation:
After the crossover operation is complete, there is a very small probablity (say 0.001) that a mutation will occur for each chromosome. If a mutation occurs then a random 1 bit in the chromosome is switched (ie if 1 then 0, or if 0 then 1). Mutation’s are included to ensure that while the algorithm runs to find an optimal solution, it does not halt on a local maximum. If this does happen then the mutation probability may be too small, or the population of the genetic pool may be too small.
Population:
Is the number of chromosomes in the gene pool. If the population is too small, then there may not be enough diversity in the gene pool to find a optimal solution quickly or at all.
Generation:
A genetic algorithm is an itterative process. Each iteration replaces those chosen for mating with their offspring. Each iteration is called a generation.
Run:
A genetic algorithm is usually run for a fixed number of generations. 1 run referers to executing the program for those generations. The results are usually checked when it’s complete. If no good solution is found, things are tweaked and it is run again.