TIM Labs

2013年6月アーカイブ

前回は、遺伝的アルゴリズムで交叉をどう実装すれば良いかを検討するための問題を出したところまでだった。

今回は、非数値遺伝子からなる染色体の交叉の実装例を示そう。
もちろん、実装方法は多々考えられるが、目的、実行時間、プログラミング作業量、効果など色々考慮することがあり、どの方法が良いかは一概には決められないことを先に言っておこう。

実装方法を、下図に示す。

NA-cross.png

(1)、(2)が、親となる2つの染色体である。
(3)が、(1)、(2)の完全一致部分だけをコピーしたものである。

ここまでを前回示した。

ここでは、交叉を次のように考えた。
2つの親(1)(2)を重ねて、同じ箇所で切断し、できた断片を、異なる親通しを結合してみた。
切断方向、切断位置は、乱数で適当に決めている。

例では、(1)の左側と、(2)の右側が子染色体にそのまま引き継がれるとした。
切断線で切られる長方形は無視し、(1)の左側に完全に含まれている全長方形と、(2)の右側に完全に含まれている長方形を、子にコピーすることで、(3)から(4)が得られた。

未決定部分は、空白のままになっている。空白部分は、切断線付近にだけできるはずである。

さて、この空白部分を適当に切り分け直して、盤面全体が長方形で分割されるようにすると、新たな長方形分割が完成する。これに関しては、核を含む長方形を適当に上下左右に拡大していくとことで、盤面全体を覆い尽くすことができる。
もしうまくいかなければ、(4)から再度繰り返すことで、たぶんそのうちできるようであった。

これが、長方形分割に対する、遺伝的アルゴリズムの交叉処理の1つの実装である。

遺伝的アルゴリズムを用いる場合、問題を解決するためのアルゴリズム自体を考える必要はほとんどなくなる。しかし、交叉や突然変異をどう実装するかという新たな問題が発生し、この実装方法次第で、速度、品質などに大差ができてしまう。

遺伝的アルゴリズムは、通常の方法では手に負えないような、非数値的な問題にこそ真価を発揮する。しかし、このあたりが書籍等にはほとんど書かれていないのが残念である。

プルリクエスト(Pull Request)、とても便利な仕組みですよね。 マージがボタン一つでできますし、ソースコードレビューも格段にやりやすくなったと感じています。

私の所属しているプロジェクトでは、Bitbucketのプルリクエストを使ってソースコードレビューを行っています。

プルリクエストは、全体テストを一回手元で通してから送るのがマナー です。 そうでないと、レビューアーが問題なしと判断してマージボタンを押した後に、

  • デグレが発生しており、テストが一部通らなくなっている
  • typoがあって、そもそもコンパイルが通らない状態になっている

といった問題が発覚することがあります。結構よく起こります。

もちろん、Jenkins等のCIツールを使っているので、問題はすぐに発覚します。 しかし、問題を修正するまではソースをpullできない状態になるわけで、他の開発者に迷惑をかけてしまいます。

「テスト通してからプルリクエスト出すとか、あたりまえじゃん」と思われるかもしれません。 しかし、毎日スケジュールに追われながら開発をしていると、そんな当たり前のこともしなくなってしまうものです。どうしたものか。何か解決策は無いものでしょうか。

遺伝的アルゴリズムの説明で出てくる染色体は、int型の配列で表現されることが多い。
その代表例が、『ナップサック問題』である。

遺伝的アルゴリズムでは、2つの個体の染色体から、次の世代の個体の染色体を生成しなければいけない。
もとの2つの配列を、A、B、新しい配列をCとしたとき、C[i] = A[i] or B[i] とでもやっておけば済む。
実際の染色体のときのように、Aから適当な個数連続で取り、次にまたBから適当な個数連続で取るという風に工夫してもよい。

ナップサック問題は、ナップサックに詰め込む物をナップサックに入れるか入れないかなので、boolean配列で済ますことができる特別に簡単な場合である。通常は、各物について、重さと価値があり、ナップサックが耐えられる重さ以内で、最大価値の組み合わせを求めるものだ。

しかし、実際のナップサックに物を詰めるのは、そんなに簡単ではない。物には、サイズがあり、物をナップサックに詰めるというのは3次元空間に物を詰めるとても難しいパズルになってしまう。重いものは下に入れないと、物が潰れることもある。物によっては、配置方向が決まっていているものもあろう。現実は非常に複雑な制約があり、本物のナップサック問題を解くのは至難の技になる。

ということで、3次元パズルになってしまう現実的ナップサック問題を諦め、2次元パズルについて考えてみよう。

10x10のマス目を長方形に分割する問題を考えよう。分割するとき、各長方形には丸で示されている「核」が1つ入っていなければいけない。複数個入っていてはいけない。核の配置はあらかじめ決まっていて、勝手に動かしてはいけない。

次図の2つが、分割例である。

na-ga1.png na-ga2.png

正しい分割が与えられると、環境順応性判定を行えるのだが、まだどちらも不十分と出た。

この2つの分割を両親とし、あたらしい分割を考えてみよう。

よく見ると、まったく同じ長方形がいくつか存在する。
どちらの親も同じになっている部分は、そのまま子にコピーすれば良いだろう。
ということで、次の図が得られる。

na-ga3.PNG

しかし、これでは未確定の部分がいっぱいで、子供ができない。
空白になっている部分をできるだけ両親の分割を反映させながら分割するにはどうすればよいだろうか?


このアーカイブについて

このページには、2013年6月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2013年5月です。

次のアーカイブは2013年7月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。