Week 4.1 - Genetic Algorithm

Aim:- Write a code in MATLAB to optimise the stalagmite function and find the global maxima of the function. Plot graphs for all 3 studies and for F maximum vs no. of iterations

WHAT IS OPTIMIZATION.

Optimization is a technique to find the best solution of a problem.It helps us to take a right decision. The main objective of the optimization is to minimize the cost of our product and also maximise the efficiency.

By using this technique we can compare no of solution to find a Best Solution. In this it also consider some factors that are Productivity, Strength, Reliability, Efficiency, Utilization.

With start of a Computer A optimization is a part of Computer Aided Design Process.

There are two types of a Optimization Algorithms-

1. Deterministic Algorithim- BY using this we can find the latest solution within the condition of initial condition.
2. Stochastic Method- a stochastic process, or sometimes random process (widely used) is a collection of random variables; this is often used to represent the evolution of some random value, or system, over time. This is the probabilistic counterpart to a deterministic process.

WHAT IS GENERAL ALGORITHM

Genetic algorithm is a method for find the best value of a solution from the no. of solutions. It is based on evolutionary theory. It use to generate high quality solution for optimization problem. The Is also have a Adaptive nature it means we can find values with respect to no of parameter we are giving. And also takes no of types of parameter for we are giving to algorithm.

Adaptive nature means this algorithm adapt with respect time change in environment.

Notion of Natural Selection

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them.

Five phases are considered in a genetic algorithm.

• Initial population
• Fitness function
• Selection
• Crossover
• Mutation

Initial Population

The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve.

An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution).

In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (string of 1s and 0s). We say that we encode the genes in a chromosome.

Population, Chromosomes and Genes

Fitness Function

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

Selection

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.

Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

Crossover

Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

For example, consider the crossover point to be 3 as shown below.

Crossover point

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

Exchanging genes among parents

The new offspring are added to the population.

New offspring

Mutation

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

Mutation: Before and After

Mutation occurs to maintain diversity within the population and prevent premature convergence.

Termination

The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then it is said that the genetic algorithm has provided a set of solutions to our problem.

SYNTEX FOR GA:

• x = ga(fun,nvars)

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)

Minimize a Nonsmooth Function with Linear Constraints

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

example:- Use the genetic algorithm to minimize the ps_example function on the region x(1) + x(2) >= 1 and x(2) <= 5 + x(1).

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

Minimize a Nonsmooth Function with Linear Equality and Inequality Constraints

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

Use the genetic algorithm to minimize the function on the region x(1) + x(2) >= 1 and x(2) == 5 + x(1).

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

Optimize with Linear Constraints and Bounds

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

Use the genetic algorithm to minimize the ps_example function on the region x(1) + x(2) >= 1 and x(2) == 5 + x(1). In addition, set bounds 1 <= x(1) <= 6 and -3 <= x(2) <= 8.

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

Optimize with Nonlinear Constraints Using ga

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

Use the genetic algorithm to minimize the ps_example function on the region 2x21+x22≤3 and (x1+1)2=(x2/2)4.

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

Minimize with Nondefault Options

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.

Use the genetic algorithm to minimize the ps_example function on the region x(1) + x(2) >= 1 and x(2) == 5 + x(1) using a constraint tolerance that is smaller than the default.

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

Minimize a Nonlinear Function with Integer Constraints

x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon) or x = ga(fun,nvars,A,b,Aeq,beq,lb,ub,nonlcon,intcon,options) requires that the variables listed in intcon take integer values.

BODY OF THE CODE:

Stalagmite function equation shown in figure.

1. Stalagmite function code

function stalagmite = sta_function(input_vector);

x=input_vector(1);
y=input_vector(2);

f1_x= [sin((5.1*pi*x) + 0.5)]^6;
f1_y= [sin((5.1*pi*y) + 0.5)]^6;
f2_x= exp((-4*0.6931*(x-0.0667)^2)/0.64);
f2_y= exp((-4*0.6931*(y-0.0667)^2)/0.64);

%GA is always use to find minima SO for finding a maxima we need -ve term
%in equation
stalagmite =(-f1_x)*(f1_y)*(f2_x)*(f2_y);
end

2. Main code for create stalagmite and for finding minima value

clear
close
clc

%Defining our search space
x = linspace(0, 0.6, 150); %x value limit with 150 interval
y = linspace(0, 0.6, 150); %y value limit with 150 interval

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

%evaluating the stalagmite function
for i=1:length(xx) %initializing xx value one by one 
    for j=1:length(yy)      %initializing yy value for every value of xx
        input_vector(1)=xx(i,j);
        input_vector(2)=yy(i,j);
        f(i,j) = sta_function(input_vector); %Finding value of f by using function code
    end
end

figure(1)
surfc(xx,yy,f)       %For create surface & create contour plot of f matrix
shading interp      %For remove meshgrid line
xlabel('X Axis')
ylabel('Y Axis')

%Finding optimum value by using GA
[x,fval]=ga(@sta_function,2)        %finds a local Unconstrained Minimum Value

This is a code for create stalagmite function,

Firstly clarify the value of x&y limit with 150 interval of each. Then create a meshgrid

Here need a nested loop for creating a matrix for every value of x & y. by using nested loop

We will get a valur of y for every value of x.

A function code is created for solving a equation of stalagmite function.

Surfc command is used for create surface and contour plot of given equation.

Tha ga stands for general algorithm.

GA function help to find the global minima. It find coordinate at which the f have minimum value.

So for getting a GLOBAL MAXIMA we just reverse the plot by using -ve X axis.

OUTPUT:-

1. PLOT

2. GA Solution

Plot graphs for all 3 studies

1. FOR UNBOUNDED CONDITION

clear
close
clc

%Defining our search space
x = linspace(0, 0.6, 150); %Print value of x axis with 150 interval
y = linspace(0, 0.6, 150); %Print value of y axis with 150 interval
num_space=50;              % Variable

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

%evaluating the stalagmite function
for i=1:length(xx) %initializing xx value one by one 
    for j=1:length(yy)      %initializing yy value for every value of xx
        input_vector(1)=xx(i,j);
        input_vector(2)=yy(i,j);
        f(i,j) = sta_function(input_vector); %Finding value of f by using function code
    end
end

% CASE-1, UNBOUNDED CONDITION
tic                          %Use for calculate funtion running time
for i=1:num_space;           %Loop for initializing numspace 
    [input,fopt(i)]=ga(@sta_function,2);
    xopt(i)=input(1);
    yopt(i)=input(2);
end
study_time1=toc
figure(1)
subplot(2,1,1)   %To see plot in one figure window
hold on
surfc(xx,yy,f)   %For create surface & create contour plot of f matrix
shading interp      %For remove meshgrid line
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('UNBOUND CONDITION')  %For print title
subplot(2,1,2)  %To see plot in one figure window
plot(fopt)
xlabel('iteration')     %For print label in X axis
ylabel('function minimum')  %For print label in Y axis

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.

This program is written for finding the global minima value of a function by using GA optimization method. Firstly defining a search space by using a linspace command and then create a 2D matrix by using a meshgrid command.

Now We need to find a stalagmite function by solving a given equation. For a equation at eery point need to use a NESTED LOOP.

Now Condition for UNBOUNDED is found by using a program inside loop.

Tic-toc command is used for calculate run time of loop.

OUTPUT:

Study Time:-

2. FOR BOUNDED CONDITION

clear
close
clc

%Defining our search space
x = linspace(0, 0.6, 150); %Print value of x axis with 150 interval
y = linspace(0, 0.6, 150); %Print value of y axis with 150 interval
num_space=50;              % Variable

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

%evaluating the stalagmite function
for i=1:length(xx) %initializing xx value one by one 
    for j=1:length(yy)      %initializing yy value for every value of xx
        input_vector(1)=xx(i,j);
        input_vector(2)=yy(i,j);
        f(i,j) = sta_function(input_vector); %Finding value of f by using function code
    end
end

% CASE-2, BOUNDED CONDITION
tic
for i=1:num_space;
    [input,fopt(i)]=ga(@sta_function,2,[],[],[],[],[0;0],[0.4;0.4]);
    xopt(i)=input(1);
    yopt(i)=input(2);
end
study_time2=toc

figure(2)
subplot(2,1,1);
hold on
surfc(xx,yy,f);  %in program it is x&y
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','G');
title('BOUND CONDITION')
subplot(2,1,2);
plot(fopt);
xlabel('iteration')
ylabel('function minimum')

This program is written for finding the global minima value of a function by using GA optimization method in bounded condition. Firstly defining a search space by using a linspace command and then create a 2D matrix by using a meshgrid command.

Now We need to find a stalagmite function by solving a given equation. For a equation at eery point need to use a NESTED LOOP.

Now Condition for BOUND is found by using a program inside loop.

Tic-toc command is used for calculate run time of loop.

OUTPUT:-

3. INCREASING GA ITERATION

clear
close
clc

%Defining our search space
x = linspace(0, 0.6, 150); %Print value of x axis with 150 interval
y = linspace(0, 0.6, 150); %Print value of y axis with 150 interval
num_space=50;              % Variable

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

%evaluating the stalagmite function
for i=1:length(xx) %initializing xx value one by one 
    for j=1:length(yy)      %initializing yy value for every value of xx
        input_vector(1)=xx(i,j);
        input_vector(2)=yy(i,j);
        f(i,j) = sta_function(input_vector); %Finding value of f by using function code
    end
end

% CASE-3,INCREASEING GA ITERATION
tic
options=optimoptions('ga')
options=optimoptions(options,'populationsize',170)

for i=1:num_space;
    [input,fopt(i)]=ga(@sta_function,2,[],[],[],[],[0,0],[1,1],[],[],options);
    xopt(i)=input(1);
    yopt(i)=input(2);
end
study_time3=toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx,yy,f)   %in program it is x&y
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','b')
title('INCREASEING GA ITERATION')
subplot(2,1,2)
plot(fopt)
xlabel('iteration')
ylabel('function minimum')

This program is written for finding the global minima value of a function by using GA optimization method in bounded condition. Firstly defining a search space by using a linspace command and then create a 2D matrix by using a meshgrid command.

Now We need to find a stalagmite function by solving a given equation. For a equation at eery point need to use a NESTED LOOP.

Now Condition for increasing GA iteration is found by using a program inside loop.

Tic-toc command is used for calculate run time of loop.

OUTPUT:-

ERRORS OCCURE WHILE PROGRAMMING:

Getting a Error of stalagmite function code.

In line8 missed a multiplication.

Error in shading intrep

Error in surface by using wrong variable:-

Error in vector length

Error in plot&Surf commnad

NOTE:

• Calling function file name and function name should be the same.
• The first program and second program should be saved in the same folder

CONCLUSION:

• Various plot which generate is shown as OUTPUT of program after body of code.