TO FIND GLOBAL MAXIMA USING GENETIC ALGORITHM
AIM: To determine "GLOBAL MAXIMA" of a "STALAGMITE FUNCTION" using "GENETIC ALGORITHM" in MATLAB
OBJECTIVE:
1. To determine global maxima by optimizing stalgamite function using genetic algorithm.
2. To understand "GENETIC ALGORITHM"
THEORY:
A Genetic algorithm is inspired by Charles Darwin’s theory of natural evolution.The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions.
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, highly nonlinear.
EXPALINING NOTION OF NATURAL SELECTION IN GENETIC ALGORITHM WITH EXAMPLE:
The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, 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 fittest individuals will be found.
This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.
Five phases are considered in a genetic algorithm.
- Initial population
- Fitness function
- Selection
- Crossover
- Mutation
1. Initial population:
The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).
2. Fitness function:
The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on fitness score.
3. Selection:
The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.
4. Crossover:
Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.
For example,we can explian this by using 6-bit binary string , consider the crossover point to be 3 as shown below.
Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.
The new offspring are added to the population.
5. Mutation:
In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.
Genetic algorithm is a random based classical evolutionary algorithm, by random here we mean that in order to find a solution using the "ga"," random changes applied to the current solutions to generate new ones", This is how genetic algorithm works.
SYNTAX WHICH ARE USED IN GENETIC ALGORITHM:
1. [x,fval] = ga(fun,nvars)
where,
x = inputs
fval = function value
ga = genetic algorithm
fun = function name
nvars = number of variables
2. [x,fval] = ga(fun,nvars,A,b,Aeq,beq,lb,ub)
where,
A,b = Linear inequality constraints
Aeq,beq = Linear equality constraints
lb = lower bound
up = upper bound
3. [x,fval] = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,Intcon,options)
where,
nonlcon = non-linear constraints
Intcon = integer constraints
options = optimization option
4. options = optimoptions(solverName)
solver name = ga
5. options = optimoptions(solverName,Name,Value)
where,
Name = populationSize
Value = populationSize value
STALAGMITE FUNCTION:
Stalagmite function is a "MATHEMATICAL MODEL" that actually gelps us generate "LOCAL MINIMA'S" AND "LOCAL MAXIMA'S". In this mathematical model, we use some equations to be solved, they are:
STOPPING CRITERIA:
The number of iterations in an optimization depends on a solver's criteria. These criteria include several tolerances you can set. Generally, a tolerance is a threshold which, if crossed, stops the iterations of a solver.
FUNCTION PROGRAM: THIS STALAGMITE FUNCTION PROGRAM IS CALLED OUT IN THE BELOW MAIN PROGRAM
function [inputs] = stalagmite(input_vector)
x1 = input_vector(1);
y1 = input_vector(2);
f1_x = sin(5.1*pi*x1+0.5)^6;
f1_y = sin(5.1*pi*y1+0.5)^6;
f2_x = exp(-4*log(2)*(x1-0.0667)^2/0.64);
f2_y = exp(-4*log(2)*(y1-0.0667)^2/0.64);
[inputs] = -(f1_x*f1_y*f2_x*f2_y);
end
PROGRAM FOR OPTIMIZING STALGAMITE FUNCTION USING GENETIC ALGORITHM TO FIND GLOBAL MAXIMA:
clear all
close all
clc
% defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50
[xx yy] = meshgrid(x,y);
% evaluating the stalagmite function
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
figure(1)
surfc(xx,yy,-f)
shading interp
tic
% study 1-statistical behaviour
for i = 1:num_cases
[inputs,fopt(i)] = ga(@stalagmite,2);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study_time1 = toc
figure(2)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('unbound inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function min')
tic
% study 2-statistical behaviour
for i = 1:num_cases
[inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study_time2 = toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bound inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function min')
tic
% study 3 increase ga iterations
options = optimoptions('ga');
options = optimoptions(options,'populationsize',200)
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
study_time3 = toc
figure(4)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bound inputs with modified population size')
subplot(2,1,2)
plot(-fopt)
xlabel('iterations')
ylabel('function min')RESULTS AND OUTPUTS:
FIGURE (1) OUTPUT: WITHOUT ANY OPTIMUM PLOTS:
Here in figure(1) shows only local maximas and local minimas.
FIGURE (2) OUTPUT: STUDY-1 STATISTICAL BEHAVIOUR
HERE WE ARE NOT PROVIDING LOWER BOUNDS, UPPER BOUNDS AND POPULATION SIZE
The above figure the shows optimized maximum values after 50 iterations ,for each iterations which are ploted in red dots are are not bounded in specific area, so they are scattered all over the graph.
Study-1 takes = 3.9548 sec to complete its 50 iterations
FIGURE (3) OUTPUT: STUDY-2 STATISTICAL BEHAVIOUR
HERE WE ARE PROVIDING LOWER BOUNDS AND UPPER BOUNDS BUT NOT PROVIDING POPULATION SIZE
The above figure shows optimized maximum values after 50 iterations, for each iterations which are ploted in red are actually within the area which we have specified, and unwanted maximum values which are not in the specified area are not ploted.
Study-2 takes = 5.2382 sec to complete its 50 iterations
FIGURE (4) OUTPUT: STUDY-3 STATISTICAL BEHAVIOUR
HERE WE ARE PROVIDING LOWER BOUNDS, UPPER BOUNDS AND POPULATION SIZE
Since the population size is increased The above figure shows GLOBAL MAXIMA.
Study-3 takes =17.1883 sec to complete its 50 iterations
CONCLUSION:
1.In "MATLAB", we use a function solver called "ga", here "ga" is used to solve and find only "MINIMA'S", here we have to find "MAXIMA'S",so we add "-" negative sign for function values to flip both point and to plot it, so we use negative sign in the function and in plot command.
2. We can provide different ITERATIONS and run the program i.e..VALUE FOR num_cases = (). if we provide less iterations and run the program, "ga" might find or may not be able to find the "GLOBAL MAXIMA". But as the number of iterations increases the PROBABILITY of finding "GLOBAL MAXIMA" also increases. In this above program we have considered "50 ITERATIONS" to be done.
3. When we increase the "POPULATION SIZE", with increase in "ITERATIONS" the probability of finding "GLOBAL MAXIMA" increases.