TY - GEN
T1 - Refined runtime analysis of a basic ant colony optimization algorithm
AU - Doerr, Benjamin
AU - Johannsen, Daniel
PY - 2007/12/1
Y1 - 2007/12/1
N2 - Neumann and Witt (2006) analyzed the runtime of the basic ant colony optimization (ACO) algorithm 1-ANT on pseudo-boolean optimization problems. For the problem ONEMAX they showed how the runtime depends on the evaporation factor. In particular, they proved a phase transition from exponential to polynomial runtime. In this work, we simplify the view on this problem by an appropriate translation of the pheromone model. This results in a profound simplification of the pheromone update rule and, by that, a refinement of the results of Neumann and Witt. In particular, we show how the exponential runtime bound gradually changes to a polynomial bound inside the phase of transition.
AB - Neumann and Witt (2006) analyzed the runtime of the basic ant colony optimization (ACO) algorithm 1-ANT on pseudo-boolean optimization problems. For the problem ONEMAX they showed how the runtime depends on the evaporation factor. In particular, they proved a phase transition from exponential to polynomial runtime. In this work, we simplify the view on this problem by an appropriate translation of the pheromone model. This results in a profound simplification of the pheromone update rule and, by that, a refinement of the results of Neumann and Witt. In particular, we show how the exponential runtime bound gradually changes to a polynomial bound inside the phase of transition.
U2 - 10.1109/CEC.2007.4424512
DO - 10.1109/CEC.2007.4424512
M3 - Conference contribution
AN - SCOPUS:56549113441
SN - 1424413400
SN - 9781424413409
T3 - 2007 IEEE Congress on Evolutionary Computation, CEC 2007
SP - 501
EP - 507
BT - 2007 IEEE Congress on Evolutionary Computation, CEC 2007
T2 - 2007 IEEE Congress on Evolutionary Computation, CEC 2007
Y2 - 25 September 2007 through 28 September 2007
ER -