Week 4.1 - Genetic Algorithm
Aim: To write a code in MATLAB to optimise the stalagmite function and find the global maxima.
Introduction:
What is Genetic Algorithm?
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.
. 
The genetic algorithm uses three main types of rules at each step to create the next generation from the current population as shown in the above image:
- 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.
It generates a population of points at each iteration. The best point in the population approaches an optimal solution. Selects the next population by computation which uses random number generators.
Working of Genetic Algorithm?
The following outline summarizes how the genetic algorithm works:
- The algorithm begins by creating a random initial population.
- The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create the new population, the algorithm performs the following steps:
- Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
- Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
- Selects members, called parents, based on their expectation.
- Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
- Produces children from the parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
- Replaces the current population with the children to form the next generation.
- The algorithm stops when one of the stopping criteria is met.
- The algorithm takes modified steps for linear and integer constraints.
- The algorithm is further modified for nonlinear constraints.
Function Description: Source - Mathworks
CODE for the following:
Now, Let us code the Stalagmite Function using two inputs as x & y which is given in the challenge to find the global maxima as shown below
%CREATING A FUNCTION OF STALAGMITE
function[f] = stalagmite(input_vector)
x = input_vector(1); %Let the 1st input be x.
y = input_vector(2); %Let the 2nd input be y.
%By using the given functions in the challenge, we code it as below
f1x = (sin(5.1*pi*x + 0.5))^6;
f1y = (sin(5.1*pi*y + 0.5))^6;
f2x = exp((-4*log(2)*(x-0.0667).^2)/0.64);
f2y = exp((-4*log(2)*(y-0.0667).^2)/0.64);
f = -(f1x.*f1y.*f2x.*f2y);
end
%Since the GA algorithm of matlab generates a minima, the negative sign is
%inserted which denotes that the plot will be reversed and the stalagmite function
%created will be inversed to find the global maxima instead of minima.
Main Program:
Part1:
%Important Commands to clear the temporary memory, close all plots and
%clear the command window.
close all
clear all
clc
% Defining the search space from 0 to 0.6 with 150 equal intervals.
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
%To create a 2d mesh
%[xx,yy] = meshgrid(x,y)
%Assigning values to inputs
for i = 1:length(x) %Takes the values until length of xx
for j = 1:length(y) %Takes values until length of yy
inputs(1) = x(i);
inputs(2) = y(j);
f(i,j) = stalagmite(inputs);
end
end
iterations = 50; %creating a variable and assigning the number to which iterations
performed
%f = get_stalagmite(x,y);
%Study case: 1
tic % Starts the timer
for z = 1:iterations % takes values until length of num_cases
[inputs,fopt(z)] = ga(@stalagmite,2);% solve stalagmite function using GA and
assigning to variables
xopt(z) = inputs(1);
yopt(z) = inputs(2);
end
Timestudy_1 = toc; % Gives time taken to perform the study case.
%Plotting
figure(1)
subplot(2,1,1) % Creates a sub plot in the figure
hold on
surfc(x,y,-f) % Creates a surface
shading interp % Varies the color in each line segment and face by interpolating the
colormap index or true color value across the line or face.
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')% Plot3 command
is used to plot in 3 axis
% marker is used to create a visible points on the plot
title('Unbounded Inputs') %Creates a title for the figure.
xlabel('X Axis')
ylabel('Y Axis')
zlabel('Z Axis')
subplot(2,1,2) %Subplot command is used to plot the figure in the same figure window.
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')Output Obtained is as follows:
PART 2:
% Study Case 2: Studying between upper and lower bounds
tic
for z = 1:iterations
[inputs,fopt(z)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4]);
%defines a set of lower and upper bounds on the design variables
xopt(z) = inputs(1);
yopt(z) = inputs(2);
end
Timestudy_2 = toc;
%Plotting
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')
xlabel('X Axis')
ylabel('Y Axis')
zlabel('Z Axis')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')Output for the above is as follows:
PART 3:
% Study Case 3: Studying with a population size with increased GA interations.
options = optimoptions('ga'); %returns a set of default options for the SolverName solver.
options = optimoptions(options,'PopulationSize',300); % Defining population size
tic
for z = 1:iterations
[inputs,fopt(z)] = ga(@stalagmite, 2,[],[],[],[],[0;0],[0.4;0.4],[],[],options);
% Takes the values of options and solves ga in required population.
xopt(z) = inputs(1);
yopt(z) = inputs(2);
end
Timestudy_3 = toc;
%Plotting
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Increased Population Size')
xlabel('X Axis')
ylabel('Y Axis')
zlabel('Z Axis')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')
Output of the above is as follows:
To Find the value of Global Maximum Value, we code as follows:
GMV_1 = -(mean(fopt1));
GMV_2 = -(mean(fopt2));
GMV_3 = -(mean(fopt3));Here, GMV refers to global maximum value of the respecting parts as given above.
Explanation of 3 Parts of the Program:
Part 1: In this study, we have not set the limits and the obtained global maximum is for the whole search space.
Part 2: In this study, we have set the upper bound and lower bound limits to the study so that the global maximum is found between them.
Part 3: In this study, we have also added the the population size to fiind the global maximum using the optimoptions.
Conclusion: Thus we have successfully understood the optimization technique using ga command.
The Time study for the cases performed is shown below.
The Global Maximum Value for all 3 parts is as follows.
Reference: Mathworks