Week 4.1 - Genetic Algorithm
AIM:
the main aim is to optimize the stalagmite function and to find the global maxima of the function by clearly explaining the concept of genetic algorithm and plotting the graph for the three studies i.e .unbounded inputs,bounded inputs, and bounded inputs with modified population size.
THEORY:
STALAGMITES:
A stalagmite is a type of rock formation that rises from the floor of a cave due to the accumulation of material deposited on the floor from ceiling drippings .stalagmites are typically composed of calcium cardonate but may consist of lava,mud,peat,pitch,sand,sinter and amberat.
GENETIC ALGORITHM:
in computer science and operations research ,a genetic algorithm is ametaheuristic inspired by the process of natural selection that belongs to the lager class of evolutionary algorithms .genetic algorithms are commonly used to generate high_quality solutions to optimization and search problems by relying on biologically inspirsed operators such as mutation ,crossover ,and selection.
WORKING PRINCIPLE:
genetic algorithm are stochastic search methods based on the principles of natural genetic systems .they perform a search in providing an optimal solution for the evalution function of an optimization problem .GAs ,each solution is closed as a string of finite length over a finite alphabet A.each string or chromosome is considred as an individual .A collection of M such individuals is called a population.
five phases are considerd in a genetic algorithm.
1.initial population
2.fitness function
3.selection
4.crossover
5.mutation
1.INITIAL POPULATION:
.the process begins with a set of individuals which is called a population .each individuals is a solution to the problem you want to solve
. an individual is characterized by a set of parameters known as genes .genes are joined into a string to form a chromosome
.in a genetic algorithm , the set of genes of an individuals is represented using a string ,in terms of an alphabet . usually ,binary values are used
2 . FITNESS FUNCTION:
. the fitness function determines how fit an individuals is .it gives a fittness score to each individual .the probability that an individual will be selected for reproduction is based on its fitness score
3. SELECTION:
. the idea of the selection phase is to select the fitness individuals and let them pass their genes to the next generation.
.two pairs of individuals are selected based on their fitness score . individuals with high fitness have more chances to be selected for reproduction
4. CROSSOVER
. crossover is the most significant phase in a genetic algorithm .for each pair of parents to be mated , a crossover point is chosen at random from within the genes
5.MUTATION:
.in certain new offspring formed ,some of their genes can be subjected to a mutation with a low random probability. this implies that some of the bits in the bit string can be flipped
EQUATIONS USED:
the function for the genetic algorithm of the global minima but in order to attain the maxima value the '-' is placed before the equation.
f(x,y) = f1.x*f2.x*f1.y*f2.y
where ,
f1.x = [sin(5.1πx+ 0.5)]^6
f1.y = [sin(5.1πy+0.5)]^6
f2.x = exp[-4ln(2)*(x-0.0667)^2/0.64]
f2.y = exp[-4ln(2)*(y-0.0667)^2/0.64]
the global maxima is as follows
f(x,y) = -(f1.x*f2.x*f1.y*f2.y)
PROCESS OF SOLVING:
the order in which the code is written is as below
1.write stalagmite function
2.evaluating the stalagmite function.
3.writing the code for unbounded inputs.
4. writing the code for the bounded inputs
5. writing the code for the bounded inputs with modifications population size
PROCEDURE:
1. writing the stalagmite function
. the stalagmite function is a core part of the code
. the function follows the formula stated in the equation used.
. the 'function' input is used to write a function code.
function[f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x +0.5)).^6;
f2 = exp(-4*log(2)*((x-0.0667).^2)./0.64);
f3 = (sin(5.1*pi*y+0.5)).^6;
f4 = exp(-4*log(2)*((y-0.0667).^2)./0.64);
f = -(f1*f2*f3*f4);
end
2. EVALUTAING THE STALAGMITE FUNCTION:
. code is written to check if the function is returning an output.
.the function creates a 3d plot showing the algorithm.
% initial input values
lower_bound = input('enter the lower bound value: ');
upper_bound = input('enter the upper bound value: ');
% input variables with proper line spaces
x = linspace(lower_bound,upper_bound,150);
y = linspace(lower_bound,upper_bound,150);
%3d matrix creation
[xx,yy] = meshgrid(x,y);
count = 50; % giving the count/num of iterations for the optimal generation
tic % tic starts the clock time for the function
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
study_ time = toc; %toc stops the timer and shows the end time
figure(1)
surfc(xx,yy,-f)
shading interp
xlabel('x label')
ylabel('y label')
legend('x values','y values')
title('stalagmite function')
seveas(1,'stalagmite.png')
3. WRITING THE CODE FOR UNBOUNDED INPUTS:
.for the unbounded stalgamites the code starts with a' for' loop having the inputs and optimal function with calling the function .
. GA is explained clearly in the 'terms used'
. the plot is generated with unbouned stalgmites
% study 1 unbounded /randam samling inputs
tic
for i = 1: count
[inputs,fopt(i)] = ga (@stalagmite,2);
xopt(i) = inputs(1);
yopt (i) = inputs(2);
end
studytime_1 = toc;
figure(2)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('unbounded inputs')
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor',#edb120');
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')
saveas(2,'unbound input.png')
4. WRITING THE CODE FOR BOUNDED INPUTS
. the code is written for the genetic algorithm function built in inside the matlab an empty array is created with starting and ending points of the x and y values
. the plot is created with inputs in the proper order .
% study 2 - statistical behaviour with upper and lower bound sampling
tic
for i = 1: count
[inputs,fopt(i)] = ga (@stalagmite,2,[],[],[],[],[lower_bound;lower_bound];[upper_bound;upper_bound]);
xopt(i) = inputs(1);
yopt (i) = inputs(2);
end
studytime_2 = toc;
figure(3)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('bounded inputs')
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor',#edb120');
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')
saveas(3,'bound input.png')
5 WRITING THE CODE FOR THE BOUNDED INPUTS WITH MODIFIED POPULATION SIZE
.the code begins with the writting 'optimoptions'.the details are given in the 'term used'
. the plot is then created as the previous method.
. the global maxima is calculated.
% study 3 -code for upper and lower bound sampling and increase the % population size
options = optimoptions(@ga);
options = optimoptions(options,'populationsize',170);
tic;
for i = 1: count
[inputs,fopt(i)] = ga (@stalagmite,2,[],[],[],[],[lower_bound;lower_bound];[upper_bound;upper_bound]);
xopt(i) = inputs(1);
yopt (i) = inputs(2);
end
studytime_3 = toc;
figure(4)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
title('bounded inputs with modified population size')
xlabel('x value')
ylabel('y value')
hold on
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','c');
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function maximum')
saveas(4,'bound inputs with modified population size .png')
global_maxima = -fopt % finding the global maxima
CODE:
FOR FUNCTION
function [f] =stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
f1 = (sin(5.1*pi*x+0.5)).^6;
f2 = exp(-4*log(2)*((x-0.0667).^2)./0.64);
f3 = (sin(5.1*pi*y+0.5)).^6;
f4 = exp(-4*log(2)*((y-0.0667).^2)./0.64);
f = -(f1*f2*f3*f4);
end
FOR MAIN FUNCTION
clear all
close all
clc
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50
[xx yy] = meshgrid(x,y);
% evaluating the stalagmite function
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
tic
% study1 - satistical behavior
for i =1:num_cases
[inputs,fopt(i)] = ga(@stalagmite, 2);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study1_time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(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('iterations')
ylabel('function minimum')
tic
% study2 - satistical behavior- eith upper and lower bounds
for i =1:num_cases
[inputs,fopt(i)] = ga(@stalagmite, 2,[],[],[],[],[0;0],[0.1;0.1]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study2_time = toc
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('iterations')
ylabel('function minimum')
% study 3 increasing GA iterations
options = optimoptions ('ga');
options = optimoptions(options,'populationsize',250);
tic
for i =1:50
[inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study3_time = toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('iterations')
ylabel('function minimum')
ERROR:
the error were made which were simple syntax errors that are rectified right away with the help of the instructions in the command window.
TERMS USED:
. for random inputs:
x= ga(fun,nvars) finds a local unconstrained minimum x to the objective function , fun nvars is the dimension
. for bounded inputs :
x = ga defines a set of lower and upper bounds on the dedsign variables x ,so that a solution is found in the range
. for population size :
x = ga requries that the variables listed in intcon take integer values.
where,
fun -function,
nvars- number of variables
A- linear inequality constraints
B- linear inequality constraints
lb- lower bounds
ub- upper bounds
nonlcon- non-linear constranits
intcon- integer constraints
2 SURFC:
surfc function contours the plot under the surface plot. surfc(x,y,z) creates a three dimensional surface plot with a contour plot underneat. a surface plot is a three dimensional surface that has solid edge colors and solid face colors .thje function plots the values in matrix z as heights above a grid in the x-y plane defined by x- y .the colors of the surface varies according to the heights specified by z
3.SHADING:
the shading function controls the color shading of surface and patch graphics object
the shading flat each mesh line segment and the face a constant color determined by the color value at the end point of the segment or the corner of the face that has the smallest index
shading faceted flat shading with supermposed black mesh lines .this is the default shading mode.
4 PLOT3:
plot 3(x,y,z)plots coordinates in 3-d space.
to plot a set of coordinates by line segment ,specific x,y,z,as vectors of the same length
5 OPTIMOPTIONS:
options = optimoptions returns a set of default options for the solvername solver.
options = optimoptions returns a copy of oldoptions with the named parameters altered eith the specified values .
6. TIC-TOC:
tic works with the toc function to measure elapsed time . the 'tic' function records the current time , and the toc function uses the recored value to calculate the elapsed time.
RESULTS:
stalagmite function
UNBOUNDED INPUTS:
BOUNDED INPUTS
BOUNDED INPUTS WITH MODIFIED POPULATION SIZE
THE above results shown that the bounded samples with population size have an accurate solution .this is because the code shows the random samples which can start and end at the random points
to overcome the issuse the bounded samples method is used giving the lower and upper limits are greather than upper bound or less than the lower bound
this loop given an output with different local maxima with bounded inputs . to conquer this problem ,we need to increase the population size as it increase the probabilitry to converage to a global maximaum.
the global maximum of a function can be found by inverting the function .find the minimum value of the inverted function , the neagative of the minimum value will give the global maximum of the function