• 検索結果がありません。

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

N/A
N/A
Protected

Academic year: 2022

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

Copied!
3
0
0

読み込み中.... (全文を見る)

全文

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

参照

関連したドキュメント

しかしマイクロカーネルをベースとするシステムは、カーネル

Title 土壤微生物学的にみた稚苗立枯病の研究( Abstract_要旨 ) Author(s) 赤井, 龍男 Citation 京都大学 Issue Date 1960-06-21 URL http://hdl.handle.net/2433/210724 Right.

[r]

Title Some polynomials on trice (Algebraic Systems, Formal Languages and Conventional and Unconventional Computation Theory)..

We apply the generalized KYP (GKYP) lemma to the LPV mechanical systems and derive a design method in the frequency-domain to yield optimal robust gain scheduled static

 (堤和子・増田珠子・堤龍一郎訳『映画技法のリテラシー I』フィルムアート社 , 2003) L.Giannetti, Understanding Movies,9th Edition,Pearson Prentice

以上の条件を組み合わせて,全部で 26 の交差パターン (2 方向条件 × 13 短音レベル) と 28 のグライドパターンとがあった (1 空隙条件 × 2 方向条件 + 13 中央区間レベル

[r]