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%.