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

Tansel Dökeroğlu

Öz


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.


Tam Metin:

PDF

Referanslar


Garey, M. R., and Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman, (1979).

Dokeroglu, T., and Cosar, A., Optimization of one-dimensional bin packing problem with island parallel grouping genetic algorithms. Computers and Industrial Engineering, 75, 176-186, (2014).

Stawowy, A., Evolutionary based heuristic for bin packing problem. Computers and Industrial Engineering, 55, 465–474, (2008).

Burke , E.K., McCollum, B., Meisels, A., Petrovic, S., and Qu, R., A graph-based hyper-heuristic for educational timetabling problems, European Journal of Opertions Research 176, 1, 177–192, (2007).

Burke, E.K., Hyde, M., Kendall, G., Ochoa, G., Ozcan, E., and Woodward, J.R., A classification of hyper-heuristic approaches, in: Handbook of Metaheuristics, Springer US, 449–468, (2010).

Beyaz, M., Dokeroglu, T., and Cosar, A. Robust hyper-heuristic algorithms for the offline oriented/non-oriented 2D bin packing problems. Applied Soft Computing, 36, 236-245, (2015).

Wolpert, D.H., and Macready, W.G., No free lunch theorems for optimization. Evolutionary Computation, IEEE Transactions on, 1, 1, 67-82, (1997).

Cantu-Paz, E., Efficient and accurate parallel genetic algorithms. Kluwer Academic Publishers, (2000).

Martello, S., and Toth, P., Knapsack Problems. Wiley, (1990).

Gupta, J.N.D., and Ho, J.C., A new heuristic algorithm for the one-dimensional bin packing problem. Production Planning and Control 10, 6, 598-603, (1999).

Fleszar, K., and Charalambous, C., Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem. European Journal of Operations Research, 210, 176–184, (2011).

Falkenauer, E., A new representation and operators for GAs applied togrouping problems. Evolutionary Computation, 2, 2, 123–144, (1994).

Bozejko, W., Uchronski, M., and Wodecki, M., Parallel hybrid metaheuristics for the flexible job shop problem. Computers & Industrial Engineering, 59, 2, 323–333, (2010).

Falkenauer, E., A hybrid grouping genetic algorithm for bin packing. Journal of Heuristics, 2, 1, 5–30, (1996).

Scholl, A., Klein, R., and Jurgens, C., BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem. Computers and Operations Research, 24, 7, 627–645, (1997).

Belov, G., Scheithauer, G., and Mukhacheva, E. A., One-dimensional heuristics adapted for two-dimensional rectangular strip packing. Journal of the Operational Research Society, 59, 6, 823–832, (2007).


Refback'ler

  • Şu halde refbacks yoktur.


Telif Hakkı (c) 2017 Tansel DÖKEROĞLU

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.