(57)【要約】【課題】  化学的遺伝アルゴリズムを適用して、プログラミングを可能とする化学的遺伝プログラミング装置を提供する。【解決手段】  ＣＰＵ１２０は、ＤＮＡの第２の部分からｔＲＮＡの転写処理を行うｔＲＮＡ転写処理部１２０１と、ＤＮＡの第３の部分とアミノアシルｔＲＮＡテーブルとに基づいて、アミノ酸の翻訳処理を行うアミノ酸翻訳処理部１２０２と、アミノ酸とｔＲＮＡとの反応処理を行ってアミノアシルｔＲＮＡテーブルを更新するためのアミノアシルｔＲＮＡ更新処理部１２０３と、アミノアシルｔＲＮＡテーブルとＤＮＡの第１の部分とに基づく翻訳により表現型ツリーを生成するための表現型ツリー生成処理部１２０５とを含むとともに、ＤＮＡに対して遺伝的処置を行う。【選択図】        図５
2005215786.tif 000002
【特許請求の範囲】
【請求項１】
各個体ごとの遺伝情報と、ルール番号とシンボルとの対を複数組含むトランスファー情報と、前記シンボルの書換の対応関係を含む書換情報と、前記トランスファー情報と前記書換情報とを組み合わせて得られる翻訳テーブルとを格納するための記憶手段を備え、
前記遺伝情報は、
表現型実体を生成するための前記ルール番号の系列を含む第１の情報と、
前記トランスファー情報を生成するための第２の情報と、
前記書換情報を生成するための前記ルール番号の系列を含む第３の情報とを含み、
前記第２の情報からの転写処理により前記トランスファー情報を生成する転写処理手段と、
前記第３情報と前記翻訳テーブルとに基づいた翻訳処理により、前記書換情報を生成するための第１の翻訳処理手段と、
前記書換情報と前記トランスファー情報とを組み合わせることで、前記翻訳テーブルを更新するための更新処理手段と、
前記第１の情報と前記翻訳テーブルとに基づいた翻訳処理により、前記表現型実体を生成するための表現型実体生成処理手段と、
前記表現型実体により表現される結果の所定の目標に対する適応度に応じて、前記個体の選択処理を行うための選択処理手段と、
前記遺伝情報に対する突然変異処理を行うための突然変異処理手段とを備える、化学的遺伝プログラミング装置。
【請求項２】
前記遺伝情報、前記トランスファー情報、前記書換情報の交叉処理を行うための交叉処理手段をさらに備える、請求項１記載の化学的遺伝プログラミング装置。
【請求項３】
前記シンボルは、
前記表現型実体により表現される結果を構成し、翻訳処理の終了を示す終端シンボルと、
継続して翻訳可能であることに対応する非終端シンボルとを含み、
前記書換情報は、
前記非終端シンボルのうちの１つから前記非終端シンボルのうちの少なくとも１つの他の非終端シンボルへの継続書換情報と、
前記非終端シンボルのうちの１つから前記終端シンボルのうちの１つへの終端書換情報とを含む、請求項１記載の化学的遺伝プログラミング装置。
【請求項４】
前記個体間で、前記トランスファー情報と、前記書換情報と、前記翻訳テーブルに含まれる情報とを交換する処理を行う交換処理手段をさらに備える、請求項１記載の化学的遺伝プログラミング装置。
【請求項５】
表現型実体を生成するためのルール番号の系列を含む第１の情報と、前記ルール番号とシンボルとの対を複数組有するトランスファー情報を生成するための第２の情報と、前記シンボルの書換の対応関係を有する書換情報を生成するための前記ルール番号の系列を含む第３の情報とを含む遺伝情報に基づいて、遺伝的プログラミングを行うための化学的遺伝プログラミング方法であって、
現在の世代の各個体ごとの前記遺伝情報と、前記書換情報と、前記トランスファー情報と、前記トランスファー情報と前記書換情報とを組み合わせて得られる翻訳テーブルとを記憶装置の記憶領域に格納する第１ステップと、
現在の世代の前記第２の情報からの転写処理により前記トランスファー情報を生成して前記記憶装置に格納する第２ステップと、
前記第３情報と前記翻訳テーブルとに基づいた翻訳処理により、前記書換情報を生成して前記記憶装置に格納する第３ステップと、
前記書換情報と前記トランスファー情報とを組み合わせることで、前記翻訳テーブルを更新する第４ステップと、
前記第１の情報と前記翻訳テーブルとに基づいた翻訳処理により、前記表現型実体を生成する第５ステップと、
前記表現型実体により表現される結果の所定の目標に対する適応度に応じて、前記個体の選択処理を行う第６ステップと、
前記遺伝情報に対する突然変異処理を行い、前記遺伝情報の交叉処理を行うことで、前記遺伝情報の世代を更新する第７ステップと、
前記第１から第７ステップを所定回数繰り返すステップとを備える、化学的遺伝プログラミング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、化学的遺伝アルゴリズムを用いた化学的遺伝プログラミング装置および化学的遺伝プログラミング方法に関する。
【背景技術】
【０００２】
生物細胞において、シンボルから機能への翻訳、すなわち、遺伝子型から表現型への翻訳は、ＤＮＡ（DeoxyriboNucleic Acid）によって決定されており、したがって、細胞が遺伝子の変更を受けると、このような翻訳プロセスも変更を受ける。ＤＮＡは、機能単位であるアミノ酸とトランスファーＲＮＡ（ｔＲＮＡ：transfer RiboNucleic Acid）とに翻訳される。翻訳されたアミノ酸とｔＲＮＡとは反応して、細胞の遺伝型の構造を決定するための翻訳テーブル、すなわち、アミノアシル−ｔＲＮＡを生成する。遺伝型を決定するコードの構造に関する情報とコードの翻訳のための情報とが、ともにＤＮＡに格納されているので、遺伝子の変異により、細胞は、その双方を進化させることができる。
【０００３】
（化学的遺伝アルゴリズム）
このような現実の生物細胞中の機構を真似ることで、新たな遺伝アルゴリズムである「化学的遺伝アルゴリズム（ＣＧＡ：Chemical Genetic Algorithms）」が提案されている（たとえば、非特許文献１および非特許文献２を参照）。
【０００４】
ＣＧＡは、遺伝子型の情報と表現型の情報との間に動的な関係を持ち込み、遺伝子型から表現型への翻訳過程を自律的に最適化していくことができる。
【０００５】
一般の遺伝的アルゴリズムにおいて、２進数で表わされるＤＮＡと最適化したい関数のパラメータとの間の対応関係を決める「コード化」は、アルゴリズムの性能を左右する最も大事な要因である。「化学的遺伝アルゴリズム」では、この決定関係を自律的に行なわせる。
【０００６】
このようなアルゴリズムは、最適化アルゴリズムとして使用することができる。最適化は、工学のさまざまな分野で最も要求度の高い処理の１つであり、化学的遺伝アルゴリズムは、生物類似にインテリジェント・システムを構築しようとするアプローチ方法の１つである。
【０００７】
人工的に設計された進化システムの進化性は、一群の基本機能ユニットによって決定される。実生物における基本機能ユニットは２０個のアミノ酸であり、ＤＮＡに書かれた遺伝情報は、上述した「アミノアシルｔＲＮＡ」と呼ばれる一群の分子によってアミノ酸に変換される。生物システムにおいては、アミノアシルｔＲＮＡが、ゲノタイプ（遺伝子型：ＤＮＡ上の塩基配列、遺伝コード）からフェノタイプ（表現型：たんぱく質の機能等）への対応関係を定義する基本的な分子である。
【０００８】
実生物の機能ユニットであるアミノ酸や、それへの変換分子であるアミノアシルｔＲＮＡを選び取る処理は、正にＤＮＡ／ＲＮＡに書かれたゲノタイプ（コード）の進化と一緒に行なわれたのであって、その意味で、コードとその変換テーブルは「同時進化」もしくは広い意味での「共進化」をしたといえる。
【０００９】
もしも、人工的な進化システムにおいても、コードと変換テーブルが共進化する仕組みを導入することができれば、進化実験をしながらシステムの進化性が自発的に高まるようにすることが可能となる。
【００１０】
「化学的遺伝アルゴリズム」では、遺伝的アルゴリズムを生物代謝系との類推で発展させた手法である。
【００１１】
通常の遺伝アルゴリズムでは、まず染色体集団が用意されて、それに突然変異・交叉などの遺伝的オペレーションが施されて処理が進む。しかしながら、「化学的遺伝アルゴリズム」（以下ＣＧＡ）では、まず、染色体ではなく細胞の集団が用意される。
【００１２】
細胞１個は、通常の染色体（ＤＮＡ）に加えて、アミノ酸、ｔＲＮＡ、アミノアシルｔＲＮＡという３つの種類の小分子集団を含んでおり、ＤＮＡ上の遺伝コードは、細胞内の転写・翻訳反応を通して実数値に変換され、適応度が計算される。
【００１３】
遺伝的オペレーションとしては、通常のＤＮＡ突然変異、ＤＮＡ交叉以外に、分子反応や細胞質交換も行なわれ、淘汰は、分子集団を含む細胞単位として行なわれる。
【００１４】
（遺伝的プログラミング）
一方で、遺伝的プログラミングが、様々な工学的応用に適用されている（たとえば、非特許文献３を参照）。
【００１５】
ランダムに生成された、所定のプログラミング構成要素からなるプログラムからスタートして、従来の遺伝的プログラミングは、遺伝的な操作を用いて各世代において最適なプログラムを、何世代にもわたって繁殖させていくことにより、その集団を進化させていく。
【非特許文献１】Suzuki, H., Sawai, H.: "Chemical genetic algorithms-Coevolution between codes and code translation." In: Standish, R.K., Bedau, M.A., Abbass, H.A. (eds.): Proceedings of the Eighth International Conference on Artificial Life(Artificial Life VIII)(2002) pp.162-172
【非特許文献２】Suzuki, H., Sawai, H., Piaseczny, W.: "Evolvability enhancement by the optimization of a chemical translation system-a case study." In: Dittrich, P., Kim, J.T.(eds.): The 7th European Conference on Artificial Life (ECAL) Workshop Proceedings (2002) pp.146-155
【非特許文献３】Koza, R.: 1992. Genetic Programming : On the programming of Computers by Means of Natural Selection. London: MIT press (1992).
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら上述したようなＣＧＡにおいては、関数パラメータの最適化の一手法については言及されているものの、これをプログラミングにどのように適用するのかについては明らかではないという問題点があった。
【００１７】
本発明の目的は、化学的遺伝アルゴリズムを適用して、プログラミングを可能とする化学的遺伝プログラミング装置および化学的遺伝プログラミング方法を提供することである。
【課題を解決するための手段】
【００１８】
この発明のある局面に従うと、各個体ごとの遺伝情報と、ルール番号とシンボルとの対を複数組含むトランスファー情報と、シンボルの書換の対応関係を含む書換情報と、トランスファー情報と書換情報とを組み合わせて得られる翻訳テーブルとを格納するための記憶手段を備え、遺伝情報は、表現型実体を生成するためのルール番号の系列を含む第１の情報と、トランスファー情報を生成するための第２の情報と、書換情報を生成するためのルール番号の系列を含む第３の情報とを含み、第２の情報からの転写処理によりトランスファー情報を生成する転写処理手段と、第３情報と翻訳テーブルとに基づいた翻訳処理により、書換情報を生成するための第１の翻訳処理手段と、書換情報とトランスファー情報とを組み合わせることで、翻訳テーブルを更新するための更新処理手段と、第１の情報と翻訳テーブルとに基づいた翻訳処理により、表現型実体を生成するための表現型実体生成処理手段と、表現型実体により表現される結果の所定の目標に対する適応度に応じて、個体の選択処理を行うための選択処理手段と、遺伝情報に対する突然変異処理を行うための突然変異処理手段とを備える。
【００１９】
好ましくは、化学的遺伝プログラミング装置は、遺伝情報、トランスファー情報、書換情報の交叉処理を行うための交叉処理手段をさらに備える。
【００２０】
好ましくは、シンボルは、表現型実体により表現される結果を構成し、翻訳処理の終了を示す終端シンボルと、継続して翻訳可能であることに対応する非終端シンボルとを含み、書換情報は、非終端シンボルのうちの１つから非終端シンボルのうちの少なくとも１つの他の非終端シンボルへの継続書換情報と、非終端シンボルのうちの１つから終端シンボルのうちの１つへの終端書換情報とを含む。
【００２１】
好ましくは、化学的遺伝プログラミング装置は、個体間で、トランスファー情報と、書換情報と、翻訳テーブルに含まれる情報とを交換する処理を行う交換処理手段をさらに備える。
【００２２】
この発明の他の局面に従うと、表現型実体を生成するためのルール番号の系列を含む第１の情報と、ルール番号とシンボルとの対を複数組有するトランスファー情報を生成するための第２の情報と、シンボルの書換の対応関係を有する書換情報を生成するためのルール番号の系列を含む第３の情報とを含む遺伝情報に基づいて、遺伝的プログラミングを行うための化学的遺伝プログラミング方法であって、現在の世代の各個体ごとの遺伝情報と、書換情報と、トランスファー情報と、トランスファー情報と書換情報とを組み合わせて得られる翻訳テーブルとを記憶装置の記憶領域に格納する第１ステップと、現在の世代の第２の情報からの転写処理によりトランスファー情報を生成して記憶装置に格納する第２ステップと、第３情報と翻訳テーブルとに基づいた翻訳処理により、書換情報を生成して記憶装置に格納する第３ステップと、書換情報とトランスファー情報とを組み合わせることで、翻訳テーブルを更新する第４ステップと、第１の情報と翻訳テーブルとに基づいた翻訳処理により、表現型実体を生成する第５ステップと、表現型実体により表現される結果の所定の目標に対する適応度に応じて、個体の選択処理を行う第６ステップと、遺伝情報に対する突然変異処理を行い、遺伝情報の交叉処理を行うことで、遺伝情報の世代を更新する第７ステップと、第１から第７ステップを所定回数繰り返すステップとを備える。
【発明の効果】
【００２３】
この発明にかかる化学的遺伝プログラミング装置および化学的遺伝プログラミング方法によれば、遺伝情報の翻訳テーブルを持ち、遺伝情報から作られたトランスファー情報および書換情報が新しい翻訳テーブルを生成するというフィードバック機構を備え、「コードと翻訳テーブルの共進化」を実現して、最適なプログラミング結果を短時間に得ることか可能である。
【発明を実施するための最良の形態】
【００２４】
以下、図面を参照して本発明の実施の形態について説明する。
【００２５】
（本発明のシステム構成）
図１は、本発明の化学的遺伝プログラミング装置１００の一例の外観を示す図である。
【００２６】
すなわち、図１に示した例では、化学的遺伝プログラミング装置１００は、一例として、汎用のコンピュータにより実現されるものとしている。
【００２７】
図１を参照して、この化学的遺伝プログラミング装置（コンピュータ）１００は、ＣＤ−ＲＯＭ（Compact Disc Read-Only Memory ）上の情報を読込むためのＣＤ−ＲＯＭドライブ１０８およびフレキシブルディスク（Flexible Disk、以下ＦＤ）１１６に情報を読み書きするためのＦＤドライブ１０６を備えたコンピュータ本体１０２と、コンピュータ本体１０２に接続された表示装置としてのディスプレイ１０４と、同じくコンピュータ本体１０２に接続された入力装置としてのキーボード１１０およびマウス１１２とを含む。
【００２８】
図２は、この化学的遺伝プログラミング装置１００のハードウェア構成をブロック図形式で示す図である。
【００２９】
図２に示されるように、この化学的遺伝プログラミング装置１００を構成するコンピュータ本体１０２は、ＣＤ−ＲＯＭドライブ１０８およびＦＤドライブ１０６に加えて、それぞれバスＢＳに接続されたＣＰＵ（Central Processing Unit ）１２０と、ＲＯＭ（Read Only Memory) およびＲＡＭ （Random Access Memory）を含むメモリ１２２と、直接アクセスメモリ装置、たとえば、ハードディスク１２４と、ネットワーク２００とデータの授受を行うための通信インタフェース１２８とを含んでいる。ＣＤ−ＲＯＭドライブ１０８にはＣＤ−ＲＯＭ１１８が装着される。ＦＤドライブ１０６にはＦＤ１１６が装着される。
【００３０】
なお、ＣＤ−ＲＯＭ１１８は、コンピュータ本体に対してインストールされるプログラム等の情報を記録可能な媒体であれば、他の媒体、たとえば、ＤＶＤ−ＲＯＭ（Digital Versatile Disc）やメモリカードなどでもよく、その場合は、コンピュータ本体１０２には、これらの媒体を読取ることが可能なドライブ装置が設けられる。
【００３１】
本発明の化学的遺伝プログラミング装置の主要部は、コンピュータハードウェアと、ＣＰＵ１２０により実行されるソフトウェアとにより構成される。一般的にこうしたソフトウェアはＣＤ−ＲＯＭ１１８、ＦＤ１１６等の記憶媒体に格納されて流通し、ＣＤ−ＲＯＭドライブ１０８またはＦＤドライブ１０６等により記憶媒体から読取られてハードディスク１２４に一旦格納される。または、当該装置がネットワークに接続されている場合には、ネットワーク上のサーバから一旦ハードディスク１２４にコピーされてもよい。そうしてさらにハードディスク１２４からメモリ１２２中のＲＡＭに読出されてＣＰＵ１２０により実行される。なお、ネットワーク接続されている場合には、ハードディスク１２４に格納することなくＲＡＭに直接ロードして実行するようにしてもよい。
【００３２】
図１および図２に示したコンピュータのハードウェア自体およびその動作原理は一般的なものである。したがって、本発明の最も本質的な部分は、ＦＤ１１６、ＣＤ−ＲＯＭ１１８、ハードディスク１２４等の記憶媒体に記憶されたソフトウェアである。
【００３３】
なお、一般的傾向として、コンピュータのオペレーティングシステムの一部として様々なプログラムモジュールを用意しておき、アプリケーションプログラムはこれらモジュールを所定の配列で必要な時に呼び出して処理を進める方式が一般的である。そうした場合、当該化学的遺伝プログラミング装置１００を実現するためのソフトウェア自体にはそうしたモジュールは含まれず、当該コンピュータでオペレーティングシステムと協働してはじめて化学的遺伝プログラミング装置１００が実現することになる。しかし、一般的なプラットフォームを使用する限り、そうしたモジュールを含ませたソフトウェアを流通させる必要はなく、それらモジュールを含まないソフトウェア自体およびそれらソフトウェアを記録した記録媒体（およびそれらソフトウェアがネットワーク上を流通する場合のデータ信号）が実施の形態を構成すると考えることができる。
【００３４】
（生物システムにおける転写・翻訳機構）
まず、本発明の化学的遺伝プログラミング装置の動作を説明する前提として、実際の生物細胞における代謝の機構について概説しておく。
【００３５】
図３は、このような実際の生物細胞における代謝の機構を説明するための概念図である。
【００３６】
図３を参照して、生物細胞における遺伝情報の翻訳は、一群の分子による代謝反応によって行なわれる。まず、生物は生合成反応により無機物からアミノ酸を作り出す。その主役となるのは植物が行なう光合成反応であり、この反応が作り出す糖を出発点とした解糖系の副産物としてのアミノ酸は合成される。また動物は、植物が合成したアミノ酸を摂取・消化することによってアミノ酸を獲得する。
【００３７】
一方、ＤＮＡが持つ遺伝情報は、大きく２つの流れをたどる。
【００３８】
まず１つは、ＤＮＡからポリメラーゼによる転写によって作られたｔＲＮＡがアミノ酸とカップリングしてアミノアシルｔＲＮＡを作る。ｔＲＮＡは、約８０個の塩基からなるポリヌクレオチドであり、細胞内では特殊なクローバ構造に折畳まれる。
【００３９】
その一方の端にはｍＲＮＡと相補的にマッチングするアンチコドンが、もう一方の端はアミノ酸とマッチングする認識部位が含まれており、ｔＲＮＡはこの特殊な構造から、コドンからアミノ酸へのアダプタとして働くことができる。
【００４０】
このｔＲＮＡをアミノ酸とカップリングする役目を果たすのがアミノアシルｔＲＮＡ合成酵素（アミノアシルｔＲＮＡシンセターゼ）と呼ばれる一群の酵素である。アミノアシルｔＲＮＡ合成酵素は、ｔＲＮＡクローバ構造に含まれるアミノ酸認識部位に取付き、それと照合するアミノ酸を見つけ出してはそれらを結合させる。各アミノ酸には１つずつ別のアミノアシルｔＲＮＡ合成酵素が用意されており、したがって細胞内では２０種類のアミノアシルｔＲＮＡ合成酵素が使われている。
【００４１】
ＤＮＡの遺伝情報がたどるもう１つの流れは、ＤＮＡからポリメラーゼによる転写によって作られたｍＲＮＡの翻訳である。ｍＲＮＡは、コドンの配列情報を保持した情報高分子であり、タンパク質のアミノ酸配列のもとになる。巨大タンパク質構造であるリボソームは、このｍＲＮＡの中に含まれるコドンを１つ１つ順番に読取っては、対合するアンチコドンを有するアミノアシルｔＲＮＡを見つけ出し、そこにカップリングしているアミノ酸を鎖状に結合していく。こうして得られたポリペプチド鎖（タンパク質）が、また酵素として細胞のさまざまな代謝反応を触媒する。
【００４２】
以上述べた生物遺伝情報の翻訳機構において、生物においては、ゲノタイプからフェノタイプへの対応関係（翻訳テーブル）が可変になっているということが特徴的である。生物では、コドン（ゲノタイプ・ユニット）とアミノ酸（フェノタイプ・ユニット）が直接結合した分子であるアミノアシルｔＲＮＡが翻訳テーブルを表わす。アミノアシルｋＲＮＡの生成は、ＤＮＡを転写したｔＲＮＡがもとになるから、生物における翻訳テーブルは、ＤＮＡ情報の改変によって変化し得る仕組みを持つ。
【００４３】
加えて、生物の翻訳機構が持つもう１つの重要な特徴は、代謝マップが一方向性のものではなく、フィードバックを含んでいるという点である。
【００４４】
すなわち、翻訳を含めた細胞内のすべての代謝反応は、酵素によって触媒されているが、それら酵素自体は代謝反応の産物であり、細胞内の各分子は複雑に相互依存している。特に、遺伝情報の翻訳については、アミノアシルｔＲＮＡを合成する酵素であるアミノアシルｔＲＮＡ合成酵素は、たんぱくとしてアミノアシルｔＲＮＡをコードしたコードの翻訳によってリボソームで合成されるから、コード（アミノアシルｔＲＮＡ合成酵素を表現するコドンシーケンス）と翻訳テーブル（アミノアシルｔＲＮＡ）が相互に依存しており、共進化する仕組みになっている。
【００４５】
（化学的遺伝プログラミング処理の概要）
以下では、このような実際の生物の代謝反応をモデル化した本発明にかかる「化学的遺伝プログラミング」の構成の概略について説明する。
【００４６】
（細胞内代謝反応）
図４は、化学的遺伝プログラミング処理の基本的な流れの概略を示す概念図である。
【００４７】
図４を参照して、まず、各々が次の４つの分子を内部に持つ複数の人工細胞（個体）を考える。すなわち、１個のＤＮＡ、Ｌ1個のｔＲＮＡ、Ｍ1個のアミノ酸、Ｒ1個のアミノアシルｔＲＮＡである。
【００４８】
これら人工の分子は、次のような代謝反応を毎世代行なう。
【００４９】
各ＤＮＡは、第１の部分、第２の部分、第３の部分を含んでいるものとする。
【００５０】
ＤＮＡの第１の部分は、後に説明するように化学的遺伝プログラミングにより生成される「表現型ツリー」の翻訳のための情報（ルール番号）を有する。
【００５１】
ＤＮＡの第２の部分は、ｔＲＮＡテーブルを転写により生成するための情報を含んでいる。この第２の部分は、ルール番号とシンボルとの対を複数組含む。ルール番号とシンボルとの対は、実際の生物におけるｔＲＮＡが、その一方の端にはｍＲＮＡと相補的にマッチングするアンチコドンを有し、もう一方の端はアミノ酸とマッチングする認識部位を有することをモデル化したことに相当する。ただし、以下の説明で明らかになるように、本発明にかかる化学的遺伝プログラミング処理では、ｍＲＮＡに相当する構成は含まれないため、ｔＲＮＡテーブルのルール番号は、後に説明するアミノアシルｔＲＮＡテーブルを介してＤＮＡの第１の部分のルール番号と対応することになる。ここでは、同一のルール番号同士が対応する。
【００５２】
ここで、「シンボル」とは、表現型ツリーを構成するアルファベット文字、数学記号、数字等である。シンボルとしては、必要に応じて、他の記号を含ませてもよい。また、シンボルには、終端シンボルと非終端シンボルとが含まれるものとする。プログラミングにより最終的に生成するのが、たとえば、ある関数形である場合を考えると、この最終的な関数形は、変数を表現するためのアルファベット文字（たとえば、ｘ）と数学記号（演算記号、たとえば、＋、−など）により表現される。したがって、このようなプログラミングの最終形に含まれるシンボルは、終端シンボルであり、それ以外のシンボルは非終端シンボルである。
【００５３】
ＤＮＡの第３の部分は、アミノ酸を翻訳により生成するための情報を含んでいる。
【００５４】
個々の「アミノ酸」は、上記シンボルの書換の対応関係に対応する。ここで、この書換の対応関係を「Ａ→Ｂ」のように表し、この対応関係において「Ａ」を始点シンボル、「Ｂ」を書換シンボルと呼ぶことにする。
【００５５】
ここで、「転写」とは、ＤＮＡ中の情報をそのままコピーする処理に相当し、「翻訳」とは、ＤＮＡ中の情報（ルール番号）を、後に説明するアミノアシルｔＲＮＡテーブルにしたがって、対応するシンボルの書換を行っていく処理を意味する。
【００５６】
すなわち、所定の非終端シンボルから、ＤＮＡの第１の部分の情報に従って、書換を順次行っていく。この書換は、途中で生成される分岐のためにツリー構造となる。このようなツリーを「表現型ツリー」とよぶ。そして、この表現型ツリーの全ての枝の端部が、終端シンボルとなった時点で、そのＤＮＡの第１の部分についての翻訳処理が終了する。このようにして翻訳処理が終了することで、生成された表現型ツリーの枝の端部により表現される結果を、「表現型実体」と呼ぶ。
【００５７】
以下、図４で示される原則的な処理について、簡単に説明する。
【００５８】
まず、ＤＮＡの第２の部分のＬ個のルール番号−シンボルのペアから、Ｌ個のｔＲＮＡが転写によって作られ、ｔＲＮＡテーブルの集団に加えられる。ここで、ｔＲＮＡの数が、Ｌ1個をオーバーしたら、ｔＲＮＡをランダムに選んで消去する。
【００５９】
次に、Ｍ個のアミノ酸をＤＮＡの第３の部分のＭ個のルール番号から翻訳によって作る。翻訳は、存在しているアミノアシルｔＲＮＡの集団（アミノアシルｔＲＮＡテーブル）を用いて行なわれ、ＤＮＡ上のルール番号に一致するルール番号を持つアミノアシルｔＲＮＡがランダムに選ばれる。それを持つアミノ酸がアミノ酸集団（アミノ酸テーブル）に加えられる。
【００６０】
このとき同様に、アミノ酸数がＭ1個をオーバーしたら、アミノ酸をランダムに選んで消す。
【００６１】
次に、ｔＲＮＡとアミノ酸との間の分子反応が起きる。ランダムに選んだｔＲＮＡのシンボルとランダムに選んだアミノ酸の始点シンボルが一致していたなら、２つを結合して１つのアミノアシルｔＲＮＡを作る。これを繰返して、Ｒ2個の新しいアミノアシルｔＲＮＡが、アミノアシルｔＲＮＡ集団に加えられたら、アミノアシルｔＲＮＡをランダムに選んで消し、アミノアシルｔＲＮＡ数がＲ1個以内になるようにする。この結果、図４に示すように、同一のルール番号に対して、異なる書換の対応関係（アミノ酸）が対応することも許容するものとする。
【００６２】
次に、ＤＮＡの第１の部分のルール番号から、アミノアシルｔＲＮＡを用いた翻訳により、表現型ツリーを生成する。
【００６３】
表現型ツリーの最終形により表現されるプログラミング結果、たとえば、関数形を外部に用意したターゲット関数と比較し、細胞の適応度を計算する。後に説明するように、この適応度に応じて、細胞の選択が行われる。さらに、遺伝的プログラミングのために、ＤＮＡには、突然変異処理と、ＤＮＡの交叉処理、細胞間の分子交換処理などが行われて、１世代分の処理が終了する。
【００６４】
以上の反応は、もちろん生物の翻訳機構を完全に模倣したものではない。ＤＮＡは、ｍＲＮＡの完全な情報を持っているわけではないし、したがって酵素として働くタンパク質はこのモデルでは作られない。しかしながら、この簡略化された代謝系は、アミノアシルｔＲＮＡが遺伝情報の翻訳テーブルを持ち、翻訳によって作られた分子が新しいアミノアシルｔＲＮＡを生成するというフィードバック機構を備えており、生物が行なう「コードと翻訳テーブルの共進化」を実現している。
【００６５】
（化学的遺伝プログラミング装置の機能構成）
図５は、図１および図２で説明した化学的遺伝プログラミング装置１００の機能ブロック図である。
【００６６】
図４で説明したような処理を実現するために、ハードディスク１２４中には、各細胞ごとのＤＮＡ情報を格納するためのＤＮＡ情報テーブル１２４２と、各細胞において転写により生成されたｔＲＮＡテーブルを格納するためのｔＲＮＡ情報テーブル１２４４と、各細胞において翻訳により生成されたアミノ酸テーブルを格納するためのアミノ酸情報テーブル１２４６と、各細胞において反応により生成されたアミノアシルｔＲＮＡテーブルを格納するアミノアシルｔＲＮＡ情報テーブル１２４８とが、記憶されている。
【００６７】
また、ＣＰＵ１２０が、ハードディスク１２４等に格納されたプログラムに基づいて行う処理として、演算処理部は、ＤＮＡの第２の部分からｔＲＮＡの転写処理を行うｔＲＮＡ転写処理部１２０１と、ＤＮＡの第３の部分とアミノアシルｔＲＮＡテーブルとに基づいて、アミノ酸の翻訳処理を行うアミノ酸翻訳処理部１２０２と、アミノ酸とｔＲＮＡとの反応処理を行ってアミノアシルｔＲＮＡテーブルを更新するためのアミノアシルｔＲＮＡ更新処理部１２０３と、アミノアシルｔＲＮＡテーブルとＤＮＡの第１の部分とに基づく翻訳により表現型ツリーを生成するための表現型ツリー生成処理部１２０５と、適応度に応じて細胞の選択処理を行うための選択処理部１２０５と、ＤＮＡに対する突然変異処理を行うための突然変異処理部１２０６と、ＤＮＡの交叉および分子交換処理を行うための交叉・分子交換処理部１２０７とを含む。
【００６８】
（遺伝的オペレーション）
以下、具体的な化学的遺伝プログラミングの処理について説明する。
【００６９】
図６および図７は、このような化学的遺伝プログラミングの処理の流れを説明するためのフローチャートである。
【００７０】
まず、図６を参照して、処理が開始されると、初期化処理が行われる（ステップＳ１００）。
【００７１】
ここで、初期化処理では、代謝機構を持った細胞を表現するため変数およびテーブルの記憶領域を、たとえば、ハードディスク１２４のような記憶装置中に細胞Ｎ個分用意する。
【００７２】
初め、各細胞のＤＮＡの第１および第３の部分にはランダムなルール番号を与え、ＤＮＡの第２の部分には、ランダムなルール番号および所定のシンボルのうちのランダムな非終端シンボルを対として与え、ｔＲＮＡテーブル、アミノアシルｔＲＮＡは、空の状態であるとする。世代を表す変数ＧＮの値が１に設定される。また、各細胞にアミノ酸をＭ1個用意する。
【００７３】
図８は、このように初期的に準備されるアミノ酸の例を示す図である。
【００７４】
図８に示した例では、シンボルは６つの非終端シンボルの”Ｉ，Ｎ，Ｏ，Ｒ，Ｚ，Ｄ”と、１６個の終端シンボルの”ｘ，＾，＋，−，＊，／，０，１，２，３，４，５，６，７，８，９”を含んでおり、アミノ酸は、これらシンボル間の書換の対応関係を示す。ここでは、全ての翻訳は、シンボル”Ｉ”から開始され、全ての非終端シンボルが終端シンボルに置き換えられたときに、翻訳が終了する。すなわち、現在存在している表現のうちの非終端シンボルに対して、ＤＮＡ中に現われている左から右の順序に従って翻訳（書換）が行われ、すべての非終端シンボルが置き換えられてしまうまでこの処理が続けられる。非終端シンボルは、さらに翻訳可能なシンボルのことを意味する。
【００７５】
また、たとえば、”Ｎ→（ＮＯＮ）”というような対応関係は、ここで、１つのシンボル”Ｎ”から３つのシンボル”Ｎ”、”Ｏ”，”Ｎ”への分岐が生じることを意味する。図８に示したアミノ酸のライブラリは、あくまでも一例であって、たとえば、さらに、多くのシンボルや他の対応関係が含まれていてもよいし、翻訳が開始されるシンボルも複数個存在してもよい。
【００７６】
なお、ＤＮＡの第２の部分中にランダムに割当てられるシンボルは、この初期的なアミノ酸のライブラリの非終端シンボルに対応するようになっているものとする。また、第１および第３の部分のランダムなルール番号は、この第２の部分のルール番号の範囲で割当てが行われているものとする。
【００７７】
再び、図６に戻って、続いて、各細胞において、Ｌ1個のｔＲＮＡをＤＮＡの第２部分からの転写により生成する（ステップＳ１０２）。
【００７８】
さらに、ランダムに選んだｔＲＮＡのシンボルとランダムに選んだアミノ酸の始点シンボルが一致していたなら、２つを結合して１つのアミノアシルｔＲＮＡを作るとの処理を繰返すことで、Ｒ１個のアミノアシルｔＲＮＡからなるテーブルを生成する（ステップＳ１０４）。
【００７９】
次に、生成されたアミノアシルｔＲＮＡテーブルを用いて、遺伝子の第１の部分を翻訳して、表現型ツリーを生成する（ステップＳ１０６）。
【００８０】
図９は、このようにして生成される表現型ツリーの一例を示す図である。
【００８１】
図９に示した例では、初期シンボル”Ｉ”から始まって、途中で３つの分岐が生じ、各分岐がそれぞれ、”４”、”＋”、”ｘ”という終端シンボルに翻訳（書換）が行われることで、翻訳処理が終了している。この場合は、この表現型ツリーにより、”４＋ｘ”との関数形（表現型実体）が生成されたことになる。より一般的には、このような最終形は、多変数の関数であってもよい。
【００８２】
再び、図６もどって、次に、表現型ツリーにより生成された関数とターゲット関数との比較に基づいて、細胞の選択処理を行う（ステップＳ１０８）。
【００８３】
すなわち、表現型ツリーにより表される関数とターゲット関数とを比較して一致度（適応度）を算出する。たとえば、所定の変数の変域において、複数の所定のサンプル点での表現型ツリーにより表される関数の値とターゲット関数の値の差の総和の平方に依存して、この平方に対して単調に減少する関数を評価関数とし、この評価関数の値を一致度とすればよい。つまり、一致の度合いが低くなるほど、一致度は小さくなる。
【００８４】
次に、この一致度に応じた確率で選択されるような選択規則、たとえば、ルーレット選択により細胞の選択を行う。したがって、次の世代の細胞の個体数は、このようにして選択されたものとなる。
【００８５】
次に、ＤＮＡの突然変異処理が行われる（ステップＳ１１０）。一旦、細胞が次の世代に対して選択されると、各細胞のＤＮＡ中のルール番号の各々は、ランダムに確率ｐmにより、他の正当なコードと置き換えられる。
【００８６】
続いて、ＤＮＡの交叉処理と分子交換処理が行われる（ステップＳ１１２）。
【００８７】
すなわち、突然変異が終わった後に、選択された細胞の個数をＮとするとき、すべての細胞をＮ／２組のペアにする。各ペアは、確率ｐcで、交叉処理を受ける。つまり、確率ｐcで、ランダムに選択されたＤＮＡの対の間で、一点における交叉が行なわれる。
【００８８】
さらに、それぞれのペアにおいて、分子交換を行う。たとえば、分子交換では、ｔＲＮＡ、アミノ酸、アミノアシルｔＲＮＡの各々について、５０％の分子をランダムに選んで交換するものとする。
【００８９】
このような進化の過程によって、最適なアミノ酸が、世代間を通して伝搬していくが、適切でないアミノ酸は除去されていく。アミノ酸およびアミノアシルｔＲＮＡの複雑さは、時間とともに大きくなっていき、アミノ酸の生産され得る組合せは、１つのアミノアシルｔＲＮＡテーブルに組み込まれていくことになる。
【００９０】
次に、世代変数ＧＮの値が１だけインクリメントされる（ステップＳ１１４）。
【００９１】
そして、世代変数ＧＮが所定の最大世代数Ｇｎｍａｘを超えているかが判断される（ステップＳ１１６）。もしも、世代変数ＧＮが所定の最大世代数Ｇｎｍａｘを超えていれば、処理は終了する。一方、世代変数ＧＮが所定の最大世代数Ｇｎｍａｘ以下であるときは、処理はステップＳ１１８に移行する。
【００９２】
続いて、ＤＮＡの第２の部分のＬ個のルール番号−シンボルのペアから、Ｌ個のｔＲＮＡが転写によって作られ、ｔＲＮＡテーブルの集団に加えられる（ステップＳ１１８）。ここで、ｔＲＮＡの数が、Ｌ1個をオーバーしたら、ｔＲＮＡをランダムに選んで消去する。
【００９３】
次に、Ｍ個のアミノ酸をＤＮＡの第３の部分のＭ個のルール番号から翻訳によって生成する（ステップＳ１２０）。翻訳は、存在しているアミノアシルｔＲＮＡの集団（アミノアシルｔＲＮＡテーブル）を用いて行なわれ、ＤＮＡ上のルール番号に一致するルール番号を持つアミノアシルｔＲＮＡがランダムに選ばれる。それを持つアミノ酸がアミノ酸集団（アミノ酸テーブル）に加えられる。
【００９４】
このとき同様に、アミノ酸数がＭ1個をオーバーしたら、アミノ酸をランダムに選んで消す。
【００９５】
次に、ｔＲＮＡとアミノ酸との間の分子反応処理により、アミノアシルｔＲＮＡテーブルの更新を行う（ステップＳ１２２）。すなわち、ランダムに選んだｔＲＮＡのシンボルとランダムに選んだアミノ酸の始点シンボルが一致していたなら、２つを結合して１つのアミノアシルｔＲＮＡを作る。これを繰返して、Ｒ2個の新しいアミノアシルｔＲＮＡが、アミノアシルｔＲＮＡ集団に加えられたら、アミノアシルｔＲＮＡをランダムに選んで消し、アミノアシルｔＲＮＡ数がＲ1個以内になるようにする。この結果、同一のルール番号に対して、異なる書換の対応関係（アミノ酸）が対応することも許容する。
【００９６】
次に、ＤＮＡの第１の部分のルール番号から、アミノアシルｔＲＮＡを用いた翻訳により、表現型ツリーを生成する（ステップＳ１２４）。
【００９７】
さらに、ステップＳ１０８，Ｓ１１０，Ｓ１１２とそれぞれ同様にして、細胞の選択処理を行い（ステップＳ１２６）、ＤＮＡの突然変異処理（ステップＳ１２８）、ＤＮＡの交叉と分子交換処理（ステップＳ１３０）を行って、処理はステップＳ１１４に復帰する。
【００９８】
（具体例）
化学的遺伝プログラミング処理の有用性を検証するために、単一変数の数学的な関数形をこの手続きで獲得する処理を行った。特に、ターゲット関数としては、以下のものとする。
【００９９】
ｆ（ｘ）＝２ｘ6＋３ｘ4＋４ｘ2＋１００
このような関数を、領域（−５，５）において最適化を行なう。各個体の一致度（適応度）は、以下の関数によって定義される。
【０１００】
【数１】
2005215786.tif 000003
【０１０１】
ここで、ｄは、上記領域において所定の間隔をもった有限個の値の組について、生成された関数の各値と、ターゲット関数の各値との間の差の和の平方である。これらの実験のためのパラメータの値は、以下のとおりである。
【０１０２】
突然変異確率ｐmは、０．００７であり、交叉確実ｐcは０．７である。
【０１０３】
個体の数は１４３とした。
【０１０４】
図１０は、以上の条件において、最適個体と平均個体の一致度の各世代ごとの変化を表す図である。
【０１０５】
この条件では、最適な個体は、第５８世代において現われていることがわかった。
【０１０６】
また、図１１は、最終的に得られた関数とターゲット関数との比較結果を示す図である。さらに、図１２は、細胞の中に進化したアミノ酸のヒストグラムを示す図である。
【図面の簡単な説明】
【０１０７】
【図１】本発明の化学的遺伝プログラミング装置１００の一例の外観を示す図である。
【図２】化学的遺伝プログラミング装置１００のハードウェア構成をブロック図形式で示す図である。
【図３】実際の生物細胞における代謝の機構を説明するための概念図である。
【図４】化学的遺伝プログラミング処理の基本的な流れの概略を示す概念図である。
【図５】図１および図２で説明した化学的遺伝プログラミング装置１００の機能ブロック図である。
【図６】化学的遺伝プログラミングの処理の流れを説明するための第１のフローチャートである。
【図７】化学的遺伝プログラミングの処理の流れを説明するための第２のフローチャートである。
【図８】初期的に準備されるアミノ酸の例を示す図である。
【図９】生成される表現型ツリーの一例を示す図である。
【図１０】最適個体と平均個体の一致度の各世代ごとの変化を表す図である。
【図１１】最終的に得られた関数とターゲット関数との比較結果を示す図である。
【図１２】細胞の中に進化したアミノ酸のヒストグラムを示す図である。
【符号の説明】
【０１０８】
１００  化学的遺伝プログラミング装置、１０２  コンピュータ本体、１０４  ディスプレイ、１０６  ＦＤドライブ、１０８  ＣＤ−ＲＯＭドライブ、１１０  キーボード、１１２  マウス、１１８  ＣＤ−ＲＯＭ、１２０  ＣＰＵ、１２２  メモリ、１２４  ハードディスク、１２８  通信インタフェース、１３０  ディスプレイ。
【図１】
2005215786.tif 000004
【図２】
2005215786.tif 000005
【図３】
2005215786.tif 000006
【図４】
2005215786.tif 000007
【図５】
2005215786.tif 000008
【図６】
2005215786.tif 000009
【図７】
2005215786.tif 000010
【図８】
2005215786.tif 000011
【図９】
2005215786.tif 000012
【図１０】
2005215786.tif 000013
【図１１】
2005215786.tif 000014
【図１２】
2005215786.tif 000015