An Efficient Two-Phase Ant Colony Optimization Algorithm for the Closest String Problem

摘要

Given a finite set S of strings of length m, the task of finding a string t that minimizes the Hamming distance from t to 5, has wide applications. This paper presents a two-phase Ant Colony Optimization (ACO) algorithm for the problem. The first phase uses the Smooth Max-Min (SMMAS) rule to update pheromone trails. The second phase is a memetic algorithm that uses ACO method to generate a population of solutions in each iteration, and a local search technique on the two best solutions. The efficiency of our algorithm has been evaluated by comparing to the Ant-CSP algorithm.