一汁一菜 TOSY

前回の記事で、沖縄のキャッシュを通る経路が、なかなか短縮できなかったので、いろいろ調べてみました。
巡回セールスマン問題は、最近は「遺伝的アルゴリズム」で解いていくのが盛んに行われていました。
「TSP」と「GA」で調べてみると、多くの文献を見ることができます。 そこで、プログラムを組んでみることに。
「遺伝的アルゴリズム (Genetic Algorithm: GA)」は、シミュレーションの計算方法の一つで、元となる要素の集合(親)から、要素を変化させながら(交叉や突然変異によって)新しい要素を作成していき(子)、より適していくものを残していく(選択)と、まるで生物が進化していくように最適化をしていくようです。  (この1週間で、だいぶ学びました)
出来上がったのはこちらでダウンロードできます。
結果はこちら、

なんだか、とても最短経路という感じではありません。経路の長さは約7000km、ランダムなときの経路が約8500km、前回の経路が1600kmであるので、全然短い経路が見つけられていません。
なぜだろう? 遺伝的アルゴリズムではパラメータの設定でだいぶ結果が変わるので、もっと良い方法を見つけないといけないようです。


そこで、もう一つの方法の「近傍探索法」を試してみました。これは、スタート地点から最も近い点を選び、その次は残った場所から最も近い点を選んでいくというもの。
これも、こちらでダウンロードできます。
結果はこちら、

こっちのほうがずっと良く、短い経路になります。経路の距離も657kmと今までの中で最短です。
プログラム自体は、遺伝的アルゴリズムよりずっと簡単なのに...
ただ、これも経路を見てみると、交差している箇所があったりと、まだまだ最適ではなさそうです。

まだ、改善の余地があります。