Simple max-min ant systems and the optimization of linear pseudo-Boolean functions

DOI10.1145/1967654.1967673MaRDI QIDQ5276101zbMATH OpenOpenAlexFDO

Authors Timo Kötzing, F. Neumann, Dirk Sudholt, Markus Wagner

Publication date 14 July 2017

Published in Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.4707, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.725.2372

zbMATH Keywords

ant colony optimizationruntime analysispseudo-Boolean optimizationMMAS

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Abstract: With this paper, we contribute to the understanding of ant colony optimization (ACO) algorithms by formally analyzing their runtime behavior. We study simple MAX-MIN ant systems on the class of linear pseudo-Boolean functions defined on binary strings of length 'n'. Our investigations point out how the progress according to function values is stored in pheromone. We provide a general upper bound of O((n^3 log n)/ ho) for two ACO variants on all linear functions, where ( ho) determines the pheromone update strength. Furthermore, we show improved bounds for two well-known linear pseudo-Boolean functions called OneMax and BinVal and give additional insights using an experimental study.

Recommendations

• Drift analysis of ant colony optimization of stochastic linear pseudo-Boolean functions
• First steps to the runtime complexity analysis of ant colony optimization
• Runtime analysis of ant colony optimization with best-so-far reinforcement
• Runtime Analysis of a Simple Ant Colony Optimization Algorithm
• Comparing Variants of MMAS ACO Algorithms on Pseudo-Boolean Functions

Cited in

(11)

• Comparing Variants of MMAS ACO Algorithms on Pseudo-Boolean Functions
• Drift analysis of ant colony optimization of stochastic linear pseudo-Boolean functions
• Analysis of the (1 + 1) EA on subclasses of linear functions under uniform and linear constraints
• Working principles of binary differential evolution
• Runtime analysis of ant colony optimization with best-so-far reinforcement
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• scientific article; zbMATH DE number 1488089 (Why is no real title available?)
• Running time analysis of ant colony optimization for shortest path problems
• First steps to the runtime complexity analysis of ant colony optimization
• A simple ant colony optimizer for stochastic shortest path problems
• scientific article; zbMATH DE number 2215631 (Why is no real title available?)

This page was built for publication: Simple max-min ant systems and the optimization of linear pseudo-Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5276101)