Week 4 - Genetic Algorithm

AIM:

1. To Write a code in MATLAB code to optimise the stalagmite function and find the global maxima of the function.
2. Clearly explain the concept of genetic algorithm also explain the syntax for ga in MATLAB in report.
3. To Make sure that code gives the same output, even if it is made to run several times.
4. Plot graphs for all 3 studies and for F maximum vs no. of iterations.

OBJECTIVE:

1. To Write a code in MATLAB code to optimise the stalagmite function and find the global maxima of the function.
2. Clearly explain the concept of genetic algorithm also explain the syntax for ga in MATLAB in report.
3. To Make sure that code gives the same output,so we use no bound points & bounding points & by increasing the population size in order to achieve this.
4. Plot graphs for all 3 studies and for F maximum vs no. of iterations.

Theory:

The flow chart for genetic algorithm is given as follows:

1. Genetic Algorithms(GAs)are commonly used to generate high-quality solutions for optimization problems and search problems.
2. Genetic algorithms simulate the process of natural selection which means those species who can adapt to changes in their environment are able to survive and reproduce and go to next generation. In simple words, they simulate “survival of the fittest” among individual of consecutive generation for solving a problem. Each generation consist of a population of individuals and each individual represents a point in search space and possible solution. Each individual is represented as a string of character/integer/float/bits. This string is analogous to the Chromosome.
3. A Fitness Score is given to each individual which shows the ability of an individual to “compete”. The individual having optimal fitness score (or near optimal) are sought.
4. The GAs maintains the population of n individuals (chromosome/solutions) along with their fitness scores.The individuals having better fitness scores are given more chance to reproduce than others. The individuals with better fitness scores are selected who mate and produce better offspring by combining chromosomes of parents. The population size is static so the room has to be created for new arrivals. So, some individuals die and get replaced by new arrivals eventually creating new generation when all the mating opportunity of the old population is exhausted. It is hoped that over successive generations better solutions will arrive while least fit die.
5. Each new generation has on average more “better genes” than the individual (solution) of previous generations. Thus each new generations have better “partial solutions” than previous generations. Once the offsprings produced having no significant difference than offspring produced by previous populations, the population is converged. The algorithm is said to be converged to a set of solutions for the problem.

Foundation of Genetic Algorithms

Genetic algorithms are based on an analogy with genetic structure and behavior of chromosome of the population. Following is the foundation of GAs based on this analogy –

1. Individual in population compete for resources and mate
2. Those individuals who are successful (fittest) then mate to create more offspring than others
3. Genes from “fittest” parent propagate throughout the generation, that is sometimes parents create offspring which is better than either parent.
4. Thus each successive generation is more suited for their environment.

Operators of Genetic Algorithms

Once the initial generation is created, the algorithm evolve the generation using following operators –
1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow them to pass there genes to the successive generations.

2) Crossover Operator: This represents mating between individuals. Two individuals are selected using selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring).

3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the diversity in population to avoid the premature convergence.

STALGMITE FUNCTION :

PROCEDURE(to code):

1. Intially we need to write a code to solve stalgmite function using the formulae mentioned above and the code is shown below:

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

2.After successfully completing the stalgmite function we need to write a code for generating the

GA for the set of the data for stalgmite function with x and y in between (0,0.6).

3.Generally the genetic algorithm is solved in 3 ways namely:

• Study-1: With no bounds for the values x &y.
• Study-2: With lower and upper bounds for the values x &y.
• Study-3: By increasing the population size .

4. Syntax used:

Ga is a inbuilt matlab code usually used to find the minimum of the function using the Ga flowchart concept which is made inbuilt in it.

1. for Study-1: x = ga(fun,nvars) finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun.
2. for Study-2: x = ga(fun,nvars,A,b,Aeq,beq,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 Aeq=[] and beq=[] if no linear equalities exist.).
3. for Study-3: x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,options) minimizes with the default optimization parameters replaced by values in options. (Set nonlcon=[] if no nonlinear constraints exist.) Create options using optimoptions.

• fun- function for which we need to find the mimima.
• nvar-No. of independent variables.
• lb1 <= x <= lb2 and rb1 <= y <= rb2.(lb1,rb1,(lb2,rb2)
• optimoptions is used in order to increase the default population size 50 to 200.

For finding Maxima:

In order to find Maxima for the ga we have used a negative sign in the end of stalgmite function in order to revert the peaks and to find Minima for the plot, but while plotting we again use negative sign in order to show the original plot.

The matlab code for this is shown below:

clear all;
close all;
clc;

%% defining the input variables x & y
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%% Generating a 2d mesh
[xx yy] = meshgrid(x,y);

%% Evaluating the Stalgmite 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) = stalgmite_function(input_vector);
    end
end

%% study-1 with out bounds
tic
num_cases = 50;
for k = 1:num_cases
    [result,f_val(k)] = ga(@stalgmite_function,2);
    x_opt(k) = result(1);
    y_opt(k) = result(2);
end
figure(1)
subplot(2,1,1)
hold on ;
surfc(xx,yy,-f);
shading interp;
plot3(x_opt,y_opt,-f_val,'marker','o','markersize',5,'markerfacecolor','r');
title('unbounded inputs');
subplot(2,1,2)
plot(-f_val)
xlabel('iterations');
ylabel('function-Maximum');
study_1_time = toc;

%% Study-2 with bounds
tic
num_cases = 50;
for k = 1:num_cases
    [result_1,f_val_1(k)] = ga(@stalgmite_function,2,[],[],[],[],[0;0],[1;1]);
    x_opt_1(k) = result_1(1);
    y_opt_1(k) = result_1(2);
end
figure(2)
subplot(2,1,1)
hold on ;
surfc(xx,yy,-f);
shading interp;
plot3(x_opt_1,y_opt_1,-f_val_1,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x-axis');
ylabel('y-axis');
%%axis([0 2 0 2])
title('bounded inputs');
subplot(2,1,2)
plot(-f_val_1)
xlabel('iterations');
ylabel('function-Maximum');
study_2_time = toc;


%% Study-3 with increasing population size
tic
num_cases = 50;
options = optimoptions('ga','populationSize',300);
for k = 1:num_cases
    [result_2,f_val_2(k)] = ga(@stalgmite_function,2,[],[],[],[],[0;0],[1;1],[],[],options);
    x_opt_2(k) = result_2(1);
    y_opt_2(k) = result_2(2);
end
figure(3)
subplot(2,1,1)
hold on ;
surfc(xx,yy,-f);
shading interp;
plot3(x_opt_2,y_opt_2,-f_val_2,'marker','o','markersize',5,'markerfacecolor','r');
xlabel('x-axis');
ylabel('y-axis');
%%axis([0 2 0 2])
title('bounded inputs with increased population size');
subplot(2,1,2)
plot(-f_val_2)
axis([1 50 0 1]);
xlabel('iterations');
ylabel('function-Maximum');
study_3_time = toc;

%% printing the end results for unbounded values
fprintf('optimised values & time taken for unbounded values are:n');
fprintf('x value :n');
fprintf('%fn',result(1));
fprintf('y value :n');
fprintf('%fn',result(2));
fprintf('time taken :n');
fprintf('%fn',study_1_time);

%% printing the end results bounded values
fprintf('optimised values & time taken for bounded values are:n');
fprintf('x value :n');
fprintf('%fn',result_1(1));
fprintf('y value :n');
fprintf('%fn',result_1(2));
fprintf('time taken :n');
fprintf('%fn',study_2_time);

%% printing the end results with increases population size
fprintf('optimised values & time taken for unbounded values are:n');
fprintf('x value :n');
fprintf('%fn',result_2(1));
fprintf('y value :n');
fprintf('%fn',result_2(2));
fprintf('time taken :n');
fprintf('%fn',study_3_time);
fprintf('population for this is increases to 300n');

Plot for Study-1 with no bounds:

Study-2 with lower and upper bounds:

Study-3 by increasing population:

Error encountered:

During this i have encountered many problems and i have attached some of the screen shots below:

1.During using the stalgmite function i used sind instead of using sin in the coding which ended up my result as shown below:

Rectified this by using Sin instead of sind in the stalgmite function:

CONCLUSION:
1. We have succesfully solved Maxima for the stalgmite function with the coordinates in between(0,0.6) for x & y.
2. We have succesfully plotted the end results of the 3 study cases where we obtained the maxima of the function.

References:

https://www.geeksforgeeks.org/genetic-algorithms/

https://in.mathworks.com/help/gads/ga.html?s_tid=srchtitle#d120e39323