MEAMCP: A Membrane Evolutionary Algorithm for Solving Maximum Clique Problem

Abstract

The maximum clique problem (MCP) is a classical NP-hard problem in combinatorial optimization, which has important applications in many fields. In this paper, a heuristic algorithm MEAMCP based on Membrane Evolutionary Algorithm (MEA) is proposed to solve MCP. First, we introduce the general structure of MEA, which includes four kinds of membrane operators: selection, division, fusion and cytolysis. MEA evolves the feasible solution population through the membrane operator. Second, MEAMCP is proposed and we discuss how to initialize the population and implement the four kinds of membrane operators. Finally, MEAMCP is tested on DIMACS benchmark datasets and compared with other MCP algorithms. The experiment results demonstrate that MEAMCP has better stability.

Keywords

• Combinatorial optimization
• heuristic algorithm
• maximum clique problem
• membrane computing
• membrane evolutionary algorithm