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

pala, osman

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

Osman PALA (Karamanoğlu Mehmetbey Üniversitesi, İktisadi ve İdari Bilimler Fakültesi, Ekonometri Bölümü, Karaman, Türkiye)

Gümüşhane Üniversitesi Sosyal Bilimler Dergisi

22 5

Yıl: 2020 Cilt: 11 Sayı: 2 Sayfa Aralığı: 278 - 288 Metin Dili: Türkçe İndeks Tarihi: 02-03-2021

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

Öz:

Bir tam sayılı programlama problemi olan Çok Boyutlu Sırt Çantası Problemi, işletmelerin karşılaştığı çeşitli tipte problemlerin analizive çö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 temellibir sezgisel algoritma olan Genetik Algoritma problemin çözümünde önde gelen yaklaşımlardan bir tanesidir. Bu çalışma kapsamındaproblemin çözümü için, başlangıç popülasyonunu iyileştiren bir yerel arama ile güçlendirilmiş yeni bir melez Genetik Algoritmaönerilmiştir. Önerilen algoritma standart Genetik Algoritma ile örnek problemlerin çözümü üzerinden karşılaştırılmıştır. Sonuçlarincelendiğinde önerilen melez Genetik Algoritma’nın Çok Boyutlu Sırt Çantası Problemi’nde daha yüksek başarım elde ettiğigörülmüştür.

Anahtar Kelime:

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 this study, a new hybrid Genetic Algorithm, which is powered by a local search that improves the initial population, is proposed for the solution of the problem.The proposed algorithm 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 Kelime:

Belge Türü: Makale Makale Türü: Araştırma Makalesi Erişim Türü: Erişime Açık

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.
Cotta, C., & Troya, J. M. (1998). A hybrid genetic algorithm for the 0–1 multiple knapsack problem. In Artificial neural nets and genetic algorithms (pp. 250-254). Springer, Vienna.
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.
Khuri, S., Bäck, T., & Heitkötter, J. (1994). The zero/one multiple knapsack problem and genetic algorithms. In Proceedings of the 1994 ACM symposium on Applied computing (pp. 188-193).
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.
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.
Thiel, J., & Voss, S. (1994). Some experiences on solving multiconstraint zero-one knapsack problems with genetic algorithms. INFOR: Information Systems and Operational Research, 32(4), 226-242.
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.

APA	pala o (2020). Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. , 278 - 288.
Chicago	pala osman Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. (2020): 278 - 288.
MLA	pala osman Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. , 2020, ss.278 - 288.
AMA	pala o Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. . 2020; 278 - 288.
Vancouver	pala o Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. . 2020; 278 - 288.
IEEE	pala o "Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi." , ss.278 - 288, 2020.
ISNAD	pala, osman. "Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi". (2020), 278-288.

APA	pala o (2020). Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. Gümüşhane Üniversitesi Sosyal Bilimler Dergisi, 11(2), 278 - 288.
Chicago	pala osman Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. Gümüşhane Üniversitesi Sosyal Bilimler Dergisi 11, no.2 (2020): 278 - 288.
MLA	pala osman Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. Gümüşhane Üniversitesi Sosyal Bilimler Dergisi, vol.11, no.2, 2020, ss.278 - 288.
AMA	pala o Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. Gümüşhane Üniversitesi Sosyal Bilimler Dergisi. 2020; 11(2): 278 - 288.
Vancouver	pala o Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi. Gümüşhane Üniversitesi Sosyal Bilimler Dergisi. 2020; 11(2): 278 - 288.
IEEE	pala o "Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi." Gümüşhane Üniversitesi Sosyal Bilimler Dergisi, 11, ss.278 - 288, 2020.
ISNAD	pala, osman. "Çok Boyutlu Sırt Çantası Problemi İçin Yeni Bir Melez Genetik Algoritma Önerisi". Gümüşhane Üniversitesi Sosyal Bilimler Dergisi 11/2 (2020), 278-288.