Parallel m-dimensional relative ant colony optimization (mDRACO) for the Costas-array problem

The Costas-array problem is a combinatorial constraint-satisfaction problem (CSP) that remains unsolved for many array sizes greater than 30. In order to reduce the time required to solve large instances, we present an Ant Colony Optimization algorithm called m-Dimensional Relative Ant Colony Optimization (mDRACO) for combinatorial CSPs, focusing specifically on the Costas-array problem. This paper introduces the optimizations included in mDRACO, such as map-based association of pheromone with arbitrary-length component sequences and relative path storage. We assess the quality of the resulting mDRACO framework on the Costas-array problem by computing the efficiency of its processor utilization and comparing its run time to that of an ACO framework without the new optimizations. mDRACO gives promising results; it has efficiency greater than 0.5 and reduces time-to-first-solution for the m= 16 Costas-array problem by a factor of over 300.