Hasso-Plattner-Institut
  
Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
  
 

12.06.2015

Two papers nominated for best paper award of the Genetic and Evolutionary Computation Conference (GECCO 2015)

Robustness of Ant Colony Optimization to Noise

Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Andrew M. Sutton

Track: ACO

Abstract: Recently Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding.
We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with ad- ditive posterior noise sampled from a Gaussian distribu- tion. Without noise the classical (μ + 1)-EA outperforms any ACO algorithm, with smaller μ being better; however, with large noise, the (μ + 1)-EA fails, even for high val- ues of μ (which are known to help against small noise). In this paper we show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor ρ is small enough dependent on the parameter σ2 of the noise and the dimension n of the search space (ρ = o(1/(n(n + σ log n)2 log n))), optimization will be successful.

Improved Runtime Bounds for the (1+1) EA on Random 3-CNF Formulas Based on Fitness-Distance Correlation

Benjamin Doerr, Frank Neumann, Andrew M. Sutton

Track: Theory

Abstract: With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942--951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time O(n log n) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low.

Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.