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

摘要

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