遺伝的アルゴリズムの力と限界を探る

この遺伝的プログラミング（GP）シリーズでは、GPの概念と情報表現、進化的アルゴリズムにおける遺伝的演算子の働き、シンボリック回帰によるソートプログラムの進化について学んできました。ここでは、この技術が発展するにつれて何が達成可能になるか、ハイレベルな視点から概観します。

遺伝的プログラミングの実践的考慮事項

このシリーズ最終章を理解するため、第1回で扱ったXORの例を思い出してみましょう：

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

前回の記事でのシンボリック回帰の例も振り返ります：

区間 (0 ≤ x ≤ π/2) における sin(x) の多項式近似

(defun program ()
  (+ (* (* (* X X) X)
        (* 0.2283 -0.6535))
     X)
)

上記プログラムを簡略化すると、以下の等価な式が得られます：

polysin(x) = -0.1492 x³ + x

結果：

x	sin(x)	polysin(x)
0.000	0.000	0.000
0.078	0.077	0.077
0.156	0.155	0.155
0.234	0.231	0.232
0.312	0.306	0.307
0.390	0.380	0.381
0.468	0.451	0.452
0.546	0.519	0.521
0.624	0.584	0.587
0.702	0.645	0.650
0.780	0.703	0.709
0.858	0.756	0.763
0.936	0.805	0.813
1.014	0.848	0.858
1.092	0.887	0.897
1.170	0.920	0.931
1.248	0.948	0.957
1.326	0.970	0.978
1.404	0.986	0.991
1.482	0.996	0.996
1.560	0.999	0.993

XORとシンボリック回帰の両例とも、評価時に単一の値を返すことに注目してください。しかし、この特性が制約になるわけではありません。関数や端子が実行時に副作用を持つことは十分あり得ます。ソートプログラムのように、ベクトル内の要素ペアを交換する副作用を持つ関数を含むケースが典型的です。実際には副作用の存在が一般的です。変数への代入や、ロボットの向き変更なども有用な副作用の例です。

関数セットには条件分岐関数を含め、進化したプログラムに意思決定能力を持たせられます。条件関数は引数を選択的に評価します。例えば、アリティ（引数の数）が3の関数 (if arg1 arg2 arg3) を考えます。第1引数を評価し、真なら第2引数を、偽なら第3引数を評価します。反復構造も可能で、関数が引数の一つを複数回評価することもできます。ただし、反復回数とネストレベルを制限し、個体の評価に過度な時間がかからないようにする必要があります。再帰的定式化を許容する研究もありますが、成功は限定的です。

GPシステムの結果はLISP風のプログラムになりがちですが、GPシステム自体をLISPで実装する必要はありません。多くのシステムはCやC++で実装されています。プログラム木の線形化表現を用いれば、動的メモリのオーバーヘッドや高コストなガベージコレクションを回避できます。適合度関数の効率には特別な注意が必要です。各世代で何度も呼び出されるため、ボトルネックになりやすいからです。実装技術について詳しくは『Advances in Genetic Programming』（推奨文献を参照）の論文が参考になります。

ニューラルネットワークなど他の機械学習パラダイムと同様、GPテストケースである訓練データへの過学習（オーバーフィッティング）の可能性があります。過学習は、解がデータを効果的に「暗記」してしまい、精巧なルックアップテーブル以上のものにならない場合に発生します。これを抑制する簡単な方法の一つが、節約係数（parsimony factor）の使用です。節約係数は通常、プログラム木のノード数に掛ける小さな係数で、その結果を適合度関数に組み込みます。より小さく、おそらくより汎用的な解を報奨する狙いがあります。また、適切な実験計画法の採用も推奨します。例えば予測モデルを開発する場合、適合度評価を利用可能データのサブセットに制限し、残りのデータで結果モデルの予測性能を測定すると良いでしょう。

進化的アルゴリズムと同様、GPは厳密な解、あるいは許容可能な解を見つける保証はありません。実行ごとに結果が大きく異なることがあり、しばしば局所的最小値に早期収束します。性能は問題の複雑さ、関数と端子の選択による表現、適合度関数の特性に大きく依存します。

遺伝的プログラミングの応用分野

遺伝的プログラミングは、以下のような領域で発生する問題に成功裏に適用されてきました：

• 回路設計
• 組み合わせ最適化
• 制御システム
• 曲線フィッティング／回帰分析
• データ圧縮
• 経済予測／金融モデリング
• ゲーム戦略の獲得
• 数列の数学的帰納
• ニューラルネットワーク設計
• パターン認識と分類
• 乱数生成
• ロボットナビゲーション
• 象徴的積分と微分
• 三次元設計

遺伝的プログラミングの将来の方向性

問題の複雑さに応じて、許容可能な解を見つけるには複数回のGP実行が必要になる場合があります。理想的には、問題の複雑さが増してもGPが「スケールアップ」して対応できることが望まれます。これを達成する良い方法を見つけることは、活発な研究領域です。従来のプログラミングと同様に、サブルーチンを通じて高レベル表現を構築するアプローチが一つの方向性です。『Genetic Programming II』でKozaは、再利用可能なサブルーチンを発見する手法を論じ、階層的・モジュール化されたプログラムがより複雑な問題を解決できることを示す結果を提示しています。

GPは、遺伝的アルゴリズムの自己組織化特性と、S式の表現力・一般性を結合させたものです。このアプローチの優雅さは、問題仕様を「ドメイン固有の適合度関数と適切な関数・端子セットの提供」に簡素化する点にあります。多様な問題に適用可能なGPは、研究の肥沃な分野であり続けています。

まだ発展途上の段階ですが、将来のブレークスルーにより、自らプログラムを作成できるシステムという「聖杯」へ一歩近づくかもしれません。

推奨文献

• 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.