Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma

Tansel DÖKEROĞLU

Makale detayları

Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma

Yazarlar:

Tansel DÖKEROĞLU

Yayıncı:

Balıkesir University

Ana Başlıklar:

Uygulamalı fizik

Dergi:

Journal of Balıkesir University Institute of Science and Technology 2017 Vol.19 Issue 1, pp.1-11

Belge Tipi:

Makale

Yayın Tarihi:

6/2017

Belge Dili:

Türkçe

Document ID (Org No.):

2000925576

Sıklık:

İki Yıllık

eISSN:

2536-5142

pISSN:

1301-7985

Anahtar kelimeler:

Özet:

 


One-Dimensional Bin
Packing Problem (1DBPP) is one of the most well-known NP-Hard problems of
industrial engineering. The execution time of a brute force approach algorithm
for finding the optimal solution for its problem instances with several items
(more than 50) can spend more than hundreds of years. Therefore, heuristic
algorithms that can find (near)-optimal solutions are preferred with their
reasonable optimization times. With this study, we propose a novel parallel
hyper-heuristic Grouping Genetic Algorithm (HHPGGA-1DBPP) that uses several
heuristics concurrently, whereas classical Grouping Genetic Algorithms (GGA)
use only a single one during the optimization. The solutions of the proposed
algorithm outperform the classical ones’. Best Fit Decreasing (BFD), First Fit
Decreasing (FFD), and Minimum Bin Slack (MBS) are the bin-oriented heuristics
used in the proposed algorithm. With the experiments carried out on 1,228
problem instances, 1,070 of the problems (88.1%) are solved optimally. The remaining
problems are optimized by producing only a single extra bin. These experimental
results show that the proposed algorithm can outperform Falkenauer GGA. The
obtained results are improved up to 9%.

.

 


Bir boyutlu kutulama problemi (1BKP), endüstri mühendisliğinin üzerinde
en çok çalışılan NP-Zor kombinatoriyal problemlerinden bir tanesidir. Büyük
sayıda (elliden fazla) parça içeren problem kümeleri için en iyi çözümün
bulunması klasik kaba kuvvet algoritmaları ile yüz yıllarca sürebilmektedir. Bu
yüzden (yaklaşık)-optimal çözümleri ile eniyilemeyi tam olarak ya da düşük
performans kayıpları ile kısa sürelerde bulabilen sezgisel algoritmalar
sıklıkla kullanılmaktadır. Bu çalışma ile birlikte, Gruplama Genetik
Algoritmalarında (GGA) kullanılan sezgisel kutulama tekniklerinden sadece bir
tanesini kullanan klasik yaklaşımlar yerine, aynı anda birçok sezgisel kutulama
tekniğini kullanan hiper-sezgisel paralel bir algoritma (HPGG-1BKP)
geliştirildi. En Uygun Boşluğu Doldur (EUBD), İlk Bulduğun Boşluğu Doldur
(İBBD) ve En Küçük Boşluğu Bırakarak Doldur (EKBBD) sezgisel kutu doldurma
algoritmaları bu algoritmada aynı anda paralel olarak kullanıldı. 1228 bençmark
problemi üzerinde yapılan deneyler sonucunda %88.1 başarı ile 1070 optimal
sonuç elde edildi. Geri kalan problemler için de sadece bir kutu daha fazla
kullanan çözümler üretilerek sonuçlar eniyilendi. Önerilen algoritma Falkenauer
GGA ile karşılaştırıldığında %9’a varan iyileşmeler elde edildi.

.

Makale detayları

Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma

Yazarlar:

Tansel DÖKEROĞLU

Yayıncı:

Balıkesir University

Ana Başlıklar:

Uygulamalı fizik

Dergi:

Journal of Balıkesir University Institute of Science and Technology 2017 Vol.19 Issue 1, pp.1-11

Belge Tipi:

Makale

Yayın Tarihi:

6/2017

Belge Dili:

Türkçe

Document ID (Org No.):

2000925576

Sıklık:

İki Yıllık

eISSN:

2536-5142

pISSN:

1301-7985

Genetik

bir boyutlu kutulama

paralel

hiper-sezgisel

Sayı

Makale detayları

Bir boyutlu kutulama probleminin eniyilenmesi için hiper-sezgisel paralel bir algoritma

Yazarlar: Tansel DÖKEROĞLU

Yayıncı: Balıkesir University

Ana Başlıklar: Uygulamalı fizik

Dergi: Journal of Balıkesir University Institute of Science and Technology 2017 Vol.19 Issue 1, pp.1-11

Belge Tipi: Makale

Yayın Tarihi: 6/2017

Belge Dili: Türkçe

Document ID (Org No.): 2000925576

Sıklık: İki Yıllık

eISSN: 2536-5142

pISSN: 1301-7985

Genetik

bir boyutlu kutulama

paralel

hiper-sezgisel

Sayı

Yazarlar:

Tansel DÖKEROĞLU

Yayıncı:

Balıkesir University

Ana Başlıklar:

Uygulamalı fizik

Dergi:

Journal of Balıkesir University Institute of Science and Technology 2017 Vol.19 Issue 1, pp.1-11

Belge Tipi:

Makale

Yayın Tarihi:

6/2017

Belge Dili:

Türkçe

Document ID (Org No.):

2000925576

Sıklık:

İki Yıllık

eISSN:

2536-5142

pISSN:

1301-7985