コロニーの巣分かれと消滅を用いたACOアルゴリズムの提案

藤田 信行  原 章  市村 匠  高濱 徹行  

誌名
電子情報通信学会論文誌 D   Vol.J89-D   No.12   pp.2661-2670
発行日: 2006/12/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 人工知能,認知科学
キーワード: 
Ant Colony Optimization,  群知能,  メタヒューリスティクス,  組合せ最適化,  

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




あらまし: 
近年,組合せ最適化問題に対する群知能を用いたメタヒューリスティクスの一つとして,蟻の採餌行動を摸倣したAnt Colony Optimization(ACO)が注目されている.ACOアルゴリズムは巡回セールスマン問題に適用されることが多く,それらは良い結果を出している.しかし,ACOアルゴリズムの一つであるASeliteの問題点として,各々の蟻が発見する解構造が類似してしまう問題や,単一コロニーによる探索であるがゆえに局所解に陥りやすいという問題がある.これらの問題を解決するために,本論文ではASeliteの行動選択機構を改良することにより大域的な探索が可能である改良型ASeliteの提案及び,複数のコロニーによるコロニーの巣分かれと消滅を模倣することにより一度の探索で複数の多様なパターンの解を発見可能なACOアルゴリズムの提案を行う.本手法を巡回セールスマン問題に適用し,その有効性を示す.