MODS: A Novel Metaheuristic of Deterministic Swapping for the Multi – Objective Optimization of Combinatorials Problems

Tipo de Publicación: Articulo
Categoria: C (COLCIENCIAS)
Idioma: Inglés
Revista: Elias D. Niño, Carlos J. Ardila , Agustín Barrios and Yezid Donoso. MODS: A Novel Metaheuristic of Deterministic Swapping for the Multi – Objective Optimization of Combinatorials Problems. Computer Technology and Application. Volume 2, Number 4, 2011

Abstract

This paper states a new metaheuristic based on Deterministic Finite Automata (DFA) for the multi – objective optimization of combinatorial problems. First, a new DFA named Multi – Objective Deterministic Finite Automata (MDFA) is defined. MDFA allows the representation of the feasible solutions space of combinatorial problems. Second, it is defined and implemented a metaheuritic based on MDFA theory. It is named Metaheuristic Of Deterministic Swapping (MODS). MODS is a local search strategy that works using a MDFA. Due to this, MODS never take into account unfeasible solutions. Hence, it is not necessary to verify the problem constraints for a new solution found. Lastly, MODS is tested using well know instances of the Bi – Objective Traveling Salesman Problem (TSP) from TSPLIB. Its results were compared with eight Ant Colony inspired algorithms and two Genetic algorithms taken from the specialized literature. The comparison was made using metrics such as Spacing, Generational Distance, Inverse Generational Distance and No-Dominated Generation Vectors. In every case, the MODS results on the metrics were always better and in some of those cases, the superiority was 100%.

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