Some method to solve Travel Salesman Problem (TSP)

巡回セールスマン問題(TSP)をいくつかの方法で取り組んでみた。 順序は都市番号が入ったベクトルで表現し、列番号が訪れる順序に該当する。 例えば５つの都市を1->4->3->2->5という順で巡る場合、s=[ 1 4 3 2 5 ]となる。

Tabu Search

あるツアーsに近似なツアーs'の集合をS'とする。 集合S'の最良ツアーs'_bestをsに代入する。この処理を繰り返す。 ここで注意しなければならないのが、s'_bestがsよりも悪いツアーだとしても、sを更新するという点である。（このようにして局所解に陥る可能性を緩和している) この探索では近傍s'の探索に2-optと呼ばれる手法を採用している。この手法はツアーで訪れるi番目とj番目の都市の順番を入れ替える。 また過去いくつかの件数の推移を禁忌として記録して、近傍探索による後戻りを防いでいる。

Simulated Anealing

大部分はTabu Searchと同じだが、最良の近傍ツアーs'_bestがsよりも悪いツアーだとしても、sを確率pで更新するという点が異なる。 確率pはざっくり言うと温度tというパラメータに大きく依存しており、高いときほど悪い値を許容しやすい。温度tは近傍探索を繰り返す毎に冷却していく。 pの式はmathjaxはいってないと表現するの面倒なのでググって。

Iterated Local Search

局所解に陥った際(あるいは長い間解の更新が見られない時)、異なる局所解にたどり着くことを期待して新たな初期値を設定し、再度探索を行なう。 異なる局所解に辿り着こうと、全順序を完全なランダムで決めてしまうと、それはMulti-start Local Searchと呼ばれる、たんに局所探索をN回やるという手法になる。 かといって現在の局所解から近すぎる値を選ぶと、同じ局所解へと収束する可能性が高くなってしまう。 そこでILSでは初期値の選定に知恵を使う。 具体的には局所解に対し4-optか5-optぐらいの変更を施したものを初期値として再探索している。

Guided Local Search

( ఠൠఠ )

Genetic Algorithm

ツアーを遺伝子型(genotype)、適合値（今回は総距離）を表現型(phenotype)としてエージェントを定義し、 このエージェントの数が常に10となるように、進化と淘汰を繰り返しながら優れた適合値を持つ遺伝子(ツアー)を獲得する。

• 遺伝子型: 順列エンコード

• 表現型: 総距離

• 淘汰： 適合値順にソートして下からm番目迄を削除

• 親の選択： ルーレット方式。優れた個体ほど選ばれやすい。

• 交叉(交配)：1点交叉

• 突然変異: N-Opt(4or5)

なお今回実装したGAは上記の生存戦略にのとっているが、これは一例にすぎない（しかもかなり効率が悪い）。 だれか別の生存戦略実装するとかissue投げるとかして…。

Ant Colony Optimization 🐜

いわゆる群知能の一種で、餌と巣穴を結ぶ蟻の往来はやがて最短経路問題の近似解を導くという創発に注目した大局最適化。 TSPでは、都市を餌場と見立てた蟻が、全ての餌場を巡り巣穴へ帰っていくという処理を行ってもらう。 蟻酸が散らばらない初期はほとんど秩序なく彷徨う蟻達だが、往復を繰り返すにつれて、やがては優れた経路を選び出すようになる。