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

David Vulakh, Raphael Finkel

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
JournalSoft Computing
StateAccepted/In press - 2022

Bibliographical note

Funding Information:
Open Access funding provided by the MIT Libraries. This study was funded by the Kentucky Young Researchers Program.

Publisher Copyright:
© 2022, The Author(s).


  • ACO
  • Costas array
  • CSP
  • Parallelism

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software
  • Geometry and Topology


Dive into the research topics of 'Parallel m-dimensional relative ant colony optimization (mDRACO) for the Costas-array problem'. Together they form a unique fingerprint.

Cite this