2005-11-30

３　遺伝アルゴリズム(GA)による最適化計算(実例紹介)

遺伝アルゴリズム

GA
- 基本
  - 決定変数と制約条件の決定(解空間 $F$ の設定
  - 目的関数 $f$ の設定
  - 決定変数の遺伝子的表現(エンコーディング)
  - 遺伝子型から表現型への置換規則の設定(デコーディング)
  - 表現型の適応度の設定(適応度は目的変数の関数として定められる)
  - 遺伝演算子(個体数・世代数。交叉確率・変異確率)の設定
- 実行上の諸設定
  - 次世代個体が解空間に納まるような遺伝演算を工夫する
  - 解空間に納まるような次世代個体が作成できるまで遺伝演算を繰り返す
  - 適応度関数と次世代子孫数とには工夫をしないと、多様性が失われてしまって解の探索が進まなくなる。これを初期収束(premature convergence)問題と呼び、それに対する適応度分布の調整をスケーリング(scaling)と呼ぶ
  - 遺伝演算パラメタの設定(集団遺伝学における生物集団の計算とは異なる用途を設定している記述であることに注意)
    - M(個体数)〜10-100
    - Pcは新しい解の探索の主力であり、同一アレル間の交叉は新アレルを生じないので、経験的に0.5-1が用いられる
    - Pmは0.1以下の値がよく用いられる。大きなPmは交叉による解候補を壊す要素として作用するらしい
    - 実行時間はMxTx(個別の新個体の評価にかかる時間)に依存する
- 構成例
  - どのくらい｢算数的か」のイメージを持とう
  - $f=a(x_1^2-x_2^2)^2+b(1-x_1)^2,-d￥le x_i ￥le d$ などとし、 $x_i$ の範囲を制約条件として定める。 $x_i$ を定める｢遺伝子」は単位長さの01でできた配列で表し、その10桁の数値は2進法として評価して10進数の $y_i$ にし、その上で、形質 $x_i$ を $x_i=2d￥frac{y_i}{k}-d$ などとして、制約条件内に納まるように数式的工夫をする
  - 遺伝子は01の配列であらわし、単位長さごと(10ずつ、とか)に「単位＝遺伝子＝形質に対応するもの」として、形質を決定する
  - 演算の進行による解の動きは、「最適解」へ向かって近づいたり離れたりしながらも次第に近づいていくが、ときおり大きく変化する
  - コーディング
    - 上述のように２進法を用いるバイナリコーディングの他、Grayコーディングというものもあり、これは、小さな遺伝子配列(01)の変化がデコードするときに小さな形質変化に対応するようなコーディングである
  - エリート戦略
    - 演算の途中で最高適応度を持つ個体については、交叉や突然変異で失われないようにする工夫
  - 適応度が高めの子孫も工夫をしないと子孫を残し損ねることがしばしばあるので、それを防ぐ工夫として、残す子孫数の決定において、適応度に応じて与えられた値のfloorをとって平均以上の適応度を有する個体は子孫を１つ以上残せるようにすることもある。また、トーナメント選択法と呼ばれる手法などもある
  - 適応度のスケーリング
    - 適応度がある程度あっても子孫を残し損ねる点の回避法を上で述べたが、逆にある程度適応度が均質化してくると、適応度の高い個体の有利な度合いが顕著でなくなり、最適解への収束が鈍る。これを防ぐ方法として、そのときどきの世代における適応度の差が子孫数に反映するように調整することを適応度のスケーリングという
  - 交叉の起こしへの工夫
    - 上述の方法では、すべての遺伝子は連鎖していた。この場合、遺伝子(決定変数)の並び方に意味が生じる。決定変数同士の関係を連鎖の強さ・その一極端としての独立を念頭に個々の決定変数間での交叉の発生を調整する(同一染色体上ではモルガン単位を、また、異なる染色体上の遺伝子の存在を考慮するようなもの)
  - ペナルティ
    - 制約条件は解の満たすべき条件であるが、遺伝アルゴリズムの経過中には、制約条件をすべての個体が満たすことを要求せず、ある一定レベルの不満足は、ペナルティ・パラメタとして定量化し適応度を下げることで対応する。適応度には下限があり、それは子孫を残せないという状況である
  - 発見的手法(heuristics)を持ち込んで最適解に近いところへジャンプしてから遺伝アルゴリズムで最適解探索を進めることも可能である
    - Greedyアルゴリズムもそのひとつ
    - Heuristics for computer scienceのWikipedia in Eglishの訳としては
      - 計算機科学において、heuristics(発見的手法)とは、ある問題を解くときに、解が正しいか否かはさておき、おおまかにはよさそうな解を与える方法、または、類似だがより簡単な問題の解を与えることがわかっている方法を適用して、仮の解を得る方法。厳密性・正確性は計算上の効率や解の理解しやすさの点から有意義とみなせることを目的として適用される
  - 巡回セールスマン問題での個体はノードの順列情報を個体に持たせる。コーディングの工夫と交叉演算子、変異演算子の工夫が紹介されている。ノードの順列自体を遺伝子型とするのではなく、ノードの訪問順を数値規則化する工夫(Grefenstetteらの方法)などがある。ただし、ノード順列の離散性のため、生成個体のノード順列が訪問ノード順列として不適切な場合が高頻度で生まれるので、それを修正する工夫が複数種類示されている。また、順列の特性(一度ずつ登場→訪問順を全体と部分に分け、部分訪問を単位に遺伝子型を変化させる交叉演算子も紹介されている。変異演算子に交換・逆位・挿入変異の概念を加えて、正等な遺伝子型を生成する工夫もある
  - GAにおける遺伝。GAでは、最適解を構成するべき決定変数の特性を遺伝させ、複数の決定変数によりよい値を持たせるために交叉させ、また、交叉だけでは実現できない「よりよい決定変数の値｣を変異によって新たに生み出す
  - スケジューリング問題であるフローショップ工程スケジューリング問題では機器ｘ作業種類をノードとしノード間にエッジを張ったグラフを想定し、それをネットワーク流(記事はこちら)問題として表現する方法や機器ｘ作業種類の要素を順列扱いする方法などが紹介されている