Week 4.1 - Genetic Algorithm
Aim
To optimize the stalagmite functions by using genetic algorithm and find the global minima of values.
Main objectives:
optimize the function by creating the stalagmite function with using the given equations.
Using the number of iterations and population sizes, global maxima and minima values can be obtained.
Also by using the syntax of ga function ,stalagmite values of global maxima occurred.
Genetic algorithm:
Genetic algorithm is a search-based optimization technique based on the principles of genetic and natural selection. It is frquently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve.
Phases of genetic algorithm
Below are the different phases of the genetic algorithm:
- 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.
- 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.
- 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.
- 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.
- 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.
Procedure :
coding the given equations and create as stalagmite functions and to be called in ga functions
initiate the x and y variable values by using the linspace command.
Convert the x and y variablex into 2d array which represented as [xx yy], for obtain the output in three dimensional plots.
Created 2d array values to be put in stalagmite in functions by calling the functions.
By using ga functions which is default function in mat lab to find the global maxima and minima values.
Ga function generally shows the value in maxima, but our concept is to find the minima values .
Minima values can be obtained by inversing the sign values (i.e, negative sign)
Study time can be calculated by using tic and toc command
Results are plotted in 3d by using surf plot and shading interpretation.
Syntax with program explanation:
Stalagmite function:
function [f] = stalagmite(input_vector)
x= input_vector(1);
y = input_vector(2);
f1= (sin(5.1*pi*x+0.5))^6;
f2 = (sin (5.1*pi*y+0.5))^6;
f3 = exp (-4*log(2)*(x-0.0667)^2/0.64);
f4 = exp(-4*log(2)*(y-0.0667)^2/0.64);
f = -(f1*f2*f3*f4);
end
CASE-1 (DEFINING THE FUNCTION WITHOUT ANY DEFINED BOUND AND LIMITS)
clear all
close all
clc
x= linspace(0,0.6,150); % X VALUES ARE ASSIGNED USING LINSPACE
y = linspace (0,0.6,150); % X VALUES ARE ASSIGNED USING LINSPACE
[xx,yy] = meshgrid(x,y); % CONVERTED INTO 2-DIMENSIONAL ARRAY
for i =1:length(xx)
for j =1:length(yy)
input_vector(1) = xx(i,j);
input_vector(2) = yy(i,j);
f(i,j) = stalagmite(input_vector);
end
end
num_cases = 50; % NUMBER OF ITERATIONS
tic % FOR STUDY TIME
for i = 1:num_cases
[inputs,f_opt(i)] = ga(@stalagmite,2); % GA IS THE DEFAULT TOOL WHICH IS BULIT-IN IN MATLAB AND USED FOR OPTIMIZATION
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
opt_f(i) = -f_opt(i); % GA DEFAULT VALUE ALWAYS IN MINIMA SO,INVERSE SIGN IS USED FOR MAXIMA
end
study1_time = toc %FOR STUDY TIME
subplot(2,1,1)
hold on
surfc(xx,yy,f) % FOR CREATING STALAGMITE
shading interp % FOR SMOOTH SURFACE WITHOUT ANY MESH LINES
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','r');
title('unbounded inputs')
subplot(2,1,2)
plot(opt_f)
xlabel('number of iterations')
ylabel('function max')CASE-2 ( UPPER AND LOWER BOUNDS ARE DEFINED)
clear all
close all
clc
x= linspace(0,0.6,150); % X VALUES ARE ASSIGNED USING LINSPACE
y = linspace (0,0.6,150); % Y VALUES ARE ASSIGNED USING LINSPACE
[xx,yy] = meshgrid(x,y); % CONVERTED INTO 2-DIMENSIONAL ARRAY
for i =1:length(xx)
for j =1:length(yy)
input_vector(1) = xx(i,j);
input_vector(2) = yy(i,j);
f(i,j) = stalagmite(input_vector);
end
end
num_cases = 100; % NUMBER OF ITERATIONS
tic % FOR STUDY TIME
for i = 1:num_cases
[inputs,f_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0 0],[0.6 0.6]); % GA IS THE DEFAULT TOOL WHICH IS BULIT-IN IN MATLAB AND USED FOR OPTIMIZATION
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
opt_f(i) = -f_opt(i); % GA DEFAULT VALUE ALWAYS IN MINIMA SO,INVERSE SIGN IS USED FOR MAXIMA
end
study2_time= toc
subplot(2,1,1)
hold on
surfc(xx,yy,f) % FOR CREATING STALAGMITE
shading interp % FOR SMOOTH SURFACE WITHOUT ANY MESH LINES
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','r');
title('unbounded inputs')
subplot(2,1,2)
hold on
plot(opt_f)
xlabel('number of iterations')
ylabel('function max')CASE -3 (NUMBER OF ITERATIONS & POPULATION SIZE ALSO INCREASED)
clear all
close all
clc
x= linspace(0,0.6,150);
y = linspace (0,0.6,150);
[xx,yy] = meshgrid(x,y);
for i =1:length(xx)
for j =1:length(yy)
input_vector(1) = xx(i,j);
input_vector(2) = yy(i,j);
f(i,j) = stalagmite(input_vector);
end
end
num_cases = 150;
options= optimoptions('ga');
options = optimoptions(options,'populationsize',450);
tic
for i = 1:num_cases
[inputs,f_opt(i)] = ga(@stalagmite,2,[],[],[],[],[0 0],[0.6 0.6],[],options);
x_opt(i) = inputs(1);
y_opt(i) = inputs(2);
opt_f(i) = -f_opt(i);
end
study3_time= toc
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_opt,y_opt,f_opt,'marker','o','markersize',4,'markerfacecolor','r');
title('unbounded inputs')
subplot(2,1,2)
hold on
plot(opt_f)
xlabel('number of iterations')
ylabel('function max')FOR CASE-1
STUDY_TIME = 5.4
FOR CASE-2
STUDY_TIME = 15.8
FOR CASE-3
STUDY_TIME = 116.8
CONCLUSION:
From case-1 without defining the bounds and limits ,cant able to find the exact result of optimization. From case-2 defining the upper and lower bounds , results can be better than the previous iterations. From case-3 , by defining the bounds and increasing the population sizes and number of iterations, results can be accurately defined.