Geri Dön

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

  1. Tez No: 383005
  2. Yazar: MUHAMMED BEYAZ
  3. Danışmanlar: PROF. DR. AHMET COŞAR, DR. TANSEL DÖKEROĞLU
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2015
  8. Dil: İngilizce
  9. Üniversite: Orta Doğu Teknik Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolHacettepe Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. SÜLEYMAN TOSUN

  2. İş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

    Türkçe

    2022

    Endüstri ve Endüstri Mühendisliğiİstanbul Teknik Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    PROF. DR. MEHMET BÜLENT DURMUŞOĞLU

  3. Ç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

    Türkçe

    2024

    Endüstri ve Endüstri MühendisliğiSakarya Üniversitesi

    Endüstri Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ALPARSLAN SERHAT DEMİR

  4. 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

    Türkçe

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSelçuk Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. NURDAN BAYKAN

  5. 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

    İngilizce

    2020

    Jeodezi ve FotogrametriKaradeniz Teknik Üniversitesi

    Harita Mühendisliği Ana Bilim Dalı

    PROF. DR. OĞUZ GÜNGÖR