Challenge

Genetic Algorithm

PPreetham Babu R G28 May 2021

Aim:

Write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function and explain the concept of the genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.
Plot graphs for all 3 studies and for F maximum vs no. of iterations.

Optimization:

It is a decision-making technique that helps to find the best result. Optimization is the process of making something better. In any process, we have a set of inputs and a set of outputs.

Genetic Algorithm:

Genetic Algorithms are search-based algorithms based on the concepts of natural selection and genetics. It was developed by John Holland(1989) and his students and colleagues at the University of Michigan. Genetic Algorithms have the ability to deliver a “good-enough” solution “fast-enough”. This makes genetic algorithms attractive for use in solving optimization problems.

The typical Genetic Algorithm consists of the following steps:

Generating an initial population of chromosomes
Evaluating the suitability of each chromosome (individual) that forms the population.
Selecting the chromosomes for mating based on the above results.
Producing offspring by mating (cross over) the selected chromosomes.
Mutating genes randomly.
Repeating steps 3-5 until a new population is generated.
Ending the algorithm when the best solution obtained has not changed after a preset number of generations.

Polynomial problems solved by present-day computers involve several steps to arrive at a solution. Each problem is bound by a polynomial, a mathematical expression of exponents and expressions.

Advantages of GAs

Does not require any derivative information (which may not be available for many real-world problems).
Is faster and more efficient as compared to the traditional methods.
Has very good parallel capabilities.
Optimizes both continuous and discrete functions and also multi-objective problems.
Provides a list of “good” solutions and not just a single solution.
Always gets an answer to the problem, which gets better over time.
Useful when the search space is very large and there are a large number of parameters involved.

Limitations of GAs

GAs are not suited for all problems, especially problems that are simple and for which derivative information is available.
The fitness value is calculated repeatedly which might be computationally expensive for some problems.
Being stochastic, there are no guarantees on the optimality or the quality of the solution.
If not implemented properly, the GA may not converge to the optimal solution.

Syntax of GA:

x=ga(@fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options)

fun - Objective function

nvars - Number of variables

A - Linear inequalities

b - Linear inequalities

Aeq - Linear equalities

beq - Linear equalities

lb - Lower bound

ub - Upper bound

nonlcon - Nonlinear inequalities

options - optimoptions is used to increase the population size.

If the data are not available go with [].

Program:

clear all
close all
clc

% Creating Search space using linspace command
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
num_case=50; % No. of iterations

% Forming an array using mesh grid command
[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); % stalagmite function
end
end


%study 1 - Statistical behaviour - Defining function and variable only.
tic
for i=1:num_case
[inputs, fval_1(i)]=ga(@stalagmite,2);
xopt_1(i)=inputs(1);
yopt_1(i)= inputs(2);

end

Study_1_time=toc;
figure(1)
subplot(2,1,1) % Subplot is a commmand which is used to create any plots in a same figure.
hold on 
surfc(xx,yy,f)
shading interp
plot3(xopt_1,yopt_1,fval_1,'marker','o','markersize',5,'markerfacecolor','c') % plot3 is a 3D plot
title('Unbounded inputs')
subplot(2,1,2)
plot(fval_1)
xlabel('iteration')
ylabel('Function minimum')


%Study 2 -  With bounded entites
tic
for j=1:num_case
[inputs, fval_2(j)]=ga(@stalagmite,2,[],[],[],[],[0,0],[0.9,0.9]);
xopt_2(j)= inputs(1);
yopt_2(j)= inputs(2);

end

Study_2_time=toc;
figure(2)
subplot(2,1,1)
hold on 
surfc(xx,yy,f)
shading interp
plot3(xopt_2,yopt_2,fval_2,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
subplot(2,1,2)
plot(fval_2)
xlabel('iteration')
ylabel('Function minimum')


% Study -3 Increasing population size

options=optimoptions('ga');
options=optimoptions(options,'PopulationSize',150)

tic
for k=1:num_case
[inputs, fval_3(k)]=ga(@stalagmite,2,[],[],[],[],[0,0],[0.9,0.9],[],[],options);
xopt_3(k)= inputs(1);
yopt_3(k)= inputs(2);

end

Study_3_time=toc;
figure(3)
subplot(2,1,1)
hold on 
surfc(xx,yy,f)
shading interp
plot3(xopt_3,yopt_3,fval_3,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs with increase in population size')
subplot(2,1,2)
plot(fval_3)
xlabel('iteration')
ylabel('Function minimum')

Figure 1:

In this figure-1, We can evidently see unstable peaks, the topmost peak is called global maxima, others are called local maxima. Here we executed ga with defining the objective function and its variable only which makes unsuitable to proceed with it.

Figure 2

In considering the limitation of the Previous figure, we are executing ga with the objective function, variables, and bounded entities. Here Upper and lower bounds are specified which reduces the search space. It is more optimized than figure 1.

Figure 3

In this figure, we can see a stable result when compared to previous images, here in this study ga is executed clearly with upper and lower bounds, objective function, variables, and Population size.

Study time is calculated using tic and toc commands for each case:

Conclusion:

By using Matlab, we have understood the function ga and how its works in different cases with the help of the stalagmite function.

Reference:

Genetic Algorithm

Advantages of GAs

Limitations of GAs

Ship work like this
in your own course.

Talk to a career counsellor

Advantages of GAs

Limitations of GAs

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.