Genetic Algorithm

1. Aim:

To write a MATLAB program to:

• To optimise stalagmite function and find the global maxima
• Explain the genetic algorithm with the standard syntax.
• Plot graph for all the studies and for F-maximum v/s no.iterations.

2. Equations:

The given stalagmite functions are:

3. Objectives:

• To solve a stalagmite function using genetic algorithm.
• To use 3 different methods to understand the function and obtain the most suitable global maxima.
• Finding the most accurate global maxima using boundary inputs
• Plotting the stalagmite and analysing the iteration graph.

4. Body of the content:

Programming language used: MATLAB

• Genetic algorithm:

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.

The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

A typical genetic algorithm requires:

1. a genetic representation of the solution domain,
2. a fitness function to evaluate the solution domain.

• Syntax of ga (genetic algorithm)

x = ga(fun,nvars)

x = ga(fun,nvars,A,b)

x = ga(fun,nvars,A,b,Aeq,beq)

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

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

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

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon)

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options)

x = ga(problem)

[x,fval] = ga(___)

[x,fval,exitflag,output] = ga(___)

x,fval,exitflag,output,population,scores] = ga(___)

x = ga(fun,nvars,A,b) finds a local minimum x to fun, subject to the linear inequalities A*x ≤ b. ga evaluates the matrix product A*x as if x is transposed (A*x').

x = ga(fun,nvars,A,b,Aeq,beq) finds a local minimum x to fun, subject to the linear equalities Aeq*x = beq and A*x ≤ b. (Set A=[] and b=[] if no linear inequalities exist.) ga evaluates the matrix product Aeq*x as if x is transposed (Aeq*x').

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.)

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon) subjects the minimization to the constraints defined in nonlcon. The function nonlcon accepts x and returns vectors C and Ceq, representing the nonlinear inequalities and equalities respectively. ga minimizes the fun such that C(x) ≤ 0 and Ceq(x) = 0. (Set lb=[] and ub=[] if no bounds exist.)

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.

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or

x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.

x = ga(problem) finds the minimum for problem, a structure described in problem.

[x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.

[x,fval,exitflag,output] = ga(___) also returns exitflag, an integer identifying the reason the algorithm terminated, and output, a structure that contains output from each generation and other information about the performance of the algorithm.

[x,fval,exitflag,output,population,scores] = ga(___) also returns a matrix population, whose rows are the final population, and a vector scores, the scores of the final population.

5. Code explanation:
   1. Program 1: Unbounded inputs
      1. The program is initiated by obtaining the input values for x and y variables
      2. Then that data is used to create a 2D array
      3. Number of iterations to be run is initiated(50)
      4. Now by using the array inputs in a for loop the stalagmite inputs are assigned to a function f(i,j).
      5. The genetic algorithm is used inside a for loop since ga is a iterative function which finds the optimum global maxima by performing the needed iterations.
      6. The ga syntax is used in which the inputs variables are assigned to a variable input and the min value is assigned to a variable fopt1.
      7. Since the ga is coded in matlab as a minimum fun by default in mathlab, negative sign has to used for the output of function f.
      8. The ga syntax is used with no boundary conditions, therefore the number os optimum global maxima is of a larger number and scattered across.
      9. The syntax used for unbounded inputs:[input,fopt1(i)]=ga(@stalagmitefn,2);
      10. The for loop is carried out for 50 iterations and the output is plotted using the plot command.

2.Program 2:Bounded inputs

1. The program is initiated by obtaining the input values for x and y variables
2. Then that data is used to create a 2D array .
3. Number of iterations to be run is initiated(50)
4. Now by using the array inputs in a for loop the stalagmite inputs are assigned to a function f(i,j).
5. The genetic algorithm is used inside a for loop since ga is a iterative function which finds the optimum global maxima by performing the needed iterations.
6. The ga syntax is used in which the inputs variables are assigned to a variable input and the min value is assigned to a variable fopt1.
7. Since the ga is coded in matlab as a minimum fun by default in mathlab, negative sign has to used for the output of function f.
8. The ga syntax is used with boundary conditions ranging from (0,0.6), therefore the number os optimum global maxima is lesser than the unbounded inputs and a better projection and idea is obtained about the global maxima region.
9. The syntax used for boundary inputs:[input,fopt1(i)]=ga(@stalagmitefn,2,[],[],[],[],[0,0],[0.6,0.6])
10. The for loop is carried out for 50 iterations and the output is plotted using the plot command.

3. Program 3: Bounded inputs with increase in population size

1. The program is initiated by obtaining the input values for x and y variables
2. Then that data is used to create a 2D array .
3. Number of iterations to be run is initiated(50)
4. Now by using the array inputs in a for loop the stalagmite inputs are assigned to a function f(i,j).
5. The genetic algorithm is used inside a for loop since ga is a iterative function which finds the optimum global maxima by performing the needed iterations.
6. The ga syntax is used in which the inputs variables are assigned to a variable input and the min value is assigned to a variable fopt1.
7. Since the ga is coded in matlab as a minimum fun by default in mathlab, negative sign has to used for the output of function f.
8. The ga syntax is used with boundary conditions and initiating a optimoptions on the ga outputs obtained so that the needed population size can be increased which is assigned to a variable options, therefore the number of optimum global maxima is very accurate and easy to analyse.
9. The syntax used for boundary inputs:[input,fopt1(i)]=ga(@stalagmitefn,2,[],[],[],[],[0,0],[0.6,0.6],[],[],options);
10. The for loop is carried out for 50 iterations and the output is plotted using the plot command.

6. Results/conclusion

This can be concluded that genetic algorithm can be best used for finding the optimum values for stalagmite functions using different approaches. The bounded inputs help the program to analyse the optimum value with much ease and accuracy. This makes the program much efficient and user friendly.

Since the ga code is set by default to figure the minimum value and out goal is to find the maximum, we have to use ‘-‘ve symbol across all the functions variable.

• Program:

Sub function program:Stalgamite function

function[f]=stalagmitefn(input)
x=input(1);
y=input(2);
f1x=(sin(5.1*pi*x+0.5))^6;
f1y=(sin(5.1*pi*y+0.5))^6;
f2x=exp(-4*log(2)*((x-0.0667)^2)/0.64);
f2y=exp(-4*log(2)*((x-0.0667)^2)/0.64);
f=-(f1x*f1y*f2x*f2y);
end

1. Case 1:stalagmite function with inbound inputs

%A program to solve a global optimisation problem using stalagmite function
%and genetic algorithm command
%for unbounded inputs
 
clear all
close all
clc
 
%defining the search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
 
%creating a 2D array using the intial inputs
[xx,yy]=meshgrid(x,y);
n=50;
 
%evaluating the stalgamite function
for i=1:length(xx)
    for j=1:length(yy)
        input(1)=xx(i,j);
        input(2)=yy(i,j);
        f(i,j)=stalagmitefn(input);
    end
end
%case 1:plotting stalagmite function for unbounded inputs
%Using the genetic algorithm command ga
tic
for i=1:n
[output,fopt1(i)]=ga(@stalagmitefn,2);
xopt1(i)=input(1);
yopt1(i)=input(2);
end
 
study1_time=toc;
 
%plotting
figure(1)
subplot(2,1,1)
hold on
surfc(xx,yy,-f)
shading interp
xlabel('x values')
ylabel('y values')
plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
subplot(2,1,2)
plot(-fopt1);
xlabel('Iterations')
ylabel('Function maximum')
legend('iterations')

Outputs obtained after execution:

2. case 2: Stalgamite function with bounded inputs

%solving stalgamite functions with bounded inputs
clear all
close all
clc
 
%defining the search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
n=50 ;
 
%creating a 2D array using the intial inputs
[xx,yy]=meshgrid(x,y);
 
%evaluating the stalgamite function
for i=1:length(xx)
    for j=1:length(yy)
        input(1)=xx(i,j);
        input(2)=yy(i,j);
        f(i,j)=stalagmitefn(input);
    end
end
%converting fitting function to change graph upwards
F=-f;
tic
for i=1:n
    [input,fopt1(i)]=ga(@stalagmitefn,2,[],[],[],[],[0,0],[0.6,0.6]);
    xopt1(i)=input(1);
    yopt1(i)=input(2);
end
study2_time=toc;
 
figure(2)
subplot(2,1,1)
hold on
surface(x,y,F)
shading interp
grid on
 
plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
zlabel('function values')
title('bounded inputs')
legend('Stalagmite','max values')
subplot(2,1,2)
plot(-fopt1)
xlabel('iterations')
ylabel('function maximum')
title('Statistical Behviour')

Outputs obtained after execution:

3. Program 3: stalgamite function with bounded inputs and increased population size

%solving stalgamite functions with bounded inputs with increased population
%size
clear all
close all
clc

%defining the search space
x=linspace(0,0.6,150);
y=linspace(0,0.6,150);
n=50 ;

%creating a 2D array using the intial inputs
[xx,yy]=meshgrid(x,y);

%evaluating the stalgamite function
for i=1:length(xx)
for j=1:length(yy)
input(1)=xx(i,j);
input(2)=yy(i,j);
f(i,j)=stalagmitefn(input);
end
end
%converting fitting function to change graph upwards
F=-f;
options=optimoptions('ga');
options=optimoptions(options,'populationsize',450);
tic
for i=1:n
[input,fopt1(i)]=ga(@stalagmitefn,2,[],[],[],[],[0,0],[0.6,0.6],[],[],options);
xopt1(i)=input(1);
yopt1(i)=input(2);
end
study3_time=toc;

figure(3)
subplot(2,1,1)
hold on
surface(x,y,F)
shading interp
grid on

plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')
xlabel('X values')
ylabel('Y values')
zlabel('function values')
title('bounded inputs with increased population size')
legend('Stalagmite','global mxima')
subplot(2,1,2)
plot(-fopt1)
xlabel('iterations')
ylabel('function maximum')
title('Statistical Behviour')

Outputs obtained after execution:

Refernces used:

1.https://en.wikipedia.org/wiki/Genetic_algorithm

2.https://skill-lync.com/knowledgebase/genetic-algorithm-explained

3.https://in.mathworks.com/discovery/genetic-algorithm.html?s_tid=srchtitle

4.https://in.mathworks.com/help/gads/genetic-algorithm-options.html?s_tid=srchtitle