ETKİLİ BİR YAPAY ARI KOLONİSİ ALGORİTMASININ ÜÇ BOYUTLU KUTU DOLDURMA PROBLEMİ ÜZERİNDE UYGULANMASI

Abstract

ÖZET

Yapay Arı Kolonisi (YAK) algoritması sayısal temelli optimizasyon problemleri yanı sıra tamsayılı optimizasyon problemlerinin çözümünde de yaygın bir şekilde kullanılmaktadır. Bununla birlikte Sırt Çantası Problemi (SÇP) gibi yüksek kompleksliğe sahip tamsayılı problemlerin kabul edilir ölçülerdeki çözümlerini mümkün olduğunca kısa sürede elde edebilmek için güçlü algoritmaların geliştirilmesine ihtiyaç duyulmaktadır. Literatürde SÇP’lerin çözümünde, keşif ve derinlemesine arama yapabilme kabiliyetine sahip YAK algoritması birçok çalışmada kullanılsa da YAK algoritmasının hammadde ve malzeme taşıma sistemlerinin en temel problemlerinden birisi olan üç boyutlu kutu doldurma problemlerinin çözümünde kullanıldığına az rastlanmaktadır. Bu çalışmada, YAK algoritmasının derinlemesine araştırma yönü Tabu Araştırması (TA) tabanlı bir hafıza mekanizması ile, keşif yönü ise Genetik Algoritmada (GA) kullanılan genetik operatörler ile ayrı

ayrı geliştirilerek farklı iki algoritma elde edilmiştir. Ayrıca her iki takviye yaklaşımın YAK algoritmasına bir arada entegre edildiği bir üçüncü algoritma da geliştirilmiştir. Geliştirilen üç algoritma kendi aralarında literatürdeki kurallara göre türetilen ve hali hazırda literatürde yaygın olarak kullanılan tekli ve çoklu konteyner yükleme problemi veri setleri üzerinde uygulanarak karşılaştırılmış, ayrıca algoritma üçlüsü arasında her iki takviye yaklaşımı da kullanan ve en iyi performansa sahip Bütünleşik Hibrit YAK (BHYAK) algoritması literatürdeki diğer yaklaşımlar ile karşılaştırılmıştır. Elde edilen sonuçlara göre hafıza mekanizması hibrit YAK algoritması geliştirmek için takviye yaklaşım olarak kullanıldığında, faydası uygulandığı problemin kompleksliğine ve çözüm süresi kısıtına göre değişiklik gösterdiği gözlemlenmiştir. Genetik operatörlerin ise hibrit YAK algoritması oluşturmada hafıza mekanizmasına göre daha tercih edilir olduğu tespit edilmiştir. Ayrıca, literatürdeki diğer yaklaşımlar ile karşılaştırıldığında tamamen rassal arama temelli bir yaklaşım olan BHYAK algoritmasının, nesneleri bir ön sınıflandırma işlemine tâbi tutan diğer yaklaşımlarınkine yakın bir performans gösterdiği tespit edilmiştir.

ABSTRACT

The Artificial Bee Colony (ABC) algorithm is widely used to achieve optimum solution in a short time in integer-based optimization problems. However, the complexity of integer-based problems such as Knapsack Problems (KP) requires robust algorithms to avoid excessive solution search time. ABC algorithm that provides both the exploitation and the exploration approach is used as an alternative approach for various KP problems in the literature. However, it is rarely used for the Three-Dimensional Bin Packing Problem (3DBPP) which is an important part of the transportation systems. In this study, the exploitation and exploration aspects of the ABC algorithm are improved by using memory mechanisms and genetic operators to develop two different hybrid ABC algorithms. The developed algorithms and the basic ABC algorithm are applied to a generated 3DBPP dataset to observe the effects of the memory mechanism and the genetic operators separately. In addition, a joint hybrid artificial bee colony (JHABC) algorithm, that uses both reinforcement approaches, has been developed. All three developed algorithm with the basic ABC algorithm has been tested on single container problem and multiple container problem data sets that widely used in the literature, and the performances of two reinforcement approaches has been compared by the test results. JHABC algorithm also has been compared with approaches from the literature. The results show that, the effect of the memory mechanism on the hybridized ABC algorithm, depends on the complexity of the problem to which it is applied, and the solution search time constraint. On the other hand, genetic operators are more useful reinforcement tools than the memory mechanism as the complexity of the problem increases, according to the test results. Compared with the results in the literature, JHABC algorithm obtains promising solution search results for container loading problems by using only complete random search method.