A novel Algorithm based on Deterministic Finite Automaton for solving the mono-objective Symmetric Traveling Salesman Problem

Tipo de Publicación: Articulo
Categoria: SCOPUS
Idioma: Inglés
Revista: Elias Niño, Carlos Ardila, Daladier Jabba, Yezid Donoso. A novel Algorithm based on Deterministic Finite Automaton for solving the mono-objective Symmetric Traveling Salesman Problem. International Journal of Artificial Intelligence, Volume 5, Number A10. ISSN 0974-0635. 2010.

Abstract

This paper states an Algorithm Based on Finite Automata: the Exchange Deterministic Algorithm (EDA). EDA is an improvement of the EDNR algorithm(Ausiello, Feuerstein, Leonardi, Stougie and Talamo, 2001). that is applied to one of the classic problems in combinatorial optimization: The Symmetric Traveling Salesman Problem (TSP). First, the feasible solutions space of TSP was modeled by using a Deterministic Finite Automaton of Swapping (DFAS). DFAS is a data structure that allows the representation of the feasible solutions space of a combinatorial problem. Once that structure is defined, the algorithm is applied to different random scenarios of the TSP in order to contrast proximity with the global optimum obtained by exhaustive searching. Afterwards, the algorithm is applied to a particular problem, and the results are compared with others that were obtained by techniques such as Ant Colony, GRASP, Genetic Algorithms, Simulated Annealing, and Tabu Search(Bin and Raidl, 2008). EDA surpassed the others in terms of number of iterations the optimum is obtained.

DESCARGAR AQUI/DOWNLOAD HERE