Week 4.1 - Genetic Algorithm

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

INTRODUCTION: A genetic algorithm (GA) is a search-based optimization technique based on the principles of Genetics and Natural Selection. It is frequently used to find optimal or near-optimal solutions to difficult problems which otherwise would take a lifetime to solve It is frequently used to solve optimization problems, in research, and in machine learning.

Optimization:- Optimization is the process of making something better in any process, we have a set of inputs and a set of outputs as shown in the following

figure.

What are Genetic algorithms?

Nature has always been a great source of inspiration to all mankind. Genetic Algorithms (GAS) are search based algorithms based on the concepts of natural selection and genetics. GAS are a subset of a much larger branch of computation known as Evolutionary Computation

GAs are developed by John Holland and his students and colleagues at the University of Michigan, most notably David E. Goldberg and has since been tried on various optimization problems with a high degree of success. In GAs, we have a pool or a population of possible solutions to the given problem. These solutions then undergo recombination and mutation (like in natural genetics), producing new children, and the process is repeated over various generations. Each individual (or candidate solution) is assigned a fitness value (based on its objective function value) and the fitter individuals are given a higher chance to mate and yield more "fitter" individuals. This is in line with the Darwinian Theory of "Survival of the Fittest".

In this way we keep "evolving" better individuals or solutions over generations, till we reach a stopping criterion.

Genetic Algorithms are sufficiently randomized in nature, but they perform much better than random local search (In which we just try various random solutions, keeping track of the best so far), as they exploit historical Information as well.

Process of natural selection

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found. This notion can be applied for a search problem. We consider a set of solutions for a problem and select the set of best ones out of them. Five phases are considered in a genetic algorithm.

1. Initial population

2. Fitness function.

3. Selection

4. Crossover

5. Mutation

1.Initial population - The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve. An 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, binary values are used (string of Is and Os). We say that we encode the genes in a chromosome.

2.Fitness fuction

Fitness Function (also known as the Evaluation Function) evaluates how close a given solution is to the optimum solution of the desired problem. It determines how fit a solution is:

• why we use fitness functions

In genetic algorithms, each solution is generally represented as a string of binary numbers, known as a chromosome. We have to test these solutions and come up with the best set of solutions to solve a given problem. Each solution, therefore, needs to be awarded a fitness score, to indicate how close it came to meeting the overall specification of the desired solution. This score is generated by applying the fitness function to the test, or results obtained from the tested solution.

3.Selection

The selectionj is based on the fitness score. 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.

4.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. Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

5. 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. termination The algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation).

Then it is said that the genetic algorithm has provided a set of solutions to our problem. The population has a fixed size. As new generations are formed, individuals with least fitness die, providing space for new offspring. The sequence of phases is repeated to produce individuals in each new generation which are better than the previous generation. Ga as function of matlab

PROGRAM FOR FUNCTION:

function [GA] stalagmite (input_vector) = x=input_vector (1);

y=input_vector (2);

term1 = pi*5.1*x;

term2 = pi*5.1*y;

term3= ((x-0.0667)^2/0.64);

term4 = ((y-0.0667)^2/0.64);

term5= (-4) * log(2);

xf1 = (sin(term1 + 0.5)).^6; yf1 = (sin(term2 + 0.5)).^6;

xf2 = exp(term5*term3);

yf2 = exp(term5*term4);

GA=-(xf1*yf1*xf2*yf2);

end

• After creating the function, we need to create a program to optimize the stalagmite function and find the global maxima of the function.

• For that start with clear all close all and clc again.

• Then we have to define the search spaces x,y using linspace command.

• Then we have to create a 2dimensional mesh by using meshgrid command in matlab.

• Using for loop in matlabe, we have to evaluate the stalagmite function which we have created.

• After evaluating the function, we have to start our study.

• First, we have to observe the statistic behavior in unbounded conditions.

. tic-toc command is used to claculate the time of optimization.

By using for loop we have call the function. • After this, we have to plot the graph of study one.

• We, have to di the same for the second study that is study the statistic behaviour with upper and lower bound conditions.

• Plot the graph for second study by using the same plot command.

• Third, we have to observe the changes by inceresing the GA iterations.

• Here on plotting stalagmite function, I am plotting the minimum value that 'ga' predicts, which is all over the place on graph, "It happens due to random sample during each iteration the value changes.

• Also in command window, we can observe the time taken for iteration is (study_1_time = 9.1623)sec

• Here from the graph, it is observed that the function predict minimum points is between 3peaks, it is much clear than Study-1 0.6, it is much

• If look at graph y-axis minimum values lies between 0.4 & accurate, but still not clear..

• Also, we can observe the time taken for iteration is (study_2_time=5.8964)sec.

• Here from subblot-1, it shows maxima only lles around 1peak

• Maxima lies at around the value 0.85 that ga predicts

• In this study it giving the optimum value, on increasing the number Of iteration and applying constraints, but it has its drawbacks, as ga slows down as it have more number of samples, to process and evaluate them for the function.

• It takes (study_3_time=20.5915)sec.

CONCLUSION:

The code In MATLAB to optimise the stalagmite function and find the global maxima of the function is writen and the result is obtained and observed.