Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems

DOI10.1016/J.TCS.2017.10.012MaRDI QIDQ2413317zbMATH OpenOpenAlexFDO

Authors Jianhui Lai, Zijun Wu, Rolf H. Möhring

Publication date 10 April 2018

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.06962

zbMATH Keywords

probabilistic analysis of algorithmsMAX-MIN ant system\((\mu + \lambda)\) EAcross entropy algorithmstochastic runtime analysis of evolutionary algorithms

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

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+epsilon})$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^{3+epsilon}lnn)$ with the edge-based random solution generation for an arbitrary $epsilonin(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 $mimesm$ grid. When the $n$ vertices span a convex polygon, we obtain a stochastic runtime of $O(n^3{m}^{5+epsilon})$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^2{m}^{5+epsilon})$ 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+epsilon}+n^{6k-1}{m}^{epsilon})$ with the vertex-based random solution generation, and a stochastic runtime of $O(n^3{m}^{5+epsilon}+n^{3k}{m}^{epsilon})$ 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.

Recommendations

• On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (extended abstract)
• First steps to the runtime complexity analysis of ant colony optimization
• Computing the variance of tour costs over the solution space of the TSP in polynomial time
• Analyzing the performance of TSP solver methods

Cites work

• scientific article; zbMATH DE number 1179314 (Why is no real title available?)
• scientific article; zbMATH DE number 2050711 (Why is no real title available?)
• scientific article; zbMATH DE number 2117227 (Why is no real title available?)
• A Dynamic Programming Approach to Sequencing Problems
• A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane
• A tutorial on the cross-entropy method
• Algorithm design and applications
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An Introduction to Metric Spaces and Fixed Point Theory
• Ant colony optimization.
• Convergence properties of the cross-entropy method for discrete optimization
• Drift analysis and average time complexity of evolutionary algorithms
• Evolutionary algorithms and matroid optimization problems
• General local search methods
• Improved time complexity analysis of the simple genetic algorithm
• Model-based heuristics for combinatorial optimization: a mathematical study of their asymptotic behavior
• Model-based search for combinatorial optimization: A critical survey
• On Some Properties of Shortest Hamiltonian Circuits
• On the analysis of the \((1+1)\) evolutionary algorithm
• Optimization of computer simulation models with rare events
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Running time analysis of ant colony optimization for shortest path problems
• Runtime Analysis of a Simple Ant Colony Optimization Algorithm
• Runtime analysis of a multi-objective evolutionary algorithm for obtaining finite approximations of Pareto fronts
• Runtime analysis of a simple ant colony optimization algorithm
• Runtime analysis of ant colony optimization on dynamic shortest path problems
• Runtime analysis of ant colony optimization with best-so-far reinforcement
• Runtime analysis of the 1-ANT ant colony optimizer
• Smoothed analysis of algorithms
• The cross-entropy method for combinatorial and continuous optimization

This page was built for publication: Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413317)