遺伝的アルゴリズム、実数値GA、確率モデルGA

• 進化的計算手法は自然における生物の進化を模倣した計算モデルで、
  • シミュレーションに基づく進化に対する考察、
  • 自然淘汰の原理を用いた最適化問題の解法、

等を目的として研究されています。

• 以下では最適化アルゴリズムとしてのGAについて解説します。

GAの特徴としては

• 目的関数への制約が少ない
• 多点探索である（大域的探索が可能）

• 評価回数に対する収束速度は遅い

• 遺伝的アルゴリズム(GA)はビット列の最適化問題への適用から始まりました。
  • 基本的な定理としてはスキーマ定理(Holland)や積み木仮説(Goldberg)などが知られています。

• GAの実装は以下の要素によって決まります。
  • 目的関数

最適化する関数です

• 表現型-遺伝子型のコード方法

問題によってバイナリ/実数値/順列など様々です。

目的関数と遺伝子型から探索空間の形状=景観が定まります。

• 選択の方法
• 遺伝オペレータ(複製/交叉/変異)

図：遺伝的アルゴリズムの手順

• 実数値コーディングGA(RCGA)は遺伝子型が実数値ベクトルであるGAです。

実数値最適化にも最初はビット列GAの延長としてGrey Codingによる遺伝子型が用いられました。

しかし、これは景観を無用に複雑にすることから実数値コーディングが優るといわれています。

実問題への応用の観点からも実数値GAの重要性は高いといえます。

• 実数値GAにおける基本となる考え方に機能分担仮説(喜多、山村)があります。GAの基本要素に以下のように役割を分担させるというものです。
  • 交叉：集団の統計量を保存しつつサンプリングを行う
  • 世代交代：評価関数に基づいて分布を変化させる
  • 突然変異：分布を拡張する
  • 交叉によって集団内の距離を増大させる(Deb)

• 上の仮説は実数値GAでは「統計量の保存」を満たす交叉として実現されます。
• 実数値GAの仕組みは
  • 集団=MC法による抽出サンプル
  • 目的関数の景観を反映する確率分布を推定

の繰り返しとして考えられています。

• 実装例: BLX-a(Eshelman), UNDX(小野), SPX(樋口), PCX(Deb), EDX(佐久間)等

• 上記交叉の式や計算量を以下に示します。
• 図は2次元の探索空間で３親個体から適当な乱数を用いて各種交叉によって生成された子供個体を示します。

• UNDX

計算量：O(m2)

定義域中央に向かうサンプリングバイアスを持ちます。

• PCX

計算量：O(m)

計算量は小さいが親を増やしても悪スケール性に対応できない

サンプリングバイアスは小さい

• SPX

• サンプリングバイアスというのは正規分布を用いるため子供個体の生成確率が定義域の中央部分と端側で異なる（中央に偏る）現象を指します。

• GAの世代交代は自然淘汰のモデル化で親子個体を併せた集団から、次世代に残す個体を選択する方法です。

世代交代を現世代Mから次世代の個体群M'を生成する関数とします

親個体Pの選択やPから子個体Cを生成する遺伝操作も以下のように定義します。

簡単のために遺伝操作は交叉だけとします

• Steady State Modelと呼ばれる世代交代モデルは

と表されます。これは現集団と子供の中から最も優れた個体を選択しようというものです。

• 上の手法は自然淘汰の概念を具体化したものですが、このようなエリートのみを選択していると集団の多様性が急速に失われます。
• 多様性の喪失はGAにとって致命的で、多点探索としての利点が損なわれると非常に無駄の多いアルゴリズムになってしまいます。
• 自然淘汰の強い収束圧力を緩和した世代交代モデルが多く提案されています。

• そのひとつがMinimal Generation Gap (佐藤)と呼ばれる多様性維持に優れたモデルです。

親n個体をランダムに選択し、

そこから多数(l)の子供個体を生成し、

子供と親を合わせた中から最優秀な一個体を選択し、

あとは目的関数値に比例する確率で選択するというものです。

他に、MGGの一部を上位選択にしたものもあります

• General Generation Gap (Deb)

• 性能評価

最適化問題のベンチマークの例を以下に示します。それぞれ、

• 単峰性/多峰性
• スケール性
• 変数間依存
• 次元数(スケーラビリティ)

などの特徴があります。よく用いられるものとして、

• Sphere/Elliptic
• Rastrigin(多峰性)
• Schwefel(多峰性)
• Rosenbrock(変数間依存性/多峰性)
• 回転/平行移動(変数間依存性/バイアス)

などがあります。ここに記していないものもありますが、テストの際はそれぞれの関数の特徴をよく把握しておくことが重要です。

• Two-max (Two-peaks)
• Cigar/Tablet(スケール性)
• Shekel
• Ackley
• Griewank

• 以下、確率モデルGAの解説ですが、まだ準備中です。

確率モデルGAの要素

• 目的関数
• コーディング
• 確率分布モデル
• モデル学習手法
• サンプリング
• 選択

例)

• UMDA: q=(m,s2)
• PBIL: q=m, q’=(1-a)q + a(q)

• バイナリ関数の最適化
  • 確率モデルを用いることで連続的な遷移を表現
  • 破壊的な交叉を削減

• 実関数の最適化
  • 目的関数を確率密度関数として表現
  • モデル推定器＋サンプラー

• モデルの種類による分類
  • Multi-variate Gaussian Model：周辺分布関数を利用
  • Graphical Model：リンケージ学習(依存性をグラフモデルで表現)
  • Non/Semi-Parametric Model

• 世代交代
  • Hessian則的(PBIL)
  • Incremental(EMNA)

• 実数値GAとの対比
  • 実数値GA:ボトムアップで分布を近似
  • 確率モデルGA: 集団全体の分布に注目する（クラスタリングや階層構造を考える）