Abstract:
A memetic algorithm is an evolutionary algorithm augmented with a local
search. This paper defines the (1+1) self-adjusting memetic algorithm with a dynamic mutation probability, and proposes a random permutation local search to
compare with a traditional random complete local search. Our time complexity
analysis proves that these two local searches can outperform each other on different functions. Also memetic algorithms with dynamic mutation probabilities can
outperform memetic algorithms with static mutation probabilities, and vice versa.
The success of our experimental results on the Maximum Clique Problem shows
the benefit of the self-adjusting strategy combined with the random permutation
local search. Also focusing on the Maximum Clique Problem, we propose another
time complexity metric (expected time to escape a local optimal) and show how
it bounds the expected running time of finding a maximum clique. This metric
provides insight and shows some advantages of our approach of using a dynamic
mutation probability and a random permutation local search.
