Java StarLogo
1.1
`turtle`
breeds [towns travelers indicators]

turtles-own [tdata] ;; catchall list for all data

;; =====================================================================
;; Rather than cluttering the namespace with lots of turtles-own
;; variables and associated implicit routines, we use a trick here; each
;; turtle, no matter what the breed, owns just one data item, a list in
;; which all other data items are embedded.  To get them back out, we
;; use the breed-appropriate set of indices, which are turtle procedures
;; acting as named constants, keeping their names out of the observer
;; procedure namespace nicely as well.
;; =====================================================================

to index-genome          ;; travelers tdata element index
  output 1
end

to index-fitness         ;; travelers tdata element index
  output 2
end

to index-annealing-limit ;; travelers tdata element index
  output 3
end

to index-tabu            ;; travelers tdata element index
  output 4
end

to index-new-genome
  output 5
end

to index-new-fitness
  output 6
end

to index-xcoord          ;; towns tdata element index
  output 1
end

to index-ycoord          ;; towns tdata element index
  output 2
end

to debugging
  output debugging_p
end

to zbitem :zbindex :somelist

  if ( ( :zbindex < 0 ) or ( :zbindex >= ( length :somelist ) ) )
  [
    print se "bad index to zbitem" list :zbindex :somelist
    stop
  ]

  let [ :myitem  ( item ( :zbindex + 1 ) :somelist ) ]

  output :myitem

end

to zbsetitem :zbindex :somelist :someelement

  if ( ( :zbindex < 0 ) or ( :zbindex >= ( length :somelist ) ) )
  [
    print se "bad index to zbsetitem"
             list :zbindex list :somelist :someelement
    stop
  ]

  setitem (:zbindex + 1) :somelist :someelement

end

to tabu-list-maximum-size
;;======================================================================
;; This routine exists to encapsulate, name, and document the implicit
;; magic number which is the number of genome allowed in the tabu list.
;;======================================================================
  output 10  ;; one more than number of heuristics, to start
end

to permutation-count

;;======================================================================
;; This routine exists to encapsulate, name, and document the implicit
;; magic number which is the number of alleles to enter into the
;; "permute" heuristic.  We want to keep it small in general, because it
;; is very expensive to run, but we want it to have a small chance to
;; have a large value, because it is our strongest possible heuristic to
;; get unstuck from a local optimum.
;;======================================================================

  let [:my-permutation-count 3 + abs int ( ( random-gaussian 1.0 ) / 1.5 )]
  if ( :my-permutation-count > ( number-of-towns - 2 ) )
  [ set :my-permutation-count (number-of-towns - 2) ]
  output :my-permutation-count
end


to simulated-annealing-random-chance-of-worstening-succeeds

;;======================================================================
;; This routine exists to encapsulate and document the implicit magic
;; number which is the chance of this random call returning true.
;; The returned result is use to determine what portion of all
;; worstening genome choices are considered further for possible
;; acceptance based on the annealing limit maintained by the next
;; procedure, when the simulated annealing metaheuristic is enabled.
;;======================================================================

  ;; 5% of worstening genomes are checked for possible use in annealing,
  ;; scaled down for number of heuristics in use.

  ifelse ( 500 > random (10000 * heuristics-enabled ) )
  [ output true  ]
  [ output false ]

end

to tournament-size

;;======================================================================
;; This routine exists to encapsulate and document the implicit magic
;; number which is the number of candidates beyond one used for the
;; tournament selection heuristic for picking inver-over or the various
;; crossover heuristic mates.
;;======================================================================

  let [:my-size  ( 2 + int abs random-gaussian 3 ) ]

  if ( :my-size > high-tournament )
  [
    print se "raising high tournament from, to =>" list high-tournament :my-size
    set high-tournament :my-size
  ]

  output :my-size

end

to inver-over-chooses-random-local-city

  ifelse ( 100 > random 10000 )  ;; 1% chance per repetition that the
  [ output true  ]               ;; inver-over algorithm selects a
  [ output false ]               ;; random next city instead of looking
                                 ;; at some other genome to pick a next
                                 ;; city

end

to decrement-annealing-limit :somelimit

;;======================================================================
;; Another trick; rather than stranding the constant magic number 0.99
;; in the code where it is directly needed without explanation as to
;; what it means, we hide it in a well named routine whose only purpose
;; is to encapsulate and identify the use of that one constant in the
;; one multiplication where it is needed.
;; The per-turtle variable modified by this procedure limits the amount
;; of backsliding considered acceptable when simulated annealing is
;; enabled; and the amount decreases over time as determined here.
;;======================================================================

  let [:mylimit :somelimit]

  output 0.99 * :mylimit ;; Decrease the backsliding allowed 1% per use.

end

to worst-possible

;; Return the longest "possible" circuit in the unit square for this
;; number of towns.  The real random circuit is usually much shorter.

  output number-of-towns * sqrt 2

end

to put-genome-in-standard-form :somegenome

;;======================================================================
;; We use this routine to prepare genomes for easy checking for identity
;; by the tabu metaheuristic; once put in standard form, two genomes can
;; be checked for identity by comparing components at the same index
;; locations.  For our purposes, standard form means that the genome
;; starts with the breed towns turtle's numeric id (allele) which mods
;; with the number-of-towns to zero, and that the mod of the allele
;; following the first one is less than the mod of the allele preceding
;; the first one, where the genome is considered as a ring.  What makes
;; this work is that neither reversing the direction of the cycle, nor
;; chosing a different point on it at which to start, changes the
;; fitness, so for our purposes such operations don't modify the genome,
;; only its representation.
;;======================================================================

;; Make a working copy of the input genome.

  let [ :workgenome clone-list :somegenome ]

;; Check first if we're already done.

  if
  (
    ( (item 1 :workgenome ) mod number-of-towns = 0 )
    and
    (
      ( (item 2 :workgenome ) mod number-of-towns )
      <
      ( ( item number-of-towns :workgenome ) mod number-of-towns )
    )
  )
  [output :workgenome]

;; Rotate "town zero" to front, spin on afterwards until done.

  repeat number-of-towns
  [
    ifelse ( ( ( item 1 :workgenome ) mod number-of-towns = 0 ) )
    [
    ]
    [
      let
      [
        :workgenome ( lput ( first :workgenome ) ( butfirst :workgenome ) )
      ]
    ]
  ]

;; If needed, invert the sublist which is the 2nd through last elements
;; of the list to get the required ordering between the mods of the 2nd
;; and last element.

  ifelse
  (
    ( ( item 2 :workgenome ) mod number-of-towns )
    <
    ( ( item number-of-towns :workgenome) mod number-of-towns )
  )
  [
  ]
  [
    let
    [
      :workgenome
      ( ring-invert 2 (number-of-towns - 1) :workgenome )
    ]
  ]

  output :workgenome

end

to clone-list :somelist

;; MAINTAINER NOTE:

;; This simple one level list cloning procedure was added to work around
;; a bug in the 1.2 beta test version of StarLogo, where a "let" copied
;; the one list to another by name, not by value, leaving one list name
;; as an alias of another.  To be a real list clone routine, this one
;; would need to clone lists within lists recursively, but that wasn't
;; needed for this simple demo.

  let [:my-clone-list :somelist]
  let [:new-clone-list empty-list]

  repeat length :my-clone-list
  [
    let [:xfer first :my-clone-list]
    let [:my-clone-list lput :xfer butfirst :my-clone-list]
    let [:new-clone-list lput :xfer :new-clone-list]
  ]

  output :new-clone-list

end

to ring-invert :start-at-element :sublist-length :somelist

  ;; indices at entry are one-based

  if ( :sublist-length < 2 ) [output :somelist]

  let [ :ring-invert-list clone-list :somelist ]
  let [ :ring-invert-list-length ( length :ring-invert-list ) ]

  let
  [ :swap-from-index
    ;; shift to zero based index
    ( ( :start-at-element - 1 ) mod :ring-invert-list-length ) 
  ]
  let
  [ :swap-to-index
    (  ( :swap-from-index + :sublist-length - 1 ) mod :ring-invert-list-length ) 
  ]

  repeat int ( :sublist-length / 2 )
  [
    let [ :temp-element zbitem :swap-to-index :ring-invert-list ]
    zbsetitem :swap-to-index :ring-invert-list zbitem :swap-from-index :ring-invert-list
    zbsetitem :swap-from-index :ring-invert-list :temp-element
    set :swap-to-index ( ( :swap-to-index - 1 ) mod :ring-invert-list-length )
    set :swap-from-index ( ( :swap-from-index + 1) mod :ring-invert-list-length )
  ]

  output :ring-invert-list

end

to town-center-xcoord

;; By naming another run time constant, the name of the x-coordinate of
;; the center of the home of the turtles of breed towns, and hiding it
;; in a routine, we can do a parameterization that lets the patch area
;; be of aspect either 1::2 or 2::1 without lots of code changes
;; anywhere.  Notice a useful programming style here, too.  Because the
;; next, parallel routine needs to use "0 -" to do a computation, we
;; make the parallelism here more obvious by including an entirely
;; gratuitious "0 +".  This style turns out to repay the effort it
;; requires handsomely when code maintenance time on someone else's code
;; comes around.

  ifelse screen-height >= screen-width
  [ output ( 0 ) ]
  [ output ( 0 + ( screen-half-width / 2 ) ) ]

end

to town-center-ycoord

;; Same trick as above, but for the y-coordinate.

  ifelse screen-height >= screen-width
  [ output ( 0 - ( screen-half-height / 2 ) ) ]
  [ output ( 0 ) ]

end

to town-xscale

;; Here again the value returned is a run time constant, but using a
;; procedure to encapsulate it gives it a name and improves
;; maintainability also by hiding a choice that is always constant for a
;; particular run but might not be if the user chooses to change the
;; patch area aspect ratio.

  ifelse screen-height >= screen-width
  [ output screen-width ]
  [ output screen-half-width ]

end

to town-yscale

;; Same as above.

  ifelse screen-height >= screen-width
  [ output screen-half-height ]
  [ output screen-height ]

end

to travel-center-xcoord

;; Same tricks again, but for the other half of the patch area, what was
;; once a traveler area but is now a histogram area, the traveler and
;; town areas having been consolidated.

  ifelse screen-height >= screen-width
  [ output ( 0 ) ]
  [ output ( 0 - ( screen-half-width / 2 ) ) ]

end

to travel-center-ycoord

  ifelse screen-height >= screen-width
  [ output ( 0 + ( screen-half-height / 2 ) ) ]
  [ output ( 0 ) ]

end

to travel-xscale

  ifelse screen-height >= screen-width
  [ output screen-width ]
  [ output screen-half-width ]

end

to travel-yscale

  ifelse screen-height >= screen-width
  [ output screen-half-height ]
  [ output screen-height ]

end

to empty-list

;; For some reason StarLogo doesn't have an empty list notation like
;; other Logos, so we need a routine that produces an empty list, a
;; uniquely useful entity in list oriented programming languages.

;; Make a list, then gut it and output the wrapper with no contents.

  let [:my-empty-list list 0 1]
  let [:my-empty-list butfirst :my-empty-list]
  let [:my-empty-list butfirst :my-empty-list]
  output :my-empty-list

end

to append-zeros :somelist :somecount

;; To make the item and setitem commands work on the tdata lists, those
;; lists must have the correct number of elements _before_ real data is
;; inserted.  We accomplish that with this routine by appending zeros to
;; the initial tdata empty list, a frequently used capability during the
;; setup stages of this demo.

  let [:mylist :somelist]
  let [:mycount :somecount]
  repeat :mycount [ let [ :mylist lput 0 :mylist ] ]
  output :mylist

end

to randomize-genome :someid

;; Use one of the known-to-be-fair ways to create a random permutation;
;; walk the list, swapping each element one by one with some other
;; randomly chosen element, possibly itself.  Ideally, and probably
;; eventually, the randomize-list part of this functionality should be
;; separated from the part that extracts the genome and then reinserts
;; it, but the StarLogo 1.2beta release I am in the process of testing
;; by developing this demo has an artificially low limit on the number
;; of "lines" (procedures, interface widgets, and perhaps some other
;; stuff too) that can exist in a single procedure, so we leave
;; refactoring for a more programmer-friendly release of the underlying
;; StarLogo tool.

;; Extract the genome into a separate local list.

  let [:myid :someid]
  let [:mytdata tdata-of :myid]
  let [:mygenome item index-genome :mytdata]

;; Randomize that list.

  let [:from-genome-index 0]

  repeat number-of-towns
  [
    let [:towntemp zbitem :from-genome-index :mygenome]
    let [:to-genome-index (random number-of-towns) ]
    zbsetitem :from-genome-index :mygenome zbitem :to-genome-index :mygenome
    zbsetitem :to-genome-index :mygenome :towntemp
    let [ :from-genome-index ( :from-genome-index + 1) ]
  ]

;; Put the genome list back, being careful not to invoke compiler
;; weaknesses in the process.

  setitem index-genome :mytdata :mygenome
  settdata-of :myid :mytdata

end
to more-fit-of :first-genome :second-genome

  let [ :my-first-genome clone-list :first-genome ]
  let [ :my-second-genome clone-list :second-genome ]

  let [ :first-fitness ( genome-fitness :my-first-genome ) ]

  let [ :second-fitness ( genome-fitness :my-second-genome ) ]

  ifelse [ :first-fitness < :second-fitness ]
  [
    output :first-genome
  ]

  [
    output :second-genome
  ]

end

to genome-fitness :somegenome

;; The "fitness" of a genome in this demo is the town to town distance
;; associated with following that list.  The list is treated as a ring
;; so that the circuit followed is a closed one.

;; This is superstitious bug avoidance; other Logo implementations make
;; the input parameter name a normal local variable without trouble, but
;; StarLogo has some historical problems in that area, so we don't poke
;; sticks into the beast's cage quite yet, we make our own local copy,
;; instead.

  let [:mygenome clone-list :somegenome]


;; We _first_ compute the ring-closing distance from the last town
;; element of the list to the first, since it takes special processing
;; and we have to initialize :myfitness with some value in any case.

  let [:from-town last :mygenome]

  let [:to-town first :mygenome]

  let [:myfitness town-distance :from-town :to-town]


;; Now we add the remaining distances in a less obscure manner.

  let [:which-item 0]

  repeat (number-of-towns - 1)
  [

    set :from-town zbitem :which-item :mygenome

    set :which-item ( :which-item + 1 )

    set :to-town zbitem :which-item :mygenome

    set :myfitness ( :myfitness + town-distance :from-town :to-town )

  ]

  output :myfitness

end

to fitness :someid

;; If all we know is the traveler's turtle id, we use it here to extract
;; the genome from that traveler's tdata before calling the
;; genome-fitness routine that does the bulk of the computation work.
;; This refactoring split allows the genome-fitness routine to be used
;; independently many other places in the code where a raw genome list
;; without an associated traveler who owns it is the item being
;; processed.

  let [:myid :someid]
  let [:mytdata tdata-of :myid]
  let [:mygenome item index-genome :mytdata ]

  output genome-fitness :mygenome

end

to town-distance :from-town :to-town

;; The inputs are numbers corresponding to turtle ids.  Suck out the
;; coordinates from the turtles of breed towns who own them, then use
;; them to compute and return a usual Cartesian distance.  While this is
;; more work than keeping the coordinates directly in the genome would
;; have been, it pays for itself by meeting other guidance from
;; programming wisdom: a) don't store data redundantly, you are just
;; inviting the multiple copies to go out of synch, and b) data can get
;; huge, use code to pull it out, space usually costs more than time.

  let [ :from-xcoord item index-xcoord tdata-of :from-town ]
  let [ :from-ycoord item index-ycoord tdata-of :from-town ]

  let [ :to-xcoord item index-xcoord tdata-of :to-town ]
  let [ :to-ycoord item index-ycoord tdata-of :to-town ]

  let [ :xdist ( :to-xcoord - :from-xcoord ) ]
  let [ :ydist ( :to-ycoord - :from-ycoord ) ]

  output sqrt ( ( :xdist * :xdist ) + ( :ydist *  :ydist ) )

end

to reposition-self

;; This routine puts the breed-travelers turtles in a rough circle
;; around a center point in one half of the patch area, with angular
;; location representing the turtle's turtle id number, radial distance
;; representing the turtle's current fitness.  This "circular histogram"
;; is a wonderful invention, I wish I could credit the original
;; conceiver.  It represents the histogram data very compactly, since
;; turtles with similar angles from the origin but different radii are
;; visually distinct, and it gives the user a warm fuzzy feeling about
;; the progress of a run in two ways: a) the circle radius shrinks as
;; the overall fitness improves, and b) the circle squeezes down from an
;; annulus to a real circle as the agreement among the turtles as to
;; their fitness improves.  It is worth noting that turtles whose
;; genomes have roughly the same fitness may draw wildly different
;; circuits, as will be evident after running the demo lots of times.

    let [:myid who]

;; Cut down visual artifacts by working mostly in the dark.

    setc black

;; Move self to the center of the histogram.

    setxy travel-center-xcoord travel-center-ycoord

;; Mark the patch at the center of the histogram circle for a visual
;; reference point for the user.

    stamp turquoise

;; Point self in a direction unique to each turtle; this demonstrates
;; the trick of using "mod" to bring turtle numbers back to the range 0
;; to n-1, useful lots of places.

    seth (360 / number-of-travelers) * ( :myid mod number-of-travelers )

;; Move self forward a scaled amount proportional to current fitness and
;; the plotting scale of the patch area compared to a unit square, and
;; inversely proportional to the worst possible fitness, where each edge
;; in the circuit is as long as the diagonal of the containing unit
;; square.  There is an implicit assumption here that the two display
;; areas are each square; no attempt is made to correct for other aspect
;; ratios.

    fd ( ( travel-xscale * (item index-new-fitness tdata ) ) / worst-possible )

;; Make self visible now that the assigned position in the histogram
;; circle has been attained.

    setc red

end

to draw-self :someparameter

  if ( breed = travelers )
  [
;; And you thought those circular histogram turtles were just sitting
;; there barely moving?  Anything but; they have a life of dashing and
;; daring as well, since each who discovers a new circuit with best ever
;; fitness is responsible for drawing it in in the circuit display half
;; of the patch area as well.  It just normally happens and the turtle
;; flashes back to its spot quicker than the eye can follow.

;; Turn the current turtle's "who" value, a special kind of entity, into
;; a more useful plain number.

    let [:myid who]

;; Probably just more superstition, but extract the genome from our own
;; tdata by talking to ourself in the third person as it were.

    let [:mygenome item index-new-genome tdata-of :myid]

;; We are sitting at our assigned spot in the histogram circle when this
;; routine gets called from an ask-turtle on the observer side, so do
;; what is needed to change our personality for the new task: pick up
;; the pen, change color, dart over to the set of turtles holding still
;; in their places to represent the sites of the towns, put down the
;; pen, draw our circuit threading though their locations, pick up the
;; pen, and return to our histogram duties.

    pu

    setc :someparameter

;; Notice how much this looks like the genome-fitness routine; we are
;; doing the same thing, walking the list of towns in our genome, just
;; visually instead of numerically.

    let [:from-town last :mygenome]
    let [:from-rawx item index-xcoord tdata-of :from-town]
    let [:from-rawy item index-ycoord tdata-of :from-town]
    let [:from-xcoord ( town-center-xcoord + ( town-xscale * :from-rawx) ) ]
    let [:from-ycoord ( town-center-ycoord + ( town-yscale * :from-rawy) ) ]

;; As when doing the fitness computation, we start at the town at the
;; end of the genome list, and draw our first edge to the first town on
;; the list, so that when we draw from the next to last to the last town
;; on the list, we will be closing the circuit.

    setxy :from-xcoord :from-ycoord

;; Let's draw!

    pd

;; Set this one too low, then bump _before_ using, inside the repeat
;; loop.

    let [:town-index 0]

    repeat number-of-towns
    [

;; Bump the index.

      let [:town-index :town-index + 1]

;; Extract and offset and scale the corresponding towns x and y
;; coordinates.

      let [:to-town item :town-index :mygenome]
      let [:to-rawx item index-xcoord tdata-of :to-town]
      let [:to-rawy item index-ycoord tdata-of :to-town]
      let [:to-xcoord ( town-center-xcoord + ( town-xscale * :to-rawx) ) ]
      let [:to-ycoord ( town-center-ycoord + ( town-yscale * :to-rawy) ) ]

;; Draw the line to that location; another weakness of StarLogo compared
;; to other Logo implementations is that setxy doesn't draw even with
;; the pen down, so we use clunkier tools instead.

      seth  towards-nowrap :to-xcoord :to-ycoord
      fd distance-nowrap   :to-xcoord :to-ycoord

    ]

    pu
  ]

  if ( breed = indicators )
  [
    let [:sqtwo (sqrt 2)]

    pu
    setxy (town-center-xcoord - (0.5 * town-xscale)) + 1
          (town-center-ycoord - (0.5 * town-yscale))
    setc black
    seth 0
    pd
    fd :sqtwo * town-yscale
    pu
    setxy (town-center-xcoord - (0.5 * town-xscale)) + 1
          (town-center-ycoord - (0.5 * town-yscale))
    setc yellow
    pd
    ifelse ( :someparameter > :sqtwo )
    [
      fd ( :sqtwo * town-yscale )
      setc cyan
      bk ( ( :someparameter - :sqtwo ) * town-yscale )
    ]
    [
      fd ( :someparameter * town-yscale )
    ]
    pu
    setc yellow
    setxy (town-center-xcoord - (0.5 * town-xscale)) + 1
          (town-center-ycoord - (0.5 * town-yscale))
  ]

end

;; =====================================================================
;; Funny to get this far into the code before seeing where things start
;; for the turtles, but the code is tree shaped, and there just isn't
;; any nice and also intuitive linear way to lay it out that I have ever
;; found.
;; =====================================================================

to init-self

;; All turtle's tdata list start out empty, here is where that happens.

  settdata empty-list

;; Handle each breed as a special case.

  if breed = towns      [ init-town      ]
  if breed = travelers  [ init-traveler  ]
  if breed = indicators [ init-indicator ]

end

to run-self

;; This tiny routine is the primary target of the observer side "go"
;; loop that runs forever.  Because StarLogo synchronizes events at the
;; end of each ask-turtles or similar command, that "go" loop calls more
;; than one turtle procedure to achieve such synchronization.

  if breed = towns      [ run-town      ]
  if breed = travelers  [ run-traveler  ]

end

to init-indicator
  setc yellow
  setxy (town-center-xcoord - (0.5 * town-xscale)) + 1
        (town-center-ycoord - (0.5 * town-yscale))
  settdata empty-list
end

to init-town

;; Add the long above mentioned place-holder zero so that we can access
;; tdata with item and setitem commands.

  settdata append-zeros tdata 2

;; Assign each town a position in a centered unit square, with x and y
;; coordinates between -0.45 and +0.45, to allow for a neat empty border
;; around the towns in the target display area, and thus to avoid
;; display artifacts.

  setitem index-xcoord tdata  (( 0 - 450000 + random 900000) / 1000000) 
  setitem index-ycoord tdata  (( 0 - 450000 + random 900000) / 1000000)

;; Towns display themselves in white, and sit at their assigned location
;; in the town and circuit display area for the rest of the demo, but
;; they aren't at all idle intellectually, they are storing and
;; returning their coordinates in response to incessant queries.

  setc white

  setx town-center-xcoord + ( town-xscale * item index-xcoord tdata )
  sety town-center-ycoord + ( town-yscale * item index-ycoord tdata )
 
end

to init-traveler

  let [:myid who]

;; Put in the needed place-holder zeros for item and setitem command
;; use.

  settdata append-zeros         tdata 6

;; Put an ordered list of towns into the genome element.

  setitem index-genome          tdata list-of-towns

;; Disorder it.

  randomize-genome who

;; Pull it out and put it back in standard form.

  setitem index-genome         tdata
    ( put-genome-in-standard-form
      item index-genome        tdata )

;; Put a copy of it into the new genome slot.

  setitem index-new-genome     tdata ( copy-list item index-genome tdata )

;; Measure and store the fitness of the initial towns permutation.

  setitem index-fitness         tdata fitness who

;; Put a copy into the new fitness slot.

  setitem index-new-fitness     tdata ( item index-fitness tdata )

;; Store an initial limit for the simulated annealing routine; at worst,
;; an annealing step can worsten the fitness by adding two unit square
;; diagonals to the length of the circuit, and the reality is always
;; less than that, but any slop beyond that amount is a waste of time.

  setitem index-annealing-limit tdata (2 * sqrt 2)

;; Put ourselves in the histogram circle picture for the first time.

;; Store an ordered genome list as the first tabu genome in the tabu
;; genome list

  setitem index-tabu            tdata butlast list list-of-towns 0

  reposition-self

end

to run-town

;; Towns are the more boring breed of turtle, very good at sitting, not
;; so good at moving, but we'll let them go out and make crop circles to
;; make themselves more visible.

  seth 0
  pd
  fd 1
  rt 90
  fd 1
  rt 90
  fd 1
  fd 1
  rt 90
  fd 1
  fd 1
  rt 90
  fd 1
  fd 1
  rt 90
  fd 1
  rt 90
  fd 1
  pu
  seth 0
end

to run-traveler

;; Our game plan here is to extract our own tdata genome element into a
;; work copy, pass that work copy through a variety of optional routines
;; controlled by interface push-buttons either before entering or while
;; in the execute loop, and then replace our tdata genome element by the
;; resulting work genome if there was either an improvement or if
;; annealing was enabled and there was a worstening that passed the
;; annealing-limits filter and the annealing worstening random chance
;; filter.

  let [ :old-genome  item index-genome  tdata ]
  let [ :old-fitness item index-fitness tdata ]

  let [ :new-genfit list ( copy-list :old-genome ) :old-fitness ]
  let [ :trial-genfit empty-list ]
  let [ :trial-genome empty-list ]
  let [ :trial-fitness worst-possible ]
  let [ :tabu-genome-list ( item index-tabu tdata ) ]

  ;; if want_debugging_p [ set debugging_p true ]

  if swap_p
  [
    if debugging [ print "entering swap" ]

    set :trial-genfit swap                      :new-genfit
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]

    if debugging [ print "exiting swap" ]
  ]

  if invert_p
  [
    if debugging [ print "entering invert" ]

    set :trial-genfit invert                    :new-genfit
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]

    if debugging [ print "exiting invert" ]
  ]

  if inver_over_p
  [
    if debugging [ print "entering inver_over" ]

    set :trial-genfit inver-over                :new-genfit
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]
    if debugging [ print "exiting inver_over" ]
  ]

  if permute_p
  [
    if debugging [ print "entering permute" ]

    set :trial-genfit permute                   :new-genfit
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]
    if debugging [ print "exiting permute" ]
  ]

  if move_sublist_p
  [
    if debugging [ print "entering move_sublist" ]

    set :trial-genfit move_sublist              :new-genfit
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]

    if debugging [ print "exiting move_sublist" ]
  ]

  if crossover_ordered_p
  [
    if debugging [ print "entering crossover_ordered" ]

    set :trial-genfit crossover_ordered         :new-genfit tournament
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]

    if debugging [ print "exiting crossover_ordered" ]
  ]

  if crossover_partial_match_p
  [
    if debugging [ print "entering crossover_partial_match" ]

    set :trial-genfit crossover_partial_match   :new-genfit tournament
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]

    if debugging [ print "exiting crossover_partial_match" ]
  ]

  if crossover_cyclic_p
  [
    if debugging [ print "entering crossover_cyclic" ]

    set :trial-genfit crossover_cyclic          :new-genfit tournament
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]

    if debugging [ print "exiting crossover_cyclic" ]
  ]

  if crossover_edge_preserving_p
  [
    if debugging [ print "entering crossover_edge_preserving" ]

    set :trial-genfit crossover_edge_preserving :new-genfit tournament
    set :trial-genome put-genome-in-standard-form first :trial-genfit
    set :trial-fitness genome-fitness :trial-genome
    set :trial-genfit list :trial-genome :trial-fitness
    set :trial-genfit tabu    :tabu-genome-list :new-genfit :trial-genfit
    set :new-genfit   anneal                    :new-genfit :trial-genfit

    if ( not same-genome ( first :new-genfit ) ( last :tabu-genome-list ) )
    [
      set :tabu-genome-list
      ( update-tabu-list ( first :new-genfit ) :tabu-genome-list )
    ]

    if debugging [ print "exiting crossover_edge_preserving" ]
  ]

  setitem index-tabu    tdata :tabu-genome-list
  setitem index-new-genome  tdata ( first :new-genfit )
  setitem index-new-fitness tdata ( last  :new-genfit )

  reposition-self

  ;; if want_debugging_p [ set debugging_p false ]

end

;; FIXME.  Docs missing from here down.

to swap :some-genfit

  if not swap_p [output :some-genfit]

;; Implement the "swap?" toggle and associated heuristic.

  let [ :my-genome copy-list first :some-genfit ]

;; Attempt improvement by swapping two towns in genome.
;; We don't care enough about swapping a town with itself
;; to take precautions against it.

  let [ :from-index 1 + random number-of-towns ]
  let [ :to-index   1 + random number-of-towns ]

  let [:temptown item :from-index :my-genome]

  setitem :from-index :my-genome item :to-index :my-genome

  setitem :to-index :my-genome :temptown

  output list :my-genome worst-possible

end

to invert :some-genfit

  if not invert_p [ output :some-genfit ]

  let [ :my-genome copy-list first :some-genfit ]

  let [:invert-from ( 1 + ( random number-of-towns ) ) ]
  let [:invert-for  ( 2 + random (number-of-towns - 3) ) ]

  set :my-genome ring-invert :invert-from :invert-for :my-genome

  output list :my-genome worst-possible

end

to inver-over :some-genfit

  if not inver_over_p [ output :some-genfit ]

  if ( number-of-travelers < 2 ) [ output :some-genfit ]

  let [ :current-city-index (1 + random number-of-towns ) ]
  let [ :my-genome copy-list first :some-genfit ]
  let [ :current-city ( item :current-city-index :my-genome ) ]

  loop
  [

    ifelse inver-over-chooses-random-local-city
    [
      let [ :city-prime-index
      ( 1 + ( ( ( 1 + random ( number-of-towns  - 1 ) )
      + :current-city-index ) mod number-of-towns ) ) ]
      let [ :city-prime ( item :city-prime-index :my-genome ) ]
    ]
    [
      let [ :random-traveler traveler-not-me who ]
      let [ :his-genome  ( item index-genome ( tdata-of :random-traveler ) ) ]
      let [ :his-current-city-index ( position :current-city :his-genome ) ]
      let [ :his-next-city-index
        ( 1 + ( :his-current-city-index mod number-of-towns ) ) ]
      let [ :city-prime ( item :his-next-city-index :his-genome ) ]
      let [ :city-prime-index position :city-prime :my-genome ]
    ]

    ifelse
    (
      ( ( :current-city-index + 1 ) = :city-prime-index )
      or
      ( ( :current-city-index + 1 - number-of-towns ) = :city-prime-index )
      or
      ( ( :current-city-index - 1 ) = :city-prime-index )
      or
      ( ( :current-city-index - 1 + number-of-towns ) = :city-prime-index )
    )
    [
      output list :my-genome worst-possible
    ]
    [
    ]

    let [ :invert-from ( 1 + ( :current-city-index mod number-of-towns ) ) ]
    let [ :invert-for ( :city-prime-index - :invert-from + 1 ) ]
    if ( :invert-for < 0 )
    [ set :invert-for ( :invert-for + number-of-towns ) ]
    set :my-genome ring-invert :invert-from :invert-for :my-genome

    set :current-city :city-prime
    set :current-city-index ( position :city-prime :my-genome )

  ]

end

to traveler-not-me :some-traveler-id

;; Notice that this is a tournament with replacement, so that it will
;; work even for a population of two genomes; and that because the genome
;; for a traveler isn't replaced until the end of an execution cycle through
;; the heuristics, the tournament may select the other traveler's existing
;; genome to crossover with the local :newgenome held in the execution cycle,
;; rather than that other traveler's current best :newgenome.

;; create a traveler list omitting me

  let [ :traveler-list list-of-travelers ]
  let [ :own-id-index position :some-traveler-id :traveler-list ]
  setitem :own-id-index :traveler-list (last :traveler-list )
  set :traveler-list butlast :traveler-list

  let [ :trial-traveler pick :traveler-list ]

  if ( not tournament_p ) [ output :trial-traveler ]

  let [ :current-best-fitness item index-fitness tdata-of :trial-traveler]
  let [ :current-best-traveler :trial-traveler ]

  repeat ( tournament-size )
  [
    let [ :trial-traveler pick :traveler-list ]
    let [ :trial-fitness item index-fitness tdata-of :trial-traveler ]
    if ( :trial-fitness < :current-best-fitness )
    [

      set :current-best-traveler :trial-traveler
      set :current-best-fitness  :trial-fitness 

    ]
  ]

  output :current-best-traveler

end

to permute :some-genfit

  if not permute_p [ output :some-genfit ]

  let [ :perm-index-list empty-list ]
  let [ :my-permutation-count permutation-count ]

  repeat :my-permutation-count
  [
    let [ :next-index ( random number-of-towns ) ]
    if ( not member? :next-index :perm-index-list )
    [ set :perm-index-list ( lput :next-index :perm-index-list ) ]
  ]

  if ( (length :perm-index-list) < 3 ) [ output :some-genfit ]

  let [ :my-genome copy-list first :some-genfit ]
  let [ :my-fitness last :some-genfit ]
  let [ :best-genome copy-list :my-genome ]
  let [ :best-fitness :my-fitness ]

  let
  [
    :perm-n length :perm-index-list
    :perm-a empty-list
    :perm-mtc false
    :perm-even true
    :perm-out empty-list
  ]

  if ( :perm-n > high-permute )
  [
    print se "raising high permute from, to =>" list high-permute :perm-n
    set high-permute :perm-n
  ]

  let [ :index 0 ]
  repeat :perm-n
  [
    set :index ( :index + 1 )
    set :perm-a lput :index :perm-a
  ]

  loop
  [
    set :perm-out ( nexper :perm-n :perm-a :perm-mtc :perm-even )
    set :perm-n     first    :perm-out
    set :perm-out   butfirst :perm-out
    set :perm-a     first    :perm-out
    set :perm-out   butfirst :perm-out
    set :perm-mtc   first    :perm-out
    set :perm-out   butfirst :perm-out
    set :perm-even  first    :perm-out
    set :perm-out   butfirst :perm-out

    let [ :work-genome copy-list :my-genome ]

    set :index 0

    repeat :perm-n
    [
      set :index ( :index + 1 )
      zbsetitem
        (item (item :index :perm-a) :perm-index-list)
        :work-genome
        (zbitem (item :index :perm-index-list) :my-genome)
    ]

    let [ :work-fitness genome-fitness :work-genome ]
    if ( :work-fitness < :best-fitness )
    [
      set :best-fitness :work-fitness
      set :best-genome copy-list :work-genome
    ]

    if (not :perm-mtc)
    [
      output list :best-genome worst-possible
    ]
  ]

end

to nexper :some-n :some-a :some-mtc :some-even

  let [:my-n :some-n :my-mtc :some-mtc :my-even :some-even]
  let [:my-a copy-list :some-a]
  let [:s 0 :d 0 :l 0 :m 0 :i 0 :ia 0 :i1 0 :j 0]
  let [:missed false]

  if (not :my-mtc)  ;; first pass logic
  [

    set :my-a butfirst butfirst list 0 0
    set :i 0
    repeat :my-n
    [
      set :i (:i + 1)
      set :my-a lput :i :my-a
    ]

    set :my-mtc true
    set :my-even true

    if ( :my-n = 1 )  ;; if only one element, we are done
    [
      set :my-mtc false
    ]

    output se list :my-n :my-a list :my-mtc :my-even

  ]

  if ( :my-even )
  [
    set :ia item 1 :my-a
    setitem 1 :my-a (item 2 :my-a)
    setitem 2 :my-a :ia
    set :my-even false

    if
    (
      ( not ( 1 = ( item :my-n :my-a ) ) )
      or
      ( not ( ( item 1 :my-a) = ( 2 + ( :my-n mod 2 ) ) ) )
    )
    [
      output se list :my-n :my-a list :my-mtc :my-even
    ]

    if ( :my-n <= 3 )
    [
      set :my-mtc false
      output se list :my-n :my-a list :my-mtc :my-even
    ]

    set :i 0
    repeat (:my-n - 3)
    [
      set :i ( :i + 1 )
      if
      (
        ( item (:i + 1) :my-a )
        !=
        ( 1 + ( item :i :my-a ) )
      )
      [
        output se list :my-n :my-a list :my-mtc :my-even
      ]
    ]

    set :my-mtc false

    output se list :my-n :my-a list :my-mtc :my-even
  ]

  set :s 0
  set :missed false
  set :i1 1

  repeat ( :my-n - 1 )
  [

    if ( not :missed )
    [

      set :i1 ( :i1 + 1 )               ;; 2

      set :ia ( item :i1 :my-a )        ;; 1
      set :i ( :i1 - 1 )                ;; 1
      set :d 0
      set :j 0

      repeat :i                         ;; 1
      [
        set :j ( :j + 1 )               ;; 1
        if
        (
          :ia < ( item :j :my-a )       ;; 1 < 2
        )
        [
          set :d ( :d + 1 )             ;; 1
        ]
      ]

      set :s ( :s + :d )                ;; 1

      if
      (
        :d != (:i * ( :s mod 2 ) )      ;; 1 != 1
      )
      [
        set :missed true
      ]
    ]

  ]

  if ( not :missed )
  [
    set :my-mtc false
    output se list :my-n :my-a list :my-mtc :my-even
  ]

  set :m ( ( :my-n + 1 ) * ( ( :s + 1 ) mod 2 ) )
  set :j 0
  set :l 0

  repeat :i
  [

    set :j ( :j + 1 )

    if
    (
      0
      >
      (
        ( ( item :j :my-a ) - :ia )
        *
        ( ( item :j :my-a ) - :m )
      )
    )
    [
      set :m ( item :j :my-a )
      set :l :j
    ]
  ]

  if ( :l = 0 ) [ print "logic error in nexper" ]

  setitem :l  :my-a :ia
  setitem :i1 :my-a :m
  set :my-even true

  output se list :my-n :my-a list :my-mtc :my-even

end

to move_sublist :some-genfit

  if not move_sublist_p [ output :some-genfit ]

  let [ :sublist-index (random number-of-towns) ]

  ;; Allow any sublist length one or more, that lets this be the
  ;; "move allele" heuristic too.

  let [ :sublist-length (1 + random (number-of-towns - 2))]

  let [ :prefix-length (1 + random (number-of-towns - :sublist-length - 1) ) ]

  let [ :remainder-index
        ( ( :sublist-index + :sublist-length ) mod number-of-towns ) ]

  let [ :work-genome first :some-genfit ]
  let [ :my-genome empty-list ]

  repeat :prefix-length
  [
    set :my-genome lput ( zbitem :remainder-index :work-genome ) :my-genome
    set :remainder-index ( ( :remainder-index + 1 ) mod number-of-towns )
  ]

  repeat :sublist-length
  [
    set :my-genome lput ( zbitem :sublist-index :work-genome ) :my-genome
    set :sublist-index ( ( :sublist-index + 1 ) mod number-of-towns )
  ]

  repeat (number-of-towns - :sublist-length - :prefix-length)
  [
    set :my-genome lput ( zbitem :remainder-index :work-genome ) :my-genome
    set :remainder-index ( ( :remainder-index + 1 ) mod number-of-towns )
  ]

;;???  set :my-genome copy-list :my-genome

  let [:my-inverted-sublist-genome 
      ( ring-invert (:prefix-length + 1) :sublist-length :work-genome ) ]

  let [:my-fitness genome-fitness :my-genome]
  let
  [
    :my-inverted-sublist-genome-fitness
    genome-fitness :my-inverted-sublist-genome
  ]

  if ( :my-fitness < :my-inverted-sublist-genome-fitness )
  [
    set :my-genome :my-inverted-sublist-genome
    set :my-fitness :my-inverted-sublist-genome-fitness
  ]

  output list :my-genome worst-possible

end

;; FIXME

to same-genome :trial-genome :tabu-genome

;; We have a precondition that the two genomes are in standard form
;; or this cheap approach will not work.

  let [ :index 0 ]
  repeat number-of-towns
  [
    set :index ( :index + 1 )
    if ( ( item :index :trial-genome ) != ( item :index :tabu-genome ) )
    [ output false ]
  ]
  output true

end

to crossover_ordered :some-genfit :partner-genfit

  if not crossover_ordered_p [ output :some-genfit ]

;; the plan for ordered crossover is to copy a sublist from the
;; partner genome (treated as a ring, not just a list) to an empty
;; trial genome, append from ;; the turtle's own genome all the towns
;; (alleles) not in that sublist, in order, to the trial genome,
;; thus creating a genome with genes in order from one parent, followed
;; by genes in order from the other parent.

  let [ :trial-genome empty-list ]
  let [ :work-genome first :some-genfit ]
  let [ :partner-genome first :partner-genfit ]

;; start the crossover anywhere

  let [:crossover-start random number-of-towns ]

;; assure that both inserted part and remains are at least of
;; length 2, or we are wasting our time doing a meaningless crossover.

  let [:crossover-length ( 2 + random ( number-of-towns - 3 ) ) ]

  repeat :crossover-length
  [
    set :trial-genome
      ( lput ( zbitem :crossover-start :partner-genome ) :trial-genome )
    set :crossover-start ( ( :crossover-start + 1 ) mod number-of-towns )
  ]

  let [ :index 0 ]

  repeat number-of-towns
  [
    let [ :next-allele ( zbitem :index :work-genome ) ]
    if ( not member? :next-allele :trial-genome )
    [ set :trial-genome ( lput :next-allele :trial-genome ) ]
    set :index ( :index + 1 )
  ]

  output list :trial-genome worst-possible

end

to crossover_partial_match :some-genfit :partner-genfit

  if not crossover_partial_match_p [ output :some-genfit ]
  let [:in-genfit :some-genfit]
  let [:out-genfit :in-genfit]
  output :out-genfit

end

to crossover_cyclic :some-genfit :partner-genfit

  if not crossover_cyclic_p [ output :some-genfit ]
  let [:in-genfit :some-genfit]
  let [:out-genfit :in-genfit]
  output :out-genfit

end

to crossover_edge_preserving :some-genfit :partner-genfit

  if not crossover_edge_preserving_p [ output :some-genfit ]
  let [:in-genfit :some-genfit]
  let [:out-genfit :in-genfit]
  output :out-genfit

end


to anneal :basis-genfit :trial-genfit

;; Procedure anneal handles "simulated annealing", the standard
;; commercial solution for the traveling salesman problem in its
;; "polynomial time and space equivalent"
;; incarnations as chip or circuit board lead routing problems.

;; The gist of the method is to allow the solution to retreat by
;; some fraction of the total circuit length, rarely, to help an
;; approximation to get "unstuck" from a local optimum to allow
;; it to go on searching for the global optimum.  To assure that
;; the solution converges anyway, the retreat fraction is slowly
;; decreased over time.  This solution is modeled on the annealing
;; of solid materials where very slow cooling allows molecules to
;; "jump" to fill defects, based on random transients in the total,
;; but ever decreasing, heat of the cooling material.

;; In this demo, procedure anneal is a META-heuristic, applied at
;; user control to either all or none of the heuristics in use, so
;; that each heuristic can take advantage of the annealing advantage.

;; To make this demo work well, procedure anneal also handles the
;; normal decrement case before testing the anneal_p flag, so that
;; the decrement or (possibly) increment choice is all localized in
;; this one procedure; other design attempts to organize this
;; choice were much more awkward.

  let [ :trial-fitness last :trial-genfit ]
  let [ :basis-fitness last :basis-genfit ]

  if ( :trial-fitness = :basis-fitness ) [ output :trial-genfit ]
  if ( :trial-fitness < :basis-fitness )
  [
    if ( color = red ) [ setc green ] ;; flag positive progress
    output :trial-genfit
  ]

  if ( not anneal_p ) [ output :basis-genfit ]

;; Ratchet progress, don't anneal if we're already gaining ground in
;; this loop, preserve the gain instead.

  if ( color = green ) [ output :basis-genfit ]

;; We use a random-gaussian bias on the annealing-limit for the turtle
;; so that even far into a run when the annealing-limit has grown very
;; low, there is a non-zero chance of kicking a stuck genome out of its
;; local optimum rut.

  if ( ( :trial-fitness - :basis-fitness ) <
       ( ( item index-annealing-limit tdata ) *
         ( abs ( random-gaussian 1 ) ) ) )
    and simulated-annealing-random-chance-of-worstening-succeeds
  [

;; There are a couple of ways to model the decrementing of the
;; annealing limit.  One can either decrement it very slowly, but
;; decrement it for each pass whether an annealing worstening of
;; fitness happens on that pass or not, or decrement it fairly rapidly,
;; but only for each time an annealing style worstening of the genome
;; fitness is actually allowed to occur.  This implementation takes the
;; latter approach, just to see how it works compared to earlier
;; opposite choices by this author in similar demos.

    setitem index-annealing-limit tdata
      decrement-annealing-limit item index-annealing-limit tdata

;; Here is where we flag each potential worstening of the genome by
;; flashing the turtle yellow at its current position in the circular
;; histogram part of the interface window patch area.

    setc yellow

    output :trial-genfit
  ]

  output :basis-genfit

end

to tabu :tabu-genome-list :safe-genfit :trial-genfit

  if not tabu_p [ output :trial-genfit ]
  let [ :trial-genome first :trial-genfit ]
  let [ :index 0]
  repeat length :tabu-genome-list
  [
    set :index ( :index + 1 )
    if
    (
      same-genome ( item :index :tabu-genome-list ) :trial-genome
    )
    [
      output :safe-genfit
    ]
  ]
  output :trial-genfit

end

to update-tabu-list :some-genome :some-tabu-list

  ifelse ( ( length :some-tabu-list ) < tabu-list-maximum-size )
  [
    output lput ( copy-list :some-genome ) :some-tabu-list
  ]
  [
    output lput ( copy-list :some-genome ) ( butfirst :some-tabu-list )
  ]

end

to tournament

;; Notice that this is a tournament with replacement, so that it will
;; work even for a population of one genome; and that because the genome
;; for a turtle isn't replaced until the end of an execution cycle through
;; the heuristics, the tournament may select the turtle's existing genome
;; to crossover with the local :newgenome held in the execution cycle.

  let [ :trial-traveler pick list-of-travelers ]
  let [  :trial-fitness item index-fitness tdata-of :trial-traveler ]

  let [ :current-best-traveler :trial-traveler ]
  let [ :current-best-fitness  :trial-fitness ]

  if ( tournament_p )
  [
    repeat ( tournament-size )
    [
      set :trial-traveler pick list-of-travelers
      set :trial-fitness item index-fitness tdata-of :trial-traveler
      if ( :trial-fitness < :current-best-fitness )
      [
        set :current-best-traveler :trial-traveler
        set :current-best-fitness  :trial-fitness 
      ]
    ]
  ]

    output
      list
      ( copy-list item index-genome  tdata-of :current-best-traveler )
      (           item index-fitness tdata-of :current-best-traveler )

end


`observer`
globals
[
  heuristics-enabled
  busy-travelers
  high-permute
  high-tournament
  debugging_p
  best-ever
  loop-count
  number-of-travelers
  draw_all_once_p
  draw_all_always_p
  swap_p
  invert_p
  inver_over_p
  permute_p
  move_sublist_p
  crossover_ordered_p
  crossover_partial_match_p
  crossover_cyclic_p
  crossover_edge_preserving_p
  anneal_p
  tabu_p
  tournament_p
  want_debugging_p
  fail_p
  minimal_spanning_tree_start_p
  local_optimization_p
]

to startup
  ct cg cp co ca
  setup-toggles
  how-many-travelers
end

to possible-cycles

  let [ :result ( 1 / ( 2 * number-of-towns ) ) ]
  let [ :multiplier 0 ]

  repeat number-of-towns
  [
    set :multiplier ( :multiplier + 1 )
    set :result ( :result * :multiplier )
  ]

  output :result
  
end

to how-many-travelers
  setnumber-of-travelers
    ( int exp ( (hecta-log10-number-of-travelers / 200 ) * (ln 10)) )
end

to setup

  cp
  ct
  co
  set high-permute 1
  set high-tournament 1
  set debugging_p false

  stopcompute-num-travelers
  how-many-travelers

  print se "number of travelers" number-of-travelers
  print se "number of towns" number-of-towns
  print se "number of possible different circuits\n"
        se "through that many towns:\n"
        possible-cycles
  let
  [
    :bf
    (
      (
        possible-cycles    ;; number of circuits to evaluate
        *
        number-of-towns    ;; number of alleles per circuit
        *
        7                  ;; floating point ops per allele
      )                    ;; ... product gives calculation
                           ;; effort needed per problem instance
                           ;; this size
      /
      (
        500000000          ;; half a gigaflop, roughly, available
                           ;; from a typical Q1 2001 AD desktop pc
        *
        3600 * 24 * 365.25 ;; seconds per year
      )                    ;; ... product gives calculation
                           ;; resources available per year
    )                      ;; ... quotient gives years for this
                           ;; sized problem solved by brute force
                           ;; exhaustive search, considering only
                           ;; the expense of doing one fitness
                           ;; evaluation for each possible circuit
  ]

  let [:duration "years"]
  if (:bf < 1.0)
  [
    let [:duration "days"]
    let [:bf (:bf * 365.25)]
  ]
  if (:bf < 1.0)
  [
    let [:duration "hours"]
    let [:bf (:bf * 24)]
  ]
  if (:bf < 1.0)
  [
    let [:duration "seconds"]
    let [:bf (:bf * 3600)]
  ]
  print se "number of"
        se :duration
        se "to compute lengths for\n"
        se "all those circuits, to find the best\n"
        se "circuit by a brute force search,\n"
        se "assuming a 500megaflop processor:\n"
           :bf

  set loop-count     1

  create-towns      number-of-towns
  create-travelers  number-of-travelers
  create-indicators 1

  ask-towns
  [
    init-self
  ]

  set busy-travelers number-of-travelers

  ask-travelers
  [
    init-self
    set busy-travelers (busy-travelers - 1)
  ]

  ask-indicators
  [
    init-self
  ]

  setup-plot

  set best-ever assay-plot

  draw-best

  draw-anneal

  ask-towns
  [
    run-town
  ]

end

to setup-toggles

;; turn off one-time drawing of all circuits

  set draw_all_once_p             false

;; enable blind heuristics to start

  set swap_p                      true
  set invert_p                    true
  set inver_over_p                true
  set permute_p                   true
  set move_sublist_p              true
  set crossover_ordered_p         true
  set crossover_partial_match_p   true
  set crossover_cyclic_p          true
  set crossover_edge_preserving_p true

;; enable metaheuristics to start

  set anneal_p                    true
  set tabu_p                      true
  set tournament_p                true

;; disable debugging to start

  set want_debugging_p            false
  set fail_p                      false
  set draw_all_always_p           false

;; disable sighted heuristics to start

  set minimal_spanning_tree_start_p  false
  set local_optimization_p           false

end

to setup-plot
  clearplot
  viewplot
  setplot-yrange 0 2
  setplot-xrange 0 8
  setplot-title "worst, mean, best; small is good"
  setplot-ylabel "lengths"
  setplot-xlabel "execution loops"
  pp  1 setppc magenta
  pp  2 setppc turquoise
  pp  3 setppc blue
  pp  4 setppc brown
  pp  5 setppc green
  pp  6 setppc red
  pp  7 setppc orange
  pp  8 setppc lime
  pp  9 setppc cyan
  pp 10 setppc black
end

to assay-plot

  let
  [
    :best-now
    min-of-turtles-with
    [breed = travelers]
    [item index-fitness tdata]
  ]

  pp  1 setppc magenta    plot ( :best-now              )

  let
  [
    :average-now
    ( ( sum-of-travelers [item index-fitness tdata] ) / number-of-travelers )
  ]

  pp  3 setppc blue       plot ( :average-now           )

  let
  [
    :worst-now
    max-of-turtles-with
    [breed = travelers]
    [item index-fitness tdata]
  ]

  pp  4 setppc brown      plot ( :worst-now             )

  output :best-now

end

to draw-anneal

  let
  [
    :annealing-limit-now
    ( ( sum-of-travelers [item index-annealing-limit tdata] ) /
      number-of-travelers )
  ]

  ;; Moved from plot window to patch area of interface window
  ;; to declutter plot window and make titling the plot simpler.

  ;; pp  5 setppc green      plot ( :annealing-limit-now   )

  ask-indicators
  [
    draw-self :annealing-limit-now
  ]

end

to draw-best

    ask-travelers
    [
      if ( best-ever = ( item index-fitness tdata ) )
      [
        draw-self green
        reposition-self
        print se "Loop:" se loop-count se "new best:" best-ever
      ]
    ]

end

to go

;; build annealing rate modifier before each pass

  set heuristics-enabled 0

  if swap_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if invert_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if inver_over_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if permute_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if move_sublist_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if crossover_ordered_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if crossover_partial_match_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if crossover_cyclic_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if crossover_edge_preserving_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if ( heuristics-enabled < 1 )
  [
    set heuristics-enabled 1  ;; prevents divide by zero, still does nothing
  ]

  set busy-travelers number-of-travelers

  if want_debugging_p [co]

  if ( draw_all_once_p or draw_all_always_p)
  [
    cg

    ask-travelers
    [
      draw-self orange reposition-self
      if (breed = travelers) [ set busy-travelers (busy-travelers - 1) ]
    ]

    ask-travelers
    [
      if ( best-ever = ( item index-fitness tdata ) )
      [
        if (breed = travelers) [ set busy-travelers (busy-travelers + 1) ]
        draw-self cyan
        reposition-self
        if (breed = travelers) [ set busy-travelers (busy-travelers - 1) ]
      ]
    ]

    setdraw_all_once_p false
  ]

  setloop-count (loop-count + 1)

  set busy-travelers number-of-travelers

  ask-turtles
  [
    run-self
    if (breed = travelers) [ set busy-travelers (busy-travelers - 1) ]
  ]

  ask-travelers
  [
    setitem index-fitness tdata ( item index-new-fitness tdata )
    setitem index-genome  tdata ( copy-list item index-new-genome tdata )
  ]

  let [ :best-now assay-plot ]

  if ( :best-now < best-ever )
  [
    setbest-ever :best-now

    cg

    draw-best
  ]

  draw-anneal

end

to print-toggles

  print " "
  print se "swap-------------------------=>" swap_p
  print se "invert-----------------------=>" invert_p
  print se "inver-over-------------------=>" inver_over_p
  print se "permute----------------------=>" permute_p
  print se "move sublist-----------------=>" move_sublist_p
  print se "ordered crossover------------=>" crossover_ordered_p
  print se "partial match crossover------=>" crossover_partial_match_p
  print se "cyclic crossover-------------=>" crossover_cyclic_p
  print se "edge preserving crossover----=>" crossover_edge_preserving_p
  print se "anneal-----------------------=>" anneal_p
  print se "tabu-------------------------=>" tabu_p
  print se "tournament-------------------=>" tournament_p
  print se "want debugging---------------=>" want_debugging_p
  print se "fail-------------------------=>" fail_p
  print se "draw all always--------------=>" draw_all_always_p
  print se "minimal spanning tree start--=>" minimal_spanning_tree_start_p
  print se "local optimization-----------=>" local_optimization_p
  print " "

end


`information`
BTSP2_02.slogo, 2001/04/06 release

****************************************
What is this?
****************************************

It is yet another blind traveling
salesman problem demo from the man from
xanth, written from scratch as a good
technique for blundering across StarLogo
compiler bugs while helping debug the
StarLogo 1.2 beta release compiler, and
continued after that version of StarLogo
was released for public consumption.

It is best used (and the windows are
placed as if it were running) in a 1280
x 1024 (or better) resolution display,
but works at least adequately in an 800
x 600 resolution display, and with less
eyestrain to make up for superimposed
windows at that resolution.

It is not yet anywhere close to "done",
my record on finishing toy programming
tasks is spotty, but the interface is
about where it belongs, and enough
parts work to make it fun and useful.

Six of the simpler approximate solution
heuristics: swap, invert, inver-over,
permute, move sublist, and ordered
crossover; and the three metaheuristics:
simulated annealing, tournament
selection of crossover candidates, and
tabu control of backtracking during
searching; are in place and now good
enough to solve modest "computationally
infeasible" level exhaustive search
sized problems reasonably quickly,
keeping the watcher's interest mostly
with flashing lights while the real work
goes on "behind the curtain".

For example, solving a problem of 25
towns by brute force exhaustive search
would require evaluation of the fitness
of about 3*10^23 circuits, each needing
175 floating point operations minimum to
calculate.

This calculation would require about 3.3
billion years, using a desktop computer
which can do 500 million floating point
operations per second, fairly affordable
as a home computer at this writing.

In this project, in contrast, a
population of 40 travelers, with all of
the currently implemented heuristics
turned on, can usually solve that
problem in around five to ten minutes,
which is what makes heuristic
approaches to solving computationally
hard problems an interesting area of
study for the hobbiest, and also the
focus of lots of academic and industry
research.

****************************************
Where is it maintained?
****************************************

Current versions of this demo may be
found in Web directory:

http://www.well.com/user/xanthian/public/code/StarLogo/BTSP/

****************************************
What do you see in the StarLogo
interface window?
****************************************

========================================
Some text instructions printed right on
the window, enough to get you going.
========================================

========================================
Some sliders:
========================================

The top slider, whose "name" is actually
instructions for using it -- used to set
indirectly the count of salespersons
who will be competing to be the first to
find that "perfect" sales route.

It is used in conjunction with the
button widget two widget rows down which
is labeled "how-many-travelers" and
with the moniter widget just below that
button labeled "number-of-travelers".

"the number of towns to visit" -- used
to set the number of cites on the route.

========================================
Some monitors:
========================================

number-of-travelers -- shows the current
number of travelers as being set by the
top slider bar, but only when the button
"how-many-travers" is depressed.

travelers still busy -- shows the number
of travelers still performing
computations in the current execution
loop.  Reset to the total number of
travelers for each new execution loop.

========================================
Some essential-to-use buttons:
========================================

reset -- clear all global variables,
then put all the toggles into default
values.

prepare -- do the demo setup after the
sliders are set to the user's choice of
values.

  The "prepare" button prints several
  lines to the output window, showing:
  the number of travelers, the size of
  the problem in possible circuits
  (derived from the number of towns),
  the effort needed to solve the problem
  by a brute force search, and the
  length of the best first ciruit among
  all the travelers.

execute -- run the demo in a
non-terminating loop.  Press "execute"
again to stop the demo.

You can do "prepare, execute, don't
execute" over and over, adjusting the
sliders for new numbers of towns and
travelers if desired before each
"prepare"; don't adjust sliders while
"execute" is enabled, bad things will
happen.

========================================
An optional-to-use "draw all once"
button:
========================================

Pressing this button will set a toggle,
so that at the start of the next
execution loop, all the travelers will
draw their current genome "circuit" in
orange, superimposed over the same set
of towns.

Then, if any traveler's fitness matches
the best fitness seen so far (not always
the case, because annealing can take the
genome of the traveler with the best
solution backsliding to a worser fit
genome , resulting in no current
traveler having the once seen best
genome so far), that circuit will be
overdrawn superimposed on all the
others, in cyan.

The visual end result is the set of
edges of the best circuit, shown in
cyan, plus the (undistinguished)
candidate edges of all the other
circuits combined, also shown in orange.

This is intended to give the user a way
to follow the progress of the population
as a whole; many candidate edges show a
population in disagreement, while few
candidate edges show a population
exploring ways to improve a solution on
which the membership agrees in general
if not in details.

========================================
An optional-to-use "draw all always?"
toggle button:
========================================

This is really a debugging tool, so it
is clustered with the debugging toggles,
but it can be fun to turn this on and
watch the number of orange edges not
involved in the current trial solution
decrease over time as the population of
travelers agree that some edges are not
worth considering, and also to watch
the results of annealing as a solution
is near and some travelers back out by
adding unpopular edges to their genomes
to try to find a better solution hiding
elsewhere.

========================================
Some optional-to-use "heuristics"
(approximate solutions) buttons:
========================================

swap? -- use the simple, "swap two cites
in the genome list and keep the change
if it shortens the circuit" heuristic.

invert? -- use the simple, "reverse a
contiguous sublist of the genome list,
keep the change if it shortens the
circuit" heuristic.

ordered crossover? -- use the fairly
complex "ordered crossover" genetic
algorithm heuristic, creating a new
genome by selecting an ordered sublist
of the circuit list from one partner's
genome, the rest of the towns (alleles)
from the other partner's genome in order
by knocking out the alleles already
selected, then keeping the better of
the original or the child genomes.

partial match crossover? -- use the
fairly complex "partial match crossover"
genetic algorithm heuristic,  which
swaps sublists at matching positions in
each partners' genome, then patches up
the rest of the genome to make it a
permutation of the towns (alleles)
again, keeping the best of the available
original or child genomes.

cyclic crossover? -- use the fairly
complex "cyclic crossover" genetic
algorithm heuristic, which swaps one
complete sub-permutation cycle through
the original and partner genomes,
keeping the best available of the
original or the child genomes.

  [As of this writing, a good tutorial
  introduction to many of the above
  heuristics (where "swap?" is instead
  called "mutation"), and to the Blind
  Traveling Salesman Problem in general,
  can be found at the (wonderful) site
  which inspired this demo, maintained
  by Scott Robert Ladd, on the page at
  the (folded) URL:
  http://www.coyotegulch.com/ complex/
  genetic.html
  starting about 3/5ths of the way down
  the page.

  Scott is in no way to blame for my
  very different algorithmic choices in
  this demo; we have a fundamental (and
  undiscussed) disagreement about the
  utility and implementation of elitism,
  and my approach here to mutation is
  very different from his as well: he
  treats it as a modifier to other
  heuristics, in agreement with existing
  practice in the genetic algorithms
  field, while I treat it as a
  self-standing heuristic on its own,
  since with the assistance of the
  simulated annealing metaheuristic,
  mutation without the help of another
  heuristic is capable of solving the
  BTSP problem in reasonable execution
  time.]

inver-over? -- use this complicated, but
fast, powerful operator from the Gao and
Michalewicz paper, which does an asexual
change to the travler's genome, but does
it by imitating other genomes in the
population.  This is powerful in part
because it can do a lot of changes to
the circuit in a single pass, where most
other heuristics are limited to a single
change per new genome.

permute? -- use the simple, but time
consuming, technique of trying all of
the possible permutations of a subset
of the towns in genome, replaced back
in the same genome positions, as changes
to the genome, and replacing the genome
with the best among the trial genomes
thus created.

  The "permute" heuristic decides how
  many alleles to include in the
  permuted sublist by use of the
  StarLogo random-gaussian function, so
  in the worst case, with a sublist
  which is the whole genome, this can be
  equivalent to a brute force exhaustive
  search, but in the worst case, we are
  all going to die, anyway, and the
  chances of selecting the worst case
  for a problem with a dozen or more
  alleles (towns) within the user's
  (or the universe's) lifetime is too
  small to consider.  What this gains is
  a very powerful way to get "unstuck"
  from a "local optimum".  Although it
  can be painfully slow for large
  sublists, it is the most powerful
  heuristic for getting "unstuck" among
  the ones included in this demo, in a
  mathematically defensible sense.

move sublist? -- use the cheesy, but
sometimes important, heuristic of
sliding a whole connected piece of the
circuit to sit between two different
towns than the ones between which it
presently sits, and possibly reversing
it as well, to see if an improved
genome can be created that way.

edge preserving crossover? -- use the
very complex "edge preserving crossover"
genetic algorithm heuristic, keeping the
common edges between two partner
genomes, then selecting for the child
genome's remaining edges randomly
between those available in the two
partner genomes.

========================================
Some optional-to-use "metaheuristics"
(meta-controllers for approximate
heuristic solutions) buttons:
========================================

anneal? -- permit backsliding to a
worser genome at a decreasing fitness
backsliding amount over time, and at a
randomly controlled chance per new,
worser genome generated, to help keep
the computations from getting "stuck" in
a "local optimum".

tournament? -- use a tournament, rather
than a single random choice, to select a
partner for a crossover heuristic,
biased by the tournament for better
fitness, in each of the crossover
heuristics.  This metaheuristic does not
apply to "asexual" heuristics which use
only a single turtle's genome, but does
apply in a slightly modified way to the
inver-over heuristic, which imitates,
though it doesn't directly cross-breed
with, other genomes.

tabu? -- forbid immediate return to a
just abandoned solution, again to help a
computation get unstuck from oscillating
between a local optimum and a nearby set
of slightly worser choices.

========================================
A canvas drawing area with a top and a
bottom section:
========================================

----------------------------------------
Canvas top half:
----------------------------------------

This part contains a circular histogram,
whose elements are StarLogo turtles each
carrying a genome representing a
possible solution to the problem, plus a
patch marked to show the center of the
histogram, and whose turtle elements are
sorted by turtle id number to have
angles smoothly spread around the
compass, and whose radial distance from
the center point represents the fitness
of that particular turtle's genome
(smaller fitness values are better in
this demo, since fitness is directly the
length of the salesperson-turtle's
circuit, considered to be scaled to the
interior of a unit square).

If there are lots of travelers working
the problem, two things become evident
with reflection: a thinner circle
"annulus" represents more agreement
about the value of the solution's
fitness, and a shrinking circle radius
represents an improving common set of
solutions.

If the anneal? metaheuristic is enabled,
the values which the turtle elements
represent will sometimes increase as
well as the usual decrease when anneal?
is disabled.

Turtles which represent values possibly
about to increase turn yellow for a
while before returning to red.

Turtles which represent values possibly
about to decrease turn green for a while
before returning to red.

Turtles for whose value no acceptable
change was found in the current
execution loop just remain red; notice
that over time the majority of turtles
remain red for most execution loops; the
solutions represented by the turtles'
genomes are getting harder to improve as
fewer possible improvements remain.

Because the anneal? metaheuristic
applies to all the heuristics, the
cumulative effect of several heuristics
may be a decrease even if anneal?
signals that an increase has been
accepted for one heuristic.

----------------------------------------
Canvas bottom half:
----------------------------------------

This area contains two displays, a
current best circuit graph, and an
average annealing limit histogram to
the same scale.

The current best circuit area contains
some white turtles standing in place to
be the cities through which the
salespersons' circuits must thread, and
after a short delay, the most fit
current solution is drawn in green as a
circuit through those cities'
locations.

Watching this area for a while when
there are both a fairly large number of
cities and also a fairly large
population of sales staff shows that the
staff's agreement about how long the
path should be implies nothing in the
way of agreement about what shape the
path should be.  You should see good
bits of path leave the current best
solution as other good bits join it;
the replacement trial solution is better
overall, not necessarily better in ever
detail.  That's what makes this version
of the Traveling Salesman Problem
"Blind".

It is mathematically easy to prove that
a circuit that intersects itself is not
optimal, so even a suboptimal circuit
that is not self intersecting is a good
indication of progress, though you may
later see even shorter circuits which
_are_ self-intersecting proposed as
trial solutions.

Changes in the displayed circuit will be
reflected by a new line of text in the
Output window showing the new circuit
length and naming the traveler which
found it.

----------------------------------------
Canvas left side:
----------------------------------------

The simulated annealing bar is folded to
make it fit at scale beside the current
best circuit graph.  The histogram is
drawn up in yellow, and back down in
blue, until the limit has decreased to
half its initial value, after which the
histogram is only drawn up in yellow.

This histogram shows the amount of extra
length that is allowed to be added to a
circuit by a traveler who has chosen to
backslide in hopes of escaping a
possible local optimum to find instead
the global optimum.  Its initial length
is twice the diagonal of the best
ciruit graph display area unit square.

****************************************
What do you see in the Plot window?
****************************************

This area contains a time series of the
current worst, average, and best
solutions, depicted with brown, blue,
and purple lines respectively; again,
lower values for these items are
better.

Following this plot for a while, you
should see the worst and best solution
squeeze the average solution between
them, until, if an exact solution is
found, possible for small numbers of
cites, the three values coincide.

When annealing is enabled, the lines can
go up as well as down, which is also fun
to watch and compare with the circular
histogram in the patches canvas and the
orange edges shown by the "draw all
once" or "draw all always?" buttons.

****************************************
What do you see in the Output window?
****************************************

A "number of travelers", a "possible
circuits", a "brute force" and a "new
best" line each time "prepare" is
pressed.

  Use the "possible circuits" value to
  understand the computational
  complexity of the problem represented
  by the current setup's number of
  towns.

  The "brute force" line shows the time
  that would be required, assuming a 500
  megaflop (floating point operations
  per second) home computer, to evaluate
  the fitness of each possible circuit
  and so solve the problem by brute
  force exhaustive search of the entire
  problem space.

  The "new best" line shows the best
  solution guessed in setting up the
  random genomes for the initial
  traveler circuits.

A running series of "new best"
announcements by each traveler-turtle
who finds a new solution better than all
the others seen so far.

The "new best" lines are accompanied by
the number of the loop at which that new
best circuit genome was found.  Notice
that many loops may separate new best
circuits, but that typically the
population average fitness as shown on
the plot window continues to improve.

A list of the status of each toggle
button for heuristics and
metaheuristics each time it is toggled.

  The Heuristics and Metaheuristics
  toggles are all set to "true" by
  default to start, after the "prepare"
  button has been pressed.  It helps the
  computation slightly to disable the
  ones that are not yet implemented.

  The Sighted Cheats toggles are set to
  "false" by default.

A report of all the toggle current
values when the "see toggles" button is
clicked.

Ongoing reports of "high tournament"
values, showing the largest number of
partner travelers to select among for
the most fit one, ever chosen by any
traveler for a tournament to select a
partner with whom to share genome
information.

Ongoing reports of the "high permute"
values, which show the largest number of
permutations to try ever chosen by any
traveler when using the "permute"
heuristic.  This can help explain to the
user why a few travlers still linger in
the "travelers still busy" count.  The
permute heuristic is very labor
intensive for the computer... here are
the number of fitness calculations that
must be done for a few values of "high
permute":

  high permute    fitnesses to compute
  ------------    --------------------
             1                       1
             2                       2
             3                       6
             4                      24
             5                     120
             6                     720
             7                    5040
             8                   40320

The randomizer for "high permute" has
been tuned so that normally you won't
see values over 5.

Because travelers are looking at and
modifying these two high-water marks in
parallel, sometimes they fight with one
another to set the value, especially
when there is a large population.  This
doesn't hurt anything, these are just
"for your information" messages, but it
can produce a raft of seemingly
conflicting messages.

****************************************
What do you see in the Information
window?
****************************************

This documentation.

****************************************
What do you see in the Control Center
window?
****************************************

The code, divided into turtle procedures
and observer procedures.

There is also lots more documentation
embedded in the code, visible in the
turtle procedures and observer
procedures frames of the Control Center
window.

****************************************
But what's the point?
****************************************

The traveling salesman problem, and the
specialized subset called the blind
traveling salesman problem, are examples
of "NP complete" problems, problems
whose exhaustive brute force solution is
so hard for even modest problem sizes
that only heuristic approximate
solutions have ever been found that can
be completed in "a reasonable time", say
the expected lifetime of the universe
given the fastest current computers.

This demo, besides originally being a
debugging tool for beta testing StarLogo
1.2 before that StarLogo version's
release, is meant to help the user gain
a visual and intuitive appreciation for
this kind of computationally complex
problem, and with luck, for the shape a
better solution would take.

  There is a standing million US dollar
  prize for the first person to
  discover a "polynomial time and
  space" direct solution to this
  problem.  It will not likely be
  awarded in my lifetime, since lots of
  very smart people have been trying to
  solve this problem for a very long
  time, since before the advent of
  electronic computers, for instance.

Nevertheless, for a student or other
interested party, this demo gives a very
visual way to see the effect of applying
some of the best currently known
approaches to solving this problem
indirectly, via heuristics which give
"good enough", commercially useful
solutions for even very, very large
problem instances.

Though such large problem instances are
not possible to attempt using this demo
due to limitations of StarLogo, of this
implementation which sometimes chooses
clarity and ease of implementation over
raw speed, of home computers, and of
interpretive computing languages in
general; the smaller instances of which
this demo is capable are more
accessible to the user, and provide
equal spark for intuition.

****************************************
What strategies should the user pick?
****************************************

Aye, there's the rub, finding the best
strategy is the point of the exercise,
now isn't it?

A little overview level guidance is
still possible.

Setups which use a small number of
travelers don't get much help from
crossover or the inver-over heuristic,
because with one genome per traveler,
there isn't a lot of variety from which
to choose solutions, and the variety
that there is can rapidly collapse from
"genetic drift" as well as actually
failing selection due to being bad trial
solutions.

However, since there is less computation
per execution cycle, those same small
population setups succeed at driving
one-genome heuristics very rapidly.  One
genome heuristics are less powerful, so
make this choice for smaller problems
(fewer towns).

Contrariwise, problems with large
numbers of towns are (perhaps
counter-intuitively) solved faster in
terms of generations needed, by use
oflarger populations and crossover
heuristics, even though the execution
time per cycle grows with the
population size, because the richer
selecton of genomes to mix and match
sometimes compensates for the time
needed to handle each genome.  However,
large populations for small problems
are counterproductive because a large
population takes proportionally longer
to step through each generation.

There is a limit to how big a population
can be used before the computation time
to solve a particular "number of towns"
setup goes from "minutes" to "days", and
there is a limit to how big a "number of
towns" problem even this mix of
heuristics can solve.  Still, increasing
the problem exhaustive search difficulty
level by factors of hundreds of
thousands may only double or triple the
heuristic solution time.

So, work your way up both sliders
slowly to get a feel for what is a
feasible problem size, but stay
optimistic.

Focusing entirely on one heuristic can
yield a lot of intuition about that one
heuristic, including possibly the way
metaheuristics affect its performance.

Multiple heuristics can help one another
get "unstuck" by providing alternative
ways to get out of "local optima".  They
also help counter "genetic drift"
problems characteristic of single
heuristic approaches by stirring the
population in different ways.

From the point of view of the crossover
heuristics, the single genome heuristics
can _all_ be considered as "mutation"
heuristics.

There is a practical limitation due to
StarLogo's implementation and its use of
Java, as well.  Beyond a certain problem
size, data used by the calculations will
overflow from the computer's main memory
("RAM") into its disk drive virtual
memory ("swap"), and this can slow down
the calculations by factors of hundreds,
at least.

****************************************
What's the demo status?
****************************************

As of this release, dated 2001/04/06:

Heuristic                   Implemented?
--------------------------- ------------
swap?                            yes
invert?                          yes
inver-over?                      yes
permute?                         yes
move sublist?                    yes
ordered crossover?               yes
partial match crossover?         no
cyclic crossover?                no
edge preserving crossover?       no

Metaheuristic               Implemented?
--------------------------- ------------
anneal?                          yes
tabu?                            yes
tournament?                      yes

Sighted Cheats              Implemented?
--------------------------- ------------
minimal spanning tree start?     no
local optimization?              no

Scaffolding is in place for adding the
other heuristics and metaheurists as
time allows: the execution loops
through stubs for some of the
unimplemented routines already, to
assure that the interfaces work OK.

Example runs with all implemented
heuristics and metaheuristics enabled
(swap, invert, inver-over, permute,
move sublist, ordered crossover, anneal,
tournament, and tabu, at this release):

Towns   Travelers    Generations to the optimum solution
-----   ---------    ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
   10          10       7   11    9    4                              
   10          20       6    7    6    5                              
   10          40       4    4    6    7                              
   10          80       4    3    5    5                              
   10         160       3    2    3    5                              
   15          10      14   17   16   20                              
   15          20      13   21   17   12                              
   15          40      12   10   16   13                              
   15          80      12   39   11   10                              
   15         160       9   11   12    8                              
   20          10      34   99   25   67                              
   20          20      23   35   30   29                              
   20          40      48   48   31   22                              
   20          80      20   22   19   25                              
   20         160      24   24   20   23                              
   25          10     344   77   39  347                              
   25          20      60  178   49   88                              
   25          40      43   31   31   41                              
   25          80                                                     
   25         160                                                     
   30          10                                                     
   30          20                                                     
   30          40      48                                             
   30          80                                                     
   30         160                                                     
   35          10                                                     
   35          20                                                     
   35          40                                                     
   35          80                                                     
   35         160                                                     
   40          10                                                     
   40          20                                                     
   40          40                                                     
   40          80                                                     
   40         160                                                     
   45          10                                                     
   45          20                                                     
   45          40                                                     
   45          80                                                     
   45         160                                                     
   50          10                                                     
   50          20                                                     
   50          40                                                     
   50          80                                                     
   50         160     240                                             

  [That 240 generations for 50 cities
  and 160 travelers took roughly six
  hours wall clock time to compute.  A
  long time, that is, but considerably
  shorter than 6.7*10^48 years, the
  brute force computation time
  estimate.

  I'm cheered in my choice of
  heuristics and metaheuristics, and of
  a steady state rather than an elitist
  approach to improving genome
  populations, to note that those 240
  generations accomplished what Scott
  Robert Ladd's demo "Traveller 1.2.1"
  (see below) had not quite finished
  doing in over half a million
  generations and about the same wall
  clock time.]

  [I'll update this table to the
  maintenance URL, without bumping the
  version number, as more test run
  results are available, I got anxious
  to put this version of this project
  on the street for others to see.]

Where the time to execute a generation
is very roughly proportional to the
product of the towns and the travelers.

Notice that the data is fairly "noisy",
run to run values are not necessarily
very much alike.  Depending on the exact
configuration of cities, and also on the
luck involved in picking particular
starting genomes and particular random
changes, the search can get pretty
tremendously "stuck" in a local optimum
where the human eye can easily pick out
an improvement, with no progress for
sometimes a hundred times as many
generations as it took to get to the
"stuck" spot.  This is normal, and is
why the search for better heuristics is
an active focus of research around the
world.

Notice too that as the problem size and
the population size grows, the noise
somewhat decreases.  Large populations
explore lots of the solution space in
parallel, and individual genomes can
lend one another bits of a final
solution as a particular run goes along.

Which is exactly the point of
evolutionary computation methods, a
name for this general way of solving
very hard problems with no feasible (or
obvious) direct solution known or
available.

****************************************
Changes from the previous releases:
****************************************

v 2_01 to v 2_02

Added a table of example run results for
various numbers of towns and travelers
to this Information window.

Substantially rearranged and enhanced
the Interface window widget set.

Added the interface and code for a new,
fast heuristic, "inver-over", from Guo
Tao and Zbigniew Michalewicz,
"Inver-over Operator for the TSP".

Added the interface and code for a new,
not wonderfully effective heuristic
"move sublist", to see how it worked,
and because I saw runs getting "stuck"
at a local optimum for lack of it.

Implemented the metaheuristic for tabu
search, a popular method for preventing
tight loops into and out of a local
optimum, after learning how to overcome
problems with my traditional Logo
programming style caused by the small
stack space StarLogo 1.2 gives to each
turtle (and to each patch).

Implemented the "permute" heuristic
after overcoming the same set of
problems for it.

Added interface, but not yet the
implementations, for two kinds of
"sighted" enhancements of the style of
ones that are part of most commercial
fast heuristic approximate solution
implementations of "traveling salesman
problem"-like code: "minimal spanning
tree start?" to seed the initial
population with known good approximate
solutions derived from the minimal
spanning tree of the set of town
coordinates [the length of the minimal
spanning tree for the towns graph is
known to be strictly less than the
optimum circuit length, so doubling it
by replacing each edge by twin,
oppositely directed edges, to make it a
circuit, and then weeding out duplicate
towns, is known to give a circuit less
than or equal to twice the length of
the optimal solution] and "local
optimization?" which will do what it
says, optimizations of local parts of
the circuit based on knowing specific
city to city distances, before
optimizing the global circuit.  Since
these two heuristics are not in the
spirit of the Blind Traveling Salesman
Problem, where only the length of the
entire circuit is know to the search
optimization part of the code, they are
labeled "Cheats" in the accompanying
Interface window text widget.

Modified all the heuristic's toggle
buttons to output a simple statement of
their own change to the Output window,
rather than the bulky dump of the status
of all the toggles printed earlier.

Added a loop counter, added the display
of the execution loop number to the
Output window "new best" display to help
the user gain an intuition that it may
take many loops of population average
fitness improvement to support one
finding of a new best circuit when the
problem is a complex one.  In very
complex problems, hundreds of loops to
improve the population fitness may occur
between findings of new best fit
genomes.

Added a "travelers still busy" monitor
so the user can see that there is some
progress happening.  The "permute" and
"inver-over" heuristics, in particular,
can take wildly different amounts of
time for each traveler, and for each
execution loop as well, which is okay,
because processor time gets focused on
the still busy travelers when the others
are done with their main run loop.

Added a "draw all once" button to the
interface window.

Marked the unimplemented heuristics'
toggles with an asterisk, added a text
widget explaining this.

When documenting a problem to the beta
development team for StarLogo 1.2, I
added some debugging buttons and code.
It is left in place, but with luck won't
be needed by users of the versions I put
up for download.  Two buttons, "want
debugging?" and "fail?" are only
interesting for debugging real problems,
but "see toggles" and "draw all always?"
may be fun for the user of the released
versions of this project.

Added code to clear the Output window
at the top of each execution loop when
"want debugging?" is enabled, to
prevent the Output window from
overflowing.

Added code so that each turtle of breed
"towns" paints a 3 by 3 pixel area
around its location after a circuit is
drawn, to make the town locations more
visible to the user.  This is a simple,
big win.

Removed the artifact of getting a "new
best" due only to accumulated round off
errors when computing fitness for the
same genome in different possible ways
it can be stored (rotation of the town
list stored in the genome doesn't
matter, reversal of the genome doesn't
matter, the genome still describes the
same circuit), by always putting the
genome in a particular standard format
before calculating its fitness for
comparision against the current best
fitness.

Added commentary written to the Output
window at the start of each run to
describe the effort needed to solve the
given problem by a brute force approach.

Moved the annealing limit display from
the Plot window to the patches canvas
area, where it is now a barely noticable
folded bar histogram to the left of the
current best circuit display.  So far,
most runs come nowhere close to
exhausting the annealing limit before
the solution is found, and so it was
more clutter than good information when
displayed in the Plot window.

Modified the code to decrease the level
of annealing attempts based on how many
heuristics are enabled, to remove an
artifact where there was almost as much
backtracking as forward progress among
the population of travelers.

Modified the number of travelers input
to use three widgets: a logorithmically
proportional slider at the top of the
Interface window, whose name is really
instructions for setting the number of
travelers, a "number-of-travelers"
monitor where the corresponding integer
number of travelers setting is shown,
and a how-many-travelers pushbutton to
enable that monitor.  This is still
overly complex, but StarLogo doesn't
have a built in log slider widget yet,
and at least now the user can see the
number of travelers directly instead of
looking for it in the Output window.

Renamed the "number-of-towns" slider to
"the number of towns to visit" for
better clarity.

Rearranged the Interface window to move
the sliders up  so that the slider that
sets the number of travelers could be
the full width of the window for greater
precision.  Yuk!

Reworded the instructions painted on the
Interface window for additional clarity.

v 2_00 to v 2_01

Added "permute?" and "edge preserving
crossover?" heuistic and "tournament?"
metaheuristic interface buttons, with
stubbed implementations for the former
two and a full implementation for the
latter.

Modified the interface window layout and
text modestly to clarify comments and
add buttons for new functionality.

Modified "number-of-travelers" slider
to be a "centi-ln-number-of-travelers"
slider instead, to support a wider range
of choices retaining higher precision
for selecting lower numbers of travelers
and accepting degraded precision for
selecting higher numbers of travelers.

  [Yes, that should be "hecta-" instead
  of "centi-", but US users with their
  British system of weights and measures
  still in common use are so metrically
  challenged most would not even
  recognize the "hecta-" prefix, so an
  incorrect but intuitive choice was
  implemented.  I'm eager to listen to
  demands to do it correctly, instead.]

Implemented intended functionality for
some additional existing interface
buttons "invert?" and "ordered
crossover?" (see the "what is the demo
status" remarks below, near the bottom
of this document).

Added color coding for turtles in the
patch area circular histogram to display
success at finding a better genome (or
alternately resignation at accepting a
worser genome, when simulated annealing
is enabled).

Added Output window lines from "prepare"
to show the number of travelers, the
number of towns, and the number of
different circuits possible through the
given number of towns, so the user can
see how hard the problem being addressed
really is.

Added enough documentation to this
information window to completely counter
any attempt at meaningful understanding.

****************************************
Credits:
****************************************

========================================
Who inflicted this mess on us poor
defenseless onlookers, anyway?
========================================

Kent Paul Dolan, xanthian@well.com, did
it with his little keyboard and way, way
too much free time on his hands.  Find
this geezer a job before he demos again!

========================================
Who inspired this project?
========================================

I've been playing with the TSP for about
thirty years now, but a specific web
offering inspired this renewed effort
and sent me out to learn more about the
problem from Web resources.

That offering came from Scott Robert
Ladd, noted evolutionary algorithms
programming textbook author and
proprietor of

http://www.coyotegulch.com/

from where a wealth of tutorial
information and free software can be had.

========================================
Where did you get the algorithms?
========================================

My take on ordered crossover is not the
same as the one Scott Robert Ladd
defines at his site mentioned above,
because I take advantage of the fact
that a permutation genome is invariant
under rotation or reversal of the
logical ring stored in its physical
array vector, but I first found the
concept of an ordered crossover at all
at his site.

The swap heuristic is the one Scott
defines as a mutator, but is used here
as a self-standing heuristic rather
than as a modifier to other heuristics
as in Scott's "Traveller 1.2.1".

The invert heuristic is written from
Scott's description.

The nexper ("next permutation")
procedure to produce all the
permutations, one per call, of a list
of numbers, is a blind port of icky
FORTRAN 66 code found at:

http://www.cs.sunysb.edu/~algorith/implement/wilf/distrib/processed/nexper_2.f

which I had to translate from spagetti
code into structured FORTRAN code
before I could port it to StarLogo
code, "blind" because I still haven't a
clue how it works, but mine now works
the same way.

The inver-over procedure was written
from a description in the technical
report:

"Inver-over Operator for the TSP" by
Guo Tau and Zbigniew Michalewicz

available here:

ftp://ftp.uncc.edu/coe/evol/p44.ps

The permute and move sublist heuristics
are my own inventions, though probably
invented also by lots of others,
they're pretty obvious.

The anneal, tournament, and tabu
metaheuristics are mine in all their
design and coding details, so they
might not be what others expect, but
the concepts were first invented by
others, and my code was inspired by
many Usenet discussions and some Web
research.

For those interested in further
information, more links for the
Traveling Salesman Problem and for Tabu
Search are available on my
Computational Complexity links page
at:

http://www.well.com/user/xanthian/link_pages/Programming/Paradigms/ComputationalComplexity.html
`SLPlot`
title "Untitled Graph"
xlabel "Time"
ylabel ""
xmin 0
xmax 1000
ymin 0
ymax 1000
pen 1 0 15
pen 2 0 25
pen 3 0 35
pen 4 0 45
pen 5 0 55
pen 6 0 65
pen 7 0 75
pen 8 0 85
pen 9 0 95
pen 10 0 105



`interface`
SLButton
turtle-or-observer? observer
top-left 90 5
width-height 80 22
name "execute"
line-to-run "go"
forever? true
button-number 3
show-name? true

SLButton
turtle-or-observer? observer
top-left 65 5
width-height 80 22
name "prepare"
line-to-run "setup"
forever? false
button-number 2
show-name? true

SLButton
turtle-or-observer? observer
top-left 35 5
width-height 80 22
name "reset"
line-to-run "startup"
forever? false
button-number 20
show-name? true

SLTextWidget
top-left 270 90
width-height 155 30
textwidth 151
linenums 1
words "[ * means not implemented yet ]"
textwidget-number 7

SLButton
turtle-or-observer? observer
top-left 115 5
width-height 80 22
name "draw all once"
line-to-run "setdraw_all_once_p true"
forever? false
button-number 4
show-name? true

SLTextWidget
top-left 35 270
width-height 127 30
textwidth 123
linenums 1
words "Toggles for Metaheuristics"
textwidget-number 2

SLButton
turtle-or-observer? observer
top-left 90 270
width-height 165 22
name "tournament?"
line-to-run "settournament_p (not tournament_p) print se \"tournament? =>\" tournament_p"
forever? false
button-number 6
show-name? true

SLButton
turtle-or-observer? observer
top-left 115 270
width-height 165 22
name "tabu?"
line-to-run "settabu_p (not tabu_p) print se \"tabu? =>\" tabu_p"
forever? false
button-number 7
show-name? true

SLTextWidget
top-left 140 5
width-height 104 30
textwidth 100
linenums 1
words "Toggles for Heuristics"
textwidget-number 1

SLButton
turtle-or-observer? observer
top-left 245 5
width-height 80 22
name "permute?"
line-to-run "setpermute_p (not permute_p) print se \"permute? =>\" permute_p"
forever? false
button-number 11
show-name? true

SLButton
turtle-or-observer? observer
top-left 270 5
width-height 80 22
name "move sublist?"
line-to-run "setmove_sublist_p (not move_sublist_p) print se \"move sublist? =>\" move_sublist_p"
forever? false
button-number 17
show-name? true

SLTextWidget
top-left 140 270
width-height 112 30
textwidth 108
linenums 1
words "Toggles for Debugging"
textwidget-number 5

SLTextWidget
top-left 245 270
width-height 132 30
textwidth 128
linenums 1
words "Toggles for Sighted Cheats"
textwidget-number 6

SLButton
turtle-or-observer? observer
top-left 170 270
width-height 165 22
name "want debugging?"
line-to-run "setwant_debugging_p (not want_debugging_p) print se se \"want_debugging? =>\" want_debugging_p \"\nNo debugging prints currently in project.\""
forever? false
button-number 18
show-name? true

SLButton
turtle-or-observer? observer
top-left 195 355
width-height 80 22
name "see toggles"
line-to-run "print-toggles"
forever? false
button-number 21
show-name? true

SLButton
turtle-or-observer? observer
top-left 195 270
width-height 80 22
name "fail?"
line-to-run "setfail_p (not fail_p) print se se \"fail? =>\" fail_p \"\nNo failing not-understood case currently in project.\""
forever? false
button-number 19
show-name? true

SLButton
turtle-or-observer? observer
top-left 220 270
width-height 165 22
name "draw all always?"
line-to-run "setdraw_all_always_p (not draw_all_always_p) print se \"draw all always? =>\" draw_all_always_p "
forever? false
button-number 24
show-name? true

SLTextWidget
top-left 314 182
width-height 171 130
textwidth 167
linenums 6
words "Canvas upper: circular histogram.\nCanvas lower: best circuit so far.\nCanvas left: \"average remaining\nannealing limit\" histogram (folded).\nEnjoy!  xanthian@well.com\n[See the information window too!]"
textwidget-number 4

SLButton
turtle-or-observer? observer
top-left 170 5
width-height 80 22
name "swap?"
line-to-run "setswap_p (not swap_p) print se \"swap? =>\" swap_p"
forever? false
button-number 8
show-name? true

SLButton
turtle-or-observer? observer
top-left 195 5
width-height 80 22
name "invert?"
line-to-run "setinvert_p (not invert_p) print se \"invert? =>\" invert_p"
forever? false
button-number 9
show-name? true

SLTextWidget
top-left 295 4
width-height 169 150
textwidth 165
linenums 7
words "Blind Traveling Salesman Demo.\n1) Open plot and output windows.\n2) Set travelers and towns.\n3) Press reset, prepare, let it finish.\n4) Choose [Meta]Heuristics.\n5) Press execute.\n6) May toggle heuristics during run."
textwidget-number 3

SLButton
turtle-or-observer? observer
top-left 170 90
width-height 165 22
name "ordered crossover?"
line-to-run "setcrossover_ordered_p (not crossover_ordered_p) print se \"crossover ordered? =>\" crossover_ordered_p"
forever? false
button-number 12
show-name? true

SLButton
turtle-or-observer? observer
top-left 295 270
width-height 165 22
name "* local optimization?"
line-to-run "set local_optimization_p (not local_optimization_p) print se \"local optimization? =>\" local_optimization_p"
forever? false
button-number 23
show-name? true

SLButton
turtle-or-observer? observer
top-left 270 270
width-height 165 22
name "* minimal spanning tree start?"
line-to-run "set minimal_spanning_tree_start_p (not minimal_spanning_tree_start_p) print se \"minimal spanning tree start? =>\" minimal_spanning_tree_start_p"
forever? false
button-number 22
show-name? true

SLButton
turtle-or-observer? observer
top-left 65 270
width-height 165 22
name "anneal?"
line-to-run "setanneal_p (not anneal_p) print se \"anneal? =>\" anneal_p"
forever? false
button-number 5
show-name? true

SLButton
turtle-or-observer? observer
top-left 220 5
width-height 80 22
name "inver-over?"
line-to-run "setinver_over_p (not inver_over_p) print se \"inver-over? =>\" inver_over_p"
forever? false
button-number 10
show-name? true

SLMonitor
top-left 90 120
width-height 105 36
name "monitor1"
list-to-run "number-of-travelers"
digits 0
delay 0.1
monitor-number 1
show-name? false

SLMonitor
top-left 130 120
width-height 105 36
name "travelers still busy"
list-to-run "busy-travelers"
digits 0
delay 0.1
monitor-number 2
show-name? true

SLButton
turtle-or-observer? observer
top-left 195 90
width-height 165 22
name "* partial match crossover?"
line-to-run "setcrossover_partial_match_p (not crossover_partial_match_p) print se \"crossover partial match? =>\" crossover_partial_match_p"
forever? false
button-number 13
show-name? true

SLButton
turtle-or-observer? observer
top-left 220 90
width-height 165 22
name "* cyclic crossover?"
line-to-run "setcrossover_cyclic_p (not crossover_cyclic_p) print se \"crossover cyclic? =>\" crossover_cyclic_p"
forever? false
button-number 14
show-name? true

SLButton
turtle-or-observer? observer
top-left 245 90
width-height 165 22
name "* edge preserving crossover?"
line-to-run "setcrossover_edge_preserving_p (not crossover_edge_preserving_p) print se \"crossover edge preserving? =>\" crossover_edge_preserving_p"
forever? false
button-number 15
show-name? true

SLSlider
top-left 35 90
width-height 165 25
name "the number of towns to visit"
variable "number-of-towns"
min-value 4
max-value 150
current-value 15
slider-number 0
show-name? true

SLButton
turtle-or-observer? observer
top-left 65 90
width-height 165 22
name "compute-num-travelers"
line-to-run "how-many-travelers"
forever? true
button-number 16
show-name? false

SLSlider
top-left 5 5
width-height 620 25
name "enable how-many-travelers button, move this slider, watch number-of-travelers monitor for value, ignore value here"
variable "hecta-log10-number-of-travelers"
min-value 0
max-value 700
current-value 205
slider-number 1
show-name? true

SLCanvas
top-left 35 440

`settings`
patch-size 4
num-shapes 256
screen-half-width 22
screen-half-height 45
interface-window-xcor 439
interface-window-ycor 0
interface-window-size 635 430
output-window-xcor 0
output-window-ycor 506
output-window-width 440
output-window-height 489
info-window-xcor 96
info-window-ycor 37
info-window-width 332
info-window-height 419
control-center-xcor 440
control-center-ycor 506
control-center-width 285
control-center-height 415
turtle-command-center-height 150
observer-command-center-height 150
plot-window-xcor 0
plot-window-ycor 0
plot-window-width 440
plot-window-height 506

`string table`
H4sIAAAAAAAAAGNgYGAAABzfRCEEAAAAAAAABA==

`symbol table`
H4sIAAAAAAAAAGNgYGAAABzfRCEEAAAAAAAABA==

`double table`
H4sIAAAAAAAAAGNgYGAAABzfRCEEAAAAAAAABA==

`list table`
H4sIAAAAAAAAAGNgYGAAABzfRCEEAAAAAAAABA==

`observer world`
H4sIAAAAAAAAALWR/07jMAzHDXdXNja2sQF33AmJv5H6DrxJcVPTRkqTKHGYdk9/
roFNPMBVSmV/vv6R2LB5CW2m9EbpMTMyvTzD8XuCypHveRDbwUV0gSN5lRYafFS/
y/kN24FKspmtyTV5bB11GrxqSz7UnPBNMlIWcgbLwfZDHSmNhUnIOayVcCjJ40ie
BX6DRUdt6Xvr+yZqn3lLmWuS+4r7Ay5dCLE2oWh8BTtfxpZSHV6/9LuAdZdw36Bz
TfCGtNgMro8Q3R4PWfEcqrzHqPYlzKyXXqzeApbqNWH6TWQJ848nqHsFq1G0JpfW
yRyUrWBnUshZc0LqKFGnwhruT0LExBZdMyKbQeUNbE+yORhnjfJr+HPi1PXSOdG0
wc8ZbWGG3pMUm7wdVIxtUfsGlqfxKrmFzR7F/jrlO6he0b7n/4SH0Xo7Srkcpe4U
w4nkjYwfY/kFNy4YCQiR7Wj/ItvgVbmfVnam+/7/5x86iRxsywIAAAAAAss=

`patch world`
H4sIAAAAAAAAAH3UycrzYJ7eYSc0iSAEtDBBCy2EMcIYx8iz5UmqMfM8rLspmvSi
6S6SWiQ7HVodUg4hlW6e5/343r8ugW3Zl+7Hu9/in/757//iD7/7q+Z//eEv/vCX
fz4u8vXbxZ/979/97f/8u/t/+Pvf/em9XPyjv/7Lv/kff/irP93Xi3/8+7/+2z/8
/i//5k9fqsWf/Z+/f7RY/JO/O+iH5xaLf/an1z///8cM//fvj06fP1z/IP1zaAWs
hC1hFayGNbAVbA1rYRvYFraD7WEd7AA7wk6wM+wCu8JusDushz1gT9gL9oZ9YANs
lE3z9gvsfoHdL7H7JXa/wu5X2P0au19j9xvsfoPdb7H77fwu/TZ+o6/WhVbAStgS
VsFqWANbwdawFraBbWE72B7WwQ6wI+wEO8MusCvsBrvDetgD9oS9YG/YBzbARtk0
b7/A7hfY/RK7X2L3K+x+hd2vsfs1dr/B7jfY/Ra7387vcuuKYLeAFbAStoRVsBrW
wFawNayFbWBb2A62h3WwA+wIO8HOsAvsCrvB7rAe9oA9YS/YG/aBDbBRNs1bal1o
2KXWhYZdal1o2KXWhYZdal1o2KXWhTa/y60rg90CVsBK2BJWwWpYA1vB1rAWtoFt
YTvYHtbBDrAj7AQ7wy6wK+wGu8N62AP2hL1gb9gHNsBG2TRvqXWhYZdaFxp2qXWh
YZdaFxp2qXWhYZdaF9r8LrduGewWsAJWwpawClbDGtgKtoa1sA1sC9vB9rAOdoAd
YSfYGXaBXWE32B3Wwx6wJ+wFe8M+sAE2yqZ5S60LDbvUutCwS60LDbvUutCwS60L
DbvUutDmd7l1VbBbwApYCVvCKlgNa2Ar2BrWwjawLWwH28M62AF2hJ1gZ9gFdoXd
YHdYD3vAnrAX7A37wAbYKJvmLbUuNOxS60LDLrUuNOxS60LDLrUuNOxS60Kb3+XW
1cFuAStgJWwJq2A1rIGtYGtYC9vAtrAdbA/rYAfYEXaCnWEX2BV2g91hPewBe8Je
sDfsAxtgo2yat9S60LBLrQsNu9S60LBLrQsNu9S60LBLrQttfpdb1wS7BayAlbAl
rILVsAa2gq1hLWwD28J2sD2sgx1gR9gJdoZdYFfYDXaH9bAH7Al7wd6wD2yAjbJp
3lLrQsMutS407FLrQsMutS407FLrQsMutS60+V1u3SrYLWAFrIQtYRWshjWwFWwN
a2Eb2Ba2g+1hHewAO8JOsDPsArvCbrA7rIc9YE/YC/aGfWADbJRN85ZaFxp2qXWh
YZdaFxp2qXWhYZdaFxp2qXWhze9y69bBbgErYCVsCatgNayBrWBrWAvbwLawHWwP
62AH2BF2gp1hF9gVdoPdYT3sAXvCXrA37AMbYKNsmrfUutCwS60LDbvUutCwS60L
DbvUutCwS60LbX6XW9cGuwWsgJWwJayC1bAGtoKtYS1sA9vCdrA9rIMdYEfYCXaG
XWBX2A12h/WwB+wJe8HesA9sgI2yad5S60LDLrUuNOxS60LDLrUuNOxS60LDLrUu
tPldbt0m2C1gBayELWEVrIY1sBVsDWthG9gWtoPtYR3sADvCTrAz7AK7wm6wO6yH
PWBP2Av2hn1gA2yUTfOWWhcadql1oWGXWhcadql1oWGXWhcadql1oc3vcuu2wW4B
K2AlbAmrYDWsga1ga1gL28C2sB1sD+tgB9gRdoKdYRfYFXaD3WE97AF7wl6wN+wD
G2CjbJq31LrQsEutCw271LrQsEutCw271LrQsEutC21+l1u3C3YLWAErYUtYBath
DWwFW8Na2Aa2he1ge1gHO8COsBPsDLvArrAb7A7rYQ/YE/aCvWEf2AAbZdO8pdaF
hl1qXWjYpdaFhl1qXWjYpdaFhl1qXWjzu9y6fbBbwApYCVvCKlgNa2Ar2BrWwjaw
LWwH28M62AF2hJ1gZ9gFdoXdYHdYD3vAnrAX7A37wAbYKJvmLbUuNOxS60LDLrUu
NOxS60LDLrUuNOxS60Kb3+XWdcFuAStgJWwJq2A1rIGtYGtYC9vAtrAdbA/rYAfY
EXaCnWEX2BV2g91hPewBe8JesDfsAxtgo2yat9S60LBLrQsNu9S60LBLrQsNu9S6
0LBLrQttfpdbdwh2C1gBK2FLWAWrYQ1sBVvDWtgGtoXtYHtYBzvAjrAT7Ay7wK6w
G+wO62EP2BP2gr1hH9gAG2XTvKXWhYZdal1o2KXWhYZdal1o2KXWhYZdal1o87vc
umOwW8AKWAlbwipYDWtgK9ga1sI2sC1sB9vDOtgBdoSdYGfYBXaF3WB3WA97wJ6w
F+wN+8AG2Cib5i21LjTsUutCwy61LjTsUutCwy61LjTsUutCm9/l1p2C3QJWwErY
ElbBalgDW8HWsBa2gW1hO9ge1sEOsCPsBDvDLrAr7Aa7w3rYA/aEvWBv2Ac2wEbZ
NG+pdaFhl1oXGnapdaFhl1oXGnapdaFhl1oX2vwut+4c7BawAlbClrAKVsMa2Aq2
hrWwDWwL28H2sA52gB1hJ9gZdoFdYTfYHdbDHrAn7AV7wz6wATbKpnlLrQsNu9S6
0LBLrQsNu9S60LBLrQsNu9S60OZ3uXWXYLeAFbAStoRVsBrWwFawNayFbWBb2A62
h3WwA+wIO8HOsAvsCrvB7rAe9oA9YS/YG/aBDbBRNs1bal1o2KXWhYZdal1o2KXW
hYZdal1o2KXWhTa/y627BrsFrICVsCWsgtWwBraCrWEtbAPbwnawPayDHWBH2Al2
hl1gV9gNdof1sAfsCXvB3rAPbICNsmneUutCwy61LjTsUutCwy61LjTsUutCwy61
LrT5XW7dLdgtYAWshC1hFayGNbAVbA1rYRvYFraD7WEd7AA7wk6wM+wCu8JusDus
hz1gT9gL9oZ9YANslE3zlloXGnapdaFhl1oXGnapdaFhl1oXGnapdaHN73Lr7sFu
AStgJWwJq2A1rIGtYGtYC9vAtrAdbA/rYAfYEXaCnWEX2BV2g91hPewBe8JesDfs
Axtgo2yat9S60LBLrQsNu9S60LBLrQsNu9S60LBLrQttfpdb1we7BayAlbAlrILV
sAa2gq1hLWwD28J2sD2sgx1gR9gJdoZdYFfYDXaH9bAH7Al7wd6wD2yAjbJp3lLr
QsMutS407FLrQsMutS407FLrQsMutS60+V1u3SPYLWAFrIQtYRWshjWwFWwNa2Eb
2Ba2g+1hHewAO8JOsDPsArvCbrA7rIc9YE/YC/aGfWADbJRN85ZaFxp2qXWhYZda
Fxp2qXWhYZdaFxp2qXWhze9y657BbgErYCVsCatgNayBrWBrWAvbwLawHWwP62AH
2BF2gp1hF9gVdoPdYT3sAXvCXrA37AMbYKNsmrfUutCwS60LDbvUutCwS60LDbvU
utCwS60LbX6XW/cKdgtYASthS1gFq2ENbAVbw1rYBraF7WB7WAc7wI6wE+wMu8Cu
sBvsDuthD9gT9oK9YR/YABtl07yl1oWGXWpdaNil1oWGXWpdaNil1oWGXWpdaPO7
3Lp3sFvAClgJW8IqWA1rYCvYGtbCNrAtbAfbwzrYAXaEnWBn2AV2hd1gd1gPe8Ce
sBfsDfvABtgom+YttS407FLrQsMutS407FLrQsMutS407FLrQpvf5dZ9gt0CVsBK
2BJWwWpYA1vB1rAWtoFtYTvYHtbBDrAj7AQ7wy6wK+wGu8N62AP2hL1gb9gHNsBG
2TRvqXWhYZdaFxp2qXWhYZdaFxp2qXWhYZdaF9r8LrduCHYLWAErYUtYBathDWwF
W8Na2Aa2he1ge1gHO8COsBPsDLvArrAb7A7rYQ/YE/aCvWEf2AAbZdO8pdaFhl1q
XWjYpdaFhl1qXWjYpdaFhl1qXWjzu9y6MdgtYAWshC1hFayGNbAVbA1rYRvYFraD
7WEd7AA7wk6wM+wCu8JusDushz1gT9gL9oZ9YANslE3zlloXGnapdaFhl1oXGnap
daFhl1oXGnapdaHN775aN33fLWAFrIQtYRWshjWwFWwNa2Eb2Ba2g+1hHewAO8JO
sDPsArvCbrA7rIc9YE/YC/aGfWADbJRN85ZbFxl2uXWRYZdbFxl2uXWRYZdbFxl2
uXWRze9y637xM/3QusgKWAlbwipYDWtgK9ga1sI2sC1sB9vDOtgBdoSdYGfYBXaF
3WB3WA97wJ6wF+wN+8AG2Cib5i21LjTsUutCwy61LjTsUutCwy61LjTsUutCm999
tW76vlvAClgJW8IqWA1rYCvYGtbCNrAtbAfbwzrYAXaEnWBn2AV2hd1gd1gPe8Ce
sBfsDfvABtgom+Ytty4y7HLrIsMuty4y7HLrIsMuty4y7HLrIpvf5db98mf6oXWR
FbAStoRVsBrWwFawNayFbWBb2A62h3WwA+wIO8HOsAvsCrvB7rAe9oA9YS/YG/aB
DbBRNs1bal1o2KXWhYZdal1o2KXWhYZdal1o2KXWhTa/+2rd9H23gBWwEraEVbAa
1sBWsDWshW1gW9gOtod1sAPsCDvBzrAL7Aq7we6wHvaAPWEv2Bv2gQ2wUTbNW25d
ZNjl1kWGXW5dZNjl1kWGXW5dZNjl1kU2v8ut+9XP9EPrIitgJWwJq2A1rIGtYGtY
C9vAtrAdbA/rYAfYEXaCnWEX2BV2g91hPewBe8JesDfsAxtgo2yat9S60LBLrQsN
u9S60LBLrQsNu9S60LBLrQttfvfVuun7bgErYCVsCatgNayBrWBrWAvbwLawHWwP
62AH2BF2gp1hF9gVdoPdYT3sAXvCXrA37AMbYKNsmrfcusiwy62LDLvcusiwy62L
DLvcusiwy62LbH6XW/frn+mH1kVWwErYElbBalgDW8HWsBa2gW1hO9ge1sEOsCPs
BDvDLrAr7Aa7w3rYA/aEvWBv2Ac2wEbZNG+pdaFhl1oXGnapdaFhl1oXGnapdaFh
l1oX2vzuq3XT990CVsBK2BJWwWpYA1vB1rAWtoFtYTvYHtbBDrAj7AQ7wy6wK+wG
u8N62AP2hL1gb9gHNsBG2TRvuXWRYZdbFxl2uXWRYZdbFxl2uXWRYZdbF9n8Lrfu
Nz/TD62LrICVsCWsgtWwBraCrWEtbAPbwnawPayDHWBH2Al2hl1gV9gNdof1sAfs
CXvB3rAPbICNsmneUutCwy61LjTsUutCwy61LjTsUutCwy61LrT53Vfrpu+7BayA
lbAlrILVsAa2gq1hLWwD28J2sD2sgx1gR9gJdoZdYFfYDXaH9bAH7Al7wd6wD2yA
jbJp3nLrIsMuty4y7HLrIsMuty4y7HLrIsMuty6y+V1u3W9/ph9aF1kBK2FLWAWr
YQ1sBVvDWtgGtoXtYHtYBzvAjrAT7Ay7wK6wG+wO62EP2BP2gr1hH9gAG2XTvKXW
hYZdal1o2KXWhYZdal1o2KXWhYZdal1o87uv1k3fdwtYASthS1gFq2ENbAVbw1rY
BraF7WB7WAc7wI6wE+wMu8CusBvsDuthD9gT9oK9YR/YABtl07zl1kWGXW5dZNjl
1kWGXW5dZNjl1kWGXW5dZPO73Lp/8TP90LrIClgJW8IqWA1rYCvYGtbCNrAtbAfb
wzrYAXaEnWBn2AV2hd1gd1gPe8CesBfsDfvABtgom+YttS407FLrQsMutS407FLr
QsMutS407FLrQpvffbVu+r5bwApYCVvCKlgNa2Ar2BrWwjawLWwH28M62AF2hJ1g
Z9gFdoXdYHdYD3vAnrAX7A37wAbYKJvmLbcuMuxy6yLDLrcuMuxy6yLDLrcuMuxy
6yKb3+XW/cuf6YfWRVbAStgSVsFqWANbwdawFraBbWE72B7WwQ6wI+wEO8MusCvs
BrvDetgD9oS9YG/YBzbARtk0b6l1oWGXWhcadql1oWGXWhcadql1oWGXWhfa/O6r
ddP33QJWwErYElbBalgDW8HWsBa2gW1hO9ge1sEOsCPsBDvDLrAr7Aa7w3rYA/aE
vWBv2Ac2wEbZNG+5dZFhl1sXGXa5dZFhl1sXGXa5dZFhl1sX2fwut+5f/Uw/tC6y
AlbClrAKVsMa2Aq2hrWwDWwL28H2sA52gB1hJ9gZdoFdYTfYHdbDHrAn7AV7wz6w
ATbKpnlLrQsNu9S60LBLrQsNu9S60LBLrQsNu9S60OZ3X62bvu8WsAJWwpawClbD
GtgKtoa1sA1sC9vB9rAOdoAdYSfYGXaBXWE32B3Wwx6wJ+wFe8M+sAE2yqZ5y62L
DLvcusiwy62LDLvcusiwy62LDLvcusjmd7l1//pn+qF1kRWwEraEVbAa1sBWsDWs
hW1gW9gOtod1sAPsCDvBzrAL7Aq7we6wHvaAPWEv2Bv2gQ2wUTbNW2pdaNil1oWG
XWpdaNil1oWGXWpdaNil1oU2v/tq3fR9t4AVsBK2hFWwGtbAVrA1rIVtYFvYDraH
dbAD7Ag7wc6wC+wKu8HusB72gD1hL9gb9oENsFE2zVtuXWTY5dZFhl1uXWTY5dZF
hl1uXWTY5dZFNr/Lrfs3P9MPrYusgJWwJayC1bAGtoKtYS1sA9vCdrA9rIMdYEfY
CXaGXWBX2A12h/WwB+wJe8HesA9sgI2yad5S60LDLrUuNOxS60LDLrUuNOxS60LD
LrUutPndV+um77sFrICVsCWsgtWwBraCrWEtbAPbwnawPayDHWBH2Al2hl1gV9gN
dof1sAfsCXvB3rAPbICNsmnecusiwy63LjLscusiwy63LjLscusiwy63LrL5XW7d
v/2ZfmhdZAWshC1hFayGNbAVbA1rYRvYFraD7WEd7AA7wk6wM+wCu8JusDushz1g
T9gL9oZ9YANslE3zlloXGnapdaFhl1oXGnapdaFhl1oXGnapdaHN775aN33fLWAF
rIQtYRWshjWwFWwNa2Eb2Ba2g+1hHewAO8JOsDPsArvCbrA7rIc9YE/YC/aGfWAD
bJRN85ZbFxl2uXWRYZdbFxl2uXWRYZdbFxl2uXWRze9y6/7dz/RD6yIrYCVsCatg
NayBrWBrWAvbwLawHWwP62AH2BF2gp1hF9gVdoPdYT3sAXvCXrA37AMbYKNsmrfU
utCwS60LDbvUutCwS60LDbvUutCwS60LbX731brp+24BK2AlbAmrYDWsga1ga1gL
28C2sB1sD+tgB9gRdoKdYRfYFXaD3WE97AF7wl6wN+wDG2CjbJq33LrIsMutiwy7
3LrIsMutiwy73LrIsMuti2x+l1v373+mH1oXWQErYUtYBathDWwFW8Na2Aa2he1g
e1gHO8COsBPsDLvArrAb7A7rYQ/YE/aCvWEf2AAbZdO8pdaFhl1qXWjYpdaFhl1q
XWjYpdaFhl1qXWjzu6/WTd93C1gBK2FLWAWrYQ1sBVvDWtgGtoXtYHtYBzvAjrAT
7Ay7wK6wG+wO62EP2BP2gr1hH9gAG2XTvOXWRYZdbl1k2OXWRYZdbl1k2OXWRYZd
bl1k87vcuv/wM/3QusgKWAlbwipYDWtgK9ga1sI2sC1sB9vDOtgBdoSdYGfYBXaF
3WB3WA97wJ6wF+wN+8AG2Cib5i21LjTsUutCwy61LjTsUutCwy61LjTsUutCm999
tW76vlvAClgJW8IqWA1rYCvYGtbCNrAtbAfbwzrYAXaEnWBn2AV2hd1gd1gPe8Ce
sBfsDfvABtgom+Ytty4y7HLrIsMuty4y7HLrIsMuty4y7HLrIpvf5db9x5/ph9ZF
VsBK2BJWwWpYA1vB1rAWtoFtYTvYHtbBDrAj7AQ7wy6wK+wGu8N62AP2hL1gb9gH
NsBG2TRvqXWhYZdaFxp2qXWhYZdaFxp2qXWhYZdaF9r87qt14/fdAlbAStgSVsFq
WANbwdawFraBbWE72B7WwQ6wI+wEO8MusCvsBrvDetgD9oS9YG/YBzbARtk0b7l1
kWGXWxcZdrl1kWGXWxcZdrl1kWGXWxfZ/O6rddP33QJWwErYElbBalgDW8HWsBa2
gW1hO9ge1sEOsCPsBDvDLrAr7Aa7w3rYA/aEvWBv2Ac2wEbZNG+5dZFhl1sXGXa5
dZFhl1sXGXa5dZFhl1sX2fzuq3V//L5bwApYCVvCKlgNa2Ar2BrWwjawLWwH28M6
2AF2hJ1gZ9gFdoXdYHdYD3vAnrAX7A37wAbYKJvmLbcuMuxy6yLDLrcuMuxy6yLD
LrcuMuxy6yKb3+XW/aef6YfWRVbAStgSVsFqWANbwdawFraBbWE72B7WwQ6wI+wE
O8MusCvsBrvDetgD9oS9YG/YBzbARtk0b6l1oWGXWhcadql1oWGXWhcadql1oWGX
Whfa/O6rdeP33QJWwErYElbBalgDW8HWsBa2gW1hO9ge1sEOsCPsBDvDLrAr7Aa7
w3rYA/aEvWBv2Ac2wEbZNG+5dZFhl1sXGXa5dZFhl1sXGXa5dZFhl1sX2fzuq3XT
990CVsBK2BJWwWpYA1vB1rAWtoFtYTvYHtbBDrAj7AQ7wy6wK+wGu8N62AP2hL1g
b9gHNsBG2TRvuXWRYZdbFxl2uXWRYZdbFxl2uXWRYZdbF9n87qt1f/y+W8AKWAlb
wipYDWtgK9ga1sI2sC1sB9vDOtgBdoSdYGfYBXaF3WB3WA97wJ6wF+wN+8AG2Cib
5i23LjLscusiwy63LjLscusiwy63LjLscusim9/l1v3nn+mH1kVWwErYElbBalgD
W8HWsBa2gW1hO9ge1sEOsCPsBDvDLrAr7Aa7w3rYA/aEvWBv2Ac2wEbZNG+pdaFh
l1oXGnapdaFhl1oXGnapdaFhl1oX2vzuq3Xj990CVsBK2BJWwWpYA1vB1rAWtoFt
YTvYHtbBDrAj7AQ7wy6wK+wGu8N62AP2hL1gb9gHNsBG2TRvuXWRYZdbFxl2uXWR
YZdbFxl2uXWRYZdbF9n87qt10/fdAlbAStgSVsFqWANbwdawFraBbWE72B7WwQ6w
I+wEO8MusCvsBrvDetgD9oS9YG/YBzbARtk0b7l1kWGXWxcZdrl1kWGXWxcZdrl1
kWGXWxfZ/O6rdX/8vlvAClgJW8IqWA1rYCvYGtbCNrAtbAfbwzrYAXaEnWBn2AV2
hd1gd1gPe8CesBfsDfvABtgom+Ytty4y7HLrIsMuty4y7HLrIsMuty4y7HLrIpvf
5db9l5/ph9ZFVsBK2BJWwWpYA1vB1rAWtoFtYTvYHtbBDrAj7AQ7wy6wK+wGu8N6
2AP2hL1gb9gHNsBG2TRvqXWhYZdaFxp2qXWhYZdaFxp2qXWhYZdaF9r87qt14/fd
AlbAStgSVsFqWANbwdawFraBbWE72B7WwQ6wI+wEO8MusCvsBrvDetgD9oS9YG/Y
BzbARtk0b7l1kWGXWxcZdrl1kWGXWxcZdrl1kWGXWxfZ/O6rddP33QJWwErYElbB
algDW8HWsBa2gW1hO9ge1sEOsCPsBDvDLrAr7Aa7w3rYA/aEvWBv2Ac2wEbZNG+5
dZFhl1sXGXa5dZFhl1sXGXa5dZFhl1sX2fzuq3V//L5bwApYCVvCKlgNa2Ar2BrW
wjawLWwH28M62AF2hJ1gZ9gFdoXdYHdYD3vAnrAX7A37wAbYKJvmLbcuMuxy6yLD
LrcuMuxy6yLDLrcuMuxy6yKb3+XW/def6YfWRVbAStgSVsFqWANbwdawFraBbWE7
2B7WwQ6wI+wEO8MusCvsBrvDetgD9oS9YG/YBzbARtk0b6l1oWGXWhcadql1oWGX
Whcadql1oWGXWhfa/O6rdeP33QJWwErYElbBalgDW8HWsBa2gW1hO9ge1sEOsCPs
BDvDLrAr7Aa7w3rYA/aEvWBv2Ac2wEbZNG+5dZFhl1sXGXa5dZFhl1sXGXa5dZFh
l1sX2fzuq3XT990CVsBK2BJWwWpYA1vB1rAWtoFtYTvYHtbBDrAj7AQ7wy6wK+wG
u8N62AP2hL1gb9gHNsBG2TRvuXWRYZdbFxl2uXWRYZdbFxl2uXWRYZdbF9n87qt1
f/y+W8AKWAlbwipYDWtgK9ga1sI2sC1sB9vDOtgBdoSdYGfYBXaF3WB3WA97wJ6w
F+wN+8AG2Cib5i23LjLscusiwy63LjLscusiwy63LjLscusim9/l1v23n+mH1kVW
wErYElbBalgDW8HWsBa2gW1hO9ge1sEOsCPsBDvDLrAr7Aa7w3rYA/aEvWBv2Ac2
wEbZNG+pdaFhl1oXGnapdaFhl1oXGnapdaFhl1oX2vzuq3Xj990CVsBK2BJWwWpY
A1vB1rAWtoFtYTvYHtbBDrAj7AQ7wy6wK+wGu8N62AP2hL1gb9gHNsBG2TRvuXWR
YZdbFxl2uXWRYZdbFxl2uXWRYZdbF9n87qt10/fdAlbAStgSVsFqWANbwdawFraB
bWE72B7WwQ6wI+wEO8MusCvsBrvDetgD9oS9YG/YBzbARtk0b7l1kWGXWxcZdrl1
kWGXWxcZdrl1kWGXWxfZ/O6rdX/8vlvAClgJW8IqWA1rYCvYGtbCNrAtbAfbwzrY
AXaEnWBn2AV2hd1gd1gPe8CesBfsDfvABtgom+Ytty4y7HLrIsMuty4y7HLrIsMu
ty4y7HLrIpvf5db995/ph9ZFVsBK2BJWwWpYA1vB1rAWtoFtYTvYHtbBDrAj7AQ7
wy6wK+wGu8N62AP2hL1gb9gHNsBG2TRvqXWhYZdaFxp2qXWhYZdaFxp2qXWhYZda
F9r87qt14/fdAlbAStgSVsFqWANbwdawFraBbWE72B7WwQ6wI+wEO8MusCvsBrvD
etgD9oS9YG/YBzbARtk0b7l1kWGXWxcZdrl1kWGXWxcZdrl1kWGXWxfZ/O6rddP3
3QJWwErYElbBalgDW8HWsBa2gW1hO9ge1sEOsCPsBDvDLrAr7Aa7w3rYA/aEvWBv
2Ac2wEbZNG+5dZFhl1sXGXa5dZFhl1sXGXa5dZFhl1sX2fzuq3V//L5bwApYCVvC
KlgNa2Ar2BrWwjawLWwH28M62AF2hJ1gZ9gFdoXdYHdYD3vAnrAX7A37wAbYKJvm
LbcuMuxy6yLDLrcuMuxy6yLDLrcuMuxy6yKb3/0/fug0NlHAAQAAAcBR

`turtle world`
H4sIAAAAAAAAAD2OPQ/CIBCGT1tav+Lk6ODg5OCgDo7+lGK5lCYECJxWf4U/Wa/Y
9BKS5wnvywHrih6BDO4iScLqBuN8oDBoG9LMVxD3gKgY91B648ijZTmCqJ1xgXEL
+btOtIJlemxsX2DGceU669lOIKKWHhkPkL/+nRyyTru0t4h6SJ6h1ChVaxuWDZ8J
CFKS5PDDjJWjMd3MKcgn7wy9TmHRWtXWklzy7MvTV35JKXsT8AAAAAAAAPA=