The analysis of evolutionary optimisation on the TSP1,2 problem
Abstract
TSP1,2 problem is a special case of the travelling salesperson problem which is NP-hard. Many heuristics including evolutionary algorithms EAs are proposed to solve the TSP1,2 problem. However, we know little about the performance of the EAs for the TSP1,2 problem. This paper presents an approximation analysis of the 1+1 EA on this problem. It is shown that both the 1+1 EA and µ + λ EA can obtain 3/2 approximation ratio for this problem in expected polynomial runtime On3 and Oµ/λn3 + n, respectively. Furthermore, we prove that the 1+1 EA can provide a much tighter upper bound than a simple ACO on the TSP1,2 problem.
References
[1]
Angel, E. (2006) 'A survey of approximation results for local search algorithms, efficient approximation and online algorithms', Lecture Notes in Computer Science, Vol. 3484, pp. 30-73.
[2]
Applegate, D., Bixby, R.E., Chvátal, V. and Cook, W. (2006) The Traveling Salesman Problem: A Computational Study, Princeton University Press, Princeton.
[3]
Cook, W. (2011) In Pursuit of the Salesman: Mathematics at the Limits of Computation, Princeton University Press, Princeton.
[4]
Droste, S., Jansen, T. and Wegener, I. (2002) 'On the analysis of the (1+1) evolutionary algorithm', Theoretical Computer Science, Vol. 276, pp. 51-81.
[5]
Giel, O. and Wegener I. (2003) 'Evolutionary algorithms and the maximum matching problem', in STACS: Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science, London, UK: Springer-Verlag, pp. 415-426.
[6]
Gu, F., Liu, H. and Li, X. (2016) 'A fast evolutionary algorithm with searching preference', International Journal of Computational Science and Engineering, Vol. 12, No. 1, pp. 29-37.
[7]
Guo, Z., Huang, H., Yang, H., Wang, S. and Wang, H. (2015) 'An enhanced gravitational search algorithm for global optimisation', International Journal of Wireless and Mobile Computing, Vol. 9, No. 3, pp. 273-280.
[8]
Guo, Z., Yue, X., Zhang, K., Deng, C. and Liu, S. (2015) 'Enhanced social emotional optimisation algorithm with generalised opposition-based learning', International Journal of Computing Science and Mathematics, Vol. 6, No. 1, pp. 59-68.
[9]
Gutin, G. and Punnen, A. (Eds.) (2002) The Traveling Salesman Problem and its Variations, Vol. 12 of Combinatorial Optimization, Kluwer, Dordrecht.
[10]
Jansen, T. (2013) Analyzing Evolutionary Algorithms. The Computer Science Perspective, Springer.
[11]
Jia, L., Wang, Y. and Fan, L. (2016) 'An improved uniform design-based genetic algorithm for multi-objective bilevel convex programming', International Journal of Computational Science and Engineering, Vol. 12, No. 1, pp. 38-46.
[12]
Kötzing, T., Neumann, F., Röglin, H. and Witt, C. (2012) 'Theoretical analysis of two ACO approaches for the traveling salesman problem', Swarm Intelligence, Vol. 6, No. 1, pp. 1-21.
[13]
Karp, R.M. (1972) 'Reducibility among combinatorial problems', in Raymond E. Miller and James W. Thatcher (Eds.): Complexity of Computer Computations, pp. 85-103, Plenum, New York.
[14]
Lai, X., Zhou, Y., He, J. and Zhang J. (2014) 'Performance analysis on evolutionary algorithms for the minimum label spanning tree problem', IEEE Transactions on Evolutionary Computation, Vol. 18, No. 6, pp. 860-872.
[15]
Li, D., Hao, H., Ji, G. and Zhao, J. (2015) 'An adaptive clustering algorithm based on improved particle swarm optimisation in wireless sensor networks', International Journal of High Performance Computing and Networking, Vol. 8, No. 4, pp. 29-37.
[16]
Neumann, F. and Wegener I. (2007) 'Randomized local search, evolutionary algorithms, and the minimum spanning tree problem', Theoretical Computer Science, Vol. 378, No. 1, pp. 32-40.
[17]
Neumann, F. and Witt C. (2010) 'Bioinspired computation in combinatorial optimization - algorithms and their computational complexity', Natural Computing Series, Springer.
[18]
Nix, A.E. and Vose, M.D. (1992) 'Modeling genetic algorithms with Markov chain', Annals of Mathematics and Artificial Intelligence, Vol. 5, No. 1, pp. 79-88.
- The analysis of evolutionary optimisation on the TSP1,2 problem
Recommendations
Co-evolutionary Diversity Optimisation for the Traveling Thief Problem
Parallel Problem Solving from Nature – PPSN XVIIAbstractRecently different evolutionary computation approaches have been developed that generate sets of high quality diverse solutions for a given optimisation problem. Many studies have considered diversity 1) as a mean to explore niches in behavioural ...
An Endosymbiotic Evolutionary Algorithm for Optimization
This paper proposes a new symbiotic evolutionary algorithm to solve complex optimization problems. This algorithm imitates the natural evolution process of endosymbionts, which is called endosymbiotic evolutionary algorithm. Existing symbiotic ...
A synergistic approach for evolutionary optimization
GECCO '08: Proceedings of the 10th annual conference companion on Genetic and evolutionary computationOne of the major causes of premature convergence in Evolutionary Algorithm (EA) is loss of population diversity, which pushes the search space to a homogeneous or a near-homogeneous configuration. In particular, this can be a more complicated issue in ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Inderscience Publishers
Geneva 15, Switzerland
Publication History
Published: 25 May 2019
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024