1.1 - Genetics Algorithm - Algorithm Overview

1.1.1 – Introduction


Genetic Algorithm is a directed search algorithms based on the mechanics of biological evolution developed by John Holland, University of Michigan (1970’s) to understand the adaptive processes of natural systems and design artificial systems software that retains the robustness of natural systems this algorithms provide efficient, effective techniques for optimization and machine learning applications so it is widely used today in business, scientific and engineering circles.

Some GA Application Types:


Application Types

**Control** Gas pipeline, pole balancing, missile evasion, pursuit
**Design** Semiconductor layout, aircraft design, keyboard configuration, communication networks
**Scheduling** Manufacturing, facility scheduling, resource allocation
**Robotics** Trajectory planning
**Machine Learning** Designing neural networks, improving classification algorithms, classifier systems
**Signal Processing** Filter design
**Game Playing** Poker, checkers, prisoner’s dilemma
**Combinatorial Optimization** Set covering, travelling salesman, routing, bin packing, graph coloring and partitioning

1.1.2 - Description - Charles Darwin Theory

Charles Darwin Theory: “Living organisms are fighting the forces of nature to survive. Those who are the fittest (strongest, fastest, biggest) are most likely to survive, Those who survive mate and reproduce (selection) and children are similar (inheritance), but not exactly like parents because of cross-fertilization and mutation, thus children can be more or less fitness than parents also, Children repeat the path of their parents, after several generations the organisms become much fitter.” - Genetic algorithm

Suppose that there are many possible solutions for the problem: x1, x2, x3, x4… The main idea is to view each solution xi of the problem as an individual living organism. The number of possible solution can be incredibly large n ◊ ∞, so we consider m < n and chose a Population: P(t) = {x1t, x2t, … , xmt} ,with time the organisms and the whole population will be evolving. - Crossover

Crossover is replacing some genes in the parent by the corresponding genes of the other.

For example:

P1 = 101 | 0010 ⇒ O1 = 101 | 1001

P2 = 011 | 1001 ⇒ O2 = 011 | 0010 - Mutation

Mutation is randomly choosing a gene and replacing it with other gene; mutation helps to add diversity to the population and help avoiding local maximum

For example:

O1 = 1011001 ⇒ O1 = 1001101 - Fitness Function

Fitness Function is a function that tells you how good the individual is. - Selection Methods

Select some of the population for reproduction there are several method for selection

  • Roulette Wheel selection: Probability selection from all population with probability proportional of their fitness
  • Ranked selection: few fittest individual - Summary

Genetic Algorithm Summary:

  1. Choose the initial population
  2. Select parent chromosomes
  3. Perform crossover
  4. Perform mutation
  5. Evaluate fitness of the new population
  6. Repeat 2 until satisfied