巡回セールスマン問題を解く

　pgRouting の TSP がお亡くなりになるのは、多分、自明な3点の問題を解く場合に限るだろうという事で、放置する事にしました。しかしサービス・ルーチンとして利用するからには、いつ、お亡くなりにならないように修正されますか？という爆弾を抱えている状態なので、難問ながらも、自前でルーチンの作成を試みることにしました。使い物になるレベルになるか？仮に使えるようになったら公開するか？は別問題で、今は考えないことにします。
　TSPの解法として、kd-tree, TS,SA,GA等いろいろありますが、あまり深く考えないでもコーディングできそうなGAを選択する事にしました。参考にした本は「組合せ最適化アルゴリズムの最新手法―基礎から工学応用まで」です。最初はSimEを実装しようと読んでいたのですが、これは、どうも 2-opt, or-opt の事を書いてあるような気がするし、わからないので、やめました。
　GAでTSPを実装する上での問題は、

• どのようなアルゴリズムで子供を作成するか？
• 集団サイズは、どのぐらいにするか？
• 突然変異をどのように扱うか？

です。
　子供を作成するアルゴリズムは、辺組み換えオペレータ[WSF89]にしました。本を参考に実装してみたけれど、実際には孤立する辺や点が出現し、これらを考慮しなければなりませんでした。しかし、解説にあるように両親の良さをうまく受け継いでくれるようで、いい感じです。
　集団サイズは、とりあえず４０としました。
　突然変異も試行錯誤しました。2-opt や or-opt を使わないと GA だけでは、なかなか良い結果が得られないという解説が多いですが、結構いい線いくようになりました。下手な鉄砲も数撃ちゃ当たるでしょうか？
　はまったのは、辺組み換えオペレータでは同一の親が発生しやすく、同じ親を除去する部分でした。

1. 経路長でソートして配列を比較してましたが、状況が改善されません
2. 0番目に特定の点が来るようにローテーションをかけてから比較するようにしましたが、だめ
3. 1番目の点と最後の点を比較して、必ず若い番号が1番目に来るように順序を反転

以上の操作で、やっと重複を取り除く事ができました。
　しかし、現在40点でテストを試みてますが、安定するまでに600世代から2400世代繰り返しが必要です。まだまだ工夫の余地があり、結構、奥が深いのねん…。