遺伝的アルゴリズムのアプリケーションと制限

遺伝的プログラミング（GP）シリーズのこの時点で、遺伝的プログラミングとは何か、それが情報をどのように表すか、進化的アルゴリズムで遺伝的演算子がどのように機能するかを学び、シンボリック回帰によるソートプログラムの進化に取り組みました。

ここでは、このテクノロジーが開発中に何を達成できるかを大まかに見ていきます。

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

シリーズのこの最後の章を理解するために、このシリーズの最初の部分で説明したXORの例を思い出してみましょう。

  GPによって発見されたXOR問題の完璧な解決策： （defunプログラム（） （AND（またはX1 X2） （NOT（およびX1 X2）） ）。 ）。 

リスト1。 XOR結果。

前の記事のシンボリック回帰の例も振り返ってみましょう：

区間（0 <=x <=pi / 2）でのsin（x）の多項式近似 （defunプログラム（） （+（*（*（* X X）X） （* 0.2283 -0.6535）） バツ） ）。 上記のプログラムを単純化すると、次の同等の方程式が得られます。 polysin（x）=-.1492 x 
 3 
 + 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

リスト4。 シンボリック回帰。

ここに示されているXORとシンボリック回帰の例はどちらも、評価時に単一の値を返すことに注意してください。

関数または端末が実行時に副作用を起こす可能性があるため、この特性を制限する必要はありません。これは、ベクトル内の要素のペアを交換するという潜在的な副作用を伴う関数を含むソートプログラムの場合によくあります。実際には、副作用が存在するのが一般的です。有用な副作用のいくつかの追加の例は、ある変数を別の変数に割り当てたり、ロボットが向いている方向を変更したりすることです。

私たちの関数セットには、進化したプログラムに意思決定機能を提供する条件関数が含まれている場合があります。条件関数は、引数を選択的に評価します。例として、（arg1 arg2 arg3の場合）のように、アリティが3の関数を考えてみます。関数は最初の引数を評価することによって評価され、結果がtrueの場合、2番目の引数が評価されます。それ以外の場合は、3番目の引数が評価されます。関数が引数の1つを複数回評価する可能性があるため、反復構文も可能です。ただし、個人の評価に非常に長い時間がかかる状況を回避するために、反復回数とネストレベルを制限する必要があるため、さらに複雑になります。この分野での成功はやや制限されていますが、再帰的な定式化を可能にするためにいくつかの作業が行われています。

GPシステムの結果はLISPのようなプログラムになる傾向がありますが、GPシステムをLISPに実装する必要はありません。多くのシステムはCまたはC ++で実装されています。プログラムツリーの線形化された表現を使用でき、高価なガベージコレクションに伴う動的メモリのオーバーヘッドを回避できます。適応度関数の効率は、世代ごとに何度も呼び出されるため、ボトルネックになることが多いため、特別な注意が必要です。さまざまな実装手法について説明している優れた論文は、 GeneticProgrammingの進歩にあります。 （以下の推奨読書セクションで引用）

ニューラルネットワークなどの他の機械学習パラダイムと同様に、トレーニングデータ（GPテストケース）を過剰適合させる可能性があります。ソリューションがデータを効果的に「記憶」する場合、過剰適合が発生する可能性があります。そのため、複雑なルックアップテーブルしか提供されません。この影響を減らすのに役立つ簡単な方法の1つは、節約係数を使用することです。節約係数は通常、プログラムツリー内のノード数を掛けた小さな部分であり、その結果が適応度関数に組み込まれます。アイデアは、より小さく、おそらくより一般的なソリューションに報酬を与えることです。さらに、適切な実験計画手法を使用することをお勧めします。たとえば、予測用のモデルを開発しようとしている場合は、適合性評価を利用可能なデータのサブセットに制限することをお勧めします。このようにして、残りのデータで結果のモデルの予測パフォーマンスを測定できます。

進化的アルゴリズムの場合と同様に、GPは、正確なソリューションまたは許容可能なソリューションを見つけることを保証しません。結果は、実行ごとに大きく異なる場合があります。多くの場合、プロセスは時期尚早に極小値に収束します。パフォーマンスは、問題の複雑さ、関数と端末の選択によって特徴付けられるその表現、および適応度関数のプロパティに大きく依存します。

遺伝子プログラミングのアプリケーション

遺伝的プログラミングは、次のような分野で発生する問題にうまく適用されています：

• 回路設計
• 組み合わせ最適化
• 制御システム
• カーブフィッティング/回帰分析
• データ圧縮
• 経済予測/財務モデリング
• ゲーム戦略の獲得
• 数学的シーケンス誘導
• ニューラルネットワークの設計
• パターン認識と分類
• 乱数の生成
• ロボットナビゲーション
• 記号積分と微分
• 3次元デザイン

遺伝子プログラミングの今後の方向性

問題の複雑さによっては、許容できる解決策が見つかったとしても、それを見つけるために数回のGP実行が必要になる場合があります。理想的には、問題の複雑さが増すにつれて、GPが「スケールアップ」することを望んでいます。この目標を達成するための良い方法を見つけることは、活発な研究分野です。従来のプログラミングと同様に、サブルーチンを介して高レベルの表現を構築するという概念は、この問題に取り組む1つの方法です。 遺伝的プログラミングII 、Kozaは、再利用可能なサブルーチンを検出できるメソッドについて説明し、より複雑な問題を解決するための階層型モジュラープログラムの機能をサポートする結果を示します。

これまで見てきたように、GPは、遺伝的アルゴリズムの自己組織化特性を、S式の表現力と一般性と結び付けます。このアプローチの優雅さは、問題の仕様を、ドメイン固有の適応度関数と適切な関数および端末セットを提供するものに単純化します。さまざまな問題に適用できるGPは、引き続き研究のための肥沃な土地です。

まだ揺籃期にありますが、将来のブレークスルーにより、独自のプログラムを作成できるシステムの聖杯にさらに一歩進む可能性があります。

推奨読書

• Kinnear、Jr.、K。E.（ed。） 遺伝子プログラミングの進歩 。マサチューセッツ州ケンブリッジ：MIT Press、1994年。
• Knuth、D。E. The Art of Computer Programming、Volume 3、Sorting and Searching 。マサチューセッツ州レディング：アディソン-ウェスリー、1973年
• Koza、J。R. 遺伝的プログラミング 。マサチューセッツ州ケンブリッジ：MIT Press、1992年。
• Koza、J。R. Genetic Programming II 。マサチューセッツ州ケンブリッジ：MIT Press、1994年。
• モンタナ、D。J。「強く型付けされた遺伝的プログラミング」。 BBNテクニカルレポート＃7866、1993年5月。
• ミッチェル、メラニー、遺伝的アルゴリズムの紹介 、MIT Press、1998年。