Year 2020, Volume 8 , Issue 2, Pages 355 - 364 2020-05-26

0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü
The Solution of 0-1 Multidimensional Knapsack Problem with Pheromonal Artificial Bee Colony (pABC) Algorithm

Dursun EKMEKCİ [1]


Optimizasyon algoritmaları, geliştirilme tarzları itibariyle bazı problemlere daha çok odaklanarak, daha başarılı çözümler üretebilmektedirler. Örneğin sayısal çözüm yaklaşımıyla üretilen yapay arı koloni (YAK) algoritması, nümerik optimizasyon problemlerinde daha başarılı sonuçlara ulaşabilirken, karınca koloni optimizasyonu (KKO), gezgin satıcı problemi (GSP) benzeri ayrık yapılı optimizasyon problemlerinde daha başarılı çözümler üretebilir. 0-1 optimizasyon problemleri, ayrık yapılı problemlerdir. Ancak çözüm elemanları itibariyle optimizasyon problemlerinin üçüncü grubu olarak değerlendirilebilir. Bu çalışmada 0-1 çok boyutlu sırt çantası problemleri için YAK ve KKO algoritmalarının melez versiyonu olarak geliştirilen fYAK algoritması önerilmiştir. Algoritma performansı, popüler test problemleri üzerinde denenmiş ve elde edilen sonuçlar YAK ve KKO sonuçlarıyla karşılaştırılmıştır.

Optimization algorithms can produce more successful solutions by focusing more on some problems in terms of their development style. For example, the artificial bee colony (ABC) algorithm produced by the numerical solution approach can achieve more successful results in numerical optimization problems, whereas ant colony optimization (ACO) can produce more successful solutions in discrete structure problems such as traveling salesman problem (TSP). 0-1 optimization problems are discrete structured problems. However, it can be considered as the third group of optimization problems in terms of solution items. In this study, the pABC algorithm developed as a hybrid version of ABC and ACO algorithms for 0-1 multidimensional knapsack problems was proposed. The performance of pABC was tested on popular benchmark problems, and the results obtained by the algorithm were compared with the results of ABC and ACO.

  • [1] S. I. Gass and A. A. Assad, An Annotated Timeline of Operations Research. Boston: Kluwer Academic Publishers, 2004.
  • [2] M. Ehrgott and X. Gandibleux, “A survey and annotated bibliography of multiobjective combinatorial optimization,” OR-Spektrum, vol. 22, no. 4, pp. 425–460, 2000.
  • [3] P. C. Chu and J. E. Beasley, “A Genetic Algorithm for the Multidimensional Knapsack Problem,” vol. 86, pp. 63–86, 1998.
  • [4] S. Member and S. Member, “A New Heuristic for Solving the Multichoice Multidimensional Knapsack Problem,” vol. 35, no. 5, pp. 708–717, 2005.
  • [5] A. Sbihi, “A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem,” pp. 337–351, 2007.
  • [6] M. E. Captivo, J. Climaco, J. Figueira, E. Martins, and J. L. Santos, “Solving bicriteria 0 – 1 knapsack problems using a labeling algorithm,” Comput. Oper. Res., vol. 30, pp. 1865–1886, 2003.
  • [7] M. Laumanns, L. Thiele, and E. Zitzler, “An efficient , adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method,” Eur. J. Oper. Res., vol. 169, pp. 932–942, 2006.
  • [8] L. Ke, Z. Feng, and Z. Ren, “An ant colony optimization approach for the multidimensional knapsack problem,” pp. 65–83, 2010.
  • [9] M. Kong, P. Tian, and Y. Kao, “A new ant colony optimization algorithm for the multidimensional Knapsack problem,” vol. 35, pp. 2672–2683, 2008.
  • [10] S. Hanafi and C. Wilbaut, “Scatter Search for the 0 – 1 Multidimensional Knapsack Problem,” pp. 143–159, 2008.
  • [11] L. Wang, X. Zheng, and S. Wang, “Knowledge-Based Systems A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem,” Knowledge-Based Syst., vol. 48, pp. 17–23, 2013.
  • [12] V. Tongur and E. Ülker, “Migrating Birds Optimization (MBO) algorithm to solve 0-1 multidimensional knapsack problem,” in 2017 International Conference on Computer Science and Engineering (UBMK), 2017, pp. 786–789.
  • [13] K. Klamroth and M. M. Wiecek, “Dynamic Programming Approaches to the Multiple Criteria Knapsack Problem,” Nav. Res. Logist., vol. 47, pp. 57–76, 2000.
  • [14] Ö. Karsu, “Eşitlikçi Çok Amaçlı Sırt Çantası Problemi,” Gazi ÜniversitesiFen Bilim. Derg., vol. 6, no. 2, pp. 358–373, 2018.
  • [15] D. Ekmekci, “A Pheromonal Artificial Bee Colony (pABC) Algorithm for Discrete Optimization Problems,” Appl. Artif. Intell., vol. 33, no. 11, pp. 1–16, Sep. 2019.
  • [16] D. Karaboga, “An Idea Based on Honey Bee Swarm for Numerical Optimization,” Kayseri, Turkey, 2005.
  • [17] M. Dorigo, V. Maniezzo, and A. Colorni, “Positive feedback as a search strategy,” Milano, Italy, 1991.
  • [18] M. Dorigo and C. Blum, “Ant colony optimization theory: A survey,” Theor. Comput. Sci., vol. 344, no. 2–3, pp. 243–278, Nov. 2005.
Primary Language tr
Subjects Engineering
Published Date Mayıs 2020
Journal Section Articles
Authors

Orcid: 0000-0002-9830-7793
Author: Dursun EKMEKCİ (Primary Author)
Institution: KARABÜK ÜNİVERSİTESİ
Country: Turkey


Dates

Publication Date : May 26, 2020

Bibtex @research article { apjes640252, journal = {Akademik Platform Mühendislik ve Fen Bilimleri Dergisi}, issn = {}, eissn = {2147-4575}, address = {}, publisher = {Academic Platform}, year = {2020}, volume = {8}, pages = {355 - 364}, doi = {10.21541/apjes.640252}, title = {0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü}, key = {cite}, author = {Ekmekci̇, Dursun} }
APA Ekmekci̇, D . (2020). 0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü . Akademik Platform Mühendislik ve Fen Bilimleri Dergisi , 8 (2) , 355-364 . DOI: 10.21541/apjes.640252
MLA Ekmekci̇, D . "0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü" . Akademik Platform Mühendislik ve Fen Bilimleri Dergisi 8 (2020 ): 355-364 <https://dergipark.org.tr/en/pub/apjes/issue/52467/640252>
Chicago Ekmekci̇, D . "0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü". Akademik Platform Mühendislik ve Fen Bilimleri Dergisi 8 (2020 ): 355-364
RIS TY - JOUR T1 - 0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü AU - Dursun Ekmekci̇ Y1 - 2020 PY - 2020 N1 - doi: 10.21541/apjes.640252 DO - 10.21541/apjes.640252 T2 - Akademik Platform Mühendislik ve Fen Bilimleri Dergisi JF - Journal JO - JOR SP - 355 EP - 364 VL - 8 IS - 2 SN - -2147-4575 M3 - doi: 10.21541/apjes.640252 UR - https://doi.org/10.21541/apjes.640252 Y2 - 2020 ER -
EndNote %0 Akademik Platform Mühendislik ve Fen Bilimleri Dergisi 0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü %A Dursun Ekmekci̇ %T 0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü %D 2020 %J Akademik Platform Mühendislik ve Fen Bilimleri Dergisi %P -2147-4575 %V 8 %N 2 %R doi: 10.21541/apjes.640252 %U 10.21541/apjes.640252
ISNAD Ekmekci̇, Dursun . "0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü". Akademik Platform Mühendislik ve Fen Bilimleri Dergisi 8 / 2 (May 2020): 355-364 . https://doi.org/10.21541/apjes.640252
AMA Ekmekci̇ D . 0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü. APJES. 2020; 8(2): 355-364.
Vancouver Ekmekci̇ D . 0-1 Çok Boyutlu Sırt Çantası Probleminin Feromonal Yapay Arı Koloni (fYAK) Algoritması ile Çözümü. Akademik Platform Mühendislik ve Fen Bilimleri Dergisi. 2020; 8(2): 355-364.