距離関数を考慮した解空間の階層構造に基づく組合せ最適化手法

カテゴリ: 部門大会

論文No: GS2-3

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

発行日: 2017/09/06

タイトル(英語): Combinatorial Optimization Method Based on Hierarchial Structure in Solution Space Considering Distance Function

著者名: 大日方 勇太(首都大学東京),田村 健一(首都大学東京),土屋 淳一(首都大学東京),安田 恵一郎(首都大学東京)

著者名(英語): Yuta Obinata|Kenichi Tamura|Junichi Tsuchiya|Keiichiro Yasuda

キーワード: 組合せ最適化|メタヒューリスティクス|局所探索法|近接最適性原理|多様化集中化|Combinatorial Optimization|Meta-heuristics|Local Search|Proximate Optimality Principle|DiversificationIntensification

要約(日本語): 組合せ最適化問題は巡回路問題や施設配置問題など現実にも多く現れる。これらの問題の最適解を得る最適化手法の中でも，高い汎用性と高い性能から発見的近似解法の枠組みであるメタヒューリスティクスが注目されている。組合せ最適化問題に対するメタヒューリスティクスの多くは局所探索法に基づいており，近傍生成による移動が基本的な戦略となっている。また，解空間における多様化・集中化の移動戦略が重要であることも知られている。近傍の定義や移動戦略は得られる解に直接的に影響を与えるが，一方でその定義の自由度は高く，任意に定めることが可能である。本稿では離散的な解空間において，複数の距離関数を定義し，近傍の定義および移動戦略に活用する。この距離関数の定義・導入により解同士の位置関係を定量的に扱い，新たに定義される解空間の階層構造に基づく手法について距離関数を考慮した上で提案し，ベンチマーク問題を用いて数値実験を行う。

PDFファイルサイズ: 161 Kバイト