Genetic algorithm

  • Post author:
Download PDF
Advertisement

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”
    Advertisement

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

Genetic Algorithm

 

Neural Networks

Advertisement