Challenge

Week 4.1 - Genetic Algorithm

AAnup Pandey7 Aug 2022

AIM:- To Write a code using ga Syntax so as to find the Global Maxima of a Stalagmite Function.

Introduction:- Genetic Algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve. It is frequently used to solve optimization problems, in research, and in machine learning.

Theory Required:-

A genetic algorithm is a search heuristic that is inspired by Charles Darwin's theory of natural evolution. This algorithm reflects the process of natural selection where the fittest individuals are selected for reproduction in order to produce offspring of the next generation.

Genetic algorithms are general-purpose search algorithms that use principles inspired by natural population genetics to evolve solutions to problems. The basic idea is that over time, evolution will select the 'fittest species'.

How the Genetic Algorithm Works

Outline of the Algorithm

The following outline summarizes how the genetic algorithm works:

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

Scores each member of the current population by computing its fitness value. These values are called the raw fitness scores.
Scales the raw fitness scores to convert them into a more usable range of values. These scaled values are called expectation values.
Selects members, called parents, based on their expectation.
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.
Produces children from the 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—
Replaces the current population with the children to form the next generation.

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

Objective:

To Understand the concept of genetic algorithm
To Understand the syntax “ga” in MATLAB
To find the Global Maxima of the stalagmite function using GA Syntax.

Syntax for genetic algorithm-

we can give the inputs by any one of the following ways-

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 of input variables-

These are the various input syntaxes that can be given-

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.

Passing Extra Parameters (Optimization Toolbox) explains how to pass extra parameters to the objective function and nonlinear constraint functions, if necessary.

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.

When there are integer constraints, ga does not accept linear or nonlinear equality constraints, only inequality constraints.

x = ga(problem) finds the minimum for problem, where problem is a structure.

Outputs from the functions-

[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

close all

clear all

clc

% Input Variables

x=linspace(0,0.6,150);

y=linspace(0,0.6,150);

num_spaces=50;

% Creating a 2-D Space

[X Y]=meshgrid(x,y)

% Creating Function as 2-D surface

for i=1:length(x)

for j=1:length(y)

input_vector(1)=X(i,j)

input_vector(2)=Y(i,j)

input_vector=[input_vector(1);input_vector(2)]

f(i,j)=stalagmite(input_vector);

end

% Study_1 (Unbounded Region)

tic

for i=1:num_spaces

[opt_inputs,fopt(i)]=ga(@stalagmite,2)

x_opt(i)=opt_inputs(1)

y_opt(i)=opt_inputs(2)

end

study_time1=toc

figure(1)

subplot(2,1,1)

surf(x,y,-f)

shading interp

hold on

plot3(x_opt,y_opt,-fopt,'marker','o')

subplot(2,1,2)

plot(-fopt)

xlabel('Iterations')

ylabel('Maximum_value')

% Study_2 (Bounded Region)

tic

for i=1:num_spaces

[opt_inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6])

x_opt(i)=opt_inputs(1)

y_opt(i)=opt_inputs(2)

end

study_time2=toc

figure(2)

subplot(2,1,1)

surf(x,y,-f)

shading interp

hold on

plot3(x_opt,y_opt,-fopt,'marker','o')

subplot(2,1,2)

plot(-fopt)

xlabel('Iterations')

ylabel('Maximum value')

% Study_3 (Increasing Population Size)

tic

options=optimoptions('ga')

options=optimoptions(options,'PopulationSize',250)

for i=1:num_spaces

[opt_inputs,fopt(i)]=ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],[],options)

x_opt(i)=opt_inputs(1)

y_opt(i)=opt_inputs(2)

end

study_time3=toc

figure(3)

subplot(2,1,1)

surf(x,y,-f)

shading interp

hold on

plot3(x_opt,y_opt,-fopt,'marker','o')

subplot(2,1,2)

plot(-fopt)

xlabel('Iteration')

ylabel('Maximum value')

PROGRAM CODE FOR STALAGMITE FUNCTION

function [S]=stalagmite(input_vector)

x=input_vector(1);

y=input_vector(2);

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

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

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

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

S =-(f1*f2*f3*f4);

end

PROGRAM EXPLAINATION

First we initialise the values of x and y taking 150 values between the interval 0 and 0.6,we consider no of iterations num_spaces=50.
Since we need to plot a 3D surface plot we take the 2d array of x and y using meshgrid command and store them in input_vector array ,So that it can be used as an argument to call the function stalagmitewe create another fuction file for the stalagmite function. here we take the ouput as -f since ga only minimises
a given function.so if -f is considered it automatically gives us the maxima.

FOR STUDY1

We take no of iterations = num_spaces and we use the genetic algorithm function to caluclate the maxima of the function. we store the outputs into results which contain maximas and fopt which contain the value at which the maxima is obtained,Here the ga is initiated with random population.

FOR STUDY2

Specify the lower and upper bounds of x and y in this case,the ga is initiated with random population only and Follow the same procedure.specify the lower and upper bounds of x and y in this case,the ga is initiated with random population only.

FOR STUDY 3

Here in this case to set a initial population we need to use command called optimumoptions and get our value of 'populationsize' to 250.

now we store the results into xopt, yopt.now we need to plot the surface of x,y,-f to get the 3D plot.

We use the plot3 command to make a plot of xopt,yopt and -fopt to plot the optimum maximas.

Also let us plot the fopt functio so that we can visualise the optimum values at each iteration.

To get the time taken to complete cycle we used the tic toc commands to record the time.
Though the time of execution is more in this case we are sucessful to find out the correct maxima for the stalagmite function.

So by increasing the initrial population size of the ga we can increase the accuracy of the algorithm.

CONCLUSION
We do Multiple iteration is to get the Global maxima in desired range. The main motive of doing so is to get the only 1 desired optimum output which is required for given problem.

Week 4.1 - Genetic Algorithm

Outline of the Algorithm

Description of input variables-

Ship work like this
in your own course.

Talk to a career counsellor

Outline of the Algorithm

Description of input variables-

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.