Stochastic Runtime Analysis of a Cross Entropy Algorithm for Traveling Salesman Problems

Abstract

This article analyzes the stochastic runtime of a Cross-Entropy Algorithm on two classes of traveling salesman problems. The algorithm shares main features of the famous Max-Min Ant System with iteration-best reinforcement. For simple instances that have a $\{1,n\}$-valued distance function and a unique optimal solution, we prove a stochastic runtime of $O(n^{6+ϵ})$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^{3+ϵ}\ln n)$ with the edge-based random solution generation for an arbitrary $ϵ\in (0,1)$. These runtimes are very close to the known expected runtime for variants of Max-Min Ant System with best-so-far reinforcement. They are obtained for the stronger notion of stochastic runtime, which means that an optimal solution is obtained in that time with an overwhelming probability, i.e., a probability tending exponentially fast to one with growing problem size. We also inspect more complex instances with $n$ vertices positioned on an $m\times m$ grid. When the $n$ vertices span a convex polygon, we obtain a stochastic runtime of $O(n^3{m}^{5+ϵ})$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^2{m}^{5+ϵ})$ for the edge-based random solution generation. When there are $k=O(1)$ many vertices inside a convex polygon spanned by the other $n-k$ vertices, we obtain a stochastic runtime of $O(n^4{m}^{5+ϵ}+n^{6k-1}{m}^{ϵ})$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^3{m}^{5+ϵ}+n^{3k}{m}^{ϵ})$ with the edge-based random solution generation. These runtimes are better than the expected runtime for the so-called $(\mu +\lambda )$ EA reported in a recent article, and again obtained for the stronger notion of stochastic runtime.