Combinatorial Optimization Method Based on Quantitative Evaluation of Proximate Optimality Principle

• Yaguchi Kota

  Tokyo Metropolitan University

• Tamura Kenichi

  Tokyo Metropolitan University

• Yasuda Keiichiro

  Tokyo Metropolitan University

• Ishigame Atsushi

  Osaka Prefecture University

Bibliographic Information

Other Title

• 近接最適性原理の定量的評価に基づく組合せ最適化手法
• キンセツ サイテキセイ ゲンリ ノ テイリョウテキ ヒョウカ ニ モトズク クミアワセ サイテキ カ シュホウ

Abstract

It is known that many actual optimization problems can be formulated as combinatorial optimization problems. Meta-heuristics, which is a category of approximation algorithm as an effective method in complex and large scale combinatorial optimization problems, attracts expectation in recent years. This study focuses on Proximate Optimality Principle (POP). POP is the principle that good solutions posses some similar structure and experientially known that it holds for many combinatorial optimization problems. In this study, POP is quantitatively evaluated from the view points of parts and distance, and can be applied to search of optimization method. The proposed combinatorial optimization method based on quantitatively evaluated POP has higher optimality and lower computational complexity than conventional neighborhood search methods.

Journal

• IEEJ Transactions on Electronics, Information and Systems

  IEEJ Transactions on Electronics, Information and Systems 133 (6), 1218-1228, 2013

  The Institute of Electrical Engineers of Japan

Keywords

• Meta-Heuristics
• Combinatorial Optimization
• Proximate Optimality Principle
• Intensification
• Diversification

Details

• CRID: 1390282679586314240
• NII Article ID: 10031175306
• NII Book ID: AN10065950
• DOI: 10.1541/ieejeiss.133.1218
• ISSN: 13488155
• ISSN: 03854221
• NDL BIB ID: 024700179
• Web Site: http://id.ndl.go.jp/bib/024700179
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I024700179
• Web Site: https://www.jstage.jst.go.jp/article/ieejeiss/133/6/133_1218/_pdf
• Text Lang: ja
• Data Source:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed