Week 4 - Genetic Algorithm

AIM:

          To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

EXPLANATION:

GENETIC ALGORITHM:

• A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution.
• Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
• The genetic algorithm is used to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

HOW THE GENETIC ALGOITHM WORKS:

The following outline summarizes how the genetic algorithm works:

1. The algorithm begins by creating a random initial population.
2. 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:
   1. Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
   2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
   3. Selects members, called parents, based on their expectation.
   4. 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.
   5. 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.
   6. Replaces the current population with the children to form the next generation.
3. The algorithm stops when one of the stopping criteria is met.

STOPPING CONDITIONS FOR THE ALGORITHM:

The genetic algorithm uses the following options to determine when to stop. See the default values for each option by running opts = optimoptions('ga').

• MaxGenerations— The algorithm stops when the number of generations reaches MaxGenerations.
• MaxTime— The algorithm stops after running for an amount of time in seconds equal to MaxTime.
• FitnessLimit— The algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to FitnessLimit.
• MaxStallGenerations— The algorithm stops when the average relative change in the fitness function value over MaxStallGenerations is less than Function tolerance.
• MaxStallTime— The algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to MaxStallTime.
• FunctionTolerance— The algorithm runs until the average relative change in the fitness function value over MaxStallGenerations is less than Function tolerance.
• ConstraintTolerance— The ConstraintTolerance is not used as stopping criterion. It is used to determine the feasibility with respect to nonlinear constraints. Also, max(sqrt(eps),ConstraintTolerance) determines feasibility with respect to linear constraints.

The algorithm stops as soon as any one of these conditions is met.

SYNTAX FOR GENITIC ALGORITHM:

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.

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,nonicon) 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,nonicon,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,[],[],lb,ub,nonicon,intcon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.

x = ga(problem) finds the minimum for problem, a structure described in problem.

[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.

MATLAB CODE:

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);


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

%study1
tic
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(xx,yy,F)
xlabel('x axis')
ylabel('y axis')
shading interp
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbounded plot')
subplot(2,1,2)
plot(Fopt)
xlabel('iterations')
ylabel('function maximum')


%study2
tic
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;

figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,F)
shading interp
xlabel('x axis')
ylabel('y axis')
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded plot')
subplot(2,1,2)
plot(Fopt)
xlabel('iterations')
ylabel('function maximum')
        
%study3
options=optimoptions('ga')
options=optimoptions(options,'populationsize',450)

tic
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;

figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,F)
xlabel('x axis')
ylabel('y axis')
shading interp
plot3(xopt,yopt,Fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded plot with increased population size')
subplot(2,1,2)
plot(Fopt)
xlabel('iterations')
ylabel('function maximum')


max_value=Fopt;

STALAGMITE FUNCTION:

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

f1_x=(sin(5.1*pi*x+0.5))^6;
f1_y=(sin(5.1*pi*y+0.5))^6;
f2_x=exp(-4*log(2)*(((x-0.0667)^2)/(0.64)));
f2_y=exp(-4*log(2)*(((y-0.0667)^2)/(0.64)));

y=-[f1_x*f2_x*f1_y*f2_y];
end

MATLAB CODE EXPLANATION:

• First we create a vector values for x and y using linspace command.
• Then the 2d arrays are created using the meshgrid command.
• We undergo three case studies to understand the different outputs for different inputs.
• Then we finally calculate the time range for each study.

STUDY1:

• We allow the genetic algorithm to generate a population in the entire domain, without giving any input parameters.
• The function used is ‘ga(@stalagmite,2)’
• For 50 iterations the plot is made between iterations and maximum f.

STUDY2:

• In this the genetic algorithm is created with upper and lower bounds.
• The function used is ’ga(@stalagmite,[],[],[],[],[0:0],[1:1])’
• The plot is made and global maxima is founded.

STUDY3:

• The genetic algorithm is for specified domain range with population size of 150.
• The plot and time range s studied.

OUTPUT:

STUDY1:

STUDY2:

STUDY3:

WORKSPACE VALUES:

 

CONCLUSION:

      Thus the MATLAB is used to find ‘global maximum’ for a stalagmite function.

 

REFERENCES:    

Genetic Algorithm - MATLAB & Simulink (mathworks.com)