Küme Birleşimli Sırt Çantası Probleminin Adaptif Yapay Arı Kolonisi Algoritması ile Çözümü

Abstract

Meta-sezgisel ve sürü zekâsı algoritmaları, NP-Zor optimizasyon problemlerine yaklaşık çözümler sunmak için uzun süredir kullanılmaktadır. Özellikle kombinatoryal ve ikili problemler söz konusu olduğunda, algoritmalar içerisine gömülü komşu çözüm üretmek için kullanılan operatör fonksiyonları, aramanın çeşitliliğine sınırlamalar getirirken algoritmaların başarısında önemli bir rol oynar. Bu tür sınırlamalardan kaçmak ve çeşitliliği iyileştirmek için, birden fazla operatörün tek bir operatör yerine bir seçim şeması yoluyla kullanılması tercih edilir. Daha önce farklı sürü zekâsı ve meta-sezgisel algoritmalarla çeşitli kombinatoryal problemleri çözmek için bir dizi operatör seçim şeması kullanılması daha yüksek etkinlik elde etmek için kullanılmıştır. Bu makalede, küme birleşimli sırt çantası problemleri, ilk kez, alternatif operatör seçim şemaları aracılığıyla seçilen birden fazla operatör içeren ikili bir yapay arı kolonisi algoritması ile çözülmüştür. Önerilen yöntem için farklı kredi atama yaklaşımları, farklı kayan pencere boyutları ve parametre konfigürasyonları test edilmiştir. Seçim şemalarının özellikleri kapsamlı olarak 30 kıyaslama problemi üzerinde incelenmiştir. Bu problem kümeleri için en iyi performans gösteren algoritma konfigürasyonu önerilmiştir. Çalışma, başarılı bir seçim şemasına sahip adaptif ikili yapay arı kolonisi algoritmasını sunmaktadır

Keywords

• Yapay arı kolonisi
• adaptif operatör seçimi
• küme birleşimli sırt çantası problemi

Solving Set Union Knapsack Problems with Adaptive Binary Artificial Bee Colony

Abstract

Metaheuristic and swarm intelligence algorithms have been utilised to solve optimization problems with NP-Hard nature providing approximate solutions for a long time. Especially in the case of combinatorial and binary problems, operator functions embedded in the algorithms to generate neighboring solutions play a crucial role in the success of the algorithms while each operator imposes limitations upon the diversity of the search. In order to escape of such limitations and improve the diversity, multiple operators are preferred to use through a selection scheme instead of a single operator. However, the nature of selection scheme whereby operators are opted out also matters for higher efficiency, where a number of operator selection schemes have been used to solve various combinatorial problems with different swarm intelligence and metaheuristic algorithms before. In this paper, set union knapsack problems are, first time, solved with a binary artificial bee colony algorithm embedded with multiple operators selected through alternative operator selection schemes. Different credit assignment approaches, different sliding window lengths and parameter configurations are tested for the proposed method. The characteristics of the selection schemes are studied and the best performing one is suggested using a comprehensive experimentation over 30 benchmark problems. The study concludes a particular variant of binary artificial bee colony algorithm with a successful selection scheme.

Keywords

• Artificial Bee Colony
• Adaptive Operator Selection
• Set Union Knapsack Problem

References

1. [1]. Bitran, Gabriel R., and Arnoldo C. Hax. "Disaggregation and resource allocation using convex knapsack problems with bounded variables." Management Science 27.4 (1981): 431-441.
2. [2]. Odlyzko, Andrew M. "The rise and fall of knapsack cryptosystems." Cryptology and computational number theory 42 (1990): 75-88.
3. [3]. Klamroth, Kathrin, and Margaret M. Wiecek. "Dynamic programming approaches to the multiple criteria knapsack problem." Naval Research Logistics (NRL) 47.1 (2000): 57-76.
4. [4]. Bretthauer, Kurt M., and Bala Shetty. "The nonlinear knapsack problem–algorithms and applications." European Journal of Operational Research 138.3 (2002): 459-472.
5. [5]. Goldschmidt, Olivier, David Nehme, and Gang Yu. "Note: On the set‐union knapsack problem." Naval Research Logistics (NRL) 41.6 (1994): 833-842.
6. [6]. Arulselvan, Ashwin. "A note on the set union knapsack problem." Discrete Applied Mathematics 169 (2014): 214-218.
7. [7]. Holland, John. "Adaptation in natural and artificial systems: an introductory analysis with application to biology." Control and artificial intelligence (1975).
8. [8]. Eberhart, Russell, and James Kennedy. "A new optimizer using particle swarm theory." MHS'95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Ieee, 1995.

9. [9]. Karaboga, Dervis, and Bahriye Basturk. "On the performance of artificial bee colony (ABC) algorithm." Applied soft computing 8.1 (2008): 687-697.
10. [10]. Karaboga, Dervis, and Bahriye Akay. "A comparative study of artificial bee colony algorithm." Applied mathematics and computation 214.1 (2009): 108-132.
11. [11]. Kiran, Mustafa Servet, and M. E. S. U. T. Gündüz. "XOR-based artificial bee colony algorithm for binary optimization." Turkish Journal of Electrical Engineering & Computer Sciences 21.Sup. 2 (2013): 2307-2328.
12. [12]. Kashan, Mina Husseinzadeh, Nasim Nahavandi, and Ali Husseinzadeh Kashan. "DisABC: A new artificial bee colony algorithm for binary optimization." Applied Soft Computing 12.1 (2012): 342-352.
13. [13]. Durgut, Rafet. "Improved binary artificial bee colony algorithm." arXiv preprint arXiv:2003.11641 (2020).
14. [14]. Arani, Behrooz Ostadmohammadi, Pooya Mirzabeygi, and Masoud Shariat Panahi. "An improved PSO algorithm with a territorial diversity-preserving scheme and enhanced exploration–exploitation balance." Swarm and Evolutionary Computation 11 (2013): 1-15.
15. [15]. Fialho, Álvaro, et al. "Analyzing bandit-based adaptive operator selection mechanisms." Annals of Mathematics and Artificial Intelligence 60.1-2 (2010): 25-64.
16. [16]. Kiran, Mustafa Servet. "The continuous artificial bee colony algorithm for binary optimization." Applied Soft Computing 33 (2015): 15-23.
17. [17]. Durgut, Rafet, and Mehmet Emin Aydin. "Adaptive binary artificial bee colony algorithm." Applied Soft Computing (2020): 107054.
18. [18]. He, Yichao, et al. "A novel binary artificial bee colony algorithm for the set-union knapsack problem." Future Generation Computer Systems 78 (2018): 77-86.
19. [19]. Ozsoydan, Fehmi Burcin, and Adil Baykasoglu. "A swarm intelligence-based algorithm for the set-union knapsack problem." Future Generation Computer Systems 93 (2019): 560-569.
20. [20]. Ozsoydan, Fehmi Burcin. "Artificial search agents with cognitive intelligence for binary optimization problems." Computers & Industrial Engineering 136 (2019): 18-30.