West London Hack Night - Genetic Algorithm

tsp.scala

import java.awt.{Color, Dimension, Graphics2D}
import javax.swing.JPanel
import scala.annotation.tailrec
import scala.collection.mutable.ListBuffer
import scala.swing.MainFrame
import scala.util.Random

class City (val x : Double, val y : Double, val name : String) {
  def distanceTo (c : City) : Double = {
    Math.sqrt((this.x - c.x) * (this.x - c.x) + (this.y - c.y) * (this.y - c.y))
  }
  override def toString : String = {name + " (" + x + ", " + y + ")"}
}

object Main extends App {

  val target : Double = 0
  val maxPopulation : Int = 1000
  val retain : Int = 20
  val maxNum : Int = 1000
  val chanceOfMutation : Double = 0.1
  val maxGeneSize : Int = 8
  val minGeneSize : Int = 1

  def fitness (x : List[City]) : Double = {
    def fitness(tot : Double, x : List[City]) : Double = x match {
      case h :: Nil  => tot
      case h :: t    => fitness(tot + h.distanceTo(t.head), t)
      case Nil       => 0
    }
    fitness(0, x)
  }

  // When adding mutations, it's important to ensure that no steps can be lost or repeated.
  def mutation (x : List[City], geneSize : Int) : List[City] = {
    @tailrec
    def switchMutate (cur: List[City], x: List[City]): List[City] = x match {
      case h :: Nil => (h :: cur).reverse
      case h :: t   => {
        if (Math.random > chanceOfMutation)
          switchMutate(t.head :: cur, h :: t.tail)
        else
          switchMutate(h :: cur, t)
      }
      case Nil      => throw new NoSuchElementException
    }

    def geneMutate (x : List[City], geneSize : Int) : List[City] = {
      val geneLength = Math.floor(Math.random() * geneSize).toInt + 1
      val geneList = ListBuffer[List[City]]()
      var temp = x
      while (temp.length > 0) {
        geneList.append(temp.take(geneLength))
        temp = temp.drop(geneLength)
      }

      Random.shuffle(geneList.toList).flatten
   }

    // Order of mutation
    geneMutate(x, geneSize)
    switchMutate(List(), x)
  }

  def breed (x : List[City], y: List[City]) : List[City] = {
    throw new NotImplementedError()
  }

  @tailrec
  final def round (start : List[List[City]], num : Int) : List[City] = {
    val generationGeneSize = Math.floor(Math.random() * (maxGeneSize - minGeneSize)).toInt + 1
    var nextGen = start
    for (i <- 1 to maxPopulation) {
      var child = start(Math.floor(Math.random() * start.length).toInt)
      child = mutation(child, generationGeneSize)
      nextGen = child :: nextGen
    }

    nextGen = nextGen.sortBy( fitness )

    if (num >= maxNum) {
      nextGen.head
    } else {
      println("Round " + num + ": " + fitness(nextGen.head))
      round(nextGen.take(retain), (num + 1))
    }
  }

  val cityA  = new City(1150.0, 1760.0,  "A")
  val cityB  = new City(630.0,  1660.0,  "B")
  val cityC  = new City(40.0,   2090.0,  "C")
  val cityD  = new City(750.0,  1100.0,  "D")
  val cityE  = new City(750.0,  2030.0,  "E")
  val cityF  = new City(1030.0, 2070.0,  "F")
  val cityG  = new City(1650.0, 650.0,   "G")
  val cityH  = new City(1490.0, 1630.0,  "H")
  val cityI  = new City(790.0,  2260.0,  "I")
  val cityJ  = new City(710.0,  1310.0,  "J")
  val cityK  = new City(840.0,  550.0,   "K")
  val cityL  = new City(1170.0, 2300.0,  "L")
  val cityM  = new City(970.0,  1340.0,  "M")
  val cityN  = new City(510.0,  700.0,   "N")
  val cityO  = new City(750.0,  900.0,   "O")
  val cityP  = new City(1280.0, 1200.0,  "P")
  val cityQ  = new City(230.0,  590.0,   "Q")
  val cityR  = new City(460.0,  860.0,   "R")
  val cityS  = new City(1040.0, 950.0,   "S")
  val cityT  = new City(590.0,  1390.0,  "T")
  val cityU  = new City(830.0,  1770.0,  "U")
  val cityV  = new City(490.0,  500.0,   "V")
  val cityW  = new City(1840.0, 1240.0,  "W")
  val cityX  = new City(1260.0, 1500.0,  "X")
  val cityY  = new City(1280.0, 790.0,   "Y")
  val cityZ  = new City(490.0,  2130.0,  "Z")
  val cityAA = new City(1460.0, 1420.0,  "AA")
  val cityAB = new City(1260.0, 1910.0,  "AB")
  val cityAC = new City(360.0,  1980.0,  "AC")
  var initRoute = List[City](cityA, cityB, cityC, cityD, cityE, cityF, cityG, cityH, cityI, cityJ,
        cityK, cityL, cityM, cityN, cityO, cityP, cityQ, cityR, cityS, cityT, cityU, cityV, cityW,
        cityX, cityY, cityZ, cityAA, cityAB, cityAC)

  var best = round(List(initRoute), 0)
  println("Result: " + best + " Score: " + fitness(best) + " (Starting score: " + fitness(initRoute))
  val canvasWidth = best.map( a => a.x ).max
  val canvasHeight = best.map( a => a.y ).max
  println("Height: "+ canvasHeight + " :: Width: " + canvasWidth)
}