Week 5 - Genetic Algorithm

PROJECT REPORT ON GENETIC ALGORITHM

Aim: To write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function

Genetic Algorithms (GAs) are adaptive heuristic search algorithms that belong to the larger part of evolutionary algorithms. Genetic algorithms are based on the ideas of natural selection and genetics. These are intelligent exploitation of random search provided with historical data to direct the search into the region of better performance in solution space. They are commonly used to generate high-quality solutions for optimization problems and search problems.

Genetic algorithms simulate the process of natural selection which means those species who can adapt to changes in their environment are able to survive and reproduce and go to next generation. In simple words, they simulate “survival of the fittest” among individual of consecutive generation for solving a problem. Each generation consist of a population of individuals and each individual represents a point in search space and possible solution. Each individual is represented as a string of character/integer/float/bits. This string is analogous to the Chromosome.

Foundation of Genetic Algorithms

Genetic algorithms are based on an analogy with genetic structure and behavior of chromosomes of the population. Following is the foundation of GAs based on this analogy –

1. Individual in population compete for resources and mate
2. Those individuals who are successful (fittest) then mate to create more offspring than others
3. Genes from “fittest” parent propagate throughout the generation, that is sometimes parents create offspring which is better than either parent.
4. Thus, each successive generation is more suited for their environment.

Why use Genetic Algorithms

• They are Robust
• Provide optimization over large space state.
• Unlike traditional AI, they do not break on slight change in input or presence of noise

Application of Genetic Algorithms

Genetic algorithms have many applications, some of them are –

• Recurrent Neural Network
• Mutation testing
• Code breaking
• Filtering and signal processing
• Learning fuzzy rule base etc.

Flow chart for GA:

GA 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,Aeq,beq,lb,ub,nonlcon,intcon)

x = ga(fun,nvars,A,b,Aeq,beq,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,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.

x = ga(problem) finds the minimum for problem, a structure described in problem.

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

Main Program:

clear all
close all
clc

x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
num_cases = 50;

[xx, yy] = meshgrid(x,y);

for i=1:length(xx)
    for j=1:length(yy)
        input(1)=xx(i,j);
        input(2)=yy(i,j);
        f(i,j) = stalagmite_fun(input);
    end
end

tic
for i = 1:num_cases
    [input, fopt(i)]= ga(@stalagmite_fun,2);
    xopt(i) = input(1);
    yopt(i)= input(2);
end
fopt = -fopt
f = -f
study1_time = toc
figure(1)
subplot(2,1,1)
hold on
surfc(x,y,f)
shading interp
plot3(xopt, yopt, fopt, 'marker', 'o', 'markersize', 5, 'markerfacecolor', 'r')
title('unbounded inputs')
subplot(2,1,2)
plot(fopt)
xlabel('Iterations')
ylabel('functions maxima')

tic
 for i = 1:num_cases
     [inputs, fopt(i)] = ga(@stalagmite_fun,2,[],[],[],[],[0;0],[1:1]);
     xopt(i) = inputs(1);
     yopt(i) = inputs(2);
 end
 fopt = -fopt
 f = -f
 figure(2)
 subplot(2,1,1)
 hold on
 surfc(x,y,f)
 shading interp
 plot3(xopt, yopt, fopt, 'markersize', 5, 'markerfacecolor','r')
 title('bounded inputs')
 subplot(2,1,2)
 plot(fopt)
 xlabel('Iterations')
 ylabel('functions maxima')
 
 options = optimoptions('ga');
 options = optimoptions(options, 'PopulationSize', 500);
 tic
 for i= 1:num_cases
     [inputs, fopt(i)] = ga(@stalagmite_fun, 2,[],[],[],[],[0;0],[1:1]);
     xopt(i) = inputs(1);
     yopt(i) = inputs(2);
 end
 
 fopt = -fopt
 f = -f
 
 study3_time = toc
    
 figure(3)
 subplot(2,1,1)
 hold on
 surfc(x,y,f)
 shading interp
 plot3(xopt, yopt, fopt, 'marker', 'o', 'markersize',5,'markerfacecolor','r')
 title('Bounded inputs with modified populations size');
 subplot(2,1,2)
 plot(fopt)
 xlabel('Iterations')
 ylabel('functions maxima')

Function:

function f = stalagmite_fun(input)
x = input(1);
y = input(2);
f1x = (sin(((5.1*pi).*x)+0.5)).^6;
f1y = (sin(((5.1*pi).*y)+0.5)).^6;
f2x = exp((((x-0.0667).^2).*(-4*log(2)./0.64)));
f2y = exp((((y-0.0667).^2).*(-4*log(2)./0.64)));
f = -f1x*f1y*f2x*f2y;

Output graphs:

1. study-1

2. study-2

3. study-3

Error ocuured :

error solved by correcting the varible name

References:

https://www.geeksforgeeks.org/genetic-algorithms/

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

https://in.mathworks.com/help/gads/ga.html#mw_f69991d0-5b23-4023-8c8e-e2890f2474d5