Meta-heurística Híbrida de Sistema de Colônia de Formigas e Algoritmo Genético para o Problema do Caixeiro Viajante
DOI:
https://doi.org/10.5540/tema.2008.09.01.0031Abstract
Apresentamos neste artigo, uma nova Meta-heurística Híbrida de Sistema de Colônia de Formigas (ACS) e Algoritmos Genéticos (AG) para resolver o Problema do Caixeiro Viajante (PCV). A resolução do Problema do Caixeiro Viajante é complexa, pois envolve uma busca em um enorme espaço de soluções que cresce conforme aumenta o número de nós do grafo, tornando inviável a utilização de métodos exatos. O Algoritmo Híbrido ACS+AG-PCV é proposto visando obter bons resultados, de maneira a contornar a questão da complexidade do Problema do Caixeiro Viajante.References
[1] M. Affenzeller, S.Wagner, A self-adaptive model for selective pressure handling within the of genetic algorithms. In: “Computer Aided Systems Theory”, Eurocast, Spriger Verlag, 2809, pp. 384-393, 2003.
E. Bonabeau, M. Dorigo, G. Theraulaz, “Swarm Intelligence: From Natural to Artificial Systems”, Oxford University Press, New York, 1999.
Bullnheimer, R.F. Hartz, C. Strauss, An improved ant system algorithm for the vehicle routing problem, Annals of Operations Research, 1999.
M. Dorigo, “Ottimizzazione, apprendimento automatico, ed algoritmi basati sumetafora naturale (Optimization, Learning, and Natural Algorithms)”, Ph.D.
Dissertation, Politecnico di Milano, Press, 1992.
M. Dorigo, L. M. Gambardella, Ant colonies for the traveling salesman problem, BioSystems, 43 (1997), 73-81.
M. Dorigo, T. St¨utzle, ACO Algorithms for the Traveling Salesman Problem, In Evolutionary Algorithms in Engineering and Computer Science (K. Miettinen, M. Makela, P. Neittaanmaki, J. Periaux, eds.) Wiley, 1999.
M.R. Garey, D.S. Johnson, “Computers and Intractability: a Guide to the Theory of NP-Completeness”, San Francisco, CA: W. H. Freeman, 1979.
J.H. Holland, “Adaptation in Natural and Artificial Systems”, 2 ed., MIT Press, MA, USA, 1992.
S. Lin, B.W. Kernighan, An effective heuristic algorithm for the traveling salesman problem. Operations Research, 21 (1973), 498-516.
P. Merz, B. Freisleber, Genetic Local Search for the TSP: New results. In: IEEE International Conference on Evolutionary, IEEE Press, pp. 159-164, Indaianapolis, 1997.
Z. Michalewicz, “Genetic Algorithms + Data Structures = Evolution Programs”, Springer-Verlag, Berlin, 1996.
M.L. Pilat, T. White, Using genetic algorithms to optimize ACS-TSP, in “Proceedings of the Third International Workshop on Ant Algorithms - ANTS”, pp. 282-287, Springer-Verlag, 2002.
G. Reinelt, TSPLIB: A travelling salesman problem library. ORSA Journal on Computing, 3 (1991), 376-384.
S.C. Sari, H.D. Sherali, A. Bhootra, New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence
constraints. Operations Research Letters, 33, No. 1 (2007), 62-70.
Downloads
Published
How to Cite
Issue
Section
License
Authors who publish in this journal agree to the following terms:
Authors retain copyright and grant the journal the right of first publication, with the work simultaneously licensed under the Creative Commons Attribution License that allows the sharing of the work with acknowledgment of authorship and initial publication in this journal.
Authors are authorized to assume additional contracts separately, for non-exclusive distribution of the version of the work published in this journal (eg, publish in an institutional repository or as a book chapter), with acknowledgment of authorship and initial publication in this journal.
Authors are allowed and encouraged to publish and distribute their work online (eg, in institutional repositories or on their personal page) at any point before or during the editorial process, as this can generate productive changes as well as increase impact and the citation of the published work (See The effect of open access).
This is an open access journal which means that all content is freely available without charge to the user or his/her institution. Users are allowed to read, download, copy, distribute, print, search, or link to the full texts of the articles, or use them for any other lawful purpose, without asking prior permission from the publisher or the
author. This is in accordance with the BOAI definition of open access
Intellectual Property
All the contents of this journal, except where otherwise noted, is licensed under a Creative Commons Attribution License under attribution BY.