Combinatorial Optimization Method Based on Hierarchical Structure in Solution Space
-
- Ochiai Hiroki
- Tokyo Metropolitan University
-
- Kanazawa Takahiko
- Kyushu Electric Power Corporation
-
- Tamura Kenichi
- Tokyo Metropolitan University
-
- Yasuda Keiichiro
- Tokyo Metropolitan University
Bibliographic Information
- Other Title
-
- 解空間の階層構造に基づく組合せ最適化手法
- カイクウカン ノ カイソウ コウゾウ ニ モトズク クミアワセ サイテキ カ シュホウ
Search this article
Abstract
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.
Journal
-
- IEEJ Transactions on Electronics, Information and Systems
-
IEEJ Transactions on Electronics, Information and Systems 135 (2), 254-264, 2015
The Institute of Electrical Engineers of Japan
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390282679585154688
-
- NII Article ID
- 130004870145
-
- NII Book ID
- AN10065950
-
- ISSN
- 13488155
- 03854221
-
- NDL BIB ID
- 026100315
-
- Text Lang
- ja
-
- Data Source
-
- JaLC
- NDL
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed