Java StarLogo
1.2
`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-zbwho
  output 7
end

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

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

to index-is-in-tree      ;; towns tdata element index
  output 3
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 ( ( 2 * heuristics-enabled ) + 1 )

  ;; one more than twice the number of enabled
  ;; heuristics, so that we go at least two generations
  ;; between use of a genome by an individual traveler, when
  ;; the tabu meta-heuristic is enabled.
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.7 ) )
  ]
  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  ( 1 + int abs random-gaussian 1 ) ]

  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
  set tdata-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-wrapper :biz :boz
  print se se ":biz :boz =>" :biz :boz
  output ( town-distance :biz :boz )
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 fitness seen, 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-ever * 2 )
    )

;; 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.

  set tdata 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))
  set tdata 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.

  set tdata append-zeros tdata 3

;; 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 start out not a member of the minimal spanning tree, when that
;; sighted cheat is used.

   setitem index-is-in-tree                   tdata false

;; 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 sample-minspan
  let [ :zbindex random length minimal-spanning-tree ]
  let [ :some-genome empty-list]
  let [ :lmst length minimal-spanning-tree ]

  repeat :lmst
  [
    if
    (
      not
      member?
      ( zbitem :zbindex minimal-spanning-tree )
      :some-genome 
    )
    [
      set
      :some-genome
      ( lput ( zbitem :zbindex minimal-spanning-tree ) :some-genome )
    ]
    set :zbindex ( ( :zbindex + 1 ) mod :lmst )
  ]

  output :some-genome

end

to init-traveler

  let [:myid who]

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

  set tdata append-zeros        tdata 7

;; Create a name useful in modular arithmetic calculations

  setitem index-zbwho           tdata ( :myid mod number-of-travelers )

  ifelse minimal_spanning_tree_start_p
  [
    setitem index-genome          tdata sample-minspan
  ]
  [
;; 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 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_singles_p
  [
    if debugging [ print "entering permute_singles" ]

    set :trial-genfit permute_singles           :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_singles" ]
  ]


  if permute_a_sublist_p
  [
    if debugging [ print "entering permute_a_sublist" ]

    set :trial-genfit permute_a_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 permute_a_sublist" ]
  ]

  if want_debugging_p [ set debugging_p true ]

  if permute_sublists_p
  [
    if debugging [ print "entering permute_sublists" ]

    set :trial-genfit permute_sublists          :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_sublists" ]
  ]

  if want_debugging_p [ set debugging_p false ]

  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

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_a_sublist :some-genfit

  if not permute_a_sublist_p [ output :some-genfit ]

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

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

;; pick up a sublist of towns from consecutive locations in the genome
;; beginning at a random location expressed as a zero based index.

  let [ :next-zbindex ( random number-of-towns ) ]
  let [ :prior-zbindex ( ( :next-zbindex - 1 ) mod number-of-towns ) ]

;; :prior-zbindex is now a zero based index to the location in the
;; genome before the start of the sublist of towns.

  let [ :prior-town ( zbitem :prior-zbindex :my-genome ) ]

  repeat :my-permutation-count
  [
    set :perm-zbindex-list ( lput :next-zbindex :perm-zbindex-list )
    set :next-zbindex ( ( :next-zbindex + 1 ) mod number-of-towns )
  ]

;; :next-zbindex is now a zero based index to the location in the
;; genome after the end of the sublist of towns.

  let [ :next-town ( zbitem :next-zbindex :my-genome ) ]

  if ( ( length :perm-zbindex-list ) < 2 ) [ output :some-genfit ]

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

;; to gain considerable speed in large problems, we will compute
;; only partial fitnesses of the part of the genome being changed,
;; until the eventual candidate has been found.  Since the first
;; permutation out of nexper is the identity permutation, we just
;; set a worst possible value now and let the :my-genome partial
;; fitness replace it the first time through the loop below.

  let [ :best-partial-fitness worst-possible ]

  let
  [
    :perm-n    length :perm-zbindex-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
  ]

;; fill a list with consecutive integers starting at 1; this is the
;; thing we will actually permute, we will use it via indirection to
;; accomplish permutation of the actual genome alleles.

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


  let [ :partial-fitness 0 ]  ;; just to create this local variable

  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

    ;; start with the edge from the rest of the list into our sublist

    set :partial-fitness
      town-distance
      :prior-town
      (
        zbitem
        ( item ( first :perm-a ) :perm-zbindex-list )
        :my-genome
      )

    ;; do each internal edge, there are only :perm-n minus one of them.

    set :index 0

    repeat ( :perm-n - 1 )
    [
      set :index ( :index + 1 )

      set :partial-fitness
          (
            :partial-fitness
            + 
            (
              town-distance
              (
                zbitem
                (
                  item
                  ( item :index :perm-a )
                  :perm-zbindex-list
                )
                :my-genome
              )
              (
                zbitem
                (
                  item
                  ( item ( :index + 1 ) :perm-a )
                  :perm-zbindex-list
                )
                :my-genome
              )
            )
          )
    ]

    ;; finish with the edge to the rest of the list from out of our
    ;; sublist

    set :partial-fitness
      (
        :partial-fitness
        + 
        (
          town-distance
          (
            zbitem
            ( item ( last :perm-a ) :perm-zbindex-list )
            :my-genome
          )
          :next-town
        )
      )

    ;; Do all the rest of the work only if this was a winning fitness.
    ;; Because these towns are always written to the same positions in
    ;; the genome, we can just write the changes over :best-genome
    ;; directly.

    if ( :partial-fitness < :best-partial-fitness )
    [
      set :index 0

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

    ;; this is our loop exit condition -- no more permutations are
    ;; left to evaluate

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

end

to permute_singles :some-genfit

  if not permute_singles_p [ output :some-genfit ]

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

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

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

  if ( (length :perm-zbindex-list) < 2 ) [ output :some-genfit ]

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

  let [ :best-partial-fitness worst-possible ]

  let
  [
    :perm-n length :perm-zbindex-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
  ]

;; Fill a list with perm-n consecutive numbers starting at 1; this list
;; is what we will actually permute, other permutations will be done by
;; indirection using this list.

  ;; this variable is created and used here, reused in loop below.
  let [ :index 0 ]

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

  let [ :partial-fitness 0 ] ;; just to create this local variable once
                             ;; outside the loop.
  let [ :prior-town      0 ] ;; ditto
  let [ :this-town       0 ] ;; ditto
  let [ :next-town       0 ] ;; ditto
  let [ :i-temp          0 ] ;; ditto

  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     copy-list 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

    set :partial-fitness 0

    set :index 0

    repeat :perm-n
    [
      set :index ( :index + 1 )

;; Because we will measure the distance from both ends if one of the
;; connecting towns is also on our list of towns being permuted,  we
;; must detect that situation and halve the contribution in that case,
;; which makes this a bit of a mess.

      set
      :this-town
      (
        zbitem
        ( item ( item :index :perm-a ) :perm-zbindex-list )
        :my-genome
      )

      set :i-temp ( item :index :perm-zbindex-list )
      set :i-temp ( ( :i-temp - 1 ) mod number-of-towns )

      ifelse member? :i-temp :perm-zbindex-list
      [

        set :i-temp ( item :index :perm-zbindex-list )
        set :i-temp ( ( :i-temp - 1 ) mod number-of-towns )
        set :i-temp position :i-temp :perm-zbindex-list
        set :i-temp ( item :i-temp :perm-a )
        set :i-temp ( item :i-temp :perm-zbindex-list )
        set :prior-town ( zbitem :i-temp :my-genome )

        set
        :partial-fitness
        (
          :partial-fitness
          +
          ( ( town-distance :prior-town :this-town ) / 2 )
        )

      ]
      [
        set :i-temp ( item :index :perm-zbindex-list )
        set :i-temp ( ( :i-temp - 1 ) mod number-of-towns )
        set :prior-town ( zbitem :i-temp :my-genome )

        set
        :partial-fitness
        ( :partial-fitness + ( town-distance :prior-town :this-town ) )

      ]

      set :i-temp ( item :index :perm-zbindex-list )
      set :i-temp ( ( :i-temp + 1 ) mod number-of-towns )

      ifelse member? :i-temp :perm-zbindex-list
      [

        set :i-temp ( item :index :perm-zbindex-list )
        set :i-temp ( ( :i-temp + 1 ) mod number-of-towns )
        set :i-temp position :i-temp :perm-zbindex-list
        set :i-temp ( item :i-temp :perm-a )
        set :i-temp ( item :i-temp :perm-zbindex-list )
        set :next-town ( zbitem :i-temp :my-genome )

        set
        :partial-fitness
        (
          :partial-fitness
          +
          ( ( town-distance :this-town :next-town ) / 2 )
        )

      ]
      [
        set :i-temp ( item :index :perm-zbindex-list )
        set :i-temp ( ( :i-temp + 1 ) mod number-of-towns )
        set :next-town ( zbitem :i-temp :my-genome )

        set
        :partial-fitness
        ( :partial-fitness + ( town-distance :this-town :next-town ) )

      ]
    ]

;; If we found a better :partial-fitness, write the latest arrangement
;; of the towns directly onto :best-genome in the appropriate slots;
;; this will be the only part of :best-genome that is modified from
;; :my-genome.

    if ( :partial-fitness < :best-partial-fitness )
    [
      set :index 0

      repeat :perm-n
      [
        set :index ( :index + 1 )

        zbsetitem
        (item :index :perm-zbindex-list)
        :best-genome
        (
          zbitem
          (item (item :index :perm-a) :perm-zbindex-list)
          :my-genome
        )

      ]

      set :best-partial-fitness :partial-fitness
    ]

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

end

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

  if (debugging) [ print "nexper: enter" ]

  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 (debugging) [ print se ":my-n =>"    :my-n    ]
  if (debugging) [ print se ":my-a =>"    :my-a    ]
  if (debugging) [ print se ":my-mtc =>"  :my-mtc  ]
  if (debugging) [ print se ":my-even =>" :my-even ]

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

    if (debugging) [ print "nexper: first pass" ]

    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 (debugging) [ print "nexper: subsequent pass" ]

  if ( :my-even )
  [
    if (debugging) [ print "nexper: even logic" ]

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

    if (debugging) [ print "nexper: even logic first if" ]

    if
    (
      ( not ( 1 = ( item :my-n :my-a ) ) )
    )
    [
      if (debugging) [ print "nexper: even logic first.a output" ]
      output se list :my-n :my-a list :my-mtc :my-even
    ]

    if
    (
      ( not ( ( item 1 :my-a) = ( 2 + ( :my-n mod 2 ) ) ) )
    )
    [
      if (debugging) [ print "nexper: even logic first.b output" ]
      output se list :my-n :my-a list :my-mtc :my-even
    ]

;; This if test had to be split into the the above two if tests because
;; the turtle stack overflowed from the complexity of this statement.
;; Yuk!

;;    if
;;    (
;;      ( not ( 1 = ( item :my-n :my-a ) ) )
;;      or
;;      ( not ( ( item 1 :my-a) = ( 2 + ( :my-n mod 2 ) ) ) )
;;    )
;;    [
;;      if (debugging) [ print "nexper: even logic first output" ]
;;      output se list :my-n :my-a list :my-mtc :my-even
;;    ]

    if (debugging) [ print "nexper: even logic second if" ]

    if ( :my-n <= 3 )
    [
      set :my-mtc false
      if (debugging) [ print "nexper: even logic second output" ]
      output se list :my-n :my-a list :my-mtc :my-even
    ]

    set :i 0
    repeat (:my-n - 3)
    [
      set :i ( :i + 1 )

      if (debugging) [ print "nexper: even logic third if" ]

      if
      (
        ( item (:i + 1) :my-a )
        !=
        ( 1 + ( item :i :my-a ) )
      )
      [
        if (debugging) [ print "nexper: even logic third output" ]
        output se list :my-n :my-a list :my-mtc :my-even
      ]

    ]

    set :my-mtc false

    if (debugging) [ print "nexper: even logic fourth output" ]
    output se list :my-n :my-a list :my-mtc :my-even

  ]

  if (debugging) [ print "nexper: odd logic" ]

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

  repeat ( :my-n - 1 )
  [

    if (debugging) [ print "nexper: odd logic first if" ]

    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 (debugging) [ print "nexper: odd logic second if" ]

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

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

      if (debugging) [ print "nexper: odd logic third if" ]

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

  ]

  if (debugging) [ print "nexper: odd logic fourth if" ]

  if ( not :missed )
  [
    set :my-mtc false

    if (debugging) [ print "nexper: odd logic first output" ]

    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 (debugging) [ print "nexper: odd logic fifth if" ]

    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

  if (debugging) [ print "nexper: odd logic second output" ]

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

end

to permute_sublists :some-genfit

  if not permute_sublists_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 (debugging) [print se ":perm-index-list =>" :perm-index-list]

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

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

  if (debugging) [ print se ":my-genome =>" :my-genome ]

  let [ :best-genome copy-list :my-genome ]
  let [ :best-partial-fitness worst-possible ]

  let [:perm-sublists empty-list]

;; Do the walk of :my-genome with a zero based index so that we can use
;; "mod" easily.

;; Start copying a sublist at the first town in the perm index list.

  let
  [
    :zbindex
    ( ( position (zbitem 0 :perm-index-list) :my-genome ) - 1 )
  ]

  let [:sublist empty-list]

;; Split the input genome into a list of sublists broken at the selected
;; towns.

  repeat number-of-towns
  [
    set :sublist lput ( zbitem :zbindex :my-genome ) :sublist
    if (debugging) [print se ":sublist =>" :sublist]
    set :zbindex ( ( :zbindex + 1 ) mod number-of-towns )

;; Is the next town in the list of sublist starting towns?  If so, break
;; the current sublist here and start a new sublist.

    if ( member? (zbitem :zbindex :my-genome) :perm-index-list )
    [
      set :perm-sublists lput ( copy-list :sublist ) :perm-sublists
      if (debugging) [print se ":perm-sublists =>" :perm-sublists]
      set :sublist empty-list
      if (debugging) [print se ":sublist =>" :sublist]
    ]
  ]

  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 [ :bitter 0 ]
  let [ :index  0 ]

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

  let [ :partial-fitness worst-possible ]
  let [:candidate-sublist empty-list]

  loop
  [
    if (debugging) [print "permute_sublists: top of loop"]

    if (debugging) [print se ":perm-n =>" :perm-n]
    if (debugging) [print se ":perm-a =>" :perm-a]
    if (debugging) [print se ":perm-mtc =>" :perm-mtc]
    if (debugging) [print se ":perm-even =>" :perm-even]
    set :perm-out ( nexper :perm-n :perm-a :perm-mtc :perm-even )
    if (debugging) [print se ":perm-out =>" :perm-out]
    set :perm-n     first    :perm-out
    set :perm-out   butfirst :perm-out
    set :perm-a     copy-list 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

    set :bitter 0

    ;; loop through possible substring orientations
    repeat ( 2 ^ ( :perm-n - 1 ) )
    [
      set :partial-fitness 0
      set :index 0
      repeat ( :perm-n - 1 )
      [
        set :index ( :index + 1 )

        ifelse ( ( ( :bitter div ( 2 ^ ( :index - 1 ) ) ) mod 2 ) = 0 )
        [
          ifelse ( ( ( : bitter div ( 2 ^ :index ) ) mod 2 ) = 0 )
          [

            set
            :partial-fitness
            (
              :partial-fitness
              +
              (
                town-distance
                (
                  last
                  (
                    item
                    ( item :index :perm-a )
                    :perm-sublists
                  )
                )
                (
                  first
                  (
                    item
                    ( item ( :index + 1 ) :perm-a )
                    :perm-sublists
                  )
                )
              )
            )

          ]
          [

            set
            :partial-fitness
            (
              :partial-fitness
              +
              (
                town-distance
                (
                  last
                  (
                    item
                    ( item :index :perm-a )
                    :perm-sublists
                  )
                )
                (
                  last
                  (
                    item
                    ( item ( :index + 1 ) :perm-a )
                    :perm-sublists
                  )
                )
              )
            )

          ]
        ]
        [
          ifelse ( ( ( : bitter div ( 2 ^ :index ) ) mod 2 ) = 0 )
          [
            set
            :partial-fitness
            (
              :partial-fitness
              +
              (
                town-distance
                (
                  first
                  (
                    item
                    ( item :index :perm-a )
                    :perm-sublists
                  )
                )
                (
                  first
                  (
                    item
                    ( item ( :index + 1 ) :perm-a )
                    :perm-sublists
                  )
                )
              )
            )
          ]
          [
            set
            :partial-fitness
            (
              :partial-fitness
              +
              (
                town-distance
                (
                  first
                  (
                    item
                    ( item :index :perm-a )
                    :perm-sublists
                  )
                )
                (
                  last
                  (
                    item
                    ( item ( :index + 1 ) :perm-a )
                    :perm-sublists
                  )
                )
              )
            )
          ]
        ]
        ifelse
        (
          (
            (
              :bitter
              div
              ( 2 ^ ( :perm-n - 1 ) )
            )
            mod
            2
          )
          =
          0
        )
        [

          set
          :partial-fitness
          (
            :partial-fitness
            +
            (
              town-distance
              (
                last
                (
                  item
                  ( item :perm-n :perm-a )
                  :perm-sublists
                )
              )
              (
                first
                (
                  item
                  ( item 1 :perm-a )
                  :perm-sublists
                )
              )
            )
          )

        ]
        [

          set
          :partial-fitness
          (
            :partial-fitness
            +
            (
              town-distance
              (
                first
                (
                  item
                  ( item :index :perm-a )
                  :perm-sublists
                )
              )
              (
                first
                (
                  item
                  ( item 1 :perm-a )
                  :perm-sublists
                )
              )
            )
          )

        ]
        
      ]

      if ( :partial-fitness < :best-partial-fitness )
      [
        set :best-partial-fitness :partial-fitness

        if (debugging)
        [print "permute_sublists: before build best genome"]

        set :best-genome empty-list
        set :index 0
        repeat :perm-n
        [
          set :index ( :index + 1 )

          set :candidate-sublist 
              ( copy-list (item (item :index :perm-a) :perm-sublists) )

          ifelse
          (
            (
              (
                :bitter
                div
                ( 2 ^ ( :index - 1 ) )
              )
              mod
              2
            )
            =
            0
          )
          [

            set
            :best-genome
            se
            ( copy-list :best-genome )
            ( copy-list :candidate-sublist )

          ]
          [
            repeat length :candidate-sublist
            [
              set
              :best-genome
              (
                lput
                ( last :candidate-sublist )
                :best-genome
              )

              set
              :candidate-sublist
              (
                fput
                ( last :candidate-sublist )
                ( butlast :candidate-sublist )
              )

            ]
          ]

          if (debugging) [ print se ":best-genome =>" :best-genome ]
        ]

        if (debugging)
        [print "permute_sublists: after build best genome"]

      ]

      ;; The genome is invariant under reversal, so we can skip
      ;; inverting any one substring, so skip the first one.
      ;; This helps when we need to close the loop, too, since we will
      ;; know the orientation of the first string without recalculating
      ;; it.

      set :bitter ( :bitter + 2 )
      ;; thus the low order bit will always be 0.

    ]

    if (not :perm-mtc)
    [
      if (debugging) [ print se ":best-genome =>" :best-genome ]
      output list :best-genome worst-possible
    ]
    if (debugging) [print "permute_sublists: end of loop"]
  ]

end

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 [ :safe-genome  first :safe-genfit ]

  if ( same-genome :trial-genome :safe-genome )
  [
    output :trial-genfit
  ]

  let [ :index 0]
  repeat length :tabu-genome-list
  [
    set :index ( :index + 1 )
    if
    (
      same-genome ( item :index :tabu-genome-list ) :trial-genome
    )
    [
      set tabus-enforced tabus-enforced + 1
      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-chosen-traveler :trial-traveler ]
  let [ :current-chosen-fitness  :trial-fitness ]

  ;; do "strong" tournament
  if ( tournament_p and strong_or_weak_tournament )
  [
    repeat ( tournament-size )
    [
      set :trial-traveler pick list-of-travelers
      set :trial-fitness item index-fitness tdata-of :trial-traveler
      if ( :trial-fitness < :current-chosen-fitness )
      [
        set :current-chosen-traveler :trial-traveler
        set :current-chosen-fitness  :trial-fitness 
      ]
    ]
  ]

  ;; do "weak" tournament
  if ( tournament_p and not strong_or_weak_tournament )
  [
    let [ :wimp-list empty-list ]
    set :wimp-list lput :trial-traveler :wimp-list

    repeat ( tournament-size )
    [
      ;; Notice that we allow duplicates in the list, so that a wimp
      ;; chosen twice may survive; this is consistent with our
      ;; tournament with replacement strategy of allowing everyone some
      ;; non-zero chance of being chosen.

      set :trial-traveler pick list-of-travelers
      set :trial-fitness item index-fitness tdata-of :trial-traveler

      ifelse ( :trial-fitness > :current-chosen-fitness )
      [
        ;; put new wimp at end
        set :wimp-list lput :trial-traveler :wimp-list

        set :current-chosen-traveler :trial-traveler
        set :current-chosen-fitness  :trial-fitness 
      ]
      [
        ;; put non-wimp earlier
        set :wimp-list fput :trial-traveler :wimp-list
      ]
    ]
    if ( ( length :wimp-list ) > 1 )
    [
      set :wimp-list butlast :wimp-list ;; discard the wimp
      set :current-chosen-traveler pick :wimp-list ;; pick anybody else
    ]
  ]

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

end


`observer`
globals
[
  heuristics-enabled
  busy-travelers
  high-permute
  high-tournament
  debugging_p
  worst-ever
  best-ever
  loop-count
  last-best
  tabus-enforced
  number-of-travelers
  pause_soon_p
  draw_all_once_p
  draw_all_always_p
  swap_p
  invert_p
  inver_over_p
  permute_singles_p
  permute_a_sublist_p
  permute_sublists_p
  crossover_ordered_p
  crossover_partial_match_p
  crossover_cyclic_p
  crossover_edge_preserving_p
  anneal_p
  tabu_p
  tournament_p
  strong_or_weak_tournament
  want_debugging_p
  fail_p
  minimal_spanning_tree_start_p
  local_optimization_p
  minimal-spanning-tree
  some-innie
  some-outie
  some-distance
]

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
  set number-of-travelers
    ( int exp ( (scaled-log10-number-of-travelers / 200 ) * (ln 10)) )
end

to setup

  cp
  ct
  co
  set high-permute 1
  set high-tournament 0
  set debugging_p false
  set minimal-spanning-tree []

  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 500megaflops processor:\n"
           :bf

  set loop-count         1
  set last-best          0
  set tabus-enforced     0
  set heuristics-enabled 8 ;; Initialized to the number of implemented
                           ;; heuristics, then gets recalculated at top
                           ;; of every execution loop so that it is
                           ;; dynamic with user toggling of heuristics
                           ;; at run time.

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

  ask-towns
  [
    init-self
  ]

  if minimal_spanning_tree_start_p
  [
    create-minimal-spanning-tree
  ]

  set busy-travelers number-of-travelers

  set worst-ever number-of-towns * sqrt 2

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

  set
  worst-ever
  (
    max-of-turtles-with
    [ breed = travelers ]
    [ item index-fitness tdata ]
  )

  ask-travelers [ reposition-self ]

  ask-indicators
  [
    init-self
  ]

  set
  best-ever 
  min-of-turtles-with
  [breed = travelers]
  [item index-fitness tdata]

  setup-plot

  set best-ever assay-plot

  draw-best

  draw-anneal

  ask-towns
  [
    run-town
  ]

end

to create-minimal-spanning-tree

  set
  minimal-spanning-tree
  ( lput ( pick list-of-towns ) minimal-spanning-tree )

  ask-turtle
  ( first minimal-spanning-tree )
  [ setitem index-is-in-tree tdata true ]

  repeat ( number-of-towns - 1 )
  [

    let
    [
      :innie-list ( list-of-towns-with [ item index-is-in-tree tdata ] )
    ]

;; For each town not in the minimal spanning tree, have it find the
;; town in the tree closest to it, and store that neighbor's ID and that
;; distance in towns-own variables.

    let
    [
      :outie-list 
      ( list-of-towns-with [ not ( item index-is-in-tree tdata ) ] )
    ]

    let [:best-distance sqrt 2]
    let [:best-innie -1]
    let [:best-outie -1]

    repeat length :innie-list
    [
      set some-innie first :innie-list
      set :innie-list lput first :innie-list butfirst :innie-list
      repeat length :outie-list
      [
        set some-outie first :outie-list
        set :outie-list lput first :outie-list butfirst :outie-list

        ask-turtle
        some-outie
        [ set some-distance town-distance some-innie some-outie ]

        if ( some-distance < :best-distance )
        [
          set :best-distance some-distance
          set :best-innie some-innie
          set :best-outie some-outie
        ]
      ]
    ]

    if ( ( :best-innie = -1 ) or ( :best-outie = -1 ) )
    [
      print "search for greedy pair failed"
      stop
    ]

    ;; roll tree member to which we wish to connect to end of list

    repeat ( length minimal-spanning-tree )
    [
      if ( :best-innie != last minimal-spanning-tree )
      [
        set
        minimal-spanning-tree
        (
          lput
          ( first minimal-spanning-tree )
          ( butfirst minimal-spanning-tree )
        )
      ]
    ]

    ;; add outie, then innie, to end of minimal spanning tree

    set
    minimal-spanning-tree
    ( lput :best-outie minimal-spanning-tree )

    set
    minimal-spanning-tree
    ( lput :best-innie minimal-spanning-tree )

    set some-outie :best-outie
    set some-innie :best-innie

    ask-turtle :best-outie
    [
      setitem index-is-in-tree tdata true

      setc cyan

      pd

      seth
      towards-nowrap
      ( xcor-of some-innie )
      ( ycor-of some-innie )

      fd
      distance-nowrap
      ( xcor-of some-innie )
      ( ycor-of some-innie )

      pu

      setx
      town-center-xcoord
      +
      ( town-xscale * item index-xcoord tdata )

      sety
      town-center-ycoord
      +
      ( town-yscale * item index-ycoord tdata )

      setc white
    ]
  ]

  wait 5

end

to setup-toggles

;; clear pause after next go loop requester

  set pause_soon_p                false

;; 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_singles_p           true
  set permute_a_sublist_p         true
  set permute_sublists_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

;; choose a tournament type;
;;   "strong" chooses the best fitness genome of "n" random picks
;;   "weak"   chooses a random pick of any-but-the-worst-fitness
;;            genome among "n" random picks
;; a "strong" tournament gives fast convergence to some optimum,
;;            but it also depletes the population genome variety
;;            quickly; risking early convergence on a local optimum
;; a "weak"   tournament gives slower convergence to any optimum
;;            but it also preserves the population genome variety
;;            longer, raising hopes for eventual convergence on a
;;            global optimum

  set strong_or_weak_tournament   false ;; == "weak"

;; 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 ( int best-ever ) ( int ( worst-ever + 1 ) )
  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.
;; We're aiming for two generations between reuse
;; of a genome by an individual traveler, when
;; tabu is enabled.

  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_singles_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if permute_a_sublist_p
  [
    set heuristics-enabled (heuristics-enabled + 1)
  ]
  if permute_sublists_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 )
  [
    ;; prevents divide by zero, still does nothing
    set heuristics-enabled 1
  ]

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

    set draw_all_once_p false
  ]

  set loop-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 )

  ]

  if
  (
    worst-ever
    <
    (
      max-of-turtles-with
      [ breed = travelers ]
      [ item index-fitness tdata ]
    )
  )
  [
    set
    worst-ever
    (
      max-of-turtles-with
      [ breed = travelers ]
      [ item index-fitness tdata ]
    )

    setplot-yrange ( int best-ever ) ( int ( worst-ever + 1 ) )

    ask-travelers [ reposition-self ]

  ]


  let [ :best-now assay-plot ]

  if ( :best-now < best-ever )
  [
    set best-ever :best-now
    set last-best loop-count
    setplot-yrange ( int best-ever ) ( int ( worst-ever + 1 ) )

    cg

    draw-best
  ]

  draw-anneal

  if pause_soon_p
  [
    pause-now
  ]

end

to pause-now

  print se "loop count-------------------=>" loop-count
  print se "last improvement at loop-----=>" last-best
  print se "best so far------------------=>" best-ever
  print se "tabus enforced---------------=>" tabus-enforced
  set pause_soon_p false
  stopexecute                             ;; turn off go loop

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 singles--------------=>" permute_singles_p
  print se "permute a sublist------------=>" permute_a_sublist_p
  print se "permute sublists-------------=>" permute_sublists_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
  "strong or weak tournament----=>"
  tournament-type strong_or_weak_tournament

  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

to tournament-type :some-bool
  ifelse :some-bool
  [ output "strong" ]
  [ output "weak" ]
end


`information`
btsp2_03.slogo, 2001/05/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.

Seven of the simpler approximate
solution heuristics: swap, invert,
inver-over, permute singles, permute a
sublist, permute sublists, 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.

There is a whole other kind of solutions
to the traveling salesman problem, those
which take advantage of knowledge about
town to town distances to do improvement
among towns close together on the way to
a global solution.  These are included
here as "sighted cheats" and one is
implemented, that seeds the initial set
of genomes (city tours) starting from a
known good approximation, culled minimal
spanning tree circuits.  Turning on this
cheat shows how much faster a solution
can be found taking advantage of more
information about the problem.

****************************************
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/

There is also a recent version
available from the StarLogo site, at

http://www.media.mit.edu/starlogo/moreprojects/Math/travelingsalesman.slogo

****************************************
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.

generation -- the current value of the
main execution loop count.

last improved -- the generation at which
an improvement to the best genome ever
was last found.  Useful when restarting
long runs, since this state is saved,
while the contents of the Output window
is not.

========================================
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 wherever it
happens to be at the time.

pause soon -- stop the demo at the end
of the current execution loop, creating
a clean place at which to save the demo
to a temporary file for later restart
from where it left off.  As a side
benefit, dumps the current execution
loop count ("generation"), the loop
number at which the best ever fitness
last improved, the best ever genome's
fitness, and the count for the current
problem setup of tabu enforcements done
overall since the last "prepare" was
done, to the output window for review.

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.

You can do "execute, pause soon, save
project as, quit, open project"
repeatedly to run a long problem to
completion.  Since the demo has a nasty
habit of finding OS and Java weaknesses,
this allows one also to baseline a long
problem, exit the demo, optionally
reboot the OS, relaunch the demo, and
thus convey long problem executions
around OS and Java and StarLogo bugs.

========================================
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 singles? -- 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" heuristics decide how
  many items to include in the set of
  items being permuted by use of the
  StarLogo random-gaussian function, so
  in the worst case, with a set of items
  which is the whole genome allele by
  allele, 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 sets of
  items, these are the most powerful
  heuristics for getting "unstuck" among
  the ones included in this demo, in a
  mathematically defensible sense.


permute a sublist? -- use the powerful,
and sometimes important, heuristic of
rearranging the items in one connected
piece of the circuit to sit in all
possible different orders, to see if
an improved genome can be created that
way.

permute sublists? -- use the sometimes
important, and extremely powerful,
heuristic of rearranging whole connected
pieces of the circuit to sit in
different orders, possibly reversing
them as well, to see if an improved
genome can be created that way.  This is
a very slow process because so many
solutions are tried per single pass.

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.

Strong | weak? -- there are two possible
tournament metaheuristic styles, so if
using the tournament metaheuristic is
enabled, this chooses between them.  The
strong version will choose the most fit
genome from a list containing a random
subset of the population of genomes.
The weak version will choose any but the
weakest genome from a list containing a
random subset of the population of
genomes.  The strong version pushes for
better fitness fast and really hard, but
at risk of choosing a local instead of a
global optimum.  The weak version is
much more gentle in its effects.

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.

========================================
Some optional-to-use "sighted cheats"
buttons:
========================================

minimal spanning tree start? -- start
the run with very good approximate
solutions, instead of random ones, by
creating a minimal spanning tree of the
cities, turning it into a circuit, but
not a circuit going through each city
just once, and then creating seed
circuits by culling the minimal spanning
tree to remove the excess cities,
starting at random locations.  The
circuits so generated are mathematically
guaranteed to be less than twice as long
as the optimum solution circuit.

local optimization? -- use a heuristic
that does optimizations among towns that
are "close" on the plane, whether they
are close in the circuit list or not.

========================================
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.

This histogram is radially scaled
relative to the worst genome ever seen,
so if an annealing excursion
significantly worstens the worst genome
ever seen, the circle may seem to jump
to a smaller radius.  There is less to
this than meets the eye, and in
particular, it is not the case that all
the other travelers suddenly got better
in lockstep, merely that one got really,
really bad and changed the scaling.

----------------------------------------
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, (or from all but the
weakest of whom to select from the rest
randomly, see "strong | weak?" above),
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 one of the "permute"
heuristics.  This can help explain to
the user why a few travlers still linger
in the "travelers still busy" count. 
The permute heuristics are very labor
intensive for the computer... here are
the number of fitness calculations that
must be done for a few values of "high
permute" for the permute a sublist and
permute singles heuristics:

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

The permute sublists heuristic also
swaps all but one sublist end for end in
all possible configurations, so it is
much more expensive...here are the
number of fitness calculations needed
for a few values of "high permute" for
this heuristic.

  high permute    fitnesses to compute
  ------------    --------------------
             1                       1
             2                       4
             3                      24
             4                     192
             5                    1800
             6                   23040
             7                  324000
             8                 5160960

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/05/06:

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

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

Sighted Cheats              Implemented?
--------------------------- ------------
minimal spanning tree start?     yes
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
singles, permute a sublist, permute
sublists, ordered crossover, anneal,
tournament, and tabu, at this release):

Notes   Towns   Travelers    Generations to the optimum solution
-----   -----   ---------    ---- ---- ---- ---- ---- ---- ---- ---- ---- ----
  a        10          10       7   11    9    4                              
  b        10          10       6    6    7    7   10    5    6    7    7    5
  a        10          20       6    7    6    5                              
  b        10          20       6    5    6    5    5    6    6    5    4    4
  a        10          40       4    4    6    7                              
  b        10          40       3    5    4    5    4    4    4    6    5    5
  a        10          80       4    3    5    5                              
  b        10          80       3    4    4    2    5    3    3    2    3    4
  a        10         160       3    2    3    5                              
  b        10         160       4    5    4    4    4    3    3    5    4    3
  a        15          10      14   17   16   20                              
  b        15          10      13   21   14   22   16   16   26   15   74   30
  a        15          20      13   21   17   12                              
  b        15          20      12   17   20   14   11   15   11   19   13   17
  a        15          40      12   10   16   13                              
  a        15          80      12   39   11   10                              
  a        15         160       9   11   12    8                              
  a        20          10      34   99   25   67                              
  a        20          20      23   35   30   29                              
  a        20          40      48   48   31   22                              
  a        20          80      20   22   19   25                              
  a        20         160      24   24   20   23                              
  a        25          10     344   77   39  347                              
  a        25          20      60  178   49   88                              
  a        25          40      43   31   31   41                              
           25          80                                                     
           25         160                                                     
           30          10                                                     
           30          20                                                     
  a        30          40      48                                             
  c        30          40      44   38   48   64   76   51   36   29   43   33
  c        30          80      34   31   47   47   40   43   32   29   33   32
  c        30         160      46   30   35   31                              
           35          10                                                     
           35          20                                                     
           35          40                                                     
  c        35          80      51                                             
           35         160                                                     
           40          10                                                     
           40          20                                                     
           40          40                                                     
           40          80                                                     
           40         160                                                     
           45          10                                                     
           45          20                                                     
           45          40                                                     
           45          80                                                     
           45         160                                                     
  d        50           1    2365                                             
           50          10                                                     
           50          20                                                     
           50          40                                                     
           50          80                                                     
  a        50         160     240                                             
  b        50         160     183                                             
  c        50         160     148                                             

Notes:
a == 2_02 release version 
b == "a" version plus permute_sublists
c == "b" version plus permute_a_sublist
d == "c", all metaheuristics off, permute heuristics only, on.

  [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_02 to v2_03

Added code to adjust the plot y
dimensions dynamically to keep the
vertical span of the plot as useful as
possible.  It now fits the worst ever
genome and best ever genome values, at
top and bottom respectively, within a
unit each, rather than accepting the
StarLogo 50% overshoot defaults.

Added code to adjust the circular
histogram dynamically to make it more
interesting in the case where a minimal
spanning tree start is enabled.  Instead
of starting with all the turtles in a
tiny circle in the center, the histogram
now starts at near maximum size based on
the worst ever genome rather than the
worst possible genome, which is never
approximated in a minimal spanning tree
start.

Added a "pause soon" button to stop
execution at the end of an execution
loop rather than at an arbitrary point
in the execution loop, to provide a
synchronization point for saving the
project to a temporary file for later
relaunch and re-execute without a
"reset" or "prepare" step, which allows
running a long problem in several
disjoint sessions, perhaps when the
computer is not otherwise being used.

Added a monitor "last improved" to show
the generation at which the best ever
genome fitness was last made better; for
problems solved in a single run, this is
redundant with the output window display
of the same information, but this value
persists when the project is paused,
saved, relaunched, and execution is
continued.

Added a "weak" tournament version and a
"strong | weak?" selector button in yet
another attempt to preserve the
diversity of genomes in the population.
After a bit of testing, made "weak" the
default, it seems much superior to the
"strong" tournament.

Added a ">" decoration to the
"tournament?" button to call the user's
attention to the new "strong | weak?"
button to its right.

Decreased the number of tournament
participants in attempt to prevent rapid
impoverishment of the collective genome.

Renamed "permute" to "permute singles"
to make it more easily distinguished
from the other permuter heuristics.

Generalized and renamed "move sublist"
to "permute sublists", to chop the
genome into a (small) set of sublists
and try them in all possible orders and
randomly invert about half of them.

Added a monitor "generation" to show 
the current value of loop-count.

Added "permute a sublist" heuristic to
permute a small connected subset of the
circuit in all possible orders and
choose the best.

Implemented the "minimal spanning tree
start?" sighted cheat, with huge
solution time improvements for big
problem sizes as a result.  This now
computes, and displays, a minimal
spanning tree during the prepare
process, which means this cheat must be
turned on before the "prepare" step.
Computing the minimal spanning tree is
slow, but bearable.

Modified the Interface window text
widget with instructions for running the
demo to more carefully define this new
order of button pressing.

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,
very powerful, but 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.

That status dump to the output window is
now available from a new "see toggles"
button among the debugging buttons.

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 sublist permute
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.

The minimal spanning tree (MST)
computation is the standard greedy
algorithm written by me from memory, but
someone else invented it long ago.

The method of storing the MST in a list
representation designed so that it can
be accessed from a random starting point
and culled to a cycle with no towns
repeated is mine, or at least I
independently invented it.

I've wanted to combine this seeding with
a genetic algorithm for years, but only
recently learned enough about genetic
algorithms to do that.  I've used other,
"sighted" approaches starting from the
minimal spanning tree for at least eight
or ten years of hobby programming now.

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 35 5
width-height 80 22
name "reset"
line-to-run "startup"
forever? false
button-number 20
show-name? true

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 115 5
width-height 80 22
name "draw all once"
line-to-run "print \"draw all once requested\" set draw_all_once_p true"
forever? false
button-number 4
show-name? true

SLButton
turtle-or-observer? observer
top-left 195 90
width-height 165 22
name "* partial match crossover?"
line-to-run "set crossover_partial_match_p (not crossover_partial_match_p) print se \"partial match crossover? =>\" 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 "* edge preserving crossover?"
line-to-run "set crossover_edge_preserving_p (not crossover_edge_preserving_p) print se \"edge preserving crossover? =>\" crossover_edge_preserving_p"
forever? false
button-number 15
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 65 5
width-height 80 22
name "prepare"
line-to-run "setup"
forever? false
button-number 2
show-name? true

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

SLButton
turtle-or-observer? observer
top-left 400 355
width-height 80 22
name "pause soon"
line-to-run "print \"pause requested at end of current execution loop\" set pause_soon_p true"
forever? false
button-number 27
show-name? true

SLButton
turtle-or-observer? observer
top-left 90 355
width-height 80 22
name "strong | weak?"
line-to-run "set strong_or_weak_tournament (not strong_or_weak_tournament) print se \"strong or weak tournament =>\" (tournament-type strong_or_weak_tournament)"
forever? false
button-number 26
show-name? true

SLButton
turtle-or-observer? observer
top-left 90 270
width-height 80 22
name "tournament? >"
line-to-run "set tournament_p (not tournament_p) print se \"tournament? =>\" tournament_p"
forever? false
button-number 6
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 120 22
name "permute singles?"
line-to-run "set permute_singles_p (not permute_singles_p) print se \"permute singles? =>\" permute_singles_p"
forever? false
button-number 11
show-name? true

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

SLButton
turtle-or-observer? observer
top-left 270 5
width-height 120 22
name "permute a sublist?"
line-to-run "set permute_a_sublist_p (not permute_a_sublist_p) print se \"permute a sublist? =>\" permute_a_sublist_p"
forever? false
button-number 25
show-name? true

SLButton
turtle-or-observer? observer
top-left 270 130
width-height 125 22
name "permute sublists?"
line-to-run "set permute_sublists_p (not permute_sublists_p) print se \"permute sublists? =>\" permute_sublists_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 "set want_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

SLMonitor
top-left 360 355
width-height 80 36
name "last improved"
list-to-run "last-best"
digits 0
delay 0.3
monitor-number 4
show-name? true

SLMonitor
top-left 320 355
width-height 80 36
name "generation"
list-to-run "loop-count"
digits 0
delay 0.3
monitor-number 3
show-name? true

SLButton
turtle-or-observer? observer
top-left 195 270
width-height 80 22
name "fail?"
line-to-run "set fail_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 "set draw_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 "set swap_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 "set invert_p (not invert_p) print se \"invert? =>\" invert_p"
forever? false
button-number 9
show-name? true

SLTextWidget
top-left 295 4
width-height 173 150
textwidth 169
linenums 7
words "Blind Traveling Salesman Demo.\n1) Open plot and output windows.\n2) Set travelers and towns, \"reset\".\n3) Set cheats, \"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 "set crossover_ordered_p (not crossover_ordered_p) print se \"ordered crossover? =>\" 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 355
width-height 80 22
name "tabu?"
line-to-run "set tabu_p (not tabu_p) print se \"tabu? =>\" tabu_p"
forever? false
button-number 7
show-name? true

SLButton
turtle-or-observer? observer
top-left 65 270
width-height 80 22
name "anneal?"
line-to-run "set anneal_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 "set inver_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

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

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 "scaled-log10-number-of-travelers"
min-value 0
max-value 700
current-value 322
slider-number 1
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

SLCanvas
top-left 35 440

`settings`
patch-size 3
num-shapes 256
screen-half-width 30
screen-half-height 61
interface-window-xcor 440
interface-window-ycor 0
interface-window-size 635 433
output-window-xcor 0
output-window-ycor 512
output-window-width 440
output-window-height 480
info-window-xcor 725
info-window-ycor 512
info-window-width 332
info-window-height 419
control-center-xcor 440
control-center-ycor 512
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 512

`string table`
H4sIAAAAAAAAAGNgYGAAABzfRCEEAAAAAAAABA==

`symbol table`
H4sIAAAAAAAAAGNgYGBiYE1LzClOZWApKSpNBQDlw1heEQAAAAAAABE=

`double table`
H4sIAAAAAAAAAGNgYGAAABzfRCEEAAAAAAAABA==

`list table`
H4sIAAAAAAAAAGNgYGAAABzfRCEEAAAAAAAABA==

`observer world`
H4sIAAAAAAAAAJ1S227UQAz1UtjurXttgaWUlssDQso/8Cepk3izIybjaGbSaPkO
PhjHe1P7hIjkaM459thjG+aPnAXyT+QfQsRIjz/h9P2AviVXxq2c/8BlbTnW5FQa
q/NJfS32DZZbarwJ0eQhIYeZpUKdp1kTdkn0+CQRPgjTg8nWlNukJl81kYR5BTNl
IjfeYUUuCnkB44KypiyNK9Na84xa9iEmJAULfgPDjM6wDyPLXCc5Nxp/CUOLInc+
AgcwjSi1SHEb9rlWN4SVa6qMfMKbZyWOYFJjEygNzE6Tj2FWeGxTtDZll5OSE1ic
SLQt7oLSV9APLdZ6nsLAOCkwKprBRFHK3a9j5rA49CEN8lBL+ysWsDrSmIYms9JZ
FZawPPnv6X3ACla55xD0YvYFeSpUuIb1WajRR4M2rTDmW5VvYHmW811uTa78W7g9
81SU8mBP3a4cp/EOBugcyWUdeg/9rrt6XsPkPEhlPsA6RM8SyT5tCX+lzyZ9C/MW
xfX5uD9Cf4Nmf/0d3FXGmUqyhVrSdj7Rk/Qg4qG1n+Daci4OXEdTmd8YzWF093Bz
CE6OwUkXLNIDjAJXlBhhO/z5gLmJir/AleJC+owydaG+dpvY0zX+J/t+obt8st5/
GLy0l3n+AtnaGbnKAwAAAAADyg==

`patch world`
H4sIAAAAAAAAAH3VyapzYZ/e551gEkEIaKCBBiIIIYQQQqjvu+r7St832BgTD4xd
JDVIZjq075ByCKk4PP/98u57XQskLela96Ph7+s//ef/8C/+8V/+6/H/+Y//4h//
1T9/f9X151//7P/6l//u//j39//hP/zLf3rvf/1H/+Zf/dv//R//9T/dj77+43/4
N//uH//hX/3bf/oy/Ppn//f//2jv6z/59wf98tzX13/2T6/H/3fM6//5/49un79c
/0H752g9WB82gA1hI9gYNoFNYTPYHLaALWEr2Bq2gW1hO9gedoAdYSfYGXaBXWE3
2B32gD1hL9hb9um2P8Luj7D7Y+z+GLs/we5PsPtT7P4Uuz/D7s+w+3Ps/hy7v8Du
L7D7S+z+Eru/wu6vsPtr7P4au7/B7m+w+1vs/ha7v8Pu77D7e+z+vnvXfnv/oO9W
RevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rANbAvbwfawA+wIO8HOsAvsCrvB7rAH
7Al7wd6yT7f9EXZ/hN0fY/fH2P0Jdn+C3Z9i96fY/Rl2f4bdn2P359j9BXZ/gd1f
YveX2P0Vdn+F3V9j99fY/Q12f4Pd32L3t9j9HXZ/h93fY/f33btqVS/svmA9WB82
gA1hI9gYNoFNYTPYHLaALWEr2Bq2gW1hO9gedoAdYSfYGXaBXWE32B32gD1hL9hb
9um21qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh11oVDbvWqmjYtVZFw661
Khp2rVXRsGutioZda1W07l21qh92X7AerA8bwIawEWwMm8CmsBlsDlvAlrAVbA3b
wLawHWwPO8COsBPsDLvArrAb7A57wJ6wF+wt+3Rba1U07FqromHXWhUNu9aqaNi1
VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSpa965aNQi7
L1gP1ocNYEPYCDaGTWBT2Aw2hy1gS9gKtoZtYFvYDraHHWBH2Al2hl1gV9gNdoc9
YE/YC/aWfbqttSoadq1V0bBrrYqGXWtVNOxaq6Jh11oVDbvWqmjYtVZFw661Khp2
rVXRsGutioZda1U07FqromHXWhWte1etGobdF6wH68MGsCFsBBvDJrApbAabwxaw
JWwFW8M2sC1sB9vDDrAj7AQ7wy6wK+wGu8MesCfsBXvLPt3WWhUNu9aqaNi1VkXD
rrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYrW
vatWjcLuC9aD9WED2BA2go1hE9gUNoPNYQvYEraCrWEb2Ba2g+1hB9gRdoKdYRfY
FXaD3WEP2BP2gr1ln25rrYqGXWtVNOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXR
sGutioZda1U07FqromHXWhUNu9aqaNi1VkXr3lWrxmH3BevB+rABbAgbwcawCWwK
m8HmsAVsCVvB1rANbAvbwfawA+wIO8HOsAvsCrvB7rAH7Al7wd6yT7e1VkXDrrUq
GnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtV
NOxaq6J176pVk7D7gvVgfdgANoSNYGPYBDaFzWBz2AK2hK1ga9gGtoXtYHvYAXaE
nWBn2AV2hd1gd9gD9oS9YG/Zp9taq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGut
ioZda1U07FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdG6d9Wqadh9wXqwPmwAG8JG
sDFsApvCZrA5bAFbwlawNWwD28J2sD3sADvCTrAz7AK7wm6wO+wBe8JesLfs022t
VdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxa
q6Jh11oVDbvWqmjdu2rVLOy+YD1YHzaADWEj2Bg2gU1hM9gctoAtYSvYGraBbWE7
2B52gB1hJ9gZdoFdYTfYHfaAPWEv2Fv26bbWqmjYtVZFw661Khp2rVXRsGutioZd
a1U07FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVbTuXbVqHnZfsB6s
DxvAhrARbAybwKawGWwOW8CWsBVsDdvAtrAdbA87wI6wE+wMu8CusBvsDnvAnrAX
7C37dFtrVTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh
11oVDbvWqmjYtVZFw661Klr3rlq1CLsvWA/Whw1gQ9gINoZNYFPYDDaHLWBL2Aq2
hm1gW9gOtocdYEfYCXaGXWBX2A12hz1gT9gL9pZ9uq21Khp2rVXRsGutioZda1U0
7FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFa17V61a
ht0XrAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MOsCPsBDvDLrAr7Aa7
wx6wJ+wFe8s+3dZaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh11oV
DbvWqmjYtVZFw661Khp2rVXRsGutita9q1atwu4L1oP1YQPYEDaCjWET2BQ2g81h
C9gStoKtYRvYFraD7WEH2BF2gp1hF9gVdoPdYQ/YE/aCvWWfbmutioZda1U07Fqr
omHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVW
ReveVavWYfcF68H6sAFsCBvBxrAJbAqbweawBWwJW8HWsA1sC9vB9rAD7Ag7wc6w
C+wKu8HusAfsCXvB3rJPt7VWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh11oVDbvW
qmjYtVZFw661Khp2rVXRsGutioZda1U07FqronXvqlWbsPuC9WB92AA2hI1gY9gE
NoXNYHPYAraErWBr2Aa2he1ge9gBdoSdYGfYBXaF3WB32AP2hL1gb9mn21qromHX
WhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOu
tSoadq1V0bp31apt2H3BerA+bAAbwkawMWwCm8JmsDlsAVvCVrA1bAPbwnawPewA
O8JOsDPsArvCbrA77AF7wl6wt+zTba1V0bBrrYqGXWtVNOxaq6Jh11oVDbvWqmjY
tVZFw661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaN27atUu7L5gPVgfNoAN
YSPYGDaBTWEz2By2gC1hK9gatoFtYTvYHnaAHWEn2Bl2gV1hN9gd9oA9YS/YW/bp
ttaqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSoa
dq1V0bBrrYqGXWtVtO5dtWofdl+wHqwPG8CGsBFsDJvAprAZbA5bwJawFWwN28C2
sB1sDzvAjrAT7Ay7wK6wG+wOe8CesBfsLft0W2tVNOxaq6Jh11oVDbvWqmjYtVZF
w661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaNi1VkXDrrUqWveuWnUIuy9Y
D9aHDWBD2Ag2hk1gU9gMNoctYEvYCraGbWBb2A62hx1gR9gJdoZdYFfYDXaHPWBP
2Av2ln26rbUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V
0bBrrYqGXWtVNOxaq6Jh11oVrXtXrTqG3ResB+vDBrAhbAQbwyawKWwGm8MWsCVs
BVvDNrAtbAfbww6wI+wEO8MusCvsBrvDHrAn7AV7yz7d1loVDbvWqmjYtVZFw661
Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62K1r2r
Vp3C7gvWg/VhA9gQNoKNYRPYFDaDzWEL2BK2gq1hG9gWtoPtYQfYEXaCnWEX2BV2
g91hD9gT9oK9ZZ9ua62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBr
rYqGXWtVNOxaq6Jh11oVDbvWqmjYtVZF695Vq85h9wXrwfqwAWwIG8HGsAlsCpvB
5rAFbAlbwdawDWwL28H2sAPsCDvBzrAL7Aq7we6wB+wJe8Hesk+3tVZFw661Khp2
rVXRsGutioZda1U07FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTs
Wquide+qVZew+4L1YH3YADaEjWBj2AQ2hc1gc9gCtoStYGvYBraF7WB72AF2hJ1g
Z9gFdoXdYHfYA/aEvWBv2afbWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqG
XWtVNOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRunfVqmvYfcF6sD5sABvCRrAx
bAKbwmawOWwBW8JWsDVsA9vCdrA97AA7wk6wM+wCu8JusDvsAXvCXrC37NNtrVXR
sGutioZda1U07FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWqui
YddaFQ271qpo3btq1S3svmA9WB82gA1hI9gYNoFNYTPYHLaALWEr2Bq2gW1hO9ge
doAdYSfYGXaBXWE32B32gD1hL9hb9um21qpo2LVWRcOutSoadq1V0bBrrYqGXWtV
NOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1W07l216h52X7AerA8b
wIawEWwMm8CmsBlsDlvAlrAVbA3bwLawHWwPO8COsBPsDLvArrAb7A57wJ6wF+wt
+3Rba1U07FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYdda
FQ271qpo2LVWRcOutSpa965a9Qi7L1gP1ocNYEPYCDaGTWBT2Aw2hy1gS9gKtoZt
YFvYDraHHWBH2Al2hl1gV9gNdoc9YE/YC/aWfbqttSoadq1V0bBrrYqGXWtVNOxa
q6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1U07FqromHXWhWte1eteobd
F6wH68MGsCFsBBvDJrApbAabwxawJWwFW8M2sC1sB9vDDrAj7AQ7wy6wK+wGu8Me
sCfsBXvLPt3WWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ27
1qpo2LVWRcOutSoadq1V0bBrrYrWvatWvcLuC9aD9WED2BA2go1hE9gUNoPNYQvY
EraCrWEb2Ba2g+1hB9gRdoKdYRfYFXaD3WEP2BP2gr1ln25rrYqGXWtVNOxaq6Jh
11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaNi1VkXr
3lWr3mH3BevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rANbAvbwfawA+wIO8HOsAvs
CrvB7rAH7Al7wd6yT7e1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo
2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6J1775b9fm5+4L1YH3YADaEjWBj2AQ2
hc1gc9gCtoStYGvYBraF7WB72AF2hJ1gZ9gFdoXdYHfYA/aEvWBv2afbqlXJsKtW
JcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqVDLtqVTLsqlXJ
sKtWJeveVav+6Hf6pVXJerA+bAAbwkawMWwCm8JmsDlsAVvCVrA1bAPbwnawPewA
O8JOsDPsArvCbrA77AF7wl6wt+zTba1V0bBrrYqGXWtVNOxaq6Jh11oVDbvWqmjY
tVZFw661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaN2771Z9fu6+YD1YHzaA
DWEj2Bg2gU1hM9gctoAtYSvYGraBbWE72B52gB1hJ9gZdoFdYTfYHfaAPWEv2Fv2
6bZqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXD
rlqVDLtqVTLsqlXJunfVqj/+nX5pVbIerA8bwIawEWwMm8CmsBlsDlvAlrAVbA3b
wLawHWwPO8COsBPsDLvArrAb7A57wJ6wF+wt+3Rba1U07FqromHXWhUNu9aqaNi1
VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSpa9+67VZ+f
uy9YD9aHDWBD2Ag2hk1gU9gMNoctYEvYCraGbWBb2A62hx1gR9gJdoZdYFfYDXaH
PWBP2Av2ln26rVqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7
alUy7KpVybCrViXDrlqVDLtqVbLuXbXqT36nX1qVrAfrwwawIWwEG8MmsClsBpvD
FrAlbAVbwzawLWwH28MOsCPsBDvDLrAr7Aa7wx6wJ+wFe8s+3dZaFQ271qpo2LVW
RcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGut
ita9+27V5+fuC9aD9WED2BA2go1hE9gUNoPNYQvYEraCrWEb2Ba2g+1hB9gRdoKd
YRfYFXaD3WEP2BP2gr1ln26rViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyq
Vcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqVrHtXrfrT3+mXViXrwfqwAWwIG8HG
sAlsCpvB5rAFbAlbwdawDWwL28H2sAPsCDvBzrAL7Aq7we6wB+wJe8Hesk+3tVZF
w661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62K
hl1rVTTsWquide++W/X5ufuC9WB92AA2hI1gY9gENoXNYHPYAraErWBr2Aa2he1g
e9gBdoSdYGfYBXaF3WB32AP2hL1gb9mn26pVybCrViXDrlqVDLtqVTLsqlXJsKtW
JcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXr3lWr/ux3+qVVyXqw
PmwAG8JGsDFsApvCZrA5bAFbwlawNWwD28J2sD3sADvCTrAz7AK7wm6wO+wBe8Je
sLfs022tVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqG
XWtVNOxaq6Jh11oVDbvWqmjdu+9WfX7uvmA9WB82gA1hI9gYNoFNYTPYHLaALWEr
2Bq2gW1hO9gedoAdYSfYGXaBXWE32B32gD1hL9hb9um2alUy7KpVybCrViXDrlqV
DLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybp31ao/
/51+aVWyHqwPG8CGsBFsDJvAprAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6w
G+wOe8CesBfsLft0W2tVNOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZd
a1U07FqromHXWhUNu9aqaNi1VkXDrrUqWvfuu1Wfn7svWA/Whw1gQ9gINoZNYFPY
DDaHLWBL2Aq2hm1gW9gOtocdYEfYCXaGXWBX2A12hz1gT9gL9pZ9uq1alQy7alUy
7KpVybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7
alWy7l216i9+p19alawH68MGsCFsBBvDJrApbAabwxawJWwFW8M2sC1sB9vDDrAj
7AQ7wy6wK+wGu8MesCfsBXvLPt3WWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1r
VTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYrWvftu1efn7gvWg/VhA9gQ
NoKNYRPYFDaDzWEL2BK2gq1hG9gWtoPtYQfYEXaCnWEX2BV2g91hD9gT9oK9ZZ9u
q1Ylw65alQy7alUy7KpVybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyq
Vcmwq1Ylw65alax7V636y9/pl1Yl68H6sAFsCBvBxrAJbAqbweawBWwJW8HWsA1s
C9vB9rAD7Ag7wc6wC+wKu8HusAfsCXvB3rJPt7VWRcOutSoadq1V0bBrrYqGXWtV
NOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1U07FqronXvvlv1+bn7
gvVgfdgANoSNYGPYBDaFzWBz2AK2hK1ga9gGtoXtYHvYAXaEnWBn2AV2hd1gd9gD
9oS9YG/Zp9uqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqVDLtqVTLsqlXJsKtW
JcOuWpUMu2pVMuyqVcmwq1Yl695Vq/7qd/qlVcl6sD5sABvCRrAxbAKbwmawOWwB
W8JWsDVsA9vCdrA97AA7wk6wM+wCu8JusDvsAXvCXrC37NNtrVXRsGutioZda1U0
7FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo
3bvvVn1+7r5gPVgfNoANYSPYGDaBTWEz2By2gC1hK9gatoFtYTvYHnaAHWEn2Bl2
gV1hN9gd9oA9YS/YW/bptmpVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqV
DLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcm6d9Wqv/6dfmlVsh6sDxvAhrARbAyb
wKawGWwOW8CWsBVsDdvAtrAdbA87wI6wE+wMu8CusBvsDnvAnrAX7C37dFtrVTTs
WquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh11oVDbvWqmjY
tVZFw661Klr37rtVn5+7L1gP1ocNYEPYCDaGTWBT2Aw2hy1gS9gKtoZtYFvYDraH
HWBH2Al2hl1gV9gNdoc9YE/YC/aWfbqtWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy
7KpVybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVsu5dtepvfqdfWpWsB+vD
BrAhbAQbwyawKWwGm8MWsCVsBVvDNrAtbAfbww6wI+wEO8MusCvsBrvDHrAn7AV7
yz7d1loVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaNi1
VkXDrrUqGnatVdGwa62K1r37btXn5+4L1oP1YQPYEDaCjWET2BQ2g81hC9gStoKt
YRvYFraD7WEH2BF2gp1hF9gVdoPdYQ/YE/aCvWWfbqtWJcOuWpUMu2pVMuyqVcmw
q1Ylw65alQy7alUy7KpVybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpWse1et+tvf
6ZdWJevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rANbAvbwfawA+wIO8HOsAvsCrvB
7rAH7Al7wd6yT7e1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVW
RcOutSoadq1V0bBrrYqGXWtVNOxaq6J1775b9fm5+4L1YH3YADaEjWBj2AQ2hc1g
c9gCtoStYGvYBraF7WB72AF2hJ1gZ9gFdoXdYHfYA/aEvWBv2afbqlXJsKtWJcOu
WpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqVDLtqVTLsqlXJsKtW
JeveVav+7nf6pVXJerA+bAAbwkawMWwCm8JmsDlsAVvCVrA1bAPbwnawPewAO8JO
sDPsArvCbrA77AF7wl6wt+zTba1V0bBrrYqGXWtVNOxaq6Jh11oVDbvWqmjYtVZF
w661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaN2771Z9fu6+YD1YHzaADWEj
2Bg2gU1hM9gctoAtYSvYGraBbWE72B52gB1hJ9gZdoFdYTfYHfaAPWEv2Fv26bZq
VTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqV
DLtqVTLsqlXJunfVqr//nX5pVbIerA8bwIawEWwMm8CmsBlsDlvAlrAVbA3bwLaw
HWwPO8COsBPsDLvArrAb7A57wJ6wF+wt+3Rba1U07FqromHXWhUNu9aqaNi1VkXD
rrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo2LVWRcOutSpa9+67VZ+fuy9Y
D9aHDWBD2Ag2hk1gU9gMNoctYEvYCraGbWBb2A62hx1gR9gJdoZdYFfYDXaHPWBP
2Av2ln26rVqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy
7KpVybCrViXDrlqVDLtqVbLuXbXqP/+dfmlVsh6sDxvAhrARbAybwKawGWwOW8CW
sBVsDdvAtrAdbA87wI6wE+wMu8CusBvsDnvAnrAX7C37dFtrVTTsWquiYddaFQ27
1qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh11oVDbvWqmjYtVZFw661Klr3
7rtVn5+7L1gP1ocNYEPYCDaGTWBT2Aw2hy1gS9gKtoZtYFvYDraHHWBH2Al2hl1g
V9gNdoc9YE/YC/aWfbqtWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXD
rlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVsu5dteq/+J1+aVWyHqwPG8CGsBFsDJvA
prAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6wG+wOe8CesBfsLft0W2tVNOxa
q6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aqaNi1
VkXDrrUqWvfuu1Xvn7svWA/Whw1gQ9gINoZNYFPYDDaHLWBL2Aq2hm1gW9gOtocd
YEfYCXaGXWBX2A12hz1gT9gL9pZ9uq1alQy7alUy7KpVybCrViXDrlqVDLtqVTLs
qlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alWy7t13qz4/d1+wHqwPG8CG
sBFsDJvAprAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6wG+wOe8CesBfsLft0
W7UqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61Khl21Khl21apk2FWrkmFX
rUqGXbUqGXbVqmTdu+9W/eHn7gvWg/VhA9gQNoKNYRPYFDaDzWEL2BK2gq1hG9gW
toPtYQfYEXaCnWEX2BV2g91hD9gT9oK9ZZ9uq1Ylw65alQy7alUy7KpVybCrViXD
rlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alax7V636L3+nX1qV
rAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MOsCPsBDvDLrAr7Aa7wx6w
J+wFe8s+3dZaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh11oVDbvW
qmjYtVZFw661Khp2rVXRsGutita9+27V++fuC9aD9WED2BA2go1hE9gUNoPNYQvY
EraCrWEb2Ba2g+1hB9gRdoKdYRfYFXaD3WEP2BP2gr1ln26rViXDrlqVDLtqVTLs
qlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqVrHv3
3arPz90XrAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MOsCPsBDvDLrAr
7Aa7wx6wJ+wFe8s+3VatSoZdtSoZdtWqZNhVq5JhV61Khl21Khl21apk2FWrkmFX
rUqGXbUqGXbVqmTYVauSYVetSoZdtSpZ9+67VX/4ufuC9WB92AA2hI1gY9gENoXN
YHPYAraErWBr2Aa2he1ge9gBdoSdYGfYBXaF3WB32AP2hL1gb9mn26pVybCrViXD
rlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCr
ViXr3lWr/qvf6ZdWJevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rANbAvbwfawA+wI
O8HOsAvsCrvB7rAH7Al7wd6yT7e1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYdda
FQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6J1775b9f65+4L1YH3YADaE
jWBj2AQ2hc1gc9gCtoStYGvYBraF7WB72AF2hJ1gZ9gFdoXdYHfYA/aEvWBv2afb
qlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqVDLtq
VTLsqlXJsKtWJevefbfq83P3BevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rANbAvb
wfawA+wIO8HOsAvsCrvB7rAH7Al7wd6yT7dVq5JhV61Khl21Khl21apk2FWrkmFX
rUqGXbUqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61K1r37btUffu6+YD1Y
HzaADWEj2Bg2gU1hM9gctoAtYSvYGraBbWE72B52gB1hJ9gZdoFdYTfYHfaAPWEv
2Fv26bZqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCr
ViXDrlqVDLtqVTLsqlXJunfVqv/6d/qlVcl6sD5sABvCRrAxbAKbwmawOWwBW8JW
sDVsA9vCdrA97AA7wk6wM+wCu8JusDvsAXvCXrC37NNtrVXRsGutioZda1U07Fqr
omHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo3bvv
Vr1/7r5gPVgfNoANYSPYGDaBTWEz2By2gC1hK9gatoFtYTvYHnaAHWEn2Bl2gV1h
N9gd9oA9YS/YW/bptmpVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqVDLtq
VTLsqlXJsKtWJcOuWpUMu2pVMuyqVcm6d9+t+vzcfcF6sD5sABvCRrAxbAKbwmaw
OWwBW8JWsDVsA9vCdrA97AA7wk6wM+wCu8JusDvsAXvCXrC37NNt1apk2FWrkmFX
rUqGXbUqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61Khl21Khl21apk2FWr
knXvvlv1h5+7L1gP1ocNYEPYCDaGTWBT2Aw2hy1gS9gKtoZtYFvYDraHHWBH2Al2
hl1gV9gNdoc9YE/YC/aWfbqtWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCr
ViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVsu5dteq/+Z1+aVWyHqwPG8CGsBFs
DJvAprAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6wG+wOe8CesBfsLft0W2tV
NOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1U07FqromHXWhUNu9aq
aNi1VkXDrrUqWvfuu1Xvn7svWA/Whw1gQ9gINoZNYFPYDDaHLWBL2Aq2hm1gW9gO
tocdYEfYCXaGXWBX2A12hz1gT9gL9pZ9uq1alQy7alUy7KpVybCrViXDrlqVDLtq
VTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alWy7t13qz4/d1+wHqwP
G8CGsBFsDJvAprAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6wG+wOe8CesBfs
Lft0W7UqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61Khl21Khl21apk2FWr
kmFXrUqGXbUqGXbVqmTdu+9W/eHn7gvWg/VhA9gQNoKNYRPYFDaDzWEL2BK2gq1h
G9gWtoPtYQfYEXaCnWEX2BV2g91hD9gT9oK9ZZ9uq1Ylw65alQy7alUy7KpVybCr
ViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alax7V636b3+n
X1qVrAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MOsCPsBDvDLrAr7Aa7
wx6wJ+wFe8s+3dZaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh11oV
DbvWqmjYtVZFw661Khp2rVXRsGutita9+27V++fuC9aD9WED2BA2go1hE9gUNoPN
YQvYEraCrWEb2Ba2g+1hB9gRdoKdYRfYFXaD3WEP2BP2gr1ln26rViXDrlqVDLtq
VTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqV
rHv33arPz90XrAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MOsCPsBDvD
LrAr7Aa7wx6wJ+wFe8s+3VatSoZdtSoZdtWqZNhVq5JhV61Khl21Khl21apk2FWr
kmFXrUqGXbUqGXbVqmTYVauSYVetSoZdtSpZ9+67VX/4ufuC9WB92AA2hI1gY9gE
NoXNYHPYAraErWBr2Aa2he1ge9gBdoSdYGfYBXaF3WB32AP2hL1gb9mn26pVybCr
ViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpV
ybCrViXr3lWr/rvf6ZdWJevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rANbAvbwfaw
A+wIO8HOsAvsCrvB7rAH7Al7wd6yT7e1VkXDrrUqGnatVdGwa62Khl1rVTTsWqui
YddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6J1775b9f65+4L1YH3Y
ADaEjWBj2AQ2hc1gc9gCtoStYGvYBraF7WB72AF2hJ1gZ9gFdoXdYHfYA/aEvWBv
2afbqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqV
DLtqVTLsqlXJsKtWJevefbfq83P3BevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rAN
bAvbwfawA+wIO8HOsAvsCrvB7rAH7Al7wd6yT7dVq5JhV61Khl21Khl21apk2FWr
kmFXrUqGXbUqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61K1r37btUffu6+
YD1YHzaADWEj2Bg2gU1hM9gctoAtYSvYGraBbWE72B52gB1hJ9gZdoFdYTfYHfaA
PWEv2Fv26bZqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpV
ybCrViXDrlqVDLtqVTLsqlXJunfVqv/+d/qlVcl6sD5sABvCRrAxbAKbwmawOWwB
W8JWsDVsA9vCdrA97AA7wk6wM+wCu8JusDvsAXvCXrC37NNtrVXRsGutioZda1U0
7FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ271qpo
3bvvVr1/7r5gPVgfNoANYSPYGDaBTWEz2By2gC1hK9gatoFtYTvYHnaAHWEn2Bl2
gV1hN9gd9oA9YS/YW/bptmpVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXDrlqV
DLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcm6d9+t+vzcfcF6sD5sABvCRrAxbAKb
wmawOWwBW8JWsDVsA9vCdrA97AA7wk6wM+wCu8JusDvsAXvCXrC37NNt1apk2FWr
kmFXrUqGXbUqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61Khl21Khl21apk
2FWrknXvvlv1h5+7L1gP1ocNYEPYCDaGTWBT2Aw2hy1gS9gKtoZtYFvYDraHHWBH
2Al2hl1gV9gNdoc9YE/YC/aWfbqtWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpV
ybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVsu5dtep/+J1+aVWyHqwPG8CG
sBFsDJvAprAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6wG+wOe8CesBfsLft0
W2tVNOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1U07FqromHXWhUN
u9aqaNi1VkXDrrUqWvfuu1Xvn7svWA/Whw1gQ9gINoZNYFPYDDaHLWBL2Aq2hm1g
W9gOtocdYEfYCXaGXWBX2A12hz1gT9gL9pZ9uq1alQy7alUy7KpVybCrViXDrlqV
DLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alWy7t13qz4/d1+w
HqwPG8CGsBFsDJvAprAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6wG+wOe8Ce
sBfsLft0W7UqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61Khl21Khl21apk
2FWrkmFXrUqGXbUqGXbVqmTdu+9W/eHn7gvWg/VhA9gQNoKNYRPYFDaDzWEL2BK2
gq1hG9gWtoPtYQfYEXaCnWEX2BV2g91hD9gT9oK9ZZ9uq1Ylw65alQy7alUy7KpV
ybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alax7V636
H3+nX1qVrAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MOsCPsBDvDLrAr
7Aa7wx6wJ+wFe8s+3dZaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6Jh
11oVDbvWqmjYtVZFw661Khp2rVXRsGutita9+27V++fuC9aD9WED2BA2go1hE9gU
NoPNYQvYEraCrWEb2Ba2g+1hB9gRdoKdYRfYFXaD3WEP2BP2gr1ln26rViXDrlqV
DLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXD
rlqVrHv33arPz90XrAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MOsCPs
BDvDLrAr7Aa7wx6wJ+wFe8s+3VatSoZdtSoZdtWqZNhVq5JhV61Khl21Khl21apk
2FWrkmFXrUqGXbUqGXbVqmTYVauSYVetSoZdtSpZ9+67VX/4ufuC9WB92AA2hI1g
Y9gENoXNYHPYAraErWBr2Aa2he1ge9gBdoSdYGfYBXaF3WB32AP2hL1gb9mn26pV
ybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy
7KpVybCrViXr3lWr/qff6ZdWJevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rANbAvb
wfawA+wIO8HOsAvsCrvB7rAH7Al7wd6yT7e1VkXDrrUqGnatVdGwa62Khl1rVTTs
WquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6J1775b9f65+4L1
YH3YADaEjWBj2AQ2hc1gc9gCtoStYGvYBraF7WB72AF2hJ1gZ9gFdoXdYHfYA/aE
vWBv2afbqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXD
rlqVDLtqVTLsqlXJsKtWJevefbfq83P3BevB+rABbAgbwcawCWwKm8HmsAVsCVvB
1rANbAvbwfawA+wIO8HOsAvsCrvB7rAH7Al7wd6yT7dVq5JhV61Khl21Khl21apk
2FWrkmFXrUqGXbUqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61K1r37btUf
fu6+YD1YHzaADWEj2Bg2gU1hM9gctoAtYSvYGraBbWE72B52gB1hJ9gZdoFdYTfY
HfaAPWEv2Fv26bZqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy
7KpVybCrViXDrlqVDLtqVTLsqlXJunfVqv/5d/qlVcl6sD5sABvCRrAxbAKbwmaw
OWwBW8JWsDVsA9vCdrA97AA7wk6wM+wCu8JusDvsAXvCXrC37NNtrVXRsGutioZd
a1U07FqromHXWhUNu9aqaNi1VkXDrrUqGnatVdGwa62Khl1rVTTsWquiYddaFQ27
1qpo3bvvVr1/7r5gPVgfNoANYSPYGDaBTWEz2By2gC1hK9gatoFtYTvYHnaAHWEn
2Bl2gV1hN9gd9oA9YS/YW/bptmpVMuyqVcmwq1Ylw65alQy7alUy7KpVybCrViXD
rlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcm6d9+t+vzcfcF6sD5sABvCRrAx
bAKbwmawOWwBW8JWsDVsA9vCdrA97AA7wk6wM+wCu8JusDvsAXvCXrC37NNt1apk
2FWrkmFXrUqGXbUqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61Khl21Khl2
1apk2FWrknXvvlv1h5+7L1gP1ocNYEPYCDaGTWBT2Aw2hy1gS9gKtoZtYFvYDraH
HWBH2Al2hl1gV9gNdoc9YE/YC/aWfbqtWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy
7KpVybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVsu5dtep/+Z1+aVWyHqwP
G8CGsBFsDJvAprAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6wG+wOe8CesBfs
Lft0W2tVNOxaq6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutioZda1U07FqromHX
WhUNu9aqaNi1VkXDrrUqWvfuu1Xvn7svWA/Whw1gQ9gINoZNYFPYDDaHLWBL2Aq2
hm1gW9gOtocdYEfYCXaGXWBX2A12hz1gT9gL9pZ9uq1alQy7alUy7KpVybCrViXD
rlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alWy7t13qz4/
d1+wHqwPG8CGsBFsDJvAprAZbA5bwJawFWwN28C2sB1sDzvAjrAT7Ay7wK6wG+wO
e8CesBfsLft0W7UqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61Khl21Khl2
1apk2FWrkmFXrUqGXbUqGXbVqmTdu+9W/eHn7gvWg/VhA9gQNoKNYRPYFDaDzWEL
2BK2gq1hG9gWtoPtYQfYEXaCnWEX2BV2g91hD9gT9oK9ZZ9uq1Ylw65alQy7alUy
7KpVybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alax7
V636X3+nX1qVrAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MOsCPsBDvD
LrAr7Aa7wx6wJ+wFe8s+3dZaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxa
q6Jh11oVDbvWqmjYtVZFw661Khp2rVXRsGutita9+27V++fuC9aD9WED2BA2go1h
E9gUNoPNYQvYEraCrWEb2Ba2g+1hB9gRdoKdYRfYFXaD3WEP2BP2gr1ln26rViXD
rlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCr
ViXDrlqVrHv33arPz90XrAfrwwawIWwEG8MmsClsBpvDFrAlbAVbwzawLWwH28MO
sCPsBDvDLrAr7Aa7wx6wJ+wFe8s+3VatSoZdtSoZdtWqZNhVq5JhV61Khl21Khl2
1apk2FWrkmFXrUqGXbUqGXbVqmTYVauSYVetSoZdtSpZ9+67VX/4ufuC9WB92AA2
hI1gY9gENoXNYHPYAraErWBr2Aa2he1ge9gBdoSdYGfYBXaF3WB32AP2hL1gb9mn
26pVybCrViXDrlqVDLtqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7
alUy7KpVybCrViXr3lWr/rff6ZdWJevB+rABbAgbwcawCWwKm8HmsAVsCVvB1rAN
bAvbwfawA+wIO8HOsAvsCrvB7rAH7Al7wd6yT7e1VkXDrrUqGnatVdGwa62Khl1r
VTTsWquiYddaFQ271qpo2LVWRcOutSoadq1V0bBrrYqGXWtVNOxaq6J1775b9f65
+4L1YH3YADaEjWBj2AQ2hc1gc9gCtoStYGvYBraF7WB72AF2hJ1gZ9gFdoXdYHfY
A/aEvWBv2afbqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7alUy7KpVybCr
ViXDrlqVDLtqVTLsqlXJsKtWJevefbfq83P3BevB+rABbAgbwcawCWwKm8HmsAVs
CVvB1rANbAvbwfawA+wIO8HOsAvsCrvB7rAH7Al7wd6yT7dVq5JhV61Khl21Khl2
1apk2FWrkmFXrUqGXbUqGXbVqmTYVauSYVetSoZdtSoZdtWqZNhVq5JhV61K1r37
btUffu6+YD1YHzaADWEj2Bg2gU1hM9gctoAtYSvYGraBbWE72B52gB1hJ9gZdoFd
YTfYHfaAPWEv2Fv26bZqVTLsqlXJsKtWJcOuWpUMu2pVMuyqVcmwq1Ylw65alQy7
alUy7KpVybCrViXDrlqVDLtqVTLsqlXJunf/L3XYXikRNQMAAAM1EQ==

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