Target audience: Advanced
Estimated reading time: 6'
In the realms of science and engineering, genetic algorithms serve dual purposes: as adaptable algorithms addressing real-world challenges and as computational representations of natural evolutionary mechanisms.
This article stands as the subsequent chapter in our series on genetic algorithms. Within, we detail the Scala-based implementation of genetic operators, encompassing selection, cross-over, and mutation, acting upon a chromosome population.
Table of contents
Introduction
In the first article on genetic algorithms, you learned about the key elements of genetic algorithms.Genetic Algorithms I: Foundation
The 3rd and final post on genetic algorithms, explores the application of genetic algorithm as a solver or optimizer Genetic Algorithms III: Solver
- Chromosomes
- Genes
- Quantization
- Population
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 fitness 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.
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 off-springs 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:
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.
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.
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
- github.com/patnicolas
---------------------------
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
