Solving Maximum Clique Problem By Mind Evolutionary Computation

Genetic Algorithm (GA) was firstly proposed in 1960's by professor Holland who came from Michigan State University. It is a computational model that simulates evolutionary process in nature. In the passed 30 years, the theoretical study and application of GA are most active, and has rapidly become a highlight in the fields of international academy. However, there are many shortcomings in GA, which should not be neglected. In the early stage, researchers have noticed the problem of GA's prematurity. Another crucial problem is computing efficiency of GA, due to non-directionality of its evolutionary mechanism.Mind Evolutionary Computation (MEC) is a new approach of Evolutionary Computation (EC) proposed by Chengyi Sun in 1998. It comes from the consideration of the existing problems of Genetic Algorithm (GA) and the analysis of the mind progress of humanity. It imitates two phenomena of human society -similartaxis and dissimilation.After years' studies on its theory and experiment have showed that the computing efficiency and the convergence percentage of MEC are generally higher than those of GA by more than 50% in numerical optimization. It shows that MEC is an efficient algorithm. MEC has successfully solved the numericalproblems, such as multimodal optimization, multi-objective optimization, etc, and the non-numerical problems, such as TSP, Job-shop and dynamic modeling of system, etc. So far, a preliminary system has already been established for MEC.The maximum clique problem (MCP) is a classical problem in combinatorial optimization, MCP is a well-known NP-complete problem, MCP finds many important applications in different domains.This paper proposes a new heuristic algorithm named MCP-MEC1 for solving the maximum clique problem (MCP)^by Mind Evolutionary Computation (MEC). The construction of individual, group and operations similartaxis and dissimilation and the evaluation of individual are accomplished for solving MCP. The MCP-MEC1 is tested on benchmark graphs provided by DIMACS (Discrete Mathematics & Theoretical Computer Science). It is well known that RLS (Reactive Local search) and HGA (heuristic genetic algorithm) are two best heuristic algorithms for solving MCP. Experiment shows that the performance of MCP-MEC1 outperforms that of HGA and is as good as that of RLS and MCP-MEC1 is one of the best heuristic algorithms for solving MCP.