FIT2017（第 16 回情報科学技術フォーラム）A-010
他個体を参照した進化的アルゴリズムによる巡回セールスマン問題の解法
Evolutionary Algorithm Referring Other Individuals for Traveling Salesman Problem
佐藤 豊浩†
Toyohiro Sato
1. はじめに
巡回セールスマン問題 (Traveling Salesman Problem, TSP)
は，配送計画やスケジューリングなどの現実問題に直結しているため，重要性の高い問題とされている．しかし，問題規模の増加に伴う解候補数の増加が指数的であるため，最適解を現実的な時間内で総当たりにより求めることは困難である．そのため，近似解を高精度かつ高速に求める研究が盛んに行われている．
既存研究には，自然界に存在する生物の習性や進化をモデル化することで，問題の近似解を求める方法が数多く存在する．それらの方法は進化的計算や進化的アルゴリズムなどと呼ばれ，その中でも遺伝的アルゴリズム (GeneticAlgorithm, GA) [1] と差分進化 (Differential Evolution, DE) [2]は様々な最適化問題に対して優れた性能を持つ進化的アルゴリズムである．しかし，これらのアルゴリズムを TSP に対して適切に機能させるためには，それぞれの解探索過程に様々な工夫を必要とする [3] ．
本研究では，GA と DE が有する解探索過程を収束性や多様性の観点から取り入れた，TSP の近似解を高精度かつ高速に求める新たな進化的アルゴリズム参照進化 (ReferentialEvolution, RE) を構築した．そして，TSPLIB [4] に掲載されているベンチマーク問題を使用して提案手法の有効性を確認した．

2. 提案手法
本研究では，GA と DE が有する解探索過程を収束性や多様性の観点から取り入れた，TSP の近似解を高精度かつ高速に求める新たな進化的アルゴリズム参照進化 (ReferentialEvolution, RE) を構築した．

2.1 RE の解探索過程
1975 年に提案された GA は，生物の進化や遺伝をモデル化したアルゴリズムである [1] ．GA が有する解探索過程の優れた点として，選択と交叉による遺伝子の収束が挙げられる．これにより，問題の解候補である個体群の中から評価の高い個体の遺伝子が優先して受け継がれる．したがって，個体群内に優秀な遺伝子が積み重なり，良い解の近傍を集中的に探索することが出来る．また 1997 年に提案された DE は，解空間上に存在する様々な個体の位置関係を利用したベクトルの差分により解空間を探索するアルゴリズ
ムである [2] ．DE が有する解探索過程の優れた点として，突然変異個体による解探索方向の多様化が挙げられる．これは，個体群の位置関係を利用したベクトルの差分により，新たな個体を生成することで，個体群のバラつきや収束に†東京都市大学大学院 工学科‡東京都市大学 知識工学部

穴田 一‡
Hajime Anada
合わせて解探索方向を多様化させることが出来る．加えて，
GA と DE のアルゴリズムは，最適化の対象となる問題の解空間の構造に依存しないため様々な最適化問題に利用可能である．しかし，これらのアルゴリズムを TSP に対して適切に機能させるためには，それぞれの解探索過程に様々な工夫を必要とする [3] ．
最適化問題の近似解を高精度かつ高速に求めるためには，解探索過程に個体群の収束性と解探索方向の多様性をバランス良く取り入れる必要がある．そこで本研究では，TSPの近似解を高精度かつ高速に求めることを目的として，他個体を参照することで個体群の収束性と解探索方向の多様性を取り入れた新たな進化的アルゴリズム RE を構築した．
提案手法では，各個体の近傍を多様な方向に探索する．そのために，進化する個体が他個体を参照することで，新たな経路を候補として加えて，それらの経路を重ね合わせる．
そして，それぞれの個体の優先度合いに従い経路の集合から新たに巡回経路を構築する．このとき，参照する他個体やその優先度合いを調整することで，解探索方向の多様性と個体群の収束性をバランス良く取り入れることが出来る．

2.2 RE のアルゴリズム
以下に RE のアルゴリズムを示す．
初期個体群の生成
初期個体群として，𝑚個の個体𝑋 𝑘 を生成する．𝑋 𝑘 はランダムに構築した巡回経路であり，𝑋𝑖𝑗𝑘 は都市𝑖から都市𝑗を訪問するとき 1 の値を取り，訪問しないとき 0の値を取る．ここで，𝑘 は個体番号 (𝑘 = 1, … , 𝑚)，𝑚は個体数，𝑖と𝑗は都市番号 (𝑖, 𝑗 = 1, … , 𝑛)，𝑛は問題の都市数である．
ii.
評価
各個体の巡回経路を経路長により評価する．
iii. 終了判定
ステップ𝑡が予め設定した反復上限𝑡𝑚𝑎𝑥 に達したとき，個体群から評価が最も良い個体を選び，解として出力してアルゴリズムを終了する．
iv. 選択個体𝑿𝒔 の選択
個体群から無作為に選択個体𝑋 𝑠 を選ぶ．
v.
報酬𝑽の付与選択個体と無作為に選ばれた個体の巡回経路を利用して，互いの経路と経路の間の経路に報酬𝑉を付与する．そのために，各経路を方向ベクトルとして扱い，互いの個体の経路から合成ベクトルの計算を行う．
そして，合成ベクトルにより経路間の経路に報酬付与を行う．報酬𝑉を参照することで個体群以外の要素を解探索に取り入れることが可能となる．以下に報酬𝑉の付与の手順を示す．
1.
ランダム個体𝑿𝒓 の選択
個体群から無作為にランダム個体𝑋 𝑟 を選ぶ．
i.

111
第 1 分冊Copyright © 2017 by Information Processing Society of Japan andThe Institute of Electronics, Information and Communication Engineers
All rights reserved.

FIT2017（第 16 回情報科学技術フォーラム）2.

合成ベクトルの計算
𝑋 𝑠 と𝑋 𝑟 の巡回経路のうち，ある都市𝑙を訪問する
𝑠𝑠𝑟𝑟
経路𝑋𝑎𝑙, 𝑋𝑙𝑏と𝑋𝑐𝑙, 𝑋𝑙𝑑を利用して合成ベクトルを計算する．ここで，𝑎, 𝑏は𝑋 𝑠 が都市𝑙の前後に訪問する都市，𝑐, 𝑑は𝑋 𝑟 が都市𝑙の前後に訪問する都市である．そして，各経路を都市𝑙が始点，もう一方の都市を終点とする方向ベクトルとして扱い，次式により合成ベクトル𝑣⃗⃗⃗𝑙 を 4 パターン生成する．
𝑠𝑟𝑣𝑙1 = 𝐹 ∗ ⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗
𝑋𝑙𝑎+ (1 − 𝐹) ∗ ⃗⃗⃗⃗⃗𝑋𝑙𝑐(1)𝑠𝑟⃗⃗⃗⃗⃗⃗ + (1 − 𝐹) ∗ 𝑋⃗⃗⃗⃗⃗⃗𝑣𝑙2 = 𝐹 ∗ 𝑋⃗⃗⃗⃗⃗𝑙𝑎𝑙𝑑𝑠𝑟
𝑣𝑙3 = 𝐹 ∗ ⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗
𝑋𝑙𝑏+ (1 − 𝐹) ∗ ⃗⃗⃗⃗⃗𝑋𝑙𝑐⃗⃗⃗⃗⃗⃗𝑟𝑣𝑙4 = 𝐹 ∗ ⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗
𝑋 𝑠 + (1 − 𝐹) ∗ 𝑋𝑙𝑏vi.

vii.

𝑙𝑑

ここで，𝐹は𝑋 𝑠 の比率を示すパラメータである．
𝑠𝑟
このとき，𝑣⃗⃗⃗⃗⃗𝑙1 は𝑋𝑙𝑎と𝑋𝑙𝑐
を(1 − 𝐹): 𝐹で内分する方向ベクトルとなり，互いの経路と経路の間の方向を表す．
3.
経路間の経路に報酬付与
𝑣𝑙1 の終点に最も近い都市𝑢と都市𝑙の経路の報酬⃗⃗⃗⃗⃗
量𝑉𝑙𝑢 ,𝑉𝑢𝑙 の値を1増加させる．同様に𝑣⃗⃗⃗⃗⃗𝑙2 , ⃗⃗⃗⃗⃗
𝑣𝑙3 , ⃗⃗⃗⃗⃗𝑣𝑙4
から報酬付与を行う．都市𝑙を他の都市に変更して，全ての都市についても同様に合成ベクトルの計算を行い，経路間の経路に報酬付与を行う．
相違個体𝑿𝒅 の選択
個体群から𝑋 𝑠 と経路の重複が最も少ない相違個体𝑋 𝑑を選ぶ．𝑋 𝑑 は𝑋 𝑠 と解空間上で距離が最も離れた個体であり，参照することで効率良く個体群内の要素を解探索に取り入れる．
進化個体𝑬の構築
𝑋 𝑠 と𝑉と𝑋 𝑑 の経路を重ね合わせ，次式により経路集合𝐺を生成する．
𝐺𝑖𝑗 = 𝑋𝑖𝑗𝑠 + 𝛼𝑉𝑖𝑗 + 𝛽𝑋𝑖𝑗𝑑(2)
ここで，𝛼, 𝛽は𝑋 𝑑 , 𝑉の経路の優先度合いを示すパラメータである．このとき，𝛼, 𝛽を 1 未満の値で設定する
ことで𝐺は𝑋 𝑠 の近傍を表す．そして，𝐺に含まれる経路から進化個体𝐸を構築する．初めに無作為に都市𝑖を選び，次に𝐺に含まれる経路𝑖𝑗を選択する．経路𝑖𝑗の選択確率𝑝𝑖𝑗 は次式により定義される．
𝑤𝑖𝑗
𝑝𝑖𝑗 = 𝑛(3)∑ℎ=1 𝑤𝑖ℎ𝐺𝑖𝑗
𝑤𝑖𝑗 =𝑑𝑖𝑗 𝛾
ここで，𝑑𝑖𝑗 は経路𝑖𝑗の経路長，γは経路長の影響度合いを示すパラメータであり，選択された経路は𝐸の経路となる．そして，再び無作為に都市𝑖を選び直し，経路の選択を繰り返すことで𝐸の巡回経路を構築する．
このとき，個体群以外の要素を持つ可能性がある報酬𝑉と個体群内で𝑋 𝑠 と最も異なる要素を持つ𝑋 𝑑 が解探索方向を多様化させる．また，選択可能な経路が存在しない場合は，例外処理として一時的に TSP の制
約条件を満たす全ての経路の重み𝑤𝑖𝑗 を次式により定義して，𝐺に含まれない経路も選択可能とする．
1
𝑤𝑖𝑗 =(4)𝑑𝑖𝑗 𝛾viii. 更新
𝑋 𝑠 より𝐸の評価が良い場合𝑋 𝑠 を𝐸で更新する．そして，𝑡 ← 𝑡 + 1として ii へ戻る．

3. 評価実験TSPLIB [4] に掲載されているベンチマーク問題を使用して，求めた解の精度より提案手法の有効性を確認した．問
題は att48，eil51，st70，eil76，kroA100，ch130 ，kroA150，rat195，tsp225，a280，rat575 を使用した．提案手法のパラメータは，予備実験より様々な問題に対して解を高精度に求められた値で，𝑚 = 100，𝐹 = 0.3，𝛼 = 0.005，𝛽 = 0.1，
γ = 2，𝑡𝑚𝑎𝑥 は各問題で個体群が十分に収束可能なステップ数に決定した．各問題を 50 試行した結果を次の表 1 に示す．但し，rat575 は 1 試行した結果である．
表 1 の平均値より，提案手法は殆どの問題において最適解を求めることが確認された．しかし，問題規模の増加に対して解探索に掛かる平均ステップの増加が大きくなることが確認されたため，解を高速に求める工夫が必要であると考えられる．

表 1 : ベンチマーク問題の結果
問題
att48
eil51
st70
eil76
kroA100
ch130
kroA150
rat195tsp225a280
rat575

opt
33522
426675
538
21282
6110
26524
2323
3916
2580
6773

平均値
33522.0
426.0
675.0538.0
21282.06110.026524.02323.23916.02580.06774.0

平均ステップ7034.95354.112242.2
10647.4
9985.360817.832039.1
51202.7
115630.8
42666.03686240.0

4. おわりに本研究では他個体を参照した新たな進化的アルゴリズム
RE を構築した．そして，評価実験によりベンチマーク問題の解が高精度に求まることが確認された．しかし、爆発的に解空間が複雑になる大規模な問題を解くためには，解探索に掛かる平均ステップを抑える必要がある．解決案として，個体数や他個体の経路の優先度合いなどのパラメー
タの調整，報酬付与方法の検討，相違個体以外の参照個体の検討が挙げられる．
今後の課題として，さらに大規模な問題（具体的には1000 都市以上の問題）に対する精度の確認，アルゴリズムのオーダーや計算時間についての検証などが挙げられる．
参考文献[1] J. H. Holland：“Adaptation in Natural and Artificial Systems”，TheMIT Press (1975)[2] R. Storn，K. Price：“Differential Evolution - A Simple and Efficient
Heuristic for Global Optimization over Continuous Spaces”，Journalof Global Optimization，vol.11，pp.341-359 (1997)[3] 山村雅幸，小野貴久，小林重信：“形質遺伝を重視した遺伝的アルゴリズムに基づく巡回セールスマン問題の解法”，人工知能学会誌，Vol.7，No.6，pp.1049-1059 (1992)[4] TSPLIB，http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

112
第 1 分冊Copyright © 2017 by Information Processing Society of Japan andThe Institute of Electronics, Information and Communication Engineers
All rights reserved.