Title :
A novel evolutionary algorithm for MCP using MEC
Author :
Sun, C.Y. ; Li, W.J. ; Gao, X.Z.
Author_Institution :
Artificial Intelligence Inst., Beijing City Univ., China
Abstract :
A novel evolutionary algorithm for the maximum clique problem (MCP) is presented in the paper. That is called MCP-MEC1 and is based on mind evolutionary computation (MEC). The construction of individuals, groups, operations-similartaxis and dissimilation and the evaluation of individuals are accomplished for MCP. 21 benchmark graphs collected by DIMACS (Discrete Mathematics and Theoretical Computer Science) are used to evaluate the performance of the MCP-MEC1 algorithm. The results obtained by MCP-MEC1 are compared with those obtained by two best algorithms for the MCP, RLS (reactive local search) and HGA (heuristic based genetic algorithm). It is shown that the MCP-MEC1 outperforms HGA and is as good as RLS. So the MCP-MEC1 is one of the best heuristic algorithms for the MCP.
Keywords :
genetic algorithms; graph theory; heuristic programming; search problems; DIMACS; Discrete Mathematics and Theoretical Computer Science; HGA; MCP-MEC1; RLS; evolutionary algorithm; heuristic based genetic algorithm; maximum clique problem; mind evolutionary computation; reactive local search; Artificial intelligence; Computer science; Evolutionary computation; Genetic algorithms; Heuristic algorithms; Mathematics; Paper technology; Power electronics; Resonance light scattering; Sun;
Conference_Titel :
Soft Computing in Industrial Applications, 2005. SMCia/05. Proceedings of the 2005 IEEE Mid-Summer Workshop on
Print_ISBN :
0-7803-8942-5
DOI :
10.1109/SMCIA.2005.1466955
