Brahimi, Nassim and Salhi, Abdellah and Ourbih-Tari, Megdouda (2017) Drift analysis of ant colony optimization of stochastic linear pseudo-boolean functions. Operations Research Letters, 45 (4). pp. 342-347. DOI https://doi.org/10.1016/j.orl.2017.05.002
Brahimi, Nassim and Salhi, Abdellah and Ourbih-Tari, Megdouda (2017) Drift analysis of ant colony optimization of stochastic linear pseudo-boolean functions. Operations Research Letters, 45 (4). pp. 342-347. DOI https://doi.org/10.1016/j.orl.2017.05.002
Brahimi, Nassim and Salhi, Abdellah and Ourbih-Tari, Megdouda (2017) Drift analysis of ant colony optimization of stochastic linear pseudo-boolean functions. Operations Research Letters, 45 (4). pp. 342-347. DOI https://doi.org/10.1016/j.orl.2017.05.002
Abstract
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.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Drift analysis; Runtime analysis; Ant System; Global optimization |
Subjects: | Q Science > QA Mathematics |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 04 Aug 2017 15:57 |
Last Modified: | 30 Oct 2024 17:06 |
URI: | http://repository.essex.ac.uk/id/eprint/19944 |