遺伝的プログラミング入門：それ自体をプログラムするシステム？

おそらく、コンピュータサイエンスの「聖杯」は、私たちのマシンが独自のプログラムを作成できる日に発見されるでしょう。遺伝的プログラミング（GP）は、その方向への一歩を表す比較的新しい機械学習パラダイムです。

GPは、制御工学の分野で大きな期待を抱いています。この記事では、遺伝的プログラミングとは何か、それをどのように表現できるかについて説明し、プログラムの例を見ていきます。

この記事はシリーズの最初の記事です。次のエントリにジャンプするには、以下から1つ選択してください：

• 進化的アルゴリズムの遺伝演算子
• 遺伝的アルゴリズムの例：ソートプログラムとシンボリック回帰の進化
• 遺伝的プログラミングのアプリケーションと制限

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

GPは本質的に、ジョン・ホランドによって最初に考案された遺伝的アルゴリズム（GA）のバリエーションです。 GAと同様に、GPは、適応度に比例した繁殖、交叉、突然変異などの遺伝的演算子に依存する進化的アルゴリズムであり、コード化されたプログラムの母集団、つまり「個人」を、世代を超えて解決に向けて推進します。

ただし、通常は固定長のビット文字列エンコーディングを使用するGAとは異なり、GPは実際のプログラムの可変サイズのツリーベースの表現を採用しています。したがって、GPの実行が成功すると、コンピュータプログラムが生成され、適切な入力を与えて実行すると、目的の結果が得られます。

NichaelCramerとJohnKozaは、GPの基礎を築いたことで知られています。ジョン・コーザ（GPの特許も取得）はGPについてかなりの量の研究を行っており、彼の画期的な本「遺伝的プログラミング」はこの主題に関する独創的な研究と見なされています。現在の研究では、ロボットナビゲーション、ゲーム戦略の取得、シンボリック回帰分析、制御システムなど、幅広いアプリケーションでGPのいくつかの有望な成功が実証されています。

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

事実上すべてのコンピュータプログラムがこのように表現される可能性があるため、前述のツリーベースの表現はGPテーマの中心です。実際には、LISPなどの関数型言語はこの形式に適していて、LISPのS式をツリーとして図式化する方法を簡単に確認できます（図1）。

以下に、同じ情報の3つの別々の表現を示します。

 単純なプログラムフラグメント： 始める IF a  LISPに相当するもの： （progn（if（a  

 
 

  
 
  図1。 プログラムのツリー表現。 （progn arg1 arg2 arg3 ... argn）は、各引数を順番に評価することに注意してください。  
 

 
 

 ツリーの内部ノードは関数で構成されていますが、リーフノードはターミナルで構成されています。関数は、少なくとも1つの引数カウント（一般にアリティと呼ばれる）を持っている必要があります。これにより、関数を他の関数または端末に接続できるようになり、ツリー内のブランチに「接着剤」が提供されます。
 

 端末には通常、定数や変数などが含まれます。端子は木の葉を形成するため、常にゼロのアリティを持ちます。解決しようとしている問題に対して、機能と端末のセットを選択する必要があります。たとえば、2つのブール入力変数を表す論理関数AND、OR、NOT、および端子X1とX2は、XORブール関数を合成できるプログラムを検出しようとする場合に適しています。あるプログラムが特定の問題の解決に優れているという意味で、あるプログラムを別のプログラムに対して測定する手段を提供する必要があるため、適応度関数も必要です。
 

 たとえば、XORの場合、X1とX2の4つの可能なブール入力（0 0、0 1、1 0、1 1）に対応する各フィットネスケースに対してプログラムを1回実行することにより、プログラムのフィットネスをテストできます。テストケースごとに、それぞれ正しい応答の数（0、1、1、0）を合計します。 
 

 明らかに、リスト1に示すように、完全なスコアが4になるプログラムは、XOR問題の解決策と見なされます。
 

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

 
 
次へ：遺伝演算子
 

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

 
 
推奨読書
 
 
 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年。
 
 

            

            

                
            

            

               流行語の評価：デジタルトランスフォーメーション         
                ファジー論理コントローラーを設計する方法