４ 遺伝アルゴリズム(GA)の理論

• アルゴリズム的内容
  
  • スキーマ解析
  • 最適解の発見確率
  • 適応度関数の自己相関(適応度関数の最適解付近での様相と最適解探索)
• 集団遺伝学的内容
  
  • 有限個体数がもたらす遺伝的浮動
• スキーマ解析
  
  • 個体を発生させて進化させていくと、個体が共有する特徴に着目するとその特徴の消長がシミュレートされる。スキーマの消長はそのスキーマに属する個体の適応度の総和により決まり、よりよいスキーマは個体数を増やしていくことにより、ますます子孫数を増やす仕組みになっており、指数関数的に子孫数を増やす。また、このスキーマは染色体上に並んでおり、そこに交叉を起こすというGAの原理から、局所的な評価をしながら、大域的に適応度を上げていく方法である。局所的に適応度が高い遺伝子配列はスキーマとして指数関数的に子孫を増やすことが示されており、スキーマ定理と呼ばれる。最適スキーマが進化の結果得られ、このスキーマが解であるとも言える。
• 最適解の発見確率
  
  • GAは有限マルコフ連鎖である。マルコフ連鎖とは、ある状態の条件付き確率がその前の状態の条件つき確率になっている状態推移過程である。その中でも直前の状態にのみ依存し、それ以前の状態には依存しないものを有限マルコフ連鎖と呼ぶ。
  • (有限)マルコフ連鎖においては、状態の推移条件により平衡状態に至ることが知られており、その平行状態は初期確率分布の与え方によらないことも知られている。このようなマルコフ連鎖の状態全体の平衡分布は、最適解以外にも正の確率を与えるので、マルコフ連鎖であるGAの解が最適解をもたらす確率は１に達しない
  • マルコフ連鎖であるGAで最適解をもたらす確率を１にするためには、GAの最適解を示す固体(もしくは集団)とマルコフ連鎖で平衡状態に持ち込む集団とに乖離をもたせ、かつ、最適解への推移が一方向(最適解が推移集団に加わることはあっても抹消されることはないような推移条件)であるようにするのが１法である。たとえば最適解をマルコフ連鎖で推移させる集団の中でもっとも適応度の高いものとし、推移集団中でもっとも適応度の高い集団は確率１で子孫を残すものとすると、平衡集団中の最大適応度個体が最適解である確率が１に収束する
• 適応度関数の最適解付近での様相と最適解探索
  
  • ある解とある解とがGAによってすぐに遷移するとき、この解同士は、｢解空間の中で近い」関係にあると考える。このような「解空間＝解分布平面」上に適応度関数をプロットすることで適応度関数の「景観」が形成される。「景観」が単純な山をなしていれば、GAにより最適解に到達することは容易だが、複数の峰の集まりであると、局所的最適解に到達してそこから脱することができなくなる。そこから脱出して最適解の探索を続け、最適解にいたるためには、「最適解付近」にいたったあと、その「周辺」を探索する必要があるが、その「探索範囲」がどれくらいかわかる必要がある。最適解付近の「景観」を特徴付ける指標として自己相関関数とその相関長というものを定義できる。適応度関数の相関長は、その相関長より遠位では適応度関数の値がランダムであり、それより近位では現在地点の値との相関が認められることを示す指標である。したがって、「仮に到達した解」から周辺を探索するにあたっては、適応度関数の相関長の格子で区分けされた小部分について「調べ｣るとよいだろうことに根拠が与えられる
• 有限個体数がもたらす遺伝的浮動
  
  • 新規に生じた変異が中立であるとき、その変異は子孫を多く残したり、少なく残したりする。中立であるのでその多寡はランダムである。もしも集団個体数が無限であると、変異が残す子孫数は、ゼロではないので、消滅することはないが、個体数が有限である限り、子孫を残さない染色体が存在する。そのような確率は低くなく、実際、大多数の変異は、１代限りで、そして多くの変異が短期間のうちに消滅する。中には、野生型を駆逐してしまう変異も数は少ないが存在する。中立変異が一定の頻度で新生しているとすると、集団中に認められる中立変異の数は、集団個体数によらず、変異率によって決まることが知られている。

このように中立な変異も消長することは、GAにおいて変異に適応度を与えて最適解を求める方法において留意するべきポイントである

１ 進化型計算の系譜

進化型計算の系譜。遺伝アルゴリズム(Genetic Algorithm)、進化プログラミング(Evolutionary Programming)、進化戦略(Evolution Strategy)と個別の呼び名と個別の由来を持つものが、進化型計算(Evolutionary Computation)として統一的に称される。遺伝アルゴリズム(GA)はその中でもっとも名称としてとおりがよい

これらの比較は、６　進化型計算の動向　の記事　にて

２ 遺伝アルゴリズム(GA)の基礎

• 最適化問題とGA

決定変数があり、それらが分布しうる範囲は基本空間のうちの部分空間についてなる制約条件を満たすときに、目的関数を最小にするようなを求めることを最適化と呼び、その解を最適解と呼ぶ。最適化には、GA以外にもさまざまな手法があるが、それらの手法が不適切な場合があり、そのような場合にGAによる最適化が有効である。そのような場合とは、目的関数が多峰性であったり、が離散集合であったりする場合である

• 組み合わせ最適化問題

決定変数の制約条件が組み合わせ的であるような条件のときの最適化問題で、離散集合型である点で連続分布に対する解法が不適であるとともに、組み合わせ数が膨大になるという点でNP困難な問題に属する

組み合わせ最適化問題に対する解法は大きく２つに分けられる。１つは厳密解法、もうひとつは近似解法である

厳密解法はしらみつぶし法であるが、すべてをしらみつぶしに調べるのはあまりに膨大なので、動的計画法(Dynamic programming)、分枝限定法などによるしらみつぶす範囲の限定操作を行う方法も用いられる

近似解法にはランダムに広域をスキャンしつつ解に到達使用とする方法(モンテカルロ)と取得情報を用いてより解に近い方向へと進む逐次改善法・欲張り(Greedy)法に大別できる。GAは近似解法に属し、その中でも取得情報を用いて進みながら、ランダム性を持たせる解法である

• GAの『遺伝的』側面

遺伝子は交叉と変異により変化する。組み換えは親世代にて起き、子世代は２親から２対の遺伝子を受け取り、そこで生じた遺伝子のペアが次々世代への伝達時の交叉を起こすペアとなる。次世代への遺伝子の伝達は遺伝子型によって決まる表現型が決める適応度により選択圧がかかる。適応度は保有遺伝子の組み合わせにより基底される

もっとも単純なGAのパラメタは、個体数(M)・世代数(T)・交叉確率(Pc)・変異確率(Pm)の４つである

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

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

遺伝的浮動

この記事の末尾

５ 遺伝アルゴリズム(GA)の拡張

• 内容
  
  • 並列化
  • ハイブリッド化
  • 可変長染色体
  • ニッチ(一定環境における生態系(複数種の混在定常状態)モデル
  • 多目的最適化
  • 免疫システムモデル
• 並列化

単純並列アプローチとして、個体ごとの処理である発生個体の適応度評価と、それらをあわせて世代単位で処理する遺伝プロセスとに分解する方法がある。また、分解型アプローチとして、集団を区分けして処理する方法がある。集団の区分けとしては集団が互いにある程度隔離された亜集団の集まりとし、亜集団ごとに処理をし、亜集団間で情報のやりとりをする方法と、個体同士の空間的位置関係になぞらえて個体間の遠近関係を導入し、個体ごとに処理し個体間処理の情報をやりとりする方法がある

• ハイブリッド化

GAを最適化探索の１部品として他の探索アルゴリズムと組み合わせる方法。Heuristicsと組み合わせるのもそのひとつ。また、GAは局所での最適解到達には不向きなアルゴリズムなのでGAによって得られた解から局所探索をする方法も知られ、遺伝的局所探索(Genetic Local Search)と呼ばれている。遺伝的局所探索は生物学的な意味合いで、次のように説明される。遺伝子がGAで作られたのち、環境適応できるものは、適応し、その環境適応の部分を局所探索による改善がもたらしていると考える。その環境適応度の多寡が子孫数に反映するというもので、この後天性の適応が遺伝子変化として次世代に伝わるとする立場(遺伝のラマルク主義)と、後天性の適応は遺伝子変化をもたらさないが、子孫数に影響を与えることによって、結果として選択個体の遺伝型(解)に影響を与えるという立場(ボールドウィン主義)とがある。また、局所探索路を複数化する方法(多スタート局所探索法)と呼ばれるものも知られる。さらには、確率的に解の改善を試みる方法である、シミュレーテッド・アニーリング法がある。この方法は熱力学的平衡状態を模している。非常に多くの分子の集合は、平衡状態において温度という値を有する。個々の分子はそれぞれ、運動エネルギーを持つが、そのエネルギーは確率的に分子間で交換され定常分布に達する。温度は、この定常分布を決めるパラメタである。温度が高いときには、分子集合中の分子の中には、局所解から近隣の別の局所解(最適解の可能性がある)に遷移しうる分子エネルギーを持つものが含まれる可能性が高く、温度が低くなるにつれ、遷移のために乗り越えるエネルギー閾値が低くなる。したがって、温度を高温から低温に下げるという１パラメタを制御することによって、演算の初めには大域的探索を行い、処理を進めるにしたがって、局所のみの探索に限定していくことが可能となる

• 可変長染色体

その名のとおり、遺伝子情報の総長を可変にすることで探索の改善を目指す方法

• ニッチ(一定環境における生態系(複数種の混在定常状態)モデル

生物界ではある環境は有限な広さを持ち、有限な資源を持つ。そこには生態系と呼ばれる生物−生物間の食物連鎖や共生関係が存在し、固定的な定常状態や周期性を持つ定常推移状態にある。この考え方を援用し、複数の目的関数が作る組み合わせ最適解を演算対象とする方法もある

• 多目的最適化

多目的最適化においては、パレート最適解という概念がある。x,yは自然数でありを満たすときに、x+yを最大にするx,yはであり、最適解が２つ存在する。このようなとき、この２つの解をパレート最適解とよび、両者をパレート最適解群とかパレート最適解集合と呼ぶ。多目的最適化問題においては、パレート最適解集合の中の１つを求めるのではなくパレート最適解をすべて求めることが通常である。探索にあたっては、パレート最適解の１つを探索し、パレート最適解集合に属する他の解を明示的に扱う方法と、それらの明示的に扱わない方法とに分けられる

• 免疫システムモデル

遺伝において遺伝子情報を交換(交叉)するのは、生物が多様性構築を通して達成している最適化戦略の一つ(目的論的にか結果論的にかは問題にしないとして)であるが、同様に生物が多様性を通じて機能を発揮しているシステムに免疫系の抗体多様性がある。この原理を最適化に援用したのが免疫システムによる最適化計算法である

駆け足で読む遺伝アルゴリズムと最適化

• 教科書は『遺伝アルゴリズムと最適化 システム制御情報ライブラリー 17』システム制御情報学会編 三宮信夫・喜多 一・玉置 久・岩本貴司 朝倉書店 おすすめ度★★★☆☆

  遺伝アルゴリズムと最適化

目次

１　進化型計算の系譜

２　遺伝アルゴリズム(GA)の基礎

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

４　遺伝アルゴリズム(GA)の理論

５　遺伝アルゴリズム(GA)の拡張

６　進化型計算の動向

７　適用事例(省略)

６ 進化型計算の動向

• 進化戦略(Evolution Strategy)

n次元実数空間において非線形最適化問題を解くことを目的に開発されたアルゴリズム。正規分布に従った摂動を加える(変異に相当)。組み換え演算の組み込みも可能。個体の進化を想定している。適応度を指標に確定的に次世代個体を選択する。次世代の選択には子世代からのみの場合と親・子両世代からの場合がある。多峰性局所解があり、微分などに向かない関数用

• 進化プログラミング(Evolutionary Programming)

種の進化の原理を利用。種間では組み換えは起こらないので、進化プログラミングでは組み換えは持ち込まず変異のみを用いる。選択は確率的。

• 遺伝プログラミング(Genetic Programming)

機械学習によりプログラムを自動生成しながら進化的に改善していく方法である。

• 遺伝アルゴリズム(GA)、進化戦略(ES)、進化プログラミング(EP)、進化プログラミング(GP)の相互比較

相互は「遺伝原理の応用」というところで一致し、相互の垣根はなくなりつつある(もうない？)

• 個体

GA:離散値、ES:連続値、EP:連続値、GP:木・S式(LISP)

• パラメタ調整

GA:しない、ES:共分散行列、EP:分散、GP:しない

• 適応度

GA:目的関数値(スケーリング)、ES:目的関数値、EP:目的関数値(スケーリング)、GP:プログラムとしての機能評価結果

• 変異と組み替え

GA:組み換えが主・変異は補助的、ES:変異が主・組み換えは補助、EP:組み換えが主、変異は補助

• 選択・淘汰・複製

GA:確率的・保存的、ES:確定的・消滅的、EP:確率的・消滅的、GP:確率的・保存的

• 対話的進化
  
  • 適応度の定義が確定的でなく、変化するような環境で、それらに応じて、「最適解」を更新させるようなシステム。入力値を受け付けながら、最適解を経時的に変化させる
• ゲーム理論

ゲーム理論では、複数のプレーヤーがそれぞれの行動をとる中で、相手の出方に対応しながら行動を決めていく。最適化問題においてもこのようなゲーム理論の枠組みでの利用が考えられる