今回は膜アルゴリズムを使い巡回セールスマン問題を解きます。
巡回セールスマン問題は、都市がいくつか(nとします)あり、それらを全てちょうど一回ずつ訪れて出発都市に戻る、距離が最短の経路を見つける問題です。詳しいことは例によってWikipediaにお任せしましょう。巡回セールスマン問題の解はn都市からなる系列です。出発都市は固定してよく、距離は幾何学的距離とすれば逆に回っても距離は同じなので、可能な解の候補は(n-1)!/2となります。!は階乗で、3!=6, 4!=24, 5!=120, 6!=720, とnが大きくなるとすごい勢いで大きくなります。だから可能な解を全部調べて・・・というやり方は論外です。今のところ他にいい工夫も見つかっていないので、最短でなくてもなるべく短い順回路を見つける近似解法が研究されています。
さて、近似解法でよく用いられるのが局所探索です。これは今の解をチョコと変化させてよくなれば次の解として採用するものです。対称型巡回セールスマン問題では2opt法が優れた局所探索法として知られています。
このように交差している2辺を交換してその間の経路を逆向きにし*1交差を解消すると距離の和は小さくなります。アルゴリズムでは交差を探したりせず、とにかく2辺を入れ替えて距離が短くなればよし、入れ替える2辺は確率的に選びます。この2opt近似だけに特化すると次のような変化が見られます。
これは巡回セールスマン問題の難しい例を集めたサイトにあるeil51という問題を解いた結果です。最終的に交差が全て解消され、距離の和が429になりました。ちなみにこのGIFアニメはコンピュータが計算するリアルタイムではなく*2、一度保存したデータをアニメ表示ソフトで表示しそれからGIFアニメツールで作りました。この問題の最短距離は426です。しかし、局所探索を用いる限りこれ以上の改善はありません。このように局所探索では改善できない解のことを局所解と言います。普通、巡回セールスマン問題には局所解が地雷のように埋まっていて、eil51では427, 428の局所解もあります。
局所解から抜け出すには解を大きく変化させる必要があります。遺伝的アルゴリズムはふたつの解のいいところを組み合わせて全く新しい解を作ることができる*3近似解法です。膜アルゴリズムの枠組みで2optと遺伝的アルゴリズムを組み合わせます。
このように2optをやる領域で遺伝的アルゴリズムの領域を挟んでやります。両側の2optから来た解ふたつに遺伝的アルゴリズムの交差をやると、ふたつの解が混ざって画期的に新しい解になることもある、という寸法です。その変化の様子を次に示します。
巡回路が大幅に変化するのが見て取れます。遺伝的アルゴリズムはこういった大変化は得意ですが、細かく探すのが不得手で、そのため局所探索とほぼ同義の「突然変異」を入れたりします。それに対し、膜アルゴリズムの考え方で異なる動作原理の近似アルゴリズムを組み合わせるとスッキリするではありませんか。アニメでは表示されていませんが、遺伝的アルゴリズムで作った解を一番内側の2opt局所探索が改良して、辺の交差などをとっているのです。10年以上前の研究ですが、もう少し工夫を凝らした膜アルゴリズムで、この問題を含め100都市程度までならほぼ毎回最適解を得る結果が出ています。
