Week 4.1 - Genetic Algorithm

AIM :- To optimise the stalagmite function and finding the global maxima of function

OBJECTIVES :-

• explaining the concept of genetic algorithm and also explain the syntax for ga in matlab.
• plot graphs of three studies for F MAXIMUM vs number of iterations.

THEORY:-

A stalagmite function generally refers to the function with which we are generating values over a stalagmite kind of surface for finding out the local and global maxima and minima of that particular given function.

> In matlab to perform optimisation we use 'genetic algorithm' method which is a inbuild function in matlab to find the global maxima of that given salagmite function

formulae

Introduction to Optimization:

Optimization is the process of making something better. In any process we, have a set of inputs and a set of outputs as shown in the following figure.

Optimization refers to finding the values of inouts in such a way that we get the "best" outpit values.The definition of "best" varies from problem to problem,byt in mathematical terms it refers to maximizing one or more objective functions,by varying the input parameters.

The set odf all possible solutions or values which the inputs can take make up the search space.In this search space,lies a point or a set of points which gives the optimal solutions.The aim of optimization is to find that point or set of points in the search space.

THE GENETIC ALGORITHM:

Nature has always been a great surce of inspiration to all the mankind.Genetic algorithm(GA's) are search based algorithm based on the concepts of natural selection and genetics.GA's are a subset of a much larger branch of computatio known as Evolutionary Computation.

GA's were developed by John Hollard and his students and collegues at the University of Michigan,most notably David.EGoldberg and hassince been tired on various optimization problems with a high degree of success.

In GA's,we have a pool or a population of possible solutions to the given problem.These solutions then ungergo recombination and mutation,producing new children,and the process is repeated over various generations.Each individual is assigned a fitness value and the fitter individuals are given a higher chance to mate and yield more "fitter" individuals.This is in line with the Drawinian Theory of "Survival of the Fittest".

In this way we keep "evolving" better individuals or solutions over generations till we reach a stopping criterion.

Genetic Algorithm are sufficiently randomized in nature,but they perform much better than random local search as they exploit historical information as well.

Basic Structure:

Advantages of GA's:

GA's have various advantages which have made them immensely popualar.Thes include-

• Does not require any derivative information .
• Is faster and more efficient as compared to the traditional methods.
• Has very good parelle capabilites.
• Optimizes both continuous and discrete functions and also milti-objective problem.
• Provides a list of "good" solutions and noy just a single solution.
• Always gets an answer to the problem,which gets better over the time.
• Useful when the search space is very large and there are a larege number of parameters involved.

Limitations of GA's:

Like any technique GA's also suffer from a few limitations.These include-

• GA's are not suited for all problems,especially problems which are simple and for which derivative information is avaliable.
• Fitness value is calculated repeatedly which might be computationally expensive for sme 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.

APLICATIONS OF GA's:

Genetic Algorithm are prmarily used in optimization problems of various kinds,but they are frequently use in other application areas as well.In this section,we list some of the areas in which Genetic Algorithm are frequently used.These are-

• Optimization-Gnetic Algorithm are most commonly used in optimization problems wherein we have to maximize or minimize a given objective function value under a given set of constraints.The approach to solve optimization problems has been highlighted throughout the tutorial.
• Economics-GA's are also uses to characterize various economic model like cobweb model,game theory equilibrium resolution,asset pricing,etc.
• Neural Networks-GA's are also used to train neural networks,particularly recurrent neural networks.
• Parallelizations-GA's also have very good parallel capabilites,and prove to be very effective means in solving certain problems,and also provide a good area for research.
• Image Processing-GA's are used for various digital image processing tasks as well like dense pixel matching.
• Travelling Salesmen Problem and its application-GA's have been used to solve the TSP,whih is a well-known combinatorial problem using novel crossover and packing strategies.

The format for writing genetic algorithm in MATLAB is as follows:

Syntax

function [f]=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));
f=-(f1_x.*f1_y.*f2_x.*f2_y);
end

• According to this formua the stalagmite function is created

MAIN CODE :

clear all
close all
clc
num_cases=50

% % study 1 satistical behavior


% defining our search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
% creating a 2d mesh
[xx,yy]=meshgrid(x,y);
% evaluating the stalagmite function
tic
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
%  surfc(xx,yy,f)
% shading interp
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)
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 minimum')

% study 2-satistical behaviour-with upper and lower bounds

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(x,y,f)
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 minimum')

% study 3-increasing GA iterations
options=optimoptions('ga')
options=optimoptions(options,'populationsize',170);

tic
for i=1:num_cases
    [inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options);
    
     xopt(i)=inputs(1);
     yopt(i)=inputs(2);
end
study3_time=toc
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
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 minimum')
axis([1 50 -1 0])

EXLANATION:-

• defining x and y with linspace command
• by ga with stalagmite function is created by plot
• in study 1 syntax used{ ga(@stalagmite,2) }
• in study 2 syntax used{ ga(@stalagmite,2,[],[],[],[],[0;0],[1;1] }
• in study 3 syntax used{ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options) }
• by using tic and toc to get study times
• ploting all three studies and sub plot is function mininum vs no of iterations

out put:

fig1 for study one

fig 2 for study 2

fig3 for study 3

work space

ERRORS

I got error in function code and i rectified by help of my suppot engineer