Week 4.1 - Genetic Algorithm
Genetic Algorithm
problem
To calculate the global maxima of a stalagmite function using matlab
by optimaizing the stalagmite function 7 to determine the global maxima of the function
global maxima of stalagmite function can be obtain by using a genetic algorithm in matlab
The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals from the current population to be parents and uses them to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution. You can apply the genetic algorithm to solve a variety of optimization problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.
This flow chart outlines the main algorithmic steps. For details, see How the Genetic Algorithm Works.
The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:
Selection rules select the individuals, called parents, that contribute to the population at the next generation. The selection is generally stochastic, and can depend on the individuals' scores.
Crossover rules combine two parents to form children for the next generation.
Mutation rules apply random changes to individual parents to form children.
The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table:
Classical AlgorithmGenetic Algorithm
Generates a single point at each iteration. The sequence of points approaches an optimal solution.
Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a deterministic computation.
Selects the next population by computation which uses random number generators.
Typically converges quickly to a local solution.
Typically takes many function evaluations to converge. May or may not converge to a local or global minimum
a class of algorithm bsed on abstraction of darwin evolution of biological systems pioneered by him , he was probably
the first to use genetic operations such as the crossover and recombination, mutation, and selection in the study of adaptive and artificial systems.
three main components or genetic operators in genetic algorithm are crossover,mutation,selection of fittest
the genetic algorithm canbe applied to solve avariety of optimaization problems that are not well suited for standard optimization
algorithm,including problems in which the objective fuction is discontinuous , non-differentialble,stochastic or highly non linear
stepwize of genetic algorithm
the following outline summarize how to the genetic algorithm works
1)the algorithm begins by creating a random initial population.
2)the algorithm then creates a sequence of new population. at each step , the algorithm uses the individuals in
the current generation to create the new population , to creatw the new population , the algorithm perform the following
steps;
a)scores each member of the current population by computing its fitness value.these values are called the raw fitness scores
b)scales the raw fitness scores to convert them into a more usable range of values these values are called expection values .
c)selects members , called parents ,based on their expectaion.
d)some of the individuals in the current population they have lower fitness are choosen as elite ,these elite individual
are passed to the next population
e)produces children from parents. children are produced either by making random changes to single parent mutation or
by combining the vector entries of the pair of parent crossover
f)replaces the current population with the children to form the next generation.
3)The algorithm stops when one of the stopping criteria is met
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
function for stalagmite
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*-1;
end
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Procedure of coding
1)initially, the stalagmite function was mentioned with appropriate argument vectors
2)the program has been subdivided into three studies based on the limitation of the previous study.
3)first study deals with unbounded inputs, thereby explainning the boundry where in the results
can be obtained
4)second study brings in their aspects of bounded inputs providing a better solution for the drowback faced
5)third study lays a apprecible platform to determine the exact solution.
6)plots of all the three studies have been display give sights of results.
7)global maxima is calculated by population sizing and the plots provide a visual context of the solution
and verifies the authenticity of the obtained value syntax for ga [x,fval] = ga(@fitnessfun, nvars, options).
Study1 will show unbounded inputs
Study2 will show bounded inputs
Study3 will show bounded inputs with modified population size
are attched in attachments following code represents as follows
xxxxxx
Reference from internet from following websites taken
https://se.mathworks.com/help/gads/what-is-the-genetic-algorithm.html
https://en.m.wikipedia.org/wiki/Genetic_algorithm
https://skill-lync.com/premium/allchallenges/76317
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
code
clear all
close all
clc
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
%converting 1D array into 2D array
[xx,yy] = meshgrid(x,y);
iterations = 50;
%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
% 1st iteration - studying the statistical behaviour
tic
for i = 1:iterations
[inputs,f_optimum(i)] = ga(@stalagmite,2);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end
iteration_1_time = toc
%plotting
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')
%2nd iterations with upper and lower limits
tic
for i = 1:iterations
[inputs,f_optimum(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end
iteration_2_time = toc
%plotting
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs')
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')
%3rd iteration - increasing the size f population
options = optimoptions('ga');
options = optimoptions(options,'populationsize',200)
tic
for i= 1:iterations
[inputs,f_optimum(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.2;0.2],[],[],options);
x_optimum(i) = inputs(1);
y_optimum(i) = inputs(2);
end
iteration_3_time = toc
%plotting
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)
shading interp
plot3(x_optimum,y_optimum,f_optimum,'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded inputs eith modified population size')
hold off
subplot(2,1,2)
plot(f_optimum)
xlabel('Iterations')
ylabel('Function maximum')
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Reference from internet from following websites
https://se.mathworks.com/help/gads/what-is-the-genetic-algorithm.html
https://en.m.wikipedia.org/wiki/Genetic_algorithm
https://skill-lync.com/premium/allchallenges/76317