あらすじ：
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() で実行するという流れだ。
DNAの表現
エージェントのDNAは、単純に都市を廻る順番を配列にしたもので表した。たとえば
[0, 2, 9, 12, 10, 4, 11, 6, 8, 1, 3, 7]
のような感じだ。
自然選択の方法
最適解に近づくため、各世代で一部のエージェントたちが死ぬ必要がある。今回は移動距離の長さでセールスマンを1～nまでランク付けし、そのうちの半分が淘汰され、半分が残る仕組みにした。
他にも選択の手法がいくつかある事をさっきWikipediaで調べて知ったのだが、この方法はどうも「エリート選択」にあたるらしい。名前は知らなかったが「ルーレット選択」というのもあり、これに似たことをしようかなとも思ったが、あまり結果に影響しなさそうだったので手を抜いた。実際、恐らく他のパラメータと比べると影響力は弱いと思う。
交配の方法
上の自然選択で死んだ分を、新しい子供で埋める。ここで親の選び方は、まさしくルーレット選択によるものだった。全てのセールスマンの成績を合計し、そのうち自分の成績が占める割合が、get laidできる確率となる。つまりできる男ほどモテるということだ。ただし問題は、男にモテるということだ。アッー！まぁ話がややこしくなるので父親･母親と呼ぶことにする。
さてどのように子供を生むかというのが考えどころだが、結局次のようにした。DNAの長さを12だとすると、そこから2つの連続した値を3つ取り出し、空の子供DNAに同じ位置で引き継がせる。たとえば
父：[0, 2, 9, 5, 10, 4, 11, 6, 8, 1, 3, 7]
↓
子：[0, 2, -, 5, 10, -, -, -, 8, 1, -, -]
のような具合だ。
次に、まだ埋まっていない場所へ、母親のDNAの同じ位置から値を引き継ぐ。ただし各都市を一回ずつ巡回する必要があるので、既にある値と重複してしまう場合はスキップする。
母：[1, 9, 0, 3, 2, 10, 7, 6, 3, 11, 8, 4]
↓
子：[0, 2, -, 5, 10, -, 7, 6, 8, 1, -, 4]
最後に、まだ埋まっていない場所をランダムな値で埋めれば子供のDＮＡが完成する。
子：[0, 2, 9, 5, 10, 3, 7, 6, 8, 1, 11, 4]
今回は重複してはいけないという制約があるため少し特殊だが、方法としては一様交差に似ていると思う。
最初は、父親のDNAから5つの値の連続を1つ取り出して同じ位置で子に渡していた。しかしこれだと世代間に多様性がなくなり、ほとんどを変異に頼ることになってしまう。そこで、もう少しバラエティに富んだ子が生まれることを期待しつつも、親の流れをそれなりに継いで欲しいとの願いから、2の連続x3を取る方法を選んだ。
他の可能性としては3の連続x2などもうまく行きそうな気がするし、同じ位置じゃなくずらして引き継がせるのもいいだろう。
突然変異
さて子を産んで再び人口が上限まで埋まったら、それぞれのエージェントを突然変異させる。DNAのうち二つの値を選んでそれを入れ替えるという作業を何回か、一定の確率で行う。
ただし、一番成績の良かったエージェントは変異しないように守ることにした。これは変異による状況の悪化を防ぐという意味で、エリート選択と少し似ている。
いろいろなパラメータ
実行時のパラメータがいろいろあって、いじり具合によってはすぐに良い結果が出たり一向に距離が縮まらなかったりするのが面白かった。
- 巡回先の都市数
- 人口の上限
- エージェントが変異する確率（今回は1）
- 変異したときにいくつのビットを入れ替えるか（今回は1）
- 世代ごとに淘汰される割合（今回は50%）
- 変異しないよう守られるエリートの数（今回は1）
たぶん、人口の上限はある程度大きいほうが効率が良いと思う。ただ、今回は世代カウンタがカタカタ上がっていくビジュアルが欲しかったので、一世代ごとの計算量を抑えるために人口は小さめにしてある。
変異する確率と入れ替えビット数は、大きすぎるとせっかく良い親を選んでもそれを生かせなくなるだろうから、そこそこにとどめておかなくてはいけない。でも逆に小さすぎると、最適さの極大値のようなところで動きが止まってしまう。
これら全てが動作結果を左右する。良い結果を得るためには試行錯誤で良いパラメータを選ばなくてはならない。
他に考慮すべきところ
今回は実装しなかったが他に考慮すべき点として、1つのマップで同じ設定のGAを数回から数十回走らせることなどが有効じゃないだろうかと思う。単純に人口を数倍にするのに比べて、ローカルマキシマムで踏みとどまってしまうことが少なくなるはずだ。
あと、せっかくコンピュータを使っているのだから、不器用な生物界をそのまま模倣する必要もない。何が言いたいかというと、生物の進化はランダムな変異が環境によってある方向へ絞られるだけだが、コンピュータでは何かの意図を持って変異させることができる。たとえば巡回セールスマン問題なら、線が交差したり往復したりしていると明らかに距離が長そうだ。そういうった状況を察知して避けるように作為的な変異をさせられれば、効率は大幅に上がるだろう。
もう1つは、そもそもこれをやろうと思った理由ながら実現していないのだが、有性生殖と無性生殖だ。子孫を残す際、二つのDNAを交叉させる必要はあるのだろうか？ひとつのDNAをさまざまな度合いで変異させる、つまり無性生殖では、有性生殖と比べて性能に差が出るのだろうか？友人のA木くんによると「愛があったほうがいい」とのことだが、また時間があれば試してみたいと思う。
おまけ：環境
とりあえずパッと実装したかったので比較的馴染みのあるFlash/ActionScript 2.0。以前にFlashでアプリを作ったときよりかなり勝手が分かるようになっていて自分でも驚いた。言語仕様は特殊じゃないから、他の言語での経験が生きたんだろうと思う。次はApolloかな。
Pingback: dustboxxx - 人工知能（遺伝的アルゴリズム GA）で巡回セールスマン問題を解く