Oddwit

いろいろなパラメータ

実行時のパラメータがいろいろあって、いじり具合によってはすぐに良い結果が出たり一向に距離が縮まらなかったりするのが面白かった。

• 巡回先の都市数
• 人口の上限
• エージェントが変異する確率（今回は1）
• 変異したときにいくつのビットを入れ替えるか（今回は1）
• 世代ごとに淘汰される割合（今回は50%）
• 変異しないよう守られるエリートの数（今回は1）

たぶん、人口の上限はある程度大きいほうが効率が良いと思う。ただ、今回は世代カウンタがカタカタ上がっていくビジュアルが欲しかったので、一世代ごとの計算量を抑えるために人口は小さめにしてある。

変異する確率と入れ替えビット数は、大きすぎるとせっかく良い親を選んでもそれを生かせなくなるだろうから、そこそこにとどめておかなくてはいけない。でも逆に小さすぎると、最適さの極大値のようなところで動きが止まってしまう。

これら全てが動作結果を左右する。良い結果を得るためには試行錯誤で良いパラメータを選ばなくてはならない。

他に考慮すべきところ

今回は実装しなかったが他に考慮すべき点として、1つのマップで同じ設定のGAを数回から数十回走らせることなどが有効じゃないだろうかと思う。単純に人口を数倍にするのに比べて、ローカルマキシマムで踏みとどまってしまうことが少なくなるはずだ。

あと、せっかくコンピュータを使っているのだから、不器用な生物界をそのまま模倣する必要もない。何が言いたいかというと、生物の進化はランダムな変異が環境によってある方向へ絞られるだけだが、コンピュータでは何かの意図を持って変異させることができる。たとえば巡回セールスマン問題なら、線が交差したり往復したりしていると明らかに距離が長そうだ。そういうった状況を察知して避けるように作為的な変異をさせられれば、効率は大幅に上がるだろう。

もう1つは、そもそもこれをやろうと思った理由ながら実現していないのだが、有性生殖と無性生殖だ。子孫を残す際、二つのDNAを交叉させる必要はあるのだろうか？ひとつのDNAをさまざまな度合いで変異させる、つまり無性生殖では、有性生殖と比べて性能に差が出るのだろうか？友人のA木くんによると「愛があったほうがいい」とのことだが、また時間があれば試してみたいと思う。

おまけ：環境

とりあえずパッと実装したかったので比較的馴染みのあるFlash/ActionScript 2.0。以前にFlashでアプリを作ったときよりかなり勝手が分かるようになっていて自分でも驚いた。言語仕様は特殊じゃないから、他の言語での経験が生きたんだろうと思う。次はApolloかな。