Traveling Salesman

model.coffee

# AgentBase is Free Software, available under GPL v3 or any later version.
# Original AgentScript code @ 2013, 2014 Owen Densmore and RedfishGroup LLC.
# AgentBase (c) 2014, Wybo Wiersma.

# Traveling Salesman demonstrates a Traveling Sales Person solution
# via a Genetic Algorithm showing the rapid conversion of stochastic
# methods.

u = ABM.util

class ABM.TravelingSalesmanModel extends ABM.Model
  setup: ->
    @agentBreeds ["nodes", "travelers"]
    
    # no optimizations: 44fps
    @refreshPatches = false # for static patches
    @refreshAgents = false # for static agents

    # globals
    @nodeCount = 50
    @travelersCount = 100
    @growPopulation = true
    @useInversion = true
    @bestTourNodes = []
    @bestTourLength = 0
    @bestTourTick = 0
    @stopTickDifference = 500
    
    @animator.setRate 10, true
    
    # defaults
    @patches.setDefault "color", u.color.yellow
    @nodes.setDefault "shape", "circle"
    @nodes.setDefault "color", u.color.red
    @nodes.setDefault "heading", 0 # override promotion to random angle
    @travelers.setDefault "hidden", true
    @links.setDefault "color", u.color.red

    @patches.create()
    @setupNode n for n in @nodes.create @nodeCount
    
    @createTourLinks @nodes #()
    @bestTourLength = @links.reduce ((sum,l) -> sum + l.length()), 0
    
    @travelers.create @travelersCount, (a) => @setupTraveler(a)

  setupNode: (agent) =>
    agent.moveTo @patches.randomPoint()
    while @nodes.neighboring(agent, radius: 2).any()
      agent.moveTo @patches.randomPoint()

  setupTraveler: (agent) =>
    agent.tourNodes = @nodes.clone().shuffle() # ()
    agent.tourLength = @lengthFromNodes agent.tourNodes
    
  step: ->
    console.log @animator.toString() if @animator.ticks % 100 is 0

    for agent in @travelers #()
      @makeTour agent

    @installBestTour()

    if (@animator.ticks - @bestTourTick) is @stopTickDifference
      console.log "Stopping at tick #{@animator.ticks} after no change " +
        "in #{@stopTickDifference} ticks"
      console.log "Best tour: #{@bestTourLength} at tick #{@bestTourTick}"
      @stop()
  
  createTourLinks: (nodeList) ->
    @links.clear()
    @links.create nodeList[0], nodeList.last()
    for i in [1...nodeList.length]
      @links.create nodeList[i], nodeList[i - 1]
    
  lengthFromNodes: (nodeList) ->
    len = nodeList[0].distance(nodeList.last().position)

    for i in [1...nodeList.length]
      len += nodeList[i].distance(nodeList[i - 1].position)

    len

  installBestTour: ->
    while @travelers.length > @travelersCount
      @travelers.max("tourLength").die()

    a = @travelers.min("tourLength")
    if a.tourLength < @bestTourLength
      @reportNewTour a
      @bestTourLength = a.tourLength
      @bestTourNodes = a.tourNodes
      @bestTourTick = @animator.ticks
      @createTourLinks @bestTourNodes

  makeTour: (agent) ->
    if @useInversion
      nlist = @inversionStrategy agent
    else
      nlist = @randomStrategy agent

    len = @lengthFromNodes nlist

    if @growPopulation
      agent.hatch 1, @travelers, (agent) =>
        agent.tourNodes = nlist
        agent.tourLength = len
    else
      if len < a.tourLength
        a.tourNodes = nlist
        a.tourLength = len

  randomStrategy: (a) ->
    a.tourNodes.clone().shuffle()

  inversionStrategy: (a) ->
    ABM.Set.from @newInversion a.tourNodes

  newInversion: (nlist) ->
    len = nlist.length
    i = u.randomInt len - 1
    len = 2 + u.randomInt len - i - 2
    [].concat (nlist.slice 0, i),
              (nlist.slice i, i + len).reverse(),
              (nlist.slice i + len)

  reportNewTour: (agent) ->
    console.log "new best tour at tick #{@animator.ticks}: " +
        "#{agent.tourLength} by traveler #{agent.id}"
    
window.model = new ABM.TravelingSalesmanModel {
  div: "world",
  patchSize: 16,
  mapSize: 28
}
window.model.start()

# Uses the AgentBase library (03-02-2017 release)
# https://github.com/wybo/agentbase/commit/3501302567c018da82601cd858be2ea6d0b9c74d