tspga.html

<html>
  <head>
    <title>TSP-GA Model</title>
    <script src="../lib/agentscript.js"></script>
    <script src="../tools/coffee-script.js"></script>
    <script type="text/coffeescript">

    u = ABM.Util # ABM.Util alias
    class MyModel extends ABM.Model
      setup: ->
        @agentBreeds "nodes travelers"

        # no optimizations: 44fps
        @refreshPatches = false # for static patches
        @refreshTurtles = false # for static turtles
        # @patches.usePixels(), setCacheTurtlesHere would not apply
        # @patches.cacheTurtlesHere() # not needed, inRadius used only once

        # both: 57+fps (max)

        # globals
        @nodeCount = 50
        @travelersCount = 100
        @growPopulation = true
        @useInversion = true
        @bestTourNodes = []
        @bestTourLength = 0
        @bestTourTick = 0
        @stopTickDifference = 500

        @anim.setRate 10, true
        # @anim.setRate 60, false

        # defaults
        @patches.setDefault "color", [250, 250, 0]
        # @turtles.setDefault "shape", "circle"
        # @turtles.setDefault "color", [255,0,0]
        # @turtles.setDefault "heading", 0 # override promotion to random angle
        @nodes.setDefault "shape", "circle"
        @nodes.setDefault "color", [255,0,0]
        @nodes.setDefault "heading", 0 # override promotion to random angle
        @travelers.setDefault "hidden", true
        @links.setDefault "color", [255,0,0]

        # p.color = [250, 250, 0] for p in @patches

        # @setupNode a for a in @turtles.create @nodeCount
        @setupNode n for n in @nodes.create @nodeCount

        @createTourLinks @nodes #()
        @bestTourLength = @links.reduce ((sum,l)->sum+l.length()), 0

        # @turtles.create @travelersCount, (a) => @setupTraveler(a)
        @travelers.create @travelersCount, (a) => @setupTraveler(a)

      setupNode: (a) =>
        a.setXY @patches.randomPt()...
        a.setXY @patches.randomPt()... while @nodes.inRadius(a,2).other(a).any()
      setupTraveler: (a) =>
        # a.hidden = true
        # a.breed = "travelers"
        a.tourNodes = @nodes.clone().shuffle() # ()
        a.tourLength = @lengthFromNodes a.tourNodes

      step: ->
        # console.log @anim.toString() if @anim.ticks % 100 is 0
        @makeTour a for a in @travelers #()
        @installBestTour()
        if (@anim.ticks - @bestTourTick) is @stopTickDifference
          console.log "Stopping at tick #{@anim.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()
        @links.create nodeList[i], nodeList[i-1] for i in [1...nodeList.length]
        # @links.setProp "color", [255,0,0]
      lengthFromNodes: (nodeList) ->
        len = nodeList[0].distance(nodeList.last())
        len += nodeList[i].distance(nodeList[i-1]) for i in [1...nodeList.length]
        len
      installBestTour: ->
        # @travelers().maxOneOf("tourLength").die() while @travelers().length>@travelersCount
        # a = @travelers().minOneOf("tourLength")
        @travelers.maxOneOf("tourLength").die() while @travelers.length>@travelersCount
        a = @travelers.minOneOf("tourLength")
        if a.tourLength < @bestTourLength
          @reportNewTour a
          @bestTourLength = a.tourLength
          @bestTourNodes = a.tourNodes
          @bestTourTick = @anim.ticks
          @createTourLinks @bestTourNodes

      makeTour: (a) ->
        nlist = if @useInversion then @inversionStrategy a else @randomStrategy a
        len = @lengthFromNodes nlist
        if @growPopulation
        then a.hatch 1, @travelers, (a) => a.tourNodes=nlist; a.tourLength=len
        else (a.tourNodes=nlist; a.tourLength=len) if len < a.tourLength
      randomStrategy: (a) -> a.tourNodes.clone().shuffle()
      inversionStrategy: (a) -> @asSet @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: (a) ->
        console.log "new best tour at tick #{@anim.ticks}: #{a.tourLength} by traveler #{a.id}"

    # div, patchSize, minX, maxX, minY, maxY, isTorus, hasNeighbors
    #   Defaults: 13, -16, 16, -16, 16, false, true
    model = new MyModel {
      div: "layers",
      size: 16,
      minX: -14,
      maxX: 14,
      minY: -14,
      maxY: 14,
      hasNeighbors: false
    }
    model.debug() # Debug: Put Model vars in global name space
    model.start() # Run model immediately after startup initialization

    </script>
  </head>
  <body>
    <div id="layers"></div>
  </body>
</html>