遺伝的プログラミング解説：機械が自らコードを書く仕組み

機械が自らプログラムを書く日が来れば、コンピュータサイエンスの「聖杯」が発見されたことになるでしょう。遺伝的プログラミング（GP）は、その方向への一歩を示す比較的新しい機械学習パラダイムです。GPは制御工学の領域で大きな可能性を秘めています。本記事では、遺伝的プログラミングとは何か、どう表現されるか、サンプルプログラムを見ていきます。

この記事はシリーズの第一弾です。次回以降へジャンプするには、以下から選択してください：

• 進化的アルゴリズムにおける遺伝的演算子
• 遺伝的アルゴリズムの例：ソートプログラムとシンボリック回帰の進化
• 遺伝的プログラミングの応用と限界

遺伝的プログラミングと遺伝的アルゴリズム

GPは、John Hollandによって本来考案された遺伝的アルゴリズム（GA）の一種です。GAと同様、GPは適応度比例選択、クロスオーバー、突然変異といった遺伝的演算子に依存し、エンコードされたプログラム、すなわち「個体」の集団を連続する世代を通じて解へと導く進化的アルゴリズムです。

しかし、GAが通常固定長ビット列エンコーディングを使用するのに対し、GPは実際のプログラムの可変サイズ・木構造ベース表現を採用します。したがって、成功したGP実行の結果は、適切な入力を与えて実行したときに望ましい結果を生み出すコンピュータープログラムとなります。

Nichael CramerとJohn KozaがGPの基礎を築いたとされています。John Koza（GPの特許も保持）はGPに関する重要な研究を行い、その画期的な著書『Genetic Programming』はこの分野のセミナルワーク（開拓的著作）と見なされています。現在の研究では、ロボットナビゲーション、ゲーム戦略獲得、シンボリック回帰分析、制御システムなど幅広い応用でGPの前向きな成功が示されています。

遺伝的プログラミングの表現

前述の木構造ベース表現はGPのテーマの中心であり、事実上あらゆるコンピュータープログラムをこの形式で表現可能です。実践では、LISPのような関数型言語がこの形式に適しており、LISPのS式がいかに木構造として図示できるかは容易に理解できます（図1）。

以下に、同一情報の3つの異なる表現を示します：

シンプルなプログラム断片：
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;
END


LISP相当：
(progn (if (a < b)
    (setq a (+ a 1))
    (setq b (* b b))
  )
  (setq c (* (* a b) 2))
)

木の内部ノードは関数で構成され、葉ノードは端子（ターミナル）で構成されます。関数は少なくとも1つの引数数（アリティ）を持たなければならず、他の関数や端子と接続可能で、木内の枝の「接着剤」となります。

端子には通常、定数と変数が含まれます。端子は木の葉を形成するため、アリティは常にゼロです。解決しようとしている問題に適した関数セットと端子セットを選択する必要があります。例えば、論理関数AND、OR、NOTと、2つのブール入力変数を表す端子X1、X2は、XORブール関数を合成できるプログラムを発見しようとする場合に適しています。また、適合度関数も必要です。あるプログラムが別のプログラムよりも与えられた問題の解決に優れているかを測定する手段を提供しなければならないからです。

例えばXORの場合、X1とX2の4つの可能なブール入力（0 0、0 1、1 0、1 1）それぞれに対応する適合度ケースでプログラムを1回ずつ実行し、正解数（それぞれ0、1、1、0）を合計することでプログラムの適合度をテストできます。満点の4点を獲得したプログラムは、リスト1に示すようにXOR問題の解と見なされます。

GPが発見したXOR問題の完璧な解：
(defun program ()
  (AND (OR X1 X2)
       (NOT (AND X1 X2))
  )
)

次回：遺伝的演算子

次回の記事では、進化的アルゴリズムを可能にする遺伝的演算子を見ていきます。また、より複雑なアルゴリズム例でそれらを使用します。

推奨文献

• Kinnear, Jr., K. E. (ed.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass.: Addison-Wesley, 1973
• Koza, J. R. Genetic Programming. Cambridge, Mass.: The MIT Press, 1992.
• Koza, J. R. Genetic Programming II. Cambridge, Mass.: The MIT Press, 1994.
• Montana, D. J. "Strongly Typed Genetic Programming." BBN Technical Report #7866, May 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.