  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.
