Lale ÖZBAKIR, Pınar TAPKAN, Adil BAYKASOĞLU

208

Arı algoritması ve genelleştirilmiş atama problemi: farklı komşuluk yapılarının karşılaştırılması

Arı Algoritması popülasyon tabanlı yeni bir arama algoritması olup sürü zekâsına dayalı metasezgisel yöntemlerden birisidir. Algoritma gerçek bal arılarının yiyecek arama davranışlarını modellemeye dayanmakta olup bilimsel yazında kombinatoryel ve genellikle de sürekli optimizasyon problemlerinin çözümünde kullanılmıştır. Diğer taraftan Genelleştirilmiş Atama Problemi NP-zor bir problem olup kombinatoryel tamsayılı optimizasyon problemi olarak formüle edilebilmektedir. Bu çalışmada öncelikle Arı Algoritması, Genelleştirilmiş Atama Problemi’nin çözümü için geliştirilmiş ve kaydırma, değiştirme, çift kaydırma ve çıkarım zinciri komşuluk yapılarının Arı Algoritması'nın performansı üzerindeki etkileri incelenmiştir.

Bees algorithm and generalized assignment problem: comparison of different neighborhood structures

Bees Algorithm is a population based new search algorithm which is one of the meta heuristic techniques based on swarm intelligence. Bees Algorithm depends on to model natural behavior of real honey bees in food foraging and is used to obtain solutions for combinatorial and generally continuous optimization problems in the literature. On the other hand, Generalized Assignment Problem is known as an NP-Hard problem and can be formulated as a combinatorial integer optimization problem. In this study, firstly Bees Algorithm is modified to solve Generalized Assignment Problem and the effects of shift, swap, double shift, and ejection chain neighborhood structures on the performance of Bees Algorithm is analyzed.
PDF

___

  • 1. Alfandari, L., Plateau, A., Tolla, P. 2001. “A Two-Phase Path Relinking Algorithm for the Generalized Assignment Problem”, 4th International Conference of Metaheuristics, Porto, Portugal, 175-179.
  • 2. Alfandari, L., Plateau, A., Tolla, P. 2002. “A Two-Phase Path Relinking Algorithm for the Generalized Assignment Problem”, Teknik Rapor No: 378, CEDRIC, CNAM.
  • 3. Alfandari, L., Plateau, A., Tolla, P. 2004. “A Path Relinking Algorithm for the Generalized Assignment Problem”, Metaheuristics: Computer Decision-Making, Hazırlayanlar: Resende, M.G.C., Sousa, J.P., Kluwer Academic Publishers, Boston, 1-17.
  • 4. Baştürk, B., Karaboğa, D. 2006. “An Artificial Bee Colony (ABC) Algorithm for Numeric Function Optimization”, IEEE Swarm Intelligence Symposium, Indianapolis, Indiana, USA.
  • 5. Baykasoğlu, A. 2001. “Goal Programming Using the Multiple Objective Tabu Search”, Journal of Operational Research Society, 52(12), 1359-1369.
  • 6. Baykasoğlu, A. 2006. “Applying the Multiple Objective Tabu Search to Continuous Optimization Problems with a Simple Neighborhood Strategy”, International Journal for Numerical Methods in Engineering, 65, 406-424.
  • 7. Baykasoğlu, A., Özbakır, L., Tapkan, P. 2007. “Artificial Bee Colony Algorithm and its Application to Generalized Assignment Problem”, Swarm Intelligence: Focus on Ant and Particle Swarm Optimization, Hazırlayanlar: Chan, F.T.S., Tiwari, M.K., I-Tech Education and Publishing, Vienna, Austria, 113-144.
  • 8. Chong, C.S., Low, M.Y.H., Sivakumar, A.I., Gay, K.L. 2006. “A Bee Colony Optimization Algorithm to Job Shop Scheduling”, 37th Winter Simulation, Monterey, California, 1954-1961.
  • 9. Chu, P.C., Beasley, J.E. 1997. “A Genetic Algorithm for the Generalized Assignment Problem”, Computers Operations Research, 24, 17-23.
  • 10. Diaz, J.A., Fernandez, E. 2001. “A Tabu Search Heuristic for the Generalized Assignment Problem”, European Journal Operational Research, 132, 22-38.
  • 11. Fisher, M.L., Jaikumar, R., Van Wassenhove, L.N. 1986. “A Multiplier Adjustment Method for the Generalized Assignment Problem”, Management Science, 32, 1095- 1103.
  • 12. Karaboğa, D., Baştürk, B. 2007. “A Powerful and Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony (ABC) Algorithm”, Journal of Global Optimization, 39(3), 459-471.
  • 13. Laguna, M., Kelly, J.P., Gonzalez-Velarde, J.L., Glover, F. 1995. “Tabu Search for the Multilevel Generalized Assignment Problem”, European Journal of Operational Research, 82, 176-189.
  • 14. Lourenço, H.R., Serra, D. 2002. “Adaptive Search Heuristics for the Generalized Assignment Problem”, Mathware and Soft Computing, 9. 209-234.
  • 15. Lucic, P. 2002. “Modeling Transportation Problems Using Concepts of Swarm Intelligence and Soft Computing”, Doktora Tezi, Civil Engineering, Faculty of the Virginia Polytechnic Institute and State University.
  • 16. Lucic, P., Teodorovic, D. 2001. “Bee system: Modeling Combinatorial Optimization Transportation Engineering Problems by Swarm Intelligence”, 4th Triennial Symposium on Transportation Analysis, Sao Miguel, Azores Islands, 441-445.
  • 17. Lucic, P., Teodorovic, D. 2002. “Transportation Modeling: An Artificial Life Approach”, International Conference on Tools with Artificial Intelligence, 216-223.
  • 18. Lucic, P., Teodorovic, D. 2003a. “Computing with Bees: Attacking Complex Transportation Engineering Problems”, International Journal on Artificial Intelligence Tools, 12(3), 375-394.
  • 19. Lucic, P., Teodorovic, D. 2003b. “Vehicle Routing Problem with Uncertain Demand at Nodes: The Bee System and Fuzzy Logic Approach”, Fuzzy Sets in Optimization, Hazırlayan: Verdegay, J.L., Springer-Verlag, Berlin Heidelberg, 67-82.
  • 20. Osman, I.H. 1995. “Heuristics for the Generalized Assignment Problem: Simulated Annealing and Tabu Search Approaches”, OR Spektrum, 17, 211-225.
  • 21. Özbakir, L., Baykasoğlu, A., Tapkan, P. 2009. “Bees Algorithm for Generalized Assignment Problem”, Applied Mathematics and Computation, doi:10.1016/ j.amc.2009.11.018
  • 22. Pham, D.T., Koç, E., Ghanbarzadeh, A., Otri, S., Rahim, S., Zaidi, M. 2006a. “The Bees Algorithm - A Novel Tool for Complex Optimisation Problems”, 2nd International Virtual Conference on Intelligent Production Machines and Systems, 454-461.
  • 23. Pham, D.T., Otri, S., Ghanbarzadeh, A., Koç, E. 2006b. “Application of the Bees Algorithm to the Training of Learning Vector Quantisation Networks for Control Chart Pattern Recognition”, International Conference on Information and Communication Technologies, Damascus, Syria, 1624-1629.
  • 24. Pham, D.T., Koç, E., Ghanbarzadeh, A., Otri, S. 2006c. “Optimisation of the Weights of Multi-Layered Perceptrons Using the Bees Algorithm”, 5th International Symposium on Intelligent Manufacturing Systems, Sakarya, Turkey, 38-46.
  • 25. Pham, D.T., Soroka, A.J., Ghanbarzadeh, A., Koç, E., Otri, S., Packianather, M. 2006d. “Optimising Neural Networks for Identification of Wood Defects Using the Bees Algorithm”, IEEE International Conference on Industrial Informatics, Singapore, 1346-1351.
  • 26. Pham, D.T., Ghanbarzadeh, A., Koç, E., Otri, S. 2006e. “Application of the Bees Algorithm to the Training of Radial Basis Function Networks for Control Chart Pattern Recognition”, 5th CIRP International Seminar on Intelligent Computation in Manufacturing Engineering, Ischia, Italy, 711-716.
  • 27. Pham, D.T., Muhamad, Z., Mahmuddin, M., Ghanbarzadeh, A., Koç, E., Otri, S. 2007a. “Using the Bees Algorithm to Optimise a Support Vector Machine for Wood Defect Classification”, Innovative Production Machines and Systems Virtual Conference, Cardiff, UK.
  • 28. Pham, D.T., Afify, A., Koç, E. 2007b. “Manufacturing Cell Formation Using the Bees Algorithm”, Innovative Production Machines and Systems Virtual Conference, Cardiff, UK.
  • 29. Pham, D.T., Koç, E., Lee, J.Y., Phrueksanant, J. 2007c. “Using the Bees Algorithm to Schedule Jobs for a Machine”, 8th International Conference on Laser Metrology, CMM and Machine Tool Performance, Euspen, UK, 430- 439.
  • 30. Pham, D.T., Castellani, M., Ghanbarzadeh, A. 2007d. “Preliminary Design Using the Bees Algorithm”, 8th International Conference on Laser Metrology, CMM and Machine Tool Performance, Euspen, UK, 420-429.
  • 31. Pham, D.T., Otri, S., Afify, A., Mahmuddin, M., Al-Jabbouli, H. 2007e. “Data Clustering Using the Bees Algorithm”, 40th CIRP International Manufacturing Systems Seminar, Liverpool, UK.
  • 32. Pham, D.T., Soroka, A.J., Koç, E., Ghanbarzadeh, A., Otri, S. 2007f. “Some Applications of the Bees Algorithm in Engineering Design and Manufacture”, International Conference on Manufacturing Automation, Singapore.
  • 33. Pham, D.T., Ghanbarzadeh, A. 2007. “Multi-Objective Optimisation Using the Bees Algorithm”, Innovative Production Machines and Systems Virtual Conference, Cardiff, UK.
  • 34. Quijano, N., Passino, K.M. 2007. “Honey Bee Social Foraging Algorithms for Resource Allocation Theory and Application”, Conference of American Control, New York City, USA.
  • 35. Racer, M., Amini, M.M. 1994. “A Robust Heuristic for the Generalized Assignment Problem”, Annals of Operations Research, 50, 487-503.
  • 36. Randall, M. 2004. “Heuristics for Ant Colony Optimisation Using the Generalised Assignment Problem”, IEEE Congress on Evolutionary Computation, Portland, Oregon, 2, 1916-1923.
  • 37. Teodorovic, D., Dell’Orco, M. 2005. “Bee Colony Optimization - A Cooperative Learning Approach to Complex Transportation Problems”, Advanced OR and AI Methods in Transportation, 51-60.
  • 38. Wedde, H. F., Farooq, M., Zhang, Y. 2004. “BeeHive: An Efficient Fault-Tolerant Routing Algorithm Inspired by Honey Bee Behavior”, Ant Colony, Optimization and Swarm Intelligence, Lecture Notes in Computer Science, Hazırlayan: Dorigo, M., 3172, Springer Berlin, 83-94.
  • 39. Yagiura, M., Yamaguchi, T., Ibaraki, T. 1998. “A Variable- Depth Search Algorithm with Branching Search for the Generalized Assignment Problem”, Optimization Methods and Software, 10, 419-441.
  • 40. Yagiura, M., Yamaguchi, T., Ibaraki, T. 1999. “A Variable- Depth Search Algorithm for the Generalized Assignment Problem”, Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Hazırlayanlar: Vob, S., Martello, S., Osman, I.H., Roucairol, C., Kluwer Academic Publishers, Boston, 459-471.
  • 41. Yagiura, M., Ibaraki, T., Glover, F. 2001. “An Effective Metaheuristic Algorithm for the Generalized Assignment Problem”, IEEE International Conference on Systems, Man, and Cybernetics, Tucson, Arizona, 242.
  • 42. Yagiura, M., Ibaraki, T., Glover, F. 2002. “A Path Relinking Approach for the Generalized Assignment Problem”, International Symposium on Scheduling, 105-108.
  • 43. Yagiura, M., Ibaraki, T., Glover, F. 2004. “An Ejection Chain Approach for the Generalized Assignment Problem”, INFORMS Journal on Computing, 16(2), 131-151.
  • 44. Yagiura, M., Ibaraki, T., Glover, F. 2006. “A Path Relinking Approach with Ejection Chains for the Generalized Assignment Problem”, European Journal of Operational Research, 169, 548-569.
  • 45. Yang, X.S. 2005. “Engineering Optimizations via Nature- Inspired Virtual Bee Algorithms”, IWINAC’2005, LNCS 3562, Hazırlayanlar: Yang, J.M., Alvarez, J.R., Springer- Verlag, Berlin Heidelberg, 317-323.
Endüstri Mühendisliği-Cover
  • ISSN: 1300-3410
  • Yayın Aralığı: Yılda 3 Sayı
  • Başlangıç: 1989
  • Yayıncı: TMMOB MAKİNA MÜHENDİSLERİ ODASI
Arşiv
Sayıdaki Diğer Makaleler

Sipariş üretimde esneklik yöntemi: yakın zamanın getirdikleri

Sinan KAYALIGİL, Bekir İlker SÜER

Arı algoritması ve genelleştirilmiş atama problemi: farklı komşuluk yapılarının karşılaştırılması

Lale ÖZBAKIR, Pınar TAPKAN, Adil BAYKASOĞLU

Migros Türk A.Ş.de birliktelik kurallarının yerleşim düzeni planlamada kullanılması

Derya AY, İbrahim ÇİL