Genetic Algorithm for choosing players in a hockey pool...

gistfile1.scala

object Pool {

  abstract sealed class Pos
  case object Forwards extends Pos
  case object Defensemen extends Pos
  case object Goaltenders extends Pos
  val posCounts: Map[Pos, Int] = Map(
    Forwards -> 9,
    Defensemen -> 6,
    Goaltenders -> 2)

  def format(name: String, pts: Int, salary: Double) = {
    def padLeft(str: String, size: Int) = str + (" " * (size - str.size))
    def padRight(str: String, size: Int) = (" " * (size - str.size)) + str
    padLeft(name, 30) + padRight(pts.toString, 10) + "pts\t" + padRight("%4.2f".format(salary) + "M$", 10)
  }

  case class Player(name: String, team: String, pts: Int, salary: Double, pos: Pos) {
    override def toString = format(name, pts, salary)
  }

  object LineUp {

    private def generateRandom = {
      val ps = for {
        (pos, n) ← posCounts
        p ← random(availablePlayers(pos)).take(n)
      } yield p
      new LineUp(ps.toSet)
    }
    def validatedStream(f: ⇒ LineUp) = Stream.continually(f).filter(_.valid)
    def randomStream = validatedStream(generateRandom)
  }

  case class LineUp(players: Set[Player]) {
    import LineUp._

    def playersAt(pos: Pos) = players.filter(_.pos == pos)
    def totalSalary = players.toSeq.map(_.salary).sum
    def totalPoints = players.toSeq.map(_.pts).sum
    def fitness = totalPoints * 10 - totalSalary

    override def toString = "\n====\n" +
      players.toSeq.groupBy(_.pos).map {
        case (pos, ps) ⇒ pos + ":\n" +
          ps.toSeq.sortBy(0 - _.pts).mkString("\n") + "\n" +
          format("Total:", ps.map(_.pts).sum, ps.map(_.salary).sum) +
          "\n----"
      }.mkString("\n") +
      "\n" + format("Grand total:", totalPoints, totalSalary)

    def valid = (totalSalary <= 64.3) &&
      players.groupBy(_.pos).forall {
        case (pos, ps) ⇒ ps.size == posCounts(pos)
      }

    private def mutate: LineUp = {
      val out = random(players).head
      val in = random(availablePlayers(out.pos)).head
      LineUp(players - out + in)
    }
    def mutants = validatedStream(mutate)
  }

  val rnd = new scala.util.Random(System.currentTimeMillis)

  def random[T](xs: TraversableOnce[T]) =
    randomInts(xs.size).map(xs.toIndexedSeq.apply)

  def randomInts(n: Int) = {
    def picks(picked: Set[Int]): Stream[Int] =
      rnd.nextInt(n) match {
        case _ if (picked.size == n)  ⇒ Stream.empty
        case i if (picked contains i) ⇒ picks(picked)
        case i                        ⇒ i #:: picks(picked + i)
      }
    picks(Set[Int]())
  }

  def readCSV(fileName: String, pos: Pos) =
    scala.io.Source.fromFile(fileName)
      .getLines
      .map(_.split("\t"))
      .map(a ⇒ Player(a(0), a(1), a(2).toInt, a(3).toDouble, pos))
      .toIndexedSeq

  val availablePlayers: Map[Pos, IndexedSeq[Player]] = Map(
    Forwards -> readCSV("forwards.csv", Forwards),
    Defensemen -> readCSV("defs.csv", Defensemen),
    Goaltenders -> readCSV("goalies.csv", Goaltenders))

  def tournament(xs: TraversableOnce[LineUp], size: Int): Stream[LineUp] =
    random(xs).take(size).maxBy(_.fitness) #:: tournament(xs, size)

  def GA(nbIter: Int, popSize: Int, tournamentSize: Int) = {
    def loop(iter: Int, pop: Seq[LineUp]): LineUp = {
      val best = pop.maxBy(_.fitness)
      println("\nBest of generation " + iter + best)
      if (iter == nbIter)
        best
      else {
        val newPop = for {
          _ ← Stream.continually()
          x = tournament(pop, tournamentSize).head
          y = (x.mutants take 5) maxBy (_.fitness)
        } yield y
        loop(iter + 1, best +: newPop.take(popSize - 1))
      }
    }
    val initialPop = LineUp.randomStream.take(popSize)
    loop(0, initialPop)
  }
  def main(args: Array[String]) {
    GA(500, 500, 10)
  }
}