巡回サンタクロース問題を遺伝的アルゴリズムで解く

はじめに

今年もクリスマスがやってきますね（吐血）
皆さんクリスマスの予定は出来ましたか？
私はないです（血涙）

予定がない人は気になる人に一旦，声を掛けてみましょう！
予定がある人は素敵なプレゼントを好きな人に買ってくださｄｊふぁおｓｈｄふぉあｄｆｄｓｊふぁｋｊｆｈごじｌｋ

さてクリスマスと言えばいい子にはプレゼントが届きますよね．
私はサンタのコスプレを着てくれる彼女が欲しいです．多分いい子にしてないのでこないです．

というわけで今回はクリスマスっぽいアルゴリズムの話をします
取り扱うのはtravelling santa claus problem(巡回サンタクロース問題)(以下TSP)です．
まずTSPはどんな問題かというと

あるN個の子どもの家があります．サンタは，各子供の家を必ず１回ずつ訪れて，すべての家にプレゼントを届けます．
「こどもたちの家の位置の集合」と「各家と家との距離」が与えられたとき、サンタの総移動距離が最小のコースを求めよ。

と言った感じです．

問題の難しさ

普通に全ての道順を計算して一番総移動距離が最小のコースを探せばいいだけじゃん？
楽勝じゃねと思った方もいるかもしれないです．

では全ての道順を探す方法だとどれくらいになるのでしょうか？
子供の家の数Nに対し，(N-1)!/2の道順があります．
これがどれくらいの大きさかというと
N=10のとき181440通り
N=100のとき
466631077219720763408496194281333502453579841321908107342964819476087999966149578044707319880782591431268489604136118791255926054584320000000000000000000000
通りの道順が存在します．
仮に1秒間に10億通りの計算を行うことができるコンピュータを使うと，列挙法ではN = 5のとき0.0000001秒、N = 10のとき0.0003628秒、N = 20のとき2432902008秒(= 約77年)かかります．
全ての道順を求めてその中からベストを選ぶようなやり方はとうてい無理なことが分かりますよね．
また今回は詳しく触れませんが，TSPはNP困難と呼ばれる問題です．
厳密にいうと，一番短い最短経路を求めるTSPがNP困難，あるコストより少ない経路（最適性は保証されないけど，ある程度良い経路を見つける）を求めるTSPはNP完全です．
詳しくはこの記事とか見るといいと思います．http://qiita.com/jkr_2255/items/e02362568ff1294fa0cd
したがって．TSPではベスト（厳密解）ではないが，概ね正しいであろう近似解を探す近似アルゴリズムが古くから提案されています．

TSPを解く近似アルゴリズム

• 焼きなまし法
• 局所探索法
• 遺伝的アルゴリズム
• タブー探索法

上記のような方法があります．
今回はこの中の遺伝的アルゴリズムをつかったTSPの解法手法を説明します．

遺伝的アルゴリズム（Genetic Algorithm）とは

生物進化は，優れた個体同士が交配して子供をつくり，その子供の中からさらに，環境に適応した個体のみが次の世代を残すことが出来ることで，より良い個体が選別され種が進化していきます．このメカニズムを真似たものが遺伝的アルゴリズムです．

例えば史上最高のイケメンと美女を生み出したいとします．
1.イケメンと美女を100人ずつ用意します.（初期集団の作成）
2.互いに交配して彼らの子供を男女100人ずつ用意します.(交叉，突然変異)
3.顔に点数をつけます．(新しい解の評価)
4.親と子の集団から顔の点数をもとに次世代に残すべき男女を100人選びます．(次世代の集団に残る解の選択)
2〜4を何回も繰り返します．
終了条件を満たした段階で停止し、その時一番のイケメンと美女が史上最高のイケメンと美女です．大雑把に説明するとこれが遺伝的アルゴリズムです笑.

厳密な説明は省きますが，もっと詳しくメカニズムを知りたい人とかはこれとかを見るといいと思います．
http://www.sist.ac.jp/~kanakubo/research/evolutionary_computing/genetic_algorithms.html
次はTSPを遺伝的アルゴリズムに適応する上での問題点を考えていきます．

どのように各個体を表現するか？

まずどのようにそれぞれの個体を表現するかですが，訪れる子供の家に番号を振ります．
そして[2,5,4,1,3]であれば家2->家5->家4->家1->家3の順に訪問することを意味します．

個体の評価

個体同士をどちらがどれだけ優れているか判断するための関数が必要です．
今回は距離のコストを評価関数にしています．
したがって[2,5,4,1,3]であれば，家2->家5->家4->家1->家3へ移動する際のコストの合計が評価関数になり，値が小さいものほど移動距離が小さいので優れた個体であると判断できますね．

どのような交叉をすべきか

交叉では親子体を2つ選んでその親個体から子個体を生成します．
その上で重要なことの一つに致死個体を生み出すような交叉を避けるということがあります．

致死個体とは，制約を満たさないなどで，存在してはいけない個体のことです．
TSPではすべての家を一度だけという制約があります．
したがって[2,4,4,2,3]のように同じ家を複数回訪れるような個体がTSPでは致死個体に当たります．

これを避けるようなような交叉を用います．今回は順序交叉と呼ばれる方法を取ります．

順序交叉

順序交叉は片方の親からは一部をそのままに受け継ぎ，残りの部分については相対的な順番は保存しつつ受け継ぐ方法です． 例として次の２つの親からの交叉を考えます．
　p1=(1 2 3 | 4 5 6 7 | 8 9)
　p2=(4 5 2 | 1 8 7 6 | 9 3)
先ず２切断点間はそのままコピーする．
　c1=(* * * | 4 5 6 7 | * )
　c2=( * * | 1 8 7 6 | * *)
次に第２切断点から開始して右回りに順序を保ちながら他の親をコピーする． その際に既定のものと衝突するものがあれば除く．
例えば，子 c1について見てみると，第２の親 p2 の順序は
　9 - 3 - 4 - 5 - 2 - 1 - 8 - 7 - 6
となるが子 c1 と衝突するもの（4, 5, 6, 7）を除くと
　9 - 3 - 2 - 1 - 8
となるので，これを c1 に挿入するとつぎのとおりになる．
　c1=(2 1 8 | 4 5 6 7 | 9 3)
同様にして， c2 がつぎのように得られます．
　c2=(3 4 5 | 1 8 7 6 | 9 2)
こうすることで先ほどの制約をみたしたまま，親の性質を引き継いだ子個体が生成できますね．
コード部分では次のように実装しています．

def order_crossover(p1, p2, house_num)
  cr_point1, cr_point2 = make_rand_num(house_num - 1)
  c1 = p2.slice(cr_point1..cr_point2 )
  c2 = p1.slice(cr_point1..cr_point2 )
  order_a1 = delete_include(p1.slice((cr_point2+1)..(house_num-1)).concat(p1.slice(0..cr_point2)), c1)
  order_a2 = delete_include(p2.slice((cr_point2+1)..(house_num-1)).concat(p2.slice(0..cr_point2)), c2)
  (house_num - 1 - cr_point2).times do
    c1 << order_a1.slice!(0)
    c2 << order_a2.slice!(0)
  end
  c1 = order_a1.concat(c1)
  c2 = order_a2.concat(c2)
  return c1, c2
end

交叉する親個体をどのように選ぶか

GAにおいては選択する機会が二回あります．子個体を生成する親のペアを選択するときと，
次世代に残す個体を選ぶ時です.
まずひとつ目の交叉する親子体をどのように選ぶかを説明します．

子世代をつくるとき，出来るだけ良い親から子供をつくりたいですよね．しかし同じ親ばかりから子供を作っていると，同じような解ばかりがうまれ，多様性を失ってしまい，探索が収束してしまいます．
生物においても近親同士での交配はあまり良い個体を生むことが出来ませんよね．
一見評価の低い個体が最適解の持つ因子を持つこともありえます．つまり遺伝的アルゴリズムではダメな子の情報がたまに交じることが，より探索を進めていく上で必要なのですね．
したがって今回はルーレット選択という選択方法を取ります．
ルーレット選択では各個体が選択される確率，選択確率P(x_i)を用います．

sum = \sum_{k=1}^{n} f(x_k) \\
P(x_i) =\frac{sum -f(x_i)}{sum} 

選択確率は親子体x_iがより優れ得た個体であるほど，大きくなります．
この選択確率をもとに親子体を選択することで，おおむね評価の高い親から子供が生成されるが，悪い個体もたまに親として選ばれることがあるような状態を実現できます．

次世代に残す個体をどう選択するか？

次世代に残す個体をどう選ぶかですが，今回はエリート戦略を使います．子個体全てを次世代の親子体にするのではなく，親世代の中で一番良い個体と，子個体の和集合を次世代とします．
今回のコードでは１世代を30個とし，子個体を29個生成，親個体の最も良い個体1つの和集合を次世代とします．

アルゴリズムのコード

最後に全体のコードを貼っときます．

require 'matrix'

def make_distance_arry(house_num)
  Matrix.build(house_num){|i, j| i == j ? 0 : rand(1..10)}.to_a
end

def init_path_array(house_num, population)
  population.times.map{[*0...(house_num)].shuffle}
end

def path_length(path)
  path.each_cons(2).map{|i, j| $distance_array[i][j]}.inject(&:+)
end

def make_rand_num(max)
  [*0...(max-1)].sample(2).minmax
end

def make_rand_num_array(max, num)
  num_array = [*0...(max-1)].shuffle
  num_array.slice(0, num)
end

#配列aから配列bの要素があれば取り除く
def delete_include(a, b)
  x = a.dup
  y = b.dup
  y.each do |i|
    x.delete(i)
  end
  x
end

def find_best_path(path_array)
  best_array = path_array.first
  path_array.each do |a|
    best_array = a if path_length(a) < path_length(best_array)
  end
  best_array
end

def order_crossover(p1, p2, house_num)
  cr_point1, cr_point2 = make_rand_num(house_num - 1)
  c1 = p2.slice(cr_point1..cr_point2 )
  c2 = p1.slice(cr_point1..cr_point2 )
  order_a1 = delete_include(p1.slice((cr_point2+1)..(house_num-1)).concat(p1.slice(0..cr_point2)), c1)
  order_a2 = delete_include(p2.slice((cr_point2+1)..(house_num-1)).concat(p2.slice(0..cr_point2)), c2)
  (house_num - 1 - cr_point2).times do
    c1 << order_a1.slice!(0)
    c2 << order_a2.slice!(0)
  end
  c1 = order_a1.concat(c1)
  c2 = order_a2.concat(c2)
  return c1, c2
end

def calculate_fittness_array(parent_path_pop)
  sum = 0
  array = parent_path_pop.dup
  array.map! { |e| path_length(e) }
  array.each do |a|
    sum += a
  end
  array.map! { |e| (sum - e)/ sum  }
  array
end

def select_in_roulette(fittness, path_array)
  p_array = path_array.dup
  fittness.each_with_index do |f, i|
    return p_array[i] if Random.new.rand < f
  end
  return p_array.shuffle[0]
end


population = 30
house_num = 20
tournament_size = 10
generation_num = 1

#初期化
$distance_array = make_distance_arry(house_num)
parent_path_pop = init_path_array(house_num, population).dup
best_path_length = path_length(find_best_path(parent_path_pop))
#終了条件(500世代目まで生成)を満たすまで繰り返し
while generation_num < 500
  children_path_array = []
  #複製選択 ルーレット選択
  parent_path_pop.sort!{|a,b| path_length(b)<=>path_length(a)}
  fittness = calculate_fittness_array(parent_path_pop)
  (population-1).times do |i|
    p1 = select_in_roulette(fittness, parent_path_pop)
    p2 = select_in_roulette(fittness, parent_path_pop)
    temp_c_array = order_crossover(p1, p2, house_num)
    children_path_array << temp_c_array[0]
  end
  #突然変異は今回は省略
  #生存選択はエリート戦略,子世代に一つだけ最も優れた親を残す．
  children_path_array << find_best_path(parent_path_pop)
  parent_path_pop = children_path_array.dup
  #解が更新したら出力
  if best_path_length > path_length(find_best_path(parent_path_pop))
    best_path_length = path_length(find_best_path(parent_path_pop))
    puts "#{generation_num}世代目の最良個体は#{find_best_path(parent_path_pop)}で距離は#{best_path_length}です"
  end
  generation_num += 1
end
puts "最良個体は#{find_best_path(parent_path_pop)}で距離は#{best_path_length}です"

まとめ

遺伝的アルゴリズムは他にも新幹線やロケット，半導体の形状を決めたり，楽曲の自動生成，文章の自動要約，シフトの自動スケジューリングなど様々な問題に対して使われます．
そしてGAはどんな問題でも，最適化したい個体を遺伝子表現できれば解けますが，あくまで最終手段です．ランダムに闇雲に動いて，たまたま上手くいった経験を利用し，突き進むようなアルゴリズムですので必ずしも上手く行くことは保証されません．こういうふうに探索を進めれば良いという基準があったときにはそれに基づく探索アルゴリズムの方が当然良いです．そのような基準がないときに，どうしようもなく使う手法が遺伝的アルゴリズムです．

恋人が欲しい季節になりましたが，本やネットの記事でこうしろと書いてあることの通りにやってもうまくいかないものです．そんな時こそ，GAのようにとにかく闇雲に動き，たまたま上手くいった方向に突き進んでいくことで，素敵な恋人が見つかるかもしれませんね．