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

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

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

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

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

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

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

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

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