Unit 3: Soft Computing(SC-401T)

Genetic Algorithms

Genetic Algorithms(GAs) are adaptive heuristic search algorithms that belong to the larger part
of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection
(Evolution) and genetics. This concept of "genetics" and "evolution" forms the foundation of
GAs and their application to probabilistic search techniques. GAs are a subset of a much larger
branch of computation known as Evolutionary Computation. GAs were developed by John
Holland and his students and colleagues at the University of Michigan.

These are intelligent exploitation of random searches provided with historical data to direct the
search into the region of better performance in solution space. They are commonly used to
generate high-quality solutions for optimization problems and search problems.

Genetic algorithms simulate the process of natural selection which means those species that
can adapt to changes in their environment can survive and reproduce and go to the next
generation. In simple words, they simulate “survival of the fittest” among individuals of
consecutive generations to solve a problem. Each generation consists of a population of
individuals and each individual represents a point in search space and possible solution. Each
individual is represented as a string of character/integer/float/bits. This string is analogous to the
Chromosome.

Foundation of Genetic Algorithms

Genetic algorithms are based on an analogy with the genetic structure and behavior of
chromosomes of the population. Following is the foundation of GAs based on this analogy –
1. Individuals in the population compete for resources and mate
2. Those individuals who are successful (fittest) then mate to create more offspring than
others
3. Genes from the “fittest” parent propagate throughout the generation, that is sometimes
parents create offspring which are better than either parent.
4. Thus each successive generation is more suited for their environment.

Basic Terminology

Before beginning a discussion on Genetic Algorithms, it is essential to be familiar with some

basic terminology:

1. Population: It is a subset of all the possible (encoded) solutions to the given problem.
The population for a GA is analogous to the population for human beings except that
instead of human beings, we have Candidate Solutions representing human beings.

2. Chromosomes: A chromosome is one such solution to the given problem.

 3. Gene: A gene is one element position of a chromosome.

4. Allele: It is the value a gene takes for a particular chromosome.

5. Genotype: Genotype is the population in the computation space. In the computation

space, the solutions are represented in a way which can be easily understood and
manipulated using a computing system.

6. Phenotype: Phenotype is the population in the actual real world solution space in which
solutions are represented in a way they are represented in real world situations.

7. Fitness Function: A fitness function simply defined is a function which takes the
solution as input and produces the suitability of the solution as the output. In some
cases, the fitness function and the objective function may be the same, while in others it
might be different based on the problem.

Decoding and Encoding:

For simple problems, the phenotype and genotype spaces are the same. However, in most of
the cases, the phenotype and genotype spaces are different. Decoding is a process of
transforming a solution from the genotype to the phenotype space, while encoding is a process
of transforming from the phenotype to genotype space. Decoding should be fast as it is carried
out repeatedly in a GA during the fitness value calculation.
Search space

The population of individuals is maintained within search space. Each individual represents a
solution in search space for a given problem. Each individual is coded as a finite length vector
(analogous to chromosome) of components. These variable components are analogous to
Genes. Thus a chromosome (individual) is composed of several genes (variable components).

The population is usually defined as a two dimensional array of – size population, size x,
chromosome size.

There are two primary methods to initialize a population in a GA. They are −

​ 1. Random Initialization − Populate the initial population with completely

random solutions.
​ 2. Heuristic initialization − Populate the initial population using a known
heuristic for the problem.

Basic Structure of GA
The basic structure of a GA is as follows −

We start with an initial population (which may be generated at random or seeded by other
heuristics), select parents from this population for mating. Apply crossover and mutation
operators on the parents to generate new off-springs. And finally these off-springs replace the
existing individuals in the population and the process repeats. In this way genetic algorithms
actually try to mimic human evolution to some extent.

A generalized pseudo-code for a GA is explained in the following program:

GA()
initialize population
find fitness of population
while (termination criteria is reached) do
parent selection
crossover with probability pc
mutation with probability pm
decode and fitness calculation
survivor selection
find best
return best
Operators of Genetic Algorithms

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 a 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 –

3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the
diversity in the population to avoid premature convergence. For example –

Application to Probabilistic Search:

GAs are applied to probabilistic search techniques because they offer several advantages:

● Global Optimization: GAs can explore a large search space and find near-optimal or
optimal solutions, even in the presence of multiple local optima.
● Robustness: GAs are relatively insensitive to noise and can handle complex and noisy
problems.
● Efficiency: GAs can be computationally efficient, especially for large-scale problems.
● Flexibility: GAs can be adapted to solve a wide range of problems, including
optimization, machine learning, and design.
By mimicking the processes of genetics and evolution, GAs provide a powerful framework for
solving a variety of search and optimization problems.

Probabilistic Search Techniques

Probabilistic search techniques are a class of algorithms that use randomness to explore the
search space and find solutions to optimization problems. These techniques are particularly
effective when the search space is large, complex, or has multiple local optima.

Here are some of the most common probabilistic search techniques:

1. Genetic Algorithms (GAs)

● Inspired by: Natural selection and evolution.

● How it works: A population of potential solutions (chromosomes) is generated. The
fittest individuals are selected based on a fitness function, and they reproduce to create
a new generation. Genetic operators like crossover and mutation are applied to
introduce diversity and explore the search space.
● Advantages: Can handle complex problems with multiple local optima, robust, and
efficient for large-scale problems.

2. Simulated Annealing (SA)

● Inspired by: The annealing process in metallurgy.

● How it works: Starts with a high temperature and gradually cools down. At higher
temperatures, the algorithm is more likely to accept worse solutions, allowing it to
explore the search space. As the temperature decreases, the algorithm becomes more
selective, focusing on improving the solution.
● Advantages: Can avoid getting stuck in local optima, effective for problems with a
complex energy landscape.

3. Particle Swarm Optimization (PSO)

● Inspired by: The behavior of bird flocks and fish schools.

● How it works: A swarm of particles moves through the search space, each updating its
position based on its own experience and the experiences of its neighbors. Particles are
attracted to the best solution found so far.
● Advantages: Simple to implement, often converges quickly, and can be effective for
optimization problems with continuous variables.

4. Ant Colony Optimization (ACO)

● Inspired by: The behavior of ants foraging for food.

 ● How it works: Ants deposit pheromones on the paths they take, and other ants are
more likely to follow paths with higher pheromone levels. This positive feedback
mechanism helps the ants find the shortest paths between their nest and food sources.
● Advantages: Effective for combinatorial optimization problems like the traveling
salesman problem, can handle dynamic environments.

5. Tabu Search

● How it works: Maintains a tabu list of recently visited solutions to prevent the algorithm
from cycling. This helps avoid local optima.
● Advantages: Can be effective for problems with complex constraints or multiple local
minima.

6. Hill Climbing

● How it works: Starts with a random solution and iteratively moves to neighboring
solutions with better fitness.
● Advantages: Simple and easy to implement, but can get stuck in local optima.

Choosing the right probabilistic search technique depends on the specific characteristics of
the problem, such as the size of the search space, the complexity of the fitness function, and
the presence of multiple local optima. It's often useful to experiment with different techniques to
find the best approach for a given problem.

Solving single‐objective optimization problems using GAs.

A Genetic Algorithm (GA) is a meta-heuristic optimization algorithm inspired by the process of
natural selection.
1. Initialization:
○ Generate an initial population of individuals, each representing a potential
solution to the problem.
○ Each individual is encoded as a chromosome, which is a string of genes.

2. Fitness Evaluation:
○ Evaluate the fitness of each individual in the population using a fitness function.
○ The fitness function measures how well an individual solves the problem.

3. Selection:
○ Select individuals for reproduction based on their fitness.
○ Common selection methods include:
■ Roulette wheel selection
■ Tournament selection
■ Rank-based selection
 4. Crossover:
○ Combine the genetic material of selected individuals to create offspring.
○ Crossover involves swapping parts of the chromosomes of two parents.

5. Mutation:
○ Introduce random changes to the offspring's chromosomes.
○ Mutation helps to explore new areas of the search space and avoid local optima.

6. Replacement:
○ Replace a portion of the old population with the newly created offspring.

7. Termination:
○ The algorithm terminates when a certain stopping criterion is met, such as
reaching a maximum number of generations or finding a satisfactory solution.

Fitness Selection
Fitness Proportionate Selection is one of the most popular ways of parent selection. In this
every individual can become a parent with a probability which is proportional to its fitness.
Therefore, fitter individuals have a higher chance of mating and propagating their features to the
next generation. Therefore, such a selection strategy applies a selection pressure to the more fit
individuals in the population, evolving better individuals over time.

Consider a circular wheel. The wheel is divided into n pies, where n is the number of individuals
in the population. Each individual gets a portion of the circle which is proportional to its fitness
value.

Two implementations of fitness proportionate selection are possible:

1. Roulette Wheel Selection

In a roulette wheel selection, the circular wheel is divided as described before. A fixed
point is chosen on the wheel circumference as shown and the wheel is rotated. The
region of the wheel which comes in front of the fixed point is chosen as the parent. For
the second parent, the same process is repeated.
Implementation wise, we use the following steps −

● Calculate S = the sum of a fitness.

● Generate a random number between 0 and S.
● Starting from the top of the population, keep adding the finesses to the partial sum P, till
P<S.
● The individual for which P exceeds S is the chosen individual.

2. Tournament Selection

In K-Way tournament selection, we select K individuals from the population at random and
select the best out of these to become a parent. The same process is repeated for selecting the
next parent. Tournament Selection is also extremely popular in literature as it can even work
with negative fitness values.
3. Rank Selection

Rank Selection also works with negative fitness values and is mostly used when the individuals
in the population have very close fitness values (this happens usually at the end of the run).
This leads to each individual having an almost equal share of the pie (like in case of fitness
proportionate selection) as shown in the following image and hence each individual no matter
how fit relative to each other has an approximately same probability of getting selected as a
parent. This in turn leads to a loss in the selection pressure towards fitter individuals, causing
the GA to make poor parent selections in such situations.

In this, we remove the concept of a fitness value while selecting a parent. However, every
individual in the population is ranked according to their fitness. The selection of the parents
depends on the rank of each individual and not the fitness. The higher ranked individuals are
preferred more than the lower ranked ones.

Chromosome Fitness Value Rank

A 8.1 1

B 8.0 4

C 8.05 2

D 7.95 6

E 8.02 3

F 7.99 5
Introduction to Crossover
The crossover operator is analogous to reproduction and biological crossover. In this
more than one parent is selected and one or more off-springs are produced using the
genetic material of the parents. Crossover is usually applied in a GA with a high
probability – pc .

1. One Point Crossover

In this one-point crossover, a random crossover point is selected and the tails of its two
parents are swapped to get new off-springs.

2. Multi Point Crossover

Multi point crossover is a generalization of the one-point crossover wherein alternating

segments are swapped to get new off-springs.

3. Uniform Crossover

In a uniform crossover, we don’t divide the chromosome into segments, rather we treat
each gene separately. In this, we essentially flip a coin for each chromosome to decide
whether or not it’ll be included in the off-spring. We can also bias the coin to one parent,
to have more genetic material in the child from that parent.
Introduction to Mutation
In simple terms, mutation may be defined as a small random tweak in the chromosome,
to get a new solution. It is used to maintain and introduce diversity in the genetic
population and is usually applied with a low probability – pm. If the probability is very
high, the GA gets reduced to a random search.

Mutation is the part of the GA which is related to the “exploration” of the search space. It
has been observed that mutation is essential to the convergence of the GA while
crossover is not.

1. Bit Flip Mutation

In this bit flip mutation, we select one or more random bits and flip them. This is used for
binary encoded GAs.

2. Random Resetting

Random Resetting is an extension of the bit flip for the integer representation. In this, a
random value from the set of permissible values is assigned to a randomly chosen
gene.

3. Swap Mutation

In swap mutation, we select two positions on the chromosome at random, and

interchange the values. This is common in permutation based encodings.

4. Scramble Mutation
Scramble mutation is also popular with permutation representations. In this, from the
entire chromosome, a subset of genes is chosen and their values are scrambled or
shuffled randomly.

5. Inversion Mutation

In inversion mutation, we select a subset of genes like in scramble mutation, but instead
of shuffling the subset, we merely invert the entire string in the subset.

Different GA Architectures
While the basic GA framework remains the same, different architectures can be employed to
tailor the algorithm to specific problem domains:

1. Simple Genetic Algorithm (SGA)

Simple Genetic Algorithm (SGA) is one of the three types of strategies followed in Genetic
algorithm.
1. SGA starts with the creation of an initial population of size N.
2. Then, we evaluate the goodness/fitness of each of the solutions/individuals.

After that, the convergence criterion is checked, if it meets then we converge the algorithm
otherwise go for the next steps –

1. Select Np individuals from the previous population.

2. Create the mating pool randomly.
3. Perform Crossover.
4. Perform Mutation in offspring solutions.
5. Perform inversion in offspring solutions.
6. Replace the old solutions of the last generation with the newly created solutions and go
to step (2).
2. Steady-State Genetic Algorithm (SSGA)

SSGA stands for Steady-State Genetic Algorithm. It is steady-state meaning that there are no
generations. It differs from the Simple Genetic Algorithm, as in that tournament selection does
not replace the selected individuals in the population, and instead of adding the children of the
selected parents into the next generation, the two best individuals out of the two parents and
two children are added back into the population so that the population size remains constant.
Pseudocode :
● Generate initial population of size N.
● Evaluate each solutions’ fitness/goodness.
● Select 2 solutions as parents without repetition.
● Do Crossover, Mutation and Inversion and create 2 offspring.
● If offspring are duplicated, then go to step 3.
● If Not, then evaluate the fitness of offspring.
● If offspring are better than the worst solutions then replace the worst individuals with the
offspring such that population size remains constant.
● Check for convergence criteria.
● If convergence criteria are met, then terminate the program else continue with step 3.
3. Micro-Genetic Algorithm (μGA)

A Micro-Genetic Algorithm (μGA) is a metaheuristic that uses genetic operators to improve a

small population of solutions. It's designed to find the most-fit solution while reducing
computational resource usage.

Characteristics of μGA:

● Small population
○ μGA uses a small population approach, which can reach the near-optimal region
faster than Simple Genetic Algorithms (SGA).
● Elitism
○ μGA uses high levels of elitism to achieve the most-fit solution.
● Restart population
○ To avoid stagnation, μGA uses a restart population method to keep the best
solution and reset the others.
● Local search
○ The inner loop of μGA explores the solution space around the elite, which is a
local search feature.
● Global search
○ After the inner loop converges, the outer loop uses a random number generator
to regenerate all individuals, except for one elite from the parent generation.

Applications of μGA:
● Cancer data classification: A memetic μGA can be used to select the most relevant
genes from microarray cancer data.
● Biorobotic pectoral fin platform: A μGA can be used to optimize gait space and discover
new gaits that optimize thrust force production.
● Function optimization: A μGA can be used to solve non-stationary function optimization
problems.

The choice of GA architecture depends on factors such as the problem complexity,

computational resources, and desired level of performance. By understanding the basic
framework and different architectures, you can effectively apply GAs to a wide range of
optimization problems.

Advantages of GAs
● Global Optimization: GAs can explore a wide range of solutions and avoid getting stuck
in local optima.
● Robustness: They can handle complex, non-linear, and discontinuous problems.
● Flexibility: GAs can be adapted to various optimization problems by modifying the
representation, fitness function, and genetic operators.
 ● Parallelism: GAs can be easily parallelized to improve performance.

Application Areas

Genetic Algorithms are primarily used in optimization problems of various kinds, but they are
frequently used in other application areas as well.

1. Optimization − Genetic Algorithms are most commonly used in optimization problems

wherein we have to maximize or minimize a given objective function value under a given
set of constraints. The approach to solve Optimization problems has been highlighted
throughout the tutorial.
2. Economics − GAs are also used to characterize various economic models like the
cobweb model, game theory equilibrium resolution, asset pricing, etc.
3. Neural Networks − GAs are also used to train neural networks, particularly recurrent
neural networks.
4. Parallelization − GAs also have very good parallel capabilities, and prove to be very
effective means in solving certain problems, and also provide a good area for research.
5. Image Processing − GAs are used for various digital image processing (DIP) tasks as
well like dense pixel matching.
6. Vehicle routing problems − With multiple soft time windows, multiple depots and a
heterogeneous fleet.
7. Scheduling applications − GAs are used to solve various scheduling problems as well,
particularly the timetabling problem.
8. Machine Learning − as already discussed, genetics based machine learning (GBML) is
a niche area in machine learning.
9. Robot Trajectory Generation − GAs have been used to plan the path which a robot
arm takes by moving from one point to another.
[Link] Design of Aircraft − GAs have been used to design aircrafts by varying the
parameters and evolving better solutions.
[Link] Analysis − GAs have been used to determine the structure of DNA using
spectrometric data about the sample.
[Link] Optimization − GAs are obviously very good approaches for multimodal
optimization in which we have to find multiple optimum solutions.
[Link] salesman problem and its applications − GAs have been used to solve the
TSP, which is a well-known combinatorial problem using novel crossover and packing
strategies.