Game-Based Memetic Algorithm to the Vertex Cover of Networks

Area of Science:

• Combinatorial Optimization
• Computational Intelligence
• Network Science

Background:

• The Minimum Vertex Cover (MVC) is a fundamental problem in combinatorial optimization with significant theoretical and practical implications.
• Existing algorithms often struggle with complex network structures and finding optimal solutions efficiently.

Purpose of the Study:

• To introduce a novel Game-based Memetic Algorithm for Minimum Vertex Cover (GMA-MVC).
• To enhance the local search capabilities beyond traditional (1,0)-exchanges using a snowdrift game.
• To improve solution quality and efficiency for the MVC problem on various networks.

Main Methods:

• Developed a Game-based Memetic Algorithm (GMA-MVC) integrating a snowdrift game for local search and an evolutionary algorithm (EA) for global search.
• Implemented an asynchronous updating snowdrift game where vertices act as agents, with strict Nash equilibria (SNE) guaranteeing vertex covers.
• Introduced a degree-based initialization method and efficient (k,l)-exchanges for enhanced solution exploration.

Main Results:

• The snowdrift game's strict Nash equilibria (SNE) consistently yield valid vertex covers.
• The GMA-MVC effectively escapes local optima by leveraging the EA to guide the game towards better Nash equilibria.
• Experimental comparisons demonstrate that GMA-MVC consistently outperforms state-of-the-art algorithms on diverse network datasets.

Conclusions:

• The proposed GMA-MVC offers a significant advancement in solving the Minimum Vertex Cover problem.
• The integration of game theory (snowdrift game) with evolutionary computation provides a powerful framework for combinatorial optimization.
• GMA-MVC demonstrates superior performance and solution quality compared to existing methods.