Open AccessElitist Ant System with 2-opt Local Search for the Traveling Salesman Problem
Author(s) -
Goran Martinović,
Dražen Bajer
Publication year - 2012
Publication title -
advances in electrical and computer engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.254
H-Index - 23
eISSN - 1844-7600
pISSN - 1582-7445
DOI - 10.4316/aece.2012.01005
Subject(s) - travelling salesman problem , 2 opt , mathematical optimization , local search (optimization) , computer science , traveling purchaser problem , bottleneck traveling salesman problem , ant colony optimization algorithms , ant colony , artificial intelligence , mathematics
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