2016
Multi-point combinatorial optimization method with estimation mechanism for landscape of combinatorial optimization problems
IEEJ Transactions on Electronics, Information and Systems
- ,
- ,
- ,
- Volume
- 136
- Number
- 7
- First page
- 963
- Last page
- 976
- Language
- Japanese
- Publishing type
- Research paper (scientific journal)
- DOI
- 10.1541/ieejeiss.136.963
- Publisher
- Institute of Electrical Engineers of Japan
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 flowshop 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.
- Link information
- ID information
-
- DOI : 10.1541/ieejeiss.136.963
- ISSN : 1348-8155
- ISSN : 0385-4221
- SCOPUS ID : 84977080446