Iterated k-Opt Local Search for the Maximum Clique Problem

摘要

This paper presents a simple iterated local search meta-heuristic incorporating a k-opt local search (KLS), called Iterated KLS (IKLS for short), for solving the maximum clique problem (MCP). IKLS consists of three components: LocalSearch at which KLS is used, a Kick called LEC-Kick that escapes from local optima, and Restart that occasionally diversifies the search by moving to other points in the search space. IKLS is evaluated on DIMACS benchmark graphs. The results showed that IKLS is an effective algorithm for the MCP through comparisons with multi-start KLS and state-of-the-art metaheuristics.