博 士 （ 工 学 ） 大 倉 和 博
学 位 論 文 題 名
Design of Genetic Algorithms based onThe Neutral Theory
（ 中立 説に基 づく 遺伝的アルゴリズムの設計に関する研究）
学 位 論 文 内 容 の 要 旨
本論 文は 、 進化的探索手 法として知られる伝統的遺伝 的アルゴリズム持つ弱点を 克服しさらな る 探索 能カ を 付与すること を目的として行った研究結果 をまとめたものであり、新 らたにオペロ ンGAが提 案され、その有効性が種々の 実験を通して検証されてい る。
ホー ラン ド により提案さ れた遺伝的アルゴリズムは、 ネオダーウィニズムに基づ くいくっかの 生 物学 的知 見 を人工システ ムに組み込んで、生物進化が 本質的に持つ適応性を人工 システムに付 加 しよ うと し たものであり 、とくにこれの直接的応用分 野である解探索問題研究領 域では進化的 探 索手 法の ク ラスを構成す る。しかし、遺伝的アルゴリ ズムを探索手法と考えた場 合、それ自体 頑 強な 手法 で はあ るが 、し ばし ばGA困 難と 呼ば れ てい るク ラス の問題に対し無カ であることが 知 られ てい る 。一般に進化 的探索では、探索すべき問題 空間そのものは環境そのも のであり、あ ら かじ めそ の 性質を議論す ることはできない。すなわち 、具体的探索問題の持つ性 質を議論する こ とが 不可 能 であ り、 そこ にGA‑困 難性 の存在を予見す ることは不可能となる。従 来提案された 多 くのGAフ ん ミり では 本問 題へ の 対処 は困 難で あ る。 これ はひ いては進化的探索 手法による探 索 結果 の信 頼 性の議論にも 直接結ぴ付く。よって、いか なる場合にも導出された解 のある程度の 信頼性を 保証するようないわばロバス トなアルゴリズムの導出が 待たれれているのが現状である。
従来 のGAフ ァミりの持つ 上述の危弱性は、遺伝的アル ゴリズムは元来有限個から なる探索点集 団 を扱 うた め 、ネオダーウ イニズムに基づぃて設計され ると、それが主張する、進 化集団中には 充分な多 様性が常に存在する、とぃう 仮定が成り立たない、すな わち 未熟な収束 状態になるこ と が往 々に し ておこり、探 索が意図せず終了してしまう 悪い性質を本質的に抱えて いることに起 因 する 。こ の 問題を解決し ようと、従来、数多く遺伝的 アルゴリズムの拡張法が提 案されてきた が 、そ れら に おいてもネオ ダーウイニズムの枠組みから 外れないよう拡張が施され ている。その た め、 主た る 遺伝的操作で あると考えられている交叉法 の工夫や、選択圧を緩める ような工夫が な され るも の の、計算世代 が進むに従って多様性を失い 続けるとぃう本質的弱点を 克服できてい ないと思 われる。
この よう な 問題認識に基 づき、本論文ではネオダーウ イニズムの基本的アイデア である自然選 択 万能 主義 、 すなわち、 全ての遺伝子型内の情報は表 現型に何らかの影響を与え 、その値は自 然選択に よって集団に定まる とぃう制約を取り除いて、 表現型は遺伝子型内の一部の情報によっ て 構築 され 、 結果として、 表現型に発現しないその他の 情報は自然選択に関与しな い とした分 子進化の 中立説に基づく考え方を導入 する。
その ため 、 通常、遺伝的 アルゴリズムでは構造を持た ないバイナリ・ストリング として構成さ れ る遺 伝子 型 を、構造を持 っものとして再構成し、表現 型は活性化した遺伝子型の 一部の情報を 使って計 算されるものとする。
本論 文で 提 案す る遺 伝子 型構 造 の設 計はそのアナロ ジィを大腸菌K‑12の(1)代謝 機構を制御す る 隠密 遺伝 子 の活 性／ 不活 性機 構 の存 在と(2)特定の遺 伝子座クラスタ、すなわち 、オペロンに 対 して 起き る 遺伝的変異の 存在、とぃうニつの分子生物 学的知見に求める。これに 従うと、遺伝 子 型内 情報 の うち、表現型 に現れて目的関数に評価され るのは遺伝子型の一部に過 ぎず、現れな い ほと んど の 部分は目的関 数に対して常に中立となり、 多様性の保持が容易になる 。さらには、
目 的関 数か ら 隠れた部分が 進化過程で自己組織化される 結果、問題の特徴を捕えた 適切な遺伝的
‑ 242−
変異を生成するための 構造が獲得されることが期待される。
以上 、本 論 文で は、ホーランド の遺伝的アルゴリズムを最適 化ツールとして使用する場 合、探 索 点集 団が 多 様性 を失うに従って 、ネオダーウィニズムが仮定 している条件を満足しなく なるた め 、充 分な 探 索が 行われなくなる ことを指摘し、その解決策の ーっとして、中立説に従っ た遺伝 的 アル ゴリ ズ ムの 設計法があると 主張している。さらに、その 具体的方法論を大腸菌K‑12の代謝 を っか さど る 遺伝 子構造に動機付 けられた遺伝子型、表現型お よぴ遺伝的操作の設計法を 提案し ている。
本論文 は以下の8章から構成されて いる。
第1章 で は 序 論 と し て 、 本 研 究 の 背 景 ・ 目 的 、本 論文 の 構成 ・概 要に つ いて 述べ てい る。
第2章で は、 標準 的 遺伝 的ア ルゴ リズ ム を解 説し 、GA困 難で ある とさ れる 問 題の 諸性 質に つ い て 議 論 し て い る 。 ま た 、 そ れ ら に 対 す る 他 の 研 究 ア プ ロ ー チ を ま と め て い る 。 第3章で は、 本論 文 で必 要と なる 生物 学 に由来することがら を紹介している。ひとっは 、進化 型 計算 でし ば しば 引用される進化 論とその進化パターンであり 、もうーっは、提案手法の 動機づ け と な っ た 大 腸 菌K‑12の 代 謝 を 司 る 遺 伝 子 構 造 と そ の 分 子 生 物 学 的 知 識 で あ る 。 第4章で は、 本論 文 で提 案す る拡 張遺 伝 的ア ルゴ リズ ム をオ ペロ ンGAと名 付 け、 その 設計 原 理 と遺 伝的 ア ルゴ リズムで基本と なるバイナリ超空間での設計 詳細を述べている。また、 単純遺 伝的アル ゴリズムと比較して、その 特徴をまとめている。
第5章 で は 、GA‑困 難 と呼 ばれ る問 題 の特 性と それ に対 す る他 の拡 張遺 伝 的ア ルゴ リズ ム研 究 を簡 単に ま とめ た後 、オ ペ ロンGAを これ に適 用 した 計算 機実 験結 果を示している。取 り上げ たGA ‑困難 な 問題 は、その代表的 な問題である非定常関数問題 、騙し関数問題、超多峰性 関数問 題 、口 ング パ ス問 題である。非定 常関数問題では、オペロンの 挙動と各遺伝子座の突然変 異率の 関 係が 詳し く 調査 され、問題に適 したオペロン構造と不活性値 を獲得して隠密遺伝子機構 を創発 す るた め、 定 方向 性進化パターン を示して最適化に成功する、 と解析している。騙し問題 では、
探 索点 集団 は 自律 的に収束・拡散 を繰り返し、断続平衡進化パ ターンを生み出しているこ とが観 測され、 これが中立説のいう 進化 の緩急理論 に相当する振舞 いであると解析している。超多峰 性 問題 では 、 この 問題を困難にし ている主因の遺伝的浮動の影 響を探索能カを低下させず に抑え る ため に、 集 団分 割選択法を提案 し、その有効性を確認してい る。ロングパス問題では、 オペロ ン GAの 示 す 適 応 的 探 索 が 有 効 で あ る こ と を 計 算 機 実 験 委 よ り 実 証 し て い る 。 第7章で は、 さら に 複雑 な非 定常 関数 最 適化 問題 に対 す るオ ペロ ンGAを用 い た問 題解 決器 の 設 計と その 計 算機 実験例を示して いる。ここで、遺伝子型に表 現型の固着機能を付与し、 活性／
不 活 性 を 確 率 的 学 習 オ ー ト マ ト ン を 用 い て 制 御 す る こ と を 提 案 し て い る 。 第8章 で は 、 オ ペ ロ ンGAを い く っ か の 応 用 問 題に 適用 し た例 を示 して い る。 まず 、ジ ョブ シ ョッ プス ケ ジュ ーリング問題を 取り上げ、それぞれに適した 遺伝子型と成熟関数を用い た表現 型 の生 成法 を 示し ている。代表的 なべンチマーク問題を用いて 計算機実験を行い、他の研 究結果 と 比較 する こ とに よって、優れた 最適化能カを持っことを示し ている。また、戦略獲得問 題の例 と して 囚人 の ジレ ンマ問題を取り 上げ、これに対しても優れた 戦略の獲得に成功すること を示し ている。
第9章 では、本研究の結論として得 られた結果を総括している 。
― 243ー
