遺伝的プログラミング

遺伝的プログラミングとは, 遺伝的アルゴリズムの遺伝子に構造的表現が扱え るようにしたもので, John Kozaによって提唱された. 以下に遺伝的プログラミングについて述べる.

図5.5: GPにおける遺伝子の例

GPではGAで行なわれてきた交叉や突然変異は, 全て木構造に対して行なわれる. GPの処理手順もGAと同様である. 遺伝子の具体例として 図5.5 に示す. この遺伝子構造は, 下のS式

(progn (incf x)(setq x 2)(print x))

と同義である. 図に示すように, 遺伝子はS式で書かれるプログラムとなり, その遺伝子を環境 上で評価することにより, 適応度が得られる. 遺伝的操作は, 基本的にはGAと同じであるが, 交差のオペレーションがGPにとっ て非常に重要なものとなるため, 以下に述べる. 遺伝的操作を 図5.6 , 図5.7 , 図5.8 に示す.

図5.6: GPにおける突然変異の例

図5.7: GPにおける交叉の例1

図5.8: GPにおける交叉の例2

GPでは遺伝子構造が木構造であるため, 交叉は２つの遺伝子のランダムに選択 された部分木を入れ換える操作となる. 図5.7 がそれであ る. GAの交叉との大きな違いは, 同じ遺伝子を持った個体同士を交叉させても, 同じ 遺伝子を持った子供が必ずしも生まれないという点である. GAの場合,

となり, 遺伝子構造が変わらないのに対し, GPにおける交叉では, 図5.8 に示す通り, 交差点によって生成される個体の遺伝 子が変化してしまうのである.