Genetik algoritma ve benzetilmiş tavlama ile iki boyutlu giyotinsiz kesme problemlerine olasılıksal yaklaşım
Tezin Türü: Yüksek Lisans
Tezin Yürütüldüğü Kurum: Kocaeli Üniversitesi, Fen Bilimleri Enstitüsü, Elektronik ve Bilgisayar Eğitimi, Türkiye
Tezin Onay Tarihi: 2003
Tezin Dili: Türkçe
Öğrenci: ALEV SÖKE
Danışman: Zafer Bingül
Açık Arşiv Koleksiyonu: AVESİS Açık Erişim Koleksiyonu
Özet: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