AI Summary & Key Takeaways
AI InsightWhen the results were examined, it was seen that the proposed hybrid Genetic Algorithm achieved higher performance in Multidimensional Knapsack Problem.
📌 3 Key Takeaways
Abstract
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.
Özet
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.