GLOBAL KARINCA KOLONİSİ OPTİMİZASYONU

Yıl 2006, Cilt: 21 Sayı: 4, 0 - , 02.04.2013

Timur Keskintürk Hasan Söyler

Öz

Bu çalışmada, Global Karınca Kolonisi Algoritması (Global Ant Colony Optimization) (GACO) adı verilen yeni bir karınca kolonisi optimizasyon tekniği anlatılmaktadır. Geliştirilmiş birçok karınca kolonisi optimizasyonu (Ant Colony Optimization) (ACO) sisteminden farklı olarak, karıncaların tam bir tur yapma ya da tüm düğümlere uğrama zorunlulukları yoktur. Özellikle sipariş büyüklüğü problemlerine (Lot Sizing Problem) (LSP) alternatif bir çözüm önerisi olarak geliştirilen GACO’da, herhangi bir düğümden başlayarak ve herhangi bir ya da birden fazla düğüme uğrayarak bir çözüm alternatifi geliştirmek mümkündür. Mevcut ACO’lardan ayrıldığı en temel bir diğer fark ise bölgesel feromon güncellemesinin olmayışıdır. Feromon güncellemesi ve karıncaların yol seçimi yolun tamamı dikkate alınarak gerçekleştirilmektedir. GACO, literatürdeki farklı tip ve boyutlardaki LSP’ne uygulanmıştır. Sonuçlar GACO’nun hem sonuçlar hem de süreler açısından LSP’nin çözümüne iyi bir alternatif olduğunu göstermektedir.

Anahtar Kelimeler

Karınca kolonisi optimizasyonu, global karınca kolonisi optimizasyonu, sipariş büyüklüğü problemi.

Kaynakça

• Dorigo, M., Gambardella, L.M., “Ant Colonies for the Travelling Salesman Problem”, Biosystems, 43 (2), 73–81, 1997.
• Dorigo, M., Gambardella L-M., “Ant Colonies for the Traveling Salesman Problem”, TR/IRIDIA/3, Universite´ Libre de Bruxelles Belgium, 1996.
• Dorigo M, Gambardella L.M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem”, TR/IRIDIA/5, Universite´ Libre de Bruxelles Belgium, 1996.
• Maniezzo, V., Gambardella L.M., De Luigi, F., “Ant Colony Optimization”, New optimization techniques in engineering, Springer, Heidelberg, Germany, 101–121, 2004.
• Dorigo, M., Maniezzo, V., Colorni, A., “The Ant System: Optimization by a Colony of Cooperating Agents”, IEEE Trans. Systems Man Cybernetics, B 26: 29–42, 1996.
• Colorni, A., Dorigo, M., Maniezzo., V., “An Investigation of Some Properties of an “Ant Algorithm””, In Proceedings of the Paralel Problem Solving from Nature Conference, Elsevier Publishing, Brussels, Belgium, 509–520, 1992.
• Gambardella, L.M., Dorigo, M., “Ant-Q: A Reinforcement Learning Approach to the Travelling Salesman Problem”, Proceedings of the Twelfth International Conference on Machine Learning, California, USA, 1995.
• 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.
• Dorigo, M., Gambardella, L.M., “Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem”, IEEE Transaction on Evolutionary Computation, 1, 53-66, 1997.
• Stützle, T., Hoos, H.H., “Max Min Ant System”, Journal of Future Generation Computer Systems, 8 (16), 889–914, 2000.
• Tsai C.F., Tsai C. W., Tseng, C.C., “A New Hybrid Heuristic Approach for Solving Large Traveling Salesman Problem”, Information Sciences, 166(1-4), 67-81, 2004.
• Gambardella L., Taillard, E.D., Agazzi, G., “MACS-VRPT: A Multiple Ant Colony System with for Vehicle Routing Problems with Time Windows”, New Ideas in Optimization, Ed.: Corne, D., Dorigo, M., Glover, F., Mc Graw-Hill, 63-76.
• Middendorf, M., Reischle, F., Schmeck, H., “Multi Colony Ant Algorithms”, Journal of Heuristics, 8-3, ABI/INFORM Global, 305-320, 2002.
• Randall M., “A Parallel Implementation of Ant Colony Optimization”, Journal of Parallel and Distributed Computing, 62, 1421–1432, 2002.
• Bullnheimer, B., Hartl, R.F., Strauss, C., “An Improved Ant System Algorithm For The Vehicle Routing Problem”, Ann. Oper. Res., 89, 1999.
• Shelokar, P.S., Jayaraman, V.K., Kulkarni, B.D., “An Ant Colony Classifier System: Application to Some Process Engineering Problems”, Computers and Chemical Engineering, 28, 1577–1584, 2004.
• Rajendran, C., Ziegler, H., “Two Ant-Colony Algorithms For Minimizing Total Flowtime In Permutation Flowshops”, Computers & Industrial Engineering, 48, 789–797, 2005.
• Rajesh, J., Gupta, K., Kusumakar, H.S., Jayaraman, V.K., Kulkarni, B.D., “Dynamic Optimization of Chemical Processes Using Ant Colony Framework”, Computers and Chemistry, 25 (6), 583-595, 2001.
• Dorigo, M., Di Caro, G., Gambardella, L.M., “Ant Algorithms for Discrete Optimization”, Technical Report IRIDIA/98-10, Université Libre de Bruxelles, Belgium, 1998.
• Vijayakumar, K., Prabhaharan, G., Asokan, P., Saravanan, R., “Optimization of Multi-Pass Turning Operations Using Ant Colony System”, International Journal of Machine Tools and Manufacture, 43 (15), 1633-1639, 2003.
• Azimi Z.N. “Hybrid heuristics for Examination Timetabling Problem”, Applied Mathematics and Computation, 163 (2), 705-733, 2005.
• Dorigo, M., Maniezzo, V., Colorni, A., “The Ant System: An Autocatalytic Optimizing Process”, Technical Report TR91-016, Politecnico di Milano, 1991.
• Gambardella L. M., Dorigo M. “An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem”, INFORMS Journal on Computing, 12, 3 ABI/INFORM Global, 237-255, 2000.
• Lee Z. J., Lee C.Y, “A Hybrid Search Algorithm with Heuristics for Resource Allocation Problem”, Information Sciences, 173 (1-3), 155-167, 2005.
• Brahimi, N., Dauzere-Peres, S., Najid, N. Nordli, M., A., “Single Item Lot Sizing Problem”, European Journal of Operational Research, 168, 1-16, 2006.
• Murata, T., Ishibuchi, H., “Positive and Negative Combination Effects of Crossover and Mutation Operators in Sequencing Problems”, Proc. of The 3rd IEEE International Conference on Evolutionary Computing, 170-175, 1996.
• Basnet C., Leung, M. Y., “Inventory Lot-Sizing with Supplier Selection”, Computers & Operation Research, 32, 1-14, 2005.
• Staggemeier, A.T., Clark, A.R., “A Survey of Lot-Sizing and Scheduling Models”, 23rd Annual Symposium of the Brazilian Operational Research Society, 2001.
• Bahl, H.C.,Ritzman, L.P.,Gupta, J.N.D., “Determining Lot Sizes and Resource Requirements: A Review”, Operation Research, 34(3), 330-345, 1986.
• Taşgetiren, M.F., Liang, Y. H., “A binary Particle Swarm Optimization Algorithm for Lot Sizing Problem”, Journal of Economic and Social Research, 5 (2), 1-20, 2004
• Wagner H.M., Whitin T.M., “Dynamic Verson of the Economic Lot Size Model”, Management Science, 5, 89-96, 1958.
• Haddock, J., D. Hubicki, E., “Which Lot-Sizing Techniques are Used in Material Requirements Planning?”, Production and Inventory Management Journal, 30, 3; 1989.
• Khouja, M., Michalewicz, Z., Wilmot, M., “The Use of Genetic Algorithms to Solve the Economic Lot Size Scheduling Problem”, European Journal of Operational Research, 110, 509-524, 1998.
• Van Hop, N., Tabucanon, M.T. (2000). "Adaptive Genetic Algorithm for Lot Sizing Problem with Self-adjustment Operation Rate", The International Conference on Production Research, Bangkok, Thailand, 2000.
• Kimms, A., “A Genetic Algorithm for Multi-Level, Multi Machine Lot Sizing and Scheduling”, Computers & Operation Research, 26, 829-848, 1999.
• Dellaert, N., Juenut, J., Jonar N., “A Genetic Algorithm to Solve the General Multi-Level Lot-Sizing Problem with Time Varying Costs”, 68, 241-257, 2000.
• Keskintürk, T., Akçay, Ö., “An Order Encoding Genetic Algorithm For Lot Sizing Problem with Supplier Selection”, Proceedings of the 35th International Conference on Computers and Industrial Engineering, 1135-1140, 2005.
• Sarker, R., Newton, C., “A Genetic Algorithm For Solving Economic Lot Size Scheduling Problem”, Computers & Industrial Engineering, 42, 189-198, 2002.
• Van Norden, L., Van de Velde, S., “Multi-Product Lot-Sizing with a Transportation Capacity Reservation Contract”, European Journal of Operational Research, 165, 127-138, 2005.
• Drexl, A., Kimms, A., “Lot Sizing and Scheduling -Survey and Extensions”, European Journal of Operational Research, 99, 221-235, 1997.
• Silver, E.A., Pyke, D.F., Peterson, R.,, Inventory Management and Production Planning and Scheduling, Wiley, New York. 1998.