  Combinatorial optimization problems are a prominent application area of
evolutionary algorithms, where the (1+1) EA is one of the most investigated. We
extend this algorithm by introducing some problem knowledge with a specialized
mutation operator which works under the assumption that the number of 1s of a
solution is critical, as frequently happens in combinatorial optimization. This
slight modification increases the chance to correct wrongly placed bits while
preserving the simplicity and problem independence of the (1+1) EA. As an
application of our algorithm we examine the vertex cover problem on certain
instances, where we show that it leads to asymptotically better runtimes and
even finds with higher probability optimal solutions in comparison with the
usual (1+1) EA. Precisely, we compare the performance of both algorithms on
paths and on complete bipartite graphs of size $n$. Regarding the path we prove
that, for a particular initial configuration, the \alg1+1 takes in expectation
$\Theta(n^4)$ iterations while the modification reduces this to $\Theta(n^3)$,
and present experimental evidence that such a configuration is reached.
Concerning the complete bipartite graph our modification finds the optimum in
polynomial time with probability $1-1/2^{\Omega(n^\xi)}$ for every positive
constant $\xi < 1$, which improves the known probability of
$1-1/\text{poly}(n)$ for the (1+1) EA..
