optimum value search on stalagmite function using genetic algorithm
GENETIC ALGORITHM :
genetic algorithm is a type of more general evolutionary algorithms. these algorithms are nature's adopted ways of life form progression. It's a nature-inspired approach to optimization, 'the process of getting the most out of it'. the main idea behind is 'survival of the fittest', proposed by Darwinian evolution and modern genetics.
the general idea behind the whole thing is that if biological evolution can produce something as amazing as humans over many generations then we should be able to use the same process artificially to evolve optimal solutions for difficulties found in the engineering field such as vehicle designs, A.I systems, spaceship and aircraft designs and much more...
to dispel any overhyping, it's worth noting that in practice evolutionary computation offers approximations to the optimal solution to the problem.
STRUCTURE OF G.A. (HOW DOES IT WORK? ) :
genetic algorithm is an iterative process, it runs iterations on a generation-long scale. each generation represents an iteration. supposedly, if the nest generation is better at satisfying objective than the algorithm works in a right direction. below are given stages of this iterative process which cycles through each generation of species.
- stage 1: initialization
we can think of this stage as a sudden start, where the initial population of members is created out of nowhere.
populations represent group of solution which are generated randomly at any stage of progress.
one important thing over here is data structure; often referred to as a chromosome in context of genetic algorithm. these chromosome stores genes or items which describe our set of solutions. in engineering computation, we describe these data structures in terms of binary digits ' 0 and 1 '. each solution has its own binary representation.
when this initial population is generated, we move on to the evaluation stage.
- stage 2: evaluation
in this stage, we figure out fitness of each of our solutions. the fitness is often a single number that gauges how the solution is fit to the objective function. the higher the fitness value, the better the solution is. after running simulations for all solutions, fitness score is gathered for each solution.
- stage 3: generational loop
here, we will try to improve our solutions over and over again. in this stage, we need to figure out when to terminate the loop so that the process doesn't continue over and over again. here we will check the current stage of the genetic improvement to check whether the solutions have satisfied the rules for loop termination. these rules are referred to as termination criteria and are defined before the beginning of the algorithm. the general types of termination criteria may include:
1) attainment of the goal
2) maximum number of generations/iterations reached.
3) The performance of generations has reached a stagnation state.
whether these termination criteria are satisfied, the loop will come to an end and we will be left with the approximate best results possible. otherwise, the loop will go on improving and finding and running iterations in search of termination criteria satisfaction and population will have to pass through the next stage of selection for the best solutions.
- stage 4: natural selection
this stage is where survival of the fittest takes place. all solutions are undergone a selection process, the best of them are selected for mating opportunities and generate offsprings. the solutions with highest fitness index will contain most valuable genetic information. hence, in the engineering case, this information would be in binary format compared to genes in a nature. this information from the selected parents would be passed on to the new generation and new set of population (solution) would emerge which is comparatively better than parent population.
- stage 5: variation stage:
this phase deals with exchange of parents genomes and introducing an offspring with genetic information derived from parents. new generation made up of parents of the previous generation and new offspring act as a starting population for next loop of genetic algorithm. method of genetic variations includes random crossovers between parent genes at a random site.
to include new genetic information in a population, concept of mutation plays a role over there. nature selects any of the random solutions and introduces some new genetic information within it. hence there is a novelty introduced within population which helps saving natural progression from the stagnation stage.
in engineering applications, we also mimic this natural process and we randomly change the binary information within solutions to produce offspring solutions. hence, at this stage, we mimic nature.
GENERATING A STALEGAMITE FUNCTION :
in order to demonstrate the operation of the genetic algorithm function in Matlab, we will take an example of stalagmite function and find a global maximum of this function using GA.
INPUT:
% generating a stalagmite function
function [stag_val] = stalagmite(feed_domain)
x = feed_domain(1);
y = feed_domain(2);
f1_x = (sin(5.1*pi*x + 0.5))^6;
f1_y = (sin(5.1*pi*y + 0.5))^6;
f2_x = exp(-4*log(2)*((x-0.0667)^2)/0.64);
f2_y = exp(-4*log(2)*((y-0.0667)^2)/0.64);
function_x = (f1_x)*(f2_x);
function_y = (f1_y)*(f2_y);
% negative sign is for making GA search maximum value
stag_val = -(function_x * function_y);
end
this is coding of stalagmite function which gives the output as a variable named ' stag_val'. after passing on values of x and y coordinate, the functions calculate the output and represent it in the stag_val variable.
feed domain over here is an input vector for values of x and y coordinates.
GENETIC ALGORITHM FUNCTION :
to demonstrate that GA function randomly selects search space and initial population, i will try to run a simple matlab program and show the optimization results.
INPUT:
close all
clear all
clc
% code conatining only function 'ga'
[opt_domain,f_val] = ga(@stalagmite,2) OUTPUT:
by observing the output, we can clearly manifest that ga function still gives results without any prior knowledge of search space or initial population.
although running code different times will give different results, this behavior corresponds to the random selection of initial guesses.
to make use of this approach, genetic algorithm should converge on the same optimum point every time code is executed. to achieve this task, we will make ga run on 3 different studies and make ga to work accurately by making constraints of the initial population and specified search space.
key thing here is, to find maximum of the given function, we have to plot it in negative manner so as to let GA find the negative most value of the function which is in actual the maximum value of the function. we can simply employ modulus function to get the maximum value out of GA search.
the code of three studies will start by having the first study as a random search in which there is not specified initial population nor defined search space. the second study would manifest progression in terms of fixed search space and consecutively, the third-most study will restrict search space as well as defined initial population.
INPUT:
close all
clear all
clc
x = linspace(0,0.6,150); % x and y domain lays desired search space
y = linspace(0,0.6,150);
generation_cycle = 50; % number of generations as stopping critarion
z = getstalagmite(x,y); % callig stalgmite function
% STUDY-1 - random initial population size and random search space
% listing out optimum domain values for each generation run
tic
for i = 1:generation_cycle
[opt_domain,stag_value(i)] = ga(@stalagmite,2);
x_opt(i) = opt_domain(1);
y_opt(i) = opt_domain(2);
end
run_time1 = toc
% plotting stalagmite function and results of ga search
figure(1)
subplot(2,1,1)
hold on
surf(x,y,z)
shading interp
scatter3(x_opt,y_opt,stag_value,'filled') % scatter function shows ga search results
title('random search')
xlabel('domain_x')
ylabel('domain_y')
subplot(2,1,2)
plot(stag_value)
xlabel('generation')
ylabel('optimum_search')
% STUDY-2 - random initial population size with bounded search space
% bounding search space for 0.8 * 0.8 XY domain
tic
for i = 1:generation_cycle
[opt_domain,stag_value(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.8;0.8]);
x_opt(i) = opt_domain(1);
y_opt(i) = opt_domain(2);
end
run_time2 = toc
% plotting stalagmite function and results of ga search
figure(2)
subplot(2,1,1)
hold on
surf(x,y,z)
shading interp
scatter3(x_opt,y_opt,stag_value,'filled') % scatter function shows ga search results
title('bounded search space')
xlabel('domain_x')
ylabel('domain_y')
subplot(2,1,2)
plot(stag_value)
xlabel('generation')
ylabel('optimum_search')
% STUDY-3 - fixed initial population size with bounded search space
options = optimoptions('ga'); % defining initial population
options = optimoptions(options,'populationsize',250);
tic
for i = 1:generation_cycle
[opt_domain,stag_value(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[0.8;0.8],[],[],options);
x_opt(i) = opt_domain(1);
y_opt(i) = opt_domain(2);
end
run_time2 = toc
% plotting stalagmite function and results of ga search
figure(3)
subplot(2,1,1)
hold on
surf(x,y,z)
shading interp
scatter3(x_opt,y_opt,stag_value,'filled') % scatter function shows ga search results
title('bounded search space and fixed initial population')
xlabel('domain_x')
ylabel('domain_y')
subplot(2,1,2)
plot(stag_value)
xlabel('generation')
ylabel('optimum_search')
OUTPUT:
STUDY - 1 ( time - 3.7174 seconds)
STUDY - 2 ( time - 5.0281 seconds)
STUDY - 3 ( time - 16.9652 seconds)
by observing all these study plots, we can say that the margin for study-3 is drastically narrowed out with value having seven-digit precision.
to locate the maximum function value, we have to simply take the modulus of stalagmite function values for study 3.
FINDING MAXIMUM VALUE OF STALAGMITE FUNCTION :
to find the maximum value, we again have to remove the negative sign assigned to optimum stalagmite function values stored in 'stag_value' variable for each of the study.
we will simply take arithmetic mean for each iteration performed. the window below shows the code for obtaining the maximum value and results for each study.
the results are clearly satisfactory for study-3 which puts definition on initial population size and search space.