論文

査読有り
2016年8月

Combinatorial Optimization Method Based on Hierarchical Structure in Solution Space

ELECTRONICS AND COMMUNICATIONS IN JAPAN
  • Hiroki Ochiai
  • ,
  • Takahiko Kanazawa
  • ,
  • Kenichi Tamura
  • ,
  • Keiichiro Yasuda

99
8
開始ページ
25
終了ページ
37
記述言語
英語
掲載種別
研究論文(学術雑誌)
DOI
10.1002/ecj.11833
出版者・発行元
WILEY-BLACKWELL

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 solution 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 metaheuristics. The proposed method clarifies the search policy by relating the hierarchical structure in solution space with intensification and diversification. With 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) 2016 Wiley Periodicals, Inc.

Web of Science ® 被引用回数 : 1

リンク情報
DOI
https://doi.org/10.1002/ecj.11833
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000379967100003&DestApp=WOS_CPL

エクスポート
BibTeX RIS