SAMODS and SAGAMODS: Novel Algorithms Based on the Automata Theory for the Multiobjective Optimization of Combinatorial Problems

Abstract

This paper states two novel algorithms based on the Automata Theory for the Multiobjective Optimization of Combinatorial Problems. The first algorithm proposed is named SAMODS. It is a hybrid Simulated Annealing MODS inspired algorithm. The main idea behind this approach consists in optimizing a Combinatorial Problem changing the Angle Improvement; this is a novel theory maintain in the classic weighted sum metric. SAMODS avoids unfeasible solutions fall back on the MODS theory. Also, it avoids local optimum due to the use of Boltzmann Distribution Probability for accepting bad solutions as good solutions. The last proposed algorithm was named SAGAMODS. It is an Evolutionary Algorithm based on the MODS theory. In addition to the advantages of SAMODS, SAGAMODS avoids in two
times local optimums because of its Crossover Step. It is taken from the Natural Selection Theory that allows creating new solutions (next generation) support in the current solutions (actual generation). Only the best solutions survive. The proposed algorithms were tested using instances from the well-known TSPLIB. The test was made using problems with two objectives, three objectives, four objectives and five objectives inclusive. The proposed algorithms were compared using metrics from the specialized literature of the Multiobjective Optimization. The results of the metrics applied to the algorithms shows that MODS algorithm was superseded up to 100% out of 100%, in some of the instances worked, by the proposed algorithms.