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

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

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

発行日: 2015/02/01

タイトル(英語): Combinatorial Optimization Method Based on Hierarchical Structure in Solution Space

著者名: 落合　広樹（首都大学東京大学院），金澤　貴彦（九州電力（株）），田村　健一（首都大学東京大学院），安田　恵一郎（首都大学東京大学院）

著者名(英語): Hiroki Ochiai (Tokyo Metropolitan University), Takahiko Kanazawa (Kyushu Electric Power Corporation), Kenichi Tamura (Tokyo Metropolitan University), Keiichiro Yasuda (Tokyo Metropolitan University)

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

要約(英語): In this paper, we introduce a new concept of hierarchical structure into solution space of a combinatorial optimization problem, and develop a novel combinatorial optimization method based on the concept. The introduction of the above new hierarchical structure concept “basin of attraction”, which is a set binding solutions by utilizing properties of local optimal solutions, enables us to construe solution space as not only set of solutions but also set of basins of attraction hierarchically. It is well known that the appropriate balance of two policies, intensification and diversification, is essential in the search of meta-heuristics. The proposed method clarifies the search policy by relating the hierarchical structure in solution space with intensification and diversification. In regard to diversification, we incorporate a movement strategy that has longer-term or more macroscopic viewpoint than before in the algorithm by utilizing the concept basin of attraction. The performance of the proposed combinatorial optimization method is inspected by numerical experiments using some typical benchmark problems of a traveling salesman problem, a knapsack problem, a flow-shop scheduling problem and a quadratic assignment problem.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.135 No.2 （2015） 特集：フレキシブルフィルムデバイスのための材料・プロセスと評価技術

本誌掲載ページ: 254-264 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/135/2/135_254/_article/-char/ja/