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

はじめに

進化は何らかの組織がまわりの条件を克服して，いくらかでも優位を保とうとするしくみと考えられます。生物は途方もない時間をかけて，この魅力的なメカニズムを利用し，自らを改良させてきました。このようなメカニズムは，生物の進化だけではなく脳内における意識の形成［Calvin 96］などにも存在しているようです。生物進化の担い手は遺伝子で，生物の設計図といわれてきましたが，生物の隅々まで遺伝子に細かく書き込まれているわけではなく，常に外界との相互作用で形成される場に従っていることがわかってきています。
　
このような進化のメカニズムをコンピュータ利用の情報処理に応用したのが遺伝的アルゴリズムであり遺伝的プログラミングなのです。コンピュータの中では個体の成長期間を無視し，実際の進化スピードを極端に切りつめて，遺伝子の変化とその評価を中心に行っています。これにより，進化のメカニズムを最適化問題などに応用しているわけです。つまり冒頭に記したように，制約条件を「克服する条件」として扱い，「いくらかでも優位を保とうとするしくみ」が最適性へのベクトルを生み出すことになります。
　
本書は，欲張って，オブジェクト指向と遺伝的アルゴリズムと遺伝的プログラミングという3つをテーマにしています。しかし単に欲張っただけではありません。遺伝的アルゴリズムと遺伝的プログラミングは，ともに進化のメカニズムを利用した最適解を求める方法であり，似ている部分が多いのです。名前からして，それは簡単にわかることでもあります。しかし，これらとオブジェクト指向とは，どう関係するのか。オブジェクト指向とは，システム開発における救世主として20年も前に出現した考え方であり，オブジェクト指向言語として具現化したのです。ただ，オブジェクト指向においても，当初喧伝されてきたような再利用性の高さ，拡張の容易さについては，必ずしも期待どおりとはなりませんでした。しかしながら20年の間に考え方が進み，今では，随分と改善されているのです。その1つが，本書で取り上げているフレームワークというシステムの構成法です。このオブジェクト指向におけるフレームワークという考え方は，特定のドメインにおけるシステムを構築するための有力な方法となっています。特定のドメインを仮定すると，システムの基本となる部分が共通に括り出せ，ドメイン内における個別の機能要求が，基本部分に付加される構造となります。これを，容易に実現する枠組みがフレームワークと呼ばれるものです。
　
遺伝的アルゴリズムと遺伝的プログラミングとは，ともに進化のしくみを使って何らかの最適化を行う手法です。それら2つの間の共通性までは求めずに，それぞれの領域を分けて考えると，さらに動きを含めて基本的な部分が拡大します。その多くは，それぞれの領域でのアプリケーションに共通的な考え方となっていますから，その共通的な部分をフレームワークとして構成しておくと，それぞれ，各種のアプリケーションに適用する場合，アプリケーションに固有な部分だけを拡張することで対処できるようになります。つまり，核となる部分を固めておき，アプリケーション固有部分を追加できるようにしておくことにより，遺伝的アルゴリズムと遺伝的プログラミングを適用するアプリケーションの開発効率を大きく向上させることができます。オブジェクト指向を用いるまでもなく，共通部分ならば共通部品として作っておけば，上述のことは可能ではあります。しかしながら，拡張しても，フレームワーク部分への変更が一切及ばないとしたら別です。オブジェクト指向が提供するしくみは，それを可能にしているのです。さらに，単なる共通部品ではなく，それだけでも遺伝的アルゴリズムと遺伝的プログラミングのシステムとして動かすことができます。もちろん，アプリケーション部を正式には定義していませんので，動きを観察できるだけですが。
　
以上のようなフレームワークを準備しておくと，何らかの課題を解決しようとするとき，新たにプログラムを作成する部分は，従来の30〜50％ほどですみます。それもその課題固有の部分だけですので，問題解決に注力できるわけです。
　
さて，遺伝的アルゴリズムと遺伝的プログラミングのしくみ部分は，フレームワークに任せるとして，これら2つの違いについて知っておくべきでしょう。両者とも，ダーウィンの進化論を基礎においている点では共通です。ともに，集団進化の効果を狙っているわけです。遺伝的アルゴリズムは，個体が持つ遺伝子とそれが配列であるということを利用して，適用する問題の特徴値をそれらに表現させます。その個体が進化することで探索や最適解を求めます。一方，遺伝的プログラミングは，個体の遺伝子にプログラムの断片（正確には関数）を表現し，遺伝子の配列である染色体で目的の機能を果たせるプログラムを表現します。遺伝的アルゴリズムが解そのものを進化させることに対して，遺伝的プログラミングは機能を進化させることになるわけです。
　
遺伝的プログラミングでは，進化の方向を決めるために事例を用います。つまり学習システムでは一般に教師データと呼んでいて，入力とそれに対してシステムが応答すべき出力を組にしたものです。入力と正しい応答の組を正事例，誤った応答の組を負事例と呼んでいますが，本書の遺伝的プログラミングでは正事例を扱っています。このような教師データを充分な数用意して，進化という学習を行わせて，すべての教師データを上手く説明できるようなプログラムを生み出すようにします。つまり，帰納的推論を行っていることになるわけです。
　
ただ何の指針もなく帰納的推論を行うことは困難でしょう。述語論理の世界で，同様に正事例から，それを説明可能な述語を合成する研究があります［shapiro82］。しかしながら，合成すべき述語の引数の数や，それがアトムなのかリストなのかといったタイプに，何の制限も与えることなく，帰納することはできません。そこでも，それらはあらかじめプロトタイプとして与えています。
　
遺伝的プログラミングでは，目的の関数を構成する基本的な関数の集合を与えています。それらの関数の働きは，当然ながら正確に規定されています。そのような関数を組み合わせて目的の関数を合成していきます。ここで注意しておかなければならないのは，手続型のプログラミング言語表現でプログラムを合成するのではなく，LISPなどの純粋な関数型として表現するということです。関数型言語の特色は，手続型の代入文や条件文などの制御構造もすべて関数化されています。この特徴が，プログラム合成を容易にしています。遺伝的プログラミングでは，LISPをその処理系として用いている場合が多いのも，そのような理由からです。しかしながら，本書では，C++を処理系として用い，合成対象のプログラム表現にLISP流の形式を用いることにしています。
　
プログラムは，個体の染色体がその構造を表現しています。つまり個体がプログラムを作っているわけですから，遺伝子表現には，プログラムの表記レベルのイメージを持たせる必要はまったくありません。いいかえると，コンパイラはソースプログラムを解析して内部表現に変換していますが，その変換後の表現を遺伝子に表現させて，そのレベルで遺伝的操作を施せばいいわけです。つまり，遺伝的プログラミングの処理中は，内部表現のままで進化を行わせることができるわけです。人間が見てわかるような表層レベルの表現は，必要になったとき変換してやればいいわけです。
　
遺伝的アルゴリズムに関しては，『応用事例でわかる遺伝的アルゴリズムプログラミング』を同じくパーソナルメディア社から出版しております。本書はその内容と重ならないように工夫しています。したがって，遺伝的アルゴリズムの基礎については，前著を参照していただけると幸いです。






戻る