Genetic Optimizer

Modified on 2016/05/26 20:37 by Eugene — Categorized as: Optimizers

Benefits of Wealth-Lab's Genetic Optimizer

Speeds up optimizations. Optimal parameters are usually discovered in a fraction of time it takes when using exhaustive search.
Works where exhaustive method stumbles: when the number of parameter combinations is too large. It takes only a subset of total runs to find the "Top-10" of values using genetic algorithm.
Aims at the near optimal solution which is likely to be a robust solution. The genetic algorithm does not seek for the absolute optimum which could easily turn an unreliable "peak" value.
Like user-guided optimization, GA focuses on important regions of solution space, having the benefit of a selective search – yet without the need for human interaction.
GA can be used by itself or to pave the way for exhaustive optimization – with a much tighter range of possible optimization values.

In a nutshell

Simply put, genetic algorithms are about solving an optimization problem by evolving a population of chromosomes of candidate solutions toward better solutions. A "chromosome" represents a combination of Strategy Parameters that defines one of the many possible solutions to the optimization problem that the genetic algorithm is trying to solve.

Genetic optimization rules out the poorly performing parameter combinations and keeps the best, letting them proliferate so that each new generation is based upon a hopefully better genotype.

Is Genetic Algorithm any different from Monte Carlo?

Sure. Although both Genetic optimizer and Monte Carlo work fast and use randomness, unlike Monte Carlo, GA does its search purposefully. Genetic algorithm employs selection and recombination, searching for populations with the best optimization criteria.

How does it work?

After installing extension and restarting Wealth-Lab, Genetic Optimizer appears in your list of installed optimizers, next to "Exhaustive" and "Monte Carlo".

The "evolution" happens in cycles, also known as "generations". The first cycle starts from a population of randomly generated chromosomes.
A "fitness" function determines the optimality of a chromosome and allows to rank it against the population. In each generation, the fitness of each chromosome is evaluated.
Based on their fitness, chromosomes are selected from the current population using a Selection method, forming the so called "mating pool". Regardless of chosen Selection method, chromosomes with better fitness have greater chances of making it to mating pool.
Then, a new generation is formed by applying two genetic "operators": Crossover and Mutation, to recombine and mutate the optimal chromosomes, producing a new, hopefully better generation.
This process goes on iteratively upon reaching a satisfactory fitness level for the population, or after producing a number of generations specified as the Generation count (in this case, leaving a chance of not finding a satisfactory solution).

Configuration cheat sheet

1. Specify population and generation count

Population count is the number of chromosomes in each generation. The larger is a population, the better is the diversity (especially in first generations) – ensuring that the algorithm won't hit a local extreme by mischance. Optimization process stops after reaching the number of generations specified as Generation Count.

No formal rule exists for finding the best combination. We recommend starting your optimization using default values for up to 200K runs required. Also, you can use companion Genetic Optimizer Test application to quickly determine optimal population and generation counts. Save the results of an exhaustive optimization of a strategy with similar required runs and perform a genetic search in the Test utility.

2. Choose a fitness function

The metric to optimize is the fitness function – a measure of a chromosome's optimality among the population. To choose one, you can leave the default "Net profit" option or select any performance metric available from Scorecards installed in Wealth-Lab – such as Basic, Extended or Community (if installed). To change a Scorecard, switch to the "Results" tab, select a different Scorecard, click "Begin optimization" and "Cancel optimization", then re-open "Settings".

3. Choose a selection method

Roulette wheel: Imagine a roulette wheel where every sector is a chromosome, and the better its fitness, the larger is the sector. Mating pool is formed among the sectors on which the ball falls after spinning the wheel, until there are enough chromosomes in the population.
Tournament method repeatedly picks a pair of chromosomes on a random basis and selects the one with the best fitness from the pair.

4. Configuring reproduction

Crossover and mutation are genetic operators that produce the next generation of chromosomes, increasing the average fitness by breeding and mixing. Among several available crossover methods, WL Crossover 1 and WL Crossover 2 are probably the best choices for solving optimization tasks:

Flat crossover randomly picks an offspring. Generally, is a suboptimal choice since it tends to stop looking for new solutions too soon.
BLX crossover (aka Blend crossover, alpha=0.5) allows the offspring gene to be located outside the interval.
WL1 and WL2 crossovers are extensions of the BLX method. WL1 aims at procreating offsprings with better fitness, picking a chromosome among just three possible candidates: the smallest and the largest values of the range and the mid-range. WL2 is similar to WL1, but when the appropriate genes of two parent chromosomes are identical, it seeks for a better fitness value by taking an adjacent gene.

Last but not least, you need to configure mutation: this is what lets GA optimizer to maintain diversity from one generation to the next, i.e., keeps them from becoming too similar to each other, and thus continue evolution. There's one method, Simple Mutation, that randomly mutates a drawn gene according to specified Probability setting.

Note: Wealth-Lab's Genetic Optimizer has elitist selection, pushing the elite – Top 3% chromosomes – to the next generation without breeding and mixing. This also protects from loss of good solutions caused by a mutation rate too high.

Analyzing results

The output of Strategy optimized with GA is available as it happens, in the Chromosomes tab and on the Fitness graph.

First, here's some absolutely necessary geek speak that will help you decipher results coming from the Chromosomes and Fitness. Wealth-Lab's genetic optimizer uses the so called "real-coded" genetic algorithm, where each Strategy optimization parameter becomes a "gene" in "chromosome". Let's take the prepackaged "Channel Breakout VT" strategy for example. It has 2 optimizable parameters: Long Channel (ranging from 35 to 100 with step 5), and Short Channel (ranging from 3 to 33 with step 3).

A chromosome takes the form of a series of numbers. For example, the "chromosome" consisting of the two genes, Long Channel = 100 and Short Channel = 18, would be coded the following way: {13;5}. How does a gene take one value or the other? It's a zero-based enumeration, as the following table illustrates:

Short channel	Gene
3	0
6	1
...	...
18	5
...	...
33	10

When running a genetic optimization, chromosomes that existed before can ensue, in a different or even in the same generation. Hence, the number of Runs Required of a genetic optimization is unknown and can not be precomputed by multiplying Population Count by Generation Count. Genetic optimizer saves processing time by not reprocessing duplicate parameter sets, freeing Wealth-Lab from having to run the Strategy redundantly, so the number of actual runs will be equal to Unique Chromosome count on the Chromosomes tab. You may filter out non-unique chromosomes by checking "Show unique only", as well as sort the table by a column.

The Fitness graph illustrates the progress of a genetic optimization. Each step on the red line means a new generation. The first one is generated randomly, and all the rest, as we already know, are the results of selecting, breeding and mutating of chromosomes.

Note: watching the progress of an optimization in real time can slow it down.

References

Known issues

Exception when the system decimal separator is not "." (e.g. ","): System.ArgumentOutOfRangeException: Value '5' is impossible for 'Value'. 'Value' must be between 'Minimum' and 'Maximum'.
- Workaround: In the WealthLabConfig.txt file, change the number on this line to 0,05: Genetic.GA_MutationProbability=0.05