巡回セールスマン問題と遺伝的アルゴリズム(GA)

巡回セールスマン問題(TSP)とは

巡回セールスマン問題 (Traveling Salesperson Problem : TSP)は、 セールスマンがN個の都市を1回ずつ通って巡回する最短の経路を見つける問題です。 TSPには多くの応用例があり、実用上でも重要な問題です。 例えば、プリント基盤に穴を空ける時の最適の順序はTSPです。

都市数をNとすると、(N-1)!/2種類の巡回経路があります。 したがって、数十都市になるとすべての巡回経路を調べることは 非常に難しく、都市の配置に法則性がなければ厳密解を求めることはできないと 言ってよいと思います。 そこで、近似解法で十分良い解を求めることになります。

近似アルゴリズム

TSPを解くための近似アルゴリズムを３つ紹介します。 これらはTSPだけでなく、多くの最適化問題に応用できます。

ランダムサーチ (Random Search)による解法

ランダムに経路を作成し、それまででもっとも良い解と比較します。
並列処理が可能です。 全体的な探索が行なえ、計算時間を無視すれば必ず最適解を求めることが出来ますが、 それまでの探索の結果が生かされず、非効率的のため、大きな問題では時間的に不向きです。

山登り法 (Hill Crimbing)による解法

ランダムに生成した解に対し、 最良解の近傍を探索し、解が改善されれば、それに置き換えていきます。 探索が局所的に良い方にしか進行しないので、局所解に陥りやすくなります。
TSPでは、訪問順に都市名を並べたリストにより、経路を表現します。 現在の最短の経路に、ある操作を加え、経路がより短くなれば 入れ換えることを繰り返すことにより、最良解を得ます。

本解説の最後につけたプログラムでは次の3種類の操作から選択することができます。

・Two Point Reverse
　　都市1と都市2の間の経路を反転するもので、2最適化と呼ばれています。 経路が交わっている時は、この交わりをとることにより、確実に 経路を短くできますが、この操作により交わった経路をとることが出来ます。

・Two Point Change
　　都市1と都市2を入れ換えます。

・One Point Jump
　　都市1を都市2の位置へ移します。

焼きなまし法 (Simulated Annealing : SA) による解法

この方法は、溶解状態にある物質を冷却して結晶状態にするプロセスから ヒントを得たアルゴリズムで、 HCに確率的な遷移を導入したものです。 解の近傍を探索し、解が改善されれば、それに置き換えますが、 解が改善されなくても、ある確率により置き換えます。 最初は、この確率を大きくしておき、少しずつ減らしていきます。 確率の減らし方をゆっくりスケジューリングすることにより良い解を 得ることが出来ます。 逆に、急なスケジューリングをすれば速く収束しますが、 あまり急なスケジューリングをすると、解はHCと同程度になってしまいます。
SAの長所は、局所解に陥りにくく大域的探索が可能であることと、 汎用性が高いことです。 短所は、スケジューリングが経験的で調整が必要なことです。
温度Tの減らし方(スケジューリング)は、いくつか提案されています。 S.Geman, D.Gemanの方法 (Boltzman分布) や、H.Szu, R.Hartleyの方法 (Cauchy分布) が あり、どちらの方法も、最適解に収束できることが証明されています。 ただし、これらのスケジューリングにしたがって温度を下げることは、 膨大な計算時間を要し、非現実的です。
プログラムでは、次のスケジューリングを用いています。
　　　T(n+1) = α・T(n)　　　ただし、0 < α < 1
αが1に近いほど緩やかなスケジューリングとなります。
また、操作にはHCのところで述べた Two Point Reverse (2最適化) を用いています。

遺伝的アルゴリズムの基本概念

遺伝的アルゴリズム(Genetic Algorithm : GA)は 生物の進化をモデルとした手法で、 選択(淘汰)、交叉、突然変異、という遺伝的操作を用いて 問題を解こうというものです。 探索問題や規則学習など最適化問題や現実の問題に有効な手法であることが 確認されています。
GAの操作で、選択(淘汰)や突然変異は、他の探索手法にもそれに相当する 操作があるが、交叉はGAだけが持つ操作で、 この交叉こそGAを特徴づけるものだといえます。 GAは、基本的に解(コード)の評価が出来れば良く、 最適化問題の解法としては応用性が高いと言えます。 多点探索なので、一般的に局所解に陥りにくく、 大域的な探索ができる。つまり、多峰性の問題にも強という特徴があります。 また、並列化にも向いており、並列コンピューター上に 実装することにより、計算時間の短縮が期待できます。 定型の最適化問題に定式化しにくい問題や、問題自体の性能が完全には明確に なっていない場合に、GAを使うと良いでしょう。

遺伝的アルゴリズムによる巡回セールスマン問題の解法

GAのTSPのコーディングは、パス表現と順序表現が提案され、用いられています。 パス表現と呼ばれるコーディング方法は、 GAだけでなく他手法でも用いられるTSPの一般的な表現方法です。 都市名を遺伝子とし、訪れる順に都市名を列挙した文字列を染色体とします。 TSPをGAで解くためにさまざまな工夫が考えられています。 ここでは、それらについて簡単に解説します。

選択・淘汰

選択・淘汰には、次のものが多いようです。
・ 巡回経路の短いものをから順に選択するもの。
・ 巡回経路の短いものをスケーリングして、確率的に選択するもの。

突然変異

HCのところで述べた操作をそのまま利用できます。 ただし、2最適化は単独でも強力な操作であり、 GAとしての特色を出すには慎重に用いなければならないでしょう。

交叉

TSPに対するGAの工夫は、ほとんど交叉になされているといってよいでしょう。 本プログラムでは以下の方法で計算ができます。 1世代の計算量は、PMXはO(n)で、サブツアー交換交叉がO(n^3)となります。

・Partially Matched Crossover (PMX) [goldberg:1989による]
交叉しても同じ経路が現れないようにうまく都市を入れ換えます。
この交叉では、交叉範囲の経路は完全に保存されます。（交叉範囲以外では経路が崩れます）

・サブツアー交換交叉
交換されるサブツアーに含まれる都市集合が一致する時に限って交叉します、 これにより、交叉時に経路が壊れることを防ぐことができます。 ただし、交叉点があまり変動しなくなる可能性があり、 初期収束(探索があまり進行しないうちに収束してしまう)の可能性があります。

実行例

ランダムに配置した500都市のTSPをPMXGAで計算した例を図に示します。 交わった経路がなくなるまで計算しました。 計算時間はPentiumPro200で15分かかりました。 (UNIX WSのSUN SparcStation2では100分ほどかかったものですが....)。

初期状態	計算結果

48都市の同心円状の都市配置でのTSP

ランダムな都市配置では最適解を計算するのは困難で、 どの程度良い解なのかわかりません。 そこで、最適解がわかるような都市配置を用いることが考えられます。 最適解が明らかな都市配置は、都市を格子状に配置したものや、 ある閉曲線上に狭い間隔で、都市を配置したものなど考えられますが、 次のような面白い問題が提案されています [yamamura:1992]。

図のように、内円と外円に24都市づつ配置したものを考えます。 内外円の半径比により、図のようなC型、歯車型の最適解を持ちます。 外円の直径を固定して、内円半径を変化させると、 内外円の半径比0.76908を境に局所解と最適解が入れ替わります。

C型	歯車型
半径比 < 0.76908	0.76908 <= 半径比

ソフトウェアダウンロード

以上、計算方法や都市の配置について簡単に説明しました。 あとは実際にプログラムを動かしてみて最良解に近づいて行く過程をご覧下さい。

★ 巡回セールスマン問題を遺伝的アルゴリズムで解く 　　　　　◇◆◇◆ダウンロード◇◆◇◆　Ver2.1 (1999/10/20)　フリーウェア

☆ 概要 TSP(Traveling Salesperson Problem)を解きます。 遺伝的アルゴリズムおよびその他にもいくつかの近似アルゴリズムで計算ができます。 役に立つたぐいのプログラムではありませんが、"TSPとはなにか？"、 "近似アルゴリズムとはどんなアルゴリズムか？"といったことが 直感的に理解できると思います。 ☆ 特徴 上記で解説した探索手法を実際に試すことができます。

以下はランダムに配置した500都市のTSPをPMXGAで計算した例です。 交わった経路がなくなるまで計算しました。計算時間はPentium!!!750MHzで170秒かかりました。

初期状態	計算結果

STUDIO-Kについて

STUDIO-Kでは対局将棋ソフトK-Shogi・ぴよ将棋、スマホアプリ等を製作しています。 また、プログラミングや電子工作、マイコン、その他最新情報についてブログで情報発信をしています。 ぜひ、他のページにもお立ち寄りください。