An external memory supported ACO for the frequency assignment problem

Abstract

Ant colony optimization algorithm is integrated with an external memory for the purpose of improving its efficiency for the solution of a well-known hard combinatorial optimization problem. The external memory keeps variable-size solution segments extracted from promising solutions of previous iterations. Each solution segment is associated with its parent's fitness value. In the construction of a solution, each ant retrieves a segment from the memory using tournament selection and constructs a complete solution by filling the absent components. The proposed approach is used for the solution of minimum span frequency assignment problem for which very promising results are obtained for provably difficult benchmark test problems that could not be handled by any other ACO-based approach so far.