アントコロニー最適化手法の専用ハードウェアの設計と評価

摘要

近年,アリの採餌行動を工学的にモデル化したアントコロニー最適化（ACO）が注目を集めている。ACOは組み合わせ最適化問題に対して，強力な解探索能力がある。しかし，非常に多くの繰り返し処理が必要であり，処理時間の問題が内在する。そこで本研究では高速なACOによる最適化を実現する専用ハードウェアを提案する。提案するハードウェアでは，各アリエージェントによる並列探索を実現するため，新しくハードウェアを指向した並列ACOアルゴリズムを導入する。さらに，フェロモン情報更新のためのメモリアクセスへのボトルネックを解消するために分散メモリによる新しいフェロモン制御方式を考案する。このように，提案ハードウェアでは，ソフトウェア処理と同等の解探索能力を維持し，高速処理を実現する。ベンチマークデータを用いた評価実験により，提案ハードウェアの有効性を検証する。%Ant Colony Optimization (ACO) is inspired by behavior of food gathering of ants, and it is a powerful search tools. However, ACO has the inherent problem of substantial processing time, because its search mechanism is based on a lot of repetitive calculations. In this paper, we propose novel dedicated hardware for Ant Colony Optimization. The proposed hardware introduces hardware-oriented parallel ACO algorithm. It enables search processes of each agent in parallel. Moreover, the proposed hardware adopts a new pheromone control technique using distributed memory. It reduces bottleneck of memory access for updating of pheromone information. Thus, the proposed hardware achieves high speed processing, while keeping the quality of solution in comparison with software processing. Experiments using benchmark data prove the effectiveness of the proposed hardware architecture.