On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization

Dirk Sudholt*, Carsten Witt

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

120 Downloads (Pure)

Abstract

Probabilistic model-building Genetic Algorithms (PMBGAs) are a class of metaheuristics that evolve probability distributions favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We provide a rigorous runtime analysis concerning the update strength, a vital parameter in PMBGAs such as the step size 1 / K in the so-called compact Genetic Algorithm (cGA) and the evaporation factor ρ in ant colony optimizers (ACO). While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to unstable behavior and possibly poor performance. We demonstrate this trade-off for the cGA and a simple ACO algorithm on the well-known OneMax function. More precisely, we obtain lower bounds on the expected runtime of Ω(Kn+nlogn) and Ω(n/ρ+nlogn), respectively, suggesting that the update strength should be limited to 1/K,ρ=O(1/(nlogn)). In fact, choosing 1/K,ρ∼1/(nlogn) both algorithms efficiently optimize OneMax in expected time Θ(nlog n). Our analyses provide new insights into the stochastic behavior of PMBGAs and propose new guidelines for setting the update strength in global optimization.

Original languageEnglish
JournalAlgorithmica
Volume81
Issue number4
Pages (from-to)1450–1489
ISSN0178-4617
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • Ant colony optimization
  • Estimation-of-distribution algorithms
  • Genetic Algorithms
  • Probabilistic model-building Genetic Algorithms
  • Runtime analysis
  • Theory of randomized search heuristics

Cite this

@article{a0de817840dd42aa9fb2399a4ddd4c5c,
title = "On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization",
abstract = "Probabilistic model-building Genetic Algorithms (PMBGAs) are a class of metaheuristics that evolve probability distributions favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We provide a rigorous runtime analysis concerning the update strength, a vital parameter in PMBGAs such as the step size 1 / K in the so-called compact Genetic Algorithm (cGA) and the evaporation factor ρ in ant colony optimizers (ACO). While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to unstable behavior and possibly poor performance. We demonstrate this trade-off for the cGA and a simple ACO algorithm on the well-known OneMax function. More precisely, we obtain lower bounds on the expected runtime of Ω(Kn+nlogn) and Ω(n/ρ+nlogn), respectively, suggesting that the update strength should be limited to 1/K,ρ=O(1/(nlogn)). In fact, choosing 1/K,ρ∼1/(nlogn) both algorithms efficiently optimize OneMax in expected time Θ(nlog n). Our analyses provide new insights into the stochastic behavior of PMBGAs and propose new guidelines for setting the update strength in global optimization.",
keywords = "Ant colony optimization, Estimation-of-distribution algorithms, Genetic Algorithms, Probabilistic model-building Genetic Algorithms, Runtime analysis, Theory of randomized search heuristics",
author = "Dirk Sudholt and Carsten Witt",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/s00453-018-0480-z",
language = "English",
volume = "81",
pages = "1450–1489",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "4",

}

On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization. / Sudholt, Dirk; Witt, Carsten.

In: Algorithmica, Vol. 81, No. 4, 01.01.2018, p. 1450–1489.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization

AU - Sudholt, Dirk

AU - Witt, Carsten

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Probabilistic model-building Genetic Algorithms (PMBGAs) are a class of metaheuristics that evolve probability distributions favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We provide a rigorous runtime analysis concerning the update strength, a vital parameter in PMBGAs such as the step size 1 / K in the so-called compact Genetic Algorithm (cGA) and the evaporation factor ρ in ant colony optimizers (ACO). While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to unstable behavior and possibly poor performance. We demonstrate this trade-off for the cGA and a simple ACO algorithm on the well-known OneMax function. More precisely, we obtain lower bounds on the expected runtime of Ω(Kn+nlogn) and Ω(n/ρ+nlogn), respectively, suggesting that the update strength should be limited to 1/K,ρ=O(1/(nlogn)). In fact, choosing 1/K,ρ∼1/(nlogn) both algorithms efficiently optimize OneMax in expected time Θ(nlog n). Our analyses provide new insights into the stochastic behavior of PMBGAs and propose new guidelines for setting the update strength in global optimization.

AB - Probabilistic model-building Genetic Algorithms (PMBGAs) are a class of metaheuristics that evolve probability distributions favoring optimal solutions in the underlying search space by repeatedly sampling from the distribution and updating it according to promising samples. We provide a rigorous runtime analysis concerning the update strength, a vital parameter in PMBGAs such as the step size 1 / K in the so-called compact Genetic Algorithm (cGA) and the evaporation factor ρ in ant colony optimizers (ACO). While a large update strength is desirable for exploitation, there is a general trade-off: too strong updates can lead to unstable behavior and possibly poor performance. We demonstrate this trade-off for the cGA and a simple ACO algorithm on the well-known OneMax function. More precisely, we obtain lower bounds on the expected runtime of Ω(Kn+nlogn) and Ω(n/ρ+nlogn), respectively, suggesting that the update strength should be limited to 1/K,ρ=O(1/(nlogn)). In fact, choosing 1/K,ρ∼1/(nlogn) both algorithms efficiently optimize OneMax in expected time Θ(nlog n). Our analyses provide new insights into the stochastic behavior of PMBGAs and propose new guidelines for setting the update strength in global optimization.

KW - Ant colony optimization

KW - Estimation-of-distribution algorithms

KW - Genetic Algorithms

KW - Probabilistic model-building Genetic Algorithms

KW - Runtime analysis

KW - Theory of randomized search heuristics

U2 - 10.1007/s00453-018-0480-z

DO - 10.1007/s00453-018-0480-z

M3 - Journal article

AN - SCOPUS:85052076548

VL - 81

SP - 1450

EP - 1489

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -