遺伝的アルゴリズムが面白かったので、簡単に紹介したいと思います。
現在参加しているプロジェクトで経路探索を行わなくてはならない場面に出くわしました。
仕様としては、
・訪問先は複数ある
・訪問先は時間指定されている
・複数人で、訪問先を回る
最初に取り掛かったのが、全経路の探索でした。
訪問先には多数の条件（制限）と、移動距離も計算するために、全経路を探索したとしても枝葉が落ちるだろう
と勝手な予測をし、再帰呼び出しで全経路を探索するプログラムを書いてみました。
i7のCPUを使って、バリバリ回したのに、１時間たっても結果がでませんでした。。。 がーーん。
もう少し枝を落とす事もできたのですが、さすがに１時間たっても結果が出ないアルゴリズムでは、
これ以上手を入れることは無理と判断しました。
ほんと、一瞬青くなりました。 やばい・・・って
と言う事で急遽、新しいアルゴリズムを考えなくてはならなくなりました。
うむ。。。
そこで思い出したのが、巡回セールス問題
詳しくは、ウィキペディアをどうぞ
http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E3%82%BB%E3%83%BC%E3%83%AB%E3%82%B9%E3%83%9E%E3%83%B3%E5%95%8F%E9%A1%8C
最短経路を求めるにはどうしたらいいの？ という事を色々と考えてくれる人がいまして、
そのなかから自分の好みにあいつつ、簡単に実装できそうなアルゴリズムを探してみました。
そこで見つけたのが、遺伝的アルゴリズム
以前にも、これに似た方法で解を求めた事があったので、先人の知恵にあやかりながら、
実装してみたいと思います。
詳細は、ウィキペディアを見てもらうとして、、、
http://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
アルゴリズムの流れは、以下のようになっています。（ウィキペディアより引用）
1.あらかじめ N 個の個体が入る集合を二つ用意する。以下、この二つの集合を「現世代」、「次世代」と呼ぶことにする。
2.現世代に N 個の個体をランダムに生成する。
3.評価関数により、現世代の各個体の適応度をそれぞれ計算する。
4.ある確率で次の3つの動作のどれかを行い、その結果を次世代に保存する。
1.個体を二つ選択（選択方法は後述）して交叉（後述）を行う。
2.個体を一つ選択して突然変異（後述）を行う。
3.個体を一つ選択してそのままコピーする。
5.次世代の個体数が N 個になるまで上記の動作を繰り返す。
6.次世代の個体数が N 個になったら次世代の内容を全て現世代に移す。
7.3. 以降の動作を最大世代数 G 回まで繰り返し、最終的に「現世代」の中で最も適応度の高い個体を「解」として出力する。
うむ。なんとも生物的。
淘汰や、閾値的なんかで動くプログラムは大好きなので、飛びついてみました。
ただ、時間的にここまで真面目に実装するのが面倒でしたので、今回のものは世代管理と突然変異を実装しませんでした。
1.種の作成（沢山作る）。ランダムに、ルートを作成する。ただし、移動時間に不整合がない形の物
2.種の中から２つ取り出して、交配させる。交配方法は、１点交叉
交配から、３種を生成し、子３種から評価値の高い種を１つ取り出す。
両親と子の比較、子が優秀な場合は、子を残し親を削除、それ以外は、親のみをそのまま残す
3.種の数が、ある一定数を下回るまで、交配を続ける
4.残った種の中から、一番評価値の良いものを、結果とする
世代管理と、突然変異を入れない事により、この遺伝的アルゴリズムがどこで破たんするかはわかりませんが、
とりあず、１日での実装でしたのでこのぐらいがちょうどいいかなぁ と思っています。
#うまくいかなければ、突然変異を実装して、その後に世代管理を行います。
ちなみに、評価値の基準は、ルートに割り当てられた人の拘束時間が最小のものとし、
移動距離と、それぞれの担当の良しあしみたいなものを組み込みました。
実際には、もっと多くの条件があるのですが・・・
社会人になって書いたプログラムの中でも、なかなか楽しいプログラムの一つでした。
実際の結果が良いかは、リリースしてみないとわからないのですが、パラメータで何とでもなるように
なっているので、なんとかなるんじゃないのかなぁ とは思っています。
最初のランダムで作る種が命なような気もしないでもないのがね。
運が良ければお客さんに喜んでもらえると思います。
ランダム＝運 しだいなのよね。
運と意思から生成される、何かには夢がありますよね。 うまくいきますように！！