Week 4.1 - Genetic Algorithm

Aim:

To write a program to do optimisation using the stalagmite function to find the global maxima by using Genetic Algorithm (ga) syntax in Matlab.

Objective:

To find the global maxima by using the stalagmite function.

To explain about the Genetic algorithm and the ga syntax in Matlab.

Then to create a plots for all the studies of ga for function maximum and no. of iterations.

Introduction:-

Optimization:

Optimisation is a pro of gathering or collecting the set of effective values from the performed inputs to get a better results. To human by handling the set of values to get defined targets are really a tough and error will pop out gradually.

So to make the process easier it can done by using the optimization for defined constrains. The optimization techniques helps us to find a way to get better output.

Applications of optimization:

Optimization methods have been applied in various fields to handle various practical problems are,

• Mechanics
• Economics and finance
• Machine learning
• Data clustering and mining
• Engineering design
• Artificial intellegence, etc..

Algorithm:

An algorithm is that having a set of input thar are arranged in a sequential manner or in an array of data stored as per defined series. It is a set of instructions for solving a problem or accomplishing a task.

Genetic Algorithm:

A Genetic Algorithm was simulated by charles darwin's theory of natural evolution. The genetic algorithm is a method are designed for solving both constrained and unconstrained optimization problems that is based on natural selection, the process that drives biological evolution. The genetic algorithm repeatedly modifies a population of individual solutions. At each step, the genetic algorithm selects individuals from the current population to be parents and uses them to produce the offspring for the next generation. Over successive growth of generations, the populations are get evolved towards an solution for optimization.

Each individual canditates will get filtered randomly by th fitness evaluation process, this gives a better result for the selection of better candidates will get a chance to yield the more fittest creation from the reproduction the better population will create for the new genration. This is the line proposed by his theory represented that "survival of the fittest".

The flowchart below will explain about the working of genetic algorithm,

The ga uses three main processes of rules at each module to produce the next generation from the upcoming population. They are,

Selection process:

It select the random membors called parents that will contribute to the population of the next offspring. The selection of members generally represented on the individual fitness scores.

Cross over:

The process of cross over for producing children for the next generation depends on combining two parents to form new population.

Mutation:

Mutation process applies the random changes to individual parents to form children for the next generation people.

Next generation:-

Types of childrens produced by the current generation people for the future generations are,

Elite child: Members having best fitness scores

Crossover child: Produced by combining two parents

Mutation child: Formed by making random changes to the single parent.

Applications of Genetic Algorithm:-

Some of the applications of GAs are,

Vehicle problem routing:

From the Electronic Control Module and BUS are the bootable areas of vehicles which can gather data to rectify and and analyze the issue using genetic algorithm.

Financial markets:

Using ga can help to find an optimal set or combination of parameters that can affect the market rules and trades.

Manufacturing system:

One of the major applications of genetic optimization is to minimize a cost function using the optimized set of parameters in product manufacturing.

Engineering design:

The fitness function in genetic optimization are needful by considering some specific requirement of the design.

Neural networks:

Machine learning are also the best areas to genetic algorithms for optimization.

Medical science:

Genetic optimization in predictive analysis like RNA structure identification and protein identification, etc.

Stopping criteria of GAs:-

MaxStall Generations:

The genetic algorithm will stops if the fitness function value of the average relative over MaxStallGenerations is less than tolerance function value.

MaxStallTime:

The ga will stops if there is no development in the objective function during an interval of time in seconds equal to MaxStallTime.

Function Tolerance:

The ga will runs until the average relative change in the function value over MaxStallGenerations is less than Function tolerance.

Syntax for ga:

x = ga(fun,nvars,A,b,Aeq,Beq,ib,ub,nonlcon,options)

where,

x = local maxima point

fun = Objective function

nvars = Number of variables (specified by positive integer)

A,b = Linear inequality constraints (A = Realmatrix; b = Real vector)

Aeq,beq =Linear equality constraints (A = Realmatrix; b = Real vector)

Lb = Lower bounds

ub = Upper bounds

nonlcon = Nonlinear constraints

options = Optimization options is used to perform operations like increasing population size by using optimoptions

Code explaination:

• The stalagmite function is developed in the function file. Then it will later called by the ga syntax.
• Let define the x and y arrays to form a one dimensional array.
• Then by using the nested for loop command to create a two dimensional vector array and to be stored in i & j variables.
• Now provide the number of iterations for the program should run.
• Then now call the stalagmite function by using the ga syntax command which is a in-built function of Matlab.
• Then provide the third variable byand give the inputs of X and y to make three dimensional array.
• After that figure out the plot by using the surf command. In this the boundaries for ga are undefined.
• Now repeat the same process by providing the boundaries to the ga command .
• Then by increasing the population size to ga command to find the global maxima.

Equations:

f1x = `(sin(5.1 pix + 0.5))^6`

f1y = `(sin(5.1 piy + 0.5))^6`

f2x = `exp[-4log(2)*frac{(x-0.667)^2}{0.64}]`

f2y = `exp[-4log(2)*frac{(y-0.667)^2}{0.64}]`

f(x,y) = -(f1x*f1y*f2x*f2y)

The above equation is used in the stalagmite function

function f = stalagmite (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(-4*log(2)*(((x-0.0667)^2)/0.64));
f2y = exp(-4*log(2)*(((y-0.0667)^2)/0.64));

f = -(f1x*f1y*f2x*f2y);
end

The ga function always provides the function minima value so by using the negative (-) sign to inverse the value to obtain the function maxima values.

Study 1: Statistical behaviour of ga

Iteration 1:

Creating surf plot by using stalagmite function to find statistical behaviour of ga without providing the boundaries. So ga doesnot run within the searchspace till the boundaries are not specified

clear all 
close all
clc

x = linspace(0,0.8,100);
y = linspace(0,0.8,100);

for i = 1:length(x)
    for j = 1:length(y)
        input(1)=x(i);
        input(2)=y(j);
        f(i,j)= stalagmite(input);
    end
end

num_case=50;  %GA runs for 50 iterations
% Study 1 Statistical behaviour of ga
for k = 1:num_case
        [input,fopt(k)] = ga(@stalagmite,2);
        xopt(k)= input(1);
        yopt(k)= input(2);
    end

    figure(1);
    subplot(2,1,1)
    hold on
    surf(x,y,-f);
    shading interp   %grid off on the plot to obtain smooth surface
    title('unbounded inputs')
    plot3(xopt,yopt,-fopt,'marker','o','markersize',6,'color','r');
    
    subplot(2,1,2);
    plot(fopt);
    xlabel('No. of iterations');
    ylabel('function max');

Output:

In the output figure it is clearly viewed that the GA algorithm has mapped the function local maxima beyond the axes.

Iteration 2:

The stalagmite function of finding ga is run with the specified lower bounds and upper bounds

clear all 
close all
clc

x = linspace(0,0.8,100);
y = linspace(0,0.8,100);

for i = 1:length(x)
    for j = 1:length(y)
        input(1)=x(i);
        input(2)=y(j);
        f(i,j)= stalagmite(input);
    end
end

num_case=50;  

    % Study 2 Statistical behaviour of ga with upper & lower bounds
    for k = 1:num_case
        [input,fopt(k)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.4;0.4]);
        xopt(k)= input(1);
        yopt(k)= input(2);
    end

    figure(2);
    subplot(2,1,1);
    hold on
    surf(x,y,-f);
    shading interp   %grid off on the plot to obtain smooth surface
    title('Bounded inputs')
    plot3(xopt,yopt,-fopt,'marker','o','markersize',6,'color','r');
    
    subplot(2,1,2);
    plot(fopt)
    xlabel('No. of iterations')
    ylabel('function max')

Output:

Iteration 3:

IN this by increasing the population size so as to converge the global maxima

clear all 
close all
clc

x = linspace(0,0.8,100);
y = linspace(0,0.8,100);

for i = 1:length(x)
    for j = 1:length(y)
        input(1)=x(i);
        input(2)=y(j);
        f(i,j)= stalagmite(input);
    end
end

num_case=50;

    % Study 3 increasing population size to find global maxima
    options = optimoptions('ga');
    options = optimoptions(options,'PopulationSize',270);

    for k =1:num_case
    [input,fopt(k)] =ga(@stalagmite,2,[],[],[],[],[0;0],[0.6;0.6],[],options);
    xopt(k) = input(1);
    yopt(k)= input(2);
    end

    figure(3);
    
    subplot(2,1,1)
    surf(x,y,-f);
    shading interp
    hold on                                                         
    plot3(xopt,yopt,-fopt,'marker','o','markersize',6,'color','r');
    title('Bounded inputs with increased population size')

    subplot(2,1,2);
    plot(fopt)
    xlabel('No. of iterations')
    ylabel('function max')

Output:

From the above picture we obtained the global maxima at an accurate range by increasing the size of the population.

Conclusion:

By using the stalagmite function the global maxima has found and the genetic algorithm and ga syntax are clearly reviewed.

Then all the three studies of the ga for the function maximum and iteration are plotted.

To find the global maxima by using the stalagmite function.

To explain about the Genetic algorithm and the ga syntax in Matlab.

Then to create a plots for all the studies of ga for function maximum and no. of iterations.

Error while programming:

The error is found that the surf plot is not displayed on the figure baceuse of providing subplot command after the surf plot throws an error

To overcome this error by removing the subplot after surf command and provide it before the surf command, the error eill get resolved.