二次割当て問題を対象とした<i>MM</i>ASにおけるランダムウォーク機構と局所探索の効用  [in Japanese] Effects of Random Walk Mechanism and Local Search in <i>MM</i>AS for Quadratic Assignment Problem  [in Japanese]

Access this Article

Search this Article

Abstract

ランダムウォーク機構を導入したMMASとしてMMAS with Random Walk(MMASRW)が先行研究で提案されており,QAPLIBのグリッドベース問題クラスに対してその有効性が確認されている.本研究では,そのMMASRWの探索性能をより詳しく評価する目的で,QAPLIBの全問題クラスを対象として探索性能を詳細に評価した.その結果,MMASRWは従来のMMASと比較して,全問題クラスのQAPに対して優れた探索性能を示すことが確認できた.さらに,ランダムウォーク機構と局所探索との併用による効果を解分布により分析し,それらの併用がMMASの探索性能の向上に寄与していることを明らかにした.The previously proposed MMAS with Random Walk (MMASRW) worked well on the problems included in one problem-class of QAPLIB and the results showed the effectiveness of MMASRW. In this study, we evaluated search performance of MMASRW in detail on all problem-classes of QAPLIB. The results showed that MMASRW has better search performance than the conventional MMAS in the QAPs of all problem-classes. In addition, we analyzed the effectiveness in the combination of RW mechanism and Local Search (LS) from the distribution of searched solutions. As a result, we clarified that the combination of exploration by RW and exploitation by LS contributed to the search performance enhancement of MMAS.

The previously proposed MMAS with Random Walk (MMASRW) worked well on the problems included in one problem-class of QAPLIB and the results showed the effectiveness of MMASRW. In this study, we evaluated search performance of MMASRW in detail on all problem-classes of QAPLIB. The results showed that MMASRW has better search performance than the conventional MMAS in the QAPs of all problem-classes. In addition, we analyzed the effectiveness in the combination of RW mechanism and Local Search (LS) from the distribution of searched solutions. As a result, we clarified that the combination of exploration by RW and exploitation by LS contributed to the search performance enhancement of MMAS.

Journal

  • 情報処理学会論文誌

    情報処理学会論文誌 54(2), 1012-1019, 2013-02-15

    情報処理学会

Codes

  • NII Article ID (NAID)
    110009537097
  • NII NACSIS-CAT ID (NCID)
    AN00116647
  • Text Lang
    JPN
  • Article Type
    Journal Article
  • ISSN
    1882-7764
  • NDL Article ID
    024299000
  • NDL Call No.
    YH247-743
  • Data Source
    NDL  NII-ELS  IPSJ 
Page Top