最大クリーク問題に対する進化的アルゴリズム

書誌事項

タイトル別名
  • 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.

収録刊行物

被引用文献 (1)*注記

もっと見る

関連プロジェクト

もっと見る

キーワード

詳細情報

  • 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

問題の指摘

ページトップへ