Oddwit

あらすじ：
Flashで、遺伝的アルゴリズム（GA)で巡回セールスマン問題を解くアプリを実装してみた。GAではパラメータのチューニングがかなり重要な要素だということが理解できた。

実行はこちら。ソースもあるよ

巡回セールスマン問題

今回扱ったのは、いくつかの都市を全て一回ずつ巡回するとき、最短となるルートを発見しようという、いわゆる「巡回セールスマン問題」。

ごり押しで解こうとなると、12の都市で12!（じゅうにバン！と読む）≒4億7千万通りのルートを試さなければならない。できるだけ少ない試行でそれなりに短いルートを得るために、今回は遺伝的アルゴリズム（Genetic Algorithm, GA）を使う。この実装では、12箇所の場合、調べる回数が数万回にまで減らせることが分かった。

遺伝的アルゴリズム

GAは、生物の進化にヒントを得たおもしろいアルゴリズムだ。定義や一般的なやり方についてはWikipediaあたりを見てもらうとして、ごく簡単に説明すると、生物の進化を模倣したアルゴリズムだ。問題に対するさまざまな解を生き物に見立て、解どうしで交配させて子どもを作ったり、環境に適さないものを淘汰したりすることで、確率的に最適解を見つける。

構成

主なクラスは5つ。

• Agent - 一人のセールスマンをあらわすエージェント。DNAを保持
• Population - セールスマンの集まり。世代を経るなどの動作をする
• World - 都市がばらまかれたマップ。エージェントのDNAを評価する
• Node - 都市。
• GA - アルゴリズムを実行する。

まずはPopulationオブジェクトとWorldオブジェクトを作成・初期化し、それをGAオブジェクトに渡して、myGA.run() で実行するという流れだ。