Challenge

Week 4 - Genetic Algorithm

AAditya Kumar Jha12 Jun 2020

AIM:

To optimize the Stalagmite function and find the Global Maxima of the function using MATLAB.

THEORY:

John Holland introduced genetic algorithms in 1960 based on the concept of Darwin's theory of evolution, and his student David E. Goldberg further extended GA in 1989. A genetic algorithm is a search heuristic where the fittest individuals are selected for reproduction in order to produce offspring of the next generation. Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problem by relying on biologically inspired operators such as mutation, crossover and selection. 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. We 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, non differentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

The difference between Classical Algorithm and Genetic Algorithm are as follows:-

Classical Algorithm	Genetic 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.

Five phases are considered in a genetic algorithm.

Initial population
Fitness function
Selection:
Crossover
Mutation

The genetic algorithm uses three main types of rules at each step to create the next generation from the current population:

Selection rulesselect the individuals, called parents, that contribute to the population at the next generation.
Crossover rulescombine two parents to form children for the next generation.
Mutation rulesapply 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.

OBJECTIVES:

To optimize the stalagmite function.
And also find the global maxima of the function.

Outline for the 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.

Syntax for ga:

x= ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.
Note:-Passing Extra Parameters (Optimization Toolbox) explains how to pass extra parameters to the objective function and nonlinear constraint functions, if necessary.
x= ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').
x= ga (fun,nvars,A,b,Aeq,beq)finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').
x= ga(fun,nvars,A,b,Aeq,beq,lb,ub) defines a set of lower and upper bounds on the design variables, x, so that a solution is found in the range lb ≤ x ≤ ub. (Set Aeq=[] and beq=[] if no linear equalities exist.)
x= ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)
x= ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.
x=ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.
Note:-When there are integer constraints, ga does not accept nonlinear equality constraints, only inequality constraints.
x= ga(problem) finds the minimum for problem, where problem is a structure.
[x,fval]= ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.
[x,fval,exitflag,output] = ga(___)also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.
[x,fval,exitflag,output,population,scores]= ga(___)also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

GOVERNING EQUATIONS:

STALAGMIT FUNCTION:

`f(x,y)=f_(1,x) f_(2,x) f_(1,y) f_(2,y)`

Where,

`f_(1,x)=〖[sin⁡(5.1πx+0.5)]〗^6`

`f_(1,y)=〖[sin⁡(5.1πy+0.5)]〗^6`

`f_(2,x)=exp[-4ln⁡(2)〖(x-0.0667)〗^2/0.64]`

`f_(2,y)=exp[-4ln⁡(2)〖(y-0.0667)〗^2/0.64]`

STALAGMITE FUNCTION PROGRAM:

function f=stalagmite(input_vector)
x=input_vector(1);
y=input_vector(2);

f_1x=(sin(5.1.*pi.*x+0.5))^6;
f_1y=(sin(5.1.*pi.*y+0.5))^6;

f_2x=exp(-4.*log(2).*((x-0.0667)^2)/0.64);
f_2y=exp(-4.*log(2).*((y-0.0667)^2)/0.64);

%for finding maximum value
f=-(f_1x.*f_2x.*f_1y.*f_2y);
end

MAIN PROGRAM:

clear all 
close all
clc

% Defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);

% Search space for ga or number of Iterations
num_cases=50

% Creating 2-Dimensional Array
[xx yy]=meshgrid(x,y);
% Evaluating the stalgamite 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


% study-1-statistical behaviour
%tic, toc is used to calculate the study time

tic        %start of timer
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study1_time=toc       % End of timer

figure(1)
subplot(2,1,1)
hold on
% surface generation
surfc(x,y,-f)
xlabel('X-value')
ylabel('Y-value')
% To remove the grindlines from the surface
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 Maximum')


% study-2-statistical behaviour with upper and lower bounds
%tic, toc is used to calculate the study time
tic          % Start of timer
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study2_time=toc       % End of timer


figure(2)
subplot(2,1,1)
hold on
% surface generation
surfc(x,y,-f)
xlabel('X-value')
ylabel('Y-value')
% To remove the grindlines from the surface
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 Maximum')


% study-3-statistical behaviour by inceasing the number of Iterations

options=optimoptions('ga');
options=optimoptions(options,'populationSize',300);

%tic, toc is used to calculate the study time
tic            %start of timer
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i)=inputs(1);
    yopt(i)=inputs(2);
end
study3_time=toc      %end of timer      
 

figure(3)
subplot(2,1,1)
hold on
% Surface generation
surfc(x,y,-f)
xlabel('X-value')
ylabel('Y-value')
% To remove the grindlines from the surface
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 Maximum')

PROGRAM EXPLANATION:

STALAGMITE FUNCTION PROGRAM:

In this program we have created Stalagmite function defining it with appropriate argument vectors.
And also we make this program to find maximum value.

MAIN PROGRAM:

First we initialize the value of x and y by using linspace
Then we take no of iterations value.
Now we have created 2-dimensional array by using meshgrid
After that we evaluate the the value of stalagmite function by calling stalagmite function inside the loops.
Now the program is divided into three studies.
In first study we deals with unbounded inputs and the functions runs for 50 iterations and here we can see the statistical behavior of genetic algorithm by analyzing the plot but this plot is not usable because it is not clear. so we go for next study.
In the second study for better solution we provide bounded upper and lower input this plot is little bit clear.
In third study we increases the population size along with bounded upper and lower input this study takes much time but the solution we get and the plots we obtain are accurate.
In all the three study we have calculated the time for each study by using tic and toc command for starting and ending the timer respectively.

OUTPUT PLOTS:

Study-1.

from this graph it is not clear that where the maximum value lies.

Study-2.

In this we have defined the upper and lower bound so the plot obtained from this study is little bit clear.

Study-3.

Here we increases the population size to 300 along with bounded inputs. and from this study we have the actual maximum point or global maximawhich is lies at asingle point.

OUTPUT SCREEN:

Study-1 time- 3.8597

Study-2 time- 4.7877

Study-3 time- 16.9456

CONCLUSION:

We have seen the statistical behavior of genetic algorithm in each of the three studies and finally get the exact location of Global maxima by increasing population size.

REFERENCES:

Week 4 - Genetic Algorithm

Ship work like this
in your own course.

Talk to a career counsellor

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.