Stochastic runtime analysis of a Cross-Entropy algorithm for traveling salesman problems

Abstract This article analyzes the stochastic runtime of a Cross-Entropy algorithm mimicking an Max-Min Ant System with iteration-best reinforcement. It investigates the impact of magnitude of the sample size on the runtime to find optimal solutions for TSP instances. For simple TSP instances that have a { 1 , n } -valued distance function and a unique optimal solution, we show that sample size N ∈ ω ( ln ⁡ n ) results in a stochastically polynomial runtime, and N ∈ O ( ln ⁡ n ) results in a stochastically exponential runtime, where “stochastically” means with a probability of 1 − n − ω ( 1 ) , and n represents number of cities. In particular, for N ∈ ω ( ln ⁡ n ) , we prove a stochastic runtime of O ( N ⋅ n 6 ) with the vertex-based random solution generation, and a stochastic runtime of O ( N ⋅ n 3 ln ⁡ n ) with the edge-based random solution generation. These runtimes are very close to the best known expected runtime for variants of Max-Min Ant System with best-so-far reinforcement by choosing a small N ∈ ω ( ln ⁡ n ) . They are obtained for the stronger notion of stochastic runtime, and analyze the runtime in most cases. 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 4 m 5 + ϵ ) with the vertex-based random solution generation, and a stochastic runtime of O ( n 3 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 6 k − 1 m ϵ ) with the vertex-based random solution generation, and a stochastic runtime of O ( n 3 m 5 + ϵ + n 3 k 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.