Skip to content

Instantly share code, notes, and snippets.

@hugoferreira
Created November 9, 2012 22:45
Show Gist options
  • Save hugoferreira/4048818 to your computer and use it in GitHub Desktop.
Save hugoferreira/4048818 to your computer and use it in GitHub Desktop.
Genetic Algorithms in Scala
import annotation.tailrec
import util.Random
object main extends App {
val target = "as armas e os baroes assinalados"
val genePool = Array('a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' ')
def fitness(src: String): Double = src.zip(target).count { case (s, t) => s == t }
val petri = new GeneticExploration[Char, String](0.01, 500, genePool, cs => new String(cs.toArray), fitness, _.exists(_ == target))
println(petri.evolution(petri.randomPool(target)))
}
class GeneticExploration[Gene, Specimen <% Iterable[Gene]]
(val mutationRate: Double, val population: Int, genePool: Array[Gene],
specimenBuilder: Iterable[Gene] => Specimen,
fitnessF: Specimen => Double,
stopCondition: List[Specimen] => Boolean) {
import Utils._
type Pool = List[Specimen]
type MatePool = List[(Specimen, Double)]
def randomGenes: Stream[Gene] = genePool(Random.nextInt(genePool.length)) #:: randomGenes
def newSpecimen(len: Int): Specimen = specimenBuilder(randomGenes.take(len))
def randomPool(archetype: Specimen): Pool = (1 to population).map(_ => newSpecimen(archetype.size)).toList
def matePool(pool: Pool): MatePool = {
val fitnesses = pool.map(fitnessF).toArray
pool.zip(renormalize(fitnesses))
}
def popReproduction(matePool: MatePool): Pool = (1 to population).par.map(_ => crossover(monteCarlo(matePool), monteCarlo(matePool))).toList
def crossover(a: Specimen, b: Specimen): Specimen = specimenBuilder(a.zip(b).map(gene => if (Random.nextFloat >= 0.5) gene._1 else gene._2))
def mutate(s: Specimen): Specimen = specimenBuilder(s.map(gene => if (mutationRate > Random.nextFloat) randomGenes.head else gene))
@tailrec final def evolution(pool: Pool, generation: Int = 0): (Pool, Int) = {
val newGeneration = popReproduction(matePool(pool))
if (stopCondition(newGeneration)) (newGeneration, generation) else evolution(newGeneration, generation + 1)
}
}
object Utils {
@tailrec final def monteCarlo[A](weightedList: List[(A, Double)]): A = weightedList(Random.nextInt(weightedList.length)) match {
case (s, f) if f > Random.nextFloat => s
case _ => monteCarlo(weightedList)
}
def renormalize(vector: Array[Double]): Array[Double] = {
val sum = vector.sum
vector.map(_ / sum)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment