Fairer Comparisons for Travelling Salesman Problem Solutions Using Hash Functions

被引：0

作者：

El Krari, Mehdi ^{[1
]}

Guibadj, Rym Nesrine ^{[2
]}

Woodward, John ^{[3
]}

Robilliard, Denis ^{[2
]}

机构：

[1] Univ Nottingham, Sch Comp Sci, Computat Optimisat & Learning Lab, Nottingham, England

[2] Univ Littoral Cote dOpale, EA 4491 LISIC, Calais, France

[3] Queen Mary Univ London, Sch Elect Engn & Comp Sci, Operat Res Grp, Mile End Rd, London E1 4NS, England

来源：

EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, EVOCOP 2023 | 2023年 / 13987卷

关键词：

Hash functions; Combinatorial Problems; Travelling Salesman Problem; Local Search; Genetic Algorithms; Memetic Algorithms; LOCAL SEARCH;

D O I：

10.1007/978-3-031-30035-6_1

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Fitness 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 Problem (TSP), the impact of using a hash function to differentiate solutions during the search process. Whereas this work is not intended to improve the state-of-the-art of the TSP solvers, it nevertheless reveals a positive effect when the hash function is used.

引用

页码：1 / 15

页数：15

共 50 条

[41] Evolutionary Algorithm Using Random Immigrants for the Multiobjective Travelling Salesman Problem
Michalak, Krzysztof
KNOWLEDGE-BASED AND INTELLIGENT INFORMATION & ENGINEERING SYSTEMS (KSE 2021), 2021, 192 : 1461 - 1470
[42] Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
Eremeev, Anton V.
Kovalenko, Yulia V.
LARGE-SCALE SCIENTIFIC COMPUTING, LSSC 2017, 2018, 10665 : 341 - 349
[43] A novel discrete bat algorithm for solving the travelling salesman problem
Saji, Yassine
Riffi, Mohammed Essaid
NEURAL COMPUTING & APPLICATIONS, 2016, 27 (07) : 1853 - 1866
[44] A memetic algorithm with optimal recombination for the asymmetric travelling salesman problem
Anton V. Eremeev
Yulia V. Kovalenko
Memetic Computing, 2020, 12 : 23 - 36
[45] Predicting Hardness of Travelling Salesman Problem Instances
Cardenas-Montes, Miguel
ADVANCES IN ARTIFICIAL INTELLIGENCE, CAEPIA 2016, 2016, 9868 : 68 - 78
[46] Application of the noising method to the travelling salesman problem
Charon, I
Hudry, O
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 125 (02) : 266 - 277
[47] Iteration Multilevel Method for the Travelling Salesman Problem
Starostin, Nikolay V.
Klyuev, Ilya V.
KNOWLEDGE-BASED SOFTWARE ENGINEERING, JCKBSE 2014, 2014, 466 : 477 - 482
[48] A Genetic Algorithm for Solving Travelling Salesman Problem
Philip, Adewole
Taofiki, Akinwale Adio
Kehinde, Otunbanowo
INTERNATIONAL JOURNAL OF ADVANCED COMPUTER SCIENCE AND APPLICATIONS, 2011, 2 (01) : 26 - 29
[49] Evolving ensembles of heuristics for the travelling salesman problem
Francisco J. Gil-Gala
Marko Durasević
María R. Sierra
Ramiro Varela
Natural Computing, 2023, 22 : 671 - 684
[50] The Travelling Salesman Problem on Permuted Monge Matrices
Burkard R.E.
Deǐneko V.G.
Woeginger G.J.
Journal of Combinatorial Optimization, 1998, 2 (4) : 333 - 350

← 1 2 3 4 5 →