IJPAM: Volume 48, No. 2 (2008)

A NEW GENETIC ALGORITHM APPLIED TO
THE TRAVELING SALESMAN PROBLEM

Sawsan K. Amous$^1$, Taïcir Loukil$^2$, Semya Elaoud$^3$, Clarisse Dhaenens$^{4}$
$^{1,2,3}$Faculty of Economics and Management
University of Sfax
Sfax, TUNISIA
$^1$e-mail: amoussawsan@yahoo.fr
$^2$e-mail: taicir.loukil@fsegs.rnu.tn
$^3$e-mail: samyaelaoud@yahoo.fr
$^4$Laboratoire d'Informatique Fondamentale de Lille (LIFL)
Université des Sciences et Technologies de Lille
LIFL - UMR USTL/CNRS 8022 - Bâtiment, M3
Villeneuve d'Ascq Cédex, 59655, FRANCE
e-mail: Clarisse.Dhaenens@lifl.fr


Abstract.Genetic algorithms can be applied to a wide class of combinatorial optimization problems. In this paper, we propose an efficient genetic algorithm (GAs) with some innovative features to solve the traveling salesman problem. We propose a new mutation operator called ``Mutation by Extended Elimination", a revised order Crossover and an Elite Selection Method. This algorithm is tested on a set of benchmarks from the TSP-LIB and compared with a previously published GA. The results show the efficiency of the algorithm when applied on both the Traveling Salesman Problem and a scheduling problem from the literature.

Received: March 13, 2008

AMS Subject Classification: 90A08, 90BXX

Key Words and Phrases: genetic algorithm, traveling salesman problem, combinatorial optimization problem

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2008
Volume: 48
Issue: 2