  A core feature of evolutionary algorithms is their mutation operator.
Recently, much attention has been devoted to the study of mutation operators
with dynamic and non-uniform mutation rates. Following up on this line of work,
we propose a new mutation operator and analyze its performance on the (1+1)
Evolutionary Algorithm (EA).
  Our analyses show that this mutation operator competes with pre-existing
ones, when used by the (1+1) EA on classes of problems for which results on the
other mutation operators are available. We show that the (1+1) EA using our
mutation operator finds a (1/3)-approximation ratio on any non-negative
submodular function in polynomial time. We also consider the problem of
maximizing a symmetric submodular function under a single matroid constraint
and show that the (1+1) EA using our operator finds a (1/3)-approximation
within polynomial time. This performance matches that of combinatorial local
search algorithms specifically designed to solve these problems and outperforms
them with constant probability.
  Finally, we evaluate the performance of the (1+1)EA using our operator
experimentally by considering two applications: (a) the maximum directed cut
problem on real-world graphs of different origins, and with up to 6.6 million
vertices and 56 million edges and (b) the symmetric mutual information problem
using a four month period air pollution data set. In comparison with uniform
mutation and a recently proposed dynamic scheme our operator comes out on top
on these instances.
