nDiki

2004年7月5日 (月)

Perl遺伝的プログラミング

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

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

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

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

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

スポンサード リンク
[ 7月5日全て ]

About Me

Naney Naney (なにい)です。株式会社ミクシィで SNS 事業の部長をしています。

nDiki1999年1月に始めたコンピュータ日誌を前身とする NaneyWeb 日記(兼パーソナルナレッジベース)です。ちょっとしたノートは nNote にあります。

※内容は個人的見解であり所属組織とは関係ありません。

月別インデックス
Process Time: 0.111386s / load averages: 0.74, 0.37, 0.32
nDiki by WATANABE Yoshimasa (Naney)
Powered by DiKicker