AI-category

# 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

Neural Networks

### Prachi

NCERT-NOTES Class 6 to 12.

Check Also
Close