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 条

[1] POPMUSIC for the travelling salesman problem
Taillard, Eric D.
Helsgaun, Keld
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2019, 272 (02) : 420 - 429
[2] Evolving ensembles of heuristics for the travelling salesman problem
Gil-Gala, Francisco J.
Durasevic, Marko
Sierra, Maria R.
Varela, Ramiro
NATURAL COMPUTING, 2023, 22 (04) : 671 - 684
[3] An Analysis of the Fitness Landscape of Travelling Salesman Problem
Tayarani-N, Mohammad-H.
Prugel-Bennett, Adam
EVOLUTIONARY COMPUTATION, 2016, 24 (02) : 347 - 384
[4] A memetic ant colony optimization algorithm for the dynamic travelling salesman problem
Mavrovouniotis, Michalis
Yang, Shengxiang
SOFT COMPUTING, 2011, 15 (07) : 1405 - 1425
[5] A linearithmic heuristic for the travelling salesman problem
Taillard, eric D.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2022, 297 (02) : 442 - 450
[6] A class of exponential neighbourhoods for the quadratic travelling salesman problem
Woods, Brad D.
Punnen, Abraham P.
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2020, 40 (02) : 303 - 332
[7] GLS Optimization Algorithm for Solving Travelling Salesman Problem
Neissi, Nourolhoda Alemi
Mazloom, Masoud
SECOND INTERNATIONAL CONFERENCE ON COMPUTER AND ELECTRICAL ENGINEERING, VOL 1, PROCEEDINGS, 2009, : 291 - +
[8] A GPU Accelerated Parallel Heuristic for Travelling Salesman Problem
Rashid, Mohammad Harun
2018 19TH IEEE/ACIS INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, ARTIFICIAL INTELLIGENCE, NETWORKING AND PARALLEL/DISTRIBUTED COMPUTING (SNPD), 2018, : 82 - 86
[9] A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem
Deineko, VG
Woeginger, GJ
MATHEMATICAL PROGRAMMING, 2000, 87 (03) : 519 - 542
[10] A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem
Deǐneko V.G.
Woeginger G.J.
Mathematical Programming, 2000, 87 (3) : 519 - 542

← 1 2 3 4 5 →