Lehmer Encoding for Evolutionary Algorithms on Traveling Salesman Problem

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Lehmer Encoding for Evolutionary Algorithms on Traveling Salesman Problem

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Lehmer Encoding for Evolutionary Algorithms on Traveling Salesman Problem

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

<a href="/cs/project/LTAIN19176" target="_blank" >LTAIN19176: Metaheuristický rámec pro vícecílové kombinatorické optimalizační problémy (META MO-COP)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název statě ve sborníku

ACM International Conference Proceeding Series 2022

ISBN

978-1-4503-9574-8

ISSN

—

e-ISSN

—

Počet stran výsledku

7

Strana od-do

216-222

Název nakladatele

ACM

Místo vydání

New York

Místo konání akce

Řím

Datum konání akce

11. 3. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—