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

　40点ぐらいなら良いけど、80点以上になってくると、かなり難しくなります。200点なんて、絶望的に難しいです（冷静に考えれば (n-1) !　から抽出するのだからしょうがない事なのかもしれない）。集団サイズは1世代あたり点数の2倍として試行錯誤し、そこそこ性能も良くなりました。40点に対して 160世代目ぐらいで安定するけど、1700世代ぐらいに忽然と世代交代する場合もあって難しいです。
　突然変異には、今のところ乱数で min( N / 2 + 1, 20 ) を最大として任意の位置を錯乱させるものと、任意の2点を交換するものをミックスしています。これらが辺組み換えオペレータと相性が良いような気がしてます。前者は局所的な改善に、後者は大局的な改善を促します。
　ＧＡは、一度にたくさんの改善をしようと思って、欲張りすぎると淘汰されてしまいます。なので、ちょっとづつ改善するしかないのですが、80点以上になると改善して欲しい場所に突然変異が適用される確率が低くなるので集団サイズを増やすか世代数を増やすしかなくなります。こういう理由から、2-opt や or-opt を組み合わせるという発想になるのだと思います。
　既に 40 点ぐらいの問題ならば、2-opt や or-opt を併用しなくても良い経路に収束するレベルにあるので、plpgsql 化しても良さそうです。
　今後の課題は、世代交代の収束回数に応じて 2-opt や or-opt を併用して 局所解への収束ステージを設けて、スイッチするなどの工夫を取り入れることです。正直 2-opt や or-opt のコーディングは面倒くさそうなので、このままお茶お濁すかも…(^^;