Adaptive Ant Colony Optimization with node clustering applied to the Travelling Salesman Problem

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F60162694%3AG42__%2F23%3A00557902" target="_blank" >RIV/60162694:G42__/23:00557902 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/61989592:15510/22:73613034

Výsledek na webu

<a href="http://www.elsevier.com/wps/find/journaldescription.cws_home/724666/description#description" target="_blank" >http://www.elsevier.com/wps/find/journaldescription.cws_home/724666/description#description</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.swevo.2022.101056" target="_blank" >10.1016/j.swevo.2022.101056</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Adaptive Ant Colony Optimization with node clustering applied to the Travelling Salesman Problem

Popis výsledku v původním jazyce

This article presents the Ant Colony Optimization algorithm to solve the Travelling Salesman Problem. The proposed algorithm implements three novel techniques to enhance the overall performance, lower the execution time and reduce the negative effects particularly connected with ACO-based methods such as falling into a local optimum and issues with settings of control parameters for different instances. These techniques include (a) the node clustering concept where transition nodes are organised in a set of clusters, (b) adaptive pheromone evaporation controlled dynamically based on the information entropy and (c) the formulation of the new termination condition based on the diversity of solutions in population. To verify the effectiveness of the proposed principles, a number of experiments were conducted using 30 benchmark instances (ranging from 51 to 2,392 nodes with various nodes topologies) taken from the well-known TSPLIB benchmarks and the results are compared with several state-of-the-art ACO-based methods; the proposed algorithm outperforms these rival methods in most cases. The impact of the novel techniques on the behaviour of the algorithm is thoroughly analysed and discussed in respect to the overall performance, execution time and convergence.

Název v anglickém jazyce

Adaptive Ant Colony Optimization with node clustering applied to the Travelling Salesman Problem

Popis výsledku anglicky

This article presents the Ant Colony Optimization algorithm to solve the Travelling Salesman Problem. The proposed algorithm implements three novel techniques to enhance the overall performance, lower the execution time and reduce the negative effects particularly connected with ACO-based methods such as falling into a local optimum and issues with settings of control parameters for different instances. These techniques include (a) the node clustering concept where transition nodes are organised in a set of clusters, (b) adaptive pheromone evaporation controlled dynamically based on the information entropy and (c) the formulation of the new termination condition based on the diversity of solutions in population. To verify the effectiveness of the proposed principles, a number of experiments were conducted using 30 benchmark instances (ranging from 51 to 2,392 nodes with various nodes topologies) taken from the well-known TSPLIB benchmarks and the results are compared with several state-of-the-art ACO-based methods; the proposed algorithm outperforms these rival methods in most cases. The impact of the novel techniques on the behaviour of the algorithm is thoroughly analysed and discussed in respect to the overall performance, execution time and convergence.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

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 periodika

Swarm and Evolutionary Computation

ISSN

2210-6502

e-ISSN

2210-6510

Svazek periodika

70

Číslo periodika v rámci svazku

April 2022

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

18

Strana od-do

101056

Kód UT WoS článku

000780758500003

EID výsledku v databázi Scopus

2-s2.0-85126141002