Frequency Fitness Assignment: Making Optimization Algorithms Invariant under Bijective Transformations of the Objective Function Value

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