Genetic Algorithm
The genetic algorithm comes to be common by the work of John Holland in the initial 1970s and for the most part his book Adaptation in Natural and Artificial Systems (1975). His work initiated by studies of cellular automata, conducted by Holland and his students at the University of Michigan.
Genetic Algorithm
A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural evolution. The genetic algorithm reflects the method of natural selection wherever the fittest entities are selected for reproduction in demand to produce offspring of the next generation.
Uses of Genetic Algorithm:
Genetic algorithms are used to provide efficient, effective techniques for optimization and machine learning applications. Genetic algorithms today frequently used in business, scientific and engineering circles.
- Optimization: Genetic Algorithms are usually used to optimize problems where we have to maximize or minimize a particular objective function value further down a given set of constraints.
- For each cell of a living thing holds chromosomes – strings of DNA
- For each chromosome holds a set of genes – blocks of DNA
- For each gene regulates some aspect of the organism (like eye color)
- A collection of aspects (like eye color) is sometimes called a phenotype
- A collection of genes is sometimes called a genotype
- Reproduction encompasses recombination of genes from parents and formerly small amounts of mutation in copying
- The fitness of an organism is depending on how much it can reproduce before it dies
- Evolution is based on “survival of the fittest”
Components of Genetic Algorithm
- Encoding technique
- Initialization procedure
- Evaluation function
- Selection of parents
- Genetic operators
- Parameter settings
Operator types are:
- Mutation
- Crossover (recombination)
Types of Crossover
- Single Point Crossover
- Two Point Crossover
- Multi-Point Crossover
- Uniform Crossover
- Ring Crossover
- Arithmetic Crossover
Types of Mutation
- Bit Inversion Mutation
- Order Changing Mutation
Crossover can only combine information from two parents, while the Only mutation can introduce different information. Crossover can’t change the frequencies of the population; we need a ‘lucky’ mutation to hit the optimum.
EXAMPLE:
X2: SELECTION
| String NO. | Initial Population | x Value | Fitness
F(x) =x2 | Prob i | Expected Count | Actual Count |
| 1
2 3 4 | 01101
11000 01000 10011 | 13
24 8 19 | 179
576 64 361 | 0.14
0.49 0.06 0.31 | 0.58
1.97 0.22 1.23 | 1
2 0 1 |
| SUM
Avg Max | 1170
293 576 | 1.00
0.25 0.49 | 4.00
1.00 1.97 | 4
1 2 |
X2: CROSSOVER
| String No. | Mating Pool | Crossover Point | OffSpring after x over | x Value | Fitness
F(x) =x2 |
| 1
2 2 4 | 0110|1
1100|0 11|000 10|011 | 4
4 2 2 | 01100
11001 11011 10000 | 12
25 27 16 | 144
625 729 256 |
| SUM
Avg MAX | 1754
439 729 |
Benefits of Genetic Algorithm
- The concept is easy to understand
- Supports multi-objective optimization
- Good for “noisy” situations
- The answer gets better with time
- Easy to exploit alternate solutions
- Flexible building blocks for hybrid applications
Applications:
- Domain Application Types: Regulate pole balancing, gas pipeline, missile evasion, the pursuit
- Design: keyboard configuration, semiconductor layout, communication networks, aircraft design,
- Scheduling: manufacturing, facility scheduling, resource allocation
- Robotics: trajectory planning
- Machine Learning: improving classification algorithms, designing neural networks, classifier systems
- Signal Processing: filter design
- Game Playing: poker, checkers, prisoner’s dilemma
