Geri Dön

Solving bin packing problem with problem specific operators using an evolutionary algorithm

Evrimsel algoritma kullanarak probleme özgü operatörler ile kutulama probleminin çözümü

PDF İndir

  1. Tez No: 582662
  2. Yazar: TUĞBA ZEYNEP YILDIZ
  3. Danışmanlar: DOÇ. DR. BETÜL DEMİRÖZ BOZ
  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: 2019
  8. Dil: İngilizce
  9. Üniversite: Marmara Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
  13. 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

  1. Tez No

    56304

    Submitted to the institutefor graduate studies in science and engineering

    Başlık çevirisi yok

    MEHMET ALİ BOZYEL

    Yüksek Lisans

    İngilizce

    İngilizce

    1996

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

    PROF. DR. LİNET ÖZDAMAR

  2. Tez No

    796392

    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

    İngilizce

    2022

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAltınbaş Üniversitesi

    Elektrik ve Bilgisayar Mühendisliği Ana Bilim Dalı

    YRD. DOÇ. DR. MESUT ÇEVİK

  3. Tez No

    697275

    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

    İngilizce

    2021

    Endüstri ve Endüstri MühendisliğiÖzyeğin Üniversitesi

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

    DOÇ. DR. ALİ EKİCİ

    DOÇ. DR. OKAN ÖRSAN ÖZENER

    PROF. DR. SERHAN DURAN

  4. Tez No

    694226

    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

    Türkçe

    2021

    Endüstri ve Endüstri MühendisliğiKarabük Üniversitesi

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

    PROF. DR. FİLİZ ERSÖZ

    PROF. DR. CEMALETTİN KUBAT

  5. Tez No

    415548

    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

    İngilizce

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. AHMET COŞAR

    YRD. DOÇ. DR. YUSUF SAHİLLİOĞLU

Geri Dön