Week 4.1 - Genetic Algorithm

Aim

To optimize the stalagmite function and find out the global maxima of the function by write a program using MATLAB. To plot for the 3 case studies and find time to take running for each case.

Objective;

• To write a code in Matlab to optimize the stalagmite function and find the global Maxima Value of the function.
• To explain the concept of Genetic algorithm and explain the syntax of ga.
• To plot 3 case studies and for F Maxima and No. fo Iterations with respect to time.
• Introduction,

Stalagmite:

Stalagmites are convex deposits that grow upward, commonly fed by an overhanging stalactite, and show flat, rounded, or slightly hollow tops, but not a central canal as shown in fig. The morphology of stalagmites is mostly determined by the drip rate, and in particular by the interannual variability of the drip rate and by the distance from the tip of the feeding stalactite. By contrast, stalagmites fed by drips that show interannual constant time elapsed between two drops yield candle-shaped stalagmites.

Function:

The function used in the stalagmite,

Optimization:

Optimization is the process of making something better. In any process, we have a set of inputs and a set of outputs.It refers to finding the values of inputs in such a way that we get the “best” output values. The definition of “best” varies from problem to problem, but in mathematical terms, it refers to maximizing or minimizing one or more objective functions, by varying the input parameters.

The set of all possible solutions or values which the inputs can take makes up the search space. In this search space, lies a point or a set of points that gives the optimal solution. The aim of optimization is to find that point or set of points in the search space.

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 at random 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.

In a genetic algorithm, there are three types of rules to reach the next generation for the current generation.

• Selection
• Crossover
• Mutation

Selection:

The selection function chooses parents for the next generation based on their scaled values from the fitness scaling function. The scaled fitness values are called the expectation values. An individual can be selected more than once as a parent, in which case it contributes its genes to more than one child.

Crossover:

Crossover children by selecting vector entries, or genes, from a pair of individuals in the current generation and combining them to form a child.

Mutation:

Mutation children by applying random changes to a single individual in the current generation to create a child.

Syntax using in Genetic algorithm,

Here we use three syntax, that find the minimum value,

1. x=ga(fun,navrs)

This syntax used to find local unconstrained minimum value

fun- Function

navrs- No of dimensional variables,

2.x=ga(fun,navrs,A,b,Aeq, beq,lb,up)

This syntax is used to find local minimum function and apply the limits by upper bounds and lower bounds,

fun-Functions

navrs- No. of dimensional variables,

A,b-linear inequalities

Aeq,beq- Nonlinear inequalities,

lb, up- upper and Lower bounds,

3. x=ga(fun,navrs,A,b,Aeq,beq,up,lb,nonlcon,intcon,options)

This syntax used in minimum function with non linear constraints by using optimoption syntax,

abouve syntax used to optimize the particular set of values functions collecting form the total values of arrays.

Programs:

The programs that create a function of stalagmite,

%To create a function of stalagmite
function S=stg_fun(input_vector)

f1x=sin(5.1*pi*input_vector(1)+0.5)^6;
f1y=sin(5.1*pi*input_vector(2)+0.5)^6;
f2x=exp((-4*log(2))*((input_vector(1)-0.0667)^2/0.64));
f2y=exp((-4*log(2))*((input_vector(2)-0.0667)^2/0.64));

S=-f1x*f1y*f2x*f2y;
end

The Program that finding the Global Maxima,

clear all
close all
clc

x=linspace(0,0.6,150); %set  input arrays of x values
y=linspace(0,0.6,150); %setinput arrays of y values
% create a parmaeters using to runs no. of time in  ga
num_cases=50;


%Creating 2Dimensional mesh
[xx,yy]=meshgrid(x,y);

%Evaluate stalagmite function by using for loop 
for i=1:length(xx)
    for j=1:length(yy)
    input_vector(1)=xx(i,j);
    input_vector(2)=yy(i,j);
    S(i,j)=stg_fun(input_vector);
    end
end

%Study case 1-statistical behaviour
%To create a loop for upto the parameters to find optimation of max values
%using ga function wrt time taken.
tic  %To find time that while running
for k=1:num_cases
    [inputs, fopt(k)]=ga(@stg_fun,2); 
    xopt(k)=inputs(1);
    yopt(k)=inputs(2);
end
study1_time=toc;

figure(1)
subplot(2,1,1); 
hold on
surfc(xx,yy,-S);
shading interp
%plotting the optimizing values in the parameters with x, y values
plot3(xopt,yopt,-fopt,'Marker','o','markersize',5,'markerfacecolor','r');
subplot(2,1,2);
%Plotting optimized functions values
plot(fopt);
hold off
xlabel('iterations');
ylabel('Funtcion Maximum');
title('Unbounded inputs');


%Study case 2- Statistical behaviour with upper and lower bounds
%To create a loop for upto the parameters to find optimation of max values
%using ga function wrt time taken within the limits.
tic
for k=1:num_cases
    [inputs,fopt(k)]=ga(@stg_fun,2,[],[],[],[],[0;0],[1;1]);
    xopt(k)=inputs(1);
    yopt(k)=inputs(2);
end

study2_time=toc;
figure(2)
subplot(2,1,1);
hold on
surfc(x,y,-S);
shading interp;
%plotting the optimizing values in the parameters with x, y values
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
subplot(2,1,2);
%Plotting optimized functions values
plot(fopt);
hold off
xlabel('iterations');
ylabel('Funtcion Maximum');
title('Bounded inputs');


%Study case 3-Increasing GA iterations
%To create a loop for upto the parameters to find optimation of max values
%using ga function wrt time taken within the limits and returns set of
%parameters with options solver.

 options=optimoptions('ga');
 options=optimoptions(options,'PopulationSize',450);
tic
for k=1:num_cases
    [inputs,fopt(k)]=ga(@stg_fun,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(k)=inputs(1);
    yopt(k)=inputs(2);
end

study3_time=toc;
figure(3)
subplot(2,1,1);
hold on
surfc(x,y,-S);
shading interp;
%plotting the optimizing values in the parameters with x, y values
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r');
subplot(2,1,2);
%Plotting optimized functions values
plot(fopt);
hold off
xlabel('iterations');
ylabel('Funtcion Maximum');
title('Modifying the Population data');

Explanations:

First lets we create a random set of array x,y, and meshing into 2 Dimensional arrays by uisng mesh grid command, a nested loop create an array that's called input_vector.After creating a function from stalagmite using the formula of stalagmite function. let's make the function negative because we have to find the Global maxima value bit in the genetic algorithm function used to find out the Global minima value so we used negatives. Then we plot a stalagmite surface by using a function in the for loop command.

We have to plot a graph for three case studies for Function minimum and No. of iterations, In the first case, optimizing the functions that use ga syntax up to the parameters with the tic-tac command(find time while running functions), then give the negative sign for foot due to reason of having to calculate global maxima, then we plot the graph stalagmite with optimized values in the parameters and plot optimized functions.

In the second case, we optimized the function using ga with bounding which gave more accuracy and compare with the surface of stalagmite. In the third case that was used to find out the global maxima value of the array, using a ga syntax wiht solver 'optimizations' and when increase the populations to find out exact maxima value and plot in the stalagmite which used to find easy.

Graph:

Stalagmite Graph:

Plot for unbounded values

The plot of Bounded Inputs,

The plot of using Increase the Populations,

the plot has obtained the Global maxima.

Workspace data has been attached below

The image which I worked in the MATLAB,

Conclusion:

The Stalagmite function has been optimized and found the Global Maxima value is (x=0.0668,y=0.0668). The Genetic algorithm has been explained briefly and told about the ga syntax used in the program. Hence, Plotted all three case studies which were used to find the global maxima and sure it's been got the same values which runs several times.