Introducing a hash function for the travelling salesman problem for differentiating solutions
Pages 123 - 124
Abstract
Solution comparison is a process used in different classes of evolutionary algorithms. It can be either for choosing a better solution or differentiating a pair of solutions. While there is no doubt that the fitness function allows determining the best solution, its use to distinguish between solutions is questionable, especially for combinatorial optimisation problems. This short paper focuses on the Travelling Salesman Problem (TSP). 39 instances of the TSPLIB are chosen, two solution samples are generated for each instance. A collision analysis of the fitness function one the TSP is presented, then an introduction to an efficient hash function with almost zero collisions.
References
[1]
Alexander EI Brownlee, John R Woodward, and Jerry Swan. 2015. Metaheuristic design pattern: surrogate fitness functions. In Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation. 1261--1264.
[2]
P. Larrañaga, Cindy Kuijpers, R.H. Murga, I. Inza, and S. Dizdarevic. 1999. Genetic algorithms for the travelling salesman problem: A review of representations and operators. Artificial intelligence review: An international survey and tutorial journal 13, 2 (4 1999), 129--170.
[3]
Gerhard Reinelt. 1991. TSPLIB---A traveling salesman problem library. ORSA journal on computing 3, 4 (1991), 376--384.
[4]
Thomas Stutzle. 2006. Iterated local search for the quadratic assignment problem. European Journal of Operational Research 174, 3 (2006), 1519 -- 1539.
[5]
Toffolo Túlio A.M., Vidal Thibaut, and Wauters Tony. 2019. Heuristics for vehicle routing problems: Sequence or set optimization? Computers Operations Research 105 (2019), 118 -- 131.
[6]
Christos Voudouris and Edward Tsang. 1999. Guided local search and its application to the traveling salesman problem. European journal of operational research 113, 2 (1999), 469--499.
[7]
David L. Woodruff and Eitan Zemel. 1993. Hashing vectors for tabu search. Annals of Operations Research 41 (1993), 123--137.
Index Terms
- Introducing a hash function for the travelling salesman problem for differentiating solutions
Recommendations
Why many travelling salesman problem instances are easier than you think
GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation ConferenceWhile there are many inexact heuristics for generating high quality solutions to the Travelling Salesman Problem, our understanding of why these methods are effective and efficient is still limited. This paper looks at two population based heuristics: ...
Fairer Comparisons for Travelling Salesman Problem Solutions Using Hash Functions
Evolutionary Computation in Combinatorial OptimizationAbstractFitness functions fail to differentiate between different solutions with the same fitness, and this lack of ability to distinguish between solutions can have a detrimental effect on the search process. We investigate, for the Travelling Salesman ...
Application of a Genetic Algorithm with Random Crossover and Dynamic Mutation on the Travelling Salesman Problem
Travelling salesman problem is a combinatorial optimization problem with wide application background and important theoretical value. The traditional method is only suitable for solving small scale travelling salesman problems, thus limiting the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2021
2047 pages
Copyright © 2021 Owner/Author.
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 July 2021
Check for updates
Author Tags
Qualifiers
- Poster
Conference
GECCO '21
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 70Total Downloads
- Downloads (Last 12 months)7
- Downloads (Last 6 weeks)1
Reflects downloads up to 09 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in