AIM: To optimise the stalagmite function and find the global maxima of the function.

EQUATIONS: Stalagmite Function

GENETIC ALGORITHM:

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.

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.

Search space

The population of individuals are maintained within search space. Each individual represents a solution in search space for given problem. Each individual is coded as a finite length vector (analogous to chromosome) of components. These variable components are analogous to Genes. Thus a chromosome (individual) is composed of several genes (variable components).

Fitness Score

A Fitness Score is given to each individual which shows the ability of an individual to “compete”. The individual having optimal fitness score (or near optimal) are sought.

The GAs maintains the population of n individuals (chromosome/solutions) along with their fitness scores.The individuals having better fitness scores are given more chance to reproduce than others. The individuals with better fitness scores are selected who mate and produce better offspring by combining chromosomes of parents. The population size is static so the room has to be created for new arrivals. So, some individuals die and get replaced by new arrivals eventually creating new generation when all the mating opportunity of the old population is exhausted. It is hoped that over successive generations better solutions will arrive while least fit die.

Each new generation has on average more “better genes” than the individual (solution) of previous generations. Thus each new generations have better “partial solutions” than previous generations. Once the offspring produced having no significant difference from offspring produced by previous populations, the population is converged. The algorithm is said to be converged to a set of solutions for the problem.

nce the initial generation is created, the algorithm evolves the generation using following operators –
1) Selection Operator: The idea is to give preference to the individuals with good fitness scores and allow them to pass their genes to successive generations.
2) Crossover Operator: This represents mating between individuals. Two individuals are selected using selection operator and crossover sites are chosen randomly. Then the genes at these crossover sites are exchanged thus creating a completely new individual (offspring). For example –

3) Mutation Operator: The key idea is to insert random genes in offspring to maintain the diversity in the population to avoid premature convergence. For example –

The whole algorithm can be summarized as –

1) Randomly initialize populations p
2) Determine fitness of population
3) Until convergence repeat:
      a) Select parents from population
      b) Crossover and generate new population
      c) Perform mutation on new population
      d) Calculate fitness for new population

GENETIC ALGORITHM in MATLAB:

ga

Stalagmite function:

%Stalagmite Function
function SF = stalagmite(input_vector)
x = input_vector(1);
y = input_vector(2);
% Stalagmite function f(x,y) = f(1,x)*f(2,x)*f(1,y)*f(2,y)
% f(1,x) = a; f(1,y) = b
% f(2,x) = c; f(2,y) = d
a = (sin(5.1*pi*x + 0.5)).^6;
b = (sin(5.1*pi*y + 0.5)).^6;
c = exp((-4*log(2)*(x - 0.0667).^2)/0.64);
d = exp((-4*log(2)*(y - 0.0667).^2)/0.64);
SF = -(a*c*b*d); % Matrix multiplication in the same order = a*c*b*d
% Genetic Algorithm (ga) minimizes the stalagmite function so in order to maximize we take it negative.
end

Program:

% Optimization of Stalagmite function and finding the global maxima
clear all
close all
clc
% Defining our search space
x = linspace(0,0.6,150); % x & y do not define the search space for the GA
y = linspace(0,0.6,150); % GA doesn't know x & y as the search space
num_cases = 50
% Creating a 2D Mesh
[xx yy] = meshgrid(x,y);
for i = 1:length(xx) %Evaluating the Stalagmite Function
    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

% To measure the time of study/evaluation we use the tic & toc commands

tic
% STUDY 1  - STATISTICAL BEHAVIOR
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) % Subplot plots multiple plots inside the same figure.
hold on
surfc(x,y,-f) % Surface plot
shading interp
plot3(xopt,yopt,-fopt,'marker','o','markersize',5,'markerfacecolor','r')
% fopt is the optimum function value that ga predicts over the 50
% studies/cases.
title('Unbounded inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function Maximum')

tic
% STUDY 2 - With Upper & Lower Bounds
% Gives the local minima
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(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')

% Study 3 - Increasing the GA iterations
options = optimoptions('ga');
options = optimoptions(options,'PopulationSize',250); % Changing the initial population size


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(x,y,-f)
shading interp
plot3(xopt,yopt,-fopt,'marker','o','MarkerSize',5,'MarkerFaceColor','r')
title('Bounded Inputs')
subplot(2,1,2)
plot(-fopt)
xlabel('Iterations')
ylabel('Function maximum')

--

OUTPUTS: