Genetik algoritmaların farklı çaprazlama teknikleriyle iki boyutlu kesme problemlerine uygulanışı

Bu çalışmada, farklı çaprazlama teknikleri kullanan genetik algoritmalar (GA) ve geliştirilmiş aşağı sol (AS) algoritmasının ortak kullanımıyla 2 boyutlu giyotinsiz bir kesme problemine Matlab ortamında çözüm geliştirilmiştir. 200x200 birimlik bir alan ile sınırlandırılmış bir büyük parça ve yerleşecek 29 adet birbirinden farklı düzgün dikdörtgen parçadan oluşan bir test problemi üzerinde çalışılmıştır. Çalışma sonucunda aynı problem için, farklı çaprazlama tekniklerinin birbirinden çok farklı sonuçlar verdiği görülmüştür. Tüm nesil boyunca her çaprazlama tekniği için elde edilmiş uygunluk değerlerinin aritmetik ortalamalarının ve standart sapmalarının frekansları, en iyi sonucun sıralamaya dayalı çaprazlama tekniği ile, en kötü sonucun ise Stefan Jakobs çaprazlama tekniği ile elde edildiğini göstermektedir.

Applying genetic algorithms with different crossover techniques to two dimensional cutting problems

In this study, a solution was developed for the two dimensional non -.guillotine a cutting problem by using both genetic algorithms (GAs) with different crossover techniques and improved bottom left (BL) algorithm in Matlab environment. A test problem which consists of a large piece that is limited with 200x200 unit field and 29 regular individual rectangle pieces to place in. At the end of this study, it was observed that the different crossover techniques for the same problem produced very different results. The frequencies of arithmetic means and standard deviations of the fitness values obtained for each of the crossover techniques during the whole generation showed that the best result was obtained with the order base crossover technique and the worst one with Stefan Jakobs crrosover technique.

___

1. Hopper, E., Two-Dimensional Packing Utilising Evolutionary Algorithms and Other Meta-Heuristic Methods, PhD Thesis, Cardiff University, UK, 2000.
2. Leung, T.W., Yung, C.H. and Trout, M.D., Applications of Genetic Search and Simulated Annealing to The Two-Dimensional Non- Guillotine Cutting Stock Problem, Computers & Industrial Engineering, vol.40, pp.201-214, 2001.
3. Hopper, E. and Turton, B., Application of Genetic Algorithms to Packing Problems - A Review, Proceedings of the 2nd On-line World Conference on Soft Computing in Engineering Design and Manufacturing, Springer Verlag, pp.279-288, 1997.
4. Callaghan, A. R., Nair A. R. and Lewis, K. E., An Extension of The Orthogonal Packing Problem Through Dimensional Flexibility, Proceedings of DETC'99: 1999 ASME Design Engineering Technical Conferences, vol.199, pp.12-15,1999.
5. Holland, J.H. Adaption in Natural and Artificial Systems, University of Michigan Pres, Ann Arbor, MI, 1975.
6. Leitch, D.D., A New Genetic Algorithm for The Evolution of Fuzzy Systems, PhD Thesis, University of Oxford, UK, 1995.
7. Beasley, D., Bull, D. R. and Martin, R. R., An Overview of Genetic Algorithms: Part 1, Fundamentals, University Computing, vol.l5(2), pp.58-69, 1993.
8. Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison- Wesley, Reading, MA, 1989.
9. Houck, C.R., Joines, J. and Kay, M., A Genetic Algorithm for Function Optimization: A Matlab Implementation. ACM Transactions on Mathematical Software, 1996
lO.Jakobs, S., On Genetic Algorithms for The Packing of Polygons, European Journal of Operational Research, vol.88, pp. 165-181, 1996.
11.Liu, D. and Teng, H., An Improved BL-Algorithm for Genetic Algorithm of The Orthogonal Packing of Rectangles, European Journal of Operational Research, vol.112, pp.413-420,1999.
12. Söke, A. ve Bingül, Z., İki Boyutlu Kesme Problemlerinin Genetik Algoritma Yardımıyla Çözümünün İncelenmesi, XII. International Twelfth Turkish Symposium on Artifical Intelligence and Neural Networks, 2-4 July, 2003, Çanakkale, Turkey