Sunday, May 18, 2014

Genetic Algorithms III: Solver

This post describes the third and last section on the implementation of genetic algorithms using Scala: reproduction cycle and solver.

Introduction
In the first post on genetic algorithms, you learned about the key elements of genetic algorithms (Chromosomes, Genes and Population). Genetic Algorithms I: Elements
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).

 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 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 (linew 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).


Financial application
Let's apply the genetic solver to a financial application. The objective is to evaluate the fittest trading strategy. The steps in the execution of the solver (or optimizer) using the genetic algorithm are:
  1. Initialize the execution and genetic algorithm configuration parameters (lines 1-6).
  2. Define a soft limit on the maximum size of the population of chromosomes (line 7)
  3. Specify the quantization or discretization function (line 9)
  4. Define the scoring function for a chromosome if a trading signal as gene (lines 15-17)
  5. Initialize the population of chromosomes as trading strategies (line 20)
  6. (
  7. Initialize the solver (lines 23 & 24)
  8. 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("->")}")
    )


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

Thursday, May 8, 2014

Genetic Algorithms II: Operators

This post describes the implementation of genetic operators such as selection, cross-over and mutation on a population of chromosome using Scala

Introduction
In the first post on genetic algorithms, you learned about the key elements of genetic algorithms.Genetic Algorithms I: Elements
  • Chromosomes
  • Genes
  • Quantization
  • Population
This second part introduces the concept and implementation of genetic operations (cross-over, mutation and selection) on a population of chromosomes. These operators are applied recursively on each chromosome and each of the genes it contains.
The 3rd and final post on genetic algorithms, explores the application of genetic algorithm as a solver or optimizer Genetic Algorithms III: Solver

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

Selection
The first genetic operator of the reproduction cycle is the selection process. The select method of the class Population implements the steps of the selection of the fittest chromosomes in the population in the most efficient manner, as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
def select(score: Chromosome[T] => Unit, cutOff: Double) = {
 val cumul = chromosomes./:(0.0)(
   (s,x) =>{ score(xy); s + xy. unfitness} 
 ) 

 chromosomes foreach( _ /= cumul) 
 val newChromosomes = chromosomes.sortWith(_.unfitness < _.unfitness)
 val cutOffSize = (cutOff*newChromosomes.size).floor.toInt
 val newPopSize = if(limit<cutOffSize) limit else cutOffSize

 chromosomes.clear
 chromosomes ++= newChromosomes.take(newPopSize)
}

The select method computes the cumulative sum of an unfitness value, cumul, for the entire population (lines 2 -3). It normalizes the unfitness of each chromosome (line 6), orders the population by decreasing value (line 7), and applies a soft limit function on population growth, cutOff (line 8). The last step reduces the size of the population to the lowest of the two limits: the hard limit, limit, or the soft limit,cutOffSize (line 9).


Cross-over
There are several options to select pairs of chromosomes for crossover. This implementation ranks the chromosomes by their finess value and then divides the population into two halves. Finally, it pairs the chromosomes of identical rank from each half as illustrated in the following diagram: 



Population cross-over
The crossover implementation, +- , selects the parent chromosome candidates for crossover using the pairing scheme described earlier.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
def +- (xOver: Double): Unit = {
 if( size > 1) {
   val mid = size>>1
   val bottom = chromosomes.slice(mid, size) 
   
   val gIdx = geneticIndices(xOver)
   val offSprings = chromosomes.take(mid)
      .zip(bottom)
      .map(p => p._1 +-(p._2, gIdx))
      .unzip

   chromosomes ++= offSprings._1 ++ offSprings._2
 }
}

The implementation of the cross-over on the population of chromosomes ranked by their unfitness consists of
  • Get the mid point of the list of ranked chromosomes (line 3)
  • Get the least fit half of the chromosome (line 4)
  • Retrieve the position of the bit in the chromosome the cross-over applies (line 6)
  • Retrieve the two offspring by crossing over pairs of chromosomes from each half of the ranked population (lines 7 - 10)
  • Add the two offsprings to the current population (line 12)

Chromosome cross-over
The implementation of the crossover for a pair of chromosomes using hierarchical encoding follows two steps:
  • Find the gene on each chromosome that corresponds to the crossover index, gIdx.chOpIdx, and then swap the remaining genes (line 6)
  • Split and splice the gene crossover at xoverIdx (lines 8 & 12)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def +-(
   that: Chromosome[T], 
   gIdx: GeneticIndices
): (Chromosome[T], Chromosome[T]) = {
 
  val xoverIdx = gIdx.chOpIdx
  val xGenes = spliceGene(gIdx, that.code(xoverIdx) )
 
  val offSprng1 = code.slice(0, xoverIdx) ::: xGenes._1 
   :: that.code.drop(xoverIdx+1)

  val offSprng2 = that.code.slice(0, xoverIdx) ::: xGenes._2 
   :: code.drop(xoverIdx+1)
 
 (Chromosome[T](offSprng1), Chromosome[T](offSprng2)
}

The crossover method computes the index of the bit that defies the crossover xoverIdx in each parent chromosome. The genes code(xoverIdx) and that.code(xoverIdx) are swapped and spliced by the spliceGene method to generate a spliced gene (lines 9 - 13).

The method spliceGene is implemented below.

def spliceGene(gIdx: GeneticIndices, thatCode: T): (T, T) = {
 ((this.code(gIdx.chOpIdx) +- (thatCode, gIdx)),
 (thatCode +- (code(gIdx.chOpIdx), gIdx)) )
}


Gene cross-over
The crossover is applied to a gene through the +- method of the Gene class. The exchange of bits between the two genes this and that uses the BitSet Java class to rearrange the bits after the permutation (lines 4 - 6). The bit string is then decoded to produce the predicate or logical representation of the gene (line 8).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def +- (that: Gene, idx: GeneticIndices): Gene = {
 val clonedBits = cloneBits(bits)

 Range(gIdx.geneOpIdx, bits.size).foreach(n =>
   if( that.bits.get(n) ) clonedBits.set(n)
   else clonedBits.clear(n)
 ) 
 val valOp = decode(clonedBits)

 Gene(id, valOp._1, valOp._2)
}


Mutation
Population mutation
The mutation operator ^ invokes the same operator for all the chromosomes in the population and then adds the mutated chromosomes to the existing population, so that they can compete with the original chromosomes.
The mutation parameter mu is used to compute the absolute index of the mutating gene, geneticIndices(mu). We use the notation ^ to define the mutation operator to remind the reader that the mutation is implemented by flipping one bit:

def ^ (mu: Double): Unit =
 chromosomes ++= chromosomes.map(_ ^ geneticIndices(mu))

Chromosome mutation
The implementation of the mutation operator ^ on a chromosome consists of mutating the gene of the index gIdx.chOpIdx and then updating the list xs of genes in the chromosome. The method returns a new chromosome with this new generic code that is added to the population.

def ^ (gIdx: GeneticIndices): Chromosome[T] = {
  val mutated = code(gIdx.chOpIdx) ^ gIdx

  val xs = Range(0, code.size).map(
    i => if(i==gIdx.chOpIdx) mutated else code(i)
  ).toList

  Chromosome[T](xs)
}


Gene mutation
Finally, the mutation operator flips (XOR) the bit at the index gIdx.geneOpIdx
The ^ method mutates the cloned bit string, clonedBits (line 2) by flipping the bit at the index gIdx.geneOpIdx (line 3). It decodes line 5) and converts the mutated bit string by converting it into a (target value, operator) tuple (line 7). The last step creates a new gene from the target-operator tuple.

1
2
3
4
5
6
7
8
def ^ (gIdx: GeneticIndices): Gene = {
  val clonedBits = cloneBits(bits)
  clonedBits.flip(gIdx.geneOpIdx)

  val valOp = decode(clonedBits)

  Gene(id, valOp._1, valOp._2)
}


This concludes the second part of the implementation of genetic algorithms in Scala, dedicated to genetic operators.


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