Simulation Code

All of these programs require a Ruby interpreter and the charlie library. The latter can be installed by using the 'gem' tool included with most Ruby distributions (gem install charlie).

Test tool with graphic user interface. Population is displayed on screen and stats (minimum, maximum, average and standard deviation) are written to stats_history. Ruby/TK required (included in the windows 'one-click' installer, for linux use the package libtcltk-ruby1.8).

Downloadable version available here

%w[rubygems charlie tk].each{|x|require x}

class traveler < FloatListGenotype(1,2..100)
  BONUS = 2
  def choice
    genes[0].between(2,100).round
  end
  def fight_points(other)
    c,oc = choice, other.choice
    c == oc ? [c,c] : c < oc ? [c+BONUS,c-BONUS] : [oc-BONUS,oc+BONUS]
  end
  use NullCrossover
end


BNS,PRB,SZ,GRP,GENS=*0..4
lbl = [["Bonus",2],["Mutation Probability",0.5],["Mutation Size (sigma)",5],["Selection Tournament Size",4],["Generations",1000]]

root  = TkRoot.new() { title "Traveler's Dilemma Simulation" }
mid,bottom = [0,0].map{ TkFrame.new(root).pack('side'=>'top','fill'=>'x','expand'=>true) }

popcv = TkCanvas.new(mid) { width 816; height 100; }.pack
entries = lbl.map{|l,v|
  f = TkFrame.new(bottom).pack('side'=>'top','fill'=>'x')
  TkLabel.new(f) {text l }.pack('side'=>'left')
  TkEntry.new(f) { set v }.pack('side'=>'right')
}
$paused = false
$thr = nil
TkButton.new(bottom) {text "[Run]" ;
   command{ $thr.kill rescue nil
    $thr = Thread.new{
     history = []
     traveler::BONUS = entries[BNS].get.to_f
     klass = Class.new(traveler){ 
       use ListMutator(:probability[entries[PRB].get.to_f],:gaussian[entries[SZ].get.to_f]), CoTournamentSelection(entries[GRP].get.to_i)
       def mutate!; super; genes[0] = genes[0].between(traveler::BONUS,100); end
     }
     pop = Population.new(klass)
     entries[GENS].get.to_i.times{|g| sleep 0.3 while $paused
       gs = pop.evolve_silent(1).map(&:choice).sort
       history << gs.stats
       popcv.delete('all')
       TkcLine.new(popcv,8*2,50,800,50)
       gs.each{|x| TkcOval.new(popcv,8*x-5,45,8*x+5,55) } 
       TkcText.new(popcv,400,75,:text=>"Generation #{g} : " + gs.map{|x|x.to_s}.join(', '))
     }
     File.open('stats_history','w'){|f| history.transpose.each{|a| f << a.join(' ') << "\n" } }
    }
   } 
}.pack
TkButton.new(bottom) {text "[Paused]" ;  command{ $paused = !$paused } }.pack
Tk.mainloop

Program that generated most of our results. When given the reward as a parameter, runs the algorithm for a variety of mutation and tournament size settings and outputs the average strategy in the population after 1000 generations. Ruby/TK not required.

Downloadable version available here

require 'rubygems'
require 'charlie'

exit(puts "GIVE ARG!") unless ARGV[0]

BONUS = ARGV[0].to_i
MIN = BONUS
MAX = 100
class traveler < FloatListGenotype(1,MIN..MAX)
  def choice
    genes[0].between(MIN,MAX).round
  end
  def fight_points(other)
    c,oc = choice, other.choice
    c == oc ? [c,c] : c < oc ? [c+BONUS,c-BONUS] : [oc-BONUS,oc+BONUS]
  end
end


for group_size in (2..20)
  $stderr.puts group_size
  for mut_size in (1..100).map{|x| x / 10.0 }
    klass = Class.new(traveler){
      use ListMutator(:probability[0.5],:gaussian[mut_size]), CoTournamentSelection(group_size)
      def mutate!; super; genes[0] = genes[0].between(MIN,MAX); end
    }
    print Population.new(klass).evolve_silent(1000).map{|x| x.genes[0] }.average, ' '
  end
  puts
end

Analyzing The Traveler's Dilemma

Menu:

PDF Version:

Simulation Code