Target audience: Advanced
Estimated reading time: 9'
Genetic algorithms fall under the umbrella of optimization algorithms, which are specifically designed to identify the peak or trough of a given function.
In this article, we present the concluding segment of our series on the Scala-based implementation of genetic algorithms, focusing on the reproduction cycle and the solver.
Table of contents
Introduction
In the first post on genetic algorithms, you learned about the key elements of genetic algorithms (Chromosomes, Genes and Population). Genetic Algorithms I: Foundation
This second part introduces the concept and implementation of genetic operations (cross-over, mutation and selection) on a population of chromosomes. Genetic Algorithms II: Operators
This 3rd and final post on genetic algorithms, explores the application of genetic algorithm as a solver or optimizer
Note: For the sake of readability of the implementation of algorithms, all non-essential code such as error checking, comments, exception, validation of class and method arguments, scoping qualifiers or import is omitted.
Reproduction cycle
Let's wrap the reproduction cycle into a Reproduction class that uses the scoring
function score. The class defines a random generator (line 2) used in identifying the cross-over and mutation rates. The key method in the reproduction cycle is mate (line 4).
1
2
3
4
5
6
7
8 | class Reproduction[T <: Gene](score: Chromosome[T] => Unit) { val rand = new Random(System.currentTimeMillis) def mate( population: Population[T], config: GAConfig, cycle: Int): Boolean = {} } |
The reproduction function, mate, implements the sequence of the three
genetic operators as a workflow:
select for the selection of chromosomes from the population (line 8)
+- for the crossover between chromosomes (line 9)
^ for the mutation of the chromosomes (line 10).
select for the selection of chromosomes from the population (line 8)
+- for the crossover between chromosomes (line 9)
^ for the mutation of the chromosomes (line 10).
1
2
3
4
5
6
7
8
9
10
11
12
13 | def mate(
population: Population[T],
config: GAConfig,
cycle: Int): Boolean = population.size match {
case 0 | 1 | 2 => false
case _ => {
population.select(score, config.softLimit(cycle))
population +- (1.0 - Random.nextDouble*config.xover)
population ^ (1.0 - Random.nextDouble*config.mu)
true
}
}
|
This method returns true (line 11) if the size of the population is larger than 2 (line 6). The last
element of the puzzle (reproduction cycle) is the exit condition. There are two options for estimating
that the reproducing cycle is converging:
- Greedy: In this approach, the objective is to evaluate whether the n fittest chromosomes have not changed in the last m reproduction cycles
- Loss (or objective) function: This approach is similar to the convergence criteria for the training of supervised learning.
Solver
The last class GASolver manages the reproduction cycle and evaluates the exit
condition or the convergence criteria:
1
2
3
4
5
6
7
8
9
10 | class GASolver[T <: Gene](
config: GAConfig,
score: Chromosome[T] => Unit
) extends PipeOperator[Population[T], Population[T]] {
var state: GAState = GA_NOT_RUNNING
def solve(in: Population[T]): Population[T]) {}
...
}
|
The class GASolver implements the data transformation, solve which transforms a population to
another one, given a configuration of the genetic algorithm, config (line 2) and a scoring method, score (line 3). The class is also responsible for maintaining and updating the state of the reproduction cycle (line 6).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 | def solve(pop: Population[T]): Population[T] =
if(in.size > 1) {
val reproduction = Reproduction[T](score)
state = GA_RUNNING
Range(0, config.maxCycles).find(n => {
reproduction.mate(pop, config, n) match {
case true => converge(pop, n) != GA_RUNNING
case false => {}
}
}) match {
case Some(n) => pop
case None => {}
}
}
else
pop
|
As mentioned previously, the solve method transforms a population by applying the sequence of genetic operators.
It instantiates a new reproduction cycle (line 3) and set the internal state of the genetic algorithm as RUNING (line 4). The mating of all the chromosomes in the population is implemented iteratively (lines 6 - 10). It exits when either the maximum number of cycles (line 6) is reached or the reproduction converged to a single solution (line 8).
Putting all together
Let's apply the genetic solver to selecting a strategy (i.e. Trading, Marketing,...). The steps in the execution of the solver (or optimizer) using the genetic algorithm are:- Initialize the execution & genetic algorithm configuration parameters (lines 1-6).
- Define a soft limit on the maximum size of the chromosomes population (line 7)
- Specify the quantization or discretization function (line 9)
- Define the scoring function applied to a chromosome if a trading signal as gene (lines 15-17)
- Initialize the population of chromosomes as trading strategies (line 20)
- Initialize the solver (lines 23 & 24)
- execute the genetic algorithm as a iterative sequence of reproduction cycles (line 28)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 | val XOVER = 0.8 // Probability or ratio for cross-over
val MU = 0.4 // Probability or ratio for mutation
val MAX_CYCLES = 400 // Maximum number of iterations during the optimization
val CUTOFF_SLOPE = -0.003 // Slope for the linear soft limit
val CUTOFF_INTERCEPT = 1.003 // Intercept value for the linear soft limit
val R = 1024 // quantization ratio for conversion Int <-> Double
val softLimit = (n: Int) => CUTOFF_SLOPE*n + CUTOFF_INTERCEPT
implicit val digitize = new Discretization(R)
// Define the scoring function for the chromosomes (i.e. Trading
// strategies) as the sum of the score of the genes
// (i.e. trading signals) in this chromosome (i.e strategy)
val scoring = (chr: Chromosome[Signal]) => {
val signals: List[Gene] = chr.code
chr.unfitness = signals.foldLeft(0.0)((sum, s) => sum + s.score)
}
val population = Population[Signal]((strategies.size <<4), strategies)
// Configure, instantiates the GA solver for trading signals
val config = GAConfig(XOVER, MU, MAX_CYCLES, softLimit)
val gaSolver = GASolver[Signal](config, scoring)
// Extract the best population and the fittest chromosomes =
// trading strategies from this final population.
val bestPopulation = gaSolver solve population
bestPopulation.fittest(1)
.getOrElse(ArrayBuffer.empty)
.foreach(
ch => logger.info(s"$name Best strategy: ${ch.symbolic("->")}")
)
|
Thank you for reading this article. For more information ...
References
- Tutorial Darell Whitley - Colorado State University
- Short Tutorial from University of California, Davis
- Genetic Algorithms in Search, Optimization & Machine Learning D. Goldberg Addison-Wesley
- Programming in Scala M. Odersky, L. Spoon, B. Venners - Artima 2010
- Scala for Machine Learning - Patrick Nicolas - Packt Publishing
---------------------------
Patrick Nicolas has over 25 years of experience in software and data engineering, architecture design and end-to-end deployment and support with extensive knowledge in machine learning.
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning" Packt Publishing ISBN 978-1-78712-238-3
He has been director of data engineering at Aideo Technologies since 2017 and he is the author of "Scala for Machine Learning" Packt Publishing ISBN 978-1-78712-238-3
