問題構造の概形の推定機構を有する多点探索型組合せ最適化手法

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2016/07/01

タイトル(英語): Multi-point Combinatorial Optimization Method with Estimation Mechanism for Landscape of Combinatorial Optimization Problems

著者名: 森田　真英（首都大学東京），落合　広樹（首都大学東京），田村　健一（首都大学東京），安田　恵一郎（首都大学東京）

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

キーワード: 組合せ最適化，メタヒューリスティクス，近接最適性原理，大谷構造，多点探索　　Combinatorial Optimization，Meta-heuristics，Proximate Optimality Principle，Big Valley Structure，Multi-point Search

要約(英語): Based on the Proximate Optimality Principle (POP) and a big valley structure in combinatorial optimization problems, an estimation mechanism for quantitatively estimating structural characteristics (landscape) of combinatorial optimization problems is developed in this paper. Using the results of a numerical evaluation of landscape for several types of combinatorial optimization problems including a traveling salesman problem, a 0-1 knapsack problem, a flow-shop scheduling problem and a quadratic assignment problem, a new multi-point combinatorial optimization method having the landscape estimation mechanism is also proposed. The proposed combinatorial optimization method uses the estimated landscape information of a given combinatorial optimization problem to control diversification and intensification during a search. The search capabilities of the proposed combinatorial optimization method are examined based on the results of numerical experiments using typical benchmark problems.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.136 No.7 （2016） 特集：平成27年電子・情報・システム部門大会

本誌掲載ページ: 963-976 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/136/7/136_963/_article/-char/ja/