Multi-point Combinatorial Optimization Method with Estimation Mechanism for Landscape of Combinatorial Optimization Problems
-
- Morita Masahide
- Tokyo Metropolitan University
-
- Ochiai Hiroki
- Tokyo Metropolitan University
-
- Tamura Kenichi
- Tokyo Metropolitan University
-
- Yasuda Keiichiro
- Tokyo Metropolitan University
Bibliographic Information
- Other Title
-
- 問題構造の概形の推定機構を有する多点探索型組合せ最適化手法
- モンダイ コウゾウ ノ ガイケイ ノ スイテイ キコウ オ ユウスル タテン タンサクガタ クミアワセ サイテキ カ シュホウ
Search this article
Description
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.
Journal
-
- IEEJ Transactions on Electronics, Information and Systems
-
IEEJ Transactions on Electronics, Information and Systems 136 (7), 963-976, 2016
The Institute of Electrical Engineers of Japan
- Tweet
Keywords
Details 詳細情報について
-
- CRID
- 1390001204608878208
-
- NII Article ID
- 130005160730
-
- NII Book ID
- AN10065950
-
- ISSN
- 13488155
- 03854221
-
- NDL BIB ID
- 027543195
-
- Text Lang
- ja
-
- Data Source
-
- JaLC
- NDL
- Crossref
- CiNii Articles
- KAKEN
-
- Abstract License Flag
- Disallowed