MEAMCP: A Membrane Evolutionary Algorithm for Solving Maximum Clique Problem

Ping Guo, Xuekun Wang, Yi Zeng, Haizhu Chen

IEEE Access · 2019 · 14 citations · 21 references

DOIFull text

Open access

Concepts

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.

References

21