An Extended Ant Colony Algorithm and Its Convergence Analysis

In this work, we propose a stochastic algorithm for solving\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ \mathcal{N}{\wp } - hard $$\end{document} combinatorial optimization problems. The procedure is formulated within the Ant Colony Optimization (ACO) framework, and extends the so-called Graph-based Ant System with time-dependent evaporation factor, (GBAS/tdev) studied in Gutjahr (2002). In particular, we consider an ACO search procedure which also takes into account the objective function value. We provide a rigorous theoretical study on the convergence of the proposed algorithm. Further, for a toy example, we compare by simulation the rate of convergence of the proposed algorithm with those from the Random Search (RS) and from the corresponding procedure in Gutjahr (2002).