Runtime analysis comparison of two fitness functions on a memetic algorithm for the Clique Problem
Kuai Wei, Michael J. Dinneen · 2014
It is commonly accepted that a proper fitness function can guide the algorithm to find a global optimum solution faster. This paper will use the runtime analysis to provide the theoretical evidence that a small change of the fitness function (additional one step looking forward) can result in a huge performance gap in terms of finding a global optimum solution. It also shows that the fitness function that gives the best results in an Memetic Algorithm on the Clique Problem is entirely instance specific. In detail, we will formalize a (1+1) Restart Memetic Algorithm with a Best-Improvement Local Search, and run them on two different fitness functions, fOLand fOPL, to solve the Clique Problem respectively. We then construct two families of graphs, G1and G2, and show that, for the first family of graphs G1, the (1+1) RMA on the fitness function fOPLdrastically outperforms the (1+1) RMA on the fitness function fOL, and vice versa for the second family of graphs G2.