進化的プログラミング

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

進化的プログラミング(しんかてきプログラミング、Evolutionary Programming)は、4つの主要な進化的アルゴリズム方法論の1つである。

概要[編集]

人工知能の生成を意図した学習過程として、シミュレーションされた進化を使った Lawrence J. Fogel が1960年に最初に使った用語である。Fogel は予測機として有限状態機械を使い、それを発展させた。

その後、彼の息子の David B. Fogelにより実数関数最適化問題を探索する手法に拡張され、進化的戦略と類似した方法に発展した。

進化的プログラミングの中心となるのは突然変異である。親ベクトルに対してランダムな変化を加えて子ベクトルを生成し、それらを評価して、ランダムに個体を選んで適用度を比較する。これによって次の世代を選び、解が収束するまでこれを繰り返していく。

現在、進化的プログラミングは他の3つの方法論に比べると特に決まった構造が無く、進化的コンピューティング全般を漠然と指す用語となっている。進化的プログラミングと進化的戦略を区別することは困難になってきている。

アルゴリズムの流れ[編集]

上記の記述通り、進化的プログラミングは現在決まった構造を持たない。そこで、ここでは D.B.Fogel が提案した実数関数の探索アルゴリズムの流れを述べる。

  1. N  個の個体(この場合は関数の引数)を用意して、これにランダムで初期値を設定する。
  2. 個体のそれぞれのコピーをつくる。
  3. 2. で作った各コピーに正規乱数(乱数列参照)を加える。
  4. 3. の操作で作られた新しい N  個の個体と、元の個体を混ぜた 2N  個の各個体に対して評価値を求める、評価値の求め方は以下の通り。
    1. 評価値を求める個体以外の個体をランダムで q 個選択する。
    2. 選んだ q 個の個体のうち、対象の個体より成績が悪い個体(最大値を求める場合は、対象の個体より関数の値が小さい個体)の数をその個体の評価値とする。
  5. 評価値順に個体をソートする。
  6. 下位 N 個の個体を削除する。
  7. 終了条件を満たすまで2. 以下の操作を繰り返す。
  8. 残った中で最も成績の良い個体を「解」として出力する。

上記のアルゴリズムの場合、コピーした個体に正規乱数を加える操作が突然変異の操作にあたる。

特徴としては、評価値の与え方がある。この評価値は集団中で最も優れた個体の評価値は q になり、最も劣っている個体の評価値は 0 になるがそれ以外の個体の評価値は一定ではなく比較的優秀な個体の評価値の方が高くなる確率が高い確率的関数であるといえる。

このような評価値を与えることを進化的プログラミングの特徴に挙げることもある。ただし、この評価値の与え方および個体の残し方は全くの拡張も変更も行わずに他の進化的アルゴリズム(遺伝的アルゴリズム進化的戦略)に適用可能である。

参考文献[編集]

日本では進化的プログラミングを専門に扱っている書籍はほとんどない。ただし、遺伝的アルゴリズムの解説本などの中には進化的プログラミングのアルゴリズムの内容に簡単に触れている本がいくつかある。

  • 坂和正敏、田中雅博、『遺伝的アルゴリズム』、朝倉書店、1995年、ISBN 4-254-20990-8
  • 三宮信夫、喜多 一、玉置 久、岩本貴司『遺伝アルゴリズムと最適化』、朝倉書店、1998年、ISBN 4-254-20977-0

関連項目[編集]