Challenge

Function Optimization using Genetic Algorithm - Matlab

AAdvait Kshirsagar28 Jul 2020

MATLAB

Introduction:- Genetic Algorithm

Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection.
Optimization refers to finding the values of inputs in such a way that we get the “best” output values
The basic structure of a GA is as follows −
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, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed integer programming, where some components are restricted to be integer-valued.

OBJECTIVE

Write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.

BODY OF THE CONTENT

The genetic algorithm is inspired by the process that drives biological evolution. The process of evolution starts with the selection of test individuals from a population. Then they produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better ness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the test individuals will be found. And this is the main working principle for the algorithm because at each step, the genetic algorithm selects randomly 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. The genetic algorithm can be applied 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.
Following are the main terms used to solve problem using genetic algorithm:-
1. Population size:- The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Often, the initial population is generated randomly, allowing the entire range of possible solutions
2. Selection:- During each successive generation, a portion of the existing population is selected to breed a new generation
3. Genetic operator:- The next step is to generate a second generation population of solutions from those selected through a combination of genetic operators: crossover (also called recombination), and mutation. crossover and mutation are known as the main genetic operators, it is possible to use other operators such as regrouping, colonization-extinction, or migration in genetic algorithms
4. Heuristics:- In addition to the main operators above, other heuristicsmay be employed to make the calculation faster or more robust. The speciation heuristic penalizes crossover between candidate solutions that are too similar; this encourages population diversity and helps prevent premature convergence to a less optimal solution.
5. Termination:- This generational process is repeated until a termination condition has been reached. Common terminating conditions are:
A solution is found that satisfies minimum criteria
Fixed number of generations reached
Combinations of the above
In Our analysis, GA stops because of “solution is found that satisfies minimum criteria”
We use following function to optimize In this program.

Program for Genetic Algorithm: -

For this exercise we are trying to optimize the stalagmite function & find its Global maximum value & co-ordinates for respective.

For this we will study Three Cases:-

1) Statistical behavior

2)Bounded statistical behavior

3)Bounded Statistical behavior with increase Population size

“GA” command in matlab program to finds, Minima of the function, but in this case, we have to find maxima, hence we are using negative sign before function to get maximum value using GA.

Case 1:- Statistical behaviour

close all
clear all
clc

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

%creating 2D array
[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)=stalegmite_fun(input_vector);
    end
end


%number of iteration
n=50;
tic
%Evaluating the stalegmite function
%Case 1:- Statistical behaviour

for i=1:n;
    [input,fval(i)]=ga(@stalegmite_fun,2);
        xopt(i)=input(1);
        yopt(i)=input(2);
end

figure(1)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fval, 'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded stastical behaviour')
subplot(2,1,2)
plot(-fval)
xlabel('Iteration')
ylabel('Function maximum')
Study1_time=toc

Syntax for Function:-

function f =stalegmite(x)
a=5.1*pi;
f10=sin(a*x(:,1)+0.5).^6;
   f11=sin(a*x(:,2)+0.5).^6;
    b=-4*log(2)/0.64;
f20=exp(b*(x(:,1)-0.0667).^2);
f21=exp(b*(x(:,2)-0.0667).^2);
f=-f10.*f11.*f20.*f21;
end

Syntax Explanation:-
In line no. 6 & 7 we are difining input for stalagmite function.
From line no. 12 to 18, we are basically making array to use as input to stalagmite function. We will use this common commands for studying each case.
From line no. 25 to 44, we are studying case 1 i.e. Unbounded statistical behavior.
In this case we are running GA in function name “stalagmite_fun”, here we can see we didn’t give any bound limits for GA, hence every time we execute the program, GA will choose random samples hence we are getting different answers every time.
From line no. 34 to 44, we are plotting the function with solution.
We are using subplot command to for better comparison, 1^st graph shows stalagmite function with maximum value, while second graph shows maximum value GA predicts at each iteration.This syntax is same for each case.

Case 2:- Bounded statistical behavior
As we see in previous case, we are getting different output at each execution because search space for sampling for genetic algorithm is not define, hence each time GA picks random samples & we are getting random answers.

Explanation of GA syntax:-

Basic GA syntax is

[x,fval,exitFlag,output,population,scores]=ga(fun,nvars,Aineq,bineq,Aeq,beq,lb,ub,nonlcon,intcon,options)

Where,

fun:- Function which need to optimize using GA

nvars:- Number of design variables

Aineq:- A matrix for inequality constraints

bineq:- b vector for inequality constraints

Aeq:- Aeq matrix for equality constraints

beq:- beq vector for equality constraints

lb:- Lower bound on X

ub:- Upper bound on X

nonlcon:- Nonlinear constraint function

intcon:- Index vector for integer variables

options:- Options created with optimoptions('ga',...)

In this program, We are keeping brackets empty[] to the function in syntax which we are not using.
In this case we are defining search space for input, x= 0 to 0.6 & y= 0 to 0.6.

%Case 2:- Bounded stastical behaviour
tic
for i=1:50;
    [input,fval(i)]=ga(@stalegmite_fun,2,[],[],[],[],[0;0],[0.6;0.6]);
        xopt(i)=input(1);
        yopt(i)=input(2);
end

figure(2)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fval, 'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded stastical behaviour')
subplot(2,1,2)
plot(-fval)
xlabel('Iteration')
ylabel('Function maximum')
Study2_time=toc

By this way, setting lb(lower bound) & ub(upper bound) values we are getting same answer every time.

Case 3:- Bounded statistical behavior with increase Population size
Although we get the same output by defining bounds, but solution have lot more variation at each iteration, which is not useful for optimization.
This is because GA have limited search space to work with, hence by increasing population size, we can converge to global maxima for this stalagmite function.

%Case 3:- Bounded stastical behaviour with increase Population size
options = optimoptions('ga');
options = optimoptions(@ga,'PopulationSize',400);
tic
for i=1:50;
    [input,fval(i)]=ga(@stalegmite_fun,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
        xopt(i)=input(1);
        yopt(i)=input(2);
end

figure(3)
subplot(2,1,1)
hold on
surfc(x,y,-f)
shading interp
plot3(xopt,yopt,-fval, 'marker','o','markersize',5,'markerfacecolor','r')
title('Bounded stastical behaviour with increase Population size')
subplot(2,1,2)
plot(-fval)
xlabel('Iteration')
ylabel('Function maximum')
Study3_time=toc

In this study we increase the population size to 400, to have less variation in solution at each iteration.
In result we can see we have very less variation in solutions at each iteration. The solution vary only 0.00000006 units.
Also to study, we use tic & toc command to display time required for simulation.

Study 1:- 3.6753 seconds

Study 2:- 4.4528 seconds

Study 3:- 19.8092 seconds
Complete coding file is attached for referance.
Conclusion:-
- We can find Optimize the function using GA in matlab.
- To avoid random solution at each execution of program define lower & Upper bounds.
- To minimize variation in solution increase the population size for GA.
- As we increase operation for better accuracy, simulation time also increase as we see in each Cases.
Referance:-

Function Optimization using Genetic Algorithm - Matlab

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.