改良2-opt法を組み込んだ遺伝的アルゴリズムによるQAPの解探索 A Genetic Algorithm with the Improved 2-opt Method for Quadratic Assignment Problem

この論文にアクセスする

この論文をさがす

著者

抄録

We propose a new 2-opt base method as a local search approach used with Genetic Algorithms (GAs) in Memetic Algorithm. We got a hint from the fast 2-opt method and devised the new 2-opt method. The main different point is such that our method exchanges genes by using histories of contributions to fitness value improvement. The contribution level is represented by the value `Priority’.<br>In computer experiment, Quadratic Assignment Problem (QAP) instances are solved by GA with the 2-opt method(First Admissible Move Strategy, the Best Admissible Move Strategy), the fast 2-opt, and our proposed method for comparative evaluation. The results showed that our improved method obtained better solutions at ealier generation of the GA and our method required less computation time than the others at some upper bound value of appropriate `Priority’ setting values. Specially, at the average elapsed time of the fast 2-opt method’s 1000th generation, the exact solution findings of ours is more than the others.<br> In further experiment, we observe that the searching capability depends on the number of levels of `Priority’. The ratio between two different Priority level sets becomes 1.59 in computation time in solving problem instance “char25a". This characteristic is shown to be statistically significant in ten instances among eleven.

収録刊行物

  • 電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and System Society

    電気学会論文誌. C, 電子・情報・システム部門誌 = The transactions of the Institute of Electrical Engineers of Japan. C, A publication of Electronics, Information and System Society 124(9), 1896-1906, 2004-09-01

    一般社団法人 電気学会

参考文献:  23件中 1-23件 を表示

被引用文献:  5件中 1-5件 を表示

各種コード

  • NII論文ID(NAID)
    10013538837
  • NII書誌ID(NCID)
    AN10065950
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    03854221
  • NDL 記事登録ID
    7077021
  • NDL 雑誌分類
    ZN31(科学技術--電気工学・電気機械工業)
  • NDL 請求記号
    Z16-795
  • データ提供元
    CJP書誌  CJP引用  NDL  J-STAGE 
ページトップへ