Evaluation of heavy-tailed mutation operator on maximum flow test generation problem

The general recommendation for the mutation rate in standard-bit mutation is 1/n, which gives asymptotically optimal expected optimization times for several simple test problems. Recently, Doerr et al. have shown that such mutation rate is not ideal, and is far from optimal for multimodal problems. They proposed the heavy-tailed mutation operator fmutβ which significantly improves performance of the (1+1) evolutionary algorithm on Jump problem and yields similar speed-ups for the vertex cover problem in bipartite graphs and the matching problem in general graphs.

We evaluate the fmutβ mutation operator on the problem of hard test generation for the maximum flow algorithms. Experiments show that the fmutβ mutation operator greatly increases performance of the (1+1) evolutionary algorithm. It also achieves performance improvement, although less drastic, on a simple population based algorithm, but hinders performance of a crossover based genetic algorithm.