Week 4 - Genetic Algorithm

AIM:

To Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.

OBJECTIVES:

• To write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function.
• To Clearly expalin the concept of genetic algorithm in your own words and also explain the syntax for ga in MATLAB

THEORY:

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

Role of Genetic Algorithms in Global Optimization:

Evolutionary algorithms are population-basedoptimization algorithms inspired by the principles of natural evolution. When compared with other optimization algorithms, the advantage of evolutionary algorithms is that they do not make limiting assumptions about the underlying objective functions. The objective functions are treated as black-box functions. Furthermore, the definition of objective functions does not require significant insight into the structure of the design space.

Darwin’s theory of evolution identified the principles of natural selection and survival of the fittest as driving forces behind biological evolution. His theory can be summarized as follows.

Variation
There is variation between individuals in a population.

Competition
Resources are limited. In such an environment, there will be a struggle for survival among individuals.

Offspring
Species have great fertility. They produce more offsprings than can grow to adulthood.

Genetics
Organisms pass genetic traits to their offspring.

Natural selection
Those individuals with the most beneficial traits are more likely to survive and reproduce.

Evolutionary algorithms are based on the principles of biological evolution described in Darwin’s theory. Genetic Algorithms (GAs) are a class of evolutionary algorithms, also known as population-based metaheuristic optimization algorithms. GA was first conceived by J.H. Holland in. GA uses a population of solutions, whose individuals are represented in the form of chromosomes. The individuals in the population go through a process of simulated evolution to obtain the global optimum.

The GA repeatedly modifies a set of solutions or individuals in the course of its entire run. At each iteration, the genetic algorithm selects individuals from the current population to serve as parents based on certain criteria. The parents are then used to create the next generation of individuals, called children. Over successive generations, the population evolves toward an optimal solution or Pareto frontier, depending on the type of problems and the type of GA being used. The procedure for a genetic algorithm is illustrated. The terms used in the procedure are explained below:

Encoding

Encoding is a way to represent individual solutions in evolutionary algorithms. Typically, individual solutions are coded as a finite fixed length string. Binary numbers are usually used as codes. This string is also known in the literature as a chromosome. For example, a binary number, 10001, represents the decimal number 17. The conversion from the binary number to the decimal number is given by 1 × 24 + 0 × 23 + 0 × 22 + 0 × 21 + 1 × 20 = 16 + 1 = 17.

Initial population

The algorithm begins by generating a population of individuals in the design space. Prior to population initialization, the designer must choose the number of individuals in each population and the number of bits in the encoding process. Both of these decisions are extremely important in promoting the success of the GA-based optimization. For example, too large a population can lead to undesirable computational expense, while too small a population can lead to premature convergence to a local optimum or suboptimal point. Further description of these features and issues of GAs can be found in the foundational book on GA by Goldberg.

Evaluation
Computation of the objective values for the individual solutions.

Optimization criteria
The stopping criteria of the algorithm. Examples of stopping criteria include the number of generations, the computation time limit, and the function tolerance.

Fitness assignment
There are several choices of fitness assignment. In a rank-based fitness assignment, the individuals are sorted according to their objective values. It creates an order among the individuals.

Selection
A selection criterion filters out the candidate solutions with poor fitness and retains those with acceptable fitness to enter the reproduction process with a higher probability.

Reproduction
A new generation in the genetic algorithm is created through reproduction from the previous generation. Three mechanisms (elitist, crossover, and mutation) are primarily used to create a new generation.

Elitist
The individuals with the best fitness values in the current generation are guaranteed to survive in the next generation.

Crossover
In this technique, a part of the encoded string of one individual is exchanged with the corresponding string part of another individual. There are many approaches to performing the crossover operation. Suppose there are two individuals, 10101 and 11001. Exchange the first two bits of the two individuals. The offspring of the two individuals are 11101 and 10001.

Mutation
Mutated child solution is generated from a single parent by randomly reversing some bits from 0 to 1, or vice versa. For example, through mutation, the 2nd bit and the 5th bit of 10101 are reversed. The new offspring is 1100.

Syntax for 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, 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.

PROGRAM:

%function

function[F]=stalagmite(input_vector)

x=input_vector(1);

y=input_vector(2);

f1=(sin(5.1*pi*x+0.5))^6;

f2=(sin(5.1*pi*y+0.5))^6;

f3=exp(-4*log(2)*((x-0.0667)^2)/0.64);

f4=exp(-4*log(2)*((y-0.0667)^2)/0.64);

F=(f1*f2*f3*f4);

F=1/(1+F);

end

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

% 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

surfc(xx,yy,f)

shading interp;

[inputs,fwal] = ga(@stalagmite,2)

%code for global optimization

clear all

close all

clc

x = linspace(0,0.6,150);

y = linspace(0,0.6,150);

num_cases = 50;

% generating 2 Dimesnional mesh

[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

% study 1 - Statistical behaviour

tic

for i = 1:num_cases;

[inputs,fopt1(i)]=ga(@stalagmite,2);

xopt1(i)=inputs(1);

yopt1(i)=inputs(2);

end

study1_time=toc

figure(1)

subplot(2,1,1)

hold on

surfc(x, y, -f)

shading interp

plot3(xopt1,yopt1,-fopt1,'marker','o','markersize',5,'markerfacecolor','r')

title('unbounded_inputs');

subplot(2,1,2)

plot(-fopt1);

xlabel('Iterations');

ylabel('Function Minimum');

legend('Iterations','Function Minimum')

% Study 2 - Statistical behaviour - with upper and lower bounds

tic

for i = 1:num_cases;

[inputs,fopt2(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);

xopt2(i)=inputs(1);

yopt2(i)=inputs(2);

end

study2_time=toc

figure(2)

subplot(2,1,1)

hold on

surfc(x, y, -f)

shading interp

plot3(xopt2,yopt2,-fopt2,'marker','o','markersize',5,'markerfacecolor','r')

title('unbounded_inputs');

subplot(2,1,2)

plot(-fopt2);

xlabel('Iterations');

ylabel('Function Minimum');

legend('Iterations','Function Minimum')

% Study 3 - Statistical behaviour - Increasing GA Iterations

options = optimoptions('ga');

options = optimoptions(options, 'populationsize', 170);

tic

for i = 1:num_cases;

[inputs,fopt3(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[1;],[],[],options);

xopt3(i)=inputs(1);

yopt3(i)=inputs(2);

end

study3_time=toc

figure(3)

subplot(2,1,1)

hold on

surfc(x, y, -f)

shading interp

plot3(xopt3,yopt3,-fopt3,'marker','o','markersize',5,'markerfacecolor','r')

title('unbounded_inputs');

subplot(2,1,2)

plot(-fopt3);

xlabel('Iterations');

ylabel('Function Minimum');

legend('Iterations','Function Minimum')

EXPLANATION:

• As we start with clear the command, clear the workspace by typing clear all; close all; clc
• Another we define the search space i.e setting lower bond and upper bond with command linspace.
• For creating 2-dimensional mesh we will write a meshgrid between particular two coordinates and for the code, it will be x,y.
• Another step is to evaluate our stalagmite function which means we have to call the main function which we save in the form of stalagmite.m
• In command window type “stalagmite ([1 2])” to verify or function is working or not and we will get 2 valves and that will be for x and y or we can say input_vector (1) or input_vector (2).
• For me it is
• Now for creating a 2D surface for stalagmite, we have to write “surfc(xx,yy,f)”.
• For proper shading the surface we have to write a code for that and that will be “shading interp”. If we will not provide shading then it will create mesh structure on a stalagmite.
• Now we have to give x and y label to indicate values.
• Colorbar will show the values range.
• Here we will use “tic” with the function and its work with “toc” to measured elapsed time.
• The “tic” function records the current time, and the “toc” function uses the recorded value to calculate the elapsed time.
• In this coding, we are going to plot Functions Vs Iteration graph.
• This coding is known as bound calculation because we will provide limit. GA command with bounded inputs means the optimum value will become from inside of search space.
• In this study we are going to increase Population size up to 150 and iteration will be 50.
• Also, in this code, we are going to add the upper and lower limit with GA syntax. “[inputs,fopt(i)]= ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6])”
• Now Executing the given code for output results

• In this study, we are going to modified the code by using “options” command in coding to optimize the value.
• Options are a method of combining a set of name-value pairs. They are useful because they allow us to:

• Also, we will use “options = gaoptimset” which creates a structure called options that contains the options, or parameters, for the genetic algorithm and sets parameters to [] , indicating default values will be used.
• Also, we will use “options = gaoptimset(options,'populationsize',170)” for adding population size.
• For evaluating gaoptimset we have to change our function command with “[inputs, fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[])”.

ERROR FACED

OUTPUT:

inputs =

0.2592 0.0705

fwal =

0.5452

study1_time =

13.5428

study2_time =

19.0940

study3_time =

52.9413