早稲田大学大学院 情報生産システム研究科
博士論文審査報告書
論 文 題 目
多目的遺伝的アルゴリズムによるシステム信頼性 の最適化設計に関する研究
Study on Optimal Design for System Reliability by Multiobjective Genetic Algorithms
申 請 者
椋 田 實
MUKUDA Minoru
情報生産システム工学専攻 ソフトコンピューティング研究
2005 年 6 月
現代社会ではインターネットを基盤とした各種業務システムが多数稼動している。例えば，株式の売買を 行うネット証券会社，個人の決済を対象としたネット銀行，商店や企業が運営するネット通信販売，相互信 頼で運用されている電子メールシステム(E-mail)などのインターネット技術を基盤とした情報システムである。
これらは，従来の業務システムとの置換え，あるいは共存しながら急速に発展している。このようなインター ネットを支えているのが，通信基盤となる各種の情報通信システムである。特に，都市間を結ぶ情報通信シ ステムはライフラインの一つとして重要であり，高速・大容量かつ信頼性の高い通信回線が要求されている。
一般に，情報通信システムに機器故障，人的障害，自然災害に伴う回線障害が発生した場合，企業や個 人は多大な損失を受ける。このように，情報通信システムは現代社会の基盤であり，システムの高信頼化設 計問題は重要な研究課題の一つである。
一般に，システムは機能的に複数のサブシステムから構成され，更にサブシステムは複数のユニットから 構成されている。システムの高信頼化設計を行う方法には，２つのアプローチがある。一つは，信頼性の高 い部品やユニットを使用することで，「装置の設計や製造において構成要素にフォールトが発生しないよう にする方法」に基づくアプローチで，フォールトアボイダンス(Fault Avoidance)と呼ばれている。しかし，ユ ニットやサブシステムの高信頼化は製造コストに関する予算制約などにより，信頼度の高い部品やユニット の選択にも限界があるため，「フォールトの発生は避けられない」と言う前提に基づくもう一つのアプローチ があり，これはフォールトトレランス(Fault Tolerance) と呼ばれている。フォールトトレランスは，サブシステ ムやユニットを並列に配置し，システムに冗長性を与えることによってシステムの信頼性を向上させる。
本研究では，高信頼化システムを実現させる手法として，並列冗長構成および待機冗長構成を想定して いる。システムの高信頼化設計は，サブシステムの容量や重量など資源の制約下において，各サブシステ ムのユニットを待機冗長構成や並列冗長構成にすることで，システム信頼度や稼働率を最大化する信頼性 最適化設計問題として取り扱える。このようにシステムの信頼度あるいは稼働率を最大化する問題は他の 資源を制約条件とすることで，単一目的の非線形整数計画(nonlinear integer programming: nIP) モデ ルとして定式化される。更に，信頼度と総コスト，稼働率と総コストなど，複数の資源が競合関係にあるシス テム設計問題は多目的信頼性最適化問題となる。このようなシステム信頼性設計問題は，多目的非線形整 数計画(multiobjective nIP)モデルとして定式化される。
最適化設計問題を解くためのメタヒューリスティクな手法として，遺伝的アルゴリズム(Genetic Algorithm:
GA)が注目されている。本論文では，システムの高信頼化設計における信頼性最適化問題の手法として，
ハイブリッド型多目的GAを提案している。更に，多目的非線形整数計画モデルを解く手法としてGAの持つ グローバルな多点探索という特徴に注目し，直接パレート最適解を求めることを目的としたハイブリッド型の 多目的GA(Multiobjective Genetic Algorithm)により，システム信頼性設計問題の解法を提案し，その有効 性を数値実験により検証している。
第１章「序論」では研究の背景と目標について，通信システムの高信頼化の重要性と，システムの信頼性 最適設計を実現するための多目的GAの有用性を述べている。また，単目的の信頼性最適化設計から多 目的の信頼性最適化設計へのプロセスを紹介し，本研究の意義を明確に示している。
第２章「システム信頼性最適化設計」では，システムの信頼度と稼働率を使用した信頼性最適化モデルと 構築方法について述べている。信頼度のモデル定式化は，Kuo氏等が提案している手法を採用しており，
また不稼働率による通信システムのモデル化に関して，その構築方法を概説している。この手法は故障の
木解析(Fault Tree Analysis)で用いる最小カットセットにより，システムの不稼働率の数学モデルを構築す るもので，複雑な通信ネットワームシステムにも適応が可能な方法である。
第３章「多目的遺伝的アルゴリズム」では，多目的最適化問題を取り扱うための多目的GAについて，いく つかの技法を提案している。一般に GA はグローバル多点探索による大域探索には優れているが，局所 探索（Local Search: LS）の機能は劣っている。このため従来の厳密解法に比べ最終的に得られる解精度 が劣る可能性の問題点がある。また，GA は解集団のサイズ，最大世代数，交叉率，突然変異率などのパ ラメータを事前あるいは状況に適応して調整することが必要である。更に，多目的最適化問題では解がパ レート最適解となることから，目的関数間でバランス（トレードオフ）の取れた多数のパレート最適解が存在 する。このパレート最適解を効率よく求めるためには，多目的最適化問題に適したGA技法が要求される。
本論文は，多目的 GA の技法として選択手法は改良パレート解保存戦略，局所探索は適応型スキーム によりパレート解のエッジ部分の探索法，局所探索自身は多方向の解を探索する指向性遺伝子法，多様 なパレート解を求めるためのシェアリングによる評価値の均等分散化を提案している。この提案により，パレ ート最適解の数が多数生成され，高い探索効率を実現している。更に，多目的 GA においてパレート最適 解が不明な場合の評価方法として，弓形面積，被覆率，パレート解の数，正規化したパレート解の図示を 採用している。
第４章「適応型局所探索GAによる信頼性最適化設計」では，LSが強く働いた場合，局所解に落ち込 むことを抑制するための手法として，単目的信頼性最適化モデルを用いた適応型スキームによる局所探索 技法を提案し，その効果を具体例で検証している。この適応型スキームとはある解が最適解の近傍にあると 判断した場合，局所探索を機能させることである。これは広域探索により最適解の近傍解を求め，更に局所 探索により最適解を求める手法である。要するに，局所探索は広域探索を抑える働きがあり，この抑制を制 御して局所探索の効果を発揮させるのが適応型スキームである。
第５章「適応型ハイブリッドGAによる信頼性最適化設計」では，適応型ハイブリッドGAを用いて単 目的信頼性最適化モデルによる信頼度最適化設計を取り扱っている。ハイブリッド型遺伝的アルゴリズムを 実現する適応型スキームとは親集団の適合値の増加や減少などの傾向を検知し，ファジィ論理制御 (Fuzzy Logic Controller: FLC)を用いて交叉率と突然変異率を制御する方法である。従来の手法では探 索にバラツキがあったが、提案手法では20回の全ての試行で最適解を求めることが確認でき，その 有効性を検証している。
第６章「多目的GAによる多目的システムの信頼性最適化設計」では，多目的GAの技法の一つであ るパレート解保存戦略，適応型スキームによる交叉率と突然変異率の制御法，改訂シンプレックス法を組み 入れた局所探索を提案している。適応型スキームにはFLCを用いて，親集団の適合値の増加や減少を入 力として交叉率と突然変異率を制御する方法を提案している。これらの多目的GA技法は従来の手法に対 して，理想最適解とのユークリッド距離の短縮と計算時間の大幅な短縮が数値実験によって確認でき，
その有効性を検証している。
第７章「多目的 GA による通信システムの信頼性最適化設計」では，システム不稼働率による数学モ デルの構築方法を用いて通信システムの信頼性モデルを定式化している。次に，不稼働率と総コストを最 適化の基準として，通信システムのパレート最適解を求める方法を提案し，数値実験によって多目的GAの 有効性を検証している。この多目的GAの技法は第３章で提案した技法を具体化したものであり，改良パレ
ート解保存戦略，適応型スキームを用いた局所探索技法，パレート解を均等に分散化させるシェアリング技 法が基本となっている。数値実験に使用する通信ネットワークモデルは，基本的な直並列接続の通信シス テム，ブリッジ接続の通信システム，複雑なネットワーク構成の通信システムの３モデルであり，これらのモデ ルを用いてパレート解の分布の多様化、最適解数の増加、解のエッジ部分の探索能力の改善が数値 実験により確認でき，その有効性を検証している。なお，評価指標は，弓形面積，被覆率，パレート解の数，
正規化したパレート解の図示を用いている。
第８章「結言」では，システムの高信頼化設計における多目的信頼性最適化問題の解法として，ハイブリ ッド型多目的GAによる研究成果に関する結論と今後の課題を総括している。
以上を要約すると，本博士論文では多目的GAのための幾つかの技法を多目的信頼性最適化設計 問題に適用し，その有効性を数値実験により検証している。主な多目的GAの技法は，改良パレー ト解保存戦略，適応型スキームによる局所探索，適応型スキームによる交叉と突然変異，シェアリ ングによるパレート最適解の多様化である。これらの提案した多目的GAの技法はパレート解探索 に大きな効果が得られており，次の２つの技法は特記すべき効果があった。
改良パレート解保存戦略：この戦略は多目的GAの基本的な技法と言え，パレート解の探索に大 きな効果が得られた。従来のパレート解保存戦略と比較して，この戦略の効果は大きい。パレート 解保存戦略と基本的な構成は同じであるが，保存する解候補群が異なり，現世代のパレート解を蓄 積する方式であり，パレート解数の増加率が大きく，この解数の多さがパレート解の多様性を維持 すると共に，シェアリングとの相乗効果で高い探索効率を実現している。
適応型スキームによる局所探索：多目的GAのLS 用適応型スキームは，単目的GAの適応型ス キームとは異なり，パレート解の多様性(均等な分布)の要求を実現するために，シェアリング度を 使用して，パレート解の少ない部分を集中的に探索するスキームとしている。また，局所探索は多 目的用に提案した指向性遺伝子法を用いている。この適応型スキームは局所探索の短所である広域 探索を阻害する働きを抑制し，パレート解の多様性を改善しながら，よりエッジ側近傍の解を求め るのが目的である。この点の有効性は数値実験により確認された。
従来の多目的GAと比較して，多数のパレート解を効率よく求めるために，改良パレート解保存戦略を提 案し，その有効性を数値実験で検証している。また，詳細な探索を実現するために広域探索と局所探索を バランス良く行うための効率的な遺伝的アルゴリズムを研究し，局所探索法と適応型スキーム法を組み合せ た多目的ハイブリッド型遺伝的アルゴリズムを提案している。更に，通信システムの高信頼化設計問題に適 用し，数値実験によって有効性を検証している。よって，本論文は博士(工学)の学位論文として価値ある ものと認める。
2005年6月13日 審査員
主査 早稲田大学 教授 工学博士（工学院大学） 玄 光 男 早稲田大学 教授 工学博士（九州大学） 平澤 宏太郎 早稲田大学 教授 工学博士（東京大学） 松山 久義 早稲田大学 教授 博士(工学)(東京工業大学） 大貝 晴俊
