解空間の階層構造と近接最適性原理に基づく組合せ最適化手法

カテゴリ: 部門大会

論文No: GS2-3

グループ名: 【C】平成24年電気学会電子・情報・システム部門大会講演論文集

発行日: 2012/09/05

タイトル(英語): A Combinatorial Optimization Method Based on Hierarchical Structure and Proximate Optimality Principle

著者名: 落合 広樹(首都大学東京),田村 健一(首都大学東京),安田 恵一郎(首都大学東京)

著者名(英語): Hiroki Ochiai(Tokyo Metropolitan University),Kenichi Tamura(Tokyo Metropolitan University),Keiichiro Yasuda(Tokyo Metropolitan University)

キーワード: 組合せ最適化|メタヒューリスティクス|近接最適性原理|局所的最適解|集中化多様化|Combinatorial Optimization|Metaheuristic|Proximate Optimality Principle|Local Optimal Solution|IntensificationDiversification

要約(日本語): 離散的構造をもつ多くの実問題は組合せ最適化問題として定式化できる。これらの実問題は大規模化・複雑化の傾向にあり，実用時間内に最適性の高い解を得られる最適化手法が求められている。メタヒューリスティクスはこれらの要求を背景として登場した発見的近似手法の枠組みであり，様々な組合せ最適化手法が提案されている。既存の手法では解空間を個々の解の集合としてのみ捉えている。しかし本研究では，個々の解を解空間における下位構造と解釈し，局所的最適解に着目することで個々の解を束ねる上位構造の概念を新たに導入する。この階層構造を利用することで長期的な探索過程の情報利用を志向する。さらに，工学分野において広く成り立つことが知られている近接最適性原理が上位構造においても成立することを検証する。この階層構造と近接最適性原理に基づく最適化アルゴリズムを構築し，代表的ベンチマーク問題を用いて検討を行う。

PDFファイルサイズ: 5,290 Kバイト