| Ant Colony Optimization (ACO) algorithm is a nature-inspired metaheuristic algorithm. It has experienced more than 10 years'development since it was proposed and has become an efficient tool for solving combinatorial optimization problem. The maximum clique problem (MCP) is a classical combinatorial optimization problem which belongs to NP-Hard, and many practical problems can be formulated to it. Therefore, studying the MCP is full of significance both in theory and in practice.This paper is devoted to investigating the capability of ACO metaheuristic for solving MCP and proposes an intensification-diversification balanced ACO algorithm for MCP. Moreover, the algorithm is applied to improving the progressive algorithm which is for multiple sequences alignment problem (MSA).Firstly the outline of metaheuristics for MCP is shown and a description of MCP is given. Then tow similar metaheuristics for MCP are introduced: EA/G, the best genetic algorithm found so far, and the existing simple ACO algorithm. Then the paper analyzes the shortcomings of simple ACO and proposes an approved ACO algorithm, and then analyzes the intensification-diversification schemes of it. Moreover experiments on DIMACS benchmarks are run and the results show that the approved ACO algorithm not only outperforms the simple ACO algorithm, but also outperforms EA/G algorithm, the best genetic algorithm for MCP found so far. Finally, the ability of applying the approved ACO algorithm to MSA is studied. The idea of divide-and-conquer is adopted to improving the progressive algorithm and the longest common subsequence of multiple sequences is proposed as the partition points of multiple sequences. Also, the paper presents how to solve the longest common subsequence of multiple sequences by the approved ACO algorithm for MCP. Besides, experimental results prove the effectiveness of the improvements. |
PDF Full Text Request