遺伝的プログラミング

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

概要

遺伝的プログラミングは1990年にジョン・コザ（John Koza）によって提案された。他の進化的アルゴリズムの主要な方法論が同時期に提案され独立して研究が進められていたのに対し、遺伝的プログラミングは最初から遺伝的アルゴリズムの拡張として提案されており、他の三つの方法とは大きく立場を異にする。具体的な内容としては、遺伝的アルゴリズムにおける遺伝子型の表現が主に配列であるのに対し、遺伝的プログラミングでは木構造を用いる。このため、遺伝的アルゴリズムでは表現できなかった数式やプログラムのコードなど、構造を持ったデータを表現することができる。大きな違いとしてはこれだけであるが、遺伝的アルゴリズムとは解の探索の傾向が異なり、また独自の現象や問題点が発生する。現在、それに対する改善案などが非常に活発に研究されており、遺伝的アルゴリズムからはほとんど独立して研究が進められている。遺伝的プログラミングのみを扱った書籍も増えている。なお、コザが発表したシステムは Lisp で書かれていたため、現在はあらゆるプログラミング言語で実装されているにもかかわらず解を Lisp のS式で表現することが一種の慣例になっている。

アルゴリズムの内容

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

解の表現方法

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

という木構造なら $x\times (2-x)$ を表しているというふうに、容易にこれを表現することができる。

解個体を表す木にどういった関数記号を用いるかは事前に決めておくのが一般的で、{＋, −, ×, ÷}など一般的な演算子の他に{sin, cos, tan, exp, log_ex, x²}といった単項の初等関数などを扱わせることもある。また、2つの枝の持つ値の最大値や最小値をとる関数max, minのほか、無条件で片方の枝の値のみを利用しもう一方は無視する関数を設定することもある。

交叉

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

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