博 士 （ 情 報 科 学 ） 辻 美 和 子
学位論文題名
Designing Genetic Algorithm Based on Exploration and Exploitation of Gene Linkage
（リンケージの同定と利用に基づく遺伝的アルゴリズムの設計）
学位論文内容の要旨
遺 伝的 ア ル ゴ リ ズ ムは ブ ラ ッ ク ポッ ク ス 最 適 化を 実 現 で き るア ル ゴ リ ズ ムであ ると期 待さ れてい る ， プ ラ ック ポ ッ ク ス 最適 化 は 問題に 関す る予備 知識な しに行 をう最 適化 であり ，従来 であれ ば高 度 を 専 門 知 識に よ っ て を され た 最 適 化 アル ゴ リ ズ ム の 設計 や 調 節 を 必要 と し をい ．遺伝 的アル ゴリ ズ ム に お い て， 適 応 度 の 高い 部 分 解はビ ルデ ィング プロッ クと呼 ばれ， ビル ディン グプロ ックの 保持 お よ び 交 換 の成 否 が 遺 伝 的ア ル ゴ リ ズ ムの 成 功 の 鍵 を 握っ て い る ． 単純 遺 伝 的ア ルゴリ ズムを 用い て 効 果 的 に ピル デ ィ ン グ プロ ッ ク を 交 換す る た め に は ，互 い に 関 連 する 遺 伝 子座 がスト リング 上で 密 に 符号化 されて いる必 要が ある． そうで をいと き，交 叉は ビルデ ィング ブロッ クを 破壊する，しかし，
ピ ル デ ィ ング ブ ロ ッ ク 破壊 を 防 ぐ密を 符号 化は， 問題に 関する 事前知 識を 必要と するた め，現 実の 問 題 におい てはし ばしぱ 困難 である ．
以 上の 問 題 を 解 決 する た め に， 問題 に関す る知識 によら ず， 自動的 に問題 構造を 検出す る試 みが行 を わ れ て きた ． 同 一 の ビル デ ィ ン グ ブロ ッ ク を 構 成 する よ う 橡 遺 伝子 座 間 の依 存関係 はりン ケー ジ と 呼ぱれ ること から， これ らの手 法はり ンケー ジ同定 と呼 ばれる ．
本 論 文 で はり ン ケ ー ジ の同 定 と り ン ケー ジ 情 報 の 利 用を 行 を う 遺 伝的 ア ル ゴリ ズムの 実現に 必要 と を る以下 の2つの手 法を提 案した ．
1．適応 度差 分に基 づく分 布推定 を導 入した りンケ ージ同 定手法 2．複雑 に重 複する ビルデ ィング ブロ ックを 交換す るため の交叉 手法
提 案した りンケ ージ 同定手 法は，Dependency Detection for Distribution Derived fromfitness Dif‑
ferences (D5)と呼 ば れ ， 適 応度 差 分 に よ り 分類 さ れ た個 体の分 布推定 を用い てり ンケー ジを検 出す る.D5は ， 既 存 の り ン ケ ー ジ 手 法 で あ る 摂 動 法(PM)と 分 布 推 定 ア ル ゴ リ ズ ム(EDA)の両 方 の 特 長 を 持つ，
EDAは ， そ れ ぞれ の ビ ル デ ィン グ ブ ロ ッ クの 適 応 度 全 体 に対 す る 寄 与 が異 を る 問 題 に対 し て ， 寄 与 の 小 さ いビ ル デ ィ ン グプ ロ ッ ク に 関わ る り ン ケ ー ジを 検 出 す る こと が 困 難で ある，PMは， そのよ う を 問 題 に対 し て も り ンケ ー ジ を検出 でき るもの の，一 般的に 必要と され る計算 コスト が大き い， こ の 新 た を アイ デ ィ ア に より ，EDA困難 な 問 題 に 対し て ，PMより も 少 を い 計算 機 コ ス ト でり ン ケ ー ジ 同 定を可 能にし た．
さ ら に ， 複 雑 に 重 複 す る ビ ル デ ィ ン グ プ ロ ッ ク を 交 換 す る 手 法 と し てContext Dependent Crossover (CDC)と 呼 ば れ る 交 叉 を 提 案 し た ． 一 般 的誼 問 題 に お い ては ， ビ ル デ ィン グ プ ロ ッ ク は 完 全 分 離可 能 を 部 分 列で は を く ， 互い に 幾 っ か の 要素 を 共 有 す る重 複 構 造を 取ると 考えら れる ．
ー1437 ‑
しかし顔がら，ピルディングプロック重複を持つ問題に関する交換手法はほとんど研究されてこ教 かった．提案したCDCはfこの問題クラスに関して，現実的に使用可能顔交叉手法としては，初のも のである．
提案したりンケージ同定手法と交叉手法を遺伝的アルゴリズムに組み込み，リンケージの同定と 利用に基づく遺伝的アルゴリズムを設計した．この遺伝的アルゴリズムにおいては，リンケージ同定 はD5により行 をわれ ，得ら れたり ンケー ジ情報 に基づ ぃたピ ルディン グプロ ック交 換がCDCに よって顔される，より広い問題クラスに対してりンケージ同定が可能をD5と，より複雑教ビルディ ング プロッ ク重複 に対し て交叉 を行を うCDCによって，従来よりも広範囲の問題に適応可能を遺 伝的アルゴリズムを実現した，
さらに，ネットワーク設計問題とグラフ着色問題を用いて，設計した遺伝的アルゴリズムの実問題 における性能を評価した．特に，ネットワーク設計問題に対して，従来の単純遺伝的アルゴリズムや 重複を考慮しをいりンケージ同定遺伝的アルゴリズムと比較して高い性能を発揮することが確認さ れた．
本論文は8章から構成される．第1章では，本論文の目的，および本論文の基礎とをる概念である ブラックポックス最適化，遺伝的アルゴリズム，ビルディングプロック，加法的分解可能関数につい て述べる．第2章では，既存のりンケージ同定手法について述ベ，その問題点を議論する．第3章で は，本論文で提案した新たをりンケージ同定手法であるD5について，その概念，アルゴリズム，メカ ニズムを述ベ，数値実験によってりンケージ同定の性能を示す．第4章では，D5の計算コストの理論 的を見積もりのために，個体群サイズ決定を行をい，適切をりンケージ同定を行をうための個体数を 計算する．また、数値実験により，理論値と実験値を比較する．第5章では，実数値ベクトルに対して D5を拡張する，第6章では，重複するビルディングブロックを持つ問題に対する交叉の困難さにつ いて 述ベ， そのよ う教問 題に対 する交 叉手法 であるCDCを提案 する．数値実験によってCDCの性 能を 示す． 第7章では，D5とCDCを用いた遺伝的アルゴリズムの適用例として，ネットワーク設計 問題とグラフ着色問題に対する結果を示す，最後に，第8章で結論と今後の課題について述べる，
― 1438―
学位論文審査の要旨
学位論文題名
Designing Genetic Algorithm Based on
Exploration and Exploitation of Gene Linkage
（リンケージの同定と利用に基づく遺伝的アルゴリズムの設計）
近年の計算機性能の大幅を向上を背景として，最適化アルゴリズム研究の焦点は，従来の限定され た問題クラス毎に特化したアルゴリズムの設計から，幅広いクラスの問題を解くことのできるアル ゴリズムの設計へと移行しつっある．遺伝的アルゴリズムはそのよう教アルゴリズムのひとつであ り．実用上の観点からも注目を集めてきた．
遺伝的アルゴリズムにおいて，適応度の高い部分解はピルディングプロックと呼ばれ，その破壊を 防ぎつつ効率的に交叉を行うためには，互いに関連する遺伝子がストリング上で密に符号化されて いる必要がある．しかし，それには問題に関する事前知識を必要とするため，現実の問題において密 な符号化を保証することはしばしば困難である．これを解決するため，リンケージと呼ばれる同一の ビルディングブロックを構成する遺伝子座間の依存関係を問題に関する知識を使わずに検出する，
リンケージ同定と呼ぱれる手法が開発されてきた．本論文は，より効率的に問題構造を同定するため のりンケージ同定手法，および得られたりンケージをもとにした効果的を交叉手法について提案し ている．
前者については，適応度差分に基づぃて分類された個体の分布を推定するりンケージ同定手法を 提案した．事前に問題構造が不明を一般的な問題に対してりンケージを検出する手法として，遺伝子 集団内の分布を推定する確率モデル構築型の遺伝的アルゴリズム，および遺伝子の摂動による適応 度の変化量をもとに検出を行う摂動法によるりンケージ同定手法が主をアプローチとしてあげられ る．本論文で提案された手法はそれら既存の手法の核とをるメカニズムを組み合わせたものであり，
摂動により得られた適応度差分の分布からモデルを構築する手法である．それにより，全体の適応度 への寄与度合いに格差がある複数のビルディングプロックを持つ問題に対しても正確にりンケージ が同定できるとともに，計算量のオーダーを従来手法よりも削減することができる．結果として提案
‑ 1439―
清 志
彰 弘
晴
正 昌
正 雅
間
川
井
田
朝
赤
古
高
水
棟
授
授
授
授
搬
教
教
教
教
助
査
査
査
査
査
主
副
副
副
副
手法により，従来はりンケージ同定が困難であった問題に対して，従来手法よりも少をい計算コスト で正しいりンケージを検出することが可能とをった，
後者については，ビルディングブロックどうしが互いに重複する問題を解くことのできる交叉手 法を提案した，このようを問題では，リンケージ同定や事前知識により問題構造がわかっていたとし ても，適切をビルディングプロック交換はしばしば困難である．実際の多くの問題は単純をピルディ ングブロックへの分割が困難であるにも関わらず，そのような問題に対する交叉手法はほとんど研 究されてこ顔かった，提案手法においては，実際に交叉が行われる個体ベアの遺伝子を検査し，ビル ディングプロックが破壊されるかどうかを個別に判断することで，従来手法よりも効果的を交叉を 実現することができる．本研究で提案した交叉手法は，ビルディングブロックどうしの重複が複雑教 場合にも適用できる，最初の実用的をアルゴリズムであるといえる．
これら提案されたりンケージ同定手法および重複するビルディングプロックの交換手法を遺伝的 アルゴリズムに組み込むことで，少ない計算コストでりンケージ情報を正しく同定するとともに，複 雑をりンケージ情報を活用した効果的をビルディングプロック交換を行うことができ，結果として 従来よりも幅広い問題に対して効率的教最適化を行をうことが可能とをった．本論文においては，複 雑に重複するりンケージ構造を有するテスト問題，および様々を制約条件を有するネットワーク設 計問題に提案手法を適用し，その有効性を確認している．
これを要するに，著者は，広範囲の問題に適用可能を遺伝的アルゴリズムの開発に関して新知見を 得たものであり，最適化アルゴリズムの発展に貢献するところ大をるものがある，よって著者は，北 海 道 大 学 博 士 （ 情 報 科 学 ） の 学 位 を 授 与 さ れ る 資 格 が あ る も の と 認 め る ．
―1440ー
