## mark a section (Learn more)

begin require 'lib/charlie' rescue LoadError require 'rubygems' require 'charlie' end class Symbol # This one works with ALL the RVMs. Charlie's default or the Rubinius' one doesn't work with Rubinius! def to_proc Proc.new { |*args| obj = args.shift args.empty? ? obj.__send__(self) : obj.__send__(self, *args) } end if RUBY_VERSION < '1.9' end def TSPGenotype(costs) n = costs.size elements = (0...n).to_a Class.new(Genotype) { define_method(:size){ n } define_method(:elements){ elements } define_method(:fitness){ d=0 (genes + [genes[0]]).each_cons(2) do |a,b| d += costs[a][b] end -d } def initialize @genes = elements.dup.shuffle end def to_s @genes.inspect end use TournamentSelection, PCrossN(EdgeRecombinationCrossover=>0.02, PermutationCrossover=>0.75), PMutateN(InversionMutator=>0.4,InsertionMutator=>0.4) cache_fitness } end class TSPSolver def initialize(costs = {}) @costs = costs @genotype = TSPGenotype(costs) end def solve! population = Population.new(@genotype,100).evolve_silent(1000) fittest = population[0] solution = @costs.sort_by{ |point| fittest.genes.index(point[0]) } # p solution puts fittest.fitness puts fittest end # The coords hash must be in the following form: # { # 0 => [x1, y1], # 1 => [x2, y2], # etc... # } # where x1,y1 are Integers and represent the cartesian coordinates of the "city" of the associated key (number). def self.from_cartesian_coords(coords = {}, real_distance = false) costs = {} coords.each do |point, v| costs[point] = {} end if real_distance raise "Real distance not implemented" else coords.each do |a_key, a_values| coords.each do |b_key, b_values| if a_key != b_key and costs[a_key][b_key] == nil d = Math.sqrt( (a_values[0]-b_values[0])**2 + (a_values[1]-b_values[1])**2 ) costs[a_key][b_key],costs[b_key][a_key] = d,d end end end end solver = self.new(costs) end def self.example(n = 100) grid = (0...n).map{|i| (0...n).map{|j| [i,j] } }.inject{|a,b|a+b} tmp_grid = Array.new(grid) coords = {} n.times do |city_num| coords[city_num] = tmp_grid.delete_at((rand(10000) - coords.size).to_i) end example = self.from_cartesian_coords(coords) end end TSPSolver.example.solve!

This paste will be private.