JP 4572304 B2 2010.11.4(57)【特許請求の範囲】【請求項１】
各個体ごとの遺伝情報と、ルール番号とシンボルとの対を複数組含むトランスファー情報のグループと、前記シンボルの書換の対応関係を含む書換情報のグループと、前記トランスファー情報と前記書換情報との組み合わせであって翻訳処理時の前記ルール番号と前記書換情報との対応関係を表す翻訳対応関係を複数個含む翻訳テーブルとを格納するための記憶手段を備え、前記書換情報は、前記シンボルのうちの始点シンボルと前記シンボルのうちの少なくとも１つの書換シンボルとの間の書換の対応関係を特定する情報であり、前記遺伝情報は、10関数を表す表現型実体を生成するための前記ルール番号の第１の系列を含む第１の情報と、
前記トランスファー情報として選択的に使用される、前記ルール番号と前記シンボルとの対を複数組含む第２の情報と、前記書換情報を生成するための前記ルール番号の第２の系列を含む第３の情報とを含み、
前記シンボルは、
前記表現型実体により表現される前記関数を構成するシンボルであって、翻訳処理の終了を示す終端シンボルと、１つまたは複数の他のシンボルに継続して翻訳可能であることに対応する非終端シンボ

20

(2)

JP 4572304 B2 2010.11.4

ルとを含み、
前記第２の情報からの転写処理により選択された前記ルール番号と前記シンボルとの対を使用して前記トランスファー情報のグループを生成する転写処理手段と、
前記翻訳テーブルにおいて、前記第３の情報中の前記ルール番号に一致するルール番号を有する前記翻訳対応関係をランダムに選択して、前記翻訳対応関係により特定される前
記書換情報を前記書換情報のグループに追加することで前記書換情報のグループを生成する第１の翻訳処理手段と、前記書換情報のグループからランダムに選択した書換情報の始点シンボルと、前記トランスファー情報のグループからランダムに選択したトランスファー情報のシンボルとが一致する場合に、当該トランスファー情報と当該書換情報との組み合わせを追加することで10、前記翻訳テーブルを更新するための更新処理手段と、
前記第１の系列に従って、当該第１の系列中の前記ルール番号に対応する前記翻訳対応
関係により、前記シンボルの書換を前記終端シンボルに到達するまで継続することで、到達した前記終端シンボルの組み合わせとして表現される前記表現型実体を生成するための表現型実体生成処理手段と、
前記表現型実体により表現される前記関数の所定の目標に対する適応度に応じて、前記個体の選択処理を行うための選択処理手段と、
前記遺伝情報に対する突然変異処理を行うための突然変異処理手段とを備える、化学的
遺伝プログラミング装置。
【請求項２】

20

前記遺伝情報、前記トランスファー情報、前記書換情報の交叉処理を行うための交叉処
理手段をさらに備える、請求項１記載の化学的遺伝プログラミング装置。
【請求項３】
前記書換情報は、
前記非終端シンボルのうちの１つから前記非終端シンボルのうちの少なくとも１つの他の非終端シンボルへの継続書換情報と、前記非終端シンボルのうちの１つから前記終端シンボルのうちの１つへの終端書換情報とを含む、請求項１記載の化学的遺伝プログラミング装置。
【請求項４】
前記個体間で、前記トランスファー情報と、前記書換情報と、前記翻訳テーブルに含ま30れる情報とを交換する処理を行う交換処理手段をさらに備える、請求項１記載の化学的遺伝プログラミング装置。
【請求項５】
関数を表す表現型実体を生成するためのルール番号の第１の系列を含む第１の情報と、
トランスファー情報として選択的に使用される、前記ルール番号とシンボルとの対を複数組含む第２の情報と、書換情報を生成するための前記ルール番号の第２の系列を含む第３の情報とを含む遺伝情報に基づいて、遺伝的プログラミングを行うための化学的遺伝プロ
グラミング方法であって、現在の世代の各個体ごとの前記遺伝情報と、前記ルール番号と前記シンボルとの対を複数組含むトランスファー情報のグループと、前記シンボルの書換の対応関係を含む前記書

40

換情報のグループと、前記トランスファー情報と前記書換情報との組み合わせであって翻訳処理時の前記ルール番号と前記書換情報との対応関係を表す翻訳対応関係を複数個含む
翻訳テーブルとを記憶装置の記憶領域に格納する第１ステップを備え、前記書換情報は、前記シンボルのうちの始点シンボルと前記シンボルのうちの少なくとも１つの書換シンボルとの間の書換の対応関係を特定する情報であり、前記シンボルは、
前記表現型実体により表現される前記関数を構成するシンボルであって、翻訳処理の終了を示す終端シンボルと、１つまたは複数の他のシンボルに継続して翻訳可能であることに対応する非終端シンボ
ルとを含み、

50

(3)JP 4572304 B2 2010.11.4

前記第２の情報からの転写処理により選択された前記ルール番号と前記シンボルとの対を使用して前記トランスファー情報のグループを生成して前記記憶装置に格納する第２ス
テップと、
前記翻訳テーブルにおいて、前記第３の情報中の前記ルール番号に一致するルール番号を有する前記翻訳対応関係をランダムに選択して、前記翻訳対応関係により特定される前
記書換情報を前記書換情報のグループに追加することで前記書換情報のグループを生成して前記記憶装置に格納する第３ステップと、
前記書換情報のグループからランダムに選択した書換情報の始点シンボルと、前記トランスファー情報のグループからランダムに選択したトランスファー情報のシンボルとが一致する場合に、当該トランスファー情報と当該書換情報との組み合わせを追加することで10、前記翻訳テーブルを更新する第４ステップと、
前記第１の系列に従って、当該第１の系列中の前記ルール番号に対応する前記翻訳対応
関係により、前記シンボルの書換を前記終端シンボルに到達するまで継続することで、到達した前記終端シンボルの組み合わせとして表現される前記表現型実体を生成する第５ス
テップと、
前記表現型実体により表現される前記関数の所定の目標に対する適応度に応じて、前記個体の選択処理を行うための第６ステップと、
前記遺伝情報に対する突然変異処理を行い、前記遺伝情報の交叉処理を行うことで、前記遺伝情報の世代を更新する第７ステップと、
前記第１から第７ステップを所定回数繰り返すステップとを備える、化学的遺伝プログ

20

ラミング方法。
【発明の詳細な説明】【技術分野】【０００１】
本発明は、化学的遺伝アルゴリズムを用いた化学的遺伝プログラミング装置および化学的遺伝プログラミング方法に関する。
【背景技術】【０００２】
生物細胞において、シンボルから機能への翻訳、すなわち、遺伝子型から表現型への翻訳は、ＤＮＡ（DeoxyriboNucleic Acid）によって決定されており、したがって、細胞が30

遺伝子の変更を受けると、このような翻訳プロセスも変更を受ける。ＤＮＡは、機能単位であるアミノ酸とトランスファーＲＮＡ（ｔＲＮＡ：transfer RiboNucleic Acid）とに翻訳される。翻訳されたアミノ酸とｔＲＮＡとは反応して、細胞の遺伝型の構造を決定するための翻訳テーブル、すなわち、アミノアシル−ｔＲＮＡを生成する。遺伝型を決定するコードの構造に関する情報とコードの翻訳のための情報とが、ともにＤＮＡに格納されているので、遺伝子の変異により、細胞は、その双方を進化させることができる。
【０００３】（化学的遺伝アルゴリズム）
このような現実の生物細胞中の機構を真似ることで、新たな遺伝アルゴリズムである「
化学的遺伝アルゴリズム（ＣＧＡ：Chemical Genetic Algorithms）」が提案されている

40（たとえば、非特許文献１および非特許文献２を参照）。
【０００４】ＣＧＡは、遺伝子型の情報と表現型の情報との間に動的な関係を持ち込み、遺伝子型から表現型への翻訳過程を自律的に最適化していくことができる。
【０００５】
一般の遺伝的アルゴリズムにおいて、２進数で表わされるＤＮＡと最適化したい関数のパラメータとの間の対応関係を決める「コード化」は、アルゴリズムの性能を左右する最も大事な要因である。「化学的遺伝アルゴリズム」では、この決定関係を自律的に行なわせる。
【０００６】50

(4)JP 4572304 B2 2010.11.4

このようなアルゴリズムは、最適化アルゴリズムとして使用することができる。最適化
は、工学のさまざまな分野で最も要求度の高い処理の１つであり、化学的遺伝アルゴリズ
ムは、生物類似にインテリジェント・システムを構築しようとするアプローチ方法の１つである。
【０００７】
人工的に設計された進化システムの進化性は、一群の基本機能ユニットによって決定される。実生物における基本機能ユニットは２０個のアミノ酸であり、ＤＮＡに書かれた遺伝情報は、上述した「アミノアシルｔＲＮＡ」と呼ばれる一群の分子によってアミノ酸に変換される。生物システムにおいては、アミノアシルｔＲＮＡが、ゲノタイプ（遺伝子型：ＤＮＡ上の塩基配列、遺伝コード）からフェノタイプ（表現型：たんぱく質の機能等）

10への対応関係を定義する基本的な分子である。
【０００８】
実生物の機能ユニットであるアミノ酸や、それへの変換分子であるアミノアシルｔＲＮ
Ａを選び取る処理は、正にＤＮＡ／ＲＮＡに書かれたゲノタイプ（コード）の進化と一緒に行なわれたのであって、その意味で、コードとその変換テーブルは「同時進化」もしくは広い意味での「共進化」をしたといえる。
【０００９】
もしも、人工的な進化システムにおいても、コードと変換テーブルが共進化する仕組みを導入することができれば、進化実験をしながらシステムの進化性が自発的に高まるようにすることが可能となる。

20【００１０】「化学的遺伝アルゴリズム」では、遺伝的アルゴリズムを生物代謝系との類推で発展させた手法である。
【００１１】
通常の遺伝アルゴリズムでは、まず染色体集団が用意されて、それに突然変異・交叉などの遺伝的オペレーションが施されて処理が進む。しかしながら、「化学的遺伝アルゴリ
ズム」（以下ＣＧＡ）では、まず、染色体ではなく細胞の集団が用意される。
【００１２】
細胞１個は、通常の染色体（ＤＮＡ）に加えて、アミノ酸、ｔＲＮＡ、アミノアシルｔ
ＲＮＡという３つの種類の小分子集団を含んでおり、ＤＮＡ上の遺伝コードは、細胞内の30

転写・翻訳反応を通して実数値に変換され、適応度が計算される。
【００１３】
遺伝的オペレーションとしては、通常のＤＮＡ突然変異、ＤＮＡ交叉以外に、分子反応や細胞質交換も行なわれ、淘汰は、分子集団を含む細胞単位として行なわれる。
【００１４】（遺伝的プログラミング）
一方で、遺伝的プログラミングが、様々な工学的応用に適用されている（たとえば、非特許文献３を参照）。
【００１５】
ランダムに生成された、所定のプログラミング構成要素からなるプログラムからスター

40

トして、従来の遺伝的プログラミングは、遺伝的な操作を用いて各世代において最適なプ
ログラムを、何世代にもわたって繁殖させていくことにより、その集団を進化させていく。
【非特許文献１】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 enhancementby 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) Wor

50

(5)

JP 4572304 B2 2010.11.4

kshop Proceedings (2002) pp.146‑155【非特許文献３】Koza, R.: 1992. Genetic Programming : On the programming of Computers by Means of Natural Selection. London: MIT press (1992).
【発明の開示】【発明が解決しようとする課題】【００１６】
しかしながら上述したようなＣＧＡにおいては、関数パラメータの最適化の一手法については言及されているものの、これをプログラミングにどのように適用するのかについては明らかではないという問題点があった。
【００１７】

10

本発明の目的は、化学的遺伝アルゴリズムを適用して、プログラミングを可能とする化学的遺伝プログラミング装置および化学的遺伝プログラミング方法を提供することである。
【課題を解決するための手段】【００１８】
この発明のある局面に従うと、各個体ごとの遺伝情報と、ルール番号とシンボルとの対を複数組含むトランスファー情報のグループと、シンボルの書換の対応関係を含む書換情報のグループと、トランスファー情報と書換情報との組み合わせであって翻訳処理時のルール番号と書換情報との対応関係を表す翻訳対応関係を複数個含む翻訳テーブルとを格納するための記憶手段を備え、書換情報は、シンボルのうちの始点シンボルとシンボルのう20

ちの少なくとも１つの書換シンボルとの間の書換の対応関係を特定する情報であり、遺伝
情報は、関数を表す表現型実体を生成するためのルール番号の第１の系列を含む第１の情報と、トランスファー情報として選択的に使用される、ルール番号とシンボルとの対を複数組含む第２の情報と、書換情報を生成するためのルール番号の第２の系列を含む第３の情報とを含み、シンボルは、表現型実体により表現される関数を構成するシンボルであって、翻訳処理の終了を示す終端シンボルと、１つまたは複数の他のシンボルに継続して翻訳可能であることに対応する非終端シンボルとを含み、第２の情報からの転写処理により選択されたルール番号とシンボルとの対を使用してトランスファー情報のグループを生成する転写処理手段と、翻訳テーブルにおいて、第３の情報中のルール番号に一致するルー
ル番号を有する翻訳対応関係をランダムに選択して、翻訳対応関係により特定される書換30

情報を書換情報のグループに追加することで書換情報のグループを生成する第１の翻訳処
理手段と、書換情報のグループからランダムに選択した書換情報の始点シンボルと、トランスファー情報のグループからランダムに選択したトランスファー情報のシンボルとが一致する場合に、当該トランスファー情報と当該書換情報との組み合わせを追加することで、翻訳テーブルを更新するための更新処理手段と、第１の系列に従って、当該第１の系列
中のルール番号に対応する翻訳対応関係により、シンボルの書換を終端シンボルに到達す
るまで継続することで、到達した終端シンボルの組み合わせとして表現される表現型実体を生成するための表現型実体生成処理手段と、表現型実体により表現される関数の所定の目標に対する適応度に応じて、個体の選択処理を行うための選択処理手段と、遺伝情報に対する突然変異処理を行うための突然変異処理手段とを備える。

40【００１９】
好ましくは、化学的遺伝プログラミング装置は、遺伝情報、トランスファー情報、書換
情報の交叉処理を行うための交叉処理手段をさらに備える。
【００２０】
好ましくは、書換情報は、非終端シンボルのうちの１つから非終端シンボルのうちの少なくとも１つの他の非終端シンボルへの継続書換情報と、非終端シンボルのうちの１つから終端シンボルのうちの１つへの終端書換情報とを含む。
【００２１】
好ましくは、化学的遺伝プログラミング装置は、個体間で、トランスファー情報と、書
換情報と、翻訳テーブルに含まれる情報とを交換する処理を行う交換処理手段をさらに備

50

(6)

JP 4572304 B2 2010.11.4

える。
【００２２】
この発明の他の局面に従うと、関数を表す表現型実体を生成するためのルール番号の第１の系列を含む第１の情報と、トランスファー情報として選択的に使用される、ルール
番号とシンボルとの対を複数組含む第２の情報と、書換情報を生成するためのルール番号の第２の系列を含む第３の情報とを含む遺伝情報に基づいて、遺伝的プログラミングを行
うための化学的遺伝プログラミング方法であって、現在の世代の各個体ごとの遺伝情報と、ルール番号とシンボルとの対を複数組含むトランスファー情報のグループと、シンボルの書換の対応関係を含む書換情報のグループと、トランスファー情報と書換情報との組み合わせであって翻訳処理時のルール番号と書換情報との対応関係を表す翻訳対応関係を複10数個含む翻訳テーブルとを記憶装置の記憶領域に格納する第１ステップを備え、書換情報
は、シンボルのうちの始点シンボルとシンボルのうちの少なくとも１つの書換シンボルとの間の書換の対応関係を特定する情報であり、シンボルは、表現型実体により表現される関数を構成するシンボルであって、翻訳処理の終了を示す終端シンボルと、１つまたは複数の他のシンボルに継続して翻訳可能であることに対応する非終端シンボルとを含み、第２の情報からの転写処理により選択されたルール番号とシンボルとの対を使用してトラン
スファー情報のグループを生成して記憶装置に格納する第２ステップと、翻訳テーブルにおいて、第３の情報中のルール番号に一致するルール番号を有する翻訳対応関係をランダムに選択して、翻訳対応関係により特定される書換情報を書換情報のグループに追加する
ことで書換情報のグループを生成して記憶装置に格納する第３ステップと、書換情報のグ20

ループからランダムに選択した書換情報の始点シンボルと、トランスファー情報のグループからランダムに選択したトランスファー情報のシンボルとが一致する場合に、当該トラ
ンスファー情報と当該書換情報との組み合わせを追加することで、翻訳テーブルを更新する第４ステップと、第１の系列に従って、当該第１の系列中のルール番号に対応する翻訳
対応関係により、シンボルの書換を終端シンボルに到達するまで継続することで、到達した終端シンボルの組み合わせとして表現される表現型実体を生成する第５ステップと、表現型実体により表現される関数の所定の目標に対する適応度に応じて、個体の選択処理を行うための第６ステップと、遺伝情報に対する突然変異処理を行い、遺伝情報の交叉処理を行うことで、遺伝情報の世代を更新する第７ステップと、第１から第７ステップを所定
回数繰り返すステップとを備える。

30【発明の効果】【００２３】
この発明にかかる化学的遺伝プログラミング装置および化学的遺伝プログラミング方法によれば、遺伝情報の翻訳テーブルを持ち、遺伝情報から作られたトランスファー情報および書換情報が新しい翻訳テーブルを生成するというフィードバック機構を備え、「コードと翻訳テーブルの共進化」を実現して、最適なプログラミング結果を短時間に得ることか可能である。
【発明を実施するための最良の形態】【００２４】
以下、図面を参照して本発明の実施の形態について説明する。

40【００２５】（本発明のシステム構成）
図１は、本発明の化学的遺伝プログラミング装置１００の一例の外観を示す図である。
【００２６】
すなわち、図１に示した例では、化学的遺伝プログラミング装置１００は、一例として、汎用のコンピュータにより実現されるものとしている。
【００２７】
図１を参照して、この化学的遺伝プログラミング装置（コンピュータ）１００は、ＣＤ−ＲＯＭ（Compact Disc Read‑Only Memory ）上の情報を読込むためのＣＤ−ＲＯＭドラ
イブ１０８およびフレキシブルディスク（Flexible Disk、以下ＦＤ）１１６に情報を読

50

(7)

JP 4572304 B2 2010.11.4

み書きするためのＦＤドライブ１０６を備えたコンピュータ本体１０２と、コンピュータ
本体１０２に接続された表示装置としてのディスプレイ１０４と、同じくコンピュータ本
体１０２に接続された入力装置としてのキーボード１１０およびマウス１１２とを含む。
【００２８】
図２は、この化学的遺伝プログラミング装置１００のハードウェア構成をブロック図形
式で示す図である。
【００２９】
図２に示されるように、この化学的遺伝プログラミング装置１００を構成するコンピュータ本体１０２は、ＣＤ−ＲＯＭドライブ１０８およびＦＤドライブ１０６に加えて、それぞれバスＢＳに接続されたＣＰＵ（Central Processing Unit ）１２０と、ＲＯＭ（Re10

ad Only Memory) およびＲＡＭ （Random Access Memory）を含むメモリ１２２と、直接アクセスメモリ装置、たとえば、ハードディスク１２４と、ネットワーク２００とデータの授受を行うための通信インタフェース１２８とを含んでいる。ＣＤ−ＲＯＭドライブ１
０８にはＣＤ−ＲＯＭ１１８が装着される。ＦＤドライブ１０６にはＦＤ１１６が装着される。
【００３０】
なお、ＣＤ−ＲＯＭ１１８は、コンピュータ本体に対してインストールされるプログラ
ム等の情報を記録可能な媒体であれば、他の媒体、たとえば、ＤＶＤ−ＲＯＭ（Digital
Versatile Disc）やメモリカードなどでもよく、その場合は、コンピュータ本体１０２には、これらの媒体を読取ることが可能なドライブ装置が設けられる。

20【００３１】
本発明の化学的遺伝プログラミング装置の主要部は、コンピュータハードウェアと、Ｃ
ＰＵ１２０により実行されるソフトウェアとにより構成される。一般的にこうしたソフト
ウェアはＣＤ−ＲＯＭ１１８、ＦＤ１１６等の記憶媒体に格納されて流通し、ＣＤ−ＲＯ
Ｍドライブ１０８またはＦＤドライブ１０６等により記憶媒体から読取られてハードディ
スク１２４に一旦格納される。または、当該装置がネットワークに接続されている場合には、ネットワーク上のサーバから一旦ハードディスク１２４にコピーされてもよい。そう
してさらにハードディスク１２４からメモリ１２２中のＲＡＭに読出されてＣＰＵ１２０
により実行される。なお、ネットワーク接続されている場合には、ハードディスク１２４に格納することなくＲＡＭに直接ロードして実行するようにしてもよい。

30【００３２】
図１および図２に示したコンピュータのハードウェア自体およびその動作原理は一般的なものである。したがって、本発明の最も本質的な部分は、ＦＤ１１６、ＣＤ−ＲＯＭ１
１８、ハードディスク１２４等の記憶媒体に記憶されたソフトウェアである。
【００３３】
なお、一般的傾向として、コンピュータのオペレーティングシステムの一部として様々なプログラムモジュールを用意しておき、アプリケーションプログラムはこれらモジュールを所定の配列で必要な時に呼び出して処理を進める方式が一般的である。そうした場合、当該化学的遺伝プログラミング装置１００を実現するためのソフトウェア自体にはそうしたモジュールは含まれず、当該コンピュータでオペレーティングシステムと協働しては40

じめて化学的遺伝プログラミング装置１００が実現することになる。しかし、一般的なプ
ラットフォームを使用する限り、そうしたモジュールを含ませたソフトウェアを流通させる必要はなく、それらモジュールを含まないソフトウェア自体およびそれらソフトウェア
を記録した記録媒体（およびそれらソフトウェアがネットワーク上を流通する場合のデータ信号）が実施の形態を構成すると考えることができる。
【００３４】（生物システムにおける転写・翻訳機構）
まず、本発明の化学的遺伝プログラミング装置の動作を説明する前提として、実際の生物細胞における代謝の機構について概説しておく。
【００３５】50

(8)JP 4572304 B2 2010.11.4

図３は、このような実際の生物細胞における代謝の機構を説明するための概念図である。
【００３６】
図３を参照して、生物細胞における遺伝情報の翻訳は、一群の分子による代謝反応によって行なわれる。まず、生物は生合成反応により無機物からアミノ酸を作り出す。その主役となるのは植物が行なう光合成反応であり、この反応が作り出す糖を出発点とした解糖系の副産物としてのアミノ酸は合成される。また動物は、植物が合成したアミノ酸を摂取・消化することによってアミノ酸を獲得する。
【００３７】
一方、ＤＮＡが持つ遺伝情報は、大きく２つの流れをたどる。

10【００３８】
まず１つは、ＤＮＡからポリメラーゼによる転写によって作られたｔＲＮＡがアミノ酸とカップリングしてアミノアシルｔＲＮＡを作る。ｔＲＮＡは、約８０個の塩基からなる
ポリヌクレオチドであり、細胞内では特殊なクローバ構造に折畳まれる。
【００３９】
その一方の端にはｍＲＮＡと相補的にマッチングするアンチコドンが、もう一方の端はアミノ酸とマッチングする認識部位が含まれており、ｔＲＮＡはこの特殊な構造から、コドンからアミノ酸へのアダプタとして働くことができる。
【００４０】
このｔＲＮＡをアミノ酸とカップリングする役目を果たすのがアミノアシルｔＲＮＡ合20

成酵素（アミノアシルｔＲＮＡシンセターゼ）と呼ばれる一群の酵素である。アミノアシ
ルｔＲＮＡ合成酵素は、ｔＲＮＡクローバ構造に含まれるアミノ酸認識部位に取付き、それと照合するアミノ酸を見つけ出してはそれらを結合させる。各アミノ酸には１つずつ別のアミノアシルｔＲＮＡ合成酵素が用意されており、したがって細胞内では２０種類のア
ミノアシルｔＲＮＡ合成酵素が使われている。
【００４１】
ＤＮＡの遺伝情報がたどるもう１つの流れは、ＤＮＡからポリメラーゼによる転写によって作られたｍＲＮＡの翻訳である。ｍＲＮＡは、コドンの配列情報を保持した情報高分子であり、タンパク質のアミノ酸配列のもとになる。巨大タンパク質構造であるリボソー
ムは、このｍＲＮＡの中に含まれるコドンを１つ１つ順番に読取っては、対合するアンチ30

コドンを有するアミノアシルｔＲＮＡを見つけ出し、そこにカップリングしているアミノ酸を鎖状に結合していく。こうして得られたポリペプチド鎖（タンパク質）が、また酵素として細胞のさまざまな代謝反応を触媒する。
【００４２】
以上述べた生物遺伝情報の翻訳機構において、生物においては、ゲノタイプからフェノタイプへの対応関係（翻訳テーブル）が可変になっているということが特徴的である。生物では、コドン（ゲノタイプ・ユニット）とアミノ酸（フェノタイプ・ユニット）が直接結合した分子であるアミノアシルｔＲＮＡが翻訳テーブルを表わす。アミノアシルｋＲＮ
Ａの生成は、ＤＮＡを転写したｔＲＮＡがもとになるから、生物における翻訳テーブルは、ＤＮＡ情報の改変によって変化し得る仕組みを持つ。

40【００４３】
加えて、生物の翻訳機構が持つもう１つの重要な特徴は、代謝マップが一方向性のものではなく、フィードバックを含んでいるという点である。
【００４４】
すなわち、翻訳を含めた細胞内のすべての代謝反応は、酵素によって触媒されているが、それら酵素自体は代謝反応の産物であり、細胞内の各分子は複雑に相互依存している。
特に、遺伝情報の翻訳については、アミノアシルｔＲＮＡを合成する酵素であるアミノア
シルｔＲＮＡ合成酵素は、たんぱくとしてアミノアシルｔＲＮＡをコードしたコードの翻訳によってリボソームで合成されるから、コード（アミノアシルｔＲＮＡ合成酵素を表現
するコドンシーケンス）と翻訳テーブル（アミノアシルｔＲＮＡ）が相互に依存しており

50

(9)

JP 4572304 B2 2010.11.4、共進化する仕組みになっている。
【００４５】（化学的遺伝プログラミング処理の概要）
以下では、このような実際の生物の代謝反応をモデル化した本発明にかかる「化学的遺伝プログラミング」の構成の概略について説明する。
【００４６】（細胞内代謝反応）
図４は、化学的遺伝プログラミング処理の基本的な流れの概略を示す概念図である。
【００４７】
図４を参照して、まず、各々が次の４つの分子を内部に持つ複数の人工細胞（個体）を10考える。すなわち、１個のＤＮＡ、Ｌ1個のｔＲＮＡ、Ｍ1個のアミノ酸、Ｒ1個のアミノ
アシルｔＲＮＡである。
【００４８】
これら人工の分子は、次のような代謝反応を毎世代行なう。
【００４９】
各ＤＮＡは、第１の部分、第２の部分、第３の部分を含んでいるものとする。
【００５０】
ＤＮＡの第１の部分は、後に説明するように化学的遺伝プログラミングにより生成される「表現型ツリー」の翻訳のための情報（ルール番号）を有する。
【００５１】

20

ＤＮＡの第２の部分は、ｔＲＮＡテーブルを転写により生成するための情報を含んでいる。この第２の部分は、ルール番号とシンボルとの対を複数組含む。ルール番号とシンボルとの対は、実際の生物におけるｔＲＮＡが、その一方の端にはｍＲＮＡと相補的にマッチングするアンチコドンを有し、もう一方の端はアミノ酸とマッチングする認識部位を有することをモデル化したことに相当する。ただし、以下の説明で明らかになるように、本発明にかかる化学的遺伝プログラミング処理では、ｍＲＮＡに相当する構成は含まれない
ため、ｔＲＮＡテーブルのルール番号は、後に説明するアミノアシルｔＲＮＡテーブルを介してＤＮＡの第１の部分のルール番号と対応することになる。ここでは、同一のルール
番号同士が対応する。
【００５２】

30

ここで、「シンボル」とは、表現型ツリーを構成するアルファベット文字、数学記号、数字等である。シンボルとしては、必要に応じて、他の記号を含ませてもよい。また、シンボルには、終端シンボルと非終端シンボルとが含まれるものとする。プログラミングに
より最終的に生成するのが、たとえば、ある関数形である場合を考えると、この最終的な関数形は、変数を表現するためのアルファベット文字（たとえば、ｘ）と数学記号（演算記号、たとえば、＋、−など）により表現される。したがって、このようなプログラミン
グの最終形に含まれるシンボルは、終端シンボルであり、それ以外のシンボルは非終端シンボルである。
【００５３】
ＤＮＡの第３の部分は、アミノ酸を翻訳により生成するための情報を含んでいる。

40【００５４】
個々の「アミノ酸」は、上記シンボルの書換の対応関係に対応する。ここで、この書換の対応関係を「Ａ→Ｂ」のように表し、この対応関係において「Ａ」を始点シンボル、「Ｂ」を書換シンボルと呼ぶことにする。
【００５５】
ここで、「転写」とは、ＤＮＡ中の情報をそのままコピーする処理に相当し、「翻訳」とは、ＤＮＡ中の情報（ルール番号）を、後に説明するアミノアシルｔＲＮＡテーブルにしたがって、対応するシンボルの書換を行っていく処理を意味する。
【００５６】
すなわち、所定の非終端シンボルから、ＤＮＡの第１の部分の情報に従って、書換を順

50

(10)

JP 4572304 B2 2010.11.4

次行っていく。この書換は、途中で生成される分岐のためにツリー構造となる。このようなツリーを「表現型ツリー」とよぶ。そして、この表現型ツリーの全ての枝の端部が、終端シンボルとなった時点で、そのＤＮＡの第１の部分についての翻訳処理が終了する。このようにして翻訳処理が終了することで、生成された表現型ツリーの枝の端部により表現される結果を、「表現型実体」と呼ぶ。
【００５７】
以下、図４で示される原則的な処理について、簡単に説明する。
【００５８】
まず、ＤＮＡの第２の部分のＬ個のルール番号−シンボルのペアから、Ｌ個のｔＲＮＡが転写によって作られ、ｔＲＮＡテーブルの集団に加えられる。ここで、ｔＲＮＡの数が10、Ｌ1個をオーバーしたら、ｔＲＮＡをランダムに選んで消去する。
【００５９】
次に、Ｍ個のアミノ酸をＤＮＡの第３の部分のＭ個のルール番号から翻訳によって作る。翻訳は、存在しているアミノアシルｔＲＮＡの集団（アミノアシルｔＲＮＡテーブル）を用いて行なわれ、ＤＮＡ上のルール番号に一致するルール番号を持つアミノアシルｔＲ
ＮＡがランダムに選ばれる。それを持つアミノ酸がアミノ酸集団（アミノ酸テーブル）に加えられる。
【００６０】
このとき同様に、アミノ酸数がＭ1個をオーバーしたら、アミノ酸をランダムに選んで消す。

20【００６１】
次に、ｔＲＮＡとアミノ酸との間の分子反応が起きる。ランダムに選んだｔＲＮＡのシ
ンボルとランダムに選んだアミノ酸の始点シンボルが一致していたなら、２つを結合して１つのアミノアシルｔＲＮＡを作る。これを繰返して、Ｒ2個の新しいアミノアシルｔＲ
ＮＡが、アミノアシルｔＲＮＡ集団に加えられたら、アミノアシルｔＲＮＡをランダムに選んで消し、アミノアシルｔＲＮＡ数がＲ1個以内になるようにする。この結果、図４に示すように、同一のルール番号に対して、異なる書換の対応関係（アミノ酸）が対応することも許容するものとする。
【００６２】
次に、ＤＮＡの第１の部分のルール番号から、アミノアシルｔＲＮＡを用いた翻訳によ30

り、表現型ツリーを生成する。
【００６３】
表現型ツリーの最終形により表現されるプログラミング結果、たとえば、関数形を外部に用意したターゲット関数と比較し、細胞の適応度を計算する。後に説明するように、この適応度に応じて、細胞の選択が行われる。さらに、遺伝的プログラミングのために、Ｄ
ＮＡには、突然変異処理と、ＤＮＡの交叉処理、細胞間の分子交換処理などが行われて、１世代分の処理が終了する。
【００６４】
以上の反応は、もちろん生物の翻訳機構を完全に模倣したものではない。ＤＮＡは、ｍ
ＲＮＡの完全な情報を持っているわけではないし、したがって酵素として働くタンパク質40はこのモデルでは作られない。しかしながら、この簡略化された代謝系は、アミノアシル
ｔＲＮＡが遺伝情報の翻訳テーブルを持ち、翻訳によって作られた分子が新しいアミノア
シルｔＲＮＡを生成するというフィードバック機構を備えており、生物が行なう「コードと翻訳テーブルの共進化」を実現している。
【００６５】（化学的遺伝プログラミング装置の機能構成）
図５は、図１および図２で説明した化学的遺伝プログラミング装置１００の機能ブロック図である。
【００６６】
図４で説明したような処理を実現するために、ハードディスク１２４中には、各細胞ご

50

(11)

JP 4572304 B2 2010.11.4とのＤＮＡ情報を格納するためのＤＮＡ情報テーブル１２４２と、各細胞において転写により生成されたｔＲＮＡテーブルを格納するためのｔＲＮＡ情報テーブル１２４４と、各細胞において翻訳により生成されたアミノ酸テーブルを格納するためのアミノ酸情報テー
ブル１２４６と、各細胞において反応により生成されたアミノアシルｔＲＮＡテーブルを格納するアミノアシルｔＲＮＡ情報テーブル１２４８とが、記憶されている。
【００６７】
また、ＣＰＵ１２０が、ハードディスク１２４等に格納されたプログラムに基づいて行う処理として、演算処理部は、ＤＮＡの第２の部分からｔＲＮＡの転写処理を行うｔＲＮ
Ａ転写処理部１２０１と、ＤＮＡの第３の部分とアミノアシルｔＲＮＡテーブルとに基づいて、アミノ酸の翻訳処理を行うアミノ酸翻訳処理部１２０２と、アミノ酸とｔＲＮＡと10の反応処理を行ってアミノアシルｔＲＮＡテーブルを更新するためのアミノアシルｔＲＮ
Ａ更新処理部１２０３と、アミノアシルｔＲＮＡテーブルとＤＮＡの第１の部分とに基づ
く翻訳により表現型ツリーを生成するための表現型ツリー生成処理部１２０５と、適応度に応じて細胞の選択処理を行うための選択処理部１２０５と、ＤＮＡに対する突然変異処理を行うための突然変異処理部１２０６と、ＤＮＡの交叉および分子交換処理を行うための交叉・分子交換処理部１２０７とを含む。
【００６８】（遺伝的オペレーション）
以下、具体的な化学的遺伝プログラミングの処理について説明する。
20【００６９】
図６および図７は、このような化学的遺伝プログラミングの処理の流れを説明するためのフローチャートである。
【００７０】
まず、図６を参照して、処理が開始されると、初期化処理が行われる（ステップＳ１００）。
【００７１】
ここで、初期化処理では、代謝機構を持った細胞を表現するため変数およびテーブルの記憶領域を、たとえば、ハードディスク１２４のような記憶装置中に細胞Ｎ個分用意する。

30【００７２】
初め、各細胞のＤＮＡの第１および第３の部分にはランダムなルール番号を与え、ＤＮＡの第２の部分には、ランダムなルール番号および所定のシンボルのうちのランダムな非終端シンボルを対として与え、ｔＲＮＡテーブル、アミノアシルｔＲＮＡは、空の状態であるとする。世代を表す変数ＧＮの値が１に設定される。また、各細胞にアミノ酸をＭ1個用意する。
【００７３】
図８は、このように初期的に準備されるアミノ酸の例を示す図である。
【００７４】
図８に示した例では、シンボルは６つの非終端シンボルのと、１６個の終端シンボルの
７，８，９

Ｉ，Ｎ，Ｏ，Ｒ，Ｚ，Ｄ

ｘ，＾，＋，−，＊，／，０，１，２，３，４，５，６，

40を含んでおり、アミノ酸は、これらシンボル間の書換の対応関係を示す。ここでは、全ての翻訳は、シンボル

Ｉから開始され、全ての非終端シンボルが終端シンボルに置き換えられたときに、翻訳が終了する。すなわち、現在存在している表現のうちの非終端シンボルに対して、ＤＮＡ中に現われている左から右の順序に従って翻訳（書換）が行われ、すべての非終端シンボルが置き換えられてしまうまでこの処理が続けられる。非終端シンボルは、さらに翻訳可能なシンボルのことを意味する。
【００７５】
また、たとえば、ル

Ｎ

Ｎ→（ＮＯＮ）

から３つのシンボル

Ｎ、というような対応関係は、ここで、１つのシンボ
Ｏ，Ｎへの分岐が生じることを意味する。

図８に示したアミノ酸のライブラリは、あくまでも一例であって、たとえば、さらに、多

50

(12)

JP 4572304 B2 2010.11.4

くのシンボルや他の対応関係が含まれていてもよいし、翻訳が開始されるシンボルも複数個存在してもよい。
【００７６】
なお、ＤＮＡの第２の部分中にランダムに割当てられるシンボルは、この初期的なアミノ酸のライブラリの非終端シンボルに対応するようになっているものとする。また、第１および第３の部分のランダムなルール番号は、この第２の部分のルール番号の範囲で割当てが行われているものとする。
【００７７】
再び、図６に戻って、続いて、各細胞において、Ｌ1個のｔＲＮＡをＤＮＡの第２部分
10からの転写により生成する（ステップＳ１０２）。
【００７８】
さらに、ランダムに選んだｔＲＮＡのシンボルとランダムに選んだアミノ酸の始点シンボルが一致していたなら、２つを結合して１つのアミノアシルｔＲＮＡを作るとの処理を繰返すことで、Ｒ１個のアミノアシルｔＲＮＡからなるテーブルを生成する（ステップＳ
１０４）。
【００７９】
次に、生成されたアミノアシルｔＲＮＡテーブルを用いて、遺伝子の第１の部分を翻訳して、表現型ツリーを生成する（ステップＳ１０６）。
【００８０】

20

図９は、このようにして生成される表現型ツリーの一例を示す図である。
【００８１】
図９に示した例では、初期シンボル
分岐がそれぞれ、

４

、

＋

、

Ｉ
ｘ

から始まって、途中で３つの分岐が生じ、各という終端シンボルに翻訳（書換）が行われる

ことで、翻訳処理が終了している。この場合は、この表現型ツリーにより、４＋ｘとの関数形（表現型実体）が生成されたことになる。より一般的には、このような最終形は、多変数の関数であってもよい。
【００８２】
再び、図６もどって、次に、表現型ツリーにより生成された関数とターゲット関数との比較に基づいて、細胞の選択処理を行う（ステップＳ１０８）。
【００８３】30

すなわち、表現型ツリーにより表される関数とターゲット関数とを比較して一致度（適応度）を算出する。たとえば、所定の変数の変域において、複数の所定のサンプル点での表現型ツリーにより表される関数の値とターゲット関数の値の差の総和の平方に依存して、この平方に対して単調に減少する関数を評価関数とし、この評価関数の値を一致度とすればよい。つまり、一致の度合いが低くなるほど、一致度は小さくなる。
【００８４】
次に、この一致度に応じた確率で選択されるような選択規則、たとえば、ルーレット選
択により細胞の選択を行う。したがって、次の世代の細胞の個体数は、このようにして選択されたものとなる。
【００８５】

40

次に、ＤＮＡの突然変異処理が行われる（ステップＳ１１０）。一旦、細胞が次の世代に対して選択されると、各細胞のＤＮＡ中のルール番号の各々は、ランダムに確率ｐmにより、他の正当なコードと置き換えられる。
【００８６】
続いて、ＤＮＡの交叉処理と分子交換処理が行われる（ステップＳ１１２）。
【００８７】
すなわち、突然変異が終わった後に、選択された細胞の個数をＮとするとき、すべての細胞をＮ／２組のペアにする。各ペアは、確率ｐcで、交叉処理を受ける。つまり、確率
ｐcで、ランダムに選択されたＤＮＡの対の間で、一点における交叉が行なわれる。
【００８８】50

(13)JP 4572304 B2 2010.11.4

さらに、それぞれのペアにおいて、分子交換を行う。たとえば、分子交換では、ｔＲＮ
Ａ、アミノ酸、アミノアシルｔＲＮＡの各々について、５０％の分子をランダムに選んで交換するものとする。
【００８９】
このような進化の過程によって、最適なアミノ酸が、世代間を通して伝搬していくが、適切でないアミノ酸は除去されていく。アミノ酸およびアミノアシルｔＲＮＡの複雑さは、時間とともに大きくなっていき、アミノ酸の生産され得る組合せは、１つのアミノアシ
ルｔＲＮＡテーブルに組み込まれていくことになる。
【００９０】
次に、世代変数ＧＮの値が１だけインクリメントされる（ステップＳ１１４）。

10【００９１】
そして、世代変数ＧＮが所定の最大世代数Ｇｎｍａｘを超えているかが判断される（ステップＳ１１６）。もしも、世代変数ＧＮが所定の最大世代数Ｇｎｍａｘを超えていれば、処理は終了する。一方、世代変数ＧＮが所定の最大世代数Ｇｎｍａｘ以下であるときは、処理はステップＳ１１８に移行する。
【００９２】
続いて、ＤＮＡの第２の部分のＬ個のルール番号−シンボルのペアから、Ｌ個のｔＲＮＡが転写によって作られ、ｔＲＮＡテーブルの集団に加えられる（ステップＳ１１８）。
ここで、ｔＲＮＡの数が、Ｌ1個をオーバーしたら、ｔＲＮＡをランダムに選んで消去する。

20【００９３】
次に、Ｍ個のアミノ酸をＤＮＡの第３の部分のＭ個のルール番号から翻訳によって生成する（ステップＳ１２０）。翻訳は、存在しているアミノアシルｔＲＮＡの集団（アミノアシルｔＲＮＡテーブル）を用いて行なわれ、ＤＮＡ上のルール番号に一致するルール番
号を持つアミノアシルｔＲＮＡがランダムに選ばれる。それを持つアミノ酸がアミノ酸集団（アミノ酸テーブル）に加えられる。
【００９４】
このとき同様に、アミノ酸数がＭ1個をオーバーしたら、アミノ酸をランダムに選んで消す。
【００９５】30

次に、ｔＲＮＡとアミノ酸との間の分子反応処理により、アミノアシルｔＲＮＡテーブ
ルの更新を行う（ステップＳ１２２）。すなわち、ランダムに選んだｔＲＮＡのシンボルとランダムに選んだアミノ酸の始点シンボルが一致していたなら、２つを結合して１つのアミノアシルｔＲＮＡを作る。これを繰返して、Ｒ2個の新しいアミノアシルｔＲＮＡが、アミノアシルｔＲＮＡ集団に加えられたら、アミノアシルｔＲＮＡをランダムに選んで消し、アミノアシルｔＲＮＡ数がＲ1個以内になるようにする。この結果、同一のルール
番号に対して、異なる書換の対応関係（アミノ酸）が対応することも許容する。
【００９６】
次に、ＤＮＡの第１の部分のルール番号から、アミノアシルｔＲＮＡを用いた翻訳により、表現型ツリーを生成する（ステップＳ１２４）。

40【００９７】
さらに、ステップＳ１０８，Ｓ１１０，Ｓ１１２とそれぞれ同様にして、細胞の選択処理を行い（ステップＳ１２６）、ＤＮＡの突然変異処理（ステップＳ１２８）、ＤＮＡの交叉と分子交換処理（ステップＳ１３０）を行って、処理はステップＳ１１４に復帰する。
【００９８】（具体例）
化学的遺伝プログラミング処理の有用性を検証するために、単一変数の数学的な関数形をこの手続きで獲得する処理を行った。特に、ターゲット関数としては、以下のものとす
る。

50

(14)

JP 4572304 B2 2010.11.4【００９９】
ｆ（ｘ）＝２ｘ6＋３ｘ4＋４ｘ2＋１００
このような関数を、領域（−５，５）において最適化を行なう。各個体の一致度（適応度）は、以下の関数によって定義される。
【０１００】【数１】【０１０１】
ここで、ｄは、上記領域において所定の間隔をもった有限個の値の組について、生成さ10れた関数の各値と、ターゲット関数の各値との間の差の和の平方である。これらの実験のためのパラメータの値は、以下のとおりである。
【０１０２】
突然変異確率ｐmは、０．００７であり、交叉確実ｐcは０．７である。
【０１０３】
個体の数は１４３とした。
【０１０４】
図１０は、以上の条件において、最適個体と平均個体の一致度の各世代ごとの変化を表す図である。
20【０１０５】
この条件では、最適な個体は、第５８世代において現われていることがわかった。
【０１０６】
また、図１１は、最終的に得られた関数とターゲット関数との比較結果を示す図である。さらに、図１２は、細胞の中に進化したアミノ酸のヒストグラムを示す図である。
【図面の簡単な説明】【０１０７】【図１】本発明の化学的遺伝プログラミング装置１００の一例の外観を示す図である。
【図２】化学的遺伝プログラミング装置１００のハードウェア構成をブロック図形式で示す図である。

30【図３】実際の生物細胞における代謝の機構を説明するための概念図である。
【図４】化学的遺伝プログラミング処理の基本的な流れの概略を示す概念図である。
【図５】図１および図２で説明した化学的遺伝プログラミング装置１００の機能ブロック
図である。
【図６】化学的遺伝プログラミングの処理の流れを説明するための第１のフローチャート
である。
【図７】化学的遺伝プログラミングの処理の流れを説明するための第２のフローチャートである。
【図８】初期的に準備されるアミノ酸の例を示す図である。
【図９】生成される表現型ツリーの一例を示す図である。

40【図１０】最適個体と平均個体の一致度の各世代ごとの変化を表す図である。
【図１１】最終的に得られた関数とターゲット関数との比較結果を示す図である。
【図１２】細胞の中に進化したアミノ酸のヒストグラムを示す図である。
【符号の説明】【０１０８】
１００

化学的遺伝プログラミング装置、１０２

プレイ、１０６
１１２

ＦＤドライブ、１０８

マウス、１１８

ードディスク、１２８コンピュータ本体、１０４

ＣＤ−ＲＯＭドライブ、１１０

ＣＤ−ＲＯＭ、１２０

ＣＰＵ、１２２

通信インタフェース、１３０

ディス

キーボード、

メモリ、１２４

ディスプレイ。

ハ

(15)
【図１】

【図２】

【図３】

【図４】

JP 4572304 B2 2010.11.4

(16)
【図５】

【図６】

【図７】

【図８】

JP 4572304 B2 2010.11.4

(17)
【図９】

【図１０】

【図１１】

【図１２】

JP 4572304 B2 2010.11.4

(18)JP 4572304 B2 2010.11.4

フロントページの続き(74)代理人 100098316
弁理士 野田 久登(74)代理人 100109162
弁理士 酒井 將行(72)発明者 澤井 秀文
東京都小金井市貫井北町４−２−１ 独立行政法人通信総合研究所内(72)発明者 ボイツェック ピアセチェニー
京都府相楽郡精華町光台二丁目２番地２ 株式会社国際電気通信基礎技術研究所内

10(72)発明者 鈴木 秀明
京都府相楽郡精華町光台二丁目２番地２ 株式会社国際電気通信基礎技術研究所内審査官 稲垣 良一(56)参考文献 特表２０００−５０７９４０（ＪＰ，Ａ）
鈴木 秀明 他，化学的GAの提案 ‑‑ DNAコードとその翻訳方法との共進化，産業システム情報化研究会資料，社団法人電気学会，２００２年１２月 ４日，IIS‑02‑29，pp.33‑40
Hidefumi Sawai, et al.，Chemical Genetic Algorithms ‑ Coevolutionary Genotype‑Phenotype Mapping by Modelling of Metabolism in Cell，Proceedings of the IEEE 2003 Congress on
Evolutionary Computation(CEC‑2003)，IEEE，２００３年１２月１２日，Vol.1，pp.639‑646
新美 礼彦 他，オブジェクト指向を用いた決定木と ADF GP の組み合わせによる学習，知識ベースシステム研究会資料，社団法人人工知能学会，１９９９年 １月２７日，SIG‑KBS‑9802，pp.1
9‑24(58)調査した分野(Int.Cl.，ＤＢ名)
Ｇ０６Ｎ

３／１２

Ｇ０６Ｎ

３／００

ＪＳＴＰｌｕｓ（ＪＤｒｅａｍＩＩ）

20