Effective reinforcement learning based local search for the maximum k-plex problem
This is an incremental improvement for researchers in combinatorial optimization and social network analysis, offering enhanced performance on a specific graph problem.
The paper tackles the maximum k-plex problem, a computationally complex graph problem from social network studies, by proposing a hybrid local search combining breakout local search with reinforcement learning, achieving results that match best-known solutions in all but four of 80 benchmark instances and finding 32 new best solutions.
The maximum k-plex problem is a computationally complex problem, which emerged from graph-theoretic social network studies. This paper presents an effective hybrid local search for solving the maximum k-plex problem that combines the recently proposed breakout local search algorithm with a reinforcement learning strategy. The proposed approach includes distinguishing features such as: a unified neighborhood search based on the swapping operator, a distance-and-quality reward for actions and a new parameter control mechanism based on reinforcement learning. Extensive experiments for the maximum k-plex problem (k = 2, 3, 4, 5) on 80 benchmark instances from the second DIMACS Challenge demonstrate that the proposed approach can match the best-known results from the literature in all but four problem instances. In addition, the proposed algorithm is able to find 32 new best solutions.