Hybrid metaheuristic algorithms for single and multi-objective 2D Bin packing problem
Tek ve çok amaçlı iki boyutlu kutu paketleme problem için melez metasezgisel algoritmalar
- Tez No: 383005
- Danışmanlar: PROF. DR. AHMET COŞAR, DR. TANSEL DÖKEROĞLU
- 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: 2015
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 104
Özet
İki boyutlu kutu paketleme problemi çözümü polinom zamanlı olmayan (NP) kombinatoriyal bir problemdir. Farklı genişlik ve uzunluktaki nesnelerin en az kutu kaplayacak şekilde birim kapasiteli kutulara bir nesnel fonksiyonun en az sonuç üretecek şekilde yerle¸stirilmesidir. Çok bilinen bu endüstri probleminin çok amaçlı versiyonlarıyla gündelik hayatta sıkça karşılaşılmaktadır. Kesin çözüm bulmanın mümkün olmadı ğı büyük ölçekli 2 boyutlu kutu paketleme problemleri için şimdiye kadar birkaç sezgisel yöntem önerilmiştir. Sonraki Ekleme, İlk Ekleme, En İyi Ekleme, Birleşik Tabu Araması ve Genetik Algoritmalar bu algoritmaların en çok kullanılan birkaçıdır. Son zamanlarda, farklı sezgisel ve lokal aramaları birleştirerek daha yüksek kalitede sonuç üreten Memetik Algoritmalar evrimsel hesaplamalarda yeni bir araştırma alanı olmuştur. Bu tezde, 2 boyutlu kutu paketleme problemi için metasezgisel ve lokal aramayı kullanan tek ve çok amaçlı memetik ve genetik algoritmalardan oluşan bir çözüm kümesi sunduk. 500 problem içeren çevrimdışı bir problem kümesi ile algoritmalarımızın optimizasyon zamanlarını ve sonuç kalitelerini analiz ettik. Bu projede geliştirdiğimiz görsel analiz aracı ile de yapılan yoğun testler sonucunda, geliştirdiğimiz memetik ve genetik algoritmaların kullanılan problem kümeleri üzerinde yüksek oranda optimum sonuç ürettiği neticesine vardık.
Özet (Çeviri)
2D Bin packing problem (2DBPP) is an NP-hard combinatorial optimization problem. Objects with different width and length sizes are packed in order to minimize the number of unit-capacity bins according to an objective function. Single or multiobjective versions of this well-known industrial engineering problem can be faced frequently in real life situations. There have been several heuristics proposed for the solution of 2DBPP until now where it is not possible to find the exact solutions for large problem instances. Next fit, First Fit, Best Fit, Unified Tabu Search and Genetic Algorithms are some of these algorithms. Recently, Memetic Algorithms have put themselves forward as a new area of research in evolutionary computation with their ability to combine different heuristics and local search mechanisms together for higher quality solutions. In this thesis, we propose a set of single and multiobjective memetic and genetic algorithms that make use of the state-of-the-art metaheuristics and local search techniques for the solution of 2DBPP. We analyze the optimization time and the resulting solution quality of the algorithms on a 2DBPP benchmark offline problem set with 500 instances. Through results of exhaustive experiments and with the aid of a novel visual analyzer developed in this study, we conclude that the proposed memetic and hybrid genetic algorithms are robust with their ability to obtain very high percentage of the optimal solutions for the given benchmark problem instances.
Benzer Tezler
- Optimization methodology for application mapping in wireless network-on-chip
Kablosuz yonga-üstü-ağlar için uygulama eşleme optimizasyon metodolojisi
ALPEREN ÇAKIN
Yüksek Lisans
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. SÜLEYMAN TOSUN
- İşgören yetkinliklerini ve tampon istasyonları dikkate alan çok modelli montaj hatlarının tasarımı
Design of multi model assembly lines considering labour competencies and buffer stations
KADİR TUNÇ DOLAR
Yüksek Lisans
Türkçe
2022
Endüstri ve Endüstri Mühendisliğiİstanbul Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET BÜLENT DURMUŞOĞLU
- Çok amaçlı enerji verimli atölye çizelgeleme problemi için yeni bir çözüm yaklaşımı: WASPAS tabanlı NSGA-2
A new solution approach for multi-objective energy efficient job shop scheduling problem: WASPAS based NSGA-2
MİNE BÜŞRA GELEN MERT
Doktora
Türkçe
2024
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALPARSLAN SERHAT DEMİR
- Metasezgisel algoritmalar ve derin öğrenme kullanılarak çok kaynaklı görüntü füzyonu
Multi-source image fusion using metaheuristic algorithms and deep learning
ASAN IHSAN ABAS ABAS
Doktora
Türkçe
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. NURDAN BAYKAN
- Metaheuristic pansharpening based on symbiotic organisms search optimization
Ortak yaşam arama algoritması tabanlı metasezgisel pan-keskinleştirme
ÇİĞDEM ŞERİFOĞLU YILMAZ
Doktora
İngilizce
2020
Jeodezi ve FotogrametriKaradeniz Teknik ÜniversitesiHarita Mühendisliği Ana Bilim Dalı
PROF. DR. OĞUZ GÜNGÖR