Category: ALife GA
Comment: これは「遺伝子アルゴリズム(GA)を使ってLISPプログラムを
        進化させる」というもので、Koza氏はずっとこの手の話をやっ
        ています。昨年のICGA(International Conference on
        Genetic Algorithms)の講演では「お掃除ロボット」を作っ
        たと言っていましたし\cite{Koza:RandomNumberByGA}のよう
        な発表をしていましたが、これも似たような話です。
        普通のGAでは解を1次元の文字列に写像してそれらの間で交
        配/突然変異処理行ないますが、ここではLispの構文木を``
        染色体''として用い、ふたつの構文木の部分木を交換する操
        作を交配処理としています。構文木のノードには\verb+if+
        文や演算子、関数などが入ります。
        この論文では3種類の問題に対するプログラムの進化につい
        て書かれています。
        紹介されているプログラムとその適用結果は以下のとおりで
        す。
        \begin{enumerate}
        \item 平面上の点をたどる問題
        32$\times$32の桝目の中に89個の点があり、これを順番にた
        どっていくプログラムを生成します。構文木の内部ノードと
        しては\verb+if-sensor+ (前方に点が存在するか調べる関数)
        と \verb+progn+を使い、葉として\verb+advance+ (前方に
        進む関数)\verb+turn-left+ (左を向く関数)
        \verb+turn-right+ (右を向く関数)の3個を使用します。こ
        れらを使ってランダムな構文木を作り、そのプログラムを実
        行させ、その評価値により構文木を進化させることにより最
        終的に正しく点をたどるプログラムが生成されます。
        \item 「蟻」のシミュレーション
        桝目の中に「巣」と「食物」があり、巣の中に20匹の蟻がい
        ます。今回は蟻のプログラム要素として「前進」、「回転」
        などの他に「フェロモンを出す」「フェロモンをたどる」な
        どの関数を加えてあり、最初に餌を発見した蟻に続いて他の
        蟻が協調して巣まで餌をはこびこむというプログラムを作ら
        せています。
        \item 対戦プログラム
        最近の進化論では「共生進化説」が力をのばしていますが、
        ここではGAの評価関数として「相手に対する自分の評価」を
        使うことにより共生進化をGAでシミュレーションし、対戦ゲー
        ムのプログラムを作りだすことを試みています。結果として、
        ミニマックス法によるものと同等のプログラムが自動的に生
        成されたということです。
        \end{enumerate}
        本当にいろいろなプログラムが自動的に作られるのか、とい
        うことは非常に疑問ではありますが、ある程度でも自動的に
        プログラムができてしまうということはなかなか面白いので
        はないかと思っています。
Bibtype: InBook
Pages: 603-629
Author: John R. Koza
Booktitle: Artificial Life II
Series: Santa Fe Institute Studies in the Sciences of
        Complexity
Editor: Christopher G. Langton
        Charles Taylor
        J. Doyne Farmer
        Steen Rasmussen
Title: Genetic Evolution and Co-Evolution of Computer Programs
Year: 1991
Volume: X
Publisher: Addison-Wesley