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ü
- Tez No: 415548
- Danışmanlar: PROF. DR. AHMET COŞAR, YRD. DOÇ. DR. YUSUF SAHİLLİOĞ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ı: 123
Özet
Farklı genişlik ve uzunluktaki nesnelerin mümkün olan en az sayıda sabit kapasiteli kutu kullanılarak yerleştirilmesini amaçlayan tek boyutlu kutu paketleme problemi, çözümü polinom zamanlı olmayan (NP) ve endüstri mühendisliği alanında popüler olan kombinatoriyal bir en iyileme problemdir. Çok bilinen bu endüstri probleminin çok amaçlı versiyonlarıyla gündelik hayatta sıkça karşılaşılmaktadır. 20 kutuya kadar olan küçük ölçekli problemler karmaşık olmayan basit algoritmalar kullanılarak çözülebilse de, büyük ölçekli problemlere optimal çözüm üretmek problemin kolay takip edilemeyen doğası sebebiyle mümkün olmayabilir. Kesin çözüm bulmanın mümkün olmadığı büyük ölçekli söz konusu problemlere en iyi çözümü bulabilmek amacı ile şimdiye kadar En Az Boşluk Algoritması, Tabu Araması, Parçacık Sürü Optimizasyonu benzeri sezgisel yontemler yaygın olarak kullanılmıştır. Ancak, problemin çözümüne yönelik geliştirilen bu sezgisel yöntemler performansı artıran son nesil paralel bilgisayar teknolojisi kullanılmaksızın tek bir işlemci kullanilarak çözülmüştür. Bu çalışma ile literatürde ilk defa CUDA (Compute Unified Device Architecture) kullanılarak grafik islemci birimi (GPU) katkısı ile Gruplama Genetik Algoritması (GGA)'nın performansı artırılmıştır. Heterojen bir mimari üzerinde koşturulan program ile GGA'nin islem süresini uzatan çarprazlama ve mutasyon algoritmalari GPU uzerinde çalıştırılmış, sonuçlar ise ekran kartı üzerinde bulunan global bellek üzerinde tutulmuştur. 1.238 farkli problem seti uzerinde koşturulan problem ve sonuçlari, Tek Boyutlu Kutulama CUDA GPU algoritmasının literatürde yer alan en iyi algoritmalar arasında yer alabileceğini ve CPU karşılığına göre de 60 kat daha hızlı olabileceğini göstermiştir.
Özet (Çeviri)
One-dimensional Bin Packing Problem (1DBPP) is a challenging NP-Hard combinatorial industrial engineering problem which is used to pack finite number of items into minimum number of fixed size bins. Different versions of 1DBPP can be faced in real life. Although the problems that have small number of items up to 20 can be solved with brute-force algorithms, large problem instances of the 1DBPP cannot be solved exactly due to its intractable nature. Therefore, heuristic approaches such as Genetic, Particle Swarm, Tabu Search, and Minimum Bin Slack have been widely used to solve this important problem (near-) optimally. Most of the the state-of-the-art algorithms that have been proposed to solve the 1DBPP are executed on a single processor and do not make use of the high performance opportunities that are offered by the recent parallel computation technologies. In this study, we increase the performance of a Grouping Genetic Algorithm (GGA) by harnessing the power of the graphics processing unit (GPU) using Compute Unified Device Architecture (CUDA) for the first time in literature. The time consuming crossover and mutation processes of the GGA are executed on the GPU and the population of solutions is kept on the global memory of GPU while running the whole algorithm in a heterogeneous computing environment. The obtained experimental results on 1,238 benchmark problem instances show that the proposed algorithm, CUDA GGA for 1DBPP (CUDA-GGA-1DBPP), is a high performance and scalable algorithm that can be counted among the best performing algorithms in literature and it is about 60 times faster than its CPU counterpart.
Benzer Tezler
- BitVertex evolutionary algorithm for accelerating graph coloring in register allocation
Kayıt tahsisinde çizge renklendirmeyi hızlandırmak için BitVertex evrimsel algoritması
GİZEM SÜNGÜ TERCİ
Doktora
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolGebze Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ALP ARSLAN BAYRAKÇİ
DR. ÖĞR. ÜYESİ BETÜL BOZ
- Sosyal örümcek algoritmasının sürekli ve ayrık optimizasyon problemlerinde performans iyileştirmeleri
Performance improvements of social spider algorithm in continuous and discrete optimization problems
EMİNE BAŞ
Doktora
Türkçe
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolKonya Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ERKAN ÜLKER
- Budget-constraint workflow scheduling for cloud computing using evolutionary algorithm
Bulut hesaplama için evrimsel algoritma kullanarak bütçe kısıtlamalı iş akışı planlaması
MEHMET KAYA
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolMarmara ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ BETÜL BOZ
- Multi-objective evolutionary algorithms for multi-label classification supported by deep auto-encoder on image and video data
Çok etiketli sınıflama ̇için çok amaçlı evrimsel algoritmaların derin otokodlayıcı desteği ̇ile resim ve video verilerine uygulanması
GİZEM NUR KARAGÖZ
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. MEHMET HALİT SEYFULLAH OĞUZTÜZÜN
PROF. DR. ADNAN YAZICI
- Developing an obsolescence management plan model for sustainment dominated electronic systems using cots parts
Rahat ürün kullanan uzun ömür devirli elektronik sistemler için demodelik yönetim planı modeli geliştirme
BARIŞ EGEMEN ÖZKAN
Doktora
İngilizce
2022
Endüstri ve Endüstri MühendisliğiMarmara ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. SEROL BULKAN