Genetic Algorithms in Scala

gistfile1.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)
  }
}