Genetic Algorithms

 Introduction
 Genetic Algorithm
 Procedure of Genetic Algorithm
 The Working of Genetic Algorithm
 The logic Behind Genetic Algorithm
 Evolutionary Programming

COMPILED BY: ER. SANTOSH PANDEYA 1

Introduction
 Algorithm An algorithm is a sequence of instructions to solve a problem Most of the
algorithms are static

 A Genetic Algorithm(GA) is adaptive ( a model of machine learning algorithm that

derives its behavior from a metaphor of some of the mechanisms of evolution in
nature

COMPILED BY: ER. SANTOSH PANDEYA 2

On 1 July 1858 Charles Darwin presented his theory of evolution This day
marks the beginning of a revolution in Biology

Darwin ’s classical theory of evolution together with Weismann’s theory of

natural selection and Mandel’s concept of genetics now represent the Neo
Darwinism

Neo Darwinism is based on process of reproduction, mutation, competition

and selection

COMPILED BY: ER. SANTOSH PANDEYA 3

Background
 Evolution can be seen as a process leading to the maintenance of a population’s ability
to survive and reproduce in a specific environment This ability is called evolutionary
fitness

 Evolutionary fitness can also be viewed as a measure of the organism’s ability to

anticipate changes in its environment

 The fitness, or the quantitative measure of the ability to predict environmental changes
and respond adequately, can be
 considered as the quality that is optimized in natural life

COMPILED BY: ER. SANTOSH PANDEYA 4

Simulation of Natural Evolution
 All methods of evolutionary computation simulate natural evolution by creating a population of
individuals, evaluating their fitness, generating a new population through genetic operations, and
repeating this process a number of times

 We focus on Genetic Algorithm as most of the other algorithms can be viewed as variations of genetic
algorithms.

COMPILED BY: ER. SANTOSH PANDEYA 5

 Genetics Algorithms
 GAs were developed by John Holland and his students and colleagues at the
University of Michigan, most notably David E. Goldberg and has since been tried on
various optimization problems with a high degree of success.

 In GAs, we have a pool or a population of possible solutions to the given problem.

These solutions then undergo recombination and mutation (like in natural genetics),
producing new children, and the process is repeated over various generations.

 Each individual (or candidate solution) is assigned a fitness value (based on its
objective function value) and the fitter individuals are given a higher chance to
mate and yield more “fitter” individuals.

 This is in line with the Darwinian Theory of “Survival of the Fittest”.

 Each artificial “ consists of a number of “ and each gene is represented by 0 or 1

COMPILED BY: ER. SANTOSH PANDEYA 6

 Two mechanisms link a GA to the problem it is solving Encoding and Evaluation

 The GA uses a measure of fitness of individual chromosomes to carry out reproduction

 As reproduction takes place, the crossover operator exchanges part of two single chromosomes

 And the mutation operator changes the gene value in some randomly chosen location of the
chromosome

GA Operators and Parameters

 Fitness function The fitness function is defined over the genetic representation and measures the quality of the
represented solution

 Selection Operator Selects parents for reproduction based on relative fitness of candidates in the population

• Roulette Wheel Selection

• Ranking Selection

COMPILED BY: ER. SANTOSH PANDEYA 7

Once the initial generation is created, the algorithm evolves the generation using following operators –
1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow
them to pass their genes to successive generations.

2) Crossover Operator: This represents mating between individuals. Two individuals are selected using
selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are
exchanged thus creating a completely new individual (offspring). For example –

COMPILED BY: ER. SANTOSH PANDEYA 8

3) Mutation Operator:
 Changes a randomly selected gene in the chromosome mimics random changes in
genetic code
 Background operator to provide exploration in search to avoid being trapped on a local
optimum
 Mutation probability is quiet small in nature and is kept low for GAs, typically in the
range between 0 001 0 01 or by formula
 The key idea is to insert random genes in offspring to maintain the diversity in the
population to avoid premature convergence. For example –

COMPILED BY: ER. SANTOSH PANDEYA 9

COMPILED BY: ER. SANTOSH PANDEYA 10
Why use Genetic Algorithms

 They are Robust

 Provide optimisation over large space state.
 Unlike traditional AI, they do not break on slight change in input or presence of noise

Application of Genetic Algorithms Elitism Approach :Saves the best individual

in next generation
 Genetic algorithms have many applications, some of them are –
 Recurrent Neural Network Basic GA Parameters
 Mutation testing
 Code breaking • Population size
• Crossover rate (Probability)
 Filtering and signal processing
• Mutation Rate (Probability )
 Learning fuzzy rule base etc
• Number of Generation a Stopping
Criterion)

COMPILED BY: ER. SANTOSH PANDEYA 11

 Advantages of Gas

GAs have various advantages which have made them immensely popular. These include
−
•Does not require any derivative information (which may not be available for many real-
world problems).

•Is faster and more efficient as compared to the traditional methods.

•Has very good parallel capabilities.

•Optimizes both continuous and discrete functions and also multi-objective problems.

•Provides a list of “good” solutions and not just a single solution.

•Always gets an answer to the problem, which gets better over the time.

•Useful when the search space is very large and there are a large number of parameters
involved.

COMPILED BY: ER. SANTOSH PANDEYA 12

 Limitations of Gas

Like any technique, GAs also suffer from a few limitations. These include
−
•GAs are not suited for all problems, especially problems which are simple
and for which derivative information is available.

•Fitness value is calculated repeatedly which might be computationally

expensive for some problems.

•Being stochastic, there are no guarantees on the optimality or the

quality of the solution.

•If not implemented properly, the GA may not converge to the optimal
solution.

COMPILED BY: ER. SANTOSH PANDEYA 13

How the genetic algorithm works

The genetic algorithm works on the evolutionary generational cycle to generate high-
quality solutions. These algorithms use different operations that either enhance or replace
the population to give an improved fit solution.
It basically involves five phases to solve the complex optimization problems, which are
given as below:
 Initialization
 Fitness Assignment
 Selection
 Reproduction
 Termination

COMPILED BY: ER. SANTOSH PANDEYA 14

COMPILED BY: ER. SANTOSH PANDEYA 15
Steps in Genetic Algorithm
1. Represent the problem variable as a chromosome of a fixed length, choose the size of a chromosome
population N the crossover probability pc and the mutation probability pm
2. Define a fitness function to measure the fitness of an individual chromosome in the problem domain
3. Randomly generate an initial population of chromosomes of size N x 1 x 2 xN
4. Calculate the fitness of each individual chromosome f x 1 f x 2 f xN
5. Select a pair of chromosomes for mating from the current population based on their fitness
6. Create a pair of offspring chromosomes by applying the genetic operators crossover andmutation
7. Place the created offspring chromosomes in the new population
8. Repeat Step 5 until the size of the new chromosome population becomes equal to the size of the initial
population, N
9. Replace the initial ( chromosome population with the new (population
10.Go to Step 4 and repeat the process until the termination criterion is satisfied

COMPILED BY: ER. SANTOSH PANDEYA 16

COMPILED BY: ER. SANTOSH PANDEYA 17
Roulette Wheel Selection
The most commonly used chromosome selection technique is the roulette wheel selection

COMPILED BY: ER. SANTOSH PANDEYA 18

Genetic algorithms are used to solve many large problems including:

-Scheduling
-Transportation
-Chemistry, Chemical Engineering
-Layout and circuit design
-Medicine
-Data Mining and Data Analysis
-Economics and Finance
-Networking and Communication
-Game etc.

COMPILED BY: ER. SANTOSH PANDEYA 19

Evolutionary Programming
 Evolutionary programming is a technique used to search for the optimal solution to a problem by evolving a
population of candidate solution over a number of generations or iterations
 The solution is evolved through mutation and competitive selection
 The structure of an evolutionary programming ( algorithm is shown in figure below
 In this approach, the real valued decision variables to be determined are represented by a trial ndimensional
vector
 Each vector is an individual of the population to be evolved

COMPILED BY: ER. SANTOSH PANDEYA 20

Evolutionary Programming Vs Genetic Algorithm
 Genetic Algorithm ( methods are used for encoding, decoding and fitness function formulation

 Evolutionary Programming ( on the other hand, is better for obtaining the global optimum, which relies on
mutation rather than crossover

 Due to inherent flexibilities in the fitness function and the ease of coding, the EP method produces the best
solution with fewer generations

 EP is a probabilistic search technique which generates the initial parent vectors distributed uniformly in intervals
within the limits and obtains the global optimum solution over a number of iterations
 The main stages of this technique are initialization, creation of offspring vectors by mutation and competition and
selection of the best vectors in order to evaluate the best fitness solution

COMPILED BY: ER. SANTOSH PANDEYA 21