遺伝的プログラミング

出典: フリー百科事典『ウィキペディア（Wikipedia）』

遺伝的プログラミング（いでんてき-、英 Genetic Programming GPと略記）とはメタヒューリスティックなアルゴリズム、遺伝的アルゴリズムの拡張手法であり進化的アルゴリズムの四つの主要な方法論の内の一つでもある。

[編集] 概要

遺伝的プログラミングは1990年にジョン・コザ（John Koza）によって提案された。他の進化的アルゴリズムの主要な方法論が同時期に提案され独立に研究が進められていたのに対し、遺伝的プログラミングは最初から遺伝的アルゴリズムの拡張として提案されており、他の三つの方法とは大きく立場を異にする。

具体的な内容としては遺伝的アルゴリズムにおける遺伝子型の表現が主に配列であるのに対し遺伝的プログラミングは木構造を用いる。このため遺伝的アルゴリズムでは表現できなかった数式やプログラムのコードなどを表現することができる。大きな違いとしてはこれだけであるが、遺伝的アルゴリズムとは解の探索の傾向が異なるうえに独自の現象や問題点が発生したり、それに対する改善案など現在非常に活発に研究されており遺伝的アルゴリズムからはほとんど独立して研究が進められている。遺伝的プログラミングのみを扱った書籍も増えている。

なおコザが発表したシステムは Lisp で書かれていたため、現在はあらゆる言語で実装されているにもかかわらず解を Lisp のS式で表現する遺伝的プログラミングのシステムが多く一種の慣例になっている。

[編集] アルゴリズムの内容

遺伝的プログラミングの探索の流れは遺伝的アルゴリズムと全く同じである（遺伝的アルゴリズム#アルゴリズムの流れ参照）。ただし遺伝子型の表現方法が違うため交叉や突然変異の方法が若干異なったものになっている。

解の表現方法

遺伝的プログラミングでは遺伝子型の表現に木構造を使う、このため取り扱う問題が自然と遺伝的アルゴリズムとは異なってくる。遺伝的プログラミングの適用分野としては関数の同定問題やニューラルネットワークや電子回路の設計、あるいはロボットの制御プログラミングの作成などに使用されている。解の表現は例えば関数同定問題なら解は関数であるため配列でこれを表現することは難しい、ところが例えば

という木構造なら $x\times(2-x)$ を表しているというふうに、木構造なら容易に表すことが可能であり、遺伝的プログラミングはこの木を遺伝子型として用いる。

交叉

交叉は主に部分木の取り換えで行われる、具体的には下記の画像のような操作が行われる。

この例では関数 $3\times((x\times 4) + x)$ と関数 $(3+x)-(2/(x\times x))$ になる木を交叉させて、関数 $3\times(x\times x)$ と関数 $(3+x)-(2/((x\times 4) + x))$ となる木が生成されたことを表している。交叉を行う部分木の場所は一般にはランダムで決める。