colony optimization

We present a hardware implementation of population-based ant colony optimization (P-ACO) on field-programmable gate arrays (FPGAs). The ant colony optimization meta-heuristic is adopted from the natural foraging behavior of real ants and has been used to find good solutions to a wide spectrum of combinatorial optimization problems. We describe the P-ACO algorithm and present a circuit architecture that facilitates efficient FPGA implementations. The proposed design shows modest space requirements but leads to a significant reduction in runtime over software-based solutions. Several modifications and extensions of the basic algorithm are also presented, including the approximation of the heuristic function by a small, dynamically changing set of favorable decisions. © 2004 Elsevier B.V. All rights reserved. Keywords: Ant colony optimization; Ant algorithm; Field-programmable gate array; FPG