著者

磯崎 敬志 穴田 一

雑誌

第79回全国大会講演論文集

巻号頁・発行日

vol.2017, no.1, pp.341-342, 2017-03-16

---

本研究では,対数感度と改良型Memory を用いたMAXMIN Ant System という新たなアントコロニー最適化技法(ACO)の提案を行い,それを組み合わせ最適化問題の一種である巡回セールスマン問題(TSP)に適用し,その有効性を検証した.本研究ではACOの一種であるMMAS の収束速度と解の精度の両方を向上させることを目的とし,ACO with Memoryで用いられたMemory の改良型の導入と,フェロモン情報およびヒューリスティック情報にウェーバー・フェヒナーの法則を用いて都市選択を行うアルゴリズムを構築した.評価実験では,TSPのベンチマーク問題を用いて従来手法との比較を行った.その結果,MMASの欠点であった収束の遅さの改善とともに,厳密解到達率の大幅な向上を確認した.

著者

磯崎 敬志 穴田 一

雑誌

研究報告数理モデル化と問題解決(MPS) (ISSN:21888833)

巻号頁・発行日

vol.2015-MPS-106, no.5, pp.1-5, 2015-12-08

---

本研究では新たなアントコロニー最適化技法 (ACO) を提案する.ACO はアリの採餌行動をモデル化したメタヒューリスティクスで,巡回セールスマン問題 (TSP) などの組み合わせ最適化問題の近似解を求めることができる.ACO の一種である MAX-MIN Ant System(MMAS) は高い精度で近似解を求めることができるが,収束が遅いなどの欠点がある.そこで提案手法では,MMAS 解を記憶させておくスペースである Memory を改良したものを持たせ,局所解からの脱出を目的とした近傍探索アリ,解の多様性の維持を目的とした複数のアリによるフェロモン更新を導入し,従来手法と比べて解の精度と収束速度の両方が向上したことを評価実験で確認した.