TIM Labs

数値配列で表現できない染色体の交叉

| コメント(0) | トラックバック(0)
遺伝的アルゴリズムで説明に使われている「ナップサック問題」はBool型の配列で染色体をモデル化できるのだが、こんな単純な例はほとんどない。

最近よくやっているのが、2次元上の指示された数百、数千箇所もある制御点の値を適当に調整する問題だ。環境適合度関数、要するに評価関数が、制御点の値すべて引数とする多変数関数なのだが、この関数値が目標値(通常は0)になる場合の制御点の値の適当な組み合わせを求めよ、というものだ。

だが、制御点の値は、独立に何でも良いわけではなく、互いに複雑に影響し合っていて、こっちを変えればあっちが変わり、それに対応しているとさらに別のところが影響を受け、収拾がつかないような問題が多い。この互いの影響の調整が済まないと、評価関数での評価の意味がないことが多い。

でも、とりあえず調整が済み、評価できるうようになったとしよう。次世代を作るときに、選択として、まず今の世代から、比較的望ましい評価がされた染色体を次世代にコピーする。次に交叉であるが、現世代から2つの染色体を選んで掛け合わせる。でも、2次元のデータ2つを掛け合わせるといっても、実際にどうやるかは色々考えられるが、1つやった方法を紹介しよう。

2つの染色体の制御点の位置は一致しているので、この2つの染色体(板)を重ねた状態で、適当なところに直線を引き分割する。次に、それぞれの側から異なる切断された染色体を取り出し、無理やり貼り付けるのだが、切断線付近は壊された遺伝子も多数あり、それらの遺伝子をとりのぞき、空白地帯を作る。しかし、空白地帯のままでは、評価不能なので、空白地帯に詰め物をして、評価可能な状態にする。この空白地帯をなんとかするのは、まさに生物の染色体の修復作業と似たようなものかも知れない。

別の例で言うならば、2枚の絵を重ねて切断し、違う絵同士を切断線で貼り付け、切断線が分からないように細工をするような感じだ。

こうして、何とか2つの親染色体の性質をできるだけ引き継いだ子染色体ができる。切断後の修復がうまく行くと、子染色体の評価が良くなることがよくある。しかし、切断後の傷跡が深いと、子染色体の評価は著しく落ちて、早々に廃棄しないといけなくなる。

実際には、以上のような考えをどうプログラミングするかが遺伝的アルゴリズムでは非常に重要で、性能にも非常に影響する。

トラックバック(0)

トラックバックURL: http://labs.timedia.co.jp/mt/mt-tb.cgi/381

コメントする

このブログ記事について

このページは、fujiが2013年5月10日 00:00に書いたブログ記事です。

ひとつ前のブログ記事は「突然変異が進化の原動力」です。

次のブログ記事は「RailsのDebug環境を改善する」です。

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