OPTIMIZING A FUNCTION USING GENETIC ALGORITHM

INTRODUCTION:

Genetic algorithm is a heuristic method that is inspired by Darwin\'s theory of natural evolution. Genetic algorithm is commonly used to generate optimizations problems & search problems. To make it do this it requires 

1. genetic representation
2. fitness function 

The genetic algorithm solves optimization problems and search problems by relying on bio-inspired operators as

1. mutations
2. crossover
3. selection

Genetic algorithm is a built-in function in Matlab but the algorithm works as follows

1. Initialization: Here it takes population size as the initial value, but MATLAB takes 50 as the default value for population size.
2. Selection: 1. Fitness function is evaluated for each individual.                                                                   2. These fitness values are then normalized by dividing each individual by sum of all                        fitness values so that the sum of all resulting values is 1.                                                     3. The population is sorted by descending fitness values.                                                           4. Accumulated normalized fitness values are the sum of its own fitness value plus                           the fitness values of all the previous individuals.                                                                   5. A Random number R between 0 and 1 is chosen.                                                                   6. The selected individual is the last one whose accumulated normalized value is                             greater than or equal to R.
3. Genetic Operators: Used to create Next-generation population of solutions from those selected through a combination of genetic operator crossover.
4. Reproduction methods: based on the use of two parents who are more biology-inspired, these process ultimately result in the next generation population of chromosomes that is different from initial generation, with this average fitness will have increased.
5. Termination:  1. A solution is found that satisfies minimum criteria.                                                                 2. Fixed number of generations reached.                                                                                   3. Allocated budget (computation time/ money) reached.                                                           4. The highest-ranking solution fitness is reaching or has reached a plateau such                             that successive iterations no longer produce better results.                                                     5. Manual inspection.                                                                                                               6. Combination above.

The syntax for the genetic algorithm in MATLAB is

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.

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,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,option), subjects the minimization to the constraints defined in nonlcon. minimizes with the default optimization parameters replaced by values in options.

[x,fval]=ga(_), for any previous input argument, also return fval, the value of fitness function at x (minimum value).

[x,fval,exitflag,output,population,scores]=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. also outputs population, whose are the final population, and a vector scores, the scores of the final population.

Here Stalagmite function is used as the fitness function and genetic algorithm is used to optimize the stalagmite function.

EXPLANATION OF THE PROGRAM:

Defining the Stalagmite function.

The stalagmite function is first defined to optimize it by using a genetic algorithm.

Stalagmite function takes in two inputs x,y and gives one output f . It is represented as

`f(x,y)=f_(1x)*f_(2x)*f_(1y)*f_(2y)`

`f_(1x)=[sin(5.1*pi*x+0.5)]^6`

`f_(2x)=e^[-4ln(2)*(x-0.667)^2/0.64]`

`f_(1y)=[sin(5.1*pi*y+0.5)]^6`

`f_(2x)=e^[-4ln(2)*(y-0.667)^2/0.64]`

The genetic algorithm tries to find the minimum value of the function but we need to calculate the maximum value by optimizing the function for that I need to finally define the stalagmite function as 

`f(x,y)=-[f_(1x)*f_(2x)*f_(1y)*f_(2y)]`

so that we get the maximum value by finding the minimum value calculated by genetic algorithm.

Use of genetic algorithm to optimize the stalagmite function.

This program is divided into three cases to understand how Genetic algorithm works and how it is used to optimize a function.

• First clear all,close all,clc is used.
• Then search space x,y is defined which are inputs for the program.
• 2D mesh is created using the meshgrid function which creates a 2D array of x,y values.
• The number of iterations each case has to run is defined.
• Using for loop, Stalagmite function is evaluated by each value of the 2D array created by the x,y values and obtaining output f of stalagmite function.
• for each case functions tic and toc are used to calculate the time taken for each case.
• In CASE 1: with only stalagmite function as input fitness function and number of variables as inputs to ga, minimum value(array of x,y values) for each iteration is calculated and also fitness value for each iteration is calculated. Then a surface plot of stalagmite function, a 3D plot of minimum values( i.e., x_out and y_out) vs fitness values(fval) and a plot between number of iterations and fitness values is plotted.
• In CASE 2: In addition to case 1 lower bound and upper bound are given as input to ga, so as to get the value in that range.
• In CASE 3: Now in addition to case 2 the population size of the ga is increased in order to get the right value.

DEFINING STALAGMITE FUNCTION:

function [f] = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
%formula of stalagmite function
f_1x = [sin(5.1pi*x+0.5)].^6;
f_2x = exp(((-4*log(2))*((x-0.0667).^2)/(0.64)));
f_1y = [sin(5.1*pi*y+0.5)].^6;
f_2y = exp(((-4*log(2))*((y-0.0667).^2)/(0.64)));
%for maximizing we need to add \'-\' to the resulting function
f = -(f_1x.*f_2x.*f_1y.*f_2y);
end

PROGRAM TO OPTIMIZE THE STALAGMITE FUNCTION USING GENETIC ALGORITHM

clear all
close all
clc
 
%Defining our search space
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);

%Creating 2D mesh
[xx,yy] = meshgrid(x,y);

%number of iterations
iterations = 50;

%Evaluating 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

%Optimizing stalagmite function using ga
%case 1

tic
for i=1:iterations
    [inputs,fval(i)] = ga(@stalagmite,2);
    x_out(i)=inputs(1);
    y_out(i)=inputs(2);
end
case1_time = toc

%plotting surface of the stalagmite function
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(x_out,y_out,fval,\'marker\',\'o\',\'markersize\',4,\'markerfacecolor\',\'r\')
xlabel(\'x-axis\')
ylabel(\'y-axis\')
title(\'stalagmite function optimized using ga\')
subplot(2,1,2)
plot(fval)
xlabel(\'iterations\')
ylabel(\'fval\')

%Optimizing stalagmite function using ga by giving lower and upper bounds
%case 2

tic
for i=1:iterations
    [inputs,fval(i)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1]);
    x_out(i)=inputs(1);
    y_out(i)=inputs(2);
end
case2_time = toc

%plotting surface of the stalagmite function
figure(2)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(x_out,y_out,fval,\'marker\',\'o\',\'markersize\',4,\'markerfacecolor\',\'r\')
xlabel(\'x-axis\')
ylabel(\'y-axis\')
title(\'stalagmite function optimized using ga with lower bounds and upper bounds\')
subplot(2,1,2)
plot(fval)
xlabel(\'iterations\')
ylabel(\'fval\')

%Optimizing stalagmite function using ga by giving lower and upper bounds
%and also by increasing the population
%case 3

options = gaoptimset(\'populationsize\',300);
tic
for i=1:iterations
    [inputs,fval(i)] = ga(@stalagmite,2,[],[],[],[],[0,0],[1,1],[],[],options);
    x_out(i)=inputs(1);
    y_out(i)=inputs(2);
end
case3_time = toc

%plotting surface of the stalagmite function
figure(3)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(x_out,y_out,fval,\'marker\',\'o\',\'markersize\',4,\'markerfacecolor\',\'r\')
xlabel(\'x-axis\')
ylabel(\'y-axis\')
title(\'stalagmite function optimized using ga by increasing population along with bounds\')
subplot(2,1,2)
plot(fval)
xlabel(\'iterations\')
ylabel(\'fval\')

RESULTS:

For case 1 it is clear that minimum values and fitness values are different(or scattered) for each iteration and some are not even close to the surface of the stalagmite function.

In case 2 as the lower bound and upper bound are given to ga it only takes minimum values in that range which gives..

In case3 population size is increased which gives the value.

END OF PROGRAM......

Resources: - 

https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3

https://towardsdatascience.com/how-to-define-a-fitness-function-in-a-genetic-algorithm-be572b9ea3b4

https://in.mathworks.com/help/gads/ga.html

https://in.mathworks.com/help/gads/vary-mutation-and-crossover.html

https://in.mathworks.com/help/gads/examples/constrained-minimization-using-the-genetic-algorithm.html

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

https://en.wikipedia.org/wiki/Mutation_(genetic_algorithm)

https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)

https://en.wikipedia.org/wiki/Selection_(genetic_algorithm)

https://in.mathworks.com/help/optim/ug/optimoptions.html