Traveling Salesman through simulated annealing

SimulatedAnnealing.kt

package annealing

import java.awt.*
import java.awt.geom.Ellipse2D
import javax.swing.JFrame

import java.util.Random
import kotlin.math.pow
import kotlin.math.roundToInt

import kotlin.concurrent.thread


class City(val x: Double, val y: Double)
{
   fun distanceTo(other: City): Double =
            ((this.x - other.x).pow(2) + (this.y - other.y).pow(2)).pow(0.5)

    override
    fun toString(): String = "($x, $y)"
}

class Tour(val cities: List<City>)
{
    val numberOfCities
        get() = this.cities.size

    operator fun get(index: Int) = this.cities[index]

    val distance
        get() = {
            cities.dropLast(1)
                    .zip(cities.drop(1))
                    .map{ (a, b) -> a.distanceTo(b) }
                    .sum()
        }
}

fun acceptanceProbability(old: Double, new: Double, temperature: Double): Double {
    if (new < old) {
        return 1.0
    }
    return Math.exp((old - new) / temperature)
}

fun main(args: Array<String>) {

    val coolingRate = 0.05
    val initialTemperature = 10_000.0

    // Sequence initial, initial*(1-cooling), initial*(1-cooling)^2, ...
    val temperatures = generateSequence(seed = initialTemperature) { current -> current * (1 - coolingRate) }
            .takeWhile { n -> n > 1 }

    // Cities
    var solution = Tour(listOf(
            City(5.0, 5.0),
            City(5.0, 6.0),
            City(6.0, 6.0),
            City(6.0, 7.0),
            City(7.0, 7.0),
            City(3.0, 3.0),
            City(3.0, 4.0),
            City(6.0, 1.0),
            City(5.0, 1.0),
            City(2.0, 8.0)

    ).shuffled())

    println("Initial distance ${solution.distance()}")

    val random = Random()

    val paint = MainPaint(solution)

    Thread.sleep(1000)

    temperatures.forEachIndexed() { index, temperature ->
        val i = random.nextInt(solution.numberOfCities)
        val j = random.nextInt(solution.numberOfCities)

        // Swap two random cities
        val newCities = solution.cities.toMutableList()
        newCities[i] = solution.cities[j]
        newCities[j] = solution.cities[i]

        val newSolution = Tour(newCities)

        val acceptance = acceptanceProbability(
                old = solution.distance(), new = newSolution.distance(), temperature = temperature)

        if (acceptance > random.nextDouble()) {
            solution = newSolution
        }

        // Paint every 100,000,000th update
        if (index.div(100_000_000) == 0) {
            thread { paint.updateTour(solution) }
            println(temperature)
            println(solution.distance())
            println()
            Thread.sleep(10)
        }
    }

    paint.updateTour(solution)
    println(solution.cities)
    println("Solution: ${solution.distance()}")
    Thread.sleep(1000)
}



// Painting classes

class MainPaint(var tour: Tour) : JFrame() {

    var canvas: TourCanvas

    init {
        this.title = "Salesman Tour"
        this.size = Dimension(1200, 1200)
        this.layout = BorderLayout()
        this.canvas = TourCanvas(tour)
        this.add(canvas)
        this.isVisible = true
    }

    fun updateTour(tour: Tour) {
        this.tour = tour
        this.canvas.updateTour(tour)
        this.repaint()
    }

}

class TourCanvas(var tour: Tour) : Canvas() {
    fun TourCanvas() {
        this.setSize(1000, 1000)
    }

    fun updateTour(tour: Tour) {
        this.tour = tour
        this.repaint()
    }

    override fun paint(g: Graphics?) {
        super.paint(g)
        val canvas = g as Graphics2D
        this.tour.cities.forEach { city ->
            val circle = Ellipse2D.Double(
                    city.x.roundToInt() * 100.0,
                    city.y.roundToInt() * 100.0,
                    10.0,
                    10.0)
            canvas.draw(circle)
        }
        this.tour.cities.dropLast(1).zip(this.tour.cities.drop(1)).forEach { (first, second) ->
            canvas.drawLine(
                    first.x.roundToInt() * 100 + 5,
                    first.y.roundToInt() * 100 + 5,
                    second.x.roundToInt() * 100 + 5,
                    second.y.roundToInt() * 100 + 5)
        }
    }

}