--- title: 遺伝的アルゴリズムで巡回セールスマン問題を解いてみる(理論編) tags: GeneticAlgorithm TravelingSalesmanProblem Python author: masaru slide: false --- # はじめに 「巡回セールスマン問題　遺伝的アルゴリズム」でググるとたくさんヒットすることを自分でもやってみました。 - [理論編](https://qiita.com/masaru/items/729a0a0e2d7f305e8e90) - [Python コード編](https://qiita.com/masaru/items/07a63f1f6e0edfbe1288) - [実行結果編](https://qiita.com/masaru/items/22b70c8e1e937814212a) # 概要 ## 巡回セールスマン問題(Traveling Salesman Problem) **巡回セールスマン問題** とは、$N$ 個の点すべてを 1 回ずつ通って元の点に戻る最短の経路を探索する問題です。 $N$ 点を全て通って戻ってくる経路の総数は $(N-1)!/2$ 通りあります。 3 点であれば 1 通りです。 4 点であれば 3 通りです。 5 点であれば 12 通りです。 点が増えると経路の総数は爆発的に増えていきます。 その中から最短の経路を見つけようとすると膨大な時間がかかります。 しかし、条件付きであれば実用的な時間内で経路を見つけられます。 例えば、点が凸多角形の頂点にあると分かっていれば、最短経路はその凸多角形です。 また、**ほぼ**最短で良ければ、遺伝的アルゴリズムやアニーリング法や自己組織化マップなど様々な探索法があります。 ## 遺伝的アルゴリズム **遺伝的アルゴリズム** は、組み合わせ最適化問題の探索アルゴリズムの一つで、生物の進化をモチーフにしています。巡回セールスマン問題も組み合わせ最適化問題の一つなので、遺伝的アルゴリズムが使えます。 遺伝的アルゴリズムの探索手順は以下の通りです。 1. 初めに、一定数の組み合わせを用意します。 1. 既存の組み合わせから何通りものペアを選びます。 1. ペア同士で互いの組み合わせの一部を交換して新しい組み合わせをつくります。 1. 新しい組み合わせの良さを測ります。 1. 良い組み合わせを一定数だけ残して残りは捨てます。 1. ペアを選んで〜捨てて、を満足するまで繰り返します。 遺伝的アルゴリズムでは、生物になぞらえて、次の言葉を使って説明します。 - **個体** ... 一つ一つの組み合わせです。 - **染色体** ... 組み合わせを適当な方法で表現したものです。 - **遺伝子** ... 染色体の基本構成要素です。 - **適合度** ... それぞれの個体について、問題に対する良さを測る数値です。 - **世代** ... 個体の集合です。 - **交雑** ... 既存の個体の染色体から新しい個体の染色体を生成する手順です。 - **突然変異** ... 1 個体の染色体を変化させて新しい個体を生成します。 - **交叉** ... 2 個体の染色体を組み合わせて新しい個体を作ります。 - **選択** ... 世代の中から、適応度の高さに応じて、交雑に使う個体を選びます。 - **淘汰** ... 交雑してできた個体の集合と親世代から、適応度が低い個体を捨てて一定数の個体を次の世代を作ることです。 [静岡理工科大学　菅沼研究室　による解説](https://www.sist.ac.jp/~suganuma/kougi/other_lecture/SE/opt/GA/GA.htm) [遺伝的アルゴリズム （Genetic Algorithm）を始めよう！ - SlideShare](https://www.slideshare.net/kzokm/genetic-algorithm-41617242) # 遺伝的アルゴリズムによる巡回セールスマン問題 巡回セールスマン問題に合わせて遺伝的アルゴリズムをアレンジします。 ## 個体（セールスマン） セールスマンが通る $N+1$ 個の点を $p_0, p_1, \dots, p_N$ とします。 $p_0$ からスタートして、点の番号順に全ての点を通って $p_0$ に戻ってくる経路は、$p_0, p_1, \dots, p_N, p_0$ と表せます。 $p_1, p_2, \dots, p_N, p_0, p_1$ は、同じ輪を $p_1$ からスタートした経路になります。 輪になった経路の長さは、どの点を始点に選んでも同じなので、始点を $p_0$ に固定して、経路を $p_{i_1}, \dots, p_{i_N}$ と表します。 また、全体を平行移動しても経路の長さは同じなので、$p_0 = O$ とし、その他の点も平行移動します。 こうしてできた経路を個体とします。 ## 適応度 適応度には、個体が表す経路の長さを使います。 二点 $p, p'$ 間の距離を $d(p, p')$ としたとき、経路 $p_{i_1}, \dots p_{i_N}$ の長さは、$d(p_0, p_{i_1})+d(p_0, p_{i_N}+\sum_{k=1}^{N-1}d(p_{i_k}, p_{i_{k+1}})$ になります。 長さが小さいほど良い経路です。 適応度は数値が大きいほど良いので、長さの逆数か符号反転を使います。 今回は符号反転を使いました。 > 適応度を、数値が小さいほど良いとするなら、長さをそのまま使います。 ## 選択 交雑の際、親世代の全ての個体から子世代を生成するのではなく、適応度が高い個体ほど子を残しやすいように**選択**を行います。 また、淘汰の際にも、適応度が高い個体ほど子世代に残りやすいように選択をします。 主な選択方法は 3 通りあります。 どれも一長一短あるので組み合わせて使います。 ### エリート選択 適応度が高い順に選択します。 優秀な個体が残るので早く収束します。 反面、初期の優秀な個体の影響が強く、世代を重ねると多様性が下がって進化の袋小路(=局所解)に陥る可能性があります。 ### ルーレット選択 適応度から計算された確率に基づいて選択します。 適応度が低い遺伝子も(確率は低いですが)残るため、多様性が下がりません。反面、適応度が高い遺伝子が破棄されて、解にたどり着けないことがあります。 確率の計算方法はいろいろあります。 - ルーレット確率 ... $(個体の適応度) \div (世代の適応度の和）$。適応度が正数で、分散が大きい場合に有効です。 - 順位確率 ... 適応度の順位と確率を 1:1 で紐付けます。適応度が負数でも使えます。適応度の差が確率の差に対応しなくなります。 - 関数変換 ... シグモイド関数などで適応度を確率に変換します。ルーレット確率よりも適応度が高い個体が選ばれやすくなります。 ### トーナメント選択 個体群からランダムに $n$ 個体を取り出して適応度が最も高い個体を残します。 これを、必要な個体数が集まるまで繰り返します。 適応度が低い遺伝子も確率的に残るため、多様性があまり下がりません。反面、適応度が高い遺伝子が破棄されて、解にたどり着けないことがあります。 ## 遺伝子と染色体 経路の表現方法(コーディング)を 2 通り紹介します。 ### 順列コーディング(Permutation Encoding) 点の番号をそのまま並べる表現方法です。 遺伝子は、点の番号 $1, \dots, N$ です。 染色体は、遺伝子が重複なく並んだ列 $g_1, \dots, g_N$ です。 $g_i = k$ であれば、$i$ 番目に $p_k$ を通ることを表します。 下は、5 点を通る経路の例とその順列コーディングです。 ```math \{ p_4, p_1, p_3, p_5, p_2 \} \rightarrow 4, 1, 3, 5, 2 ``` この表現方法では、常に $g_i \neq g_j (i \neq j)$ が保たれます。 ### 序数コーディング > 序数コーディングは勝手につけた名前です。正式な名前はわかりませんでした。 通過した点を除外した点列の序数を使う表現方法です。 $i$ 番目の遺伝子 $g_i$ は、残っている点の個数 $N-i+1$ までの数値をとります。 点列 $P_1 = p_1, p_2, \dots, p_N$ があるとき、$g_i$ を決める手順は次の通りです。 1. 点列 $1, 2, \dots, N$ を $P_1$ とします。 1. 1 番目に通る点 $p_i$ が点列 $P_1$ 中の何番目にあるか調べます。$i'$ 番目にあれば、$g_1=i'$ とします。$P_1$ から $p_i$ を除いた点列 $P_2$ を作ります。 1. 2 番目に通る点 $p_j$ が点列 $P_2$ 中の何番目にあるか調べます。$j'$ 番目にあれば、$g_2=j'$ とします。$P_2$ から $p_3$ を除いた点列 $P_3$ を作ります。 1. 以下同様に続けていきます。 下は、5 点を通る経路の例とその序数コーディングです。 ```math \{ p_4, p_1, p_3, p_5, p_2 \} \rightarrow 4, 1, 2, 2, 1 \\ \begin{array}{lll} p_1, p_2, p_3, p_4, p_5 & -, -, -, -, - & 数列中の位置を記録しながら点を取り除く \\ p_1, p_2, p_3, p_5 & 4, -, -, -, - & p_4 は 4 番目 \\ p_2, p_3, p_5 & 4, 1, -, -, - & p_1 は 1 番目 \\ p_2, p_5 & 4, 1, 2, -, - & p_3 は 2 番目 \\ p_2 & 4, 1, 2, 2, - & p_5 は 2 番目 \\ & 4, 1, 2, 2, 1 & p_2 は 1 番目 \end{array} ``` この表現方法では、常に $g_i \le N-i+1$ が保たれます。 その代わり、染色体中に同じ数値が現れる($g_i = g_j (i \neq j)$ となる)ことがあります。 遺伝子 $g_i$ と点の対応は直感的ではなく、$g_1, \dots, g_{i-1}$ を調べないとわかりません。 ## 交雑 生物の交雑では、対になる染色体同士を交換したり、染色体同士で対応する区間を交換するのが一般的です。 また、遺伝子の位置に制約がなく、染色体の長さも融通が利くので、多様な突然変異があります。 セールスマンの染色体にはコーディングに応じた制約があるので、その範囲で交叉や突然変異を定義します。 - 順列コーディングでは遺伝子が 1 回ずつという制約があるので、染色体同士の交叉では重複がないような操作が必要です（幸いながら、賢い人たちが順序の遺伝子向けの交叉を考案してくれています）。一方で、染色体の中で遺伝子を交換するのは、制約を破らないので簡単に記述できます。 - 序数コーディングでは遺伝子の位置で制約が決まっているため、遺伝子の位置を交換するような操作より、染色体同士で同じ位置の遺伝子を交換したり、単純に遺伝子を変更するような操作が簡単に記述できます。 ### 順列コーディングの交叉 #### 循環交叉 (Cycle Crossover: CX) 2 つの染色体から、点の組と位置の組が等しいグループを探し、グループ同士を交換します。 1. ランダムな遺伝子 $q_1$ を選択します。 1. $q_i$ まで決まっているとき、親 1 から $q_i$ を探し、その位置を $k_{i+1}$ とします。 1. 親 2 の $k_{i+1}$ 番目の遺伝子 $h_{k_{i+1}}$ が表す点を $q_{i+1}$ とします。 1. $q_{i+1} = q_1$ なら終了します。そうでなければ $q_{i+1}$ について繰り返します。 ```math \begin{array}{cc} 親 1 & 1\acute{2}345678 \\ 親 2 & 6\grave{7}852341 \end{array} \rightarrow \begin{array}{c} 1\acute{2}3456\acute{7}8 \\ 6\grave{7}8523\grave{4}1 \end{array} \rightarrow \dots \rightarrow \begin{array}{c} 1\acute{2}3\acute{4}\acute{5}6\acute{7}8 \\ 6\grave{7}8\grave{5}\grave{2}3\grave{4}1 \end{array} \rightarrow \begin{array}{cc} 子 1 & 1\hat{7}3\hat{5}\hat{2}6\hat{4}8 \\ 子 2 & 6\hat{2}8\hat{4}\hat{5}3\hat{7}1 \end{array} ``` #### 部分的交叉 (Partial Crossover) ランダムな位置 $r$ を選び、親 1 と親 2 でその位置の遺伝子 ${g_1}_r, {g_2}_r$ を調べます。 親 1 と親 2 のそれぞれで、遺伝子 ${g_1}_r, {g_2}_r$ を交換します。 これを何度か繰り返して、子 1 と子 2 の染色体を生成します。 ```math \begin{array}{cc} 親 1 & 12\acute{3}4567\grave{8} \\ 親 2 & 67\grave{8}52\acute{3}41 \end{array} \rightarrow \begin{array}{cc} 子 1 & 12\acute{8}4567\acute{3} \\ 子 2 & 67\grave{3}52\grave{8}41 \end{array} ``` #### 順序交叉 (Oder Crossover: OX) 親 1 は、染色体のランダムな区間をそのまま子に引き継ぎます。 親 2 は、子に足りない遺伝子を順序を崩さないように引き継いで空欄を埋めます。 ```math \begin{array}{cc} 親 1 & \acute{1}\acute{2}\acute{3}|456|\acute{7}\acute{8} \\ 親 2 & 6\grave{7}\grave{8}5\grave{2}\grave{3}4\grave{1} \end{array} \rightarrow \begin{array}{cc} 子 & \grave{7}\grave{8}\grave{2}|456|\grave{3}\grave{1} \end{array} ``` #### 一様順序交叉 (Order Based Crossover: OX2) いくつかのランダムな位置 $r_1, \dots, r_k$ を決めて、親 1 でそれらの位置にある遺伝子 $g_{r_1}, \dots, g_{r_k}$ を調べます。 親 2 のそれらの遺伝子 $g_{r_1}, \dots, g_{r_k}$ を、親 1 での順序に並べ替えて、子 1 の染色体を生成します。 親 1 と親 2 を入れ替えて同様の操作をして、子 2 を生成します。 ```math \begin{array}{cc} 親 1 & 1\acute{2}3\acute{4}\acute{5}67\acute{8} \\ 親 2 & 67\grave{8}\grave{5}\grave{2}3\grave{4}1 \end{array} \rightarrow \begin{array}{cc} 子 1 & 67\acute{2}\acute{4}\acute{5}3\acute{8}1 \end{array} ``` #### 一様位置交叉 (Position Based Crossover: POX) いくつかのランダムな位置 $r_1, \dots, r_k$ を決めます。 子 1 は、親 1 からそれらの位置にある遺伝子 $g_{r_1}, \dots, g_{r_k}$ をそのまま受け継ぎます。 足りない遺伝子は親 2 から順序を崩さないように受け継ぎます。 親 1 と親 2 を入れ替えて同様の操作をして、子 2 を生成します。 ```math \begin{array}{cc} 親 1 & 1\acute{2}3\acute{4}\acute{5}67\acute{8} \\ 親 2 & \grave{6}\grave{7}852\grave{3}4\grave{1} \end{array} \rightarrow \begin{array}{cc} 子 & \grave{6}\acute{2}\grave{7}\acute{4}\acute{5}\grave{3}\grave{1}\acute{8} \end{array} ``` > 子が 1 個体だけならば、一様順序交叉と一様位置交叉は等価になります。 #### サブツアー交換交叉(Sub tour Exchange Crossover: SXX) 2 つの染色体から同じ組の遺伝子が並んだ区間を探し、その区間同士を交換して子 1, 2 を生成します。 ```math \begin{array}{cc} 親 1 & 1\acute{2}\acute{3}\acute{4}\acute{5}678 \\ 親 2 & 678\grave{5}\grave{3}\grave{2}\grave{4}1 \end{array} \rightarrow \begin{array}{cc} 子 1 & 1\grave{5}\grave{3}\grave{2}\grave{4}678 \\ 子 2 & 678\acute{2}\acute{3}\acute{4}\acute{5}1 \end{array} ``` #### その他の交叉 - 部分写像交叉 (Partial Mapped Crossover: PMX) - 辺組換え交叉 (Edge Recombination Crossover: ERX) - 枝組立て交叉 (Edge Assembly Crossover: EAX) ### 順列コーディングの突然変異 #### 交換 (Swap) ランダムに選択した 2 区間について、遺伝子を区間ごと交換します。 ```math \begin{array}{cc} 親 & 1|\acute{2}\acute{3}\acute{4}|56|\grave{7}\grave{8}| \end{array} \rightarrow \begin{array}{cc} 子 & 1|\grave{7}\grave{8}|56|\acute{2}\acute{3}\acute{4}| \end{array} ``` #### 転座 (Translocation) ランダムに選択した区間を別の位置に移動します。 ```math \begin{array}{cc} 親 & 1|\acute{2}\acute{3}\acute{4}\acute{5}|678 \end{array} \rightarrow \begin{array}{cc} 子 & 167|\acute{2}\acute{3}\acute{4}\acute{5}|8 \end{array} ``` #### 位置移動 2 つの遺伝子 $g_1, g_2$ をランダムに選択して、$g_2$ の前に $g_1$ を移動します。 転座の特殊形です。 ```math \begin{array}{cc} 親 & 1\acute{2}3456\grave{7}8 \end{array} \rightarrow \begin{array}{cc} 子 & 1\grave{7}\acute{2}34568 \end{array} ``` #### 逆位 (Inversion) ランダムに選択した区間について、遺伝子の順序を反転します。 ```math \begin{array}{cc} 親 & 1|\acute{2}\acute{3}\acute{4}|5678 \end{array} \rightarrow \begin{array}{cc} 子 & 1|\acute{4}\acute{3}\acute{2}|5678 \end{array} ``` #### 撹拌 (Scramble) ランダムに選択した区間について、遺伝子の順序をランダムに並べ替えます。 ```math \begin{array}{cc} 親 & 1|\acute{2}\acute{3}\acute{4}\acute{5}|678 \end{array} \rightarrow \begin{array}{cc} 子 & 1|\acute{4}\acute{2}\acute{5}\acute{3}|678 \end{array} ``` ### 序数コーディングの交叉 #### 1 点交叉 (Single Point Crossover) 2 つの染色体をランダムな 1 箇所で切断して交換します。 ```math \begin{array}{cc} 親1 & g_1 g_2 g_3 | g_4 g_5 g_6 \\ 親2 & h_1 h_2 h_3 | h_4 h_5 h_6 \end{array} \rightarrow \begin{array}{cc} 子1 & g_1 g_2 g_3 | h_4 h_5 h_6 \\ 子2 & h_1 h_2 h_3 | g_4 g_5 g_6 \end{array} ``` #### 2 点交叉 (2 Points Crossover) 2 つの染色体をランダムな 2 箇所で切断した区間を交換します。 ```math \begin{array}{cc} 親1 & g_1 g_2 | g_3 g_4 g_5 | g_6 \\ 親2 & h_1 h_2 | h_3 h_4 h_5 | h_6 \end{array} \rightarrow \begin{array}{cc} 子1 & g_1 g_2 | h_3 h_4 h_5 | g_6 \\ 子2 & h_1 h_2 | g_3 g_4 g_5 | h_6 \end{array} ``` #### 多点交叉 (Multi Points Crossover) 2 つの染色体をランダムな数箇所で切断した区間を交換します。 ```math \begin{array}{cc} 親1 & g_1 | g_2 g_3 | g_4 g_5 | g_6 \\ 親2 & h_1 | h_2 h_3 | h_4 h_5 | h_6 \end{array} \rightarrow \begin{array}{cc} 子1 & g_1 | h_2 h_3 | g_4 g_5 | h_6 \\ 子2 & h_1 | g_2 g_3 | h_4 h_5 | g_6 \end{array} ``` #### 一様交叉 (Uniform Crossover) 2 つの染色体のそれぞれの遺伝子を、適当な確率で交換します。 ```math \begin{array}{cc} 親1 & g_1 g_2 g_3 g_4 g_5 g_6 \\ 親2 & h_1 h_2 h_3 h_4 h_5 h_6 \end{array} \rightarrow \begin{array}{cc} 子1 & g_1 h_2 g_3 h_4 h_5 g_6 \\ 子2 & h_1 g_2 h_3 g_4 g_5 h_6 \end{array} ``` ### 序数コーディングの突然変異 #### 置換 (Substitution) ランダムな位置の遺伝子を別の遺伝子に置き換えます。 ```math \begin{array}{cc} 親 & g_1 g_2 g_3 g_4 g_5 g_6 \end{array} \rightarrow \begin{array}{cc} 子 & g_1 h_2 g_3 h_4 g_5 g_6 \end{array} ``` ### 新規生成 交叉や突然変異ではなく、全く新しい個体を生成します。 # おわりに 遺伝的アルゴリズム・巡回セールスマン問題をさらっと紹介して、プログラムを掲載するつもりだったのですが、遺伝的アルゴリズムの紹介だけで長文になってしまったので、プログラムは別記事にします。