博士論文審査結果報告書

1

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

博士論文審査結果報告書

論   文   題   目

A Study on DNA Computation Model to Solve Combinatorial Optimisation Problems

申    請    者 ABU BAKAR Rohani

情報生産システム工学専攻 経営工学研究

２ ０ １ ０ 年   ６ 月

2

D N A コ ン ピ ュ ー テ ィ ン グ は 化 学 反 応 に よ る 超 並 列 計 算 が 可 能 で あ り 、 計 算 時 間 の 指 数 関 数 的 増 大 を 防 ぎ 、 組 合 せ 問 題 を 短 時 間 で 解 く 方 法 と し て 原 理 的 に 有 効 で あ る 。D N A コ ン ピ ュ ー テ ィ ン グ の 研 究 は 、 大 き く 分 け る と 、( 1 ) Ｄ Ｎ Ａ 化 学 反 応 プ ロ セ ス の 自 動 化 の 研 究 、( 2 )新 し い バ イ オ 化 学 手 法 の 研 究 、 ( 3 )個 別 の 問 題 の 計 算 ア ル ゴ リ ズ ム の 研 究 、 さ ら に ( 4 )化 学 反 応 の 信 頼 性 に 関 す る 研 究 を あ げ る こ と が で き る 。 具 体 的 な 組 合 せ 問 題 の 最 適 解 を 求 め る ア ル ゴ リ ズ ム を 開 発 す る に は 、 問 題 の タ イ プ に 応 じ た D N A コ ー デ ィ ン グ を 工 夫 す る こ と が 必 要 で あ る 。 本 論 文 で は 、 計 算 ア ル ゴ リ ズ ム に つ い て 、 ク ラ ス タ リ ン グ 、 ス ケ ジ ュ ー リ ン グ 、 証 拠 推 論 の 3 タ イ プ の 組 合 せ 問 題 を 対 象 と し 、 良 質 な 解 を 効 率 的 に 求 め る D N A コ ー デ ィ ン グ 方 法 と 計 算 ア ル ゴ リ ズ ム を 提 案 し て い る 。 そ れ ら の 具 体 的 な 例 題 と し て 配 送 セ ン タ ー 位 置 決 定 、 フ レ キ シ ブ ル 生 産 ケ ジ ュ ー リ ン グ 、 故 障 診 断 の 問 題 に つ い て シ ミ ュ レ ー シ ョ ン 実 験 で 解 き 、 計 算 ア ル ゴ リ ズ ム の 有 効 性 を 示 し て い る 。

以 下 に 各 章 を 概 括 し て 、 本 論 文 の 評 価 を 述 べ る 。

第 1 章 は 、 序 論 と し て 、D N A コ ン ピ ュ ー テ ィ ン グ の 歴 史 と そ の 研 究 に つ い て 概 観 し 、D N A コ ン ピ ュ ー テ ィ ン グ の 問 題 点 を 述 べ て い る 。

D N A ア ル ゴ リ ズ ム の 困 難 な 点 は 、 数 値 の 表 現 と そ の 演 算 で あ る 。D N A コ ー デ ィ ン グ は 4 種 類 の D N A 塩 基(ア デ ニ ン 、 グ ア ニ ン 、 シ ト シ ン 、 チ ミ ン) か ら 構 成 し 、D N A 塩 基 の 数（ コ ー デ ィ ン グ の 長 さ ）を 数 値 表 現 に 用 い て い る 。 現 在 の D N A コ ン ピ ュ ー テ ィ ン グ で は 積 ・ 除 演 算 を 行 え な い た め 、D N A の 計 算 ア ル ゴ リ ズ ム に は 加 減 算 や ソ ー テ ィ ン グ な ど の 限 ら れ た 処 理 を 用 い て ア ル ゴ リ ズ ム を 作 成 し て い る 。

第 2 章 で は 、D N A コ ン ピ ュ ー テ ィ ン グ の 計 算 ア ル ゴ リ ズ ム に つ い て 各 章 で 用 い る バ イ オ 化 学 手 法 を 説 明 し て い る 。D N A コ ン ピ ュ ー テ ィ ン グ で は 、Ｄ Ｎ Ａ 塩 基 の サ イ ズ が 1 n m よ り 小 さ い こ と を 利 用 し て 、試 験 管 の 中 の バ イ オ 化 学 反 応 で 膨 大 な 量 の 全 可 能 解 を 超 並 列 的 に 生 成 で き る 。D N A ア ル ゴ リ ズ ム は 、 全 可 能 解 を 生 成 す る 部 分 と 、 そ の 可 能 解 集 合 か ら 目 的 に 最 も 適 し た 解 を 選 ぶ 部 分 か ら 構 成 さ れ て い る 。 特 に 本 論 文 の コ ー デ ィ ン グ は 、 バ イ オ 化 学 反 応 が 保 証 さ れ て い る 、生 物 の 持 つ D N A シ ー ク エ ン ス を コ ー ド と し て 用 い て い る 。 第 3 章 で は 、 ク ラ ス タ リ ン グ 問 題 を 扱 っ て い る 。D N A コ ン ピ ュ ー テ ィ ン グ に よ る ク ラ ス タ リ ン グ 手 法 は 最 近 ま で 研 究 さ れ て い な い 。 そ の 大 き な 理 由 は 膨 大 な 計 算 処 理 を 行 う 上 で 、 そ の ア ル ゴ リ ズ ム が 複 雑 で あ る こ と 、 対 象 の 数 値 表 現 が 困 難 で あ る こ と 、 さ ら に 用 い る 数 値 演 算 が 限 ら れ て い る こ と 、 で あ る 。

本 章 で は 、 扱 う 数 値 情 報 を 順 序 数 で 表 現 す る こ と を 提 案 し て い る 。 速 度 勾 配 法 と 呼 ば れ る D N A の 長 さ に 基 づ く 方 法 を 用 い て い る 。 し か し 順 序 数 を 用 い て も D N A の 長 さ が サ ン プ ル の 数 と と も に 長 く な り 、 結 果 的 に 膨 大 な 長 さ の D N A シ ー ク エ ン ス を 扱 う こ と に な る 。 膨 大 な 量 の 数 値 を D N A シ ー ク エ ン ス 長 で 表 現 す る こ と は 効 率 的 で な い 。 こ の 欠 点 を 解 消 す る た め に グ ア ニ ン

3

の 含 有 数 に よ っ て 融 点 温 度 が 異 な る こ と を 利 用 し た 温 度 勾 配 法 を 用 い た ア ル ゴ リ ズ ム も 提 案 し て い る 。 一 定 長 の D N A コ ー ド を 用 い 、 リ ア ル タ イ ム ポ リ メ ラ ー ゼ 連 鎖 反 応( P C R )で 用 い ら れ る 蛍 光 強 度 の 急 変 す る 温 度 で あ る 融 点 温 度 の 相 違 で 、 各 デ ー タ の 評 価 を 行 う 方 法 で あ る 。 本 章 で は 、 こ の 方 法 を 用 い る こ と で D N A コ ー デ ィ ン グ の 総 長 を 抑 え た ア ル ゴ リ ズ ム を 構 成 す る こ と に 成 功 し て い る 。

本 手 法 の 計 算 複 雑 度 は 線 形 で あ る 。 通 常 の ク ラ ス タ リ ン グ で は O ( n²l o g n ) の オ ー ダ で あ る の に 対 し 、D N A コ ン ピ ュ ー テ ィ ン グ で 提 案 し た ア ル ゴ リ ズ ム で は O ( n )で あ る 。 こ こ で 、 ｎ は サ ン プ ル 数 で あ る 。 ち な み に 、1 0 億 サ ン プ ル の D N A コ ン ピ ュ ー テ ィ ン グ の 計 算 量 は 、1 0⁹C0 で 、 通 常 の ク ラ ス タ リ ン グ で は 、2 . 1・1 0^{1 9}C１に な る 。 こ こ で 、C0 と C１は 定 数 で あ る 。

第 4 章 で は 、 サ ン プ ル 値 の 変 化 に 対 す る 第 3 章 の ク ラ ス タ リ ン グ の 頑 健 性 を 分 析 し て い る 。 サ ン プ ル 値 に ラ ン ダ ム な 変 化 を 与 え た 場 合 の ク ラ ス タ リ ン グ の 変 化 を シ ミ ュ レ ー シ ョ ン 実 験 で 検 証 し 、D N A ク ラ ス タ リ ン グ の 頑 健 性 が 従 来 の 手 法 と 比 較 し て 高 い こ と を 示 し た 。 順 序 数 を 用 い る 場 合 に は デ ー タ の 変 化 が サ ン プ ル の 順 序 を 変 化 さ せ な い 限 り ク ラ ス タ リ ン グ に 影 響 を 与 え な い た め 、 こ の 頑 健 性 が 得 ら れ る 。 デ ー タ の 外 乱 が 避 け ら れ な い 実 際 の バ イ オ 化 学 プ ロ セ ス の 頑 健 性 の 向 上 は 、 第 3 章 で 提 案 さ れ た ア ル ゴ リ ズ ム の 実 用 性 に と っ て 重 要 な 性 質 で あ る と 、 評 価 で き る 。

第 5 章 で は 、 ク ラ ス タ リ ン グ の 手 法 を 応 用 し て 物 流 配 送 問 題 を 解 く 方 法 を 提 案 し て い る 。 す な わ ち 、n 顧 客 に 対 し て 配 送 セ ン タ ー 数 K が 与 え ら れ た 場 合 に そ れ ら の 配 送 セ ン タ ー の 設 置 位 置 を 決 定 し 、 ど の 配 送 セ ン タ ー か ら 資 材 や 商 品 を n 顧 客 に 効 率 的 に 配 送 す る か を 決 定 し て い る 。 こ の 問 題 は サ プ ラ イ チ ェ ー ン シ ス テ ム の 管 理 問 題 で 重 要 で あ る 。 こ こ で は 近 似 解 を 得 る た め に 単 位 長 を D N A の １ 単 位 で 表 現 し て い る 。 す な わ ち 、 上 述 し た 順 序 数 を 割 り 当 て る と き １ 単 位 で 一 定 区 間 を 表 現 す る こ と で 近 似 処 理 が 可 能 で あ る 。 こ の 方 法 を 用 い る こ と で 、 １ 単 位 区 間 L の 近 似 精 度 で 問 題 を 解 く こ と が で き る 。 こ の 計 算 の 誤 差 の 最 大 値 は ( L / 2 ) × n と な る 。 大 規 模 な 配 送 セ ン タ ー の 問 題 を 解 く 方 法 を 提 案 し た 点 で 実 用 的 な 意 味 が あ る 。

第 6 章 で は 、 フ レ キ シ ブ ル 生 産 シ ス テ ム の ス ケ ジ ュ ー リ ン グ 問 題 を 扱 っ て い る 。 特 に 、 ロ ボ ッ ト の 生 産 ス ケ ジ ュ ー ル を 解 い て い る 。 す な わ ち 、 複 数 の 作 業 台 と 複 数 の 部 品 台 を 可 動 ロ ボ ッ ト が 作 業 す る 1 ロ ボ ッ ト 生 産 シ ス テ ム と 、 複 数 ロ ボ ッ ト 生 産 シ ス テ ム の 例 と し て 平 面 上 に 配 置 さ れ た 2 ロ ボ ッ ト 生 産 シ ス テ ム の 最 適 ス ケ ジ ュ ー リ ン グ を 扱 っ て い る 。

こ こ で は ロ ボ ッ ト 間 の コ ン フ リ ク ト は 考 慮 し て い な い 。 各 作 業 台 と 部 品 台 の D N A コ ー デ ィ ン グ を 定 義 し 、 ロ ボ ッ ト の 移 動 距 離 の D N A コ ー デ ィ ン グ を 与 え 、 部 品 台 と 作 業 台 、 作 業 台 間 、 部 品 台 間 の ロ ボ ッ ト の 移 動 距 離 を 含 ん だ D N A コ ー デ ィ ン グ を 定 義 し て い る 。 ま た 、 複 数 部 品 が 同 一 部 品 台 に あ る と き に は 同 一 部 品 台 間 の 距 離 ０ の シ ー ク エ ン ス を 用 い る こ と で 解 決 し て い る 。 作 業 台 で は 作 業 時 間 の 長 さ を 示 す D N A コ ー デ ィ ン グ を 用 い て い る 。 コ ン プ

4

リ メ ン ト D N A シ ー ク エ ン ス を 定 義 し 、 エ ン ザ イ ム と 反 応 さ せ る こ と で 、 す べ て の 可 能 解 D N A 二 重 ら せ ん が 生 成 さ れ る 。 全 可 能 解 を 含 む 溶 液 か ら 、 要 求 条 件 を 満 た す 解 D N A 二 重 ら せ ん を 抽 出 し 、 最 後 に 電 気 泳 動 法 で 最 適 解 を 抽 出 で き る こ と を シ ミ ュ レ ー シ ョ ン 実 験 で 示 し た 。

比 較 す る 上 で 全 探 索 解 を 求 め る た め 、 こ こ で は 比 較 的 小 さ な 規 模 の 問 題 を 解 い て い る が 、 大 規 模 な 複 数 ロ ボ ッ ト の 最 適 ス ケ ジ ュ ー リ ン グ を 原 理 的 に 抽 出 で き る こ と を 示 し た こ と は 評 価 で き る 。

第 7 章 で は 、 組 み 合 わ せ 計 算 に 基 づ く 証 拠 推 論 の 問 題 を 解 く D N A ア ル ゴ リ ズ ム を 提 案 し て い る 。証 拠 推 論 の 基 礎 で あ る D e m p s t e r - S h a f e r が 提 案 し た 証 拠 理 論 で は 部 分 集 合 に 与 え ら れ た 確 率 測 度 （ 基 本 確 率 と 呼 ぶ ） を 用 い 、 対 象 サ ン プ ル の 上 界 確 率 と 下 界 確 率 を 評 価 で き る 。 こ れ ら の 計 算 は 組 合 せ 計 算 と な る た め 、 サ ン プ ル 数 が 多 い と き に は 膨 大 な 計 算 が 必 要 に な る 。 こ の 問 題 を 解 く た め に Ｄ Ｎ Ａ シ ー ク エ ン ス を 用 い た 計 算 ア ル ゴ リ ズ ム を 提 案 し て い る 。 全 探 索 解 が 分 か っ て い る 簡 単 な 故 障 診 断 の 問 題 を 用 い て 最 適 解 の 抽 出 を 示 し た こ と は 、 こ の 方 法 の 実 用 性 へ の 道 を 開 い た 点 で 評 価 で き る 。

第 8 章 で は 、 本 論 文 で 提 案 し 比 較 評 価 を 行 っ た D N A ア ル ゴ リ ズ ム に 関 す る 研 究 を 総 括 し て い る 。

以 上 、本 論 文 は 、D N A 化 学 反 応 を 用 い た 組 合 せ 最 適 化 問 題 を 解 く D N A コ ー デ ィ ン グ 法 と 計 算 ア ル ゴ リ ズ ム を 提 案 し た も の で あ り 、 ク ラ ス タ リ ン グ 、 ス ケ ジ ュ ー リ ン グ 、 証 拠 推 論 の 問 題 に つ い て D N A 計 算 ア ル ゴ リ ズ ム を 提 案 し て い る 。 シ ミ ュ レ ー シ ョ ン に よ っ て 、 こ れ ら の 手 法 が ク ラ ス タ リ ン グ で は 良 質 な 解 を ス ケ ジ ュ ー リ ン グ と 証 拠 推 論 で は 真 の 最 適 解 を 得 る こ と を 示 し 、 そ の 有 効 性 を 確 認 し て い る 。さ ら に 、D N A コ ン ピ ュ ー テ ィ ン グ で は 従 来 の 計 算 手 法 の 処 理 時 間 に 比 べ て 十 分 良 い 結 果 が 得 ら れ る こ と を 示 し て い る 。ま た 、 本 ク ラ ス タ リ ン グ 手 法 が 頑 健 性 に お い て 優 れ て い る こ と を 示 し た 。

今 後 は 実 用 化 に 向 け て 、( 1 )自 動 的 に 稼 働 す る D N A コ ン ピ ュ ー テ ィ ン グ ・ プ ロ セ ス を 開 発 す る こ と が 必 要 で あ る 。 ま た 、( 2 ) D N A の 化 学 反 応 を も と に 行 わ れ て い る の で 、 開 発 さ れ た ア ル ゴ リ ズ ム に 関 す る 化 学 反 応 の 信 頼 性 を 研 究 す る こ と も 重 要 で あ る 。

本 論 文 は D N A コ ン ピ ュ ー テ ィ ン グ の 組 合 せ 問 題 を 解 く 基 礎 と な る ア ル ゴ リ ズ ム を 提 案 し て い る 点 で 、 こ れ ら の 問 題 を 扱 う 経 営 工 学 や オ ペ レ ー シ ョ ン ズ リ サ ー チ 、 等 の 発 展 、 さ ら に D N A コ ン ピ ュ ー テ ィ ン グ の 発 展 に 寄 与 す る と こ ろ が 大 で あ る 。 よ っ て 、 本 論 文 は 博 士 （ 工 学 ） の 学 位 論 文 と し て の 価 値 あ る も の と 認 め る 。

2 0 1 0 年 6 月 １ 日

主 査   早 稲 田 大 学   教 授   工 学 博 士 （ 大 阪 府 立 大 学 ） 和 多 田 淳 三         早 稲 田 大 学   教 授   工 学 博 士 （ 東 京 工 業 大 学 ） 村 田   智 洋         早 稲 田 大 学   教 授   工 学 博 士 （ 早 稲 田 大 学 ） 吉 江   修         早 稲 田 大 学   教 授   博 士 （ 工 学 ）（ 大 阪 大 学 ） 吉 村   猛