Oddwit

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のうち二つの値を選んでそれを入れ替えるという作業を何回か、一定の確率で行う。

ただし、一番成績の良かったエージェントは変異しないように守ることにした。これは変異による状況の悪化を防ぐという意味で、エリート選択と少し似ている。