Stochastic Runtime Analysis of a Cross Entropy Algorithm for Traveling Salesman Problems
share
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+ϵ n) with the edge-based random solution generation for an arbitrary ϵ∈ (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× m grid. When the n vertices span a convex polygon, we obtain a stochastic runtime of O(n^3m^5+ϵ) with the vertex-based random solution generation, and a stochastic runtime of O(n^2m^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^4m^5+ϵ+n^6k-1m^ϵ) with the vertex-based random solution generation, and a stochastic runtime of O(n^3m^5+ϵ+n^3km^ϵ) 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.
READ FULL TEXT