Week 4.1 - Genetic Algorithm

-Each chromosome indicates a possible solution. Thus the population is a collection of chromosomes

-A fitness function characterizes each individual in the population. Therefore, greater fitness better is the solution.

-Out of the available individuals in the population, the best individuals are used to reproduce the next generation offsprings.

-The offspring produced will have features of both the parents and is a result of mutation. A mutation is a small change in the gene structure.

Below are the different phases of the Genetic Algorithm:

1. Initialization of Population(Coding)

• Every gene represents a parameter (variables) in the solution. This collection of parameters that forms the solution is the chromosome. Therefore, the population is a collection of chromosomes.
• Order of genes on the chromosome matters.
• Chromosomes are often depicted in binary as 0’s and 1’s, but other encodings are also possible.

2. Fitness Function

• We have to select the best ones to reproduce offspring out of the available chromosomes, so each chromosome is given a fitness value.
• The fitness score helps to select the individuals who will be used for reproduction.

3. Selection

• This phase’s main goal is to find the region where getting the best solution is more.
• Inspiration for this is from the survival of the fittest.
• It should be a balance between exploration and exploitation of search space.
• GA tries to move the genotype to higher fitness in the search space.
• Too strong fitness selection bias can lead to sub-optimal solutions.
• Too little fitness bias selection results in an unfocused search.
• Thus, Fitness proportionate selection is used, also known as roulette wheel selection, as a genetic operator used in genetic algorithms to select potentially useful recombination solutions.

4. Reproduction

Generation of offsprings happen in 2 ways:

• Crossover
• Mutation

a) Crossover

Crossover is the most vital stage in the genetic algorithm. During crossover, a random point is selected while mating a pair of parents to generate offsprings.

There are 3 major types of crossover.

• Single Point Crossover: A point on both parents’ chromosomes is picked randomly and designated a ‘crossover point’. Bits to the right of that point are exchanged between the two parent chromosomes.
• Two-Point Crossover: Two crossover points are picked randomly from the parent chromosomes. The bits in between the two points are swapped between the parent organisms.
• Uniform Crossover: In a uniform crossover, typically, each bit is chosen from either parent with equal probability.

The new offspring are added to the population.

b) Mutation

In a few new offspring formed, some of their genes can be subjected to a low random probability mutation. This indicates that some of the bits in the bit chromosome can be flipped. Mutation happens to take care of diversity among the population and stop premature convergence.

5. Convergence (when to stop)

Few rules which are followed which tell when to stop is as follows:

• When there is no improvement in the solution quality after completing a certain number of generations set beforehand.
• When a hard and fast range of generations and time is reached.
• Till an acceptable solution is obtained.

close all
clear all
clc

function [f]=stalagmite(input_vector)

x=input_vector(1);
y=input_vector(2);

f1=(sin(5.1*pi*x+0.5)).^0.6 ;
f2=exp(-4*log(2)*((x-0.0667).^2)./0.64) ;
f3=(sin(5.1*pi*y+0.5)).^0.6 ;
f4=exp(-4*log(2)*((y-0.0667).^2)./0.64) ;

f=-(f*f2*f3*f4);
end

clear all
close all
clc

x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_cases=50;

%study1
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end

study_time(1)=toc;
figure(1);
subplot(2,1,1);
hold on
surface(x,y,-f);
shading interp
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('interation')
ylabel('function maximum')

% study2
tic
for i=1:num_cases
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[0.6,0.6]);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end

study_time(2)=toc;
figure(2)
subplot(2,1,1);
hold on
surface(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('optimum solution')
subplot(2,1,2)
plot(-fopt)
xlabel('interation')
ylabel('function maximum')

% study3
options=optimoptions(@ga);
options=optimoptions(options,'PopulationSize',170);

tic
for i=1:rep
[inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
xopt(i)=inputs(1);
yopt(i)=inputs(2);
end

study_time(3)=toc;
figure(3)
subplot(2,1,1);
hold on
surface(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'Marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('optimum solution')
subplot(2,1,2)
plot(-fopt)
xlabel('interation')
ylabel('function maximum')

global_maxima=-fopt;