nDiki : 遺伝的アルゴリズム

Perl で遺伝的プログラミング

創発本(ソフトバンクパブリッシング)を読んでいたら、遺伝的プログラミングしてみたくなった。 余暇としてコードを書いてみる。 しかし遺伝的プログラミングも遺伝的アルゴリズムもきちんと学んだことがないのでかなり適当。もしかしてやっている事はGPではないかも。

• 終端記号集合を用意 ('1', ';', '+', 'if', ...)
• これらの列を遺伝子とする。
• ランダムに並べたものを、沢山用意。
• トークン列をjoin(' ')して、sub { } の中にいれて eval
• エラーが出なかったらパラメータを与えて実行。返り値をチェックして適応度を計算
• 選択 - 適応度の高いものを残すように
• 交叉 - ある遺伝子の前半と、ある遺伝子の後半をくっつける。長さはそれぞれランダム
• 突然変異 - 遺伝子の1つの終端記号をランダムに変更

'3' を返す関数とかは簡単にできあがる(sub { 1 + 1 + 1} など)。 max(a, b) に対応する関数を作ろうとしたら、これは今のところ駄目。

• eval (コンパイル) 成功したものの方が、失敗したものより適応度を高くするようにしていたため、交叉の長さをランダムにするとどんどん遺伝子が短くなる(長いものはほとんどコンパイルエラーになるので)
• '}' などの順序にによっては sub が閉じられてしまう。パターンによっては perl 自体がセグメンテーション例外で落ちてしまった。最低限 '{', '}' の対応があうように eval 前に '{', '}' を挿入するようにした。
• 遺伝子がちょっと長くなるとほとんど eval に失敗する。
• '<', '>' を終端記号集合に含めておくと、<$a> のようなものも生成してしまう事もあり危険。
• 無限ループ検出がないため、終端記号集合に for, while 等を入れられない。

やはり構文木を遺伝子にしないと駄目かな。