記憶した最良解を参照するMAX-MIN Ant Systemによる巡回セールスマン問題の解法

磯崎 敬志  穴田 一  

誌名
電子情報通信学会論文誌 D   Vol.J100-D   No.7   pp.672-680
発行日: 2017/07/01
Online ISSN: 1881-0225
論文種別: 論文
専門分野: 情報・システム基礎
キーワード: 
メタヒューリスティクス,  ACO,  MMAS,  TSP,  アルゴリズム,  

本文: PDF(651.3KB)
>>論文を購入


あらまし: 
本研究では,新たなアントコロニー最適化技法(Ant Colony Optimization,以下ACO)として,記憶した最良解を参照するMAX-MIN Ant Systemというアルゴリズムを提案する.このアルゴリズムでは,ACOの一種であるMAX-MIN Ant System(以下MMAS)のアリに,Ant Colony Optimization with Memoryで用いられた解を記憶しておく領域であるMemoryの導入を行った.また,従来のMemoryで行われていた都市の入れ替え方法を改良し,従来のMemoryよりもMemory内の解の形質を残す都市の入れ替えを可能にした.評価実験では,このアルゴリズムを巡回セールスマン問題へ適用し,MMASやMMASに従来のMemoryを導入した手法と比較して,提案手法は収束速度と解の精度の両方で優れた性能が得られたことを確認した.