Focused on the performance degradation problem of the fitness-based selection-crossover mechanism in solving
the hard deceptive maximum clique problem(MCP), a novel Memetic algorithm based on match-crossover(MC Memetic) is proposed. The concept of matching degree is defined to measure the best accessible fitness in two individuals’ crossover operations. Through the selection strategy based on matching degree, the crossover direction is optimized towards the solution with high matching degree value, which ensures that the new high quality schemes are produced with high probability. Simulation results on 40 benchmark graphs show that the MC Memetic algorithm is superior to the most effective phased local search algorithm in solving the maximum clique problem.