Week 4 - Genetic Algorithm

AIM: Write code in MATLAB to optimize the stalagmite function and find the global maxima of the function.

OBJECTIVES:

• Write code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
• Clearly explain the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB in your report.
• Make sure that your code gives the same output, even if it is made to run several times.
• Plot graphs for all 3 studies and for F maximum vs no. of iterations. Title and axes labels are a must, legends could be shown if necessary

TASKS:

• Step-wise explanation of your code.
• Mention the errors while programming. (If any)
• Steps were taken to overcome those errors (if any).
• Screenshots showing errors (if any) thrown in the command window.
• Under references, mention the literature or online material you have used during research.

GIVEN:

THEORY:

• Genetic Algorithm:

A genetic algorithm (GA) is a method for solving both constrained and unconstrained optimization problems based on a natural selection process that mimics biological evolution. The algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm randomly selects individuals from the current population and uses them as parents to produce the children for the next generation. Over successive generations, the population "evolves" toward an optimal solution.

You can apply the genetic algorithm to solve problems that are not well suited for standard optimization algorithms, including problems in which the objective function is discontinuous, nondifferentiable, stochastic, or highly nonlinear. The genetic algorithm can address problems of mixed-integer programming, where some components are restricted to be integer-valued.

The genetic algorithm differs from a classical, derivative-based, optimization algorithm in two main ways, as summarized in the following table.

Classical Algorithm	Genetic Algorithm
Generates a single point at each iteration. The sequence of points approaches an optimal solution.	Generates a population of points at each iteration. The best point in the population approaches an optimal solution.
Selects the next point in the sequence by a deterministic computation.	Selects the next population by computation which uses random number generators.

• How did the Genetic Algorithm work?

Outline of the Algorithm:

The following outline summarizes how the genetic algorithm works:

1. The algorithm begins by creating a random initial population.
2. The algorithm then creates a sequence of new populations. At each step, the algorithm uses the individuals in the current generation to create the next population. To create a new population, the algorithm performs the following steps:

1. Scores each member of the current population by computing its fitness value. These values are called raw fitness scores.
2. Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
3. Selects members, called parents, based on their expectations.
4. Some of the individuals in the current population that have lower fitness are chosen as elite. These elite individuals are passed to the next population.
5. Produces children from their parents. Children are produced either by making random changes to a single parent—mutation—or by combining the vector entries of a pair of parents—crossover.
6. Replaces the current population with the children to form the next generation.

3. The algorithm stops when one of the stopping criteria is met.

Initial Population:

The algorithm begins by creating a random initial population.

Creating the Next Generation:

At each step, the genetic algorithm uses the current population to create the children that make up the next generation. The algorithm selects a group of individuals in the current population, called parents, who contribute their genes—the

entries of their vectors—to their children. The algorithm usually selects individuals that have better fitness values as parents. You can specify the function that the algorithm uses to select the parents in the Selection function field in the Selection options.

The genetic algorithm creates three types of children for the next generation:

1. Elite are the individuals in the current generation with the best fitness values. These individuals automatically survive to the next generation.
2. Crossover is created by combining the vectors of a pair of parents.
3. Mutation children are created by introducing random changes, or mutations, to a single parent.

The following schematic diagram illustrates the three types of children.

Mutation and Crossover explains how to specify the number of children of each type that the algorithm generates and the functions it uses to perform crossover and mutation.

The following sections explain how the algorithm creates crossover and mutation of children.

Crossover Children

The algorithm creates crossover children by combining pairs of parents in the current population. At each coordinate of the child vector, the default crossover function randomly selects an entry, or gene, at the same coordinate from one of the two parents, and assigns it to the child. For problems with linear constraints, the default crossover function creates the child as a random weighted average of the parents.

Mutation Children

The algorithm creates mutation children by randomly changing the genes of individual parents. By default, for unconstrained problems, the algorithm adds a random vector from a Gaussian distribution to the parent. For bounded or linearly constrained problems, the child remains feasible.

Stopping Conditions for the Algorithm:

The genetic algorithm uses the following conditions to determine when to stop:

1. Generations — the algorithm stops when the number of generations reaches the value of Generations.
2. Time limit — the algorithm stops after running for an amount of time in seconds equal to the Time limit.
3. Fitness limit — the algorithm stops when the value of the fitness function for the best point in the current population is less than or equal to the Fitness limit.
4. Stall generations — the algorithm stops when the average relative change in the fitness function value over Stall generations is less than Function tolerance.
5. Stall time limit — the algorithm stops if there is no improvement in the objective function during an interval of time in seconds equal to the stall time limit.
6. Stall test — the stall condition is either average change or geometric weighted. For geometric weighted, the weighting function is 1/2n, where n is the number of generations prior to the current. Both stall conditions apply to the relative change in the fitness function over Stall generations.
7. Function tolerance — the algorithm runs until the average relative change in the fitness function value over Stall generations is less than Function tolerance.
8. Constraint tolerance — Constraint tolerance is not used as a stopping criterion. It is used to determine the feasibility with respect to nonlinear constraints. Also, max(sqrt(eps),ConstraintTolerance) determines feasibility with respect to linear constraints.

The algorithm stops as soon as anyone of these conditions is met. You can specify the values of these criteria in the Stopping criteria pane in the Optimization app. The default values are shown in the pane.

When you run the genetic algorithm, the Run solver and view results panel display the criterion that caused the algorithm to stop.

The options Stall time limit and Time limit prevent the algorithm from running too long. If the algorithm stops due to one of these conditions, you might improve your results by increasing the values of the Stall time limit and Time limit.

Selection:

The selection function chooses parents for the next generation based on their scaled values from the fitness scaling function. The scaled fitness values are called expectation values. An individual can be selected more than once as a parent, in which case it contributes its genes to more than one child. The default selection option, stochastic uniform, lays out a line in which each parent corresponds to a section of the line of length proportional to its scaled value. The algorithm moves along the line in steps of equal size. At each step, the algorithm allocates a parent from the section it lands on.

A more deterministic selection option is Remainder, which performs two steps:

1. In the first step, the function selects parents deterministically according to the integer part of the scaled value for each individual. For example, if an individual's scaled value is 2.3, the function selects that individual twice as a parent.
2. In the second step, the selection function selects additional parents using the fractional parts of the scaled values, as in stochastic uniform selection. The function lays out a line in sections, whose lengths are proportional to the fractional part of the scaled value of the individuals, and moves along the line in equal steps to select the parents.

Note that if the fractional parts of the scaled values all equal 0, as can occur using top scaling, the selection is entirely deterministic.

Reproduction Options:

Reproduction options control how the genetic algorithm creates the next generation. The options are

1. Elite count — the number of individuals with the best fitness values in the current generation that are guaranteed to survive to the next generation. These individuals are called elite children. The default value of Elite count is 5% of the population size, rounded up.

When Elite count is at least 1, the best fitness value can only decrease from one generation to the next. This is what you want to happen since the genetic algorithm minimizes the fitness function. Setting Elite count to a high value causes the fittest individuals to dominate the population, which can make the search less effective.

2. Crossover fraction — the fraction of individuals in the next generation, other than elite children, that are created by crossover. Setting the Crossover Fraction describes how the value of Crossover fraction affects the performance of the genetic algorithm.

Because elite individuals have already been evaluated, ga does not reevaluate the fitness function of elite individuals during reproduction. This behavior assumes that the fitness function of an individual is not random, but is a deterministic function. To change this behavior, use an output function. See EvalElites in The State Structure.

Mutation and Crossover:

The genetic algorithm uses the individuals in the current generation to create the children that make up the next generation. Besides elite children, which correspond to the individuals in the current generation with the best fitness values, the algorithm creates

1. Crossover children by selecting vector entries, or genes, from a pair of individuals in the current generation and combines them to form a child
2. Mutation children by applying random changes to a single individual in the current generation to create a child

Both processes are essential to the genetic algorithm. Crossover enables the algorithm to extract the best genes from different individuals and recombine them into potentially superior children. Mutation adds to the diversity of a population and thereby increases the likelihood that the algorithm will generate individuals with better fitness values.

Syntax ga:

Find a minimum of a function using a genetic algorithm;

Syntax

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(___)

Description:

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

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, where problem is a structure.

• [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.

BODY OF THE CONTENT:

Start the program writing by creating a new script and save the script with function name;

First, write the function stalagmite for given function x and y;

As given;

F = (fx_1*fy_1*fx_2*fy_2)

Stalagmite function code to record the input vector for x and y;

To get the correct stalagmite function to multiply the output by -1 as shown;

Script for optimizing and recording the stalagmite function with ga;

Also, use the –ve sign for the main function as it will affect the stalagmite surface plot in the right way.

Initial Testing Plot for xx and yy square matrix;

Stalagmite function provides us the output of minima’s and maxima’s in the form stalagmite rock-like structure but in the above case, the plot is inverted thus use –ve sign before the function and run it again.

But till now we have just tested the stalagmite function in the process to optimize it using ga, which providing us the result but it is not controlled as we can see in the output comment.

Thus now we will give it the number of iteration/cases to work up to.

Thus we will start the study with different ga syntax and the integration value to get the global maxima

Study 1: statistical Behavior with the cases 50

We will give the function length from 1 till the number of cases;

Then we will use the ga function to use recorded stalagmite function and record

d number of variables 2.

We will also record the study time, with the help of tic and toc command.

In the end, we will do the plotting i.e. surface plot with the help of input values (ga doesn’t consider these inputs as the limit, however with more iteration, it will try to get somewhat near to these limits)

We will also use subplot command to record multiple plots and thus hold is also used.

We will also use the plot3 command to get a clear understanding of output.

We will use the second subplot to record the main function value for 50 integration.

Output:

Study time:

But we have a lot of peaks for this study and thus it is very hard for us to find the global maxima.

Study 2: statistical Behavior Bound Calculation (Upper and Lower)

Study is same as study 1 with one change, that is the ga command syntax; x = ga(fun,2,A,b,Aeq,beq,[],[],[],options). It is now like this to include the lower and upper case bound.

We will give the function length from 1 till the number of cases;

Then we will use the ga function to use recorded stalagmite function and a record number of variables 2.

We will also record the study time, with the help of tic and toc command.

In the end, we will do the plotting i.e. surface plot with the help of input values (ga doesn’t consider these inputs as the limit, however with more iteration, it will try to get somewhat near to these limits)

We will also use subplot command to record multiple plots and thus hold is also used.

We will also use the plot3 command to get a clear understanding of output.

We will use the second subplot to record the main function value for 50 integration.

Output:

Study Time:

As we can see in this study we don’t have a lot of peaks and to conclude the global maxima we can have only three points and all others are within those 3 points.

But still, we cannot conclude for global maxima.

Thus in the next study, we will increase productivity.

Study 3: statistical Behavior after modification of population size increasing the ga iteration

For the last 2 studies we have received the values as per ga function even though we have assigned the limit, but we can make this more optimized by using optimoptions command for ga to create optimization options.

For this option, we can create the plot for the best fitting.

For this study we are keeping the population size of 200 and here is where it is different from the previous study. Now it is will not be random for ga.

The ga command syntax; x = ga(fun,2,A,b,Aeq,beq,[],[],[],options). It is now like this to include the lower and upper case bound.

We will give the function length from 1 till the number of cases;

Then we will use the ga function to use recorded stalagmite function and a record number of variables 2.

We will also record the study time, with the help of tic and toc command.

In the end, we will do the plotting i.e. surface plot with the help of input values (ga doesn’t consider these inputs as a limit, however with more iteration, it will try to get somewhat near to these limits)

We will also use subplot command to record multiple plots and thus hold is also used.

We will also use the plot3 command to get a clear understanding of output.

We will use the second subplot to record the main function value for 50 integration.

Output:

Study Time:

This study is not as bad study 1but it certainly not effective than study 2. And it can be because of population size thus in the next study just change the population size.

Study 4: statistical Behavior after modification of population size increasing the ga iteration

For the last 2 studies we have received the values as per ga function even though we have assigned the limit, but we can make this more optimized by using optimoptions command for ga to create optimization options.

For this option, we can create the plot for the best fitting.

For this study we are keeping the population size of 400 and here is where it is different from the previous study. Now it is will not be random for ga.

The ga command syntax; x = ga(fun,2,A,b,Aeq,beq,[],[],[],options). It is now like this to include the lower and upper case bound.

We will give the function length from 1 till the number of cases;

Then we will use the ga function to use recorded stalagmite function and a record number of variables 2.

We will also record the study time, with the help of tic and toc command.

In

the end, we will do the plotting i.e. surface plot with the help of input values (ga doesn’t consider these inputs as the limit, however with more iteration, it will try to get somewhat near to these limits)

We will also use subplot command to record multiple plots and thus hold is also used.

We will also use the plot3 command to get a clear understanding of output.

We will use the second subplot to record the main function value for 50 integration.

Output:

Study Time:

For this study, we have successfully optimized the global maxima for the given function.

This we have obtained with a population size of 400 and thus ga need an option function help to get the global maxima art local.

Complete Output:

%providing stalagmite function
%input variables
%popullation and mutation/crossover points


function F = fun_stalagmite(input_vector)

%input vectors to record
x = input_vector(1);
y = input_vector(2);

%solution for number of variables listed
fx_1=(sin(5.1*pi*x+0.5)).^6;
fy_1=(sin(5.1*pi*y+0.5)).^6;
fx_2=exp(-4.*log(2)*((x-0.0667)^2/0.64));
fy_2=exp(-4.*log(2)*((y-0.0667)^2/0.64));

F = -1*(fx_1.*fx_2.*fy_1.*fy_2);
end


% using genetic algorithm to find the optimization of the via global minima
% and maxima
% objective to find global maxima

% defining our search space
 x = linspace(0,0.6,150);    
 y = linspace(0,0.6,150);
 
% creating 2-D mesh
[xx,yy] = meshgrid(x,y);

% Evaluate 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)= fun_stalagmite(input_vector);
    end
end

%2d/3d plot
surfc(xx,yy,-F);    %(Square Matrix-1, Square Matrix-2, Function)
shading interp      % to disable to grids on the surface plot
xlabel('x values')
ylabel('y values')
title('Initital Test')
colorbar
[input,Fval]=ga(@fun_stalagmite,2);  % (function, number of variables)

%optimizing the output for control and for that we will to study 1
%study will have 50 interation, i.e. it stop after 50 cases unlike the test

%study 1 - statistical Behaviour
cases = 50;

study_time_1 = tic;  %record start
for i = 1:cases
   [input,Fo(i)]=ga(@fun_stalagmite,2);
   xo(i)=input(1);
   yo(i)=input(2);
end
toc  %record time end

figure(2)
subplot(2,1,1) 
hold on
surfc(x,y,-F)
shading interp
xlabel('x values')
ylabel('y values')
plot3(xo,yo,-Fo,'marker','o','markersize',5,'markerfacecolor','r')
title('statistical Behaviour-unbounded input')
subplot(2,1,2)
plot(-Fo)
xlabel('Iterations')
ylabel('Function minimum')
colorbar

%study 2 - statistical Behaviour Bound Calculation (Upper and Lower)
cases = 50;

study_time_2 =tic;  %record time start
for i = 1:cases
   [input,Fo(i)]=ga(@fun_stalagmite,2,[],[],[],[],[0;0],[0.6;0.6]);
   xo(i)=input(1);
   yo(i)=input(2);
end
toc  %record time end

figure(3)
subplot(2,1,1) 
hold on
surfc(x,y,-F)
shading interp
xlabel('x values')
ylabel('y values')
plot3(xo,yo,-Fo,'marker','o','markersize',5,'markerfacecolor','r')
title('statistical Behaviour-bounded input')
subplot(2,1,2)
plot(-Fo)
xlabel('Iterations')
ylabel('Function minimum')
colorbar

%study 3 - statistical Behaviour after modification of population size
%increasing the ga interation 
cases = 50;
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',200);

study_time_3 = tic;  %record time start
for i = 1:cases
   [input,Fo(i)]=ga(@fun_stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
   xo(i)=input(1);
   yo(i)=input(2);
end
toc  %record time end
figure(4)
subplot(2,1,1) 
hold on
surfc(x,y,-F)
shading interp
xlabel('x values')
ylabel('y values')
plot3(xo,yo,-Fo,'marker','o','markersize',5,'markerfacecolor','r')
title('statistical Behaviour-bounded input')
subplot(2,1,2)
plot(-Fo)
xlabel('Iterations')
ylabel('Function minimum')
colorbar

%study 4 - statistical Behaviour after modification of population size
%increasing the ga interation 
cases = 50;

options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',400);

study_time_4 = tic;  %record time star
for i = 1:cases
   [input,Fo(i)]=ga(@fun_stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
   xo(i)=input(1);
   yo(i)=input(2);
end
toc  %record time end

figure(5)
subplot(2,1,1) 
hold on
surfc(x,y,-F)
shading interp
xlabel('x values')
ylabel('y values')
plot3(xo,yo,-Fo,'marker','o','markersize',5,'markerfacecolor','r')
title('statistical Behaviour-bounded input')
subplot(2,1,2)
plot(-Fo)
xlabel('Iterations')
ylabel('Function minimum')
colorbar

Optimization Toolbox Output for ga and fun_stalagmite:

ERRORS OR ISSUES

Spelling mistake.

And the other error is preallocating for a couple of command like variables as the variables will change the size for the number of iteration.

This means I can pre-define the length of changing variable but that would limit the functionality for stalagmite function thus I did not do that.

REFERENCE

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

https://in.mathworks.com/help/gads/how-the-genetic-algorithm-works.html