忍者ブログ
MASTER →  ADMIN / NEW ENTRY / COMMENT
現代魔法(nearly equal 情報技術)を勉強中な人のメモ(チラシの裏)
/ 2017/10/18 (Wed) / 編集
×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

/ 2008/05/04 (Sun) / 編集
[wikipedia]遺伝的プログラミングと『複雑系のシミュレーション』より

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

S式の例

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

木構造は以下のようになる。 program_A S式
ここで、
  • 「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) ) を作る LISPのS式の交叉
(ちなみにGAでは「突然変異(Mutation)」と「交叉(Crossover)」の2つ)

進化させる

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

拍手[0回]

PR
忍者ブログ [PR]