Comparative study : AGO and EC for TSP

• Autorzy: Boryczka U. , Skinderowicz R. , Swistowski D.
• Konferencja: Evolutionary Computation and Global Optimization 2006 / National Conference (9 ; 31.05-2.06.2006 ; Murzasichle, Poland)
• Języki publikacji: EN

Abstrakty

EN

Evolutionary Computing (EC) and Ant Colony Optimization (ACO) apply stochastic searching, parallel investigation as well as autocatalitic process (or stigmergy) to solve optimization problems. This paper concentrates on the Traveling Salesman Problem (TSP) solved by evolutionary and ACO algorithms. We consider the sets of parameters and operators which influence the acting of these algorithms. Two algorithmic structures emphasizing the selection problem are discussed. We describe experiments performed for different instances of TSP problems. The comparison concludes that evolution, which is exploited especially in evolutionary algorithms, can also be observed in the performance of the ACO approach.

Słowa kluczowe

EN

evolutionary computing; EC; ant colony optimization; ACO; traveling salesman problem; TSP; optimization

PL

obliczenia ewolucyjne; algorytm mrówkowy; problem komiwojażera; optymalizacja

• Wydawca: Oficyna Wydawnicza Politechniki Warszawskiej
• Czasopismo: Prace Naukowe Politechniki Warszawskiej. Elektronika
• Rocznik: 2006
• Tom: z. 156
• Strony: 69--76
• Opis fizyczny: Bibliogr. 10 poz., tab., wykr.

Twórcy

autor

Boryczka U.

autor

Skinderowicz R.

autor

Swistowski D.

• University of Silesia, Institute of Computer Science, Sosnowiec, Poland,

Bibliografia

• [1] U. Boryczka. Influence of the Problem Representation over the Selection of the Genetic Operators in the Genetic Algorithms. In Proceedings of the Conference "Expert Systems", Wrocław, 1997.
• [2] U. Boryczka and M. Boryczka. Generative Policies in Ant System. In Proceedings of the Conference EUFIT'97, pages 857-861, Aachen, 8-11 wrzesień 1997.
• [3] A. Colorni, M. Dorigo and V. Maniezzo. Distributed Optimization by Ant Colonies. In F. Vavala and P. Bourgine, editors, Proceedings of First European Conference on Artificial Life, pages 134-142, Cambridge, 1991. MIT Press.
• [4] A. Colorni, M. Dorigo and V. Maniezzo. An investigation of some properties of Ant System. In Proceedings of the Parallel Problem Solving from Nature Conferrence (PPSN92), Bruksela, 1992.
• [5] M. Dorigo, V. Maniezzo and A. Colorni. Positive Feedback as a Search Strategy. Technical Report 91-016, Politechnico di Milano, Włochy, 1991.
• [6] L.M. Gambardella and M. Dorigo. Ant-Q. A Reinforcement Learning Approach to the Traveling Salesman Problem. In Proceedings of Twelfth International Conference on Machine Learning, pages 252-260, Palo Alto, CA, 1995. Morgan Kaufman.
• [7] D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.
• [8] S. Goss, R. Beckers, J.L. Deneubourg, S. Aron and J.M. Pasteels. How Trail Laying and Trail Following can solve Foraging Problems for Ant Colonies. In R.N. Hughes, editor, Behavioural Mechanisms for Food Selection, volume G20, Berlin, 1990. Springer Verlag.
• [9] J. Holland. Adaptation in Natural and Artificial Systems. MIT Press, 1975.
• [10] Z. Michalewicz. Algorytmy genetyczne + struktury danych = programy. WNT, 1996.