Week 5 - Genetic Algorithm

AIM :- Write a code in MATLAB to optimise stalagmite function and find the global maxima of the function

OBJECTIVE:- study about genetic algorithim and syntax also plot the graph

THEORY:- Genetic Algorithm is optimization method based on the mechanics of natural genetics and natural selection. Genetic Algorithm mimics the principle of natural genetics and natural selection to constitute search and optimization procedures.GA is used for scheduling to find the near to optimum solution in short time.

The genetic algorithm works on the evolutionary generational cycle to generate high-quality solutions. These algorithms use different operations that either enhance or replace the population to give an improved fit solution.

It basically involves five phases to solve the complex optimization problems, which are given as below:

• Initialization
• Fitness Assignment
• Selection
• Reproduction
• Termination

1. Initialization

The process of a genetic algorithm starts by generating the set of individuals, which is called population. Here each individual is the solution for the given problem. An individual contains or is characterized by a set of parameters called Genes. Genes are combined into a string and generate chromosomes, which is the solution to the problem. One of the most popular techniques for initialization is the use of random binary strings.

2. Fitness Assignment

Fitness function is used to determine how fit an individual is? It means the ability of an individual to compete with other individuals. In every iteration, individuals are evaluated based on their fitness function. The fitness function provides a fitness score to each individual. This score further determines the probability of being selected for reproduction. The high the fitness score, the more chances of getting selected for reproduction.

3. Selection

The selection phase involves the selection of individuals for the reproduction of offspring. All the selected individuals are then arranged in a pair of two to increase reproduction. Then these individuals transfer their genes to the next generation.

There are three types of Selection methods available, which are:

• Roulette wheel selection
• Tournament selection
• Rank-based selection

4. Reproduction

After the selection process, the creation of a child occurs in the reproduction step. In this step, the genetic algorithm uses two variation operators that are applied to the parent population. The two operators involved in the reproduction phase are given below:

• Crossover: The crossover plays a most significant role in the reproduction phase of the genetic algorithm. In this process, a crossover point is selected at random within the genes. Then the crossover operator swaps genetic information of two parents from the current generation to produce a new individual representing the offspring.
  
  The genes of parents are exchanged among themselves until the crossover point is met. These newly generated offspring are added to the population. This process is also called or crossover. Types of crossover styles available:
  • One point crossover
  • Two-point crossover
  • Livery crossover
  • Inheritable Algorithms crossover
• Mutation
  The mutation operator inserts random genes in the offspring (new child) to maintain the diversity in the population. It can be done by flipping some bits in the chromosomes.
  Mutation helps in solving the issue of premature convergence and enhances diversification. The below image shows the mutation process:
  Types of mutation styles available,
  • Flip bit mutation
  • Gaussian mutation
  • Exchange/Swap mutation
  
  

5. Termination

After the reproduction phase, a stopping criterion is applied as a base for termination. The algorithm terminates after the threshold fitness solution is reached. It will identify the final solution as the best solution in the population.

GENETIC ALGORITHM SYNTAX

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

fun= objective function

nvars= number of variables

A,b = linear inequality constraints

Aeq,beq= linear equality constraints

Lb,ub= lower bounds, upper bounds

nonlcon= non linear constraints

intcon = vector of positive integers that contains the x components

options= optimization options

General Workflow of a Simple Genetic Algorithm

STALAGMITE FUNCTION SCRIPT

MATLAB CODE

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

clear all
close all
clc
x = linspace(0,0.6,150);
y = linspace(0,0.6,150);
[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

% study 1 : unbounded behaviour
num_cases=50;
tic
for i = 1:num_cases
[inputs, fopt(i)] = ga(@stalagmite,2);
xopt(i) = inputs(1);
yopt(i) = inputs(2);
end
study1_time = toc

figure(1)
subplot(2,1,1)
hold on
surfc(xx, yy, -f)
shading interp
plot3(xopt,yopt,fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('Unbounded inputs')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')

% study_2 upper and lower bounds
tic
for i= 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);
    xopt(i)= inputs(1);
    yopt(i)= inputs(2);
end
study2_time= toc
figure(2)
subplot(2,1,1)
hold on
surfc(xx, yy, -f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('bounded inputs')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')

% study_3 by increasing the population size
 options= optimoptions('ga')
 options= optimoptions(options,'PopulationSize',500)
tic
for i= 1:num_cases
    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);
    xopt(i)= inputs(1);
    yopt(i)= inputs(2);
end
study3_time= toc
figure(3)
subplot(2,1,1)
hold on
surfc(xx, yy, -f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
title('increasing the population sze')
xlabel('X values')
ylabel('Y values')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')