文献

J-GLOBAL ID：201502230561794892   整理番号：15A0321493

解空間の階層構造に基づく組合せ最適化手法

Combinatorial Optimization Method Based on Hierarchical Structure in Solution Space

著者 (4件)： 落合広樹 (首都大学東京大学院) ,  金澤貴彦 (九州電力(株)) ,  田村健一 (首都大学東京大学院) ,  安田恵一郎 (首都大学東京大学院)
資料名： 電気学会論文誌 C  (IEEJ Transactions on Electronics, Information and Systems)
巻： 135  号： 2  ページ： 254-264 (J-STAGE)  発行年： 2015年 
JST資料番号： S0810A  ISSN： 0385-4221  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では,組合せ最適化問題の解空間に,最良移動戦略の局所探索に基づく新たな概念「引き込み領域」を導入し,解空間を階層的に再解釈した。解空間の下位構造における移動戦略を集中化,上位構造における移動戦略を多様化と対応付け,それぞれの戦略を明確化した最適化手法を提案した。特に,多様化については,引き込み領域の概念を活用することで特定の範囲を探索済みとして扱い,未探索範囲へ移動を方向付ける新たな移動戦略を組込んだ。そして,ベンチマーク問題を用いた数値実験により,提案手法が,代表的な組合せ最適化手法であるタブー探索と比べて,多くの場合で優れた結果が得られることを確認した。

シソーラス用語： *組合せ最適化問題 ,  階層構造 ,  *空間 ,  *発見的方法 ,  漸近挙動 ,  近傍探索法 ,  集中化 ,  多様化 ,  タブー探索 ,  *メタヒューリスティクス
準シソーラス用語： *解空間 ,  漸近最適性

分類 (1件)： システム最適化手法  (IA02050Z)

引用文献 (29件)：

• (1) M. Sipser: “Introduction to the Theory of Computation”, PWS Publishing (1997)
• マイケル・シプサ(著),渡辺 治,太田和夫(監訳),阿部正幸,植田広樹,田中圭介,藤岡 淳(訳):「計算理論の基礎」,共立出版(2000)
• (2) J. Hromkovic: “Algorithmics for Hard Problems”, Springer-Verlag, (2003)
• J・ホロムコヴィッチ(著),和田幸一,増澤利光,元木光雄(訳):「計算困難問題に対するアルゴリズム理論」,丸善出版(2012)
• (3) 久保幹雄,J·P・ペドロソ:「メタヒューリスティクスの数理」,共立出版(2009)

タイトルに関連する用語 (4件)： 解空間 ,  階層構造 ,  組合せ ,  最適化手法