Problem Solving in Networks

;;;;
;;;;
;;;;    code created by
;;;;    joshua becker
;;;;    standing on the shoulders of giants
;;;;
;;;;



;;;;
;;;;  LEARNING POINTS
;;;;
;;;;  extension for this:
;;;;      when is the game over?
;;;;      adding the error factor
;;;;      allowing agents to change more than 1 bit at a time
;;;;      reducing the frequency with which agents copy
;;;;

extensions[array palette]
globals [
  nk-space         ;; an array of length B^K that determines the value of a given allele
  allele-map       ;; an array of length N that maps each digit-location to K other digit-locations
  infinity                             ;; a very large number.
                                         ;; used to denote distance between two turtles which
                                         ;; don't have a connected or unconnected path between them

  b

  global-max
  global-min

  plist            ;; used for
  numpeaks         ;; value distribution

]

turtles-own [
  solution                      ;; a turtle's solution to the complex problem.
  distance-from-other-turtles   ;; list of distances of this node from other turtles
                                ;; (just to make sure the small-world rewiring doesn't leave islands
]

links-own [
  rewired?
]

to setup
  clear-all
  ask patches [ set pcolor white ]
  set infinity 99999  ;; just an arbitrary choice for a large number
  set b 2

  ;; initialize distribution
  set numpeaks 8
  set plist []
  let i 0
  while [i < numpeaks]
  [
    set plist lput random-float 1 plist
    set i i + 1
  ]


  define-allele-values
  set-interdependencies

  spawn-turtles
  wire-ringlat
  reset-ticks
end 

to go
  run-step
  let keepgoing false
  let compare-to [solution] of turtle 0
  ask turtles [
    ; If anybody's doesn't match, then we keep going.
    if (solution != compare-to) [ set keepgoing true ]
  ]
  if (not keepgoing) [ stop ]
end 

;;;  run a step   ;;;

to run-step
  ask turtles [
    ;; step 1:  ask around.  do any of my neighbors have better solutions?
    let best-solution solution
    let better-one? false
    ask link-neighbors [
      if evaluate-fitness solution > evaluate-fitness best-solution
      [
        set best-solution solution
        set better-one? true
      ]
    ]

    ;; step 2:  if nobody had a better one, explore
    if not better-one?
    [
      let found-solution explore
      if evaluate-fitness found-solution > evaluate-fitness solution
      [
        set best-solution found-solution
        set better-one? true
      ]
    ]

    set solution best-solution

    let this-color precision evaluate-fitness solution 2
    ifelse enable-space-analysis
    [ set color palette:scale-scheme "Sequential" "Reds" 7 this-color 0 1 ]
    [ set label this-color ]
  ]
  tick
end 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                                 ;;;
;;; the following set of functions  ;;;
;;; defines the agent behavior.     ;;;
;;;                                 ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to spawn-turtles
  create-turtles Number-Of-Agents [
    ;; each turtle starts with a randomly generated solution
    set solution n-values n [ random b ]
    set label-color black
    set color palette:scale-scheme "Sequential" "Reds" 7 0 0 1
  ]
  set-default-shape turtles "circle"
  layout-circle (sort turtles) max-pxcor - 1
end 

to-report explore
  ;; set the variable 'new answer' to be the turtle's solution variable
  ;; with a randomly chosen item (from 0 to n) replaced with a random value
  ;; from 0 to b that does not include the one already there.
  let replaced-item random n
  let new-answer replace-item replaced-item solution (item random (b - 1) list-not-x (item replaced-item solution) 0 b )
  report new-answer
end 




;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                               ;;;
;;; the following set of methods  ;;;
;;; also known as 'functions'     ;;;
;;; also known as 'to-do-things'  ;;;
;;; defines the nk space.         ;;;
;;;                               ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;


  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;;                                                                                           ;;
  ;; NK space is generated according to Appendix A in                                          ;;
  ;;      Lazer, D., & Friedman, A. (2007). The network structure of exploration and           ;;
  ;;      exploitation. Administrative Science Quarterly, 52(4), 667-694.                      ;;
  ;; There are two key components to this nk-space:                                            ;;
  ;;    a)  the value of a given "allele," which is here represented as a numeric string.      ;;
  ;;        - an agent has N alleles                                                           ;;
  ;;    b)  the pairs of digits that make up each allele.  these are randomly chosen           ;;
  ;;        - each allele has k digits                                                         ;;
  ;;                                                                                           ;;
  ;; The one departure from Lazer's implementation is that here we allow 'b' to be >2, meaning ;;
  ;; that our numeric strings CAN be bitstrings, as his were, but do not have to be.           ;;
  ;;                                                                                           ;;
  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to define-allele-values
  ;; this function defines the value of each
  ;; allele of length k.  together with set-interdependencies
  ;; this defines the nk-space by creating an identifiable
  ;; value for any nk-string
  ;;
  ;; we're not actually directly defining the alleles:  rather,
  ;; we're defining them by their index in a list.  later,
  ;; a converter will take an allele (0 1 1) and convert it
  ;; to a decimal index.
  ;;
  ;; for a given index - allele - the value is randomly chosen
  ;; from a given distribution.

  set nk-space []
  let i 0
  repeat B ^ (K + 1) [
    set nk-space lput nk-distribution nk-space
    set i i + 1
  ]
end 

to set-interdependencies
  ;; for each digit-location in the numeric string,
  ;; this function sets (k - 1) other digit-locations
  ;; to define alleles of size k.

  if k > (n - 1)
  [
    show "Error!  K cannot be greater than N-1.  Setting K to N-1."
    set k (n - 1)
  ]

  set allele-map []
  let i 0
  repeat n
  [
    set allele-map lput fput i n-of k (list-not-x i 0 n) allele-map
    set i i + 1
  ]
end 

to-report nk-distribution
  ;; this function simply outputs a random number
  ;; from the appropriate distribution for the
  ;; desired nk-space.


  let p item (random numpeaks) plist

  let bin_ct 0
  repeat 1000 [
      if random-float 1 < p
      [
        set bin_ct bin_ct + 1
      ]
  ]
  report bin_ct
end 

to-report evaluate-fitness [ test-solution ]
  let fitness 0
  let i 0
  while [i < n]
  [
    let this-allele []
    foreach item i allele-map
    [ [?1] ->
      set this-allele lput item ?1 test-solution this-allele
    ]
    set fitness fitness + item convert-allele this-allele nk-space
    set i i + 1
  ]
  set fitness (fitness / n)

  ; If max-value has been calculated,
  ; normalize the score.

  if (global-max != 0) [
    set fitness fitness / global-max
    set fitness fitness ^ 8
  ]

  report fitness
end 



;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                               ;;;
;;; some generic, non-model       ;;;
;;; utilities.                    ;;;
;;;                               ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to-report list-not-x [x x.min x.max]
  ;; a little utility to draw-without-replacement
  ;; from the range x.min to x.max excluding x.
  let i x.min
  let report-list []
  repeat (x.max - x.min)
  [
    if i != x
    [
      set report-list lput i report-list
    ]
    set i i + 1
  ]
  report report-list
end 

to-report convert-allele [string]
  ;; this utility converts a base b string into
  ;; a decimal number - the index location of that
  ;; allele's value.
  ;; eg, when b = 2, this is a decimal-to-binary converter.
  let i 0
  let decimal-output 0
  repeat length string
  [
    set decimal-output decimal-output + ( ( b ^ (length string - i - 1) ) * item i string )
    set i i + 1
  ]
  report decimal-output
end 

to-report convert-to-allele [ decimal ]
  ;; reverse process of above - so if b=2, this
  ;; is a decimal-to-binary converter.


  let output-string []
  repeat n [
    set output-string fput (decimal mod b) output-string
    set decimal floor (decimal / b)
  ]

  report output-string
end 











;;;;;;;;;;;;;;;;;;;;;
;;;;;;;;;;;;;
;;;
;;; much of this network construction code was
;;; copy-pasted from the uri wilensky small worlds model
;;;
;;; some of it was copy-pasted from previous work of mine
;;;
;;;
;;; remember:
;;;
;;; if you're not copy-pasting,
;;; you're not coding!
;;;
;;;;;;;;;;;;;
;;;;;;;;;;;;;;;;;;;;;

to wire-ringlat
  layout-circle (sort turtles) max-pxcor - 1

  layout-circle (sort turtles with [ who mod 2 = 0] ) max-pxcor - 4


  ;; iterate over the turtles
  let ni 0
  while [ni < count turtles]
  [
    ;; make edges with the next two neighbors
    ;; this makes a lattice with average degree of 4
    let z 1
    while [z <= floor (degree / 2)]
    [
      ask turtle ni [ create-link-with turtle ((ni + z) mod count turtles) ]
      set z z + 1
    ]
    set ni ni + 1
  ]
end 



;; connects the two turtles

to make-edge [node1 node2]
  ask node1 [ create-link-with node2  [
    set rewired? false
  ] ]
end 

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;;                            ;;;
;;;   game state computations  ;;;
;;;                            ;;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

to-report number-of-unique-solutions
  let solution-set []
  ask turtles
  [
    let already-there? false
    foreach solution-set
    [ [?1] ->
      if solution = ?1
      [
        set already-there? true
      ]
    ]
    if not already-there?
    [
      set solution-set lput solution solution-set
    ]
  ]

  report length solution-set
end 

to-report average-score
  let avg 0
  ask turtles [
    set avg avg + evaluate-fitness solution
  ]
  report ( avg / count turtles )
end 

to determine-peaks
  if enable-space-analysis [
    ;; WARNING!!!
    ;; this function can easily take a long time
    ;; if n or b are too high...

    ;; determine decimal value of highest numerical-string
    let mylist []
    repeat n
    [
      set mylist lput (b - 1) mylist
    ]

    let best-answer 0
    let worst-answer 999999999
    let i 0
    while [i <= convert-allele mylist]
    [
      let this-value evaluate-fitness (convert-to-allele i)
      if this-value > best-answer
      [
        set best-answer this-value
      ]
      if this-value < worst-answer
      [
        set worst-answer this-value
      ]
      set i i + 1
    ]

    set global-max best-answer
    set global-min worst-answer
  ]
end 

to-report global-peak

  ;; report global max without recalculating
  report global-max
end 

to-report global-minimum

  ;; report global min without recalculating

  report global-min
end