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

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(n4m5+ϵ) with the vertex-based random solution generation, and a stochastic runtime of O(n3m5+ϵ) 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(n4m5+ϵ+n6k−1mϵ) with the vertex-based random solution generation, and a stochastic runtime of O(n3m5+ϵ+n3kmϵ) 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.