Abstract:
We investigate the effect of restricting the mutation operator in evolutionary algorithms with respect to the runtime behavior. Considering the Eulerian cycle problem we present runtime bounds on evolutionary algorithms with a restricted operator that are much smaller than the best upper bounds for the general case. In our analysis it turns out that a plateau which has to be coped with for both algorithms changes its structure in a way that allows the algorithms to obtain an improvement much faster. In addition, we present a lower bound for the general case which shows that the restricted operator speeds up computation by at least a linear factor.