Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi

Yıl 2020, Cilt: 11 Sayı: 2, 278 - 288, 26.06.2020

Osman Pala

Öz

Bir tam sayılı programlama problemi olan Çok Boyutlu Sırt Çantası Problemi, işletmelerin yüz yüze olduğu çeşitli tipte problemlerin analizi ve çözümü için bir matematiksel zemin görevi görmektedir. Problemin matematiksel modelini oluşturan değişkenler ve kısıtların adetleri çoğaldığında ise problem sıklıkla optimuma yakınsayan değerleri bulabilen sezgisel yaklaşımlar ile çözülmektedir. Popülasyon temelli bir sezgisel algoritma olan Genetik Algoritma problemin çözümünde önde gelen yaklaşımlardan bir tanesidir. Çalışma kapsamında problemin çözümünde yeni bir melez Genetik Algoritma önerilmiştir. Başlangıç popülasyonunda yerel arama ile iyileştirmeye ve probleme özgü önerilen yeni bir tamir operatörü ile uygun olmayan çözümleri tamir etmeye dayanan melez yaklaşım standart Genetik Algoritma ile örnek problemlerin çözümü üzerinden karşılaştırılmıştır. Sonuçlar incelendiğinde önerilen melez Genetik Algoritma’nın Çok Boyutlu Sırt Çantası Problemi’nde daha yüksek başarım elde ettiği görülmüştür.

Anahtar Kelimeler

Çok Boyutlu Sırt Çantası Problemi, Genetik Algoritma, Melez Algoritmalar, Başlangıç Popülasyonu, Tamir Operatörü.

A New Hybrid Genetic Algorithm Proposal for Multidimensional Knapsack Problem

Öz

The Multidimensional Knapsack Problem which is an integer programming problem serves as a mathematical basis for the analysis and solution of various types of problems facing businesses. When the number of variables and constraints that compose the mathematical model of the problem increases, the problem is often solved with heuristic approaches that can find values that converge to the optimum. Genetic Algorithm, which is a population-based heuristic algorithm, is one of the leading approaches in solving the problem. Within the scope of the study, a new hybrid Genetic Algorithm was proposed to solve the problem. The hybrid approach based on local search improvement in the initial population and on repairing unsuitable solutions with a new problem-specific repair operator was compared with the standard Genetic Algorithm through the solution of sample problems. When the results were examined, it was seen that the proposed hybrid Genetic Algorithm achieved higher performance in Multidimensional Knapsack Problem.

Anahtar Kelimeler

Multidimensional Knapsack Problem, Genetic Algorithm, Hybrid Algorithms, Initial Population, Repair Operator

Kaynakça

• Abdel-Basset, M., El-Shahat, D., El-Henawy, I., & Sangaiah, A. K. (2018). A modified flower pollination algorithm for the multidimensional knapsack problem: human-centric decision making. Soft Computing, 22(13), 4221-4239.
• Akçay, Y., Li, H., & Xu, S. H. (2007). Greedy algorithm for the general multidimensional knapsack problem. Annals of Operations Research, 150(1), 17-29.
• Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of the operational research society, 41(11), 1069-1072.
• Berberler, M., Guler, A., & Nurıyev, U. (2013). A genetic algorithm to solve the multidimensional knapsack problem. Mathematical and Computational Applications, 18(3), 486-494.
• Chih, M. (2015). Self-adaptive check and repair operator-based particle swarm optimization for the multidimensional knapsack problem. Applied Soft Computing, 26, 378-389.
• Chih, M. (2018). Three pseudo-utility ratio-inspired particle swarm optimization with local search for multidimensional knapsack problem. Swarm and evolutionary computation, 39, 279-296.
• Chih, M., Lin, C. J., Chern, M. S., & Ou, T. Y. (2014). Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem. Applied Mathematical Modelling, 38(4), 1338-1350.
• Chu, P. C., & Beasley, J. E. (1998). A genetic algorithm for the multidimensional knapsack problem. Journal of heuristics, 4(1), 63-86.
• Djannaty, F., & Doostdar, S. (2008). A hybrid genetic algorithm for the multidimensional knapsack problem. International Journal of Contemporary Mathematical Sciences, 3(9), 443-456.
• Fréville, A. (2004). The multidimensional 0–1 knapsack problem: An overview. European Journal of Operational Research, 155(1), 1-21.
• Haddar, B., Khemakhem, M., Hanafi, S., & Wilbaut, C. (2016). A hybrid quantum particle swarm optimization for the multidimensional knapsack problem. Engineering Applications of Artificial Intelligence, 55, 1-13.
• Hanafi, S., & Freville, A. (1998). An efficient tabu search approach for the 0–1 multidimensional knapsack problem. European Journal of Operational Research, 106(2-3), 659-675.
• Hoff, A., Løkketangen, A., & Mittet, I. (1996, November). Genetic algorithms for 0/1 multidimensional knapsack problems. In Proceedings Norsk Informatikk Konferanse (pp. 291-301). Citeseer.
• Holland J, H. (1975). Adaptation in natural and artificial systems. Ann Arbor: University of Michigan Press.
• Ke, L., Feng, Z., Ren, Z., & Wei, X. (2010). An ant colony optimization approach for the multidimensional knapsack problem. Journal of Heuristics, 16(1), 65-83.
• Kong, M., Tian, P., & Kao, Y. (2008). A new ant colony optimization algorithm for the multidimensional knapsack problem. Computers & Operations Research, 35(8), 2672-2683.
• Lai, G., Yuan, D., & Yang, S. (2014). A new hybrid combinatorial genetic algorithm for multidimensional knapsack problems. The Journal of Supercomputing, 70(2), 930-945.
• Lienland, B.,& Zeng, L. (2015). A review and comparison of genetic algorithms for the 0-1 multidimensional knapsack problem. International Journal of Operations Research and Information Systems (IJORIS), 6(2), 21-31.
• López, L. F. M., Blas, N. G., & Albert, A. A. (2018). Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations. Soft Computing, 22(8), 2567-2582.
• Luo, K., & Zhao, Q. (2019). A binary grey wolf optimizer for the multidimensional knapsack problem. Applied Soft Computing, 83, 105645.
• Meng, T., & Pan, Q. K. (2017). An improved fruit fly optimization algorithm for solving the multidimensional knapsack problem. Applied Soft Computing, 50, 79-93.
• OR-Library http://people.brunel.ac.uk/~mastjjb/jeb/info.html Erişim tarihi: 24.08.2019.
• Ozsoydan, F. B., & Baykasoglu, A. (2019). A swarm intelligence-based algorithm for the set-union knapsack problem. Future Generation Computer Systems, 93, 560-569.
• Raidl, G. R. (1999, July). Weight-codings in a genetic algorithm for the multi-constraint knapsack problem. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406) (Vol. 1, pp. 596-603). IEEE.
• Uslu, F. S. (2015). Solving Knapsack Problem with Genetic Algorithm. In 2015 23nd Signal Processing and Communications Applications Conference (SIU) (pp. 1062-1065). IEEE.
• Wang, L., Zheng, X. L., & Wang, S. Y. (2013). A novel binary fruit fly optimization algorithm for solving the multidimensional knapsack problem. Knowledge-Based Systems, 48, 17-23.
• Zhang, X., Wu, C., Li, J., Wang, X., Yang, Z., Lee, J. M., & Jung, K. H. (2016). Binary artificial algae algorithm for multidimensional knapsack problems. Applied Soft Computing, 43, 583-595.