Design and analysis of an asymmetric mutation operator

Abstract

Evolutionary algorithms are general randomized search heuristics and typically perform an unbiased random search that is guided only by the fitness of the search points encountered. However, in practical applications there is often problem-specific knowledge that suggests some additional bias. The use of appropriately biased variation operators may speed-up the search considerably. Problems defined over bit strings of finite length often have the property that good solutions have only very few 1-bits or very few 0-bits. A specific mutation operator tailored towards such situations is studied under different perspectives and in a rigorous way discussing its assets and drawbacks. This is done by considering illustrative example functions as well as function classes. The main focus is on theoretical run time analysis yielding asymptotic results. These findings are accompanied by the results of empirical investigations that deliver additional insights.