Created
October 4, 2011 05:11
-
-
Save nicolaspayette/1260949 to your computer and use it in GitHub Desktop.
Genetic Algorithm for choosing players in a hockey pool...
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment