The Population class takes two arguments:

A reproduction cycle executes the following sequence of three genetic operators on a population: select for the selection across all the chromosomes of the population (line 1), +- for crossover of all the chromosomes (line 2), and ^ for the mutation of each chromosome (line 3). Consider the following code:

type Pool[T <: Gene] = mutable.ArrayBuffer[Chromosome[T]]

class Population[T <: Gene](
    limit: Int, val chromosomes: Pool[T]) {    
  def select(score: Chromosome[T]=>Unit, cutOff: Double) //1
  def +- (xOver: Double) //2
  def ^ (mu: Double) //3
  …
}

The limit value specifies the maximum size of the population during optimization. It defines the hard limit or constraints on the population growth.

The chromosome is the second level of containment in the genotype hierarchy. The Chromosome class takes a list of genes as parameter (code). The signature of the crossover and mutation methods, +- and ^, are similar to their implementation in the Population class except for the fact that the crossover and mutable parameters are passed as indices relative to the list of genes and each gene. The section dedicated to the genetic crossover describes the GeneticIndices class:

class Chromosome[T <: Gene](val code: List[T]) {   
  var cost: Double = Random.nextDouble //4
  def +- (that: Chromosome[T], idx: GeneticIndices): 
        (Chromosome[T], Chromosome[T]) 
  def ^ (idx: GeneticIndices): Chromosome[T]
   …
}

The algorithm assigns the (un)fitting score or a cost value to each chromosome to enable the ranking of chromosomes in the population, and ultimately, the selection of the fittest chromosomes (line 4).

Finally, the reproduction process executes the genetic operators on each gene:

class Gene(val id: String, 
    val target: Double, 
    op: Operator)
    (implicit quantize: Quantization, encoding: Encoding){//5
  lazy val bits: BitSet = apply(target, op)

  def apply(value: Double, op: Operator): BitSet //6
  def unapply(bitSet: BitSet): (Double, Operator) //7
   …
  def +- (index: Int, that: Gene): Gene //8
  def ^ (index: Int): Unit //9
  …
}

The Gene class takes three arguments and two implicit parameters, which are as follows:

The apply method encodes a pair of value and operator into a bit set (line 6). An unapply method is the reverse operation of apply. In this case, it decodes a bit set into a pair of value and operator (line 7).

The implementation of the crossover (line 8) and mutation (line 9) operators on a gene is similar to the operations on the container chromosome.

The quantization is implemented as a case class:

case class Quantization(toInt: Double => Int,
     toDouble: Int => Double) {
   def this(R: Int) =  this((x: Double) => 
         (x*R).floor.toInt, (n: Int) => n/R) 
}

The first toInt function converts a real value to an integer and toDouble converts the integer back to a real value. The discretization and inverse functions are encapsulated into a class to reduce the risk of inconsistency between the two opposite conversion functions.

The instantiation of a gene converts the predicate representation into a bit string (bits of the java.util.BitSet type) using the quantization function, Quantization.toInt.

The layout of a gene is defined by the Encoding class as follows:

class Encoding(nValueBits: Int, nOpBits: Int) {
  val rValue = Range(0, nValueBits)  
  val length = nValueBits + nOpBits
  val rOp = Range(nValueBits, length)
}

The Encoding class specifies the bits layout of the gene as a number of bits, nValueBits, to encode the value and the number of bits, nOpBits, to encode the operator. The class defines the rValue range for the value and the rOp range for the operator. The client code has to be supplied to the implicit instance of the Encoding class.

The bit set, bitset, of the gene (encoding) is implemented by using the apply method:

def apply(value: Double, op: Operator): BitSet = {
  val bitset = new BitSet(encoding.length)  
  encoding.rOp foreach(i =>  //10
    if(((op.id>>i) & 0x01)==0x01) bitset.set(i))
  encoding.rValue foreach(i => //11
    if( ((quant.toInt(value)>>i) & 0x01)==0x01) bitset.set(i))
  bitset
}

The bits layout of the gene is created using java.util.BitSet. The op operator is encoded first through its identifier, id (line 10). The value is quantized by invoking the toInt method and then encoded (line 11).

The unapply method decodes the gene from a bit set or bit string to a pair of values and operators. The method uses the quantization instance to cover bits into values and a convert auxiliary function that is described along with its implementation in the source code, accompanying the book (line 12):

def unapply(bits: BitSet): (Double, Operator) = 
  (quant.toDouble(convert(encoding.rValue, bits)), 
   op(convert(encoding.rOp, bits))) //12

The Operator trait defines the signature of any operator. Each domain-specific problem requires a unique set of operations: Boolean, numeric, or string manipulation:

trait Operator {
   def id: Int
   def apply(id: Int): Operator
}

The preceding operator has two methods: an identifier id and an apply method that converts an index to an operator.

We use the +- notation as the implementation of the crossover operator in Scala. There are several options to select pairs of chromosomes for crossover. This implementation ranks the chromosomes by their fitness (or inverse cost) 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:

Pairing of chromosomes within a population prior to crossover

The crossover implementation, +-, selects the parent chromosome candidates for crossover using the pairing scheme described earlier. Consider the following code:

def +- (xOver: Double): Unit = 
  if( size > 1) {
    val mid = size>>1
    val bottom = chromosomes.slice(mid, size) //19
    val gIdx = geneticIndices(xOver)  //20

    val offSprings = chromosomes.take(mid).zip(bottom)
          .map{ case (t, b) => t +- (b, gIdx) }.unzip //21
    chromosomes ++= offSprings._1 ++ offSprings._2 //22
  }

This method splits the population into two subpopulations of equal size (line 19) and applies the Scala zip and unzip methods to generate the set of pairs of offspring chromosomes (line 20). The +- crossover operator is applied to each chromosome pair to produce an array of pairs of offSprings (line 21). Finally, the crossover method adds offspring chromosomes to the existing population (line 22). The xOver crossover value is a probability randomly generated over the interval [config.xOver, 1].

The GeneticIndices case class defines two indices of the bit whenever a crossover or a mutation occurs. The first chOpIdx index is the absolute index of the bit affected by the genetic operation in the chromosome (line 23). The second geneOpIdx index is the index of the bit within the gene subjected to crossover or mutation (line 24):

case class GeneticIndices(val chOpIdx: Int, //23
     val geneOpIdx: Int)  //24

The geneticIndices method computes the relative indices of the crossover bit in the chromosomes and genes:

def geneticIndices(prob: Double): GeneticIndices = {
  var idx = (prob*chromosomeSize).floor.toInt //25
  val chIdx = if(idx == chromosomeSize) chromosomeSize-1 
       else idx //25

  idx = (prob*geneSize).floor.toInt  
  val gIdx = if(idx == geneSize) geneSize-1 else idx //26
  GeneticIndices(chIdx, gIdx)
}

The first chIdx indexer is the index or rank of the gene within the chromosome to be affected by the genetic operator (line 25). The second gIdx indexer is the relative index of the bit within the gene (line 26).

Let's consider a chromosome composed of 2 genes with 63 bits/elements each, as illustrated in the following diagram:

The geneticIndices method computes the following:

First, we need to define the Chromosome class, which takes a list of genes, code, (for genetic code) as the parameter:

val QUANT = 500
class Chromosome[T <: Gene](val code: List[T]) {  
  var cost: Double = QUANT*(1.0 + Random.nextDouble) //27

  def +- (that: Chromosome[T], indices: GeneticIndices): //28
     (Chromosome[T], Chromosome[T]) 
  def ^ (indices: GeneticIndices): Chromosome[T] //29
  def /= (normalizeFactor: Double): Unit =   //30
      cost /= normalizeFactor
  def decode(implicit d: Gene=>T): List[T] =  //31
      code.map( d(_)) 
  …
}

The cost (or unfitness) of a chromosome is initialized as a random value between QUANT and 2*QUANT (line 27). The genetic +- crossover operator generates a pair of two offspring chromosomes (line 28). The genetic ^ mutation operator creates a slightly modified (1 or 2 bits) clone of this chromosome (line 29). The /= method normalizes the cost of the chromosome (line 30). The decode method converts the gene to a logic predicate or rule using an implicit conversion, d, between a gene and its subclass (line 31).

The implementation of the crossover for a pair of chromosomes using hierarchical encoding follows two steps:

Consider the following code:

def +- (that: Chromosome[T], indices: GeneticIndices): 
    (Chromosome[T], Chromosome[T]) = {
  val xoverIdx = indices.chOpIdx //32
  val xGenes =  spliceGene(indices, that.code(xoverIdx)) //33

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

The crossover method computes the index xoverIdx of the bit that defines the crossover in each parent chromosome (line 32). The this.code(xoverIdx) and that.code(xoverIdx) genes are swapped and spliced by the spliceGene method to generate a spliced gene (line 33):

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

The offspring chromosomes are gathered by collating the first xOverIdx genes of the parent chromosome, the crossover gene, and the remaining genes of the other parent (line 34). The method returns the pair of offspring chromosomes (line 35).

The crossover is applied to a gene using the +- method of the Gene class. The exchange of bits between the this and that genes uses the BitSet Java class to rearrange the bits after the permutation:

def +- (that: Gene, indices: GeneticIndices): Gene = {
  val clonedBits = cloneBits(bits) //36

  Range(indices.geneOpIdx, bits.size).foreach(n => 
    if( that.bits.get(n) ) clonedBits.set(n) 
    else clonedBits.clear(n) //37
   )
   val valOp = decode(clonedBits) //38
   new Gene(id, valOp._1, valOp._2)
}

The bits of the gene are cloned (line 36) and then spliced by exchanging their bits along with the indices.geneOpIdx crossover point (line 37). The cloneBits function duplicates a bit string, which is then converted into a (target value, operator) tuple using the decode method (line 38). We omit these two methods because they are not critical to the understanding of the algorithm.

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. We use the ^ notation to define the mutation operator to remind you that the mutation is implemented by flipping one bit:

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

The prob mutation parameter is used to compute the absolute index of the mutating gene, geneticIndices(prob).

The implementation of the ^ mutation operator on a chromosome consists of mutating the gene of the indices.chOpIdx index (line 39) and then updating the list of genes in the chromosome (line 40). The method returns a new chromosome (line 41) that will compete with the original chromosome:

def ^ (indices: GeneticIndices): Chromosome[T] = { //39 
  val mutated = code(indices.chOpIdx) ^ indices 
  val xs = Range(0, code.size).map(i =>
    if(i== indices.chOpIdx) mutated 
    else code(i)).toList //40
  Chromosome[T](xs) //41
}

Finally, the mutation operator flips (XOR) the bit at the indices.geneOpIdx index:

def ^ (indices: GeneticIndices): Gene = { 
  val idx = indices.geneOpIdx
  val clonedBits = cloneBits(bits) //42
  
  clonedBits.flip(idx)  //43
  val valOp = decode(clonedBits)  //44
  new Gene(id, valOp._1, valOp._2) //45
}

The ^ method mutates the cloned bit string, clonedBits, (line 42) by flipping the bit at the indices.geneOpIdx index (line 43). It decodes and converts the mutated bit string by converting it into a (target value, operator) tuple (line 44). The last step creates a new gene from the target-operator tuple (line 45).