Just $ A sandbox

プログラミングと計算機科学とかわいさ

0.Haskellで遺伝的プログラミング

Haskell遺伝的プログラミングを組んでみることにしました。
そもそも「論理式は解の個数と判定時間が性質を与えているに違いない!*1」「プログラム的な手法(つまりはアルゴリズム)は多くの場合は限定論理式で書けるのではないか」「ではプログラムは自己組織化するのか?*2」という発想からこのようなプロジェクトを立ち上げてみました。
プログラムが自己組織化可能かどうかを、より単純なモデルから探っていこうという考え方です。

大まかなアルゴリズム

  1. まず、論理式がたくさん書かれたファイルを読み込みます
  2. それらを解析します
  3. 解析した論理式を遺伝子とみなして「交叉」「突然変異」をさせます
  4. 一定時間ごとに「自然淘汰」を加えます
  5. 残ったものをファイルに書き出します
  6. はじめに戻る

設計

本当はプログラムをそのまま読み込んで解析するインタープリターを作れば良いのですがそれは複雑すぎるのでやめました。代わりにPA(ペアノ算術)で扱える範囲の限定論理式のみを解析の対象とします。つまり、四則演算及び(範囲付きの)∃∀のみからなる論理式を解析したいと思います。

発展性

最終的には論理式だけでなくてもう少し一般的な遺伝子(プログラムのようなもの)を解析できるようになれば、もう少し「生命の複雑さを量る」ということができるようになるのかもしれませんね(希望的観測)。

*1:論理式とはここでは限定論理式のことで、例えば  は、解の個数は5個、判定時間は最大100ループなので100k(k:比例定数)のように考えています

*2:生命と呼べるような、増殖や進化といった組織を作り出すことができるか、くらいの意味です