  Population-based memetic algorithms have been successfully applied to solve
many difficult combinatorial problems. Often, a population of fixed size was
used in such algorithms to record some best solutions sampled during the
search. However, given the particular features of the problem instance under
consideration, a population of variable size would be more suitable to ensure
the best search performance possible. In this work, we propose variable
population memetic search (VPMS), where a strategic population sizing mechanism
is used to dynamically adjust the population size during the memetic search
process. Our VPMS approach starts its search from a small population of only
two solutions to focus on exploitation, and then adapts the population size
according to the search status to continuously influence the balancing between
exploitation and exploration. We illustrate an application of the VPMS approach
to solve the challenging critical node problem (CNP). We show that the VPMS
algorithm integrating a variable population, an effective local optimization
procedure (called diversified late acceptance search) and a backbone-based
crossover operator performs very well compared to state-of-the-art CNP
algorithms. The algorithm is able to discover new upper bounds for 13 instances
out of the 42 popular benchmark instances, while matching 23 previous
best-known upper bounds.
