An Improved Pheromoal Artificial Bee Colony (ipABC) Algorithm for Optimization Problems

Abstract

Honey bee colony, which collects information from the environment and determines its behavior accordingly, is one of the most popular examples of colonial life. This dynamic structure has been evaluated with different approaches and solutions have been proposed for many engineering problems. In the field of computer systems, many solutions proposed for computer networks, mobile network optimization, numerical and combinatorial optimization model the behavior of the honey bee colony. Operations researchers are mostly concentrated on the communication, interaction, marriage, and foraging behaviors of colony members. In this context, the Artificial Bee Colony (ABC) Algorithm, which imitates honey bees, which take on the task of searching and collecting food, has significant success in the optimization literature. In the classical ABC structure to derive more successful solutions the roulette wheel is used, and to escape the algorithm from the trap of local optima, random solutions are evaluated during the "limit" period. However, algorithm derivatives have been developed that make the interaction between bees more efficient. In this study, the pheromonal ABC (pABC) algorithm developed for honey bees to search more efficiently is discussed. In pABC, the pheromone trail is used for the onlooker bees to benefit more from the experience of employed bees. Thus, onlookers use procedures that construct new solutions, not derive. In the improved pABC (ipABC) model, which is presented as a solution proposal, memory is used, which relations the correlation between the solution components with the success of the solution, and transfer functions are used to enable the algorithm to move to more effective solution regions. Memory and pheromone matrix are updated in each cycle. In the current cycle, if the best solution ever found, a general update is made for the pheromone matrix. Three different transfer functions were used in the study to investigate the convergence performance of the algorithm and analyze the effect of transfer functions. Experiments on different sizes of Traveling Salesman Problem (TSP) have shown that the algorithm can produce better solutions compared to classical ABC and pABC.

Keywords

• ABC
• pABC
• ipABC

Optimizasyon Problemleri İçin Geliştirilmiş Feromonal Yapay Arı Koloni (gfYAK) Algoritması

Öz

Çevreden bilgi toplayan ve davranışını buna göre belirleyen bal arısı kolonisi, sürü yaşamının en popüler örneklerinden biridir. Bu dinamik yapı, farklı yaklaşımlarla değerlendirilerek, birçok mühendislik problemine çözüm önerisi getirilmiştir. Bilgisayar sistemleri alanında, bilgisayar ağları, mobil ağ optimizasyonu, sayısal ve kombinasyonel optimizasyon için geliştirilen birçok çözüm önerisi, bal arısı kolonisinin davranışlarını model almaktadır. Yöneylem araştırmacıları ise daha çok, koloni üyelerinin, haberleşme, etkileşim, evlilik ve yem arama davranışlarına yoğunlaşmışlardır. Bu bağlamda, yiyecek arama ve toplama görevini üstlenen bal arılarını taklit eden Yapay Arı Koloni (YAK) Algoritması, optimizasyon literatüründe önemli bir başarıya sahiptir. Klasik algoritma yapısında, limit periyodunda oluşturulan rastgele çözümler, algoritmayı yerel optimumdan kurtarırken, daha başarılı çözümler üretebilmek için rulet tekerleği kullanılır. Ancak arılar arasındaki etkileşimi daha verimli kılan algoritma türevleri de geliştirilmiştir. Bu çalışmada bal arılarının daha verimli yerel arama yapabilmesi için geliştirilen feromonal YAK (fYAK) algoritması ele alınmıştır. fYAK’ta gözcü arıların, işçi arıların tecrübesinden daha fazla yararlanabilmesi için feromon salgısı kullanılır. Böylece gözcü arılar, yeni çözümler üreten değil, yeni çözümler oluşturan prosedürler kullanır. Çözüm önerisi olarak sunulan Geliştirilmiş fYAK (gfYAK) modelinde, çözüm bileşenleri arasındaki korelasyonu, çözüm başarısıyla daha çok ilişkilendiren hafıza ve algoritmanın daha etkili çözüm bölgelerine yönelmesini sağlayan transfer fonksiyonları kullanılmaktadır. Herbir çevrimde hafıza ve buna bağlı olarak feromon matrisi güncellenmektedir. İlgili çevrimde, o ana kadarki en iyi çözüm bulunmuşsa feromon matrisi için genel güncelleme yapılır. Algoritma yakınsama performansını araştırabilmek ve transfer fonksiyonlarının etkisini analiz edebilmek için, çalışma kapsamında üç farklı transfer fonksiyonu kullanılmıştır. Farklı boyutlardaki Gezgin Satıcı Problemi (GSP) üzerinde yapılan denemeler, algoritmanın klasik YAK ve fYAK’a oranla daha iyi çözümler üretebildiğini göstermiştir.

Anahtar Kelimeler

• YAK
• fYAK
• gfYAK

Kaynakça

1. Akay, B., & Karaboga, D. (2009). Parameter Tuning for the Artificial Bee Colony Algorithm (Vol. 5796, pp. 608–619). https://doi.org/10.1007/978-3-642-04441-0_53
2. Akay, B., & Karaboga, D. (2015). A survey on the applications of artificial bee colony in signal, image, and video processing. Signal, Image and Video Processing, 9(4), 967–990. https://doi.org/10.1007/s11760-015-0758-4
3. Bansal, J. C., Sharma, H., & Jadon, S. S. (2013). Artificial bee colony algorithm: A survey. International Journal of Advanced Intelligence Paradigms, 5(1–2), 123–159. https://doi.org/10.1504/IJAIP.2013.054681
4. Barnebau, E., Dorigo, M., & Theraulaz, G. (1999). Swarm Intelligence From Natural to Artificial Systems. New York: Oxford University Press.
5. Beni, G., & Wang, J. (1993). Swarm Intelligence in Cellular Robotic Systems. In P. Dario, G. Sandini, & Aebischer Patrick (Eds.), Robots and Biological Systems: Towards a New Bionics? (pp. 703–712). Springer Berlin Heidelberg. https://doi.org/https://doi.org/10.1007/978-3-642-58069-7_38
6. Dorigo, M, & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66. https://doi.org/10.1109/4235.585892
7. Dorigo, Marco, Maniezzo, V., & Colorni, A. (1991). Positive feedback as a search strategy. Milano, Italy.
8. Ekmekci, D. (2019a). A Pheromonal Artificial Bee Colony (pABC) Algorithm for Discrete Optimization Problems. Applied Artificial Intelligence, 33(11), 935–950. https://doi.org/10.1080/08839514.2019.1661120

9. Ekmekci, D. (2019b). An Ant Colony Optimization Memorizing Better Solutions (ACO-MBS) for Traveling Salesman Problem. In 2019 3rd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT) (pp. 1–5). IEEE. https://doi.org/10.1109/ISMSIT.2019.8932768
10. Karaboga, D. (2005). An Idea Based on Honey Bee Swarm for Numerical Optimization. Kayseri, Turkey. Retrieved from https://www.researchgate.net/publication/255638348_An_Idea_Based_on_Honey_Bee_Swarm_for_Numerical_Optimization_Technical_Report_-_TR06
11. Kwang Mong Sim, & Weng Hong Sun. (2003). Ant colony optimization for routing and load-balancing: survey and new directions. IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, 33(5), 560–572. https://doi.org/10.1109/TSMCA.2003.817391
12. Monteiro, M. S. R., Fontes, D. B. M. M., & Fontes, F. A. C. C. (2012). Ant Colony Optimization: a literature survey. FEP Working Papers. Retrieved from http://ideas.repec.org/p/por/fepwps/474.html