Week 4 - Genetic Algorithm

Global maxima for stalagmite function using MATLAB

1]Aim- To find global maxima for stalagmite function optimizing MATLAB programming .

2]Objective

• Programming to find global maxima for stalagmite function
• To explain the concept and syntax of Genetic Algorithm (ga) used for programming.

3]Introduction

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.

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. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents 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 problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear.

Syntax

These syntax are for finding the minima and as we have to find maxima the function is assigned to –Ve sign to get maxima.

Explanation for general ga

1] Case 1[x,fval] = ga(FitnessFunction,numberOfVariables)

finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of function.

2] Case2[x,fval] = ga(FitnessFunction,numberOfVariables,[],[],[],[],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 A=[] ,b=[], Aeq=[] and beq=[] if no linear equalities exist.)

3]Case3

[x,fval] = ga(VFitnessFunction,numberOfVariables,[],[],[],[],lb,ub,[],[],options)

minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

Sub-Plot

1] subplot(m,n,p)

subplot(m,n,p) divides the current figure into an m-by-n grid and creates axes in the position specified by p. MATLAB^® numbers subplot positions by row. The first subplot is the first column of the first row, the second subplot is the second column of the first row, and so on. If axes exist in the specified position, then this command makes the axes the current axes.

4] Program

Sub Program

function [v] = 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));

[v] = -(f1_x * f2_x * f1_y * f2_y);

end

Main Program

%Optimizing global maxima using genetic algorithm
clear all
close all
clc

%Inputs
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%Number of iterations
num_cases = 50;

%Creating data points of stalagmite function
for i = 1:length(x)
    for j = 1:length(y)
        input(1) = x(i);
        input(2) = y(j);
        f(i,j) = stalagmite(input);
        
    end
end


%Case 1 without boundary conditions

%Iterations for ga without boundary conditions
tic
for i = 1:num_cases
    
    [input,fmax(i)] = ga(@stalagmite,2);
    
    xopt(i) = input(1);
    yopt(i) = input(2);
end
speed1 = toc

%Plotting
figure(1)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
colorbar()
hold on 
plot3(xopt,yopt,-fmax,'marker','o','markerfacecolor','r','markersize',2)
title('Genetic Algorithm unbound inputs');
xlabel('x axis');
ylabel('y axis');
subplot(2,1,2)
plot(-fmax)
xlabel('Iteration')
ylabel('fmax')



%Case 2 using boundary conditions

%Iterations for ga with boundary conditions
tic
for i = 1:num_cases
    
    [input,fmax(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
    
    xopt(i) = input(1);
    yopt(i) = input(2);
end
speed2 = toc


%Plotting
figure(2)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
colorbar()
hold on 
plot3(xopt,yopt,-fmax,'marker','o','markerfacecolor','r','markersize',2)
title('Genetic Algorithm for bound inputs');
xlabel('x axis');
ylabel('y axis');
subplot(2,1,2)
plot(-fmax)
xlabel('Iteration')
ylabel('fmax')



%Case 3 with boundary conditions and population size

%Defining population size
options = optimoptions('ga');
options = optimoptions(options ,'Populationsize',250);

%Iterations for ga with boundary conditions and increased population size
tic
for i = 1:num_cases
    
    [input,fmax(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    
    xopt(i) = input(1);
    yopt(i) = input(2);
end
speed3 = toc


%Plotting
figure(3)
subplot(2,1,1)
surfc(x,y,-f)
shading interp
colorbar()
hold on 
plot3(xopt,yopt,-fmax,'marker','o','markerfacecolor','r','markersize',2)
title('Genetic Algorithm for bound inputs and increased population size');
xlabel('x axis');
ylabel('y axis');
subplot(2,1,2)
plot(-fmax)
xlabel('Iteration')
ylabel('fmax')

5] Code Explanation

-First we created a function by name stalagmite which will be used in main program which consists of four formula , together used to create a function and the whole term is assigned –Ve sign as the ga is used to find minima values using –Ve we will get maxima values.

-In main program we defined two input variables x and y having 150 equally spaced values both between 0 and 0.6.

-Then No. of iterations are defined i.e. the ga function will run for 50 times.

-For Loop is created to find the coordinates using i and j variables that keeps on changing upto length of x and y ,this value is assigned to input(1) and input(2) then stalagmite function is called as it will calculate the coordinates.

-In this step we are going to find the global maxima’s for given data in Case1 it is found without any boundary conditions .

-Next is the plotting for case1 in which two plots are made one is the surfc (3D color) plot showing the whole data space its stalagmite curve on calculated x and y coordinates using code subplot(2,1,1) and the global maxima for the plot. ‘shading interp’ is used to clearly show the curve without any meshing.

-In subplot(2,1,2) only the maxima values and the iterations are shown.

-For Case2 we have introduced boundary conditions which helps to focus on specifically the area within boundary conditions .

-Next is the plotting for case2 which is done similarly but within specified boundary conditions. In subplot(2,1,2) only the maxima values and the iterations are shown.

-For Case3 we have also introduced population space to get more appropriate value for global maxima.

-Next is the plotting for case3 which is similar to above to cases.

6] Results

Case1 without boundary conditions

Case1 show the maxima values all around the plot and not specifically within the boundary conditions and also for every program run the points where changing hence to improve this case2 is coded.

Case 2 using boundary conditions

Case2 showcases relatively less or particulate local maxima within boundary conditions but here also the we do not get value for global maxima.

Case 3 with boundary conditions and population size

Case3 gives the global maxima for stalagmite function

7] Conclusion

Case 3 gives the perfect global maxima value than other two cases having than more time than other cases.

8]References

MathWorks dictionary

Wikipedia