Drift analysis of ant colony optimization of stochastic linear pseudo-boolean functions

作者：Brahimi Nassim^*; Salhi Abdellah; Ourbih Tari Megdouda

来源：Operations Research Letters, 2017, 45(4): 342-347.

DOI：10.1016/j.orl.2017.05.002

• Drift analysis
• Runtime analysis
• Ant System
• Global optimization

In this paper we study the behavior of a variant of the Max-Min Ant System algorithm when applied to a stochastic Linear Pseudo-Boolean Optimization problem. Previous related work is on a partial analysis of its performance on a different problem. Here, we carry out its complete performance analysis giving a bound on its average runtime using drift analysis. For the purpose, we give a new drift theorem and use it to analyze the algorithm when applied to our problem.

• 出版日期2017-7