問題構造の概形の推定機構を有する多点探索型組合せ最適化手法

• 森田 真英

  首都大学東京

• 落合 広樹

  首都大学東京

• 田村 健一

  首都大学東京

• 安田 恵一郎

  首都大学東京

書誌事項

タイトル別名

• Multi-point Combinatorial Optimization Method with Estimation Mechanism for Landscape of Combinatorial Optimization Problems
• モンダイ コウゾウ ノ ガイケイ ノ スイテイ キコウ オ ユウスル タテン タンサクガタ クミアワセ サイテキ カ シュホウ

抄録

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.

収録刊行物

• 電気学会論文誌Ｃ（電子・情報・システム部門誌）

  電気学会論文誌Ｃ（電子・情報・システム部門誌） 136 (7), 963-976, 2016

  一般社団法人 電気学会

キーワード

• 組合せ最適化
• メタヒューリスティクス
• 近接最適性原理
• 大谷構造
• 多点探索

詳細情報

• CRID: 1390001204608878208
• NII論文ID: 130005160730
• NII書誌ID: AN10065950
• DOI: 10.1541/ieejeiss.136.963
• ISSN: 13488155
• ISSN: 03854221
• NDL書誌ID: 027543195
• Web Site: https://ndlsearch.ndl.go.jp/books/R000000004-I027543195
• Web Site: https://www.jstage.jst.go.jp/article/ieejeiss/136/7/136_963/_pdf
• 本文言語コード: ja
• データソース種別:
  • JaLC
  • NDL
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可