KÜME BİRLEŞİMLİ SIRT ÇANTASI PROBLEMİNİN ADAPTİF YAPAY ARI KOLONİSİ ALGORİTMASI İLE ÇÖZÜMÜ

Abstract

ÖZET Bu çalışmada, 0-1 yapılı sırt çantası probleminin özel bir hali olan Küme Birleşimli Sırt Çantası problemine, doğadan esinlenilmiş metasezgisel bir algoritma olan Yapay Arı Kolonisi algoritmasına adaptif bir yapı eklenmesi vasıtasıyla optimum çözüm sağlanmıştır. Yapay Arı Kolonisi algoritması sürekli optimizasyon problemlerinin çözümü için önerilmiştir ve ikili yapıda olan bu probleme adapte olabilmesi için algoritmanın da ikili yapıdaki forma dönüştürülmesi gerekmektedir. Bu dönüştürme iki şekilde gerçekleştirilmektedir. Birincisi, eğer sürekli karar değişkeni kullanılırsa bu değişkenler haritalama fonksiyonu vasıtasıyla ikili karar değişkenine dönüştürülebilir. Diğer bir çözüm ise komşu çözümlerin ikili operatörler sayesinde üretilmesidir. İkinci yaklaşımda yöntemin başarısı operatörlerin başarısı ile belirlenmektedir. Çalışmada arama uzayının genişletilmesi maksadıyla birden fazla operatörün kullanımı hedeflendiği için operatörlerin adaptif bir mekanizma içerisinde çalışması sağlanmıştır. Adaptif operatör seçimini benimseyen bu yöntem Adaptif Yapay Arı Kolonisi (AYAK) olarak isimlendirilmiş olup, tüm arama sürecinde tek bir operatör kullanılmasının yerine operatör havuzundan uygun operatörün seçilerek komşu çözüm üretilmesini önermektedir. Oluşturulan bu 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 önerilmiştir. Elde edilen sonuçlar güncel literatürdeki yöntemler ile karşılaştırılmış ve oldukça rekabetçi sonuçlar elde edilmiştir. Çalışma, başarılı bir seçim şemasına sahip adaptif ve ikili yapıda bir yapay arı kolonisi algoritması sunmaktadır.

ABSTRACT

In this study, the optimum solution was provided to the Set Union Knapsack Problem which is a special form of the 0-1 backpack problem, by adding an adaptive structure to the Artificial Bee Colony algorithm which is a metaheuristic algorithm inspired by nature. The Artificial Bee Colony algorithm has been proposed for the solution of continuous optimization problems, and in order to adapt to this binary problem, the algorithm must be transformed into a binary form. This conversion is carried out in two ways. First, if a continuous decision variable is used, these variables can be converted into a binary decision variable through the mapping function. Another solution is to produce neighboring solutions through binary operators. In the second approach, the success of the method is determined by the success of the operators. Since it is aimed to use more than one operator in order to expand the search space in the study, it is ensured that the operators work in an adaptive mechanism. This method which adopts the selection of adaptive operators, is named Adaptive Artificial Bee Colony and instead of using a single operator during the entire search, it suggests selecting the appropriate operator from the operator pool and producing a neighboring solution. The features of these selection schemes have been extensively examined 30 comparison problems. The best performing algorithm has been proposed for these problem clusters. The results obtained were compared with the methods in the current literature and extremely competitive results were obtained. The study presents an adaptive binary artificial bee colony algorithm with a successful selection scheme