A Simple Neural Network
KotlinConf 2018 - Mathematical Modeling
Creating a Sudoku Solver from Scratch
Traveling Salesman Problem
Text Categorization w/ Naive Bayes
Monty Hall Problem
Solving World's Hardest Sudoku

## Saturday, October 6, 2018

### Animating the Traveling Salesman Problem with JavaFX

Untitled Document.md

Animation can be a powerful tool. It is one thing to explain a complex topic in words or even in pictures, but visuals in motion have an amazing quality to bring abstract ideas to life. This can be especially helpful in complex areas of computer science like optimization and machine learning.

I recently gave a talk at KotlinConf on optimization and machine learning. Of the several examples, one was the Traveling Salesman Problem (a.k.a. “TSP”). This is such a fun and fascinating problem and it often serves as a benchmark for optimization and even machine learning algorithms. However, explaining some of the algorithms (like k-opt and simulated annealing) is less intuitive without a visual aid. Therefore, I made this an open-source project using JavaFX via TornadoFX.

A lot of folks at the conference and online were surprised by the animated visuals, remarking how “integrated” and slick it looked. The truth is I hacked this application together and JavaFX was instrumental in the heavy lifting. It took care of the animation for me so I could focus on the algorithm itself. This is what I want to blog about in this article.

You can watch the video walkthrough of this application (with a thorough explanation of the TSP) here. I recommend watching this before reading on!

The focus of this blog post will be on the animation and how it was achieved. For an in-depth explanation of the TSP and how it can be solved, please watch the above video.

## The Structure

To build this, let’s first lay out the structure of our visual framework. I am going to express this in the Kotlin language, and leverage JavaFX via TornadoFX. Thankfully, TornadoFX does not hide or supresss any of JavaFX’s functionality, but rather augments it with expressive Kotlin DSL’s. So you can do this in Java, Kotlin, Scala, or any JVM language that can use JavaFX.

The first thing I’m going to do in my application is declare a Pane, and place in it an ImageView with a simple map image of Europe. Then from my domain model, I’ll import my City objects and place a red Circle on the x and y screen coordinates relative to the Europe map. Finally, I’ll import the Edge objects from my domain where each one is tied to a City, and bind each one to a Line. Each Edge represents a connection between two cities, and it is initialized with the start point and end point being the same city. Therefore, the Line will initialize by resting inside the Circle as a little dot. The Line will also be bound to the startX, endX, startY, and endY properties of its owning Edge.

pane {
imageview(Image("europe.png")) {
fitHeight = 1000.0
fitWidth = 1000.0

CitiesAndDistances.cities.forEach { city ->
circle(city.x,city.y,10.0) {
fill = Color.RED
}
}

Model.edges.forEach { edge ->
line {
startXProperty().bind(edge.edgeStartX)
startYProperty().bind(edge.edgeStartY)
endXProperty().bind(edge.edgeEndX)
endYProperty().bind(edge.edgeEndY)
strokeWidth = 3.0
stroke = Color.RED
}
}
}
}


At this point, I should have something that renders like this:

When we animate, we will change each Edge’s startX, endX, startY, and endY properties. When we want to connect two cities, for instance, I can change the endX and endY properties to make that line extend to that other city’s coordinates.

## Planning the Animation

With this structure in place, I did have to make a few considerations next. Should I animate the algorithm in live time or queue up the animations and make them replayable? Did I want to animate every single thing the algorithm did or filter out the noise and animate only the key events?

These decisions may seem unimportant at first glance, and I even told myself “why not animate everything?”. Of course, this backfired quickly because the animations already slow down the algorithm… and animating unproductive events in the algorithm only added noise. This also made the animation incredingly long and boring.

So what are unproductive events, you ask? Well, the algorithm works by doing thousands of random Edge swaps as explained in the video. When the swap did not improve the solution (or it failed the coin flip in the Simulated Annealing approach), I would undo the swap and put everything back. I learned it was best to not animate these events because most iterations were failed swaps, and it was better to animate successes to show progress rather than every iteration including failures.

Another adapatation I ultimtely made is running the algorithm first, and then animating the results. This had the benefit of being able to replay the results without having to run the entire process again. The key utility I needed in the JavaFX library is the SequentialTransition, which allows me to queue up animations and have them played in order (rather than all at once). I can then have my algorithm add animations to the SequentialTransition and it can be played later when it is done.

I stored each algorithm (“GREEDY”, “TWO-OPT”, “SIMULATED_ANNEALING”, etc) as an enumerable so I gave each one its own SequentialTransition. I also created some convenient extension functions so I could use += operators to add animations.

enum class SearchStrategy {

RANDOM {
...
},

GREEDY {
...
},

REMOVE_OVERLAPS {
...
},
TWO_OPT {
...
},

SIMULATED_ANNEALING {
...
}

val animationQueue = SequentialTransition()

abstract fun execute()
}

// extension functions for SequentialTransition
operator fun SequentialTransition.plusAssign(timeline: Timeline) { children += timeline }
fun SequentialTransition.clear() = children.clear()
operator fun SequentialTransition.plusAssign(other: SequentialTransition) { children.addAll(other) }



And of course, I set a speed as a constant that defines how long each animation frame takes.

// animation parameters
var speed = 200.millis



## Executing a Path Traversal

On the domain model side, I have Edgeitems that initially belong to one City. However, the startCity and endCity can be mutated and on each mutation, the Edge has an animateChange() function returning a deferred Timeline that will play that change.

But here is the interesting design decision I ended up doing. I created the edgeStartX, edgeStartY, edgeEndX, and edgeEndY to not be synchronized to their respective startCity and endCity. Rather, these are used purely for animation execution. When I decide to animate a change in the startCity or endCity, I call animateChange() to create a Timeline that animates the coordinate changes. It will take the current value in each JavaFX property holding the coordinate values, and animate it by gradually increasing/decreasing to the specified value in that amount of time (which is the speed of the KeyFrame).

Note though this Timeline does not execute, that is up to the function caller on how to use that animation.

class Edge(city: City) {

val startCityProperty = SimpleObjectProperty(city)
var startCity by startCityProperty

val endCityProperty = SimpleObjectProperty(city)
var endCity by endCityProperty

val distance get() = CitiesAndDistances.distances[CityPair(startCity.id, endCity.id)]?:0.0

// animated properties
val edgeStartX = SimpleDoubleProperty(startCity.x)
val edgeStartY = SimpleDoubleProperty(startCity.y)
val edgeEndX = SimpleDoubleProperty(startCity.x)
val edgeEndY = SimpleDoubleProperty(startCity.y)

fun animateChange() = timeline(play = false) {
keyframe(speed) {
keyvalue(edgeStartX, startCity?.x ?: 0.0)
keyvalue(edgeStartY, startCity?.y ?: 0.0)
keyvalue(edgeEndX, endCity?.x ?: 0.0)
keyvalue(edgeEndY, endCity?.y ?: 0.0)
keyvalue(Model.distanceProperty, Model.totalDistance)
}
}
}


This particular function is used to expand an Edge for the first time to another city, which happens in the GREEDY and RANDOM algorithms. Stiching these together in a sequence results in a path traversing slickly to create a round-trip. Here is how the animateChange() function is leveraged in the RANDOM algorithm. Note how when I traverse to each random City, I connect each consecutive Edge pairs by their startcity and endCity respectively. Then I call animateChange() to return a Timeline and add it to the animationQueue.

RANDOM {
override fun execute() {
animationQueue.clear()

val capturedCities = mutableSetOf<Int>()

val startingEdge = Model.edges.sample()
var edge = startingEdge

while(capturedCities.size < CitiesAndDistances.cities.size) {
capturedCities += edge.startCity.id

val nextRandom = Model.edges.asSequence()
.filter { it.startCity.id !in capturedCities }
.sampleOrNull()?:startingEdge

edge.endCity = nextRandom.startCity
animationQueue += edge.animateChange()
edge = nextRandom
}

Model.bestDistanceProperty.set(Model.totalDistance)
}
}


My UI can then call animationQueue.play() to execute that change when the green play button is pressed.

## Executing a Swap

Swaps are a bit more tricky than animating a path traversal. When TWO_OPT or SIMULATED_ANNEALING algorithms select random edges and try to swap their cities (vertices) somehow, sometimes it will fail and sometimes it will succeed. A failure can happen if a swap breaks the tour, and the reverse() function will be called. If it is successful, an animate() function can be called and return a Timeline that waits to be queued or executed.


class TwoSwap(val city1: City,
val city2: City,
val edge1: Edge,
val edge2: Edge
) {

fun execute() {
edge1.let { sequenceOf(it.startCityProperty, it.endCityProperty) }.first { it.get() == city1 }.set(city2)
edge2.let { sequenceOf(it.startCityProperty, it.endCityProperty) }.first { it.get() == city2 }.set(city1)
}
fun reverse() {
edge1.let { sequenceOf(it.startCityProperty, it.endCityProperty) }.first { it.get() == city2 }.set(city1)
edge2.let { sequenceOf(it.startCityProperty, it.endCityProperty) }.first { it.get() == city1 }.set(city2)
}

fun animate() = timeline(play = false) {
keyframe(speed) {
sequenceOf(edge1,edge2).forEach {
keyvalue(it.edgeStartX, it.startCity?.x ?: 0.0)
keyvalue(it.edgeStartY, it.startCity?.y ?: 0.0)
keyvalue(it.edgeEndX, it.endCity?.x ?: 0.0)
keyvalue(it.edgeEndY, it.endCity?.y ?: 0.0)
}
}
keyframe(1.millis) {
sequenceOf(edge1,edge2).forEach {
keyvalue(Model.distanceProperty, Model.totalDistance)
}
}
}

}

fun attemptTwoSwap(otherEdge: Edge): TwoSwap? {

val e1 = this
val e2 = otherEdge

val startCity1 = startCity
val endCity1 = endCity
val startCity2 = otherEdge.startCity
val endCity2 = otherEdge.endCity

return sequenceOf(
TwoSwap(startCity1, startCity2, e1, e2),
TwoSwap(endCity1, endCity2, e1, e2),

TwoSwap(startCity1, endCity2, e1, e2),
TwoSwap(endCity1, startCity2, e1, e2)

).filter {
it.edge1.startCity !in it.edge2.let { setOf(it.startCity, it.endCity) } &&
it.edge1.endCity !in it.edge2.let { setOf(it.startCity, it.endCity) }
}
.firstOrNull { swap ->
swap.execute()
val result = Model.tourMaintained
if (!result) {
swap.reverse()
}
result
}
}



This can then be used for the TWO_OPT and SIMULATED_ANNEALING algorithms. Note that for both these algorithms I start by cleaning the animationQueue, execute the RANDOM algorithm and take all of its animations, and add them to this algorithm’s animations. For the TWO_OPT, I then attempt 2000 random swaps and only add animations that improve the distance of the tour. Otehrwise I call reverse() and do not animate the swap (as if it never happened).

TWO_OPT {
override fun execute() {
animationQueue.clear()
SearchStrategy.RANDOM.execute()
animationQueue += SearchStrategy.RANDOM.animationQueue

(1..2000).forEach { iteration ->
Model.edges.sampleDistinct(2).toList()
.let { it.first() to it.last() }
.also { (e1,e2) ->

val oldDistance = Model.totalDistance
e1.attemptTwoSwap(e2)?.also {
when {
oldDistance <= Model.totalDistance -> it.reverse()
oldDistance > Model.totalDistance -> animationQueue += it.animate()
}
}
}
}
Model.distanceProperty.set(Model.totalDistance)
Model.bestDistanceProperty.set(Model.totalDistance)

println("TWO-OPT BEST DISTANCE: \${Model.totalDistance}")

}
}


The SIMULATED_ANNEALING, at least on the animation front, is not much different. I essentially add a further condition to animate inferior moves that pass the coin flip. Swaps that do not are again reversed.

// Desmos graph for intuition: https://www.desmos.com/calculator/rpfpfiq7ce
if (weightedCoinFlip(
exp((-(newDistance - bestDistance)) / temperature)
)
) {
animationQueue += swap.animate()

} else {
swap.reverse()
}


As soon as the algorithm is done, call animationQueue.play() on the desired SearchStrategy enumerable and watch the fireworks.

1. Why is Denmark deleted?

1. It was drawn in later but this isn't reflected in the video or all the images. The image had some geographic inaccuracies I had to correct once I saw them.

2. Looking for best TNPSC study materials to prepare for the examination? Make use of our samacheer kalvi books and other study guide to learn from experts. TNPSC One Time Registration

3. I am happy with your article,your website is pretty good. Many articles are very useful for everyone. I am sure your website will grow in the future.
You can take guidance from Quickbooks desktop support to grow your business with the help of add-ons.

4. Unable to receive SMS verification for Gemini? Do you want to fix this issue immediately? If yes, don’t waste your single minute and directly get connected to the professionals by dialing Gemini customer support number. The professionals know all the Gemini Support Number means and methods that easily vanish the errors. They also provide assistance for better understanding. You can approach them as per your needs and requirements and you will never be disappointed with their services.

5. Are you dealing up with stolen password issue in your Blockchain account? Is your password got hacked? There could be various reasons for password problems but the main thing is how to recover them. To nullify all the password errors from roots, you should directly call on Blockchain support number as soon as you encounter such issues. You will be connected Blockchain Support NUmber to the experts team and they will provide ultimate solutions and remedies related to the error that can easily fix up the error without any difficulty.

6. Dealing with the 403 forbidden error in Binance account? Unable to access Binance account due to this error? Such complex errors need proper guidance and support from the specialists as on average person can’t handle such high-level issues. So, you better call on Binance support number and you will get in touch with the professionals immediately. They will fix their issue by delivering high-end assistance to the users. So, enjoy their services at fullest for removing your Binance Support Number errors and doubts. Speak to the experienced team by dialing customer support phone number which is functional throughout the year without any discontinuity.

7. Are you a Gemini user who is facing issues due to glitches and server errors. One such error is appearance of connectivity issue in Gemini. Issues such these can be tackled very easily. Dial Gemini customer support number to find solutions to your problems. Get in touch with a representative via phone call and find the remedies that you are looking for. The experts at Gemini are knowledgeable and skilled. They are always available to help you out. You need to dial Gemini number and get ultimate solutions and ways from the team to end the errors.

8. ATT is one of the greatest remote specialist organizations in the United States. These clients utilize the administrations at the fullest and might confront issues while utilizing the administrations. in the event that you have any sorts of issue identified with ATT remote, at that point you can contact ATT Customer Service Number. We have experts technician remove your anytype issues.
ATT Customer Service Number
ATT Email Support Number
Gmail Customer Service Number
Gmail support number

9. QuickBooks Customer Service is available round the clock to resolve accounting problems. Reach experts at QuickBooks support phone Number and get instant help.

10. We are one of the third party which provide best in class support for all kind of Roku tv setup , installation, updation and much more related issues over phone call and chat across the USA 24*7. We have a dedicated team of professionals who are well certified and experience to handle all kind of Roku tv box issues. We ensure each and every customer to get full satisfaction for his concern. You just need to dial up our roku customer support service number 1-800-382-3046.
Roku Customer Service Number
Roku Support Phone Number
Roku Toll Free Number
Roku Customer Care Number
Roku Helpline Number