Lehmer Encoding for Evolutionary Algorithms on Traveling Salesman Problem

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F22%3A10250416" target="_blank" >RIV/61989100:27240/22:10250416 - isvavai.cz</a>
Result on the web
<a href="https://dl.acm.org/doi/10.1145/3529399.3529433" target="_blank" >https://dl.acm.org/doi/10.1145/3529399.3529433</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1145/3529399.3529433" target="_blank" >10.1145/3529399.3529433</a>

Result language
angličtina
Original language name
Lehmer Encoding for Evolutionary Algorithms on Traveling Salesman Problem
Original language description
The traveling salesman problem is a well-known NP-hard permutation optimization problem. It is often successfully solved by nature-inspired metaheuristics such as differential evolution (DE) and particle swarm optimization (PSO). Both algorithms are originally designed for real-parameter optimization in a continuous space. The crucial problem is an appropriate solution representation-a mapping between continuous search space and discrete permutation space. In this work, we study the popular random key (RK) encoding and its properties. We point out its typical issues (solution redundancy, sorting) and propose a novel permutation representation based on the Lehmer code (LC) encoding and its factorial representation. Both encodings are tested with DE and PSO metaheuristics on popular TSP instances. The results are very promising as the LC often significantly overcomes the performance of the RK. (C) 2022 ACM.
Czech name
—
Czech description
—

Project
<a href="/en/project/LTAIN19176" target="_blank" >LTAIN19176: Metaheuristics Framework for Multi-objective Combinatorial Optimization Problems (META MO-COP)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
ACM International Conference Proceeding Series 2022
ISBN
978-1-4503-9574-8
ISSN
—
e-ISSN
—
Number of pages
7
Pages from-to
216-222
Publisher name
ACM
Place of publication
New York
Event location
Řím
Event date
Mar 11, 2022
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)