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:

Domain	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

1.1.2.1 - 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.”

1.1.2.2 - 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.

1.1.2.3 - 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

1.1.2.4 - 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

1.1.2.5 - Fitness Function

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

1.1.2.6 - 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

1.1.2.7 - Summary

Genetic Algorithm Summary:

Choose the initial population
Select parent chromosomes
Perform crossover
Perform mutation
Evaluate fitness of the new population
Repeat 2 until satisfied