AIM

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

INTRODUCTION

1.       OPTIMIZATION TECHNIQUES:

Mathematical optimization (alternatively spelled optimization) or mathematical programming is the selection of a best element (with regard to some criterion) from some set of available alternatives. In the simplest case, an optimization problem consists of maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics. More generally, optimization includes finding "best available" values of some objective function given a defined domain (or input), including a variety of different types of objective functions and different types of domains. [1]

The classical optimization techniques are useful in finding the optimum solution or unconstrained maxima or minima of continuous and differentiable functions. The optimization techniques are the analytical methods, and they make use of differential calculus in locating the optimum solution. The classical methods have limited scope in practical applications as some of them involve objective functions which are not continuous and/or differentiable. Yet, the study of these classical techniques of optimization forms a basis for developing most of the numerical techniques that have evolved into advanced techniques more suitable to current practical problems. These optimization methods assume that the function is differentiable twice with respect to the design variables and the derivatives are continuous.

Three main types of problems that can be handled by the classical optimization techniques:

• single variable functions
• multivariable functions with no constraints
• multivariable functions with both equality and inequality constraints. [In problems with equality constraints the Lagrange multiplier method can be used. If the problem has inequality constraints, the Kuhn-Tucker conditions can be used to identify the optimum solution.] [2]

 

2.     NUMERICAL METHODS OF OPTIMIZATION:

The numerical methods of optimization are discussed below: [2]

• Linear Programming: This programming technique studies the case in which the objective function f is linear, and the set A is specified using only linear equalities and inequalities. (A is the design variable space).
• Integer Programming: This programming studies the linear programs in which some or all variables are constrained to take on integer values.
• Quadratic Programming: This programming technique allows the objective function to have quadratic terms, while the set A must be specified with linear equalities and inequalities.
• Nonlinear Programming: This programming studies the general case in which the objective function or the constraints or both contain nonlinear parts.
• Stochastic Programming: This programming studies the case in which some of the constraints depend on random variables.
• Dynamic Programming: This programming studies the case in which the optimization strategy is based on splitting the problem into smaller sub-problems.
• Combinatorial Optimization: This optimization technique is concerned with problems where the set of feasible solutions is discrete or can be reduced to a discrete one.
• Infinite-dimensional Optimization: This optimization studies the case when the set of feasible solutions is a subset of an infinite-dimensional space, such as a space of functions.
• Constraint Satisfaction: This optimization technique studies the case in which the objective function f is constant (this is used in artificial intelligence, particularly in automated reasoning).

 

3.      ADVANCED OPTIMIZATION TECHNIQUES:

The advanced optimization techniques are discussed below: [2]

• Hill Climbing: This technique is a graph search algorithm where the current path is extended with a successor node which is closer to the solution than the end of the current path. In simple hill climbing, the first closer node is chosen whereas in steepest ascent hill climbing all successors are compared and the closest to the solution is chosen. Both forms fail if there is no closer node. This may happen if there are local maxima in the search space which are not solutions. Hill climbing is used widely in artificial intelligence fields, for reaching a goal state from a starting node. Choice of next node/ starting node can be varied to give a number of related algorithms.
• Simulated Annealing: In the simulated annealing method, each point of the search space is compared to a state of some physical system, and the function to be minimized is interpreted as the internal energy of the system in that state. Therefore, the goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy.
• Ant Colony Optimization: In the real world, ants (initially) wander randomly, and upon finding food return to their colony while laying down pheromone trails. If other ants find such a path, they are likely not to keep traveling at random, but instead follow the trail laid by earlier ants, returning, and reinforcing it if they eventually find food. Over time, however, the pheromone trail starts to evaporate, thus reducing its attractive strength. The more time it takes for an ant to travel down the path and back again, the more time the pheromones have to evaporate. A short path, by comparison, gets marched over faster, and thus the pheromone density remains high Pheromone evaporation has also the advantage of avoiding the convergence to a locally optimal solution. If there were no evaporation at all, the paths chosen by the first ants would tend to be excessively attractive to the following ones. In that case, the exploration of the solution space would be constrained. Thus, when one ant finds a good (short) path from the colony to a food source, other ants are more likely to follow that path, and such positive feedback eventually leaves all the ants following a single path. The idea of the ant colony algorithm is to mimic this behavior with "simulated ants" walking around the search space representing the problem to be solved.  Ant colony optimization algorithms have been used to produce near-optimal solutions to the traveling salesman problem. They have an advantage over simulated annealing and genetic algorithm approaches when the graph may change dynamically. The ant colony algorithm can be run continuously and can adapt to changes in real time. This is of interest in network routing and urban transportation systems.
• Genetic Algorithm: A genetic algorithm (GA) is a local search technique used to find approximate solutions to optimization and search problems. Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination). Genetic algorithms are typically implemented as a computer simulation, in which a population of abstract representations (called chromosomes) of candidate solutions (called individuals) to an optimization problem, evolves toward better solutions. The evolution starts from a population of completely random individuals and occurs in generations. In each generation, the fitness of the whole population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness) and modified (mutated or recombined) to form a new population. The new population is then used in the next iteration of the algorithm.

4.     GENETIC ALGORITHM:

In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover, and selection. In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible. The evolution usually starts from a population of randomly generated individuals, and is an iterative process, with the population in each iteration called a generation. In each generation, the fitness of every individual in the population is evaluated; the fitness is usually the value of the objective function in the optimization problem being solved. The more fit individuals are stochastically selected from the current population, and each individual's genome is modified (recombined and possibly randomly mutated) to form a new generation. The new generation of candidate solutions is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.

A typical genetic algorithm requires:

1. a genetic representation of the solution domain,
2. a fitness function to evaluate the solution domain.

A standard representation of each candidate solution is as an array of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in genetic programming and graph-form representations are explored in evolutionary programming; a mix of both linear chromosomes and trees is explored in gene expression programming. Once the genetic representation and the fitness function are defined, a GA proceeds to initialize a population of solutions and then to improve it through repetitive application of the mutation, crossover, inversion, and selection operators. [3]

The five phases that are considered in a genetic algorithm are described as follows:[4]

• Initial Population: The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem that has to be solved. Each individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution). In a genetic algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, the binary values are used (string of 1s and 0s). In common terminology, it is referred to as ‘encoding the chromosome’.

 

           Figure 1. Depiction of Gene, Chromosome and Population

• Fitness Function: The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.
• Selection: The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.
• Crossover: Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

For example, consider the crossover point to be 3 as shown below in the figure 2.

 Figure 2. Showing Crossover point

 The offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

Figure 3. Process of crossover

The new offspring are added to the population as shown below:

 

Figure 4. Offspring

•  Mutation: In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped. Mutation occurs to maintain diversity within the population and prevent premature convergence.

 

 Figure 5. Offspring before and after mutation

•  Termination: The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). It is then said that the genetic algorithm has provided a set of solutions to our problem.

 

OBJECTIVES

• To write a code in MATLAB to optimize the stalagmite function and find the global maxima of the function.
• To explain the genetic algorithm in own words along with the explanation of the syntax for 'ga' in MATLAB.
• To make sure that the code gives the same output, even after repeated trials.
• To plot the graphs for all 3 studies and for f maximum versus number of iterations.

 

PROGRAM – CODE WRITTEN IN MATLAB

PROBLEM STATEMENT:

A stalagmite function defined by the following set of equations:

A code using the above set of equations is to be written to evaluate the Global maxima.

 

CODE SIMULATION-i:

%Program to evaluate the global maxima

clear all

close all

clc

 

%Defining the search space

x = linspace(0,0.6,150);

y = linspace(0,0.6,150);

 

%creating 2D mesh

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

 

%defining the number of times to run the genetic algorithm

p = 50;

 

%EVALUATION USING BASIC FITNESS FUNCTION

tic

 

%Evaluating stalgamite 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

for i = 1:p

    [inputs,fopt(i)] = ga(@stalagmite,2);

    xopt(i) = inputs(1);

    yopt(i) = inputs(1);

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','k');

legend('stalagmite','stalgamite','Global maxima')

xlabel('X-values');

ylabel('Y-values');

zlabel('Z-Values');

title('Unbounded Inputs');

 

subplot(2,1,2);

plot(-fopt);

legend('Optimized f value');

xlabel('Iterations');

ylabel('Function Fitness');

 

 

%EVALUATION USING ADDITIONAL PARAMETERS - setting the boundaries

tic

for i = 1:p

    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);

    xopt(i) = inputs(1);

    yopt(i) = inputs(1);

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','k');

legend('stalagmite','stalgamite','Global maxima')

title('Bounded Inputs');

xlabel('X-values');

ylabel('Y-values');

zlabel('Z-Values');

subplot(2,1,2);

plot(-fopt);

legend('Optimized f value');

xlabel('Iterations');

ylabel('Function Fitness');

 

 

%EVALUATION USING ADDITIONAL PARAMETERS - varying population

 

options = optimoptions('ga');

options = optimoptions(options,'PopulationSize',100);

tic

for i = 1:p

    [inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);

    xopt(i) = inputs(1);

    yopt(i) = inputs(1);

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','k');

legend('stalagmite','stalgamite','Global maxima')

title('Bounded Inputs with defined Popoulation');

xlabel('X-values');

ylabel('Y-values');

zlabel('Z-Values');

subplot(2,1,2);

plot(-fopt);

legend('Optimized f value');

xlabel('Iterations');

ylabel('Function Fitness');

 

 

EXPLANATION:

 

EVALUATION USING BASIC FITNESS FUNCTION

• The code begins with the introduction of search space governed by the variables x and y and are in turn defined using the command ‘linspace’.
• This 1-D search space is not identified by the genetic algorithm.
• A 2-D array is created with the values of x and y using the command ‘meshgrid’.
• An arbitrarily chosen value, in this case, p=50, is used depict the number of times to run the genetic algorithm.
• A stalagmite function is created i.e. a function as defined in the problem statement is written as a ‘function’ in MATLAB that details every parameter. The following shows the function ‘stalagmite’ written in MATLAB:

 

function [z] = stalagmite(input_vector)

x = input_vector(1);

y = input_vector(2);

f_1x = (sin(5.1*pi*x + 0.5))^6;

f_1y = (sin(5.1*pi*y + 0.5))^6;

f_2x = exp(-4*log(2)*((x-0.0667)^2/0.64));

f_2y = exp(-4*log(2)*((y-0.0667)^2/0.64));

[z] = -[f_1x*f_2x*f_1y*f_2y];

end

 

DESCRIPTION:

In this, a matrix [z] is assigned to a function stalagmite which takes a single input named ‘input_vector’.

The input_vector(1) is assigned to x value and input_vector(2) is assigned to y value. The stalagmite function is defined using f_1x, f_1y, f_2x and f_2y as mentioned in problem statement. At last, the value of [z] is defined by the negative product of the values of the function f along x and y directions. The incorporation of the negative sign is because, genetic algorithm by default, calculates the global minima and here, in the current study, global maxima is needed. Therefore, the sign variation mathematically sums up to the value being global maxima.

• Evaluating the Stalagmite function:

Selecting two loop counter variables I and j which run from 1 to the length of xx and yy respectively. The values of xx(i,j) and yy(i,j) are assigned to input_vector(1) and input_vector(2) respectively. Then stalagmite function is invoked to be assigned to f(i,j). It is made sure that the dimensions are intact.

• Running the genetic algorithm on defined stalagmite function:

A for loop is established that ranges from 1 to 50 (i.e. number of times the genetic algorithm was intended to run which is defined as ‘p’ in the inputs). An array consisting of inputs and optimum function value is considered and genetic algorithm that runs on stalagmite is assigned to this array as shown below:

 

[inputs,fopt(i)] = ga(@stalagmite,2);

 

In this, we observe the command ‘ga’ that stands for genetic algorithm.

 

COMMAND ‘ga’ : Genetic algorithm solver for mixed-integer or continuous-variable optimization, constrained or unconstrained. Genetic algorithm solves smooth or nonsmooth optimization problems with any types of constraints, including integer constraints. It is a stochastic, population-based algorithm that searches randomly by mutation and crossover among population members

.

Syntax: x = ga(fun,nvars)

 

This finds a local unconstrained minimum, x, to the objective function, fun. nvars is the dimension (number of design variables) of fun. [6]

Therefore, in the written code, to evaluate the optimum value for the input, the genetic algorithm takes in a function handle that holds the function to be evaluated i.e., stalagmite function and also the number of variables that are a part of the function ‘stalagmite’ which in this case are two i.e., x and y.

 

• The process of defining variables that can be incorporated in the stalagmite function and invoking the stalagmite function consume time. The process time is recorded by using two commands from MATLAB namely ‘tic’ and ‘toc’.

 

COMMANDS TIC AND TOC: The command ‘tic’ works with the ‘toc’ function to measure elapsed time. The tic function records the current time, and the toc function uses the recorded value to calculate the elapsed time. [7]

 

• The value of toc is assigned to a variable called study1_time. This gives the time taken to perform the Basic Fitness optimization.
• A figure window using figure(1) is created to store the data from the subplot that creates a surface plot with the variation of the variables in xx, yy and -f.

 

SUBPLOT COMMAND: subplot(m,n,p) divides the current figure into an m-by-n grid and creates axes in the position specified by p. MATLAB® numbers subplot positions by row. The first subplot is the first column of the first row, the second subplot is the second column of the first row, and so on. If axes exist in the specified position, then this command makes the axes the current axes. [8]

 

SURFACE CONTOUR COMMAD: surfc(X,Y,Z) creates a three-dimensional surface plot with a contour plot underneath. A surface plot is a three-dimensional surface that has solid edge colors and solid face colors. The function plots the values in matrix Z as heights above a grid in the x-y plane defined by X and Y. The color of the surface varies according to the heights specified by Z. [9]

 

• A new command named ‘shading interp’ is used. This command is used to avoid the grids that are created on the plot.

 

SHADING INTERP: shading interp varies the color in each line segment and face by interpolating the colormap index or true color value across the line or face. [10]

 

• A plot3 command is used to plot the values of the optimum values of x , y and the function ‘f’ (this value of ‘f’ is predicted by genetic algorithm over 50 studies) with a marker ‘o’ colored in red of size 5 units in the same subplot created above.

 

PLOT3 COMMAND: plot3(X, Y, Z) plots coordinates in 3-D space. To plot a set of coordinates connected by line segments, specify X, Y, and Z as vectors of the same length. To plot multiple sets of coordinates on the same set of axes, specify at least one of X, Y, or Z as a matrix and the others as vectors. [11]

 

• The x, y and z labels are created to identify the values on the plot and title of the plot is given as the ‘Unbounded inputs.’ Legend is written to identify the parameters on the graph.
• Another subplot is created to clearly understand the variation of optimum f i.e., fopt over 50 iterations that genetic algorithm performs.

 

OBSERVATION AND CONCLUSION:

• The global maxima is said to occur at:

X : 0.681514

Y: 0.681514

Z: 0.994995

• The time taken to evaluate the genetic algorithm is 2.1724 seconds.
• The drawback with the written code is that the value of global maxima is not constant. It varies with every simulation run. To avoid this, the search space of the genetic algorithm is controlled.
• The results of the simulation of genetic algorithm using basic fitness function are:

Figure 6. Results of basic fitness using genetic algorithm.

•  The range of maximum value lies between 0 and 1 as observed from the figure 6, which does not give us a proper concentrated area. The values are diffused in the given range which does not imply a good solution.

 

EVALUATION USING ADDITIONAL PARAMETERS - setting the boundaries:

 

• No prior code is necessary. This modified code is simulated in the same editor.
• Running the genetic algorithm on defined stalagmite function with the same initial parameters:

A for loop is established that ranges from 1 to 50 (i.e. number of times the genetic algorithm was intended to run which is defined as ‘p’ in the inputs). An array consisting of inputs and optimum function value is considered and genetic algorithm that runs on stalagmite is assigned to this array as shown below:

 

[inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1]);

 

In this, we observe the command ‘ga’ that stands for genetic algorithm, has a different syntax from the one that was used to execute the optimization in the case mentioned before. The syntax for ga is explained as below:

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.) [6]

• Tic-toc command is used to evaluate the time taken to run the genetic algorithm.
• The plots and corresponding commands are kept unchanged and are followed to code this program as well.

OBSERVATION AND CONCLUSION:

• The results of the simulation of genetic algorithm using basic fitness function are:

Figure 7. Results of bounded inputs using genetic algorithm.

• The global maxima is said to occur at:

X : 0.0668267

Y: 0.0668267

Z: 1

• The time taken to evaluate the genetic algorithm is 2.5177 seconds.
• The range of maximum value lies between 0.5 and 1 as observed from the figure 7.
• By default, ‘ga’ takes the number of samples as 50. Since there are two variables, there will be 50 sets of two random variables which constitute the population. In the current case of defining the boundaries, if the population is too small, ‘ga’ may not be able to find the required global maxima but with definitely find the local maxima.
• Although, in this code, the search space for the genetic algorithm is properly defined, the output is still not satisfactory. On repetitive revaluation of the code, the solution set still does not converge.
• A further advanced and specific code is written by introducing more parameters in ‘ga’ function.

EVALUATION USING ADDITIONAL PARAMETERS - varying population along with defined boundaries.

• No prior code is necessary. This modified code is simulated in the same editor.
• Running the genetic algorithm on defined stalagmite function with the same initial parameters:

A for loop is established that ranges from 1 to 50 (i.e. number of times the genetic algorithm was intended to run which is defined as ‘p’ in the inputs). An array consisting of inputs and optimum function value is considered and genetic algorithm that runs on stalagmite is assigned to this array as shown below:

 

[inputs,fopt(i)] = ga(@stalagmite,2,[],[],[],[],[0;0],[1;1],[],[],options);

 

In this, we observe the command ‘ga’ that stands for genetic algorithm, has a different syntax from the one that was used to execute the optimization in the case mentioned before. This not only includes the boundaries but also includes the options that are used to guide the execution of ‘ga’. The syntax for ga is explained as below:

 

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.) (Set Aeq=[] and beq=[] if no linear equalities exist.) Create options using optimoptions. [6]

 

OPTIMOPTIONS COMMAND: It is used to create optimization options.

options = optimoptions(SolverName) returns a set of default options for the SolverName solver.

options = optimoptions(oldoptions,Name,Value) returns a copy of oldoptions with the named parameters altered with the specified values. [12]

 

• Due to the small population size, which may have occurred in the case where only boundaries are defined in the genetic algorithm, the global maxima may have been compromised. In order to avoid that, population size has been introduced.
• The population size in this code is varied from 100 t0 300.
• Tic-toc command is used to evaluate the time taken to run the genetic algorithm.
• The plots and corresponding commands are kept unchanged and are followed to code this program as well.

OBSERVATION AND CONCLUSION:

• The global maxima is said to occur at the following when the population size is 300.

X : 0.066842

Y: 0.066842

Z: 1

• The time taken to evaluate the genetic algorithm is 10.2600 seconds.
• The results of the simulation of genetic algorithm using basic fitness function are:

Figure 8. Results of bounded inputs with defined population using genetic algorithm.

• The results of the simulation of genetic algorithm using additional parameters that include specification of the boundaries and the population size has a good impact on the optimization of the function.
• In the above two cases of using ‘ga’ algorithm, the outputs did not show any consistency but on the bright side, they did compute fast. Therefore, the above cases can be used when the problem in hand is well defined by various parameters and the size of the problem is small.
• From figure (8) the maximum value of the function lies in a very narrow range and the value lies remarkably close to 1. While this is not observed with the other two cases of using genetic algorithm. The case of unbounded ‘ga’ algorithm had range of maxima of [0,1] whilst the case of bounded ‘ga’ algorithm encompassed a range of [0.5,1]. Although the improvement from case 1 to case 2 is remarkable, the case 3 of closely defined parameters for ‘ga’ algorithm yielded the best set of results.
• On running the ‘ga’ algorithm with defined boundaries and varying population size, the following data is obtained:

Population Size	X- Value	Y- Value	Z- Value	Time taken (seconds)
100	0.0668368	0.0668368	1	4.1511
150	0.0668285	0.0668285	1	5.5437
200	0.0668249	0.0668249	1	7.2886
250	0.0668319	0.0668319	1	8.6755
300	0.0668424	0.0668424	1	10.2600
350	0.0668414	0.0668414	1	11.9839
400	0.0668298	0.0668298	1	14.8394

Table 1. Tabulation of results obtained by varying population size.

• From the above tabulated information, it is safe to assume that the population size of 300 produced highly optimum result which not only balanced the accuracy of the solution but also could complete the algorithm in appreciable amount of time.

 

UNDERSTANDING GENETIC ALGORITHM IN OWN TERMS:

In 1895, Charles Darwin proposed a theory of natural selection that emphasized on the carrying of the desired characteristic traits of one generation to their offspring. This detailed about a species’ adaption to the environment that it is subjected to and passing down the necessary and important information of survival to the next generation.

Charles Darwin defined natural selection as the "principle by which each slight variation [of a trait], if useful, is preserved" [6]

Based on this theory, genetic algorithm is formulated, that performs optimization of the population. A certain set of population is considered and is subjected to calculate the fitness. This procedure identifies the heritable traits of the population over the regular traits. If any appreciable phenotype is observed from the population under consideration it is processed further, otherwise the process of mutation is terminated. Once the desired traits are observed, the selection of such population is carried on and is subjected to crossover. This process is analogous to reproduction in biological terms. Off-springs with desired traits are obtained. Among the produced off-springs, few of them undergo mutation i.e. development in their traits to stand a better chance for selection. The mutated species are again subjected to fitness calculation. The process is iterative until there is no chance of generating an heir or until all the possibilities of the mutations are exhausted and the domain converges into a single point.

   Figure 6.  Flowchart of Genetic Algorithm

 

VARIOUS SYNTAXES FOR GENETIC ALGORITHM:

MATLAB gives the user to evaluate the genetic algorithm using different syntaxes based on the availability of the information with the user. It helps to optimize the function accordingly thereby helping the user find the global minima. The following are the syntaxes used to evaluate the genetic algorithm:

1. 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.
2. 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').
3. 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').
4. 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.)
5. 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.)
6. 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.
7. x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon) or x = ga(fun,nvars,A,b,[],[],lb,ub,nonlcon,IntCon,options) requires that the variables listed in IntCon take integer values.

8. x = ga(problem) finds the minimum for problem, a structure described in problem.
9. [x,fval] = ga(___), for any previous input arguments, also returns fval, the value of the fitness function at x.
10. [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.
11. [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. [6]

 

RESULT

• A code to optimize the stalagmite function and also finding the global maxima has been written.
• A clear understanding of genetic algorithm has been achieved.
• Various syntaxes for genetic algorithm have been identified and few among the identified syntaxes have been used in the code written to find global maxima.
• The genetic algorithm when subjected to additional parameters has been observed to perform really good. The algorithm on being given such conditions has narrowed its path of evaluation and could conclude the global maxima at the value 1 in a short time span.

Description	X-Value	Y-Value	Z-Value	Time (sec)
Only function and number of variables are invoked in ‘ga’	0.681514	0.681514	0.994995	2.1724
Boundaries are also invoked in ‘ga’	0.0668267	0.0668267	1	2.5177
Boundaries along with population size are invoked in ‘ga’	0.0668424	0.0668424	1	10.2600

 

CONCLUSION

In conclusion, the genetic algorithm is one of the finest ways to perform the optimization of the function under consideration. The efficiency of the genetic algorithm can also be improved by using additional parameters. In this method the anonymous function is used to capture the values of additional arguments, namely the constants. And further assigning this to the known function and evaluating it by defining the constant values will reduce the computational time. To further reduce the computational time when large amounts of information is being subjected to optimization, vectorized parameter method can be adopted. The parameters in this method are converted into vectors.

 

BIBLIOGRAPHY

1. https://en.wikipedia.org/wiki/Mathematical_optimization
2. https://nptel.ac.in/content/storage2/courses/105108127/pdf/Module_1/M1L4slides.pdf
3. https://en.wikipedia.org/wiki/Genetic_algorithm
4. https://towardsdatascience.com/introduction-to-genetic-algorithms-including-example-code-e396e98d8bf3#:~:text=A%20genetic%20algorithm%20is%20a,offspring%20of%20the%20next%20generation.
5. http://darwin-online.org.uk/content/frameset?itemID=F373&viewtype=side&pageseq=76
6. https://in.mathworks.com/help/gads/ga.html
7. https://in.mathworks.com/help/matlab/ref/tic.html
8. https://in.mathworks.com/help/matlab/ref/subplot.html?searchHighlight=subplot&s_tid=srchtitle
9. https://in.mathworks.com/help/matlab/ref/surfc.html
10. https://in.mathworks.com/help/matlab/ref/shading.html
11. https://in.mathworks.com/help/matlab/ref/plot3.html
12. https://in.mathworks.com/help/optim/ug/optim.problemdef.optimizationproblem.optimoptions.html