Naslov
Elitist Ant System with 2-opt Local Search for the Traveling Salesman Problem

Autori
Martinović, Goran ; Bajer, Dražen

Izvornik
Advances in Electrical and Computer Engineering (1582-7445) 12 (2012), 1; 25-32

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
2-opt algorithm; elitist ant system; local search; search stagnation; Traveling Salesman Problem

Sažetak
The Traveling Salesman Problem is one of the most famous problems in combinatorial optimization. The paper presents an algorithm based upon the elitist ant system for solving the traveling salesman problem. 2-opt local search is incorporated in the elitist ant system, and it is used for improvement of a given number of solutions previously constructed by artificial ants. A simple mechanism for avoiding a too early stagnation of the search is also proposed. The aforementioned is based on depositing strong pheromones on solution edges of randomly selected ants called random elitist ants. The aim is to encourage exploration in a greater area of the solution space. Experimental analysis shows how high-quality solutions can be achieved by using the considered algorithm instead of the usual elitist ant system with incorporated 2-opt local search.

Izvorni jezik
Engleski

Znanstvena područja
Računarstvo

POVEZANOST RADA