Animando o Problema do Vendedor Viajante

Lições Aprendidas da Animação de Modelos

Thomas Nield Blocked Desbloquear Seguir Seguindo 8 de janeiro

A animação pode ser uma ferramenta poderosa. Uma coisa é explicar um tópico complexo em palavras ou mesmo em imagens, mas os visuais em movimento têm uma qualidade incrível para dar vida a ideias abstratas. Isso pode ser especialmente útil em áreas complexas da ciência da computação, como otimização e aprendizado de máquina.

Em outubro de 2018, dei uma palestra na KotlinConf sobre otimização e aprendizado de máquina . Dos vários exemplos, um foi o Problema do Viajante Viajante (também conhecido como "TSP") . Este é um problema tão divertido e fascinante e muitas vezes serve como uma referência para otimização e até mesmo algoritmos de aprendizado de máquina . No entanto, explicar alguns dos algoritmos (como pesquisa local e recozimento simulado) é menos intuitivo sem uma ajuda visual. Portanto, fiz deste um projeto de código aberto usando o JavaFX via TornadoFX .

Um monte de gente na conferência e on-line foram surpreendidos pelos visuais animados, observando como "integrado" e liso parecia. A verdade é que eu hackeei esse aplicativo juntos e o JavaFX foi fundamental para o trabalho pesado. Ele cuidou da animação para que eu pudesse me concentrar no próprio algoritmo. Isto é o que eu quero blog sobre neste artigo.

Você pode assistir ao vídeo passo a passo deste aplicativo (com uma explicação completa do TSP) aqui. Eu recomendo assistir isso antes de ler.

O foco deste post será sobre a animação e como ela foi alcançada. Para uma explicação detalhada sobre o TSP e como ele pode ser resolvido, assista ao vídeo acima.

A estrutura

Para construir isso, vamos primeiro delinear a estrutura de nossa estrutura visual. Vou expressar isso na linguagem Kotlin e aproveitar o JavaFX via TornadoFX. Felizmente, o TornadoFX não oculta ou supressa qualquer funcionalidade do JavaFX, mas o aumenta com expressivas DSLs do Kotlin. Então você pode fazer isso em Java, Kotlin, Scala ou qualquer linguagem da JVM que possa usar o JavaFX.

A primeira coisa que vou fazer na minha aplicação é declarar um Pane e colocar nele um ImageView com uma simples imagem de mapa da Europa. Então, do meu modelo de domínio, importarei meus objetos City e colocarei um Circle vermelho nas coordenadas da tela xey em relação ao mapa da Europa. Por fim, importarei os objetos Edge do meu domínio, onde cada um deles está vinculado a uma City , e vincule cada um deles a uma Line . Cada Edge representa uma conexão entre duas cidades e é inicializado com o ponto inicial e o ponto final sendo a mesma cidade. Portanto, a Line inicializará descansando dentro do Circle como um pequeno ponto. A Line também será vinculada às propriedades startX , endX , startY e endY de seu próprio 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
}
}
}
}

Neste ponto, eu deveria ter algo que processa assim:

Quando animamos, alteraremos as propriedades startX , endX , startY e endY cada Edge. Quando queremos conectar duas cidades, por exemplo, eu posso mudar as endX e endY propriedades para fazer essa linha estende a coordenadas que outra cidade.

Planejando a Animação

Com essa estrutura em vigor, tive que fazer algumas considerações a seguir. Devo animar o algoritmo em tempo real ou enfileirar as animações e torná-las reproduzíveis? Eu queria animar cada coisa que o algoritmo fez ou filtrar o ruído e animar apenas os eventos principais?

Essas decisões podem parecer sem importância à primeira vista, e até me disse: “por que não animar tudo?”. Claro, isso saiu pela culatra rapidamente porque as animações já diminuem o ritmo do algoritmo … e animando eventos improdutivos no algoritmo apenas adicionaram ruído. Isso também tornou a animação incrivelmente longa e chata.

Então, quais são os eventos improdutivos, você pergunta? Bem, o algoritmo funciona fazendo milhares de trocas aleatórias de Edge conforme explicado no vídeo. Quando a troca não melhorou a solução (ou falhou o lançamento da moeda na abordagem Simulated Annealing), eu iria desfazer a troca e colocar tudo de volta. Eu aprendi que era melhor não animar esses eventos porque a maioria das iterações eram falhas de troca, e era melhor para animar sucessos para mostrar o progresso ao invés de cada iteração, incluindo falhas.

Outra adaptação que finalmente fiz foi executar o algoritmo primeiro e depois animar os resultados. Isso teve a vantagem de poder reproduzir os resultados sem ter que executar todo o processo novamente. O utilitário de chave que eu precisava na biblioteca JavaFX é o SequentialTransition , que me permite enfileirar animações e executá-las em ordem (ao invés de todas de uma vez).

Eu posso então ter meu algoritmo adicionar animações ao SequentialTransition e ele pode ser reproduzido mais tarde quando estiver pronto. Eu armazenei cada algoritmo ("GREEDY", "TWO-OPT", "SIMULATED_ANNEALING", etc) como um enumerável, então eu dei a cada um deles sua própria SequentialTransition . Eu também criei algumas funções de extensão convenientes para que eu pudesse usar os operadores += para adicionar animações.

 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)
}

Executando um Traversal de Caminho

No lado do modelo de domínio, eu tenho itens Edge que inicialmente pertencem a uma City . No entanto, o startCity e endCity podem ser mutados e em cada mutação, o Edge tem uma função animateChange() retornando uma linha de Timeline adiada que vai jogar essa mudança.

Mas aqui está a interessante decisão de design que acabei fazendo. Eu criei o edgeStartX , edgeStartY , edgeEndX e edgeEndY para não ser sincronizado com seus respectivos startCity e endCity . Em vez disso, eles são usados apenas para execução de animação. Quando decido animar uma alteração no startCity ou endCity , chamo animateChange() para criar uma Timeline que anima as alterações de coordenadas. Ele pegará o valor atual em cada propriedade do JavaFX que contém os valores de coordenadas e o anima gradualmente aumentando / diminuindo para o valor especificado nesse período de tempo (que é a speed do KeyFrame ).

Note que esta linha de Timeline não é executada, ou seja, cabe ao chamador da função como usar essa animação.

 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)
}
}
}

Essa função específica é usada para expandir um Edge pela primeira vez para outra cidade, o que acontece nos algoritmos GREEDY e RANDOM . Costurá-los juntos em uma sequência resulta em um caminho percorrendo-o para criar uma viagem de ida e volta. Aqui está como a função animateChange() é aproveitada no algoritmo RANDOM . Observe como, quando eu atravesso cada City aleatória, conecto cada um dos pares de Edge consecutivos pela sua startcity e endCity respectivamente. Em seguida, chamo animateChange() para retornar uma Timeline e adicioná-la ao 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)
}
}

Minha interface do usuário pode, então, chamar animationQueue.play() para executar essa alteração quando o botão verde de reprodução for pressionado.

Executando um Swap

Swaps são um pouco mais complicados do que animar uma trajetória de caminho. Quando os algoritmos TWO_OPT ou SIMULATED_ANNEALING selecionam arestas aleatórias e tentam trocar suas cidades (vértices) de alguma forma, algumas vezes falhará e algumas vezes terá sucesso. Uma falha pode acontecer se uma troca interromper o tour e a função reverse() será chamada. Se for bem sucedido, uma função animate() pode ser chamada e retornar uma linha do Timeline que aguarda para ser enfileirada ou executada.

 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
}
}

Isso pode ser usado para os algoritmos TWO_OPT e SIMULATED_ANNEALING . Note que para ambos os algoritmos eu começo limpando o animationQueue , executo o algoritmo RANDOM e pego todas as suas animações, e as adiciono às animações deste algoritmo. Para o TWO_OPT , eu TWO_OPT 2000 trocas aleatórias e adicionei apenas animações que melhoram a distância do tour. Caso contrário, eu chamo reverse() e não animo a troca (como se nunca tivesse acontecido).

 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}")

}
}

Assim que o algoritmo estiver pronto, chame animationQueue.play() na SearchStrategy desejada e observe os fogos de artifício.