  Under Frequency Fitness Assignment (FFA), the fitness corresponding to an
objective value is its encounter frequency in fitness assignment steps and is
subject to minimization. FFA renders optimization processes invariant under
bijective transformations of the objective function value. On TwoMax, Jump, and
Trap functions of dimension s, the classical (1+1)-EA with standard mutation at
rate 1/s can have expected runtimes exponential in s. In our experiments, a
(1+1)-FEA, the same algorithm but using FFA, exhibits mean runtimes that seem
to scale as $s^2\ln{s}$. Since Jump and Trap are bijective transformations of
OneMax, it behaves identical on all three. On OneMax, LeadingOnes, and Plateau
problems, it seems to be slower than the (1+1)-EA by a factor linear in s. The
(1+1)-FEA performs much better than the (1+1)-EA on W-Model and MaxSat
instances. We further verify the bijection invariance by applying the Md5
checksum computation as transformation to some of the above problems and yield
the same behaviors. Finally, we show that FFA can improve the performance of a
memetic algorithm for job shop scheduling.
