Genetik algoritma ve benzetilmiş tavlama ile iki boyutlu giyotinsiz kesme problemlerine olasılıksal yaklaşım

Abstract

GENETİK ALGORİTMA ve BENZETİLMİŞ TAVLAMA ile İKİ BOYUTLU GİYOTİNSİZ KESME PROBLEMLERİNE OLASILIKSAL YAKLAŞIM Alev SOKE Anahtar Kelimeler: Genetik Algoritma, Benzetilmiş Tavlama, Yerleştirme Algoritmaları, İki Boyutlu Kesme ve Paketleme Problemleri, Kırma Yaklaşımlar. ÖZET: Kesme problemleri tam bir matematiksel modelle ifade edilemezler. Bu yüzden, bu problemlerin çözümünü bulmak için çok boyutlu uzayda kombinasyonel eniyileme yapılır. Kesme problemlerinin amacı, yerleştirmenin yapılacağı ana parçanın kullanılabilirliğini arttırmak ve böylelikle en az fire değerine sahip kesme yerleşim planını elde etmektir. Bu tez çalışmasında, Matlab ortamında iki boyutlu giyotinsiz kesme problemleri için bir çözüm yaklaşımı geliştirilmiştir. Bu problemlerin çözümü için ilk önce genetik algoritmalar (GA) ve geliştirilmiş aşağı sol (AS) algoritması, daha sonra benzetilmiş tavlama (BT) ve geliştirilmiş AS algoritması kullanıldı. Test problemleri 200x200 birimlik bir ana parça içine yerleştirilecek 1 7 ve 29 adet düzgün biçimli birbirinden farklı dikdörtgenlerden oluşan farklı parçalar içermektedir. Çalışmanın birinci bölümünde, kesme problemlerinin çözümü için sıralamaya dayalı bir GA ve geliştirilmiş AS algoritması birleştirildi. Bu çözüm yaklaşımı kırma GA olarak bilinmektedir, tik önce, kırma GA 1 7 parçalı test problemlerinin çözümü için kullanıldı. Bu problemlerin çözümü üzerinde farklı nüfus büyüklükleri ve mutasyon oranlarının etkileri incelenmiştir. Bu çalışmaya göre, nüfus büyüklüğü arttıkça fire değerinin azaldığı gözlemlenmiştir. Çözüm üzerinde mutasyon oranının çok küçük bir etkisi vardır. İkinci olarak kırma GA 29 parçalı bir test problemine uygulanmıştır. Bu kesme probleminin çözümü üzerinde farklı çaprazlama tekniklerinin etkileri incelenmiştir. Bu çalışma sonucunda en iyi sonucun sıralamaya dayalı çaprazlama tekniği ile elde edildiği görülmüştür. Çalışmanın ikinci bölümünde, BT ve geliştirilmiş aşağı sol (AS) algoritması aynı kesme problemlerinin çözümü için bir araya getirilmiştir. Bu çözüm yaklaşımı kırma BT olarak bilinmektedir. Kırma BT, ilk önce 17 parçalı test problemlerinin çözümü için uygulanmıştır. Bu kesme problemlerinin çözümü üzerinde farklı sıcaklık değerleri için, farklı soğutma planlarının, komşuluk hareketlerinin ve denge koşulu için farklı değerlerlerin etkileri incelenmiştir. İkinci olarak 29 parçalı bir test probleminin çözümü bir önceki çalışmada elde edilen en iyi sonuçların parametreleri kullanılarak çözülmüştür. Bu benzetim çalışmaları sonucunda, kırma GA kullanılarak elde edilen 17 ve 29 parçalı test problemlerinin fire değerleri sırasıyla %2 ve %11 arasında, %5 ve %9 arasında değişmektedir. Benzer olarak kırma BT kullanılarak elde edilen 17 ve 29 parçalı test problemlerinin fire değerleri sırasıyla %4 ve %21 arasında, %10 ve %17 arasında değişmektedir. Sonuç olarak, kesme problemleri için kırma GA'nın kırma BT'den daha iyi olduğu görülmektedir. ii

STOCHASTIC APPROACH FOR TWO DIMENSIONAL NON-GUILLOTINEABLE CUTTING PROBLEMS with GENETIC ALGORITHM and SIMULATED ANNEALING Alev SOKE Keywords; Genetic Algorithm, Simulated Annealing, Placement Algorithms, Two Dimensional Cutting and Packing Problems, Hybrid Approaches. ABSTRACT: Cutting problems can not be defined explicitly with a mathematical model. The solution of these problems are found by using combinational optimization in multi dimensional space. The objective of the cutting problems is to increase the usability of main object and thus to obtain the cutting pattern that has minimum trim loss values. In this thesis, A solution approach was developed for two dimensional non-guillotineable cutting problems in Matlab environment. First of all, genetic algorithms (GA) and improved bottom left (BL) algorithm were Used to solve this problems and then simulated annealing (SA) and improved BL algorithm were used. Test problems consist of different pieces: 17 and 29 regular individual rectangles to place in main object with 200x200 unit. First part of this work, an order-based GA is combined with improved BL algorithm to solve the cutting problems. This solution approach is known as hybrid GA. Firstly, hybrid GA was used to solve 1 7 pieces test problems. The influences of the different population sizes and mutation rates on the solution of these problems were examined. Base on this examination, it is observed that as the population size increases the trim loss value decreases. There is very small effect of mutation rate on the solution. Secondly hybrid GA was applied to 29 pieces a test problem. The influences of different crossover techniques on the solution of the cutting problem were studied. At the result of this study, it is seen that the best result is obtained with order based crossover technique. Second part of this work, SA and improved BL algorithm are combined to solve the same cutting problems. This solution approach is known as hybrid SA. Firstly, hybrid SA was applied to solve the 17 pieces test problems.The influences of different cooling schemes, neighbourhood moves and values for equilibrium condition on the solution of the cutting problems were examined for the different temperature values. Secondly, the solution for 29 pieces a test problem was solved using parameteres of the best results obtained in previous work. At the result of these simulations, the trim loss values of the 17 and 29 pieces test problems obtained by using hybrid GA are varied between 2% and 11%, 5% and 9% respectively. Similarly, the trim loss values of the 17 and 29 pieces test problems obtained by using hybrid SA are varied between 4% and 21%, 10% and 17% respectively. Finally, it is seen that hybrid GA gives better results than hybrid SA for cutting problems. in