A simple simulated annealing algorithm for the maximum clique problem |
| |
Authors: | Xiutang Geng Jin Xu Linqiang Pan |
| |
Affiliation: | Key Laboratory of Image Processing and Intelligent Control, Department of Control Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, China |
| |
Abstract: | Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin. |
| |
Keywords: | Simulated annealing algorithm Maximum clique problem Minimum vertex cover problem NP-hard optimization problem Heuristic algorithm |
本文献已被 ScienceDirect 等数据库收录! |