KARINCA KOLONİLERİ METASEZGİSELİ VE GEZGİN SATICI PROBLEMLERİ ÜZERİNDE BİR UYGULAMASI

Öz

Karınca kolonileri meta sezgiseli, popülasyon tabanlı rastsal arama prensibine dayanan bir arama yöntemidir. Doğal süreçlerin gözlemlenmesinden ortaya çıkan, karınca kolonilerinin yiyecek toplama prensibini dikkate alan biyoloji biliminden esinlenerek geliştirilmiş bir meta sezgisel yöntemdir. Bu çalışmada Karınca Sisteminin (KS), algoritması, formülasyonu ve işleyişi belirlenerek son dönemlerde ortaya çıkartılan max-min, mertebe temelli karınca sistemleri hakkında bilgi verilmektedir. Karınca sistemi ile ilgili olarak 1992 yılından günümüze kadar yapılan uygulamalar hakkında bir yayın taraması yapılmıştır. Ayrıca literatürde önerilen gezgin satıcı problemleri, Karınca Kolonileri meta sezgiseli için Visual Basic programlama dilinde hazırlanan Karınca Programı yardımı ile uygun parametreler kullanılarak çözülmüş ve elde edilen sonuçlar optimum değerleri ile kıyaslanmıştır.

Anahtar Kelimeler

• Karınca metasezgiseli, gezgin satıcı problemi.

Kaynakça

1. Dorigo M, Optimization, Learning and Natural Algorithms, PhD tesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992.
2. Colorni A., M. Dorigo, Maniezzo and M. Trubian., Ant system for Job-shop Scheduling, Belgian Journal of Operations Research, Statistics and Computer Science, 1994.
3. http://www.iwr.uni-heidelberg.de/groups/ comopt/software/TSPLIB95/
4. Goss S., Aron S., Deneubourg J. L., and Pasteels J. M., Self-organized Shortcuts in the Argentine Ant, Naturwissenschaften, 76:579-581, 1989.
5. Dorigo M., Maniezzo V., Colorni A., The ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics–Part, 1996.
6. Dorigo M.,Gambardella L.M.., Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactionson Evolutionary Computation, 1(1): 53-66, 1997.
7. Di Caro G., Dorigo M., Extending AntNet for best-effort Quality-of-Service routing, From Ant Colonies to Artificial Ants: First International Workshop on Ant Colony Optimization http://iridia.ulb.ac.be/ants98/ants98.html, 15-16 1998.
8. Gambardella L.M., Dorigo M., Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem., In Proceedings of the Eleventh International Conference on Machine Learning, 252-260. Morgan Kaufmann, 1995.

9. Taillard D., Gambardella M., Gendreau M, Potvin J., Adaptive Memory Programming: A unified view of MetaHeuristics, European Journal of Operational Research, 135(2001), 1-16, 2000.
10. Colorni A., M. Dorigo & V. Maniezzo, Distributed Optimization by Ant Colonies. Proceedings of the First European Conference on Artificial Life, Paris, France, Elsevier Publishing. 1992.
11. Stützle T., Hoos H., The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem, Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC'97), 1997.
12. Stützle T., Local Search Algorithms for Combinatorial Problems |Analysis, Improvements, and New Applications, PhD Tesis, Darmstadt University of Technology, Department of Computer Science, 1998.
13. Bullnheimer B., Hartl R.F., Strauss C., A New Rank Based Version of the Ant System: A Computational Study, Central European Journal for Operations Research and Economics, 1997.
14. V. Maniezzo, A. Colorni, and M. Dorigo., The ant system applied to the quadratic assignment problem. Technical Report IRIDIA/94-28, IRIDIA, Universite Libre de Bruxelles, Belgium, 1994.
15. Stützle T., Hoos H., Improvements on the Ant System: Introducing the MAX-MIN Ant System., Artificial Neural Networks and Genetic Algorithms, Springer Verlag, Wien New York, 1998.
16. White T., Pagurek B., Oppacher F., ASGA: Improving the Ant System by Integration with Genetic Algorithms, Systems and Computer Engineering, Carleton University Pres, 2000.
17. Kawamura H., Yamamoto M., Multiple Ant Colonies Algorithm Based on Colony Level Interactions, IEICE Trans. Fundamentals, 2000.
18. Gagne C., Gravel M., Price W., A Look-Ahead Edition to the Ant Colony Optimization MetaHeuristic and Its Application to an Industrial Scheduling Problem, 4th Metaheuristics International Conference, 2001.
19. Fığlalı, A., Engin, O., Fığlalı, N., A Systematic Procedure For Setting Ant System Parameters, International Conferance On Fuzzy Systems Soft Computational Intelligence In Management And Industrial Engineering, 114 121, 2002.
20. Court J.M., Algorithms and Heuristics for the Travelling Salesman Problem: Implementation, Analysis and Comparison, Technical report, 2003.
21. Stützle T.,Hoos H., MAX-MIN Ant System and Local Search for Combinatorial Optimization Problems, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, Boston, 1999.
22. Gambardella L.M., Taillard E. D., and Dorigo M., Ant colonies for the QAP. Technical Report IDSIA-4-97, IDSIA, Lugano, Switzerland, 1997.
23. Maniezzo V., Colorni A.. The ant system applied to the quadratic assignment problem. IEEE Trans. Knowledge and Data Engineering, 1998.
24. Maniezzo V, Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem. Technical Report CSR 98-1, C. L. In Scienze dell'Informazione, Universite di Bologna, sede di Cesena, Italy, 1998.
25. Bullnheimer B., Strauss C., Tourenplanung mit dem Ant System. Technical Report 6, Institut fƒur Betriebwirtschaftslehre, University of Vienna, Austria, 1996.
26. Gambardella L.M., Taillard E., Agazzi G.. Ant colonies for vehicle routing problems. New Ideas in Optimization, McGraw-Hill, 1999.
27. Schoonderwoerd R., Holland O., Bruten J., Rothkrantz L., Ant-based load balancing in telecommunications networks. Adaptive Behavior, 5(2):169-207, 1996.
28. White T., Pagurek B., Oppacher F.. Connection management using adaptive mobile agents. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (PDPTA'98), 802-809. CSREA Press, 1998.
29. Bonabeau E., Henaux F., Guerin S., Snyers D., Kuntz P., Theraulaz G., Routing in telecommunication networks with "Smart" ant-like agents. In Proceedings of IATA'98, Second Int. Workshop on Intelligent Agents for Telecommunication Applications, Lectures Notes in AI vol. 1437, Springer Verlag, 1998.
30. Di Caro G., Dorigo M., AntNet: A mobile agents approach to adaptive routing. Technical Report IRIDIA/97-12, IRIDIA, Universite Libre de Bruxelles, Belgium, 1997.
31. Subramanian D., Druschel P., Chen J.. Ants and reinforcement learning: A case study in routing in dynamic networks. In Proceedings of IJCAI-97, International Joint Conference on Artificial Intelligence, 832-838. Morgan Kaufmann, 1997.
32. Van der Put R., Routing in the faxfactory using mobile agents. Technical Report R&D-SV-98-276, KPN Research, The Netherlands, 1998.
33. Van der Put R., Rothkrantz L.. Routing in packet switched networks using agents. Simulation Practice and Theory, 1998.
34. Costa D. Hertz A.. Ants can colour graphs. Journal of the Operational Research Society, 48:295-305, 1997.
35. Gambardella L.M., Dorigo M., HAS-SOP: An hybrid ant system for the sequential ordering problem, Technical Report IDSIA-11-97, IDSIA, Lugano, Switzerland, 1997.