aiQUANT

Part 2:  Algorithm Overview

 The Genetic Algorithm is a subset of Evolutionary Algorithms that model biological processes to optimise highly non-linear cost functions.  They require multiple initialisation points on the cost surface hence giving the algorithm a global outlook towards the minimisation or maximisation task.  A few other advantages of these algorithms over traditional local search algorithms include

• Don’t need to compute the derivative of the function
• They can escape local minima
• They can provide a list of suitable solutions and not just one
• Simultaneous searching due to wide sampling of the cost surface
• etc etc

  The figure below shows the main steps in the Genetic Algorithm.

1.  Set Constants

Constants are the parameters that drive the rate and quality of evolution in the Genetic Algorithm.  In out example we have three constants namely

1. Population Size
2. Mutation Probability
3. Mating Probability

There is no fixed rule on how to choose the best values for these constants since they can differ from problem to problem.  The Population Size is the number of organisms or sampling points on the cost surface.  The fittest organisms of this population, which is calculated via a fitness function are allowed to breed via crossover with the premise that they will produce fitter organisms.  Mutation adds random diversity to future generations of the population.  Mating Probability ensures certain genes during crossover are unchanged hence adding more diversity.

2.  Initialise Population

In our example the population is composed of different samplings of the parameters we want to evolve.  A single member organism or chromosome is shown below: 

A gene refers to an individual entity or parameter belonging to the the prediction function.  Recall that our prediction function is:

 Note that the words organism and chromosome are used interchangeably.

3.  Evaluate Fitness

The fitness function determines how fit individual members of the population are with regards to the prediction function.  In our case we shall use a fitness function that compares the predicted price movement with the actial price movement, averaging the absolute value of the difference over a time period of  days.   

I shall explain later the variable .

4.  Sort by Fitness

Each member of the poplation is assigned a fitness value.  If the fitness is above a pre-defined threshold the algorithm is terminates.  Otherwise the algorithm proceeds to inter-breed the population so as to produce fitter organisms.

5.  Select Parents

There are many ways of selecting parents, which for instance can be based on their fitness ranking within the population.  However the actual selection mechanism may be random such as Roulette Selection.  We will use Roulette Selection in our example and I shall talk more about this later on.

6.  Breed

The genes of the selected parents are crossed over with the aim of producing a fitter organism/chromosome.  The Mating Probability ensures that certain genes are unaltered, hence adding diversification to the resulting generation.

7.  Mutate

The downside of cross over during breeding is that values are exchanged between parents but no new ones are introduced.  Mutation allows new genes to show up, hence adding even more diversification to the population.   We are emphasising on diversification because this prevents the algorithm from getting stuck at a local minimum as different members of the population represent a wider range of sampling points on the cost surface.

8.  Remove Twins

The existance of two organisms with identical genomes has limited utility in a Genetic Algorithm.  In our case, we search for two similar organisms and replace the genes of one of the organism with random values.

Bookmark & Share