書誌事項
- タイトル別名
-
- An Effective Evolutionary Algorithm for the Maximum Clique Problem
- アルゴリズム理論
この論文をさがす
抄録
組合せ最適化問題の代表例である最大クリーク問題(maximum clique problem,MCP)に対して,これまでに遺伝的アルゴリズム等の進化的アプローチが多く提案されてきた.本研究では,高性能な進化的アルゴリズムの設計を目指し,まず,MCPにおける探索空間内の地形を解析する.その結果,DIMACSベンチマークグラフ群の多くの例題において,MCPに対するk-opt局所探索法によって算出される局所最適解群は,真の最適解との間に相関が見られない場合が多いことを示す.本論文では,このような悲観的な地形解析結果に対応するMemeticアルゴリズム(memetic algorithm,MA)を提案し,最先端の進化的アプローチとの比較を通して,本MAの有効性を示す.
Many evolutionary approaches have been proposed for the maximum clique problem (MCP). To design a high-performance evolutionary algorithm for the MCP, we first analize the landscape of local optima that can be obtained by the k-opt local search (KLS) based on the variable depth search. The results show that the search space is very pessimistic on many of the DIMACS benchamrk graphs. This paper presents an effective memetic algorithm (MA) — an evolutionary algorithm incorporating KLS — for the MCP, and shows the effectiveness of the MA through comparisons of state-of-the-art evolutionary approaches to the problem.
収録刊行物
-
- 情報処理学会論文誌
-
情報処理学会論文誌 49 (11), 3715-3724, 2008-11-15
- Tweet
キーワード
詳細情報
-
- CRID
- 1050845762811351296
-
- NII論文ID
- 110007970258
-
- NII書誌ID
- AN00116647
-
- ISSN
- 18827764
-
- Web Site
- http://id.nii.ac.jp/1001/00009381/
-
- 本文言語コード
- ja
-
- 資料種別
- journal article
-
- データソース種別
-
- IRDB
- CiNii Articles
- KAKEN