博 士 論 文 概 要

早稲田大学大学院情報生産システム研究科

博 士 論 文 概 要

論 文 題 目

多目的遺伝的アルゴリズムによるシステム信頼 性の最適化設計に関する研究

Study on Optimal Design for System Reliability by Multiobjective Genetic Algorithms

申 請 者

椋 田 實

MUKUDA Minoru

情報生産システム工学専攻

ソフトコンピューティング研究

2005 年 4 月 氏 名

専攻・研究指導 (課程内のみ)

現 代 社 会 で は イ ン タ ー ネ ッ ト を 基 盤 と し た 各 種 業 務 シ ス テ ム が 多 数 稼 動 し て い る 。 例 え ば ， 株 式 の 売 買 を 行 う ネ ッ ト 証 券 会 社 ， 個 人 の 決 済 を 対 象 と し た ネ ッ ト 銀 行 ， 商 店 や 企 業 が 運 営 す る ネ ッ ト 通 信 販 売 ， 相 互 信 頼 で 運 用 さ れ て い る 電 子 メ ー ル シ ス テ ム( E - m a i l )な ど ， イ ン タ ー ネ ッ ト を 基 盤 と し た 情 報 シ ス テ ム で あ る 。 こ れ ら は ， 従 来 の 業 務 シ ス テ ム と の 置 き 換 え ， あ る い は 共 存 し な が ら ， 急 速 に 発 展 し て い る 。 こ の よ う な イ ン タ ー ネ ッ ト を 支 え て い る の が ， 通 信 基 盤 と な る 各 種 の 情 報 通 信 シ ス テ ム で あ る 。 特 に ， 都 市 間 を 結 ぶ 通 信 シ ス テ ム は ラ イ フ ラ イ ン の 一 つ と し て 重 要 で あ り ， こ れ ら の 情 報 シ ス テ ム は 高 速 か つ 大 容 量 の 通 信 回 線 で ， 高 信 頼 性 が 要 求 さ れ て い る 。 一 般 に ， 情 報 シ ス テ ム に 機 器 故 障 ，人 的 障 害 ，自 然 災 害 に よ る 回 線 障 害 が 発 生 し た 場 合 ， 企 業 や 個 人 は 多 大 な 損 失 を 受 け る 。 例 え ば ，E - m a i l の 基 盤 と な っ て い る 情 報 通 信 シ ス テ ム が 停 止 す る と ，E - m a i l に 依 存 し た 業 務 が 中 断 と な り ， 単 な る 停 止 で は な く ， 情 報 の 遅 延 や 欠 落 の た め に 大 き な 損 失 を 受 け る 可 能 性 が あ る 。 さ ら に ， 証 券 や 銀 行 の 業 務 シ ス テ ム は リ ア ル タ イ ム 性 の 高 い 情 報 ， す な わ ち 株 の 売 買 情 報 ， 為 替 決 済 情 報 ， 預 金 払 戻 し 停 止 情 報 や ク レ ジ ッ ト の 信 用 情 報 な ど を 取 り 扱 っ て い る 。 こ れ ら の 情 報 が も し 遅 延 し た 場 合 の 社 会 的 影 響 は 大 き い 。 こ の よ う に ， 情 報 通 信 シ ス テ ム は 現 代 社 会 の 基 盤 で あ り ， シ ス テ ム の 高 信 頼 化 設 計 問 題 は 重 要 な 研 究 課 題 の ひ と つ で あ る 。

一 般 に ， シ ス テ ム は 処 理 機 能 に よ り 複 数 の サ ブ シ ス テ ム か ら 構 成 さ れ ， さ ら に,サ ブ シ ス テ ム は 複 数 の ユ ニ ッ ト か ら 構 成 さ れ て い る 。サ ブ シ ス テ ム に は ， ハ ー ド ウ ェ ア 及 び ソ フ ト ウ ェ ア が 含 ま れ る 。 一 般 に ， シ ス テ ム の 高 信 頼 化 設 計 を 行 う 方 法 に は ， 大 き く 分 け て ２ つ の ア プ ロ ー チ が あ る 。 ひ と つ は ， 信 頼 性 の 高 い 部 品 や ユ ニ ッ ト を 使 用 す る こ と で ，“ 装 置 の 設 計 や 製 造 に お い て 構 成 要 素 に フ ォ ー ル ト が 発 生 し な い よ う に す る 方 法 ”に 基 づ く ア プ ロ ー チ で あ り ， フ ォ ー ル ト ア ボ イ ダ ン ス( F a u l t A v o i d a n c e )と 呼 ば れ て い る 。 し か し ， ユ ニ ッ ト や サ ブ シ ス テ ム の 高 信 頼 化 は 製 造 コ ス ト に 関 す る 予 算 制 約 な ど の た め ， 信 頼 度 の 高 い 部 品 や ユ ニ ッ ト の 選 択 に も 限 界 が あ る た め ， フ ォ ー ル ト の 発 生 は 避 け ら れ な い と 言 う 前 提 に 基 づ く も う ひ と つ の ア プ ロ ー チ が あ り ， フ ォ ー ル ト ト レ ラ ン ス( F a u l t To l e r a n c e ) と 呼 ば れ て い る 。 フ ォ ー ル ト ト レ ラ ン ス と は ， 付 加 装 置 や 付 加 機 能 の 影 響 を 自 動 的 に 防 ぎ ， フ ォ ー ル ト が 起 き て も シ ス テ ム と し て は 正 し い 機 能 を 保 持 さ せ よ う と す る ア プ ロ ー チ で あ る 。 こ の ア プ ロ ー チ は シ ス テ ム の 一 部 が 故 障 し て も ， 他 の 部 分 が そ の 不 具 合 を 補 い ， 全 体 と し て 正 常 に 機 能 す る よ う な 仕 組 み で あ る 。こ の 考 え 方 は 非 常 に 基 本 的 な も の で ， 大 規 模 な 通 信 シ ス テ ム に 古 く か ら 用 い ら れ て い る 。フ ォ ー ル ト ト レ ラ ン ス は ， サ ブ シ ス テ ム や ユ ニ ッ ト を 並 列 に 配 置 し ， シ ス テ ム に 冗 長 性 を 与 え る こ と に よ っ て 信 頼 性 を 向 上 さ せ る 。並 列 に サ ブ シ ス テ ム や ユ ニ ッ ト を 配 置 す る 場 合 ，

① 予 備 の サ ブ シ ス テ ム や ユ ニ ッ ト と し て 故 障 時 に 切 り 替 え る タ イ プ の も の を 待 機 冗 長 構 成 と 呼 び ， ② 並 列 化 し た サ ブ シ ス テ ム や ユ ニ ッ ト に も 同 時 に 異 な

る 仕 事 を さ せ る も の を 並 列 冗 長 構 成 と 呼 ぶ 。

本 研 究 で は ， 高 信 頼 化 シ ス テ ム を 実 現 さ せ る 手 法 と し て ， 並 列 冗 長 構 成 お よ び 待 機 冗 長 構 成 を 想 定 し て い る 。 シ ス テ ム の 高 信 頼 化 設 計 に は ， サ ブ シ ス テ ム の 容 量 や 重 量 な ど 資 源 の 制 約 下 に お い て ， 各 サ ブ シ ス テ ム の ユ ニ ッ ト を 待 機 冗 長 構 成 や 並 列 冗 長 構 成 と す る こ と で ， シ ス テ ム 信 頼 度 や 稼 働 率 を 最 大 化 す る 信 頼 性 最 適 化 設 計 問 題 と し て 扱 え る 。 こ の よ う に 信 頼 度 や 稼 働 率 を 最 大 化 す る 問 題 は 他 の 資 源 を 制 約 条 件 と す る こ と で 単 一 目 的 の 非 線 形 整 数 計 画 ( n o n l i n e a r i n t e g e r p r o g r a m m i n g : n I P ) モ デ ル と し て 定 式 化 さ れ る 。 さ ら に ， 信 頼 度 と 総 コ ス ト ，稼 働 率 と 総 コ ス ト な ど,複 数 の 資 源 が 競 合 関 係 に あ る シ ス テ ム の 設 計 問 題 は 多 目 的 な 信 頼 性 最 適 化 問 題 と な る 。 こ の よ う な 多 目 的 信 頼 性 設 計 問 題 は 多 目 的 非 線 形 整 数 計 画( m u l t i o b j e c t i v e n I P )モ デ ル と し て 定 式 化 さ れ る 。

最 適 化 設 計 問 題 を 解 く た め の メ タ ヒ ュ ー リ ス テ ィ ッ ク な 手 法 と し て ， 遺 伝 的 ア ル ゴ リ ズ ム( G e n e t i c A l g o r i t h m : G A )が 注 目 さ れ て い る 。 本 論 文 で は ， シ ス テ ム の 高 信 頼 化 設 計 に お け る 信 頼 性 最 適 化 問 題 の 手 法 と し て ， ハ イ ブ リ ッ ド 型 多 目 的 G A を 提 案 し て い る 。 ま た ， 適 応 型 ハ イ ブ リ ッ ド G A に よ り ， 単 目 的 信 頼 性 最 適 化 モ デ ル に よ る 信 頼 度 の 最 適 化 設 計 法 を 提 案 し て い る 。 さ ら に ， 多 目 的 非 線 形 整 数 計 画 モ デ ル を 解 く 手 法 と し て G A の 持 つ 多 点 探 索 と い う 特 徴 に 注 目 し ， 直 接 に パ レ ー ト 最 適 解 を 求 め る こ と を 目 的 と し た ハ イ ブ リ ッ ド 型 の 多 目 的 G A ( M u l t i o b j e c t i v e G e n e t i c A l g o r i t h m )に よ り ， 多 目 的 信 頼 性 設 計 問 題 の 解 法 を 提 案 し ， そ の 有 効 性 を 数 値 実 験 に よ り 検 証 し て い る 。 本 論 文 の 構 成 は ， 第 １ 章 で は 研 究 の 背 景 ， 第 ２ 章 で は 不 稼 働 率 に よ る シ ス テ ム 信 頼 性 モ デ ル を 明 ら か に し ，第 ３ 章 で は 多 目 的 G A の 一 方 法 を 提 案 す る 。 第 ４ 章 と 第 ５ 章 で は ，単 目 的 信 頼 性 最 適 化 問 題 に よ る 単 目 的 G A 技 法 の 提 案 ， 第 ６ 章 で は 多 目 的 信 頼 性 最 適 化 問 題 に よ る 多 目 的 G A 技 法 の 検 証 ， 第 ７ 章 で は 通 信 シ ス テ ム の 信 頼 性 最 適 化 設 計 へ の 適 用 と 多 目 的 G A 技 法 の 検 証 を 行 っ て い る 。 最 後 に ， 第 ８ 章 で は 提 案 し た 多 目 的 G A 技 法 の 効 果 に つ い て 結 論 を 述 べ る 。 次 に 各 章 の 概 要 を 説 明 す る 。

第 ２ 章 で は ， シ ス テ ム の 信 頼 度 と 稼 働 率 を 使 用 し た 信 頼 性 最 適 化 の た め の 信 頼 度 に よ る モ デ ル 構 築 方 法 を 説 明 す る 。 次 に ， 不 稼 働 率 に よ る 通 信 シ ス テ ム の モ デ ル 構 築 方 法 を 示 す 。こ れ は 故 障 の 木 解 析( F a u l t T r e e A n a l y s i s )で 使 わ れ る 最 小 カ ッ ト セ ッ ト を 用 い て ，シ ス テ ム 不 稼 働 率 の 数 学 モ デ ル を 構 築 す る 。

第 ３ 章 で は ， 多 目 的 最 適 化 問 題 を 取 り 扱 う た め の 多 目 的 G A の 一 技 法 を 提 案 す る 。 一 般 に G A は 多 点 探 索 に よ る 大 域 探 索 に は 優 れ て い る が ， 局 所 探 索 の 機 能 は 劣 っ て い る 。 こ の た め 厳 密 解 法 に 比 べ 最 終 的 に 得 ら れ る 解 の 精 度 が 劣 る 可 能 性 の 問 題 点 が あ る 。 ま た ，G A は 解 集 団 の サ イ ズ ， 最 大 世 代 数 ， 交 叉 率 ， 突 然 変 異 率 な ど の パ ラ メ ー タ を 事 前 あ る い は 状 況 に 適 応 し て 調 整 す る こ と が 必 要 で あ る 。 さ ら に ， 多 目 的 最 適 化 問 題 で は 解 が パ レ ー ト 最 適 解 と な

る こ と か ら 目 的 関 数 間 で バ ラ ン ス （ ト レ ー ド オ フ ） の 取 れ た 多 数 の 解 が 存 在 す る 。 パ レ ー ト 最 適 解 を 効 率 よ く 求 め る た め に は ， 多 目 的 に 適 し た G A 技 法 が 必 要 あ る 。 本 論 文 で は ， 多 目 的 G A の 技 法 と し て ， 選 択 手 法 は 改 良 パ レ ー ト 解 保 存 戦 略 ， 局 所 探 索 は 適 応 型 ス キ ー ム に よ る 近 傍 探 索 技 法 ， 均 等 な パ レ ー ト 最 適 解 を 求 め る た め の シ ェ ア リ ン グ 技 法 を 提 案 す る 。さ ら に ，多 目 的 G A に お い て パ レ ー ト 最 適 解 が 不 明 な 場 合 の 評 価 方 法 と し て ，弓 形 面 積 ，被 覆 率 ， パ レ ー ト 解 の 数 ， 正 規 化 し た パ レ ー ト 解 の 図 示 を 採 用 す る 。

第 ４ 章 で は ， 単 目 的 信 頼 性 最 適 化 モ デ ル を 用 い て 適 応 型 ス キ ー ム に よ る 局 所 探 索 技 法 を 提 案 し ， そ の 効 果 を 具 体 例 で 検 証 す る 。 こ の 適 応 型 ス キ ー ム と は あ る 解 が 最 適 解 の 近 傍 に あ る と 判 断 し た 場 合 ， 局 所 探 索 を 働 ら か せ る 制 御 を 行 う こ と で ， こ れ は 広 域 探 索 で 最 適 解 の 近 傍 解 を 求 め ， さ ら に 局 所 探 索 で 最 適 解 を 求 め る た め で あ る 。 局 所 探 索 は 広 域 探 索 を 抑 え る 働 き が あ る が ， こ の 抑 制 を 制 御 し て 局 所 探 索 の 効 果 を 発 揮 さ せ る の が 適 応 型 ス キ ー ム で あ る 。 第 ５ 章 で は ， 適 応 型 ハ イ ブ リ ッ ド G A を 用 い て 単 目 的 信 頼 性 最 適 化 モ デ ル に よ る 信 頼 度 の 最 適 化 設 計 を 行 う 。 ハ イ ブ リ ッ ド 型 遺 伝 的 ア ル ゴ リ ズ ム を 実 現 す る 適 応 型 ス キ ー ム は 交 叉 率 と 突 然 変 異 率 を 制 御 す る 方 法 を 提 案 し ， 数 値 実 験 に よ っ て ， そ の 有 効 性 を 検 証 す る 。

第 ６ 章 で は ， 多 目 的 G A の 技 法 の ひ と つ で あ る パ レ ー ト 解 保 存 戦 略 ， 局 所 探 索 ， 適 応 型 ス キ ー ム に よ る 交 叉 率 と 突 然 変 異 率 の 制 御 法 を 提 案 す る 。 適 応 型 ス キ ー ム に は フ ァ ジ ィ 論 理 制 御 （F L C） を 用 い て 交 叉 率 と 突 然 変 異 率 を 制 御 す る 方 法 を 提 案 す る 。 ま た ， 局 所 探 索 は 単 目 的 化 し た 評 価 値 を 用 い た 改 訂 シ ン プ レ ッ ク ス 探 索 法 を 提 案 す る 。 こ れ ら の 多 目 的 G A の 技 法 を 多 目 的 な 信 頼 性 最 適 化 問 題 の 数 値 実 験 に よ っ て ， そ の 有 効 性 を 検 証 す る 。

第 ７ 章 で は ， シ ス テ ム 不 稼 働 率 に よ る 数 学 モ デ ル の 構 築 方 法 用 い て 通 信 シ ス テ ム の 信 頼 性 モ デ ル を 構 築 す る 。 次 に 不 稼 働 率 と 総 コ ス ト を 最 適 化 の 基 準 と し て ， 通 信 シ ス テ ム の パ レ ー ト 最 適 解 を 求 め る 方 法 を 提 案 し ， 数 値 実 験 に よ っ て 多 目 的 G A の 有 効 性 を 検 証 す る 。 こ の 多 目 的 G A の 技 法 は 第 ３ 章 で 提 案 し た 技 法 を 具 体 化 し た も の で あ り ， 改 良 パ レ ー ト 解 保 存 戦 略 ， 適 応 型 ス キ ー ム を 用 い た 局 所 探 索 技 法 ， パ レ ー ト 解 を 均 等 に 分 散 化 さ せ る シ ェ ア リ ン グ 技 法 な ど で あ る 。 な お ， 数 値 実 験 に 使 用 す る 通 信 ネ ッ ト ワ ー ク モ デ ル は ， 基 本 的 な 直 並 列 接 続 の 通 信 シ ス テ ム ， ブ リ ッ ジ 接 続 の 通 信 シ ス テ ム ， 複 雑 な ネ ッ ト ワ ー ク 構 成 の 通 信 シ ス テ ム の ３ モ デ ル で ， こ れ ら の モ デ ル を 用 い て 多 目 的 G A 技 法 の 有 効 性 を 数 値 実 験 に よ り 検 証 す る 。

第 ８ 章 で は ， 多 目 的 信 頼 性 最 適 化 問 題 に 対 す る 多 目 的 G A の 有 効 性 と 今 後 の 問 題 点 に つ い て 述 べ る 。

本 論 文 で は ， シ ス テ ム の 高 信 頼 化 設 計 に お け る 信 頼 性 最 適 化 問 題 の 解 法 と し て ハ イ ブ リ ッ ド 型 多 目 的 G A を 提 案 し た 。 こ の ハ イ ブ リ ッ ド 型 多 目 的 G A を 多 目 的 信 頼 性 最 適 化 設 計 に 適 用 し ，そ の 有 効 性 を 数 値 実 験 に よ り 検 証 し た 。

研 究 業 績

種 類 別 著者、 題名、 発表・発行掲載誌名、 発表・発行年月日、 頁等

学 術 誌 原 著 論 文

査 読 の あ る 国 際 会 議・シ ン ポ ジ ウ ム 論 文

１． Minoru Mukuda, YoungSu Yun, Mitsuo Gen: Reliability Optimization Problems Using Adaptive Hybrid Genetic Algorithms, Journal of Advanced Computational Intelligence and Intelligent Informatics, Vol.8, No.4, pp.437-441, 2004

２． Minoru Mukuda, YoungSu Yun, Mitsuo Gen: Adaptive Genetic Local Search Algorithms for Solving Reliability Optimization Problems, IEEJ Trans. on Electronics, Information and Systems, Vol.124, No.10, pp.1986-1990, 2004

３． 椋田實，辻村泰寛，玄光男： FLC 制御の遺伝的アルゴリズムによる多目的シス テム信頼性最適設計, 電気学会論文誌Ｃ, Vol.125, No.4, pp.623-630, 2005

１． Minoru Mukuda, YoungSu Yun, Mitsuo Gen: Reliability Optimization Problems using Adaptive Hybrid Genetic Algorithms, Proc. of The 4^th International Symposium on Advanced Intelligent Systems, pp. 183-186, Jeju, Korea, September 25-28, 2003

２． Minoru Mukuda, YoungSu Yun, Mitsuo Gen: Adaptive Genetic Local Search Algorithms for Solving Reliability Optimization Problems, Proc. of 2003 Asia Pacific Symposium on Intelligent and Evolutionary Systems: Technology and Applications, pp. 205-209, Kitakyushu, Japan, November 21-22, 2003

３． Mitsuo Gen, Minoru Mukuda, Masao Mukaidono: Soft Computing Approach for Reliability Design Problem: State-of-the-Art Survey, Proc. of International Workshop on Reliability and its Applications, pp. 3-18, Seoul, Korea, December 3-5, 2003

４． Minoru Mukuda, Yasuhiro Tsujimura, Mitsuo Gen: Local Search Algorithm for Multiobjective System Reliability Design, Proc. of The 33^rd International Conference on Computers and Industrial Engineering, cie735 (6 pages), Jeju, Korea, March 25-27, 2004

５． Minoru Mukuda, Yasuhiro Tsujimura, Mitsuo Gen: Hybrid Genetic Algorithm for Multiobjective System Reliability Optimization Problem, Proc. of The Third International Conference on Information and Management Sciences, pp.

177-181, Dunhuang, China, June 5-10, 2004

６． Minoru Mukuda, Mitsuo Gen: Availability Optimization for Optical fiber Communication Network System by Genetic Algorithm, Proc. of The Fifth Asia-Pacific Industrial Engineering and Management Systems Conference, Papers on CD-ROM pp.32.11.1-32.11.8, Gold Coast, Australia, December 12-15, 2004

研 究 業 績

種 類 別 著者、 題名、 発表・発行掲載誌名、 発表・発行年月日、 頁等

その他(国 内 学 会 ・ 他)

著書・他

１． 椋田實，片山滋友，新藤義昭，樺澤康夫：情報処理一斉教育システムの開発，教育 システム情報学会第21回全国大会予稿集，pp.119-122，1996

２． 椋田實，市川新：モデリングのための支援環境，日本シミュレーション＆ゲーミン グ学会第8回大会予稿集，分冊，pp.35-38，1996

３． 椋田實：これからの情報処理教育環境，私立大学情報教育協会第12回情報センター 部門研修会，講演，1996

４． 市川新，椋田實，丸茂眞一：問題開発のためのゲーミング・システム・ダイナミッ クスの研究開発，財団法人科学技術融合振興財団研究助成報告書，全66p，1998 ５． 椋田實，市川新：JavaによるSDモデルのプログラム構造と仕組み，日本シミュレ

ーション＆ゲーミング学会第11回大会予稿集，pp.68-71，1999

６． 椋田實：プログラミング教育のための演習用プラットフォームⅣ，教育工学関連学 協会連合第6回全国大会予稿集, 第2分冊pp.823-824，2000

７． Yoshiaki Shindo, Hiroshi Matsuda, Minoru Mukuda, Masatoshi Abe: Programming Education Based on the Computer Graphics Animation Programming Training Kit:

WinTK, Proc. of The 4^th Global Chinese Conference on Computers in Education, Singapore, Vol.2, pp.592-597, May 29-31, 2000

８． 椋田實：情報処理一斉教育システムの開発（２），教 育 シ ス テ ム 情 報 学 会 第 2 6 回 全 国 大 会 予 稿 集 ，p p . 2 4 1 - 2 4 2，2 0 0 1

９． 片山滋友，椋田實，長田光平，阿部正平，郡千治，宮崎卓弥，中山克則：視聴覚複 合障害者のための指点字コミュニケーションシステム(1)，情報処理学会第 64 回全 国大会予稿集，第4分冊，pp.695-696，2002

１０． 阿部正平，郡千治，宮崎卓弥，中山克則，片山滋友，椋田實，長田光平：視聴 覚複合障害者のための指点字コミュニケーションシステム(2)，情報処理学会第 64 回全国大会予稿集，第4分冊，pp.697-698，2002

１１． 柿戸英広，椋田實：指点字教材と学習支援装置の開発，教育システム情報学会 第27回全国大会予稿集，pp.63-64，2002

１２． 椋田實，辻村泰寛，玄光男：多目的システム信頼性最適化のための指向性遺伝 子による局所探索法，日本経営工学会春季大会予稿集，pp.30-31，2004

１． 椋田實，市川新，小島孝治：オ フ ィ ス の コ ン ピ ュ ー タ 教 室 ， 槇 書 店 ， 全 2 1 6 p，（1 9 8 2）

２． 椋田實：は じ め て の C， 技 術 評 論 社 ， 全 2 6 3 p，1 9 8 5

３． 椋田實，佐古卓司：Cプログラムテクニック，オーム社，全227p，1 9 8 6 ４． 椋田實：C言語（上巻），技 術 評 論 社 ， 全 2 9 4 p，1 9 8 7

５． 椋田實：C言語（下巻），技 術 評 論 社 ， 全 3 1 7 p，1 9 8 8

６． 椋田實：改訂４版 はじめてのC，技 術 評 論 社 ， 全 4 0 6 p，2 0 0 1

７． 松 田 洋， 新藤 義 昭， 椋田 實 ： プ ロ グ ラ ミ ン グ 演 習 教 材 ソ フ ト ウ ェ ア W i n T K， 情 報 教 育 方 法 研 究 ，Vo l . 1 , N o . 1 , p p . 3 1 - 3 6 , 1 9 9 8