はじめに
これは「明治大学 Advent Calendar 2018」1日目の記事です。去年(これ)に引き続きトップバッターをやります。
目標
遺伝的アルゴリズムを用いて巡回セールスマン問題を解く。特に、インタラクティブに自在に家を追加できて、その都度遺伝的アルゴリズムを用いて最適な経路を見つけてくれるプログラムを作成する。
イメージとしてはこんな感じ
先にプログラムも貼っておきます
(GitHubのリンクだよ)
巡回セールスマン問題
英語ではTraveling Salesman Problem(TSP) (wikiはこちら).
その名の通り、セールスマンがとある区域の家すべてを巡回する上で最短経路を見つけなさい、という最適化問題の一つ。多項式時間では解けない問題としても有名。
遺伝的アルゴリズム
遺伝的アルゴリズム(Genetic Algorithm; GA)とは生物の交配・突然変異・自然淘汰のサイクルを模倣して、最適化問題を解こうじゃないかという代物。ざっくりとした流れを以下に記載する。
まず問題として最適化したい目的関数$f(x)$があって、その$f(x)$を最小化するような$x^\ast$を求めることを考えよう。
- **(集団の用意)**最適化したい情報を個体として捉えて、N匹の個体$x_1, \ldots, x_N$を用意する。
- (カップル作成) 個体のペアをMペア用意する。
- **(交配・突然変異)**何らかの手法を用いて、各ペアを組み合わせて子供の個体を作成する。この際、生まれた子供にランダムに変化を加える。
- **(自然淘汰)**何らかの手法を用いて、子供と親すべての個体の中から、適応度($f(x_j)$の値)が「良い感じ」の個体だけを残してあとは消す。(自然淘汰)
- **(世代交代)**所望の結果が得られるまで2から4を繰り返す。
ざっくりではあるが、上のような感じ。実装しようとなると
- 「個体」をどう表現するか
- 「交配」をどう行うか
- 「当然変異」をどう行って、どれくらいの確率で起こすか
- 「自然淘汰」でどんな適応度の個体を残すか
が問題点になる。これは最適化問題に応じて変わることなので、問題ごとにプラクティスがある。
巡回セールスマン問題 using 遺伝的アルゴリズム
さて、巡回セールスマン問題を遺伝的アルゴリズムを用いて解いていこう。まずは問題設定を明確にしてから、遺伝的アルゴリズムで解けるような形にしていこう。
巡回セールスマン問題の数学的な表現
$K$個の家$h_1, \ldots, h_K$が2次元空間内に配置されているとする。$h_i$を「$i$番目の家」と呼ぶことにしよう。これらをセールスマンが巡回するわけだから、訪問順序を$n(1), \ldots, n(K)$($n(1) \sim n(K)$は$1 \sim K$を並び替えたもの)とする。
目的関数を$$f(n_1, \ldots, n_K) = \sum_{i = 1}^{K - 1} d(h_{n_i}, h_{n_i + 1})$$とする。なお、$d(x, y)$は2地点間の距離を表す関数。ここでは$d$はいわゆる普通の距離としておこう。そうすれば、$f$は訪問順序が与えられたときにセールスマンがその順序で巡回して移動する総距離になる。
巡回セールスマン問題はこの移動総距離を最小化する巡回順を見つけるこという問題である。
遺伝的アルゴリズムが使える形に
(GitHubのリンクだよ)
最適化問題を遺伝的アルゴリズムを用いて解けるようにするためには、個体の表現・交配方法・当然変異の方法・自然淘汰の方法の4つを決めれば良い。
個体の表現
大きさ$K$の1次元int配列により1個体を表現する。巡回順$n_i(1) \sim n_i(K)$を記録している。これを$N$個用意する。
交配方法
2つ個体(父$x_♂$と母$x_♀$と呼ぶ)を選ぶ。この夫婦に2人の子供を生んでもらうような交配アルゴリズム以下にを記す。
- 父配列からランダムにインデックスを1点$m_♂$を選び、$n_♂(m_♂)$を母配列から探し、そのインデックスを$m_♀$とする。
- $m_♂$に対して母配列の中から$n_♀(m_♂)$を選ぶ。$n_♀(m_♂)$と同じ数を父配列の中から探して、そのインデックスを$m_♂'$とする。
- 大きさ$K$の配列を2つ用意して、1で選んだ$n_♂(m_♂)$と$n_♀(m_♂)$をそれぞれ父親、母親から引き継ぐ。それ以外は順序を保ちながら互いに入れ替える。こうしてできた2つの配列を子供たちとする。
ちょっと複雑なので、例を一つ。
例えば下のような配列で父配列の3番目を選んで交配するとしよう。
-
父配列の3番目の値は3であり、同じインデックスにある母配列の値は2である。
父: 1234 $\to$ 子A: --3-
母: 4321 $\to$ 子B: --2- -
相手の配列にて選ばれた値を子供に受け継ぐ
父: 1234 $\to$ 子A: -23-
母: 4321 $\to$ 子B: -32- -
最後に残った値を順序そのままで交換する
父: 1234 $\to$ 子A: 4231
母: 4321 $\to$ 子B: 1324
突然変異
ある確率$p$で生まれた子供に突然変異を起こす。その変異方法は簡単で突然変異すると決めた個体の配列からランダムで2点を選び、その間の順序を逆転する。
自然淘汰
自然淘汰にはメジャーな方法として「エリート選択」と「ルーレット選択」の２種類がある。エリート選択はその名の通り適応度が高い(今回なら目的関数の値が小さい)上位$K$匹を残す手法。ルーレット選択は適応度に比例した確率で残す手法。エリート選択は局所最適解に陥りやすく、ルーレット選択は良い個体を捨ててしまう可能性が高いという欠点がある。
そのため、折衷案として上位20%はエリート選択により残し、残りはルーレット選択を行うようにする。
プログラム
(GitHubのリンクだよ)
これをProcessingで実装するにあたって、5つのクラスを作成しよう。なお、このプログラムの仕様を再度掲げておくと、
インタラクティブに自在に家を追加できて、その都度遺伝的アルゴリズムを用いて最適な経路を見つけてくれるプログラム
である。
- Individualクラス: 個体を表し巡回順と適応度を持つ
- Crossクラス: 交配や突然変異を行って子供を作成する
- Environmentクラス: 個体を統括して、自然淘汰を行う
- Graphicクラス: 描画用
- TravellingSalesmanProblemクラス: 全部をまとめあげる
#実行結果
(目標に載せたのと一緒です)
家を増やしても勝手に遺伝的アルゴリズムが最適な経路を探してくれる
結論
巡回セールスマン問題に適した形で遺伝的アルゴリズムを実装して、インタラクティブに最適な経路を見つけるプログラムが作れた。