組み合わせ最適化と木最適化に対する差分進化の拡 張に関する研究

全文

(1)

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

組み合わせ最適化と木最適化に対する差分進化の拡 張に関する研究

船木, 亮平

https://doi.org/10.15017/1544003

出版情報:Kyushu University, 2015, 博士(工学), 課程博士 バージョン:

権利関係:Fulltext available.

(2)

(別紙様式2)

氏 名 :船 木 亮 平

論文題名 :組み合わせ最適化と木最適化に対する差分進化の拡張に関する研究

区 分 :甲

論 文 内 容 の 要 旨

進 化 計 算 と は 生 物 の 集 団 が 環 境 に 適 応 し て 繁 栄 す る 進 化 の 仕 組 み か ら 着 想 を 得 た 最 適 化 手 法 で あ る . 解 が ど の 程 度 優 れ て い る か を 示 す 適 合 度 を 得 る こ と が で き る 問 題 で あ れ ば 最 適 化 可 能 で あ る た め , 性 質 が 不 明 な 問 題 を 最 適 化 可 能 で あ る こ と や ア ル ゴ リ ズ ム を 変 更 せ ず に 多 く の 最 適 化 問 題 に 運 用 可 能 で あ る こ と が 利 点 で あ る . 照 明 設 計 サ ポ ー ト シ ス テ ム や 入 出 力 デ ー タ か ら の 関 数 同 定 , 人 工 内 耳 の パ ラ メ ー タ チ ュ ー ニ ン グ な ど そ の 応 用 範 囲 は 多 岐 に 渡 る .

近 年 , 実 数 値 パ ラ メ ー タ の 最 適 化 向 け の 進 化 計 算 手 法 と し て 差 分 進 化 の 研 究 が 行 わ れ て い る . 解 候 補 ( 個 体 ) は 実 数 値 ベ ク ト ル で 表 現 さ れ , 新 し い 個 体 を 作 成 す る た め に 個 体 間 差 分 ベ ク ト ル を 使 用 す る . 差 分 ベ ク ト ル は 個 体 の 変 異 幅 を 示 し て お り , 個 体 が 広 範 囲 に 分 布 し て い る 探 索 序 盤 で は 大 域 的 な 探 索 , 個 体 が 集 中 し て く れ ば 局 所 的 な 探 索 を 行 う . 差 分 を 用 い た 探 索 範 囲 の 調 整 に よ り 探 索 効 率 化 が 実 現 で き る た め , 様 々 な 問 題 に 適 用 さ れ て い る . ウ ェ ブ ペ ー ジ の レ イ ア ウ ト や 照 明 配 置 な ど の 組 み 合 わ せ 最 適 化 や , 関 数 同 定 や 画 像 変 換 フ ィ ル タ の 生 成 な ど に 応 用 で き る 木 最 適 化 向 け に 差 分 進 化 の 考 え を 取 り 入 れ る 研 究 も 行 わ れ て い る .

本 研 究 で は , 組 み 合 わ せ 最 適 化 問 題 及 び 木 最 適 化 問 題 に お け る 差 分 を 適 切 に 定 義 し , 両 最 適 化 問 題 向 け に 差 分 進 化 を 拡 張 す る . シ ミ ュ レ ー シ ョ ン に よ っ て 提 案 手 法 と 従 来 手 法 を 比 較 し , 性 能 評 価 を 行 う .

第1章 で は , 研 究 の 背 景 に つ い て 述 べ る .

第2章 で は 本 研 究 で の 差 分 進 化 拡 張 に 関 す る 基 礎 的 な 技 術 の 紹 介 を 行 う .2.1節 で は 進 化 計 算 に つ い て の 説 明 を 行 う . 進 化 計 算 で は 複 数 の 個 体 を 用 い て 最 適 化 を 行 う . 各 個 体 に 対 し て 目 的 関 数 ( 評 価 関 数 ) を 用 い て 適 合 度 を 計 算 し , そ の 情 報 を 使 っ て 新 し い 個 体 を 作 成 す る . 優 れ た 適 合 度 を 得 た 個 体 と 似 た 特 徴 を 持 つ 個 体 は 同 様 に 優 れ て い る 可 能 性 が 高 い と い う 仮 説 の も と ,優 れ た 個 体 の 近 傍 探 索 を 行 う .2.2節 で は ,進 化 計 算 を 用 い て 人 間 の 好 み や 感 性 に 合 っ た も の を 見 つ け る 対 話 型 進 化 計 算 の 説 明 を 行 う . 対 話 型 進 化 計 算 で は , ユ ー ザ か ら の 評 価 を 用 い て 最 適 化 を 行 う た め , 評 価 時 の ユ ー ザ の 疲 労 の 大 き さ が 課 題 で あ る . そ の 課 題 解 決 の た め に , よ り 高 性 能 な 進 化 計 算 手 法 を 用 い て 解 発 見 ま で の 評 価 回 数 を 減 ら す 取 り 組 み と , 評 価 イ ン タ ー フ ェ イ ス を 改 良 し ユ ー ザ へ の 負 担 を 軽 減 す る 取 り 組 み が 行 わ れ て い る .2.3節 で は

(3)

差 分 進 化 の 説 明 を 行 う . 差 分 進 化 で は 実 数 値 ベ ク ト ル で 個 体 を 表 現 し , 個 体 間 の 差 分 ベ ク ト ル を 用 い て 効 率 的 に 探 索 を 行 う . 差 分 ベ ク ト ル は 新 し い 解 候 補 を 生 成 す る 際 の 個 体 の 変 異 量 と し て 使 用 し , 差 分 ベ ク ト ル が 大 き れ ば 大 域 的 な 探 索 , 差 分 ベ ク ト ル が 小 さ け れ ば 局 所 的 な 探 索 を 行 う . こ の 特 徴 か ら , 個 体 間 の 差 分 ベ ク ト ル が 小 さ け れ ば そ れ ら の 個 体 の 適 合 度 も 近 い と い う 前 提 が 必 要 で あ る .ま た ,評 価 方 法 が2個 体 の 対 比 較 評 価 で あ る た め ,従 来 手 法 で 用 い ら れ る 全 個 体 を 比 較 し 点 数 を 与 え る 評 価 方 法 に 比 べ て 評 価 時 の ユ ー ザ 疲 労 が 少 な い と い う 特 徴 も 持 つ .

第3章 で は 組 み 合 わ せ 最 適 化 問 題 向 け に 差 分 進 化 を 拡 張 す る .3.1節 で は 従 来 手 法 で あ る 遺 伝 的 ア ル ゴ リ ズ ム (GA) に つ い て 紹 介 し ,GAの 課 題 を 考 察 す る .3.2節 で は 差 分 進 化 を 組 み 合 わ せ 最 適 化 問 題 向 け に 拡 張 し たRe-labeling Differential Evolution(RLDE) の 提 案 を 行 う . 組 み 合 わ せ 最 適 化 問 題 で は い く つ か の 対 象 の 最 適 な 組 み 合 わ せ を 探 す . 整 数 値 ベ ク ト ル で 個 体 を 表 現 す る が , そ れ ら の 整 数 値 は 対 象 を 識 別 す る た め の 番 号 で し か な い . こ の よ う な 問 題 で は 個 体 同 士 の 差 分 ベ ク ト ル は 距 離 と し て の 意 味 を 持 た な い . 差 分 進 化 で は 個 体 間 差 分 ベ ク ト ル が 小 さ け れ ば 適 合 度 の 差 も 小 さ い と い う 差 分 進 化 の 前 提 が 必 要 で あ る .RLDEで は , 個 体 分 布 情 報 か ら 優 れ た 対 象 を 推 定 し , そ れ ら の 番 号 が 近 く な る よ う に 番 号 を 割 り 振 り 直 す . そ し て ,3.3節 で は ,テ ス ト 問 題 を 用 い て 進 化 計 算 ,対 話 型 進 化 計 算 の 条 件 で シ ミ ュ レ ー シ ョ ン を 行 い , 提 案 手 法RLDEと 従 来 手 法GAを 比 較 し , 評 価 す る .100個 体 ,16個 体 の 両 条 件 で RLDEはGAに 比 べ て 優 れ た 解 を 発 見 し た . 3.4節 で 第3章 の ま と め を 行 う .

第4章 で は 木 最 適 化 問 題 向 け に 差 分 進 化 を 拡 張 す る .4.1節 で は 代 表 的 な 木 最 適 化 手 法 で あ る 遺 伝 的 プ ロ グ ラ ミ ン グ(GP)に つ い て 紹 介 し ,GPに お け る 近 傍 探 索 や 課 題 を 考 察 す る .4.2 節 で は 差 分 進 化 を 木 最 適 化 問 題 向 け に 拡 張 し た 先 行 技 術 で あ るTree Based Differential

Evolution(TreeDE)に つ い て 記 述 し ,そ の 課 題 を 明 ら か に す る .こ の 手 法 で は ,木 を 固 定 長 の 実 数 値 ベ ク ト ル と し て 表 現 す る こ と で 差 分 進 化 を 用 い た 木 最 適 化 を 実 現 し て い る . 木 に お い て ノ ー ド の 接 続 関 係 な ど の 構 造 が 適 合 度 に 大 き く 影 響 す る .し か し ,TreeDEで は 各 ノ ー ド を 独 立 に 計 算 す る た め 構 造 が 崩 れ や す い と い う 欠 点 が あ る .4.3節 で は 木 最 適 化 問 題 向 け に 差 分 進 化 を 拡 張 し たTree Structure- Based Differential Evolution(TSDE)の 提 案 を 行 う .TSDEで は 木 の 構 造 に 着 目 し て お り , 部 分 木 の 付 与 や 削 除 を も っ て 個 体 を 変 異 さ せ る . 付 与 や 削 除 す る 部 分 木 の 大 き さ を 個 体 間 差 分 に よ っ て 決 定 す る こ と で ,構 造 の 異 な る2個 体 の 差 分 は 大 き く な り ,構 造 の 似 た2個 体 の 差 分 は 小 さ く な る .こ れ に よ り ,様 々 な 構 造 の 木 が 存 在 す る 探 索 初 期 で は 大 域 的 な 探 索 を 行 い ,探 索 が 進 む と 局 所 探 索 に 移 行 す る .4.4節 で は ,関 数 同 定 問 題 を 用 い て 進 化 計 算 ,対 話 型 進 化 計 算 の 条 件 で の シ ミ ュ レ ー シ ョ ン を 行 い ,TSDEと 従 来 手 法 で あ るGP,TreeDEと の 比 較 評 価 を 行 う .100個 体 ,16個 体 の 両 条 件 でTSDEは 従 来 手 法 に 比 べ て 優 れ た 解 を 発 見 し た .対 話 型 進 化 計 算 に お い て 従 来 手 法 よ り も 疲 労 軽 減 が 期 待 で き る .4.5節 で 第4章 の ま と め を 行 う

第5章 で は ,本 論 文 の ま と め を 行 う .本 研 究 で は ,組 み 合 わ せ 最 適 化 問 題 及 び 木 最 適 化 問 題 に お い て , 差 分 進 化 の 個 体 間 差 分 を 用 い た 効 率 的 な 探 索 と 対 話 型 進 化 計 算 に お け る 評 価 時 の ユ ー ザ 疲 労 軽 減 を 目 的 と し , 差 分 進 化 の 拡 張 を 行 っ た . シ ミ ュ レ ー シ ョ ン で は 両 提 案 手 法 は 多 個 体 条 件 で 従 来 手 法 よ り も 高 い 確 率 で 大 域 的 最 適 解 を 発 見 し , 少 個 体 条 件 で は 探 索 早 期 に お い て 従 来 手 法 よ り も 優 れ た 解 を 発 見 し た . さ ら に 対 話 型 進 化 計 算 で は 対 比 較 評 価 を 利 用 す る こ と で , こ れ ま で 疲 労 が 大 き く 最 適 化 困 難 で あ っ た 問 題 に 対 し て も 最 適 化 が 可 能 と な る . こ れ に よ り , 差 分 進 化 が 適 用 で き る 現 実 問 題 の 範 囲 を 拡 大 す る こ と が で き る .

Updating...

参照

Updating...

関連した話題 :

Scan and read on 1LIB APP