This paper was accepted for publication in The International Journal of Artificial Intelligence. Special Issue in Metaheuristic in Artificial Intelligence. It will be available by January of 2012.
Authors: Elias D. Nino
Authors: Elias D. Nino
Here is the 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.
Graphic Comparison MODS, SAMODS and SAGAMODS for Three-objectives instances of TSP:
For a detail definition and analysis of the results, wait for the entire paper.
No hay comentarios:
Publicar un comentario