TraveringSalesman問題のリベンジ

前回は全順序でルートの総合距離を求めていたせいで，12点以上で実行すると終わらなかった．（何処かの記事で読んだけど全順序じゃ何十年とかかってしまうらしい．すごいね．）
そこで今回は，焼きなまし法という手法で書いてみる．

焼きなまし法

確率的に距離が遠くなるルートを選ぶことで大局的な最小値に近い値を求めることができるよ．

実装

とりあえずコードをペタリ．前回のTravelingSalesmanクラスを継承して一部の関数をオーバーライドしています．

https://qiita.com/takakikata/items/0939b92a483409b888ab

traveling_salesman.rb

require 'numo/gnuplot'
class Array
  def swap(idx1,idx2)
    temp = self.dup
    temp[idx1],temp[idx2] = temp[idx2],temp[idx1]
    temp
  end

  def swap!(idx1,idx2)
    self[idx1],self[idx2] = self[idx2],self[idx1]
    self
  end
end

class TravelingSalesman
  def initialize(points_count)
    # the component is {id: Int, x_point: Float, y_point: Float}
    @route = init_route(points_count)
    @routes = [] # for plot
  end

  def execution
    add_routes(@route.clone)
    std_energy = energy(@route)
    puts "first std_energy: #{std_energy}"
    exchanges = mk_full_orders(@route, 1, @route.size-2)
    exchanges.each do |order_item|
      @route[1..@route.size-2] = order_item
      compared_energy = energy(@route)
      if std_energy > compared_energy
        add_routes(@route.clone)
        std_energy = compared_energy
      end
    end
    @route.each do |item|
      puts "min_distance_order_sales_points: #{item[:id]}"
    end
    puts "std_energy: #{std_energy}"
    gnuplot
  end

  def add_routes(hashes)
    @routes << [[], []]
    hashes.each do |hash|
      @routes.last[0] << hash[:x_point]
      @routes.last[1] << hash[:y_point]
    end
  end

  def gnuplot
    points = @routes
    Numo.gnuplot do
      set output: 'traveling_salesman_gnuplot.gif'
      set term: 'gif', animate:true, delay:12, size:[500,500]
      set :nokey
      set size: {ratio: 1.0}
      set xrange: -0.1..1.1
      set yrange: -0.1..1.1
      unset :colorbox
      set palette_defined:'(0 "white", 1 "green")'
      points.each do |item|
        plot item[0], item[1], w: :lp, pt: 6
      end
    end
  end

  def mk_full_orders(hashes, from_index, to_index)
    exchanges = []
    count = 0
    first_nums = []
    first_num = 1
    for i in 0...(to_index - from_index)
      first_num *= (to_index - 1 - from_index - i + 1)
    end
    hashes[from_index..to_index].permutation(to_index - from_index + 1) do |item|
      first_nums << item[0][:id] if count % first_num == 0
      exchanges << item if !first_nums.include?(item.last[:id])
      count += 1
    end
    exchanges
  end

  def dist(point0, point1)
    tmp = Math.sqrt((point0[0] - point1[0])**2 + (point0[1] - point1[1])**2)
    return tmp
  end

  def energy(order_points)
    tmp = 0.0
    for i in 0..order_points.size-2 do
      tmp+=dist([order_points[i][:x_point], order_points[i][:y_point]],
                    [order_points[i+1][:x_point], order_points[i+1][:y_point]])
    end
    return tmp
  end

  def init_route(size)
    order_points = []
    for item in 0...size
      order_points << {id: item, x_point: rand(0..10).to_f/10, y_point: rand(0..10).to_f/10}
    end
    order_points << order_points[0]
    order_points
  end
end

traveling_salesman_exp.rb

require_relative './traveling_salesman.rb'
require 'colorize'

class TraveringSalesmanExp < TravelingSalesman
  def execution
    puts "Please input temperature"
    temp = STDIN.gets.chomp.to_f
    puts "Please input loop_count"
    loop_count = STDIN.gets.chomp.to_i
    first_temp = temp
    std_energy = save_energy
    puts "first std_energy: #{std_energy}"
    change_count = 0
    cool = 0.9
    loop_count.times do
      i = rand(1...@route.size-1)
      j = 0
      loop do
        j = rand(1...@route.size-1)
        break if i != j
      end
      i,j=j,i if i>j
      # exchange1: revese per randam area
      rev = @route[i..j].reverse
      @route[i..j] = rev
      # exchange2: revese 2points
      # @routes.swap!(i, j)
      compared_energy = energy(@route)
      dE = compared_energy - std_energy
      if dE <= 0
        next if dE == 0
        std_energy = save_energy
        change_count+=1
      else
        exp1 = Math.exp(dE * -1 / temp)
        ra = rand()
        if exp1 > ra
          puts "not minimum".red
          std_energy = save_energy
          change_count+=1
        else
          @route[i..j] = rev.reverse
        end
      end
      # temp *= cool
    end
    gnuplot
  end

  def save_energy
    add_routes(@route.clone)
    std_energy = energy(@route)
  end
end

前回とは違い，焼きなまし法では温度が下がるにつれて(繰り返しを行うごとに)確率(遠いルートを選ぶ)が下がっていく様になっている．coolはその温度の減少率を決めている．

また，ルートの選び方は完全にランダムにしている．こうすることで繰り返しのチェックで数十年かかるであろう処理を限りなく有限にしている．
ちなみに，ルートの選び方は２点の入れ替えを行うパターンと一部のルートを逆転させるの２パターンで試したが後者の方が効率的になった気がした．（多分街の数によって効率的なルート変更の方法が違うのかな）

実行は以下のコードで行う．

main.rb

require_relative './traveling_salesman.rb'
require_relative './traveling_salesman_exp.rb'

puts 'Please input city count'
get_count = STDIN.gets.chomp.to_i

traveling_salesman_exp = TraveringSalesmanExp.new(get_count)
traveling_salesman_exp.execution

大事に感じたポイント

ルートの変更は距離が短いルートや確率的に採択されるルートが現れるまでしない．これが大事．理由は，最小ルートの可能性のあるルートを基準に少しずつ真の最小ルートにたどり着く必要があるからです．しかしこれをしてしまうと局所解にハマってしまう可能性があるので確率的にルートを採択する必要があるのです．

まとめ

ちなみに，main.rbを実行したのちにパラメータの入力を以下の様にすると，次のgifの様な結果が得られた．

Please input city count
100
Please input temperature
10
Please input loop_count
1000000

最後はこんな感じ

続・TravelingSalesman（巡回セールスマン）問題を初めてRubyで解いて見た．（焼きなまし法）

TraveringSalesman問題のリベンジ

焼きなまし法

実装

大事に感じたポイント

まとめ