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

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 $(μ\!+\!λ)$ EA reported in a recent article, and again obtained for the stronger notion of stochastic runtime.