| 大会名称 |
|---|
| 2009年 情報科学技術フォーラム(FIT) |
| 大会コ－ド |
| F |
| 開催年 |
| 2009 |
| 発行日 |
| 2009/8/20 |
| セッション番号 |
| 7F |
| セッション名 |
| ネットワーク |
| 講演日 |
| 2009/09/04 |
| 講演場所(会議室等) |
| F会場（9号館2F 921教室） |
| 講演番号 |
| F-016 |
| タイトル |
| ランダムウォークと局所探索を導入したMMASによる二次割当問題の実験的検討 |
| 著者名 |
| 飯村 伊智郎, 石橋 賢, 中山 茂, |
| キーワード |
| 群知能, Ant Colony Optimization, ランダムウォーク, 局所探索, 二次割当問題 |
| 抄録 |
| 筆者らは先に,ランダム選択（RS）を導入したMAX-MIN Ant System（MMASRS）を提案し,組合せ最適化問題の中でも困難とされている二次割当問題（QAP）において有効であることを確認した.QAPには,ベンチマーク問題（QAPLIB）があり4つの問題クラスに分類されるが,全問題クラスにおいての有効性は未評価である.そこで本研究では,QAPLIBの全問題クラスを対象として従来手法であるMMASとの比較実験を通し,本手法の有効性を評価する.なお,アリの初期採餌行動に現れるランダムウォーク（RW）にアナロジーを得たことから,ここでは,RSをRWと,MMASRSをMMASRWと称する.さらに,局所探索（LS）を導入し,RWとの併用による効果を検討する.計算機実験の結果から,本手法であるMMASRWがQAPにおいて有効な手法であることが確かめられ,さらにRWとLSとの併用により大幅な探索性能の向上が確認できた. |
| 本文pdf |
| PDF download (48.7KB) |