遺伝的プログラミングのソースを表示

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

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

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

=== 解の表現方法 ===
遺伝的プログラミングでは遺伝子型の表現に木構造を使うため、取り扱う問題が自然と遺伝的アルゴリズムとは異なってくる。遺伝的プログラミングの適用分野としては[[関数_(数学)|関数]]の同定問題や[[ニューラルネットワーク]]や[[電子回路]]の設計、あるいは[[ロボット]]の制御プログラミングの作成などがある。解の表現は、例えば関数同定問題なら解は関数であるために、配列でこれを表現することは難しい。ところが、例えば
[[画像:GP_tree1.png|center|200px]]
という木構造なら <math>x\times(2-x)</math> を表しているというふうに、容易にこれを表現することができる。

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

=== 交叉 ===
交叉は主に[[部分木]]の取り換えで行われる。具体的には下記の画像のような操作が行われる。
[[画像:GP_crossover.png|center|300px]]
この例では関数 <math>3\times((x\times 4) + x)</math> と関数 <math>(3+x)-(2/(x\times x))</math> になる木を交叉させて、関数 <math>3\times(x\times x)</math> と関数 <math>(3+x)-(2/((x\times 4) + x))</math> となる木が生成されたことを表している。交叉を行う部分木の場所は、一般的には[[ランダム]]に決定する。

== 参考文献 ==
*伊庭斉志、『遺伝的プログラミング入門』、東京大学出版会、2001年、ISBN 4-13-061402-9

== 関連項目 ==
*[[進化的計算]]
*[[進化的アルゴリズム]]
*[[遺伝的アルゴリズム]]
*[[進化的プログラミング]]
*[[進化戦略]]

== 外部リンク ==
* [https://www.waseda.jp/sem-hflab/eclab/index.html 平澤研究室]（[http://www.waseda.jp/ips/ 早稲田大学大学院情報生産システム研究科]）

{{Computer-stub}}
{{Normdaten}}
{{DEFAULTSORT:いてんてきふろくらみんく}}
[[Category:人工知能]]
[[Category:最適化アルゴリズム]]
[[Category:遺伝的アルゴリズム]]

[[de:Evolutionärer Algorithmus#Genetische Programmierung]]