遺伝的プログラミング
遺伝的プログラミングでは遺伝子型の表現に木構造を使うため、取り扱う問題が自然と遺伝的アルゴリズムとは異なってくる。遺伝的プログラミングの適用分野としては関数の同定問題やニューラルネットワークや電子回路の設計、あるいはロボットの制御プログラミングの作成などがある。解の表現は、例えば関数同定問題なら解は関数であるために、配列でこれを表現することは難しい。ところが、例えば
という木構造なら x × ( 2 − x ) {\displaystyle x\times (2-x)} を表しているというふうに、容易にこれを表現することができる。
解個体を表す木にどういった関数記号を用いるかは事前に決めておくのが一般的で、{+, −, ×, ÷}など一般的な演算子の他に{sin, cos, tan, exp, logex, x}といった単項の初等関数などを扱わせることもある。また、2つの枝の持つ値の最大値や最小値をとる関数max, minのほか、無条件で片方の枝の値のみを利用しもう一方は無視する関数を設定することもある。
交叉は主に部分木の取り換えで行われる。具体的には下記の画像のような操作が行われる。
この例では関数 3 × ( ( x × 4 ) + x ) {\displaystyle 3\times ((x\times 4)+x)} と関数 ( 3 + x ) − ( 2 / ( x × x ) ) {\displaystyle (3+x)-(2/(x\times x))} になる木を交叉させて、関数 3 × ( x × x ) {\displaystyle 3\times (x\times x)} と関数 ( 3 + x ) − ( 2 / ( ( x × 4 ) + x ) ) {\displaystyle (3+x)-(2/((x\times 4)+x))} となる木が生成されたことを表している。交叉を行う部分木の場所は、一般的にはランダムに決定する。