Genetic Algorithm

Minimization of Multivariable Functions

by Madeleine Ong Siang Ting

Introduction

Genetic algorithm is a stochastic search process, termininating upon exhaustion or by simply meeting the exit criteria.  That line itself do not divulge the differences between genetic algorithm and other stochastic methods used in programs or scripts.

The main difference comes from the evolution of the initial population, creating subsequent generations with desirable traits.

To fully appreciate that idea, as well as to illustrate the difference between GA and other stochastic process, it is somewhat recommended to speak briefly on Infinite Monkey Theorem.

Infinite Monkey Theorem (IMT)

Imagine a monkey being provided with a keyboard that has 27 keys - 26 of them being the alphabets in the English language and a spacing. The probability of said monkey reproducing a line from Shakespeare’s Hamlet:
“to be or not to be that is the question”
is a classical probability case, whereby all characters have equal probabilities of turning up. There are 39 characters in that line, and probability of said monkey getting the first letter right is just 1/27.

Probability of getting the entire sentence correct would be:

(1/66555937033867822607895549241096482953017615834735226163)

Which is a remarkably small number. So what’s the probability of the monkey reproducing all of Shakespeare’s works? Even if it started during the Big Bang, it’s highly unlikely for us to even have Hamlet at this time.

Having an infinite number of monkeys will actually improve the chance of getting a line right, but still it would take a long period of time before they could reproduce all of Shakespeare’s works. Not to mention it is hardly cost effective, let alone a smart way of handling resources.

The IMT illustrates the weakness of some stochastic processes: increasing the number of sample points increases the chance of getting a more accurate results. Large increase in sample size also increases computational cost.

The Problem

An optimization problem - minimization/maximisation of functions. Here our primary concern is the minimization of a function f[var], seeking the global minimum.

The function used in this presentation/project is a function of 3 variables and is expected to have a global minimum about the origin (0,0,0).

The aforementioned function is:

f[x,y,z] = x^2 + y^2 + Cos(2xy) + z^2

General Outline of the Algorithm

The point of this chapter is to briefly introduce the major components of GA. It should be noted that there are other far more complicated and better schemes that can be used, and the one used here is chosen for its simplicity.

The alogirthm can be imagined as consisting of three major sections:

Initialization - creating the first generation that acts as the ancestors of all subsequent generations.

This part is further divided into two parts:

Encoding

Decoding

Selection - selecting individuals that best satisfy the fitness test. Selected individuals are kept, crossbred and mutated to create the next generation.

There are several matters to attend to in selection and relies partially on the type of encoding scheme used.

Replacement Scheme

Selection Scheme

Breeding - creating subsequent generations

Consists of two major parts:

Crossbreeding

Mutation (Optional)

Initialization

Prior to any detailed explaination on Initialization, it’s best to explain a the term population:

Population: set of possible solutions that when plugged into f[x,y,z] may or may not yield a global minimum. 
Eg: {3.091876, 4.56789, 0.02980}; {0.8726, 1.9802, -1.6802} - both are possible solutions to the function f[x,y,z] and are collectively called as a set of possible solutions/population. It is a population of size 2.

As previously mentioned, the purpose is to create a set of individuals. This set of individuals is often generated randomly. See code below.

CreatePop[var_Integer:3,size_:20]:=Module[{},
PopSize=size;nIndex=var;
Do[
Pop[ngen]=N[RandomReal[{-5,5},PopSize],7];
encodePop[ngen],{ngen,nIndex}];
];

From the code above, the first generation is created in a sample space {-5,5} for all variables and the population size is only 20.

It does look somewhat easy - and in fact, there is an easier way then the one shown above.

Genotype and Phenotype

This is a good point to talk about phenotype and genotype and the importance they have in GA.

Genotype:

In genetics, genotype of an organism is the information contained on its DNA. It is the actual genetic code that is transferred down from generation to generation.

In GA, the genotype is the digital information

Phenotype:

In genetics, phenotype is the set of observable properties of an organism.

In GA, this is what the digital information is supposed to represent

An example to drive the point through:

The encoding and decoding mechanisms facilitate in mapping from genotype space to phenotype space and vice versa.

Encoding & Decoding

Usually in GA the population is converted from the numeric data types to an array of strings, and normally binary strings are preferred. The conversion process from different data types can be done by typecasting them with operators and/or builtins. But is it really required to convert the data from decimal to binary?

Binary representation is preferred as it is the most natural ways numbers are represented in computers, mimicking how DNA and RNA are produced from 4 different bases: A (adenine), C (cytosine), G (guanine), and T (thymine). However this does not imply that a direct conversion or hexadecimal or other conversion schemes should not be used.

The type of conversion used is unique to the problem and also depending on how the fitness test is designed to filter out the fittest/weakest of the population. Below shows how each individual of the population is encoded:

encodePop[index_Integer]:=Module[{},
Pop[index]=Table[ToString[Pop[index][[i]]],{i,PopSize}];
];

It should be noted that how the population is encoded will greatly effect the design of the range, fitness test, fitness function, and crossbreeding and mutation schemes.

Below is the code for decoding:

decodePop[index_Integer]:=ToExpression[Pop[index]];

Decoding are normally used to display data to the user, however there are cases whereby decoding is required before it is sent to the fitness function.

Selection

The importance of selection: removal of recessive genes/ weak individuals.

Process of selection is divided into two steps:

Fitness evaluation

Creation of mating pool

Fitness Evaluation

A fitness function must be designed in order for the GA to function properly.  The function produces a numeric score to describe the fitness of an individual of the population.

Example: Evolving the word “cat”
Fitness = number of correct characters

or...
Fitness = standard deviation from accepted value

The function f is used as the fitness function to evaluate inidividuals of the population.

fitnessfunc[i1_Integer,i2_Integer,i3_Integer]:=(decodePop[i1])^2+(decodePop[i2])^2+ Cos[3*decodePop[i1]*decodePop[i2]]+(decodePop[i3])^2;

Creation of Mating Pool

Once the fitness of each member of the population is evaluated, members that are fit to become parents can be selected and placed in a mating pool.

In general, creation of a mating pool is usually a two step process that is defined by one’s choice of selection scheme and replacement scheme.

In designing a properly functioning GA, one needs to first figure out the replacement scheme to be used:

Replace worst

Replace best

Replace parent

Replace random

Replace most similar

The replacement scheme used in this project is replace worst.

Selection scheme is used to select inidividuals from the population that are deemed suitable to be parents for the next generation.
Selection schemes:

Rank Selection

Roulette Wheel Selection

Tournament Selection

The selection scheme used in the project is rank selection - easiest scheme to exceute, however not the best. Rank selection scheme is made by ranking individuals according to their fitness. Individuals with the highest fitness value will be placed at the top and will be parents of the next generation. This scheme is somewhat prone to the creation of superindividuals.

There are other selection schemes than the ones stated above, however the three are among the most common. Roulette wheel selection is normally a good selection scheme as individuals are categorized into groups and groups are weighted depending on the average of each groups fitness. This allows individuals with low fitness to be introduced back into the population.
Tournament selection requires far more rigorous fitness tests and are often difficult to design.

Below shows the code used:

fitnesstest[ParentNo_Integer:10,OffspringNo_Integer:10]:=Module[{},
Parent=ParentNo;
f=fitnessfunc[1,2,3];
Scan[If[f[[#]]≤min,min=f[[#]]]&,Range[PopSize]];
selected=Ordering[f];
count=Take[selected,Parent];
Do[
Pop[ngen]=Part[Pop[ngen],count],{ngen,3}]; (*pop reduced to best 10*)
];

Breeding

Purpose of breeding is to produce new individuals/ next generation. In breeding, there are two major components at play: crossbreeding and mutation.

Crossbreeding

Or sometimes called as crossover. It involves the creation of a new individual from the genetic code of two parents. See image below:

The scheme used above is the 50/50 method - both parent contribute equivalent amount of genetic material to their child. Other combinations could be used to create more variations in the population.

Other variations of crossover:

Random midpoint approach

Coin-flipping approach

The two strategy essentially produce the same results. Below is a portion of a user defined function that implements the random midpoint approach:

Scan[(locator=RandomInteger[{3,5}];
If[StringTake[Pop[index][[#]],{locator}]=="."||StringTake[dupPop[[#]],{locator}]==".",locator+=RandomChoice[{-1,1}]];
Pop[index]=Append[Pop[index],
StringReplace[Pop[index][[#]],StringTake[Pop[index][[#]],{locator,StringLength[Pop[index][[#]]]}]->StringTake[dupPop[[#]],{locator,StringLength[dupPop[[#]]]}]]])&,Range[1,Parent]];

Mutation

Mutation is an optional step and is often controlled by parameters: mutation rate and mutation radius. Mutation can be made compulsory, but fixing the mutation rate = 1.0

Mutation is implemented in the project as a way to introduce variation into the population, as well there can only be so much variety when seeding the first generation.

When mutation occurs, the bit that is replaced does not originate from its parents, but is randomly produced.

The mutation rate and mutation radius used here are varied. The code shown below shows mutation of offsprings:

For[i=Parent+1,i≤Parent+10,i++,
rate=RandomInteger[{1,3}];
Do[
loc=RandomInteger[{1,7}];
If[StringTake[Pop[index][[i]],{loc}]==".",loc+=1];
gene=RandomInteger[{loc,loc},2];
Pop[index]=ReplacePart[Pop[index],Pop[index][[i]]->StringReplacePart[Pop[index][[i]],ToString[RandomInteger[{0,9}]],gene]]
,{irate,rate}];
];

Setup

Initialized cell containing the code:

Clear["Global`*"];
min=10^6;SeedRandom[123];

CreatePop[var_Integer:3,size_:20]:=Module[{},
PopSize=size;nIndex=var;
Do[
Pop[ngen]=N[RandomReal[{-5,5},PopSize],7];
encodePop[ngen],{ngen,nIndex}];
];

encodePop[index_Integer]:=Module[{},
Pop[index]=Table[ToString[Pop[index][[i]]],{i,PopSize}];
];

decodePop[index_Integer]:=ToExpression[Pop[index]];

(*use like value-returning funcs in py*)
fitnessfunc[i1_Integer,i2_Integer,i3_Integer]:=(decodePop[i1])^2+(decodePop[i2])^2+ Cos[3*decodePop[i1]*decodePop[i2]]+(decodePop[i3])^2;

(*Ordering min->max*)
fitnesstest[ParentNo_Integer:10,OffspringNo_Integer:10]:=Module[{},
Parent=ParentNo;
f=fitnessfunc[1,2,3];
Scan[If[f[[#]]≤min,min=f[[#]]]&,Range[PopSize]];
selected=Ordering[f];
count=Take[selected,Parent];
Do[
Pop[ngen]=Part[Pop[ngen],count],{ngen,3}]; (*pop reduced to best 10*)
];

crossbreed[index_Integer,OffspringNo_Integer:10]:=Module[{},
dupPop=RandomSample[Pop[index]];(*best Parent*)
(*Crossbreed*)
Scan[(locator=RandomInteger[{3,5}];
If[StringTake[Pop[index][[#]],{locator}]=="."||StringTake[dupPop[[#]],{locator}]==".",locator+=RandomChoice[{-1,1}]];
Pop[index]=Append[Pop[index],
StringReplace[Pop[index][[#]],StringTake[Pop[index][[#]],{locator,StringLength[Pop[index][[#]]]}]->StringTake[dupPop[[#]],{locator,StringLength[dupPop[[#]]]}]]])&,Range[1,Parent]];

Clear[dupPop];

(*mutation // Grab random genesString*)
(*For[i=Parent+1,i≤Parent+10,i++,*)
For[i=1,i≤20,i++,
rate=RandomInteger[{1,3}];
Do[
loc=RandomInteger[{1,7}];
If[StringTake[Pop[index][[i]],{loc}]==".",loc+=1];
gene=RandomInteger[{loc,loc},2];
Pop[index]=ReplacePart[Pop[index],Pop[index][[i]]->StringReplacePart[Pop[index][[i]],ToString[RandomInteger[{0,9}]],gene]]
,{irate,rate}];
];
];

Initialize: create the first generation. Default population size is 20.

Loop:

Selection

Reproduction/Breeding

Replace population

The latter two are executed in a single module - crossbreed

Example:

CreatePop[];
For[cycle=1,cycle≤300,cycle++,
fitnesstest[];
Do[crossbreed[imut],{imut,3}];
];

Results

Clear["Global`*"];
min=10^6;SeedRandom[123];

CreatePop[var_Integer:3,size_:20]:=Module[{},
PopSize=size;nIndex=var;
Do[
Pop[ngen]=N[RandomReal[{-5,5},PopSize],7];
encodePop[ngen],{ngen,nIndex}];
];

encodePop[index_Integer]:=Module[{},
Pop[index]=Table[ToString[Pop[index][[i]]],{i,PopSize}];
];

decodePop[index_Integer]:=ToExpression[Pop[index]];

(*use like value-returning funcs in py*)
fitnessfunc[i1_Integer,i2_Integer,i3_Integer]:=(decodePop[i1])^2+(decodePop[i2])^2+ Cos[3*decodePop[i1]*decodePop[i2]]+(decodePop[i3])^2;

(*Ordering min->max*)
fitnesstest[ParentNo_Integer:10,OffspringNo_Integer:10]:=Module[{},
Parent=ParentNo;
f=fitnessfunc[1,2,3];
Scan[If[f[[#]]≤min,min=f[[#]]]&,Range[PopSize]];
selected=Ordering[f];
count=Take[selected,Parent];
Do[
Pop[ngen]=Part[Pop[ngen],count],{ngen,3}]; (*pop reduced to best 10*)
];

crossbreed[index_Integer,OffspringNo_Integer:10]:=Module[{},
dupPop=RandomSample[Pop[index]];(*best Parent*)
(*Crossbreed*)
Scan[(locator=RandomInteger[{3,5}];
If[StringTake[Pop[index][[#]],{locator}]=="."||StringTake[dupPop[[#]],{locator}]==".",locator+=RandomChoice[{-1,1}]];
Pop[index]=Append[Pop[index],
StringReplace[Pop[index][[#]],StringTake[Pop[index][[#]],{locator,StringLength[Pop[index][[#]]]}]->StringTake[dupPop[[#]],{locator,StringLength[dupPop[[#]]]}]]])&,Range[1,Parent]];

Clear[dupPop];

(*mutation // Grab random genesString*)
(*For[i=Parent+1,i≤Parent+10,i++,*)
For[i=1,i≤20,i++,
rate=RandomInteger[{1,3}];
Do[
loc=RandomInteger[{1,7}];
If[StringTake[Pop[index][[i]],{loc}]==".",loc+=1];
gene=RandomInteger[{loc,loc},2];
Pop[index]=ReplacePart[Pop[index],Pop[index][[i]]->StringReplacePart[Pop[index][[i]],ToString[RandomInteger[{0,9}]],gene]]
,{irate,rate}];
];
];

CreatePop[];
ptsi=Thread[{decodePop[1],decodePop[2],decodePop[3]}];
Print[ptsi];
gptsi=ListPointPlot3D[ptsi,PlotStyle->{Gray},PlotRange->Automatic];
minima=ListPointPlot3D[{{0,0,0}},PlotStyle->{Red}];
Show[gptsi,minima]

p=0;
For[cycle=1,cycle≤100,cycle++,
fitnesstest[];
Do[crossbreed[imut],{imut,3}];
pts[p++]=Thread[{decodePop[1],decodePop[2],decodePop[3]}];
];
Print[f];
ptsf=Thread[{decodePop[1],decodePop[2],decodePop[3]}];
Print[ptsf];
gptsf=ListPointPlot3D[ptsf,PlotStyle->{Green}];
Show[gptsi,gptsf,minima]

Manipulate[ListPointPlot3D[pts[i],PlotRange->{{-5,5},{-5,5},{-5,5}}],{i,1,p-1,1}]