Solving bin packing problem with problem specific operators using an evolutionary algorithm
Evrimsel algoritma kullanarak probleme özgü operatörler ile kutulama probleminin çözümü
- Tez No: 582662
- Danışmanlar: DOÇ. DR. BETÜL DEMİRÖZ BOZ
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2019
- Dil: İngilizce
- Üniversite: Marmara Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: 56
Özet
Kutu paketleme problemi, literatürdeki en önemli optimizasyon problemlerinden biridir. Problem çok çeşitli gerçek yaşam kullanımına sahiptir. Kutu paketleme problemi NP-Hard sınıfına ait olduğundan, bu problemi farklı alanlarda kendi avantajlarıyla çözmek için önerilen birçok çözüm vardır, ancak çoğu optimum çözüme ulaşamamıştır. Kutu paketleme probleminde, kutulara yerleştirilmesi gereken sınırlı sayıda obje vardır. Her objenin kendi ağırlığı vardır ve her kutu sınırlı bir kapasiteye sahiptir. Problemin temel amacı, tüm objeleri kutulara koyarken, kullanılan kutu sayısını en aza indirmektir. Bu çalışmada, tek boyutlu kutu paketleme problemini çözmek için yeni bir havuz temelli evrimsel algoritma öneriyoruz. Algoritma, problemin arama alanını arttırmayı amaçlayan havuz tabanlı bir çaprazlama operatörü ve çaprazlama çözümü sonucunda oluşan bireyde mevcut olan az kullanılmış kutuları dikkate alarak çözümün kalitesini iyileştirmeyi amaçlayan yerel bir arama tekniğini kullanır. Önerilen yöntem, kıyaslama problem kümelerinden alınan orta ve zor örneklere uygulandı ve literatürdeki altı algoritma ile karşılaştırıldı. Deneysel sonuçlarımız, önerilen algoritmanın, sağlanan test vakalarının çoğunda bu algoritmalardan önemli ölçüde daha iyi performans sergilediğini göstermektedir.
Özet (Çeviri)
Bin packing problem is one of the most important optimization problems from the literature. The problem has a wide range of real life usage. Since bin packing problem belongs to NP-Hard class, there are many heuristics proposed to solve this problem with their own advantages in different domains, but most of them could not reach the optimum solution. In bin packing problem, there are finite number of items which must be placed into bins. Each item has their own weight and each bin has a finite capacity. Main objective of the problem is to place all items into the bins in a manner that minimizes the number of bins used. This work proposes a novel pool-based evolutionary algorithm for the solution of one-dimensional bin packing problem. The algorithm exploits a pool-based crossover operator which increases the problem's search space and a local search method which tries to decrease the bin usage of the solution by considering underutilized bins available in the offspring. The proposed method is applied to medium and hard instances taken from benchmark problem sets and is compared with six algorithms from the literature. Our experimental evolution indicates that the proposed algorithm significantly outperforms these algorithms in most of the test cases provided.
Benzer Tezler
- Submitted to the institutefor graduate studies in science and engineering
Başlık çevirisi yok
MEHMET ALİ BOZYEL
Yüksek Lisans
İngilizce
1996
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiPROF. DR. LİNET ÖZDAMAR
- Solving bin packing problem based on parallel hybrid genetic algorithm
Paralel hıbrıt genetık algorıtmaya dayalı hazır paketleme problemını çözme
MOHAMMED HUSHAM ABDULKAREEM ABDULKAREEM
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş ÜniversitesiElektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. MESUT ÇEVİK
- Single machine scheduling with sequence dependent setup times
Sıra bağımlı hazırlık süreleriyle tekli makina çizelgeleme
BURAK LEFKUR
Yüksek Lisans
İngilizce
2021
Endüstri ve Endüstri MühendisliğiÖzyeğin ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ EKİCİ
DOÇ. DR. OKAN ÖRSAN ÖZENER
PROF. DR. SERHAN DURAN
- Etkili bir yapay arı kolonisi algoritmasının üç boyutlu kutu doldurma problemi üzerinde uygulanması
An effective artificial bee colony algorithm for solving three-dimensional bin packing problem
TUĞRUL BAYRAKTAR
Doktora
Türkçe
2021
Endüstri ve Endüstri MühendisliğiKarabük ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. FİLİZ ERSÖZ
PROF. DR. CEMALETTİN KUBAT
- Scalable evolutionary algorithm for solving the one-dimensional bin packing problem on GPU using CUDA
Tek boyutlu kutu paketleme probleminin grafik işlemci üzerinde CUDA kullanılarak ölçeklenebilir evrimsel algoritma ile çözümü
ŞÜKRÜ ÖZER ÖZCAN
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET COŞAR
YRD. DOÇ. DR. YUSUF SAHİLLİOĞLU