Evolutionary Algorithm based on the Automata Theory for the Multi-objective Optimization of Combinatorial Problems
Keywords:
Combinatorial Optimization, Multi-objective Optimization, Automata Theory, Metaheuristic of SwappingAbstract
This paper states a novel, Evolutionary Metaheuristic Based on the Automata Theory (EMODS) for the multiobjective optimization of combinatorial problems. The proposed algorithm uses the natural selection theory in order to explore the feasible solutions space of a combinatorial problem. Due to this, local optimums are often avoided. Also, EMODS exploits the optimization process from the Metaheuristic of Deterministic Swapping to avoid finding unfeasible solutions. The proposed algorithm was tested using well known multi-objective TSP instances from the TSPLIB. Its results were compared against others Automata Theory inspired Algorithms using metrics from the specialized literature. In every case, the EMODS results on the metrics were always better and in some of those cases, the distance from the true solutions was 0.89%.
References
University Of Heidelberg. Tsplib - office research group discrete optimization - university of heidelberg. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.
Elias D. Ni-o. Samods and sagamods: Novel algorithms based on the automata theory for the multi-objective optimization of combinatorial problems. Int. J. of Artificial Intelligence - Special issue of IJAI on Metaheuristics in Artificial Intelligence, accepted, 2012.
Elias D. Ni-o, Carlos Ardila, Yezid Donoso, and Daladier Jabba. A novel algorithm based on deterministic finite automaton for solving the mono-objective symmetric traveling salesman problem. Int. J. of Artificial Intelligence, 5(A10):101-108, 2010.
Elias D. Ni-o, Carlos Ardila, Yezid Donoso, Daladier Jabba, and Agustin Barrios. Mods: A novel metaheuristic of deterministic swapping for the multi objective optimization of combinatorials problems. Computer Technology and Application, 2(4):280-292, 2011.
Elias D. Ni-o, Carlos Ardila, Adolfo Perez, and Yezid Donoso. A genetic algorithm for multiobjective hard scheduling optimization. INT J COMPUT COMMUN, 5(5):825-836, 2010.
J.G. Sauer and L. Coelho. Discrete differential evolution with local search to solve the traveling salesman problem: Fundamentals and case studies. In Cybernetic Intelligent Systems, 2008. CIS 2008. 7th IEEE International Conference on, pages 1-6, 2008.
Yang Xiawen and Shi Yu. A real-coded quantum clone multi-objective evolutionary algorithm. In Consumer Electronics, Communications and Networks (CECNet), 2011 International Conference on, 4683-4687, 2011.
Qin Yong-Fa and Zhao Ming-Yang. Research on a new multiobjective combinatorial optimization algorithm. In Robotics and Biomimetics, 2004. ROBIO 2004. IEEE International Conference on, 187-191, 2004.
Published
Issue
Section
License
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
