遺伝的プログラミング(GP)

[wikipedia]遺伝的プログラミングと『複雑系のシミュレーション』より

遺伝的プログラミング(GP)は遺伝的アルゴリズム(GA)の拡張で木構造（LispのS式表現で表記するのが慣例）を用いる。

S式の例

例えば以下のような「xをインクリメントしたあとにxに2を代入し、その後xを出力してxを返す」というプログラムだと

木構造は以下のようになる。
ここで、

• 「program_A」や「x」「2」などの各文字を『ノード』という。
• 「program_A」のことを『ルート』という
• 「x」や「2」などの端っこにあるノードを『終端ノード／終端記号／葉』という。
• 「program_A」「set」「print」などの終端記号でないノードを『非終端ノード／非終端記号／LispのS式の関数記号』という。
• 自ノードの直下に直接つながっているノードを『子供／引数／LispのS式のアトム』という。（「set」の引数は「x」と「2」）
• 自ノードに上につながっているノードを『親』という。（「set」の親は「program_A」）

これをLispのS式で表すと
(program_A (increment x) (set x 2) (print x) )
になる。
このS式をGAのようにして進化させてゆくのがGP。

GPのオペレータ

GPオペレータは以下の3つ

• 突然変異(Gmutation)：ノードのラベルの変更
ex) (+xy) -> (+xz)
• 逆位(Ginversion)：兄弟の入れ替え
ex) (program_A (increment x) (set x 2) (print x) ) -> (program_A (set x 2) (increment x) (print x) )
• 交叉(Gcrossover)：複数のS式間で部分木(木の一部)の入れ替え
ex) (program_A (increment x) (set x 2) (print x) )　と (program_B (/x2) (* x 2) (print x) )　を交叉して (program_A (/x2) (set x 2) (print x) ) と (program_B (increment x) (* x 2) (print x) ) を作る

(ちなみにGAでは「突然変異(Mutation)」と「交叉(Crossover)」の2つ)

進化させる

オペレータが3つなのと構造（式）を操作すること以外は通常のGAと同じように「パラメータ(突然変異率や交叉率など)」をもとに各式に対してオペレータを実行し、「適応度」をもとに「選択」を行い次の世代を作るという作業を「終了条件」に達するまで繰り返す。