Grup Teknolojilerinde Kümelendirme Yöntemlerine Sezgisel
Transkript
Grup Teknolojilerinde Kümelendirme Yöntemlerine Sezgisel
T. C. İstanbul Üniversitesi Sosyal Bilimler Enstitüsü Üretim Anabilim Dalı Yüksek Lisans Tezi GRUP TEKNOLOJİLERİNDE KÜMELENDİRME YÖNTEMLERİNE SEZGİSEL YAKLAŞIMLAR ve BİR UYGULAMA Musa Can KAPLAN 2501040109 Doç. Dr. Necdet ÖZÇAKAR İstanbul 2008 ÖZ Bu tez çalışmasında, Grup Teknolojisi yöntemi incelenerek, makine - ürün eşleştirmelerinin kümelendirilmesi problemi konusunda çözüm teşkil edebilecek sezgisel yöntemler ele alınmıştır. Çalışmada ele alınan sezgisel yöntemler, OVS, AVS ve AVS-M olarak isimlendirilen köşe - değişimi yöntemleri ve Genetik Algoritma yöntemidir. Bu yöntemlerin herbirinin kümelendirmede nasıl uygulanacağından bahsedilmiş, algoritmaları verilmiş, AVS ve Genetik Algoritma yöntemleri için örnek problemler çözülmüştür. Çözülen problemler, farklı büyüklükteki makine - ürün matrisi verilerini içerir. Problemler literatürde üzerinde çalışılmış örnek kümeleme problemlerinden seçilmiştir. Yapılan uygulamada tekstil sektöründe faaliyet gösteren bir şirkete ait veriler kullanılmıştır.. Tüm örnekler MATLAB ve MS Office – Excel üzerinde VB Script dili kullanılarak çözülmüştür. Elde edilen çözümler literatürde geçen bir verimlilik ölçütü ile değerlendirilmiştir. iii ABSTRACT In this thesis the heuristic methods that can be used for solving machine-part clustering problems are dealt with by investaging Group Technology method. The heuristic methods that are dealt with in the thesis are vertex substitution methods named OVS, AVS, AVS-M and Genetic Algorithm. It is given how the algorithms work and how each methods are applied to clustering problems. Sample problems are solved with AVS and Genetic Algorithm methods. Solved problems contain different size of machine-part matrices. The problems are chosen from the sample literature clustering problems. In the application uses the datas from a company that is in textile industry sector. All of the examples are solved with MATLAB and VB Script over MS Office Excel. The results are evaluated with a efficiency criterion. iv ÖNSÖZ Tez sürecinin başlangıcından itibaren, gerek tez gerekse tez diğer konularda sık sık görüşme olanağı bulduğum ve anlayışı, teşvik edici davranışlarıyla büyük desteğini gördüğüm danışman hocam, sayın Doç. Dr. Necdet ÖZÇAKAR’ a, Konuyu tartışma fırsatı bulabildiğim araştırma görevlisi arkadaşlarım Rüya ŞAMLI, Nihan ÖZŞAMLI, Vefa ARIKAN’ a ve gösterdikleri sabır ve anlayıştan dolayı aileme, Teşekkürlerimi bir borç bilirim... Musa Can KAPLAN, Eylül 2008. v İÇİNDEKİLER ÖZ .......................................................................................................................... iii ABSTRACT ........................................................................................................... iv ÖNSÖZ ....................................................................................................................v İÇİNDEKİLER....................................................................................................... iii ŞEKİLLER ...............................................................................................................x TABLOLAR........................................................................................................... xi GİRİŞ .......................................................................................................................1 1 GRUP TEKNOLOJİSİ ......................................................................................4 1.1 GRUP TEKNOLOJİSİNE GİRİŞ ...............................................................4 1.2 GRUP TEKNOLOJİSİNİN TARİHSEL GELİŞİMİ ...................................7 1.3 GRUP TEKNOLOJİSİNİN AVANTAJLARI .............................................8 1.3.1 İŞ AKIŞLARINA ETKİSİ ...................................................................8 1.3.2 TAŞIMA MİKTARLARINA ETKİSİ .................................................8 1.3.3 Üretim İçi Stoklarına Etkisi .................................................................8 1.3.4 Toplam Üretim Zamanına Etkisi..........................................................9 1.3.5 Makine Hazırlık Zamanına Etkisi ........................................................9 1.3.6 Üretim Kalitesine Etkisi.......................................................................9 1.3.7 ÜPK (Üretim Planlama Kontrol) Faaliyetlerine Etkisi.........................9 1.3.8 İş Görene Etkisi ...................................................................................9 vi 1.3.9 Fabrika Kullanım Alanına Etkisi........................................................10 1.3.10 Veri Bankasına Etkisi ........................................................................10 1.3.11 Tasarıma Etkisi..................................................................................10 1.3.12 Maliyet Tahminlerinde Kullanılabilirlik.............................................11 1.3.13 Sayısal Kontrollü Makinelerde Kullanılabilirlik.................................11 2 1.4 GRUP TEKNOLOJİSİNİN DEZAVANTAJLARI....................................11 1.5 GRUP TEKNOLOJİSİNİN UYGULAMA AŞAMALARI .......................12 1.6 GRUP TEKNOLOJİSİNDE KÜMELENDİRME ALGORİTMALARI ....13 1.6.1 1.6.1 Kümelendirmede Modelleme Yaklaşımı ..................................13 1.6.2 Kümelendirmede Sezgisel Yaklaşımlar..............................................15 1.6.3 Benzerlik Katsayısı Bazlı Algoritmalar..............................................15 PROBLEM ve YÖNTEM ...............................................................................18 2.1 -MEDİAN PROBLEMİ..........................................................................18 2.2 P-MEDİAN PROBLEMİ ÇÖZÜM TEKNİKLERİ ...................................20 2.3 ORİJİNAL KÖŞE DEĞİŞİMİ (ORİGİNAL VERTEX SUBSTİTUTİON - OVS ) YÖNTEMİ...............................................................................................20 2.4 AYARLANMIŞ KÖŞE DEĞİŞİMİ (ADJUSTED VERTEX SUBSTİTUTİON - AVS) YÖNTEMİ .................................................................24 2.5 ÇOKLU BAŞLANGIÇ NOKTALARI İLE AYARLANMIŞ KÖŞE DEĞİŞİMİ (ADJUSTED VERTEX SUBSTİTUTİON METHOD STARTİNG POİNTS AVS-M) YÖNTEMİ...........................................................................25 vii 2.6 GENETİK ALGORİTMA ........................................................................26 2.6.1 Genetik Algoritmaya Giriş.................................................................26 2.6.2 Genetik Algoritmanın Tarihçesi.........................................................29 2.6.3 Genetik Algoritma Tekniği ................................................................29 2.6.4 Genetik Algoritmanın Aşamaları .......................................................30 2.6.5 Genetik Algoritma Terimleri..............................................................31 2.6.6 Genetik Algoritma Kodlama Türleri ..................................................36 2.6.7 Genetik Algoritmanın Diğer Yöntemlerden Farkları .........................37 2.6.8 Genetik Algoritmanın Faydaları.........................................................39 2.6.9 Genetik Algoritma Araçları................................................................39 2.6.10 Genetik Algoritma Kullanım Alanları ................................................39 2.6.11 Genetik Algoritma Genel Uygulama Alanları ....................................40 2.6.12 Genetik Algoritmanın İşletmelerdeki Uygulama Alanları...................41 2.6.13 Genetik Algoritmanın Üretimde Uygulama Alanları ..........................42 3 UYGULAMALAR .........................................................................................45 3.1 GENETİK ALGORİTMA UYGULAMASI..............................................45 3.2 OVS ALGORİTMASI VE ÖRNEK UYGULAMASI...............................54 3.3 AVS ALGORİTMASI VE ÖRNEK UYGULAMASI...............................57 3.4 ÖBEKLEME UYGULAMASI – 1............................................................61 3.5 ÖBEKLEME UYGULAMASI - 2 ............................................................65 viii 3.6 ÖBEKLEME UYGULAMASI - 3 ............................................................68 3.7 TEKSTİL SEKTÖRÜNDE BİR UYGULAMA ........................................73 SONUÇ ve ÖNERİLER........................................................................................78 EKLER...................................................................................................................81 EK A: ÖBEKLEME İÇİN BİLGİSAYAR PROGRAMI .....................................81 EK B : MATLAB PROGRAMI ..........................................................................93 KAYNAKÇA .......................................................................................................100 ix ŞEKİLLER Şekil 1: Genetik Algoritmanın Aşamaları ,.............................................................30 Şekil 2: Genetik Algoritma Örneği İçin Makine - Ürün Gruplanması ...................47 Şekil 3: Genetik Algoritma Örneği İçin Problemin Gösterimi .................................51 Şekil 4 : Genetik Algoritma Örneği İçin MATLAB Uygulaması Ekran Görüntüsü 1 ............................................................................................................52 Şekil 5: Genetik Algoritma Örneği İçin MATLAB Uygulaması Ekran Görüntüsü 2 ............................................................................................................52 Şekil 6 : Öbekleme Uygulaması - 1 İçin Öbekler.....................................................64 Şekil 7: Öbekleme Uygulaması - 2 İçin Öbekler.....................................................67 x TABLOLAR Tablo 1: Benzerlik Katsayısı Bazlı Algoritma .........................................................17 Tablo 2 : Genetik Algoritma İçin Permutasyon Kodlama ........................................36 Tablo 3: Genetik Algoritma İçin Değer Kodlama....................................................37 Tablo 4: Genetik Algoritma Örneği İçin Ürün 1’in Makine Matrisindeki Satırı ......47 Tablo 5: Genetik Algoritma Örneği İçin Kromozomlar ...........................................49 Tablo 6: Genetik Algoritma Örneği İçin Çaprazlama Noktaları...............................49 Tablo 7: Genetik Algoritma Örneği İçin Kromozomların Çaprazlamadan Sonraki Durumu ..................................................................................................................49 Tablo 8: Genetik Algoritma Örneği İçin Çaprazlamadan Sonraki İlk Çocuk Kromozom..............................................................................................................50 Tablo 9: Genetik Algoritma Örneği İçin Kromozomun İşlemden Sonraki Hali........50 Tablo 10: Genetik Algoritma Örneği İçin 2. Çocuk Kromozom ..............................50 Tablo 11: Genetik Algoritma Örneği İçin 2. Kromozom..........................................50 Tablo 12: Genetik Algoritma Örneği İçin 3. Kromozom..........................................51 Tablo 13: Genetik Algoritma Örneği İçin Best_chromosome Vektöründe Makine Grupları ..................................................................................................................54 Tablo 14: Genetik Algoritma Örneği İçin Best_part Vektöründe Ürün Grupları ......54 Tablo 15: Öbekleme Uygulaması - 1 İçin Makine – Ürün Matrisi ...........................62 Tablo 16 : Öbekleme Uygulaması - 1 İçin Makine – Makine Matrisi.......................63 Tablo 17: Öbekleme Uygulaması - 1 İçin Öbekleme Değişimi Tablosu...................63 xi Tablo 18 : Öbekleme Uygulaması - 1 İçin Öbekler..................................................64 Tablo 19: Öbekleme Uygulaması – 2 İçin Makine – Ürün Matrisi...........................65 Tablo 20 : Öbekleme Uygulaması - 2 İçin Makine – Makine Matrisi.......................66 Tablo 21 : Öbekleme Uygulaması - 2 İçin Öbekler..................................................67 xii GİRİŞ Bu tez çalışmasında, Grup Teknolojisi yöntemi incelenerek, makine - ürün eşleştirmelerinin kümelendirilmesi problemi konusunda çözüm teşkil edebilecek sezgisel yöntemler ele alınmıştır. Bu yöntemler, OVS, AVS, AVS-M ve Genetik Algoritma yöntemleridir. Bu bölümde tezde incelenen konulardan bahsedilmiş ve tezin bölümlerine ait genel bilgiler verilmiştir. Çalışma, üç ana bölümden oluşmaktadır, ayrıca “Sonuç ve Öneriler” bölümü ile kodların verildiği “Ekler” bölümü bulunmaktadır. Birinci bölümde Grup Teknolojisi (GT) kavramı incelenmiş, GT’nin neden gittikçe önem kazandığından, GT ile Hücresel Üretim Sistemleri (HÜS) ve Just In Time (JIT) arasındaki bağıntıdan bahsedilmiştir. Daha sonra GT’nin tarihsel gelişimi, GT’nin avantaj ve dezavantajları anlatılmış, ardından GT’nin uygulama aşamaları verilmiştir. GT’deki kümelendirme algoritmalarından ve kullanılan kümelendirme yöntemlerinden bahsedildikten sonra, kümelendirme modelleme yaklaşımı, ve benzerlik katsayısı bazlı algoritmalar matematiksel modelleriyle birlikte verilmiştir. GT ile ilgili verilen diğer bir veri benzerlik katsayısı bazlı algoritma’nın tablo halinde gösterimidir. İkinci bölümde tezde kullanılan malzeme, yöntem, algoritmalar, yöntemler ve bilgisayar programlama dillerinden bahsedilmiştir. İlk olarak tezde ele alınan pmedian probleminin matematiksel modeli ve problemi çözmek için kullanılan yöntemler verilmiştir. Bu yöntemler birer sezgisel yöntem olan ve köşe-değiştirme yöntemleri olarak adlandırılabilen OVS (Orijinal Köşe Değişimi, Original Vertex Substitution - OVS), OVS’nin aksine çözüm kümesini daha dar inceleyen ve ayarlanmış olarak ilerleyen AVS (Ayarlanmış Köşe Değişimi, Adjusted Vertex Substitution - AVS) ve başlangıç noktası çok olan AVS-M (Çoklu Başlangıç Noktaları İle Ayarlanmış Köşe Değişimi, Adjusted Vertex Substitution Method 1 Starting Points AVS-M) yöntemleridir. Aynı bölümde, Genetik Algoritma (GA) yönteminden de bahsedilmiştir. Burada GA’ya genel bir giriş yaptıktan sonra, GA’nın tarihçesinden bahsedilmiş, GA’nın nasıl çalıştığı ve aşamaları anlatılmıştır. Ardından GA terimleri, kodlama türleri, GA’nın diğer yöntemlerden farkları, faydaları ve GA araçları konusunda açıklamalar yapılmıştır. GA’nın kullanım alanları, (genel, işletmelerdeki ve üretimler konusundaki) uygulanma alanları ve bu alanlarda GA’nın çözümünde kullanıldığı problemler verilmiştir. Üçüncü bölümde anlatılan sezgisel yöntemlerin algoritmaları verilmiştir. AVS ve GA ile literatürde varolan problemler, örnek olarak çözülmüştür. Ardından İstanbul’da tekstil sektöründe faaliyet gösteren orta ölçekli bir şirkete ait veriler ile bir uygulama gerçekleştirilmiştir. Bu problemlerde başlangıç verisi olarak çeşitli büyüklüklerdeki makine - ürün matrisleri kullanılmış ve bu makine - ürün matrislerine uygun olacak şekilde kümelendirmeler yapılmıştır. Makine - ürün matrisindeki ilişkiler kullanılarak makine - makine matrisleri oluşturulduktan sonra, makinelerin hangi öbeklere ait oldukları tespit edilmiştir. Ürünlerin en çok işlem gördüğü makineler gözönünde bulundurularak ürünler de makine öbeklerine atanmıştır. Bu şekilde makinelerin ve ürünlerin hangi öbeklere dahil olduğunu gösteren kümelendirme tabloları elde edilmiştir. Elde edilen çözümlerde literatürde geçen bir verimlilik ölçütü kullanılarak değerlendirilmeler yapılmıştır. Problemler çözülürken MATLAB simulasyon programı ve MS Office – Excel üzerinde VB Script dili kullanılmıştır. Sonuç bölümünde ise problemlere ait çözümler ele alınarak elde edilen sonuçlar, incelenen yöntemler açısından değerlendirilmiştir. Burada elde edilen sonuçlar şu şekildedir : OVS yöntemi, kümelendirme yapabilmek için olası tüm durumları inceler ve 2 ancak tüm durumları inceledikten sonra karar verebilir. Bu durum zaman, emek ve para kaybına yol açabilir. Bu sebeple daha az durum inceleyerek en iyi çözüm elde etmeye yakın olan farklı algoritmalar kullanılmıştır. Bunlardan biri AVS yöntemidir. Adım sayısını azaltma gibi bir avantajının yanında çözümün lokal kalması gibi bir dezavantajı vardır. Bunu giderebilmek için farklı pek çok başlangıç noktası alınarak devam edilir. Bu yönteme de AVS-M denir. En iyi çözüme daha hızlı yaklaşabilmek için benzer şekilde Genetik Algoritma (GA) yönteminden de yararlanılmıştır. GA kullanılırken farklı parametrelerden en iyi çözümü verecek parametrelerin kombinasyonunun elde edilmesi için "deney tasarımı" yapılmasına ihtiyaç duyulur. EKLER bölümünde öbekleme problemlerinin çözümünde kullanılan VBScript - Excel makro kodları ve GA örneğine ait olan MATLAB programı kodları bulunmaktadır. 3 1 GRUP TEKNOLOJİSİ 1.1 GRUP TEKNOLOJİSİNE GİRİŞ Grup Teknolojisi (GT), en genel tanımıyla işletmelerin verimliliğinin arttırılmasını amaçlayan, bu amaçla işletmelerde üretilen ürünlerin tasarlanması ve ürünlerin kendi içlerindeki benzer yönlerinden yararlanarak bu ürünleri gruplandıran bir üretim tekniğidir 1. İşletmelerin GT'ye başvurmasındaki temel amaç, verimliliğin arttırılması, üretilen ürünlerin, talebi karşılayabilecek seviyede sayı ve kaliteye sahip olmasıdır. Her işletme, diğer işletmelerle girdiği rekabet ortamında kendisini ürünleri, tesisleri, kullandıkları malzeme, araç, gereç vb açısından öne geçirmeye çabalamaktadır. Bu çaba maddi getirinin yanında işletmenin sürekliliği için de gereklidir. Bu esnada gelişen teknolojiden yararlanılarak pek çok yeni teknikler geliştirilmiştir. GT de bunlardan biridir. GT'nin mantığı, üretilen benzer ürünlerin kendi içlerinde gruplandırılmasıdır . Bu gruplandırmada amaç, birbirlerinden ayrı, bağımsız ve kendi içlerinde kontrol mekanizmaları olan ürün grupları oluşturmaktır. Bu tarz bir gruplandırma yapılmasının sebebi de günümüzde işletmelerin oldukça fazla sayıda ürün üretmesi ve dolayısıyla atölye tipi üretimin artması ve ürüne göre düzenlenmenin oldukça zorlaşmasıdır. Tek tek her ürüne göre düzenleme yapılamadığından gruplandırma ve düzenlemeler oldukça önem kazanmıştır. gruplandırmaya göre yapılacak olan 2 Atölye tipindeki üretimin özelliği, üretimin genelde az sayıda ürün içeren küçük partiler halinde olmasıdır. Ancak bu üretim tipinde üretilen ürün oldukça çoktur. Bir atölyenin çok farklı dallarda üretim yapamayacağı gözönünde 1 Nancy Lea Hyer, Urban Wemmerlov, Capabilities of group technology, 1987. s.3 2 C.C. Gallagher and W.A. Knight. Gallagher, C. C., Group technology production methods in manufacture,1986. s.15. 4 bulundurulursa ürettiği ürün çok çeşitli olsa bile benzer özellikler taşıması kaçınılmazdır. Bu benzerlikler tasarım benzerlikleri ya da üretim benzerlikleri olabilir. Tasarım özelliklerinden kastedilen ürünün sahip olduğu dış özellikler, geometrik şekli vs, üretim özellikleri ise üretilmesi esnasında kullanılan malzeme çeşitleri, miktarları, üretilmesi için yapılan işlemler, işlemlerin sırası vb'dir. Bu benzer özelliklere sahip gruplar gözle muayene veya kodlama sınıflandırma sistemleri ile belirlenebilir. GT kullanılarak yapılan üretim, ürünleri gruplandırarak, tasarım, planlama ve üretim faaliyetlerini ürünler arasında var olan bu benzerliklere göre gerçekleştirir, bu sayede de zaman, emek ve maliyet açısından tasarruf yapılmasını sağlar. Ayrıca da sistemlerin üretim kısmındaki karmaşıklığını azaltarak, anlaşılır ve daha kolay implemente edilebilir bir sistemde çalışılmasını sağlar. GT oldukça fonksiyonel bir sistemdir ve bu özelliği sayesinde ürüne göre düzenleme yapan pek çok sistemdeki eksiklikleri ortadan kaldırmıştır. Günümüzde işletmelerin imalat konusunda gerçekleştirdiği veya gerçekleştirmeyi planladığı pek çok değişiklik GT kullanılmasını neredeyse kaçınılmaz hale getirmiştir. Bunlar : • Malzeme çeşidinin artması • Çalışan kişi, makine sayısında ve üretim zamanında ihtiyaç duyulan artış • İmalatın daha az kaynak kullanarak gerçekleştirilmesi ihtiyacı • Hassasiyeti daha fazla olan ekonomik vasıta ihtiyacı • Müşteri ihtiyacının çeşitlenmesi • Talep ve ürün çeşitliliğinin artması sonucu daha karışık bir sistem yapısının oluşması • Oluşan kompleks yapının mümkün olduğunca basite indirgenerek daha rahat çalışma imkanının sağlanması ihtiyacıdır. 5 İşletmeler en genel anlamda bir sistem olarak düşünüldüğünde üretim sistemi kısmı, bu ana sistemin bir alt sistemi olarak ifade edilebilir. Temelde beş tür üretim sistemi mevcuttur. Bunlar : • Atölye tipi üretim • Akış tipi üretim • Proje tipi üretim • Sürekli üretim • Hücresel üretim sistemi (HÜS)’dir. Bu üretim sistemlerinde, üretkenliğin ve verimliliğin artmasına yönelik çalışmalar gerçekleştirilmektedir. Günümüz koşullarında işletmelerin ürettikleri ürünlerin, gösterdikleri hizmetlerin, potansiyel alıcıların talep ve gereksinimlerinin farklılaşması, atölye tipi (kesikli) üretim sistemine karşı eğilimin artmasına neden olmuştur. Bu anlamda HÜS, önemli bir üretim tekniği olarak bu teknikler arasından öne çıkmaktadır. Çünkü HÜS, en genel anlamda, Grup Teknolojisi’nin atölye ortamına uygulanması olarak tanımlanabilir. HÜS’ün elde edilmesine yönelik literatürde pek çok teknik bulunmaktadır. Örneğin makine kapasiteleri ve müşterilerin ürünü, verimli bir HÜS düzeninin elde edilmesinde etkili, önemli faktörlerden bazılarıdır 3. GT ve HÜS, Tam Zamanında Üretim (TZÜ- Just In Time - JIT) felsefesi ile uyumludur ve GT yöntem biliminin tam sonuç verebilmesi için TZÜ ile uygulanması gerekmektedir. 3 Mustafa ÇELİK,Küreselleşme Hareketleri İçinde İşyeri Düzenlemesi ve Bir Matematiksel Model, Dokuz Eylül Üniversitesi Sosyal Bilimler Enstitüsü Ekonometri Aanabilim Dalı Doktora Tezi, 1999. s. 4. 6 Son zamanlarda ortaya çıkan ve Japon sistemi olarak adlandırılan Tam Zamanında Üretim (TZÜ) – Just In Time (JIT) üretim sistemi, işlemin her aşamasında bir önceki iş tamamlandığı sırada bir sonraki iş gelecek şekilde, hem üretim süresince malların hareketinin hem de tedarikçilerin teslimatlarının dikkatli bir şekilde zamanlamasının yapılması anlamına gelen bir üretim çeşididir. Diğer bir deyişle JIT, tam zamanında satın alma ve üretim gerektiren bir maliyet ve stok kontrol sistemidir 4. JIT üretim sisteminin temelini teşkil eden GT bu üretim sisteminden, üretimde stok kontrolü yerine akış kontrolü sağladığı için ayrılmakta ve bu yolla üretimin verimliliği ve kontrolünü daha etkin kılacak ilkelerin uygulanmasını sağlamaktadır. 1.2 GRUP TEKNOLOJİSİNİN TARİHSEL GELİŞİMİ GT, ismi GT olarak ifade edilmese de uzun zamandır kullanılmakta olan bir kavramdır. Bilinen ilk uygulamalarından biri Taylor tarafından yapılmıştır. Taylor, ürünlerin değil ama yapılan işlerin birbirirleriyle benzer özellikler taşıyabileceğini, dolayısıyla da bu işleri benzerliklerine göre sınıflandırabileceğini ve bu sınıflandırmalar sonucunda daha verimli bir çalışmanın sözkonusu olabileceğini farketti. GT konusundaki bazı ciddi çalışmalar 1960'lı yıllarda Batı Almanya ve Büyük Britanya tarafından yapılmıştır. GT konusunda Almanya ve Britanya'nın öncülük ettiği çalışmalardan sonra Avrupa'nın geri kalanında da çeşitli çalışmalar yapıldı.GT ardından Sovyetler Birliği'nde uygulandı. Uygulamanın oldukça başarılı olması sonucunda GT, 4 Azzem ÖZKAN,Murat ESMERAY, Bir Maliyet Kontrol Sistemi Olarak JIT Üretim Sistemi ve Muhasebe Uygulamaları, C.Ü. İktisadi ve İdari Bilimler Dergisi, Cilt 3, Sayı 1, 2002. s. 129. 7 Sovyetler Birliği'nin üretim endüstrisinde oldukça yaygın olarak kullanılmaya başlandı. 1.3 GRUP TEKNOLOJİSİNİN AVANTAJLARI 1.3.1 İŞ AKIŞLARINA ETKİSİ GT, ürünlerin gruplanması temelli olduğundan sistemleri karmaşıklıktan uzaklaştırır, üretimin miktarında, sırasında kolay kontrol ve planlama yapılmasını, ayrıca makineler arasında gidip gelen işlerin akışının da kolaylaşmasını sağlar 5. 1.3.2 TAŞIMA MİKTARLARINA ETKİSİ GT kullanıldığında makineler gruplanacak ve bu makine grupları, üretilen ürünlerin, üretim sırasında geçtiği hat içerisindeki hareketlere göre düzenlenecektir. Bu sayede bir noktadan diğer noktaya taşınan ürün miktarı azalacak ve ürünlerin taşındığı mesafe de kısalacaktır. Bunun dolaylı olarak etkisi taşınan ürünün ve taşıma mesafesinin azalması sonucunda taşıma için yapılan masrafın, zamanın ve emeğin de azalmasıdır. 1.3.3 Üretim İçi Stoklarına Etkisi GT'nin basitleştirdiği üretim sistemleri ve iş akışları sayesinde makineler önünde işlenmek için bekleyen ürün azalacaktır. Bir ürünün bekleme kuyruğunda geçireceği süre az olacağından üretim içi stoklar da azalır. Üretim içerisindeki stokların azalması, üretim yapan işletmenin stok için ayıracağı sermaye maliyetinin de azalması anlamına gelir. 5 A. Sütçü, E. Tanrıtanır, A. Eroğlu, H. İbrahim Koruca, Orman Ürünleri Endsütrisinde Benzetim Destekli Çalışmalar ve Bir Örnek Uygulama, Süleyman Demirel Üniversitesi Orman Fakültesi Dergisi, Seri : A, Sayı : 2, Yıl : 2006, ISSN : 1302-7085, s. 145. 8 1.3.4 Toplam Üretim Zamanına Etkisi İşlerin basitleşmesi, makinelerin ayarlanma süresinin azalması, üretim içi stok miktarının ve kuyrukta bekleme süresinin, taşıma süresinin azalması sonucunda herhangi bir ürünün toplam üretim zamanında kayda değer bir azalma sözkonusu olacaktır. Bu da üretim yapılan birim ve daha genel düşünülecek olursa üretim yapan işletmenin daha fazla üretim yapmasına olanak sağlayacak ve dolayısıyla işletmenin üretkenliğinin ve üretim verimliliğinin artmasına vesile olacaktır. 1.3.5 Makine Hazırlık Zamanına Etkisi Ürünlerin benzer şekilde gruplandırması sonucunda, bu ürünlerin üretilmesi için kullanılan araç, gereç ve makineler bir ürünün üretiminden diğerine geçerken kısa bir hazırlık süresi geçireceklerdir. Bu ürünler benzerliklerine göre gruplandırılmamış olsaydı, makinelerin aralarında az benzerlik olan veya hiç olmayan ürünler arasındaki geçişi oldukça uzun zaman alabilirdi. 1.3.6 Üretim Kalitesine Etkisi Benzerliklerine göre gruplandırılmış ürünler, adım adım üretime girdiğinden varolan herhangi bir hata varsa, hata anında görünerek düzeltilir ve üretim kalitesi de bu şekilde artmış olur. 1.3.7 ÜPK (Üretim Planlama Kontrol) Faaliyetlerine Etkisi Gruplandırma ÜPK faaliyetlerinde de oldukça işe yarayan bir faaliyettir. Gruplandırma sayesinde sorumluluğun merkezî olması yerine bölünmesi sözkonusudur. Sorumluluk miktarının ve alanının azalması üretimin, planlamanın ve kontrolün daha kolay bir şekilde yapılmasını sağlayacaktır. 1.3.8 İş Görene Etkisi GT yaklaşımının temelindeki noktalardan biri işletmelerde iş gören 9 pozisyonundaki kişilerin güdülenmesidir. GT, iş görenlere kendi dallarında daha fazla sorumluluk verildiğinde daha başarılı olduklarını kabul eder.İş gücünün gerçekleştirdiği fonksiyonda uzmanlaşmasını kolaylaştırır. Yapılan gruplandırma sonucunda bir iş görenin kendine daha uygun bir alanda sorumluluk sahibi olması ihtimali artacağından tatmin olma ihtimali de yükselir 1.3.9 Fabrika Kullanım Alanına Etkisi İşletmelerde taşıma mesafesinin en aza inebilmesi için makineler ve araç gereçler arasındaki mesafe en az olmalı, diğer bir deyişle bu teçhizatlar birbirlerine yakın konumlandırılmalıdır. Bu sayede bu teçhizatın fabrika içerisinde işgal ettiği toplam alan azalırken, diğer ekipmanlara bıraktıkları toplam alan artar. 1.3.10Veri Bankasına Etkisi GT, benzer işlemleri bir arada yapar. Buradaki amaç, bağımsız işler arasındaki geçişlerde mümkün olduğunca az zaman kaybetmektir. Bu açıdan birbirleri ile yakın ilişkili, benzerlik oranı yüksek faaliyetleri standartlaştırmak, faaliyet bilgilerini saklamak ve belli bir kalıba oturtulan bu işlemleri gerçekleştirmek için yapılan tekrarları önlemek gerekmektedir. İşlemlerin bilgilerininsaklanması sayesinde bir veri bankası oluşturulur. Bu banka gerektiğinde, daha önceden çözülmüş bir problemi yeniden çözüp vakit kaybetmeyi engeller. 1.3.11 Tasarıma Etkisi GT basit uygulamalarda rahatlıkla kullanılmakta iken, üretim endüstrisinde Bilgisayar Destekli Tasarım (BDT – Computer Aided Design CAD) ve Bilgisayar Destekli Üretim (BDÜ - Computer Aided Manufacturing CAM) sistemlerinin gelişmesi GT'nin daha karmaşık yapılarda da kullanılabilmesini sağlamıştır 6. 6 M. Kaan Doğan, İstanbul Üniversitesi Mühendislik Fakültesi Makine Mühendisliği Bölümü Bitirme Ödevi , “ Optimum İmalat Programının Bilgisayar Benzeşimi”, 02.06.2000. s.13. 10 BDT ve BDÜ kullanılarak hem tasarım işlemi daha kısa zamanda gerçekleşir hem de tasarım tekrarları engellenmiş olur. 1.3.12Maliyet Tahminlerinde Kullanılabilirlik Müşteriye fiyat vermesi gereken ve bu amaçla da ürünlerinin ortalama maliyetini hesaplaması gereken bir işletme, bu amaçla daha önceden oluşturulmuş GT veri bankasında araştırma yapabilir. 1.3.13Sayısal Kontrollü Makinelerde Kullanılabilirlik GT yöntemi sayısal kontrollü makinelerde zaman ve maliyet azaltıcı yönde kullanılabilir. 1.4 GRUP TEKNOLOJİSİNİN DEZAVANTAJLARI 1) Üretilen ürünlerin taşınmaması için bazı üretim araçlarından birden fazla sayıda bulundurulması gerekebilir. Bu durum atölye üretim tarzına göre daha fazla yatırım gerektirir ve kapasite kullanım oranının düşmesine neden olabilir 7. 2) İşletmenin ürün üretimi sırasında, tüm ürünlerin imalat hücrelerinde üretilmesi söz konusu olmayabilir. Böyle bir durumda, hücrelerin oluşturulmasından sonra üretilen diğer ürünler için verimliliğin düşmesi sözkonusudur. 3) GT yöntemini kullanan bir işletmede, ustabaşının değişik özelliklere sahip makineler hakkında bilgi sahibi olması ve çeşitli ürünleri üretme amacı güden iş görenlere görev dağılımı yapabilmesi gerekecektir. Diğer bir deyişle, ustabaşının GT kullanılmayan kesikli sistemlerde olduğu gibi, sadece kendi bölümüyle igili bilgi sahibi olması yeterli olmayacaktır. 4) Tezgahların toplam kullanım sürelerini azalır. 5) Tasarım ve üretim kısımları arasındaki iletişim zayıfsa, GT uygulanması sırasında yapılması gereken kodlama ve gerçekleştirilmesinde zorluklarla karşılaşılabilir. 7 Gallagher, Knight a.g.e. s.16. 11 sınıflandırma işlemlerinin 6) Herkes tarafından kabul edilmiş GT standartları yoktur. Herkesin GT uygulama şekli farklıdır. Bir işletmede benzerlikleri yeterli olarak görülüp aynı gruba alınan 2 ürün, diğer bir işletmede yeterince benzer olmadıkları düşünülüp farklı gruplara atanabilir. 7) Tezgahların gruplandırılması sonucunda, gruptaki bazı tezgahlar daha az kullanılır. Bu işlem sonucunda toplam maliyet azalsa bile, bu durum işletmeler tarafından genelde kabul görmez. 8) GT'nin uygulanabilmesi için kimi zamanbazı tezgahların bir kısmının veya tamamnın yeniden düzenlenmesi, organize edilmesi gerekebilir. Bu da ekstra masraf anlamına gelir. 9) GT yönteminin uygulanması, çalışanların o ana kadar çalıştıkları sistemin değişmesi anlamına gelir ki alıştığı şekli değiştirmek istemeyen çalışanlar tarafından bu konuda itiraz gelmesi oldukça muhtemeledir. 10) İşletmelerde GT uygulamak isteyen birimden daha üstteki birimden destek gelmezse, GT yönteminin uygulanması oldukça zor olabilir. 1.5 GRUP TEKNOLOJİSİNİN UYGULAMA AŞAMALARI 1. Adım : (GT Yönteminin Sözkonusu Sisteme Uygulanıp Uygulanamayacağının Belirlenmesi) Ürünlerin üretim sıraları ve tasarımları incelenir. Benzerlikler miktarlarına bakılır. Benzerlik miktarları ürün aileleri oluşturulup oluşturulamayacağını belirler. Ürünler çok farklıysa gruplamaya uygun değildir ve GT yöntemi uygulanamaz, işlem sonlandırılır; ürünlerde benzerlikler sözkonusu ise GT uygulanabilme ihtimali vardır ve adım 2’ye geçilir. 2. Adım : (GT’de Kullanılacak Gruplama Yönteminin Seçimi) GT’nin uygulanabilmesinin temelinde gruplama olduğu daha önceden belirtilmişti. Bu gruplamanın nasıl yapılacağı üretim yapan sistemin özelliklerine ve ürün grupları oluşturulma ölçütlerine bağlıdır. Bu adımda sisteme uygun bir gruplama yöntemi seçilir ya da gerek görülürse yeni bir gruplama yöntemi geliştirilir. 3. Adım : (Ürün Gruplarının Oluşturulması) 2. adımda gruplama yöntemi belirlendikten sonra belirlenen bu yönteme göre 12 ürünlerin tasarım ve üretim bilgileri toplanır, benzerlikleri (geometrik şekil, boyutlar, malzeme, işlem sırası, teknik özellikler) belirlenir ve bu sayede ürün grupları (aileleri) oluşturulur. 4. Adım : (Makine Hücrelerinin Oluşturulması) 3. adımda ürün aileleri oluşturulduktan sonra bu adımda bu ailelerin işlem sırası belirlenir. İşlem sırası belirlendikten sonra, bu sıraya göre, her ürün ailesindeki ürünleri işleyecek makineler belirlenir. Bu makinelerin bir araya gelmesi ile ”makine hücresi” adı verilen yapılar oluşturulur 8. 5. Adım : (Makine Araç ve Gerecin Yerleşiminin Yapılması) 4. aşamada oluşturulan makine hücreleri için gerekli teçhizat, araç, gereç ve işgören sayısı belirlenir. Belirlenen işgörenler,makine ve araç, gereçler uygun hücrelere atanır. 1.6 GRUP TEKNOLOJİSİNDE KÜMELENDİRME ALGORİTMALARI GT yönteminin gerçekleştirildiği uygulamalarda, uygulamaya bağlı olarak pek çok farklı kümelendirme yöntemi kullanılabilmektedir. • İkili kümelendirme Yöntemi • Müşteri Gruplaması 9 • Veri Madenciliği • Veri Modellemesi 1.6.1 1.6.1 Kümelendirmede Modelleme Yaklaşımı GT yöntemindeki kümeleme modelleme yaklaşımı şu şekilde verilebilir : 8 M. Akif Altunay, Yüksek Lisans Tezi, “Çağdaş Maliyetleme Sistemlerinden Faaliyet Tabanlı Maliyetleme Sistemi ve Bir Tekstil İşletmesindeki Uygulaması”, Süleyman Demirel Üniversitesi Sosyal Bilimler Enstitüsü İşletme Ana Bilim Dalı. s.4. 9 Emin GÜLLÜ, Yusuf ULCAY, Kalite Fonksiyonu Yayılımı ve Bir Uygulama, Uludağ Üniversitesi,Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 7, Sayı 1, 2002. s.74. 13 ve makineleri arasındaki değer Hücrelerdeki gruplama makineleri için 0-1 tamsayı modeli şu formülle ifade edilebilir : 14 1.6.2 Kümelendirmede Sezgisel Yaklaşımlar Kümelendirme problemi, matematiksel model yapısına bakıldığında, temel olarak çözümü NP (non-polynomial) yapıda olan bir problem tipidir. NP olmasının anlamı, küçük olmayan değişken kümelerinde işlem zamanının uzun sürmesi hatta en iyi çözümü bulmanın her zaman mümkün olamamasıdır. Bu nedenle literatürde kümelendirme probleminin çözümünü ele alan pek çok sezgisel yöntem önerilmiş ve uygulanmıştır. 1.6.3 Benzerlik Katsayısı Bazlı Algoritmalar Benzerlik katsayısı yönteminin çalışma şekli aşağıdaki gibidir : • Her iki makine arasındaki ürün akışını kullanır. • Bu sayede makineler arasındaki ilişkinin benzerlik değerini ölçer. • Bu ölçü kullanılarak hazırlanan ağaç çizelgesi yardımıyla makine hücrelerini oluşturur. • Ürün ailelerini, makine - ürün matrisini veri olarak alıp, makine hücrelerine atayarak oluşturur. İki makine arasındaki benzerlik katsayısı, her iki makineye en az bir kez uğrayan ürün sayısının, makinelere ayrı ayrı ve her iki makineye de en az uğrayan ürün sayısına oranıdır. Bu oran makineler arasındaki ürün hareketlerini, hangi ürünün hangi makineye ne kadar uğradığını gösteren makine - makine matrisi sayesinde hesaplanmaktadır. Bu matris, bütün ürünlerin makine - işlem sıralarından makineleri ikili gruplar halinde alarak, ilgili satır - sütun ve sütun - satırdaki hücre değerlerine 1 eklenerek elde edilir. Makine - makine matrisi X(I;J) olarak tanımlanırsa, i. makine ile j. makine arasındaki benzerlik katsayısı değeri aşağıdaki formülle hesaplanır : 15 Burada; X(I,J)= i. ve j makineların her ikisine de en az bir kez uğrayan ürünlerin toplam sayısı, X(I,I) = Sadece i. makineye uğrayan (j.makineye uğramayan) ürünlerin toplam sayısı, X(J,J) = Sadece j. makineye uğrayan (i.makineye uğramayan) ürünlerin toplam sayısı, S(I,J) = i. makine ile j. makine arasındaki benzerlik katsayısı olarak tanımlanır. Makine hücrelerinin oluşturulmasında ağaç çizelgesi yöntemi kullanılır. Bu işlemde büyüklüklerine göre sıralanmış benzerlik katsayılarının eşlendiği makineler bir araya getirilir. Benzerlik katsayısı yönteminin en önemli avantajlarından biri, diğer pek çok yöntemde ifade edilmesi mümkün olmayan, aynı ürünün aynı makinede birden fazla işlenmesi durumunun ifade edilebilmesidir. Ancak bu yöntemin bazı yetersizlik yönleri de mevcuttur. Bunlar : • X(J,J) > X(I,I) olması durumunda, elde edilen katsayı oldukça küçük olacağından, bu küçük katsayı sonucunda, aynı hücrede bulunması gereken makineler farklı hücrelerde yer alabilir. • Makine - ürün matrisinde, uygun dağılım göstermeyen istisnaî ürünler bulunabilir. Bu ürünler, ürün ailelerinin ve makine hücrelerinin matris ana köşegeni üzerinde yer almasını engelleyebilir. • Darboğaz oluşan makinelerin matriste ana köşegen üzerine yerleştirilemez ve tam olarak bir makine hücresine atanması olanaksızdır. • Makine - ürün matrisinde aynı tipteki makinelerden yalnız birer adet gösterilmesi mümkündür, daha fazlasının gösterilmesi mümkün değildir. 16 Tablo 1: Benzerlik Katsayısı Bazlı Algoritma Adım 1 Ürünlerin rotalarına bakarak, ürünlerin makine işlem sıralarını belirle. Adım 2 Belirlenen makine - işlem sıraları sayesinde makine – ürün matrisini kur. Adım 3 Makineler arasındaki ürün akışının gösterdiği, makine – makine matrisini oluştur. Adım 4 Her makine çifti için benzerlik katsayısını hesapla. Adım 5 Benzerlik katsayısına göre ağaç çizelgesini ve makine hücrelerini oluştur. Adım 6 Makine – Ürün matrisi sayesinde, makine hücrelerine ürünleri atayarak, ürün ailelerini oluştur. Adım 7 Grupları eşleştir. 17 2 PROBLEM ve YÖNTEM Bu tezde p-median problemi ve p-median probleminin çözüm tekniklerinden bahsedilmiştir. İncelenen yöntemler, Orijinal Köşe Değişimi (Original Vertex Substitution - OVS ) Yöntemi, Ayarlanmış Köşe Değişimi (Adjusted Vertex Substitution - AVS) Yöntemi, Çoklu Başlangıç Noktaları İle Ayarlanmış Köşe Değişimi (Adjusted Vertex Substitution Method Starting Points, AVS-M) Yöntemi ve Genetik Algoritma Yöntemi’dir. Bu yöntemlerin nasıl uygulandıkları, algoritmaları incelenmiş ve örnekler çözülmüştür. Yöntemlerin birbirilerine göre avantaj ve dezavantajları, Sonuçlar ve Öneriler kısmında anlatılmıştır. Bilgisayar programları ise MATLAB ve MS Office EXCEL - Visual Basic makroları ile yazılmıştır. 2.1 -MEDİAN PROBLEMİ p-median kümeleme modeli, en temel tanımıyla bir tesis yerleşim problemidir 10 . (p tane tesisin açılması sözkonusudur). p adet tesisin açılması demek diğer bir deyişle p adet küme oluşturulması demektir. Problemde bir uzaklık matrisi ’nin temelinde, geriye kalan elemanlara ayrılacak olan farklı elemanlar (medianlar) seçilecektir. Bu yüzden adet küme oluşturulur. ‘nin değeri değiştikten sonra prosedür tekrarlanır. Bir küme medianı, kümedeki her eleman için temsil edilebilecek bir elemanı olarak tanımlanır. adet median varken adet de küme oluşturmak isteriz. Burada kümelenmesi gereken ürünlerin sayısı olmak üzere eşitsizliği sözkonusudur. n : müşteri kümesi 10 J. Ashayeri, R. Heuts, B. Tammel, A modified simple heuristic for the p-median problem, with facilities design applications, Robotics and Computer-Integrated Manufacturing 21 (2005). s.452. 18 m : aday tesis kümesi p : kurulacak tesis sayısı : i müşterisinin talebi : i müşterisi ile j aday tesisi arasındaki uzaklık, zaman veya maliyet talebi Karar Değişkenleri Amaç: Talep ağırlıklı toplam uzaklığı minimum hale getirecek şekilde açılacak en uygun p tesisin belirlenmesi p-median matematiksel modeli şu şekildedir : Min i = 1, ....., N i = 1,.....,N j = 1,.....,M i = 1,.....,N j = 1,.....,M 19 j = 1,.....,M 11 12 13 , , Burada, tesis ikili olmayan problemlerde matrisi üzerine kurulmalıdır. Bu tarz -matrisi performans ölçmek için gerekli doğru ölçüm metotlarını sağlar. Bununla birlikte bir depolama veya üretim çevresinde eğer bir kümeleme problemi varsa, matrisi ikilik bir matris üzerine temellenmiş olur. Bir depolama probleminde, ikilik matris, müşteriler tarafından genelde beraber sipariş edilen ürünleri temsil eden bir ürün - sipariş matrisi olur. Burada dikkat edilmesi gereken husus, sıklıkla sipariş verilen ürünleri, birbirine yakın bir şekilde yerleştirmenin önemidir. Bir ürün probleminde ise ikilik matris, ürünlerin aynı kümesini işlemek için kullanılan makineleri göstermektedir. Burada da dikkat edilecek husus makineleri, bir hücrede yakına getirmektir. 2.2 P-MEDİAN PROBLEMİ ÇÖZÜM TEKNİKLERİ -median kümeleme problemini çözebilmek için literatürde pek çok yöntem vardır . Bu tez çalışmasında bir köşe değişimi sezgisel yöntemi ele alınmıştır. 2.3 ORİJİNAL KÖŞE DEĞİŞİMİ (ORİGİNAL VERTEX SUBSTİTUTİON - OVS ) YÖNTEMİ OVS yöntemi, adından da anlaşılabileceği gibi köşelerin yerdeğiştirmesi üzerine kurulmuş bir yöntemdir için ilk olarak 14 . Bu yöntemin nasıl uygulandığını anlatabilmek adet düğümü olan bir ağ yapısının varolduğu varsayılırsa, bu ağ yapısı üzerindeki her - çifti için, minimum uzaklık olan gerekir. Bahsedilen ağ yapısı, bir ’nin hesaplanması graphı ile ifade edilebilir. Graph ile ifade 11 A. Al-khedhairi, Simulated Annealing Metaheuristic Simulated Annealing Metaheuristic for Solving P-Median Problem, Int. J. Contemp. Math. Sciences, Vol. 3, 2008, no. 28, s. 1358. 12 E. Dominguez Merino, J. Munoz Perez and J. Jerez Aragones, Neural Network Algorithms for the p-Median Problem, ESANN'2003 proceedings - European Symposium on Artificial Neural Networks Bruges (Belgium), 23-25 April 2003, d-side publi., ISBN 2-930307-03-X. s.2. 13 Rajeev Kumar, Peter Rockett, Multiobjective Genetic Algorithm Partitioning for Hierarchical Learning of High-Dimensional Pattern Spaces - A-Learning-Follows--Decomposition Strategy, IEEE Transactions On Neural Networks, VolL. 9, No. 5,September 1998. s 824. 14 Ashayeri, Heuts, Tammel, a.g.e. s. 453-454. 20 edebilmek için 1’den ’e kadar olan tüm noktalar numaralandırılır. Bu numaralandırılmış düğümler arasına değerler yerleştirilir ve olur. olan graphının köşe medianı şu şekilde tanımlanır : , tüm - çiftleri için hesaplanan graphının uzaklık matrisi ’nin simetriğidir. boyutunda olur. Buna göre olduğundan, matris graphı oluşturulmuş adet düğüm köşe median’ı, ’nin karşılık gelen hangi kolonlarındaki elemanların toplamı minimum ise, o köşeye ait olacaktır. ’nin adet köşesini içeren bir altkümemiz olduğunu varsayalım. Bu kümeye diyelim. Buna göre de, uzaklık matrisinin eşleşen kolonları tarafından oluşturulmuş tanımlanır. Bir de ’deki köşe sayıları ile boyutundaki matris olarak ’i tanımlanır. Burada amaç, sistemdeki tüm köşelere en yakın olan bir küme bulmaktır. Algoritma şu şekilde çalışır : köşelerini içeren bir başlangıç altkümesi, ( ) seç. 1) 2) Başlangıç değeri olarak ve ata. için olarak ifade edilen bir hedef kümesi, ( ) oluştur. Toplam mesafe ile ifade edilmektedir ve 3) içerisinde bulunmayan köşeleri ( olarak ifade edilir) seç. 4) içerisindeki her köşesi için, ile hesaplanır. olduğunu varsayalım, buna göre ’yi yerdeğiştir. , altmatrisinin minimum satırı değilse, bu durumda toplam 21 mesafeye göre, satırda bir değişiklik olmayacaktır. , altmatrisinin minimum satırı ise, ile yerdeğişimi aşağıdaki durumlara göre farklı değişikliklere sebep olabilir. ise (a) veya ise (b) ise (c) veya Burada , üzere) ’den ’ye kadar olan mesafeyi göstermektedir. Diğer bir deyişle, için , ve ’deki 2. en küçük için olmak satır elemanıdır. ’in durumu şu anda şu şekildedir : (a) durumunda (b) durumunda (c) durumunda için . ’yi yerdeğiştirmek, toplam uzaklıkta, ancak olması durumunda bir azalmaya sebep olabilir. Buna göre : 5) içerisinde ve şartını sağlayan köşesini bul. 22 6) Herhangi bir köşesi 5. adımdaki şartları sağlıyorsa, altkümede yerdeğiştir, ’yi 1 arttır ve yeni altkümeyi karşılık gelen için olarak etiketlendir. ’yi ’yi ve ’yi hesapla. Hiçbir köşe, 5. adımdaki şartları sağlamıyorsa eski altkümesi ile işleme devam et. 7) Daha önceden denenmemiş ve - altkümesinin tümleyeni olan kümede varolan başka bir köşe seç ve 4-6 adımlarını tekrarla. 8) ’in tümleyenindeki tüm köşeler denendiği zaman sonuç altkümesini olarak tanımla. 2-7 arasındaki adımları tekrarla. Bu adım, bir iterasyon veya bir çevrim tamamlar. 9) Tamamlanmış bir çevrim sonlandır. Bu durumda ve başlangıç değeri ile yeni bir çevrim başlat. ’de bir azaltmaya sebep olmadıysa, o prosedürü artık, ’nin -median köşesinin bir tahminidir. Köşe ağırlıkları uzaklık matrisinin tanımında de şu yollarla bir ayarlamaya ihtiyaç duyar : ayarlanmış uzaklık matrisi =[ ] ‘lik köşegensel bir matristir ve köşegenleri üzerinde köşe ağırlıkları bulunmaktadır. Burada matrisi, öncelikleri belirler. Kümeleme için 2. bir boyuttur. Algoritmada, uzaklık matrisi, ağırlıklı uzaklık matrisi ile yer değişebilir. 23 2.4 AYARLANMIŞ KÖŞE DEĞİŞİMİ (ADJUSTED VERTEX SUBSTİTUTİON - AVS) YÖNTEMİ Bu bölümde, bazı durumlarda OVS yönteminin çözümünün geliştirilebileceğinden yola çıkarak oluşturulan diğer bir algoritmadan (AVS) bahsedilecektir. Bu gelişmenin gerçekleşebilmesi için sözkonusu sezgisel yöntemin (OVS) bazı ayarlamalar yapması gerekmektedir. Bu ayarlamalar yapıldıktan sonra oluşan algoritmaya da AVS adı verilmiştir 15. OVS algoritmasındaki 1-3 arasındaki adımlar değişmeden kalır. Ancak diğer adımlarda değişiklikler sözkonusudur. Adım 4’te üzerinde için ’nin değişim etkisi hesaplanır. OVS anlatılırken, yalnızca ’nin satır minimumu olması halinde mesafe üzerinde ’nin satır etkisinin değişebileceği belirtilmişti. Bu yüzden bu ayarlama yapılan algoritmada ( ’de olmayan) için ( ’deki) ’nin yerdeğiştirme etkisine yeniden bakılması gerekir. Bu ’nin durumda satır minimumunun ’den daha küçükse, OVS algoritmasında, orijinasl yönteme göre sonuçtaki değil , için ’nin yerdeğiştirmesinin satırın mesafeye varsayılmıştır. Bununla birlikte mesafe olduğunu varsayalım. olan katkısını değiştirmediği işlemi ile yanlış bir sonuç üretmiş olur. Algoritmaya yukarıdaki ayarlamayı ekleyebilmek için 4.adım şu şekilde değiştirilir: 4. ’deki her köşesi için ’nin ’de olmayan ’leri yerdeğiştir. ’nin elemanı olup olmadığına veya olup olmadığına karar ver. 15 Ashayeri, Heuts, Tammel, a.g.e. s. 456-457. 24 olmak suretiyle ise (veya, nin (a) eğer ise, (b) eğer ise, ’nin ’nin satır minimumu değilse), 2 adet olasılık vardır. satırın katkısında bir değişiklik yoktur. ’dir. satır minimumu olması durumunda 4. adım değişmez. . AVS algoritmasının geri kalanı, OVS ile aynıdır. Bu durum, OVS ile AVS arasında olacak şekilde şartını sağlayan bir kesin olması durumunda bir fark olacağını göstermektedir. Algoritmaya bakıldığında AVS yönteminin, OVS yönteminin aksine prosedür boyunca bir gelişme gösterebileceği görülür. Bu da bir medianın tam bir yerdeğişimi anlamına gelir. OVS sezgisel yöntemi ise sürekli olarak eski altküme ile işlem yapmaktadır. Bununla beraber, bütün durumlarda AVS yönteminin en azından OVS sezgisel yöntemi kadar iyi olduğu söylenemez. Deneysel bazı durumlarda negatif farklar çıkması mümkündür. Bunun sebebi, OVS yönteminin AVS yönteminden başka median kombinasyonlarını analiz etmesi dolayısıyla daha iyi bir sonuç elde etmesidir. Tüm test durumlarında bu durum az bir değişiklikle birer kez gerçekleşmiştir. 2.5 ÇOKLU BAŞLANGIÇ NOKTALARI İLE AYARLANMIŞ KÖŞE DEĞİŞİMİ (ADJUSTED VERTEX SUBSTİTUTİON METHOD STARTİNG POİNTS AVS-M) YÖNTEMİ AVS yönteminin uygulandığı durumlarda, algoritmadaki ayarlama, çözümün geliştirilmesini amaçlar. Bununla birlikte, AVS yönteminin uygulandığı durumlarda, bazı hesaplamalar yaptıktan sonra çözümün hala bir yerel optimum olduğunu görürüz. Örneğin öbeklemeler ardarda köşelerde değil de ayrı ayrı köşelerde 25 olduğunda çözüm yerel optimumdan global optimuma geçebilir. Bu yüzden pek çok farklı başlangıç altkümeleri kullanmak pek çok durumda problemi çözebilmek için daha doğru bir yol olarak görülebilir. En önemli problemlerden biri başlangıç altkümesinin doğru seçimidir. AVS yönteminde bu durum şu şekildedir : p adet öbekleme için başlangıç altkümesi şeklindedir. Ardından bu durum sezgisel olarak geliştirilir. O ana kadarki en iyi sonuç BEST olarak adlandırılır, ardından bu çözümün diğer bir başlangıç altkümesi ile geliştirilip geliştirilmeyeceğine bakılır. p < m olması durumunda, ilk p köşenin ‘i sağlamayacağı açıktır. Bu yüzden algoritmanın 2. iterasyonunda şeklinde diğer bir başlangıç altkümesi kullanılır. AVS yöntemi bu yeni başlangıç altkümesine yeniden uygulanır. Eğer elde edilen çözüm daha önce en iyi olarak düşünülen BEST çözümünden daha iyiyse, BEST bu yeni çözüm ile modifiye edilir. Eğer daha iyi bir çözüm bulunamadıysa BEST aynı kalır. Bu işlem p + k = m + 1 ‘i sağlayan k sayısı kadar tekrar edilir. Bu yolla , başlangıç altkümeleri sayesinde sağlanmış olur. Bu işlem, AVS yönteminin bulduğundan daha iyi bir çözüm oluşturur. Bu yönteme AVS-M yöntemi denir 16. 2.6 GENETİK ALGORİTMA 2.6.1 Genetik Algoritmaya Giriş Genetik Algoritma (GA), yapay zekanın bir kolu olan evrimsel hesaplama tekniğinin bir parçasıdır. Evrimsel hesaplama tekniği gittikçe genişleyen ve önem kazanan bir yöntem olduğundan paralel olarak GA da gittikçe önem kazanmakatdır. GA, temelde Darwin’in Evrim Teorisi’den esinlenerek oluşturulmuştur 17. Bunun anlamı, herhangi bir problemin GA ile çözümünün, problemi sanal olarak evrimden geçirmek suretiyle yapılmasıdır. 16 Ashayeri, Heuts, Tammel, a.g.e. s. 457. Halil KARAHAN, M. Tamer AYVAZ, Gürhan GÜRARSLAN, Şiddet-Süre-Frekans Bağıntısının Genetik Algoritma ile Belirlenmesi: GAP Örneği, İMO Teknik Dergi, 2008, Yazı 290. s.4395. 17 26 GA, doğada pek çok yerde gözlemlenebilen evrim sürecine benzer bir şekilde çalışan bir arama ve eniyileme yöntemidir. GA’nın evrim sürecine en benzer yanı, doğadaki evrimde en güçlünün hayatta kalması gibi GA’da da en iyinin çözüm olarak alınmasıdır. GA, problemlere tek bir çözüm üretmez. Bunun yerine farklı farklı çözümlerden oluşan bir çözüm kümesi üretir. Bunu yapmasındaki amaç, arama uzayında aynı anda birçok noktanın değerlendirilebilmesi ve sonuç olarak çözüme ulaşma olasılığının artmasıdır. Çözüm kümesindeki çözümler birbirinden tamamen bağımsız, her biri çok boyutlu uzay üzerinde bir vektör olarak kabul edilebilen çözümlerdir. GA, uygulandığı problemlerde çözümü bulmak için evrimsel süreci bilgisayar ortamında simule eder. Problem için oluşan çözüm kümesi GA terminolojisinde nüfus adını alır. Bu nüfuslar bir vektör yapısına sahip olan ve kromozom veya birey adı verilen sayı dizilerinden oluşur. Birey (kromozom) içerisindeki her bir elemana gen adı verilir. Nüfustaki bireyler GA’nın geliştiği evrimsel süreç içerisinde GA işlemcileri tarafından belirlenirler. Problemin bireyler içerisindeki gösterimi GA’nın uygulandığı problemden probleme değişiklik gösterir. GA’nın bir problemin çözümündeki başarısını belirlemedeki en önemli faktör, problemin çözümünü temsil eden bireylerin gösterimidir. Nüfus içerisindeki her bireyin sözkonusu problem için çözüm olup olmayacağına karar vermek ve çözüm için uygun olan bireyleri kullanmak gerekir. GA’da bu uygun olup olmama durumuna karar veren bir uygunluk fonksiyonu mevcuttur 18 . Her değerin ayrı ayrı uygunluk fonksiyonuna parametre olarak girmesinden sonra, fonksiyondan dönen değeri alınır. Bu değerler birbirleri ile kıyaslandığında yüksek olan bireylere, nüfustaki diğer bireyler ile çoğalmaları için fırsat verilir. Bu işlem çaprazlama olarak adlandırılır ve çaprazlama işlemi sonucunda çocuk adı verilen yeni bireyler üretilir. Çocuklar gerçek dünyada olduğu gibi kendisini meydana getiren ebeveynlerin (anne, 18 S. Özgür DEĞERTEKİN, Mehmet ÜLKER, M. Sedat HAYALİOĞLU, Uzay Çelik Çerçevelerin Tabu Arama ve Genetik Algoritma Yöntemleriyle Optimum Tasarımı, İMO Teknik Dergi, 2006. Yazı 259. s. 3924. 27 baba) özelliklerini taşır. Yeni bireyler (çocuklar) üretilirken düşük uygunluk değerine sahip bireyler daha az seçileceğinden bu bireyler bir süre sonra nüfus dışında kalırlar. Dolayısıyla nüfus sürekli olarak yenilenir. Yenilenen nüfus, bir önceki nüfusta yer alan uygunluğu yüksek bireylerin bir araya gelip çoğalmaları sayesinde oluşur. Aynı zamanda bu yeni nüfus, kendisini oluşturan eski nüfusun uygunluk değerleri yüksek olan bireylerin sahip olduğu özelliklerin büyük bir kısmını içerir. Böylece, nesiller geçtikçe iyi özellikler nüfus içersinde yayılırlar ve genetik işlemler (çaprazlama vb) aracılığıyla diğer iyi özelliklerle birleşebilirler. Arama uzayında iyi bir çalışma alanı elde edilmesi uygunluk değeri yüksek olan bireylerin mümkün olduğunca çok sayıda bir araya gelmesine bağlıdır. Uygunluk değeri yüksek olan ne kadar çok birey bir araya gelip, yeni bireyler oluşturursa arama uzayı içerisindeki çalışma alanı o kadar iyi olur. Buna göre GA ile bir probleme ait en iyi çözümün bulunabilmesi için bireylerin gösteriminin doğru bir şekilde yapılması, uygunluk fonksiyonunun verimli olarak kullanılacak şekilde oluşturulması ve yapılacak genetik işlemcilerin doğru seçilmesi gerekmektedir. Doğru işlemler yapıldığında GA kullanılan problemdeki çözüm kümesi problem için tek bir noktada birleşecektir. GA’nın avantajlarından biri, diğer eniyileme yöntemleri kullanılırken büyük zorluklarla karşılaşılan, işlem yapması zor, büyük arama uzayına sahip problemlerin çözümünde başarı göstermesidir. GA yöntemi uygulandığı problemin, en iyi çözümünü bulmayı garanti etmez ancak problemlere makul bir süre içinde, kabul edilebilir, iyi denebilen çözümler bulur. GA’nın asıl amacı, en iyi çözümü bulmak değil, hiçbir çözüm tekniği bulunmayan problemlere çözüm aramaktır. Kendilerine has çözüm teknikleri olan özel problemlerde GA kullanılmaz. Çünkü kendilerine özel teknikleri bulunan problemlerde çözüm için mutlak sonuç zaten bulunuyordur. GA ancak, çözüm arama uzayının çok büyük ve karmaşık olduğu, eldeki mevcut bilgiyle geniş arama uzayında çözümün zor olduğu, problemin belli bir matematiksel modelle ifade edilemediği, geleneksel eniyileme yöntemlerinden istenen sonucun 28 alınmadığı durumlarda etkili ve kullanışlıdır. 2.6.2 Genetik Algoritmanın Tarihçesi Evrimsel hesaplama ilk olarak 1960’larda I.Rechenberg tarafından tanıtılmıştır 19 . Onun fikri daha sonra başka araştırmacıların da ilgisini çekmiş ve geliştirilmiştir. John Holland evrim sürecinin bir bilgisayar yardımıyla kullanılarak, bilgisayara anlayamadığı çözüm yöntemlerinin öğretilebileceğini düşündü 20. Genetik Algoritma (GA) böylece John Holland tarafından bu düşüncenin bir sonucu olarak bulundu 21 . 1992 yılında John Koza GA’yı kullanarak çeşitli görevleri yerine getiren programlar geliştirdi 22. 2.6.3 Genetik Algoritma Tekniği GA ilk olarak popülasyon olarak ifade edilen bir çözüm seti ile başlatılır. Bir popülasyondan alınan sonuçlar yeni bir popülasyon oluşturmak için kullanılır. Bu yeni popülasyonun bir öncekinden daha iyi olması beklenir. Yeni popülasyon oluşturulması için seçilen çözümler en uygun olma şekillerine göre seçilir. İstenen çözüm sağlanıncaya kadar bu işlem devam ettirilir. 19 Michael Affenzeller, Stefan Wagner, Reconsidering the Selection Concept of Genetic Algorithms from a Population Genetics Inspired Point of View, 2001. s. 3. 20 Günay KÖROĞLU, Tayfun GÜNEL, Sürekli Parametreli Genetik Algoritma Yardımı İle Geniş Bantlı ve Çok Katmanlı Radar Soğurucu Malzeme Tasarımı, Havacılık ve Uzay Teknolojileri Dergisi Ocak 2005 Cilt 2 Sayı 1. s.72. 21 Iraj Mahdavi, Mohammad Mahdi Paydar, Maghsud Solimanpur, Armaghan Heidarzade, Genetic algorithm approach for solving a cell formation problem in cellular manufacturing, Elsevier, Expert Systems with Applications 2008. s.2. 22 John R. Koza, Genetic Programming on The Programming of Computers by Means of Natural Selection, 1992. s.17. 29 2.6.4 Genetik Algoritmanın Aşamaları Şekil 1: Genetik Algoritmanın Aşamaları 23,24 Şekil 1’den de görüldüğü üzere GA’nın yapısı oldukça geneldir ve herhangi bir probleme uygulanabilir. 23 Barış Taze, Ankara Üniversitesi Sosyal Bilimler Enstitüsü İşletme Anabilim Dalı, Yüksek Lisans Tezi, “Genetik Algoritmaların Finansal Uygulamaları”. 2004 . s. 10,12. 24 T. CEBESOY, Madencilikte Bilgisayara Dayalı Yapay Zeka Teknikleri Uygulamaları, Türkiye 14.Madencilik Kongresi / 14th Mining Congress of Turkey, 1995 , ISBN 975-395-150-7. s.185. 30 GA’da kromozomların tanımlanması genelde ikilik düzendeki sayılarla yapılır. Çaprazlama işlemi için kullanılan bireyler iyi bireylerden seçilir. GA kullanılarak bir problem çözüldüğünde algoritmanın ne zaman sonlanacağına kullanıcı karar verir. Çünkü GA’nın belli bir sonlanma kriteri yoktur 25 . Problemde sonucun yeterince iyi olması veya istenilen yakınsamanın sağlanması durumunda algoritma durur. 2.6.5 Genetik Algoritma Terimleri 2.6.5.1 Kromozom ve Gen Kromozom: Kromozomlar, GA’daki çözüm kümesindeki çözüm adaylarını gösterirler26. Diğer bir deyişle kromozom, GA’nın çözmesi istenen problemin mümkün olan her çözümünü göstermektedir. Belirlenen bir problem için n tane çözüm olabilir. (n herhangi bir sayı olabilir.) GA’nın bu çözümler arasında en iyisini arayıp bulması istenmektedir. Başlangıçta rastgele olarak atanan çözümler daha sonra GA’nın çalışma prensiplerine göre iyileştirilir. Gen: Doğal sistemlerde, gen, kalıtsal molekülde bulunan ve organizmanın karakterlerinin tayininde rol oynayan kalıtsal birimlerdir. Yapay sistemlerde ise gen, kendi başına anlamlı bilgi taşıyan en küçük birim olarak tanımlanır. GA’da bir kromozomun elemanlarından her birisi çözümün sahip olduğu özelliklerden birini göstermektedir. Özellikleri gösteren bu elemanlar da gen adı ile ifade edilmektedir. Diğer bir deyişle birden fazla gen bir araya gelerek kromozomları oluşturur. 25 Nihat TOSUN, Gül TOSUN, Minimum Yüzey Pürüzlülüğü Koşulu İçin Delme Parametrelerinin, Genetik Algoritma İle Optimizasyonu, F. Ü. Fen ve Mühendislik Bilimleri Dergisi, 16(2), 2004. s. 307. 26 Öznur İşçi, Serdar KORUKOĞLU, Genetik Algoritma Yaklaşımı ve Yöneylem Araştırmasında Bir Uygulama, Celal Bayar Üniversitesi .İ İ.B.F., YÖNETİM VE EKONOMİ l:2003 Cilt:10 Sayı :2. s. 194. 31 2.6.5.2 Popülasyon GA’da kromozomlardan oluşan topluluğa popülasyon denir. Diğer bir deyişle popülasyon, GA problemindeki geçerli alternatif çözüm kümesidir. Popülasyondaki birey sayısı (kromozom) genelde değişken değildir. GA’da popülasyondaki birey sayısı ile ilgili genel bir kural yoktur. Popülasyondaki kromozom miktarı arttıkça çözüme ulaşma süresi (çözüme iterasyon sayısı) azalır. 2.6.5.3 Çözüm Havuzu Çözüm havuzu, problemin en iyi çözümünü aramak için kullanılan ve başlangıçta rastgele olarak belirlenmiş çözüm setidir 27. GA’nın kullanıldığı problemin yapısına ve içeriğine göre değişen sayıda başlangıç çözümü belirlenebilir. Çözüm havuzunun diğer bir ismi başlangıç popülasyonudur. Bu ham popülasyon, GA operatörleri kullanılmadan oluşturulmuş tek popülasyondur. Bu şekilde bir seçim yapılmasının sebebi GA’da tamamen tesadüfî olarak seçilmiş olan bir popülasyonla çözüme başlamanın en iyi yol olduğunun düşünülmesidir. Başlangıç popülasyonu gelişigüzel üretildiğinden, her zaman çözüme ulaşılamayabilir. Bazen yerel çözümde kalınabildiği gibi çözümden uzaklaşma durumu ile de karşılaşılabilir. 2.6.5.4 Seçim GA’da seçim, uygunluk değeri temel alınarak, uygunluk değeri popülasyonun uygunluk değerinden düşük olan bireylerin elenmesi ve yerlerine uygunluk değerleri yüksek bireylerin kopyalarının konmasıdır 28 . Buna göre “hangi bireyin sonraki topluluğa taşınacağını uygunluk değeri belirler.“ denebilir. 27 Cevdet GÖLOĞLU, Yenal ARSLAN, Genetik Programlama İle İmalat İçin, Yüzey Pürüzlülük Modeli Geliştirilmesi, Gazi Üniv. Müh. Mim. Fak. Der., Cilt 21, No 4, 2006. s. 668. 28 Sarper GÖZÜTOK, Osman N. ÖZDEMİR, Genetik Algoritma Yöntemi İle Su Şebekelerinde Hidrolik Kalibrasyonun Geliştirilmesi, Gazi Üniv. Müh. Mim. Fak. Der. Cilt 19, No 2, 125-130, 2004. s.126. 32 2.6.5.5 Çaprazlama Çaprazlama, biyolojik terim olarak üreme kromozomlarının birbirleriyle yapmış oldukları gen alışverişidir. GA’da çaprazlama, problem çözüm havuzunda bulunan çözümleri (kromozomları) ikişer ikişer birleştirerek bu çözümlerin özelliklerini taşıyan yeni çözümler meydana getirmektir. GA’da seçim sonrasında kromozomlar ikili olarak seçilir ve rasgele belirlenen bir noktanın sağ tarafındaki genler karşılıklı olarak değiştirilir bu sayede çaprazlama işlemi gerçekleştirilmiş olur. İki kromozomdan her ikisi de eski iki kromozomun özelliklerini taşıyan iki adet yeni kromozom üretilir. Bir problemin çözüm uzayında kaç adet çaprazlama yapılacağı diğer bir deyişle kaç kromozomun çaprazlanacağı önceden belirlenen çaprazlama oranına göre belirlenir. Çaprazlama, GA’nın performansını oldukça fazla etkileyen temel operatörlerden biridir29. Çaprazlama, iki bireyin özelliklerinin birleşmesini sağlar 30 . Burada temel amaç, uygunluk değeri yüksek olan iki bireyin iyi özelliklerini birleştirerek daha iyi özelliklere sahip olan bireyler (sonuçlar) elde etmektir. Fakat hangi özelliklerin daha iyi performans sağladığı tam olarak bilinemediğinden özelliklerin değiş tokuşu rassal olarak gerçekleştirilir. Bu şekilde rassal olarak yapılan birleşimler ile iyi bireylerin oluşması, çözümün iyi olması beklenir. Bu durumda her zaman en iyi özelliklerin bir bireyde toplanmasının mümkün olmadığı açıkça görülmektedir.Çaprazlama sonucunda bazen en kötü özellikler bir çocukta toplanabilir. Bu durumda bu çocuk çözüm kümesinden atılacak yani elenecektir. 29 Timur KESKİNTÜRK, Diferansiyel Gelişim Algoritması, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi Yıl: 5 Sayı: 9 Bahar 2006/1. s.87. 30 Mahdavi, Paydar, Solimanpur, Heidarzade, a.g.e. s.4. 33 2.6.5.6 Mutasyon Mutasyon kelimesinin geçek anlamı, organizmalarda radyasyon veya başka sebeplerle değişiklik meydana gelmesidir. Bazen çaprazlama yapıldıktan sonra bile farklı çözümlere ulaşmazk zor olabilmektedir. Mutasyon, yeni çözümler aramak amacı ile bir kromozomun bir elemanının (gen) değiştirilmesi işlemidir 31 . Bir problemin çözüm havuzunda kaç kromozomun mutasyona uğratılacağına önceden belirlenen mutasyon oranına göre karar verilmektedir. Algoritmanın işleyişine göre mutasyon oranı değiştirilebilir 32 . Mutasyon yapılacak noktaların belli özellikleri yoktur. Diğer bir deyişle, mutasyon kromozomlarda tesadüfî olarak belirlenen noktalarda yapılan değişikliktir 33. 2.6.5.7 Uygunluk Fonksiyonu GA’da tek bir çözümün değil, bir çözüm kümesinin varolduğu, çözüm kümesindeki elemanların sonuca ne kadar uygun olduğunun uygunluk fonksiyonu adı verilen bir fonksiyon tarafından belirlendiği 34 daha önceden belirtilmişti. Her problem için bir uygunluk fonksiyonun belirlenmelidir. Uygunluk fonksiyonu GA’da probleme özgü çalışan tek kısımdır. Bu fonksiyon, problemin yapısına ve içeriğine göre değişir. 2.6.5.8 Yeniden Üretim Çözüm havuzundaki kromozomların sayısı, çaprazlama ve mutasyon sonucunda oluşturulan yeni kromozomlar sebebi ile artacaktır. Problemin çözüm havuzunun büyüklüğüne göre kromozomların bazıları seçilerek geri kalanlar atılır. Seçilen 31 B. Altunkaynak, A. Esin, “The Genetic Algorithm Method For Parameter Estimation in Nonlinear Regression”, G.Ü. Fen Bilimleri Dergisi 17 (2) . (2004) ISSN 1303 – 9709. s. 48. 32 Bilal ALATAŞ, Ahmet ARSLAN, Birliktelik Kurallarının Madenciliği İçin Genetik Algoritma ve Bulanık Küme Tabanlı Yeni Bir Yaklaşım, F. Ü. Fen ve Mühendislik Bilimleri Dergisi, 17 (1), 2005. s.47. 33 İbrahim GÜNGÖR, Ecir Uğur KÜÇÜKSİLLE, Küme Bölme Problemlerinin Genetik Algoritmayla Optimizasyonu: Türkiye İkinci Futbol Ligi Uygulaması, Review of Social, Economic & Business Studies, Vol.5/6, s. 388. 34 Ö. Türkodlu, “Genetik Algoritma Metodu İle Düzlemsel Yakın Alan Elde Etmek İçin Uygunluk Fonksiyonu Analizi”, Istanbul University Engineering Faculty Journal of Electrical & Electronics, Year :2001, Volume:1, Number :2, s. 262. 34 kromozomlar, yeniden çaprazlanıp sonraki nesiller için çözümleri 35 üretirler . Yeniden üretim için literatürde değişik yöntemler vardır. 2.6.5.9 Rulet Tekeri Rulet tekeri, bir önceki maddede anlatılan ve literatürde yeniden üretim için varolan bu yöntemlerden biridir 36. Yaygın olarak kullanılır. Bu yöntemde yeni havuz üyeleri, rulet oyunundaki mantığa uygun şekilde seçilmektedirler 37. Rulet seçiminde kromozomlar, uygunluk fonksiyonu değerlerine göre bir rulet etrafına gruplanır. Ardından bu rulet üzerinden rassal olarak bir birey seçilir. Bu yöntemde rahatlıkla görülebileceği gibi daha büyük alana sahip bireyin seçilme şansı daha fazla olacaktır. 2.6.5.10 Turnuva Seçimleri İki kromozom çözüm havuzu içerisinden seçilerek uygunluk fonksiyonu büyük olan kromozom eşleşme havuzuna gönderilir, diğeri ise çözüm havuzunun içine tekrar bırakılır. Bu işlem, yeni toplum dolduruluncaya kadar devam edilir. Bu yöntemde herhangi bir kromozomun kaybedilme olasılığı rulet tekeri seçim yöntemine göre daha azdır. 2.6.5.11 Seçkinlik (Elitizm) Çözüm havuzunda uygunluk fonksiyonu değeri en yüksek olan bireyin çaprazlama ve mutasyon gibi operatörlerle kaybolabilme ihtimali vardır. Bunun önlenmesi için 35 S. Kulluk , O. Türkbey, “Tesis Yerleşimi Problemi İçin Bir Genetik Algoritma”, YA/EM’ 2004 Yöneylem Araştırması/Endüstri Mühendisliği – XXIV Ulusal Kongresi, 15-18 Haziran 2004, Gaziantep – Adana. s.2. 36 A. Coşkun, “Bir Optimizasyon Yöntemi : Genetik Algoritma – Molga Programı İle İterasyon Sayılarının Değerlendirilmesi”, 2006 Gazi Üniversitesi Endüstriyel Sanatlar Eğitim Fakültesi Dergisi Sayı :18, s. 51. 37 M. Akansel, T. İnkaya, ”Akış Atölyesinde Kesikli Parti Bölme Problemi İçin Bir Genetik Algoritma Yaklaşımı”, YA/EM’ 2004 Yöneylem Araştırması/Endüstri Mühendisliği – XXIV Ulusal Kongresi, 15-18 Haziran 2004,Gaziantep – Adana. s.2. 35 çözüm havuzunda uygunluk değeri en yüksek olan birey hiçbir işleme tabi tutulmadan bir sonraki jenerasyona aktarılır. Bu sayede, bir jenerasyondaki uygunluğu en yüksek olan bireyin bir önceki jenerasyondaki uygunluğun yüksek olan bireyden kötü olma ihtimali ortadan kaldırılmış olur 38. 2.6.5.12 Kodlama Kodlama GA’nın çok önemli bir kısmıdır. Bir probleme GA uygulanmadan önce, verinin uygun bir şekilde kodlanması gerekmektedir 39. Oluşturulan genetik modelin hızlı ve güvenilir bir şekilde çalışabilmesi için bu kodlamanın doğru yapılması gerekmektedir. 2.6.6 Genetik Algoritma Kodlama Türleri 2.6.6.1 İkili Kodlama Bu kodlama türünde her kromozom yalnızca {0,1} elemanlarından oluşan ikili bir diziye sahiptir 40 . Bu dizideki her bit, çözümün belli karakteristiğini temsil edebilir. Diğer bir seçenek de tüm dizinin toplamda bir sayıyı temsil etmesidir. GA yöntemindeki kodlama çeşitleri arasında en sık kullanılan yöntemdir. 2.6.6.2 Permutasyon Kodlama Bu kodlama türü, en çok düzenleme (gezgin satıcı ve çizelgeleme gibi) problemlerde kullanılır. Burada her kromozom, sayıları bir sırada temsil eder 41. Tablo 2 : Genetik Algoritma İçin Permutasyon Kodlama 38 Ergüven VATANDAŞ, İbrahim ÖZKOL, Kanat dizaynında genetik algoritma ve dinamik ağ yöntemlerinin birleştirilmesi, itüdergisi/d mühendislik Cilt:5, Sayı:6, Aralık 2006. s.44. 39 D. Özdağlar, E. Benzeden, A. Murat Kahraman, “Kompleks Su Dağıtım Şebekelerinin Genetik Algoritma ile Optimizasyonu”, İMO Teknik Dergi, 2006, Yazı 253. s. 3854-3855. 40 Şenay ATABAY, F. Gülten GÜLAY, Genetik algoritmalar ile perdeli yapı sisteminin maliyet optimizasyonu, itüdergisi/d mühendislik Cilt:3, Sayı:6, Aralık 2004. s.72, 77. 41 Timur KESKİNTÜRK, Permutasyon Kodlamalı Genetik Algoritmada, Operatörlerin Etkinliklerinin Araştırılması, VI. Ulusal Üretim Araştırmaları Sempozyumu, İstanbul Kültür Üniversitesi, 22-23 Eylül 2006. s. 1-7. 36 Kromozom A 78941 Kromozom B 87914 2.6.6.3 Değer Kodlama Karmaşık değerlerin kullanıldığı problemlerde, ikili kodlama yapmak zor olduğu için değerler doğrudan kullanılabilir 42. Bu yönteme değer kodlama adı verilir. Tablo 3: Genetik Algoritma İçin Değer Kodlama Kromozom A 1.2324 3.5354 4.6465 3.5556 Kromozom B Doğu, Batı, Güney, Kuzey 2.6.6.4 Ağaç Kodlama Bu kodlama yöntemi, başladığı ile aynı kalmayan, gelişen, değişen programlar veya ifadeler için kullanılır. Ağaç kodlamada her kromozom, bazı nesnelerin ağacı konumundadır 43. (örneğin programlama dillerindeki komutlar gibi). 2.6.7 Genetik Algoritmanın Diğer Yöntemlerden Farkları • GA, problemlerin çözümünü parametrelerin direkt olarak değerleriyle değil, kodlarıyla arar. Bu sayede, GA, kesikli sayı ve tamsayı programlama problemlerinin çözümlerinde uygulanabilir. 42 N. Tunalıoğlu, T. Öcalan, Üç Boyutlu Karayolu Güzargah Optimizasyonunda Karar Destek Sistemi Olarak Genetik Algoritmaların Kullanımı, TMMOB Harita ve Kadastro Mühendisleri Odası 11. Türkiye Harita Bilimsel ve Teknik Kurultayı 2 – 6 Nisan 2007, Ankara. s.5. 43 Tahir Emre KALAYCI, Yapay Zeka Teknikleri Kullanan Üç Boyutlu Grafik Yazılımları İçin “Extensible 3D” (X3D) İle Bir Altyapı Oluşturulması ve Gerçekleştirilmesi, Ege Üniversitesi Fen Bilimleri Enstiyüsü, Yüksek Lisans Tezi. s. 82-83. 37 • GA, her kromozom için amaç fonksiyonu yerine uygunluk fonksiyonunun ürettiği değeri kullanır. Bu değerin kullanılması sayesinde, ayrıca yardımcı bir bilginin kullanılmasına gerek kalmaz. • GA’da deterministik değil rassal geçiş kuralları kullanılır. GA, ebeveyn seçimini ve eski jenerasyonlardan çaprazlama yöntemini rassal şekilde kullanır. Böylece elde olan bilgilere dayanarak yeni kombinasyonlar oluşur ve uygunluk değeri daha yüksek olan yeni jenerasyonlar gelişir. • GA, geleneksel yöntemlerin aksine GA, tek nokta üzerine değil bir noktalar popülasyonu (aday çözümler kümesi) ile araştırma yapmaktadır. Bu sayede çok karmaşık olan ve birçok minimum veya maksimum noktası bulunan problemler arasında optimum veya yakın optimum çözümlere ulaşılabilir. Böylece GA yönteminin yerel optimum çözüm tuzağına düşme olasılığı zayıftır. • GA, bir çözüm kümesine (uzayına) sahiptir ancakbu kümenin tamamında değil belirli bir kısmında araştırma yapar. Böylece, daha etkin bir arama yaparak çok daha kısa bir sürede çözüme ulaşırlar. • GA çözümlerden oluşan popülasyonu eş zamanlı olarak inceler ve böylelikle yerel en iyi çözümlere takılmamaz. • GA, sezgisel bir metod olması nedeniyle verilen her problem için optimum sonucu bulamayabilir, ancak başka yöntemlerle çözülemeyen ya da çözüm zamanı problemin büyüklüğü ile üstel olarak artan dolayısıyla da çözülmesi oldukça çok zaman alan problemlerde optimuma yakın sonuçlar vermektedir. • GA, sürekli ve kesikli değişkenlerin bir arada bulunduğu, birçok pratik optimizasyon problemlerinde kullanılabilir. Bu tarz problemlerde standart 38 doğrusal olmayan programlama teknikleri kullanılırsa hesaplamaların pahalıya malolmasının yanında etkin olmayan durumlarla da karşılaşılması sözkonusudur. • GA,paralel arama yapar. GA, çözüm topluluğuna adım adım genetik operatörler uygulayarak ve uygun toplulukta arama yaparak yeni nesiller üretir ve en iyi çözümlere ulaşılmasını sağlar. 2.6.8 Genetik Algoritmanın Faydaları • Verilerin kolay tasarlanması • Çok amaçlı en iyileme yöntemleri ile birlikte kullanılabilmesi • Çok karmaşık ortamlara uyarlanabilmesi • Kısa sürelerde iyi sonuçlar verebilmesi • Klasik yöntemlerle çözülemeyen problemlere uygulanabilmesi 2.6.9 Genetik Algoritma Araçları Herhangi bir problemde en iyileme için kullanılacak GA tasarımı, C, C++, C#, Java, Fortran, LISP, Prolog, Excel, VB, Pascal veya Delphi gibi herhangi bir programlama dili ile uygun bir kod geliştirme platformunda gerçekleştirilebilir. Bunun dışında bir simulasyon programı olan MATLAB’in GA için özelleşmiş “The Genetic Algorithm Optimization Toolbox (GAOT) for MATLAB 5” isminde bir aracı da vardır. Ayrıca bu çalışmada da uygulandığı gibi GA, MATLAB’de özel tool olmadan tek başına da kodlanabilmektedir. 2.6.10Genetik Algoritma Kullanım Alanları GA, karmaşık problemleri hızlı ve en uyguna yakın olarak çözer. Bu özelliği sayesinde GA, çok çeşitli problem tiplerine uygulanabilmektedir. Büyük çözüm kümelerine sahip problemler, geleneksel yöntemlerle tarandığında hesaplama zamanı olukça fazla olmaktadır. Bu tip problemler, GA ile ele alınıp çözülmeye 39 çalışıldığında, çok daha kısa sürede, kabul edilebilir çözümler bulunabilmektedir. Bu yüzden GA özellikle çözüm uzayının geniş ve karmaşık olduğu problem tiplerinde başarılı sonuçlar vermektedir. 2.6.11Genetik Algoritma Genel Uygulama Alanları 2.6.11.1 Optimizasyon GA, farklı dallardaki optimizasyon problemlerini çözmede kullanılmaktadır 44, 45. Bunlara örnek olarak gezgin satıcı problemi, araç rotalama problemi, yönetim biliminin tüm dalları (finans, pazarlama, üretim, stok kontrolü, veritabanı yönetimi vb.), Çinli postacı problemi, atama problemi, yerleşim tasarımı problemi ve sırt çantası problemi gibi problemler sayılabilir. 2.6.11.2 Otomatik Programlama ve Bilgi Sistemleri GA, bilgisayar programlarının geliştirilmesinde yaygın olarak kullanılabilir 46. Ayrıca, bilgisayar çipleri tasarımı, ders programı hazırlanması ve ağların çizelgelenmesi gibi problemlerde de kullanılabilir. GA kullanılarak dağıtılmış bilgisayar ağlarının tasarımı da gerçekleştirilebilmektedir. Ağ tasarımında GA kullanılması, tasarım sürelerinin ve maliyetlerinin azalmasını sağlar. 2.6.11.3 Mekanik Öğrenme Mekanik öğrenme, gözlenmiş bir veri takımını anlamak ve yorumlamak ve görülmemiş objelerin özelliklerini tahmin etmek şeklindeki iki temel amaç için 44 A. Hacıoğlu, İ. Özkol, “Titreşimli Genetik Algoritma İle Hızlandırılmış Kanat profili Optimizasyonu”, Havacılık ve Uzay Teknolojileri Dergisi, Ocak 2003 Cilt 1 Sayı 1. s.1-10. 45 Gül Gökay Emel, Çağatan Taşkın, “Genetik Algoritmalar ve Uygulama Alanları”, Uludağ Üniversitesi İktisadî ve İdarî Bilimler Fakültesi Dergisi, cilt XXI, Sayı 1, 2002, s. 129, 136. 46 R. Daş, İ. Türkoğlu, M. Poyraz, “Genetik Algoritma Yöntemleriyle Internet Erişim Kayıtlarından Bilgi Çıkarılması”, SAÜ Fen Bilimleri Enstitüsü Dergisi 10. Cilt, 2. Sayı, 2006. s. 67-72. 40 model kurmayı amaçlayan bir yöntemdir. GA’nın mekanik öğrenme alanında uygulanması mümkündür 47. 2.6.11.4 Ekonomik ve Sosyal Sistem Modelleri Ekonomideki en önemli problemlerden biri “bir sistemi ölçen, gözlenmiş değişkenler arasındaki matematiksel ilişkiyi keşfetme problemi”dir. GA ile bu tip problemlere tatmin edici çözümler getirilmektedir 48. 2.6.12 Genetik Algoritmanın İşletmelerdeki Uygulama Alanları 2.6.12.1 Finans GA, finansal modelleme uygulanan problemlerin çözümünde son derece uygundur. GA, amaç fonksiyonu odaklı bir yöntemdir. Finans problemleri de genel olarak, amaç fonksiyonları tahmin etme gücüne veya bir kıyaslama sonucuna bağlı getirilerdeki gelişmeleri içerir. GA, özellikle hisse senedi fiyatlarındaki değişimleri tahmin etmede ve bulmada, kaynak tahsisi ve uluslararası sermaye tahsisi stratejilerini belirlemede kullanılabiir. Finans problemlerinin çözümünde GA, tek başına kullanılabildiği gibi bulanık mantık ve Yapay Sinir Ağları (YSA) yaklaşımlarıyla birlikte de kullanılabilmektedir. 2.6.12.2 Pazarlama GA, pazarlama problemlerinde de kullanılabilir. Özellikle çok geniş veri tabanlarından veriyi süzme tekniği olan ve pazarı ve tüketiciyi tanımada son derece önemli rol oynayan veri madenciliğinde kullanılan tekniklerden biri GA’dır. GA tabanlı yaklaşım kullanılarak veri yığınlarından modeller elde edilmektedir. 47 P. Turğut, A. Arslan, “Sürekli Bir Kirişte Maksimum Momentlerin Genetik Algoritmalar İle Belirlenmesi”, DEÜ Mühendislik Fakültesi Fen ve Mühendislik Dergisi Cilt : 3 Sayı : 3 Ekim 2001. s. 2,9. 48 Hakan Er, M. Koray Çetin, Emre İpekçi Çetin, “Finansta Evrimsel Algoritmik Yaklaşımlar : Genetik Algoritma Uygulamaları”, Akdeniz İ.İ.B.F. Dergisi (10) 2005, s.77. 41 2.6.13Genetik Algoritmanın Üretimde Uygulama Alanları 2.6.13.1 Montaj Hattı Dengeleme Problemi Endüstrilerde çok önemli bir rol oynayan montaj işlemi problemlerinde GA kullanılabilir 49. 2.6.13.2 Çizelgeleme Problemi GA, çizelgeleme problemlerinde genel olarak diğer yöntemlerden daha hızlı bir şekilde optimale yakın çözüm bulmuşlardır. 2.6.13.3 Tesis Yerleşim Problemi Tesis yerleşim problemleri araç/gereçleri veya ihtiyaca göre diğer bazı kaynakları belirli bir kritere göre optimum performans sağlayacak şekilde yerleştiren problemlerdir. Bu gibi problemler, araç/gereçlerin genellikle farklı ürünleri üretme esnasında kullanılmasından dolayı karmaşık hale gelmektedir. GA bu karmaşık problemde uygun sonuç verecek şekilde kullanılabilir 50. 2.6.13.4 Atama Problemi Atama problemleri genel olarak; n tane elemanın, n tane farklı göreve atanması problemidir. GA diğer problem tiplerinde olduğu gibi atama problemlerinde de kullanılabilir 51. 49 Birgül Küçük, Timur Keskintürk, “Montaj Hattı Dengelemede Genetik Algoritma Operatörlerinin Etkinliklerinin Araştırılması”, YA / EM 2006 – Yöneylem Araştırması / Endüstri Mühendisliği – XXVI. Ulusal Kongresi, 3 – 5 Temmuz 2206, Kocaeli. s. 390-393. 50 Ralf Schleiffer, Jens Wollenweber, Hans-Juergen Sebastian, Florian Golm, Natasha Kapoustina, “Application of Genetic Algorithms for the Design of Large-Scale Reverse Logistics Networks in Europe’s Automotive Indsutry”, Proceeding of the 37th Hawaii International Conferenece on System Sciences – 2004. s. 2,6. 51 Selda Oktay, Orhan Engin, “Scatter Search Method for Solving Industrial Problems : Literature Survey”, Journal of Engineering and Natural Sciences, 2006. s. 151. 42 2.6.13.5 Hücresel Üretim Problemi GA, hücreler arası taşımanın minimum olduğu bir hücre kuruluşu amaçlanan problemlerde kullanılabilmektedir 52. 2.6.13.6 Sistem Güvenilirliği Problemi Bir sistemin güvenilirliği, belirli koşullar altında belirli bir zaman aralığında sistemin başarılı olarak çalışma olasılığı olarak tanımlanmaktadır. Çoğu sistem, çeşitli işlemlerde kritik bir role sahiptir ve eğer sistemde arıza olursa sonuçları oldukça ciddi olmaktadır. GA, oldukça önemli olan bu problemin çözümünde de kullanılabilmektedir. 2.6.13.6 Taşıma Problemi Tüm talebin karşılanması ve maliyet minimizasyonu şartıyla mamulün arz yerinden talep yerine optimum tahsisini sağlamak amacına sahipolan problemlerin çözümünde de GA tekniği kullanılabilmektedir.. 2.6.13.7 GA’nın, Gezgin Satıcı Problemi en yoğun olarak uygulandığı problemlerden biri gezgin satıcı problemleridir. Bu problemlerde amaç, katedilen toplam mesafeyi minimize eden bir yolculuk planı oluşturmaktır. Örnek olarak; devre tasarımı, posta taşıyıcılarının, havayolu uçaklarının, okul otobüslerinin rotalarının bulunması verilebilir. 2.6.13.8 Araç Rotalama Problemi Temel araç rotalama problemi, tek bir depodan araçların ayrılması ve müşteri taleplerini karşılayarak tekrar depoya dönmesi anlamına gelir. Bu tarz problemlerde 52 Tuğba Saraç, Feriştah Özçelik,”Alternatif Rotaların Varlığında Üretim Hücrelerinin Genetik Algoritma Kullanılarak Oluşturulması ”, Endüstri Mühendisliği Dergisi, Cilt : 17, Sayı : 4, s. 22-36. 43 her aracın bir kapasite kısıtı vardır. Bu temel probleme , her aracın alacağı yol, mesafe kısıtı olarak; harcayacağı süre, zaman kısıtı olarak eklenebilir. GA özellikle zaman pencereli araç rotalama problemlerinin çözümü için kullanılmaktadır53. Minimum Yayılan Ağaç Problemi 2.6.13.9 Minimum yayılan ağaç problemi, grafik teorisinde sıklıkla karşılaşılan klasik bir problemdir. Problemin anlaşılabilmesi için bir örnek vermek gerekirse “coğrafî bir alanda dağılmış çeşitli şehirler arasında fiber-optik kablo döşeme problemi” verilebilir. Problemin amacı, tüm şehirleri fiber-optik kablo ağına bağlayan yerleşim şeklini en düşük maliyetle bulabilmektir. GA minimum yayılan ağaç problemini çözerken 54 dikkat ettiği en önemli olan nokta, sözkonusu ağacın nasıl kodlanacağıdır. GA’nın verimli bir sonuca ulaşabilmesi için kodlamanın doğru şekilde yapılması gerekmektedir. 53 Yaw Chang and Lin Chen, “Solve the Vehicle Routing Problem With Time Windows Via a Genetic Algorithm”, Discrete and Continuous Dynamical Systems Supplement 2007, s. 240-249. 54 Önder Belgin, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Yüksek Lisans Tezi, “Haberleşme Şebekelerinin Tasarımında Sezgisel Yaklaşımlar : Değişken Komşu Arama, Kuş Sürüsü Optimizasyonu, Karınca Kolonisi Optimizasyonu”, Temmuz 2007. s. 30-31. 44 3 UYGULAMALAR Bu bölümde tez çalışmasında incelenen yöntemler ile ilgili çeşitli örnekler ve uygulamalara yer verilmiştir. Uygulamalar kısmında çözümlenen makine - ürün matrisleri literatürde kullanılan örnek kümelendirme problemlerinden alınmıştır 55. 3.1 GENETİK ALGORİTMA UYGULAMASI Girdiler C: İstenen küme sayısı p_m : Makine - ürün matrisi ch_no : Her bir jenerasyonda bulunan kromozom sayısı generations: Yaratılacak jenerasyon sayısı Repetitions: Kaç kere yeni jenerasyon kadar populasyon üretileceği Çıktılar Best_chromosome: En iyi kromozon (çözüm) Best_part: En iyi kromozomun belirlediği ürün kümelendirmesi Best: En iyi kromozomun gruplama verimliliği Best_found_at: En iyi kromozomun bulunduğu jenerasyon Algoritma, repetitions parametresi kadar yeniden başlayıp bitmektedir. Her bir yeniden başlama sürecinde, generations parametresi kadar jenerasyon algoritmada yaratılır ve çaprazlanır, algoritma sonunda çıkan en iyi gruplama verimliliği değeri ve kromozom, diğer çalıştırmalarla karşılaştırılmak için saklanır. Algoritma ilk başladığında başlangıç popülasyonu yaratmaktadır. Daha sonra generations 55 Tabitha L. James, Evelyn C. Brown, Kellie B. Keeling, A hybrid grouping genetic algorithm for the cell formation problem, Computers & Operations Research 34 (2007). s. 2072-2074. 45 parametresi kadar sürecek bir çevrim içerisinde önce üretilen kromozomların uygunluk fonksiyonu değerlerini hesaplar, bu değerlerin oluşturduğu seçilme olasılıkları kılavuzluğunda, başlagıç popülasyonu kadar kromozom seçilir ve bu kromozomlar üzerinde çaprazlama işlemi uygulanır. Daha sonra çaprazlama sonrası oluşan çocuk kromozomların uygunluk fonksiyonunun hesaplanması için çevrim başına geçilerek, ikinci çevrim başlatılmış olur. Aşağıda, bahsedilen süreçlerin ayrıntılı açıklaması yer almaktadır. Süreç: her bir tekrar için, Başlangıç popülasyonu Her bir kromozom, her bir makinanın hangi hücreye ait olduğunu tanımlayan numaralar dizisi ile ifade edilir. Örn: 6 makina, 3 hücreye gruplanacaksa örnek bir kromozom: şeklinde türetilebilir. Bu da makina 2,3 nin birinci hücreye, makina 1,6’ nın ikinci, makina 4,5 ‘in üçüncü hücreye gideceği anlamına gelir. Düzgün dağılıma uygun olarak dağılıma uygun bir şekilde rastsal sayılar üretilir.Fonksiyonda tanımlanan kromozom sayısı kadar sayı yaratılır. Iterasyon sayısı kadar çalıştırılacak bir döngü içerisinde: Uygunluk Fonksiyonu İkili makine - ürün matrisinde grupların dışında kalan ürün - makine eşleşmeleri (istisnaî elemanları) ve grubun içerisinde bulunan fakat gerçekte eşleşmeleri bulunmayan makine - ürün ikililerini (boş elemanları) göz önünde bulundurularak oluşturulan bir ölçü kullanılmaktadır. Makina gruplamasını tamamladıktan sonra ürünlerin de hangi gruplara atanması gerektiği belirlenir. Bu, daha önce bahsedildiği gibi ürünün grubunu, ürünün en çok uğradığı grup olarak seçer. Bir örnekle anlatırsak, ürün 1 in makine - ürün matrisindeki satırı aşağıdaki gibi olsun: 46 Tablo 4: Genetik Algoritma Örneği İçin Ürün 1’in Makine Matrisindeki Satırı 1 2 3 4 5 6 1 0 1 1 0 0 Kolonlar makinaları göstermektedir. Kromozomumuzdaki makinelerin sırası ile dahil olduğu makine öbeklerinin olduğunu varsayalım. Buna göre ürün 1, birinci hücreye 1, ikinci hücreye 2, üçüncü hücreye de 0 kere gitmiştir. Bu durumda ürün ikinci hücreye atanır. Eşitlik durumunda da kullanılan programlama dili olan MATLAB’daki maksimum fonksiyonu gereğince ilk hücreye atama yapılır. Bu işlem tamamlandıktan sonra, düzenlenmiş makine - ürün matrisinde istisnaî elemanlara ve boş elemanlara bakmak gerekir. Ürün ve makineleri aşağıdaki gibi gruplandırdığımızı varsayalım: 1 4 6 2 3 5 2 1 1 4 1 1 1 7 1 1 1 1 1 1 1 1 3 1 1 5 1 1 6 1 1 1 8 1 1 1 Şekil 2: Genetik Algoritma Örneği İçin Makine - Ürün Gruplanması Burada 8 ürün ve 5 makine vardır.1. hücrede ürün 2,4,7 ve makine 1,4,6; 2. hücrede ürün 1,3,5,6,8 ve makine 2,3,5 bulunmaktadır. Buna göre hücreler arası ürün hareketliliği ve makine faydalılığı gibi etkinliklerin ağırlıklı ortalaması olan gruplama verimliliği şu şekilde hesaplanır. 47 Formülde: e: Ürün - makine matrisinde toplam 1 sayısını; e0: İstisnaî eleman sayısını ev : Boş eleman sayısını göstermektedir 56 . -(2,2) ve (7,2) karelendirmenin dışında olduğundan istisnaî eleman sayısı = 2’dir Boş eleman sayısı, 2 yukaridaki dikdörtgende, 2 de aşağıdaki dikdörtgende olmak üzere toplam 4’tür. Buna göre verimlilik; ’dır. Bu verimlilik, kromozomun uygunluk değeri olmaktadır. Her bir kromozomun değerleri toplamları 1 olacak şekilde normalize edilmektedir. Bu da rulet tekerleği prosedürüne seçilme olasılıkları olarak ifade edilmektedir. Seçim Rulet tekerleği tekniğine göre uygunluk değerleri orantılı olasılıklarla kromozomlar seçilmektedir. Çaprazlama 56 Başar UYANIK, A Thesis Submitted To The Graduate School Of Natural And Applied Sciences Of METU, Master Of Science In Industrial Engineering, 2005. s.24-25. 48 Burada tek pozisyonlu çaprazlama yapılmıştır. Çaprazlama pozisyonları rastsal olarak belirlenmektedir. Örneğin kromozomların aşağıdaki gibi olduğunu varsayalım: Tablo 5: Genetik Algoritma Örneği İçin Kromozomlar 3 1 1 3 3 2 1 1 2 2 3 3 2 1 2 3 1 2 3 3 1 2 1 2 Çaprazlama işleminin yapıldığı noktaları da aşağıdaki gibi belirlenmiş olsun. Bu nokta sayısının, kromozon sayısından 1 eksik olmasına dikkat etmek gerekmektedir. Tablo 6: Genetik Algoritma Örneği İçin Çaprazlama Noktaları 4 2 3 Bu durumda kromozom 1,2 alınmaktadır. 1’den ilk 4, 2’den 5. ve 6. elemanlar alınıp birleştirilmektedir. Tablo 7: Genetik Algoritma Örneği İçin Kromozomların Çaprazlamadan Sonraki Durumu Bu durumda 3 1 1 3 3 2 1 1 2 2 3 3 ilk çocuk kromozom aşağıdaki gibi olur: 49 Tablo 8: Genetik Algoritma Örneği İçin Çaprazlamadan Sonraki İlk Çocuk Kromozom 3 1 1 3 3 3 Yapılan program yukarıdaki kromozomda 2. hücreye atama yapılmamasını belirlemektedir ve bu kromozomu “makinalar iki hücreye gruplanmış” şeklinde kabul etmektedir. Bu durumda kromozomun son hali aşağıdaki gibi olur. Tablo 9: Genetik Algoritma Örneği İçin Kromozomun İşlemden Sonraki Hali 2 1 1 2 2 2 İkinci çocuk kromozom da ikinci kromozomum ilk 2 elemanı, 3. kromozomun 3,4,5,6. elemanını alınıp oluşturulur: Tablo 10: Genetik Algoritma Örneği İçin 2. Çocuk Kromozom 1 1 2 2 3 3 2 1 2 3 1 2 İkinci kromozom şu şekildedir: Tablo 11: Genetik Algoritma Örneği İçin 2. Kromozom 1 1 2 3 Üçüncü kromozom şu şekildedir: 50 1 2 Tablo 12: Genetik Algoritma Örneği İçin 3. Kromozom 2 1 2 2 1 2 Üçüncü kromozomda dikkat edilirse üç hücre yoktur, iki hücre bulunmaktadır. Bu, da kod tarafından kabul edilmektedir. Kromozom ilk üretilen kromozom gibi bir sonraki iterasyonlara iletilebilmektedir. Dört tane kromozoma ihtiyacımız olduğundan, son kromozoma da şimdiye kadarki en iyi uygunluk fonksiyonuna sahip kromozom konulur. Böylece en iyi sonucun elde edildiği dizilim bir sonraki jenerasyona aktarılmış olur. Iterasyon sayısı kadar dönen döngü ve süreç döngüleri burada alt alta bitirilebilir. Algoritma MATLAB programı üzerinde çalıştırılmış ve sonuçları elde edilmiştir. Uygulamanın çalıştırıldığı platforma ve genel olarak uygulamaya ait ekran çıktıları aşağıda yer almaktadır. Problem şu şekilde ifade edilebilir : Şekil 3: Genetik Algoritma Örneği İçin Problemin Gösterimi Problemin çözümü MATLAB simulasyon programında gerçekleştirildiğinde 51 aşağıdaki gibi ekran görüntüleri sözkonusu olur : Şekil 4 : Genetik Algoritma Örneği İçin MATLAB Uygulaması Ekran Görüntüsü 1 Şekil 5: Genetik Algoritma Örneği İçin MATLAB Uygulaması Ekran Görüntüsü 2 Problemim çözümü ile ilgili olarak MATLAB’de yazılan kodlar EKLER ksmında 52 verilmiştir. Ancak burada bu programın nasıl yazıldığından biraz bahsetmek faydalı olacaktır. • Problemi çözebilmek için öncelikle makine - ürün matrisine ihtiyaç duyulmaktadır. Sözkonusu matris Excel’de (veya uygun başka bir programda) hazırlanıp MATLAB’da bir diziye yüklenir. • Yükleme işlemi gerçekleştirildikten sonra dosya adı, matris olarak kullanılabilir duruma gelmiş olur. Artık GA çalıştırılabilir. • x’ler girdiler, y’ler çıktılar olmazk üzere y = fonksiyon(x) formatında bir fonksiyon çalıştırılır. • Bunun dışında çalıştırılacak GA fonksiyonuna, best_chromosome,best_found_at, best_part, best, p_m,ch_no, generations, repetitions gibi parametreler de beslenir. • Algoritma boyunca jenerasyonlar süresince bulunan en iyi kromozom skorlarının grafiği işlenir. Sonuçlarda da komut satırında makine hücreleri ve ürün hücreleri yazılır. • Buradaki parametreler kaç hücreli gruplama yapılacağını, her bir jenerasyonda bulunacak kromozom sayısını, genetik algoritmanın kaç jenerasyon boyunca çalıştırılacağını, genetik algoritmanın kaç kere tekrar başlatılacağını ve yüklenen makine - ürün matrisini ifade etmektedir. • Çözülecek probleme göre bu parametre değerleri değişebilir. 53 Makine grupları best_chromosome vektöründe şu şekildedir: Tablo 13: Genetik Algoritma Örneği İçin Best_chromosome Vektöründe Makine Grupları 1 2 3 4 5 6 7 8 9 10 1 2 2 2 1 2 2 1 2 1 Makina 1,5,8,10 hücre 1’e; diğerleri hücre 2’ye gitmektedir. Ürün grupları best_part vektöründe şu şekildedir : Tablo 14: Genetik Algoritma Örneği İçin Best_part Vektöründe Ürün Grupları 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 2 1 2 1 2 2 1 2 2 2 2 1 2 Ürün 1,4,6,9,14 hücre 1’e gitmektedir. Ürün 2,3,5,7,8,10,11,12,13,15 hücre 2’ye gitmektedir. “Best” değişkeninde elde edilen en iyi verimlilik değeri, “Best_found_at” değişkeninde en iyi değeri elde ettiğimiz kromozomun kaçıncı jenerasyonda elde edildiği tutulur. 3.2 OVS ALGORİTMASI VE ÖRNEK UYGULAMASI Ürün - sipariş matrisi P ve karşılık gelen mesafe matrisi D 57 aşağıdaki gibi olduğunu varsayalım. 57 Ashayeri, Heuts, Tammel, a.g.e. s. 455-456. 54 5 adet ürünü 3 gruba öbeklemek istediğimizi varsayalım. (p = 3). Bu durumda OVS yöntemi aşağıdaki şekilde gelişir. 1) altkümesini {1,2,3} olarak başlat. 2) ’yi her medyana karşılık gelecek şekilde belirle. ve j {1,2,3}. Şimdi şunlar oluşur. ürün 1, grup 1’dedir. : ürün 2, grup 1’de değildir. : ürün 3, grup 1’de değildir. : ürün 4, grup 1’de değildir. : ürün 5, grup 1’de değildir. Benzer şekilde, j = 2 ve 3 için de oluşturulur. Bu, anlamına gelir. Toplam mesafe : 3 ve 4) Ürün 4’ü seç, (b = 4) ve mesafeye katkılar şu şekilde hesaplanır : Ürün 1’i yerdeğiştir (j = 1) : i = 1: in satır minimumudur. (bu durumda, 5 3’lük matris, D’nın ilk 3 kolonundan oluşmaktadır). (c durumu) olduğundan 55 ’dir. i=2: , ’in 2. satır minimumu değildir , i=3: , ’in 3. satır minimumu değildir , i=4: , ’in 4. satır minimumu değildir , i=5: , ’in 5. satır minimumu değildir Bu, anlamına gelir. Ürün 2 (j = 2)’yi benzer bir şekilde yerdeğiştir. . Ürün 3 (j = 3)’ü benzer bir şekilde yerdeğiştir. . 5)Yerdeğişimlerinin hiçbiri tolam mesafede bir azalmaya sebep olmaz. (Bütün katkılar 0 veya pozitiftir.) 6)Ürün 5’i seç. Yerdeğişimi mesafe üzerinde şu etkilere sebep olur: Bakıldığında bu kez de herhangi bir yerdeğişiminin mesafede bir azalmaya sebep olmadığı görülür. Kompla bir çevrim bitmiştir ve altküme hala 1,2 ve 3 ürünlerini içermektedir. Bu başlangıç koşulu, final sonucuna eşit olduğunda işlemi sonuçlandırırız. Grup 1 : {1}, medyan : ürün 1 Grup 2 : {2}, medyan : ürün 2 Grup 3 : {3,4,5}, medyan : ürün 3 56 Karşılık gelen mesafe ise 4’tür. ( ) 3.3 AVS ALGORİTMASI VE ÖRNEK UYGULAMASI 5 tane ürünün 3 gruba ayrılacağını varsayalım. Örnek matrisimiz 58şu şekilde olsun. 1) yani 1.,2. ve 3. ürünlerin olduğu yere tesis koyar gibi. 2) Her bir median için bulunmalıdır. İlk anda ’dır. 3) Her bir ürünün 1.,2. ve 3.ürüne (medyana) olan uzaklıklarına bakılmalıdır. 4) Her bir elemanın hangisine uzaklıklığı en azsa o medyana atılmalıdır. (1. ürün için) ilk satırın ilk 3 elemanı alınır elemanın en küçük elemanı yani min ’dır. (2. ürün için) 2. satırın ilk 3 elemanı alınır elemanın en küçük elemanı yani min 58 Ashayeri, Heuts, Tammel, a.g.e. s. 456-457. 57 bu 3 ’dır. (4. ürün için) 4. satırın ilk 3 elemanı alınır elemanın en küçük elemanı yani min bu 3 ’dır. (3. ürün için) 3. satırın ilk 3 elemanı alınır elemanın en küçük elemanı yani min bu 3 ’dir. bu 3 (5. ürün için) 5.satırın ilk 3 elemanı alınır elemanın en küçük elemanı yani min bu 3 ’dir. Bu durumda medyan 1 = medyan 2 = medyan 3 = Buna göre toplam uzaklık şu şekilde hesaplanır : 1 1 ‘e uzaklık 0 2 2’ye uzaklık 0 3 3’e uzaklık 0 3 4’e uzaklık 2 3 5’e uzaklık 2 Toplam uzaklık 0 + 0 + 0 + 2 + 2 = 4 olur. 5) 4 ya da 5’ten herhangi bir nokta seçilir. Çünkü bunlar ’e dahil değildir. Burada 4 seçilir. Bu durumda 4’ü, her eleman yerine teker teker ’ye alıp uzaklığı azaltmaya katkısına bakılacaktır. 1 ile 4’ün yeri değiştirilir : Eğer değiştirilen kolon, o sıranın minimum elemanı değilse, uzaklık hesaplamada değişiklik yapılmayacaktır. (minimum değişmeyecektir). Burada 1. ürün için minimumdu, ama minimum, median olmaktan çıkarıldı. 58 Bu durumda 1. ürün için bizim uzaklıklarımız olur. ( 2.üründe ya da ’tır. Bu durumda minimum ) minimumdur. 2 atılmadığı için herhangi bir değişiklik yapmaya gerek yoktur. . 3.,4. ve 5. ürün için de değişiklik yoktur. 1. ürün için minimum olan ’di. 1. kolon hala ’de olduğundan değişiklik yoktur. 2. ürün için değişiklik vardır. min . minimum bu durumda idi. Bu durumda değişiklik (+1) 3. ürün için değişiklik yoktur. 1. ve 2. ürün için değişiklik yoktur. 3. ürün için min ( ) (+1) 4. ürün için min ( ) (-2) 5. ürün için min ( ) (+1) 6) Hiçbir değişiklik uzunluğu azaltmamaktadır. 1 arttı. 1 arttı. değişmedi. 7) Başka bir nokta (örneğin 5.nokta) denenecek olursa : 1. ürün için min artışa neden oldu. 2. ürün için min artışa neden oldu. 3. ürün için min artışa neden oldu. 59 4. ürün için min artışa neden oldu. 5. ürün için min artışa neden oldu. toplamı değişmedi. Uzaklıkta yine azalış olmamıştır. Toplamda bir çevrim (cycle) bitti. Olabilecek herşey denenmiştir ama daha iyisi bulunamayacaktır. Son durumda çözüm uzaklık = 4’tür. AVS’de ise yeni bir kolon soktuktan sonra farklı bir hesaplama yapılıyor. ( ) için , , ve seçilmişti. Eğer çözümden çıkartılan kolonda o ürünün minimumu yoksa değişiklik yok denir. Oysa öncelikle kolondaki yeni girenin değerinin sıradaki en küçük değerle karşılaştırılması gerekir. Örnek içinde : için 1. üründe değişiklik (+1) minimumda 4 > 0 hala 2. ürün için AVS değişikliği duruyor. değişiklik yok. 3. ürün için 2 > 0 , değişiklik yok. 4. ürün için 0 > 2 , değişiklik var. ( 5. ürün için 4 > 2 , değişiklik yok. ) 4. ürün 4. medyanda Toplamda değişiklik -1 oldu. AVS ve GA yöntemlerinin her ikisi de ürünlerin en yoğun olarak bulundukları makine öbeklerine atanmaları kısıtı içeren algoritmalarından dolayı ürün atamalarında bazı durumlarda verimliliği olumsuz etkileyecek düzenlemeler yapabilir ve bu sebeple en iyi çözümün elde edilmesine engel olabilir. 60 Bir örnekle açıklamak gerekirse ; İçerisinde 1,2,3,4,5,6,7 nolu makinelerin bulunduğu 1. nolu makine öbeğinde 3 işlem gören, 8,9,10 nolu makinelerin bulunduğu ikinci makine öbeğinde 2 işlem gören bir ürün, en çok işlem gördüğü makine öbeğine atama yapılması mantığı sebebi ile 1 nolu öbeğe atanır. 1 nolu öbekte 4 makinede işlem görmemesinden (boş elemanlar) ve 2. nolu öbekte 2 işlem görmesinden (istisnai elemanlar) dolayı e: Ürün - makine matrisinde toplam 1 sayısını; e0: İstisnaî eleman sayısını ev : Boş eleman sayısını göstermektedir verimlilik olur. Oysaki ürün 2. öbeğe atanmış olsaydı; olurdu. 3.4 ÖBEKLEME UYGULAMASI – 1 Sözkonusu makaledeki 59 4. problem : Makine – ürün matrisi aşağıdaki gibi olan bir durum için öbekleme işlemini gerçekleştirelim. Burada eğer bir ürün, bir makine içerisinde işleniyorsa kesişim alanlarındaki değer 1, yoksa 0’dır. 59 James,Brown, Keeling, a.g.e. s. 2072. 61 Tablo 15: Öbekleme Uygulaması - 1 İçin Makine – Ürün Matrisi Öncelikle makine benzerliği için makine kolonları sırayla 2’şer 2’şer incelenir. Tüm ürün satırları için makine kolonları birbirleri ile karşılaştırılır. Benzerlik karşılaştırılması sonucunda, benzer makinelerde işlem gören ürünlere uzaklık değeri olarak -2 (yakınlaştırma) , 0 (ilişki yok) ya da +1 (uzaklaştırma) değeri eklenir. Bu eklenen değerlere göre toplam olarak elde edilen değer 2 makine arasındaki ilişkiyi göstermektedir. En küçük değerlerin elde edildiği ikililer birarada olmayan en yakın makineleri (yani benzer ürünleri yoğun bir şekilde işleyen makineleri) göstermektedir. Örneğin 1. ve 2. makine kolonlarını inceleyelim : 1. ürün için eklenecek değer (1. makinede bulunmayıp, 2.makinede bulunduğundan uzaklaştırma değeri olan) +1, toplam değer +1’dir. 2. ürün için eklenecek değer (2 makinede de bulunduğundan yakınlaştırma değeri olan) -2, toplam değer -1’dir. 3. ürün için eklenecek değer +1, toplam değer 0’dır. 4. ürün için eklenecek değer +1, toplam değer +1’dir. 62 5. ürün için eklenecek değer +1, toplam değer +2’dir. 6. ürün için eklenecek değer +1, toplam değer +3’tür. 7. ürün için eklenecek değer -2, toplam değer +1’dir. 8. ürün için eklenecek değer +1, toplam değer +2’dir. 8 ürüne bakıldıktan sonra ortaya çıkan toplam değer 2’dir. Buna göre makine(1,2)= 2 olur denilebilir. Aynı mantıkla tüm kolonlar için bu işlem gerçekleştirildikten sonra makine - makine matrisi şu şekilde elde edilmiş olur : Tablo 16 : Öbekleme Uygulaması - 1 İçin Makine – Makine Matrisi Makine 1 Makine 2 Makine 3 Makine 4 Makine 5 Makine 6 Makine 1 0 2 6 -3 8 -3 Makine 2 2 0 -2 5 -8 5 Makine 3 6 -2 0 5 -4 5 Makine 4 -3 5 5 0 7 -4 Makine 5 8 -8 -4 7 0 7 Makine 6 -3 5 5 -4 7 0 Öbekleme işlemi bu matrise göre yapılacaktır. Tabi öncelikle kaçlı öbek olduğunun belirlenmesi gerekir. Bu örnekte 2’li öbek aldığımızı varsayalım. Bu öbeğe göre çözüm yaparken ilk başta (1-2) kolonlarını alınır. Ardından sırasıyla tüm kolonlar denenir. Hangi kolonun yerine hangi kolonun geleceği belirlenir. Buna göre aşağıdaki gibi bir tablo oluşur : Tablo 17: Öbekleme Uygulaması - 1 İçin Öbekleme Değişimi Tablosu GRUP ENK KARŞ. GRUP ENK KARŞ. GRUP ENK KARŞ. GRUP ENK KARŞ. 1-3 0 -16 1-4 -17 1 4-5 -8 -9 4-6 -19 0 2-3 -12 -4 2-4 4 -20 2-5 -19 2 5-6 6 -25 Burada, Enk (en küçük değer): Seçili kolonlardaki satır için en küçük değerler alındığında 63 elde edilen değer, Karş : İyileştirme diğer bir deyişle mesafedeki kısalma anlamlarına gelir. Buna göre sonuçtaki öbeklenmeler şu şekilde bulunur : Tablo 18 : Öbekleme Uygulaması - 1 İçin Öbekler MAKİNE ÖBEK ÜRÜN ÖBEK 1 1 1 2 2 2 2 1 3 2 3 2 4 1 4 1 5 2 5 2 6 1 6 2 7 1 8 2 Bir şekille gösterecek olursak öbekler aşağıdaki gibi oluşmuştur. Şekil 6 : Öbekleme Uygulaması - 1 İçin Öbekler Bu örnek için verimlilik : 64 olarak bulunur. 3.5 ÖBEKLEME UYGULAMASI - 2 Sözkonusu makaledeki 60 11. problem : Makine – ürün matrisi aşağıdaki gibi olan bir durum için öbekleme işlemini gerçekleştirelim. (Eğer bir ürün, bir makine içerisinde işleniyorsa kesişim alanlarındaki değer 1, yoksa 0 olduğu daha önce de belirtilmişti.) Tablo 19: Öbekleme Uygulaması – 2 İçin Makine – Ürün Matrisi Öncelikle makine benzerliği için makine kolonları sırayla incelenir. Tüm ürün satırları için makine kolonları birbirleri ile karşılaştırılır. 60 James,Brown, Keeling, a.g.e. s. 2072. 65 Benzerlik karşılaştırılması sonucunda, benzer makinelerde işlem gören ürünlere uzaklık değeri olarak -2 (yakınlaştırma), 0 (ilişki yok) ya da +1 (uzaklaştırma) değeri eklenir. Bu eklenen değerlere göre toplam olarak elde edilen değer 2 makine arasındaki ilişkiyi göstermektedir. En küçük değerlerin elde edildiği ikililer birarada olmayan en yakın makineleri (yani benzer ürünleri yoğun bir şekilde işleyen makineleri) göstermektedir. Tüm kolonlar için bu işlem gerçekleştirildikten sonra makine - makine matrisi şu şekilde elde edilmiş olur : Tablo 20 : Öbekleme Uygulaması - 2 İçin Makine – Makine Matrisi Makine 1 1 0 2 9 3 8 4 8 5 9 6 9 7 -7 8 9 9 8 10 -7 2 9 0 9 9 -10 10 10 -10 9 10 3 8 9 0 -4 9 -7 9 9 -4 9 4 8 9 -4 0 9 -7 9 9 -4 9 5 9 -10 9 9 0 10 10 -10 9 10 6 9 10 -7 -7 10 0 10 10 -7 10 7 -7 10 9 9 10 10 0 10 9 -10 8 9 -10 9 9 -10 10 10 0 9 10 9 8 9 -4 -4 9 -7 9 9 0 9 10 -7 10 9 9 10 10 -10 10 9 0 Öbekleme işlemi bu matrise göre yapılacaktır. Bu örnekte 4’lü öbek aldığımızı varsayalım. Bu öbeğe göre çözüm yaparken ilk başta (1-2-3-4) kolonlarını alınır. Ardından sırasıyla tüm kolonlar denenir. Hangi kolonun yerine hangi kolonun geleceği belirlenir. Buna göre sonuçtaki öbeklenmeler şu şekilde bulunur : 66 Tablo 21 : Öbekleme Uygulaması - 2 İçin Öbekler Bir şekille gösterecek olursak öbekler aşağıdaki gibi oluşmuştur. Şekil 7: Öbekleme Uygulaması - 2 İçin Öbekler 67 Bu problem için verimlilik aşağıdaki gibi bulunmuştur : . 3.6 ÖBEKLEME UYGULAMASI - 3 Sözkonusu makaledeki 61 22. problem : Makine – ürün matrisi aşağıdaki gibi olan bir durum için öbekleme işlemini gerçekleştirelim. (Eğer bir ürün, bir makine içerisinde işleniyorsa kesişim alanlarındaki değerin 1, yoksa 0 olduğu daha önce belirtilmişti.) Öncelikle makine benzerliği için makine kolonları sırayla incelenir. Tüm ürün satırları için makine kolonları birbirleri ile karşılaştırılır.Benzerlik karşılaştırılması sonucunda, benzer makinelerde işlem gören ürünlere uzaklık değeri olarak -2 (yakınlaştırma) , 0 (ilişki yok) ya da +1 (uzaklaştırma) değeri eklenir. Bu eklenen değerlere göre toplam olarak elde edilen değer 2 makine arasındaki ilişkiyi göstermektedir. En küçük değerlerin elde edildiği ikililer birarada olmayan en yakın makineleri (yani benzer ürünleri yoğun bir şekilde işleyen makineleri) göstermektedir. Tüm kolonlar için bu işlem gerçekleştirildikten sonra makine - makine matrisi şu şekilde elde edilmiş olur : 61 James,Brown, Keeling, a.g.e. s. 2074. 68 Tablo 22: Öbekleme Uygulaması - 3 İçin Makine – Ürün Matrisi 69 Tablo 23 : Öbekleme Uygulaması -3 İçin Makine – Makine Matrisi Öbekleme işlemi bu matrise göre yapılacaktır. Tabi öncelikle kaçlı öbek olduğunun belirlenmesi gerekir. Bu örnekte 4’lü öbek aldığımızı varsayalım. Bu öbeğe göre çözüm yaparken ilk başta (1-2-3-4) kolonlarını alınır.Ardından sırasıyla tüm kolonlar denenir. Hangi kolonun yerine hangi kolonun geleceği belirlenir. Buna göre aşağıdaki gibi bir öbeklenme oluşur : 70 Tablo 24: Öbekleme Uygulaması -3 İçin Öbekler Bir şekille gösterecek olursak öbekler aşağıdaki gibi oluşmuştur. 71 Şekil 8 : Öbekleme Uygulaması - 3 İçin Öbekler Bu problem için verimlilik olarak bulunur. 72 3.7 TEKSTİL SEKTÖRÜNDE BİR UYGULAMA Bu uygulama sunulan başlangıç verileri (makine, ürün ilişkilerinden oluşan matris) İstanbul'da teksil sanayinde faaliyet gösteren orta ölçekli bir firmadan alınan bilgiler ışığında türetilmiştir. Makinelerin ve ürünlerin gerçek isimleri firmanın isteği üzerine kullanılmamıştır. Bunun yerine sözkonusu şirketin üretimine devam ettiği 30 ürün ve kullanılan 15 makineden bahsedilirken ürün 1, ürün 2, makine 1, makine 2, makine 3 gibi kodlamalar kullanılmıştır. Makineler temel olarak baskı, dikiş, nakış, boya fonksiyonlarını yerine getirmektedir. Çözüm bu veriler üzerinden yapılmıştır. Makine – ürün eşleşmelerine ait matris aşağıdaki tabloda gösterilmiştir : 73 Tablo 25: Tekstil Sektöründeki Uygulama İçin Makine – Ürün Matrisi Bu makine – ürün matrisine göre öbekleme işlemini gerçekleştirelim. (Eğer bir ürün, bir makine içerisinde işleniyorsa kesişim alanlarındaki değerin 1, yoksa 0 olduğu daha önce belirtilmişti.) Öncelikle makine benzerliği için makine kolonları ilk olarak 1-2-3-4. kolonlar olmak üzere sırayla incelenir. 4’lü öbekleme yapıldığından kolonlar 4’erli olarak ele alınır.Tüm ürün satırları için makine kolonları birbirleri ile karşılaştırılır.Benzerlik karşılaştırılması sonucunda, benzer makinelerde işlem gören ürünlere uzaklık değeri olarak -2 (yakınlaştırma) , 0 (ilişki yok) ya da +1 (uzaklaştırma) değeri eklenir.Bu eklenen değerlere göre toplam olarak elde edilen değer 2 makine arasındaki ilişkiyi göstermektedir. 74 En küçük değerlerin elde edildiği ikililer birarada olmayan en yakın makineleri (yani benzer ürünleri yoğun bir şekilde işleyen makineleri) göstermektedir. Tüm kolonlar için bu işlem gerçekleştirildikten sonra makine - makine matrisi şu şekilde elde edilmiş olur : Tablo 26 : Tekstil Sektöründeki Uygulama İçin Makine – Makine Matrisi Hangi kolonun yerine hangi kolonun geleceği belirlenir. Buna göre aşağıdaki gibi bir öbeklenme oluşur : 75 Tablo 27 : Tekstil Sektöründeki Uygulama İçin Öbekler Makine Öbek Ürün Öbek 3 1 1 3 2 2 2 2 3 3 3 4 4 4 4 3 3 5 5 4 1 6 6 2 4 7 7 3 2 8 8 4 1 9 9 2 2 10 10 2 3 11 11 3 4 12 12 1 2 13 13 4 3 14 14 2 3 15 15 2 16 1 17 2 18 3 19 3 20 4 21 1 22 4 23 2 24 3 25 1 26 2 27 3 28 2 29 3 30 3 Bir şekille gösterecek olursak öbekler aşağıdaki gibi oluşmuştur. 76 12 16 21 25 2 6 9 10 14 15 17 23 26 28 1 4 7 11 18 19 24 27 29 30 3 5 8 13 20 22 6 1 1 1 1 9 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 8 10 13 1 3 5 11 14 15 7 4 12 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 Şekil 9 : Tekstil Sektöründeki Uygulama İçin Öbekler Bu problem için verimlilik aşağıdaki gibi bulunur : 77 SONUÇ ve ÖNERİLER Bu tez çalışmasında genel olarak öbekleme problemleri ve öbekleme probleminin çözüm yöntemleri incelenmiştir. İncelenen yöntemler OVS, AVS, AVS-M ve Genetik Algoritma yöntemleridir. AVS yöntemi OVS’den; AVS-M yöntemi de AVS’den türetilmiş yöntemlerdir. Ancak aralarında çözüm yöntemi olarak farklılıklar sözkonusudur. OVS yöntemi, öbekleme yapmak için olabilecek durumları incelerken algoritması sebebi ile daha iyi çözümlerin bulunabileceği durumları atlayabilir. Bu yüzden özellikle büyük problemlerde oldukça fazla adımda ve görece kötü sonuçlar bulabildiği söylenebilir. OVS’nin her adımının zaman, emek ya da para kaybı (ya da bunlardan birkaçı) anlamına geldiğini düşünülecek olursak OVS için “uygun sonuçlara erişmenin önemli olduğu, zaman, emek ve paranın önem arzetmediği durumlarda kolayca kullanılabilir” denilebilir. Fakat gerçek dünya problemlerine bakılacak olursa bu tarz bir durumun varolması pek de olası değildir. Sonuçta işletmeler, fabrikalar, akademik birimler ve öbekleme yapan tüm birimlerde zaman, emek ve para mutlaka önemlidir. Bu yüzden tüm olası durumlara bakmayacak, bu sayede de adım sayısını azaltacak yöntemler kullanmak daha mantıklı olacaktır. AVS yöntemi, OVS yöntemi gibi tüm olası durumları incelemez. Çözümde ilerleme yaparken tek tek her durumu inceleme ihtiyacı duymaz. AVS’nin çalışma mekanizması şu şekildedir : Bir makine öbeğini, mevcut öbek kolonları ile bir kez test ettikten sonra, o ana kadar elde edilmiş tüm sonuçlardan daha iyi bir sonuç elde edilmesi halinde, sözkonusu makine öbeğini mevcut öbekler arasına ekler. Ayrıca mevcut durumda yerine girdiği kolonu, kontrol edeceği kolonlar listesinden çıkarır ve aynı kolonu bir daha test etmeyecek şekilde ilerler. Bu şekilde aynı kolona geri dönüşü engellenmiş olur. Eğer makine öbeği, o ana kadar elde edilen çözümlerden daha iyi bir çözüme ulaşmayı sağlayamıyorsa denenecek kolonlar listesinden çıkarılır. AVS yönteminin adım sayısında OVS’den daha az olduğu görünmektedir fakat bu yöntemin de sakıncaları sözkonusudur. Örneğin AVS’nin kullanımında makine öbeğinin varolan çözümler arasından en iyiyi elde edememesi durumunda denenecek kolonlar listesinden çıkarılması zaman zaman yerel en iyi çözümlere takılmaya yol açar. En iyi çözüm elde edilir fakat bu çözüm 78 yalnızca belli bir kesim için (yerel) en iyi olur. Globalleşmesi durumu yoktur. Bunun önüne geçmek için de AVS’den elde edilmiş AVS-M yöntemi kullanılabilir. Bu yöntemin uygulanışı ile AVS yönteminin uygulanışı arasında genel olarak bir fark yoktur. Aralarındaki tek fark, AVS ile AVS-M yöntemlerinin başlangıç noktalarınun oluşturduğu kümelerdir. AVS-M için “farklı başlangıç noktaları ile AVS yöntemi uygulanır” denilebilir. Bu tez çalışmasında bu 3 yöntem (OVS, AVS ve AVS-M) dışında bir de Genetik Algoritma yöntemi kullanılmıştır. Genetik Algoritma lokal en iyi çözümlerden kurtulup global en iyi çözümü bulmak hedefiyle çözüm setindeki birçok farklı noktadan başlar (başlangıç popülasyonu). GA, elde edilen her iyi çözümün daha iyi çözümlere ulaşabileceği varsayılarak sürekli olarak daha iyi çözümleri çeşitli işlemlerle elde etmeye çalışır (çaprazlama, mutasyon). Bunları yaparken de rassallıktan yararlanarak, alternatif iyi çözüm sayısını en fazla sayıda tutmaya çalışır (rulet tekeri, rassallık). Bu çalışmada başlangıç kromozomları tamamıyla rassal olarak üretilmiş ve mutasyon olmadan tek noktalı çaprazlama kullanılmıştır. Literatürdeki örnek problemler ile kıyaslandığında elde edilen sonuçlar gösterilmiştir. Buna göre ulaşılabilecek en iyi gruplama verimliliği değerlerine, uygulanan GA ile ulaşılabilmiştir. GA, hesaplama verimliliği oldukça yüksek bir algoritma olduğundan, gerçek hayattaki çok ürünlü ve çok makineli kümelendirme problemlerinde rahatlıkla uygulanabilir. GA, en iyi çözümü bulmayı garanti etmez, ancak uygulanabilir farklı sonuçları kısa zamanda bulabilir. Bu da çoğu zaman GA’nın gerçek problemlerde uygulanabilmesi için yeterlidir. GA’nın önemli tek dezavantajı, ayarlanması gereken parametre değerlerinin fazlalığıdır. Bu nedenle GA kullanılırken farklı parametre değerleri arasından en iyi çözümü verecek parametre kombinasyonunun elde edilmesi için "deney tasarımı" yapılması gereklidir. Bu çalışmada p-median problemi, p-median probleminin çözüm yöntemlerinden OVS, AVS, AVS-M yöntemleri ve Genetk Algoritma yöntemleri incelenmiş ve bu yöntemler öbekleme problemlerine uygulanarak her biri için öbekleme problemlerinin çözümü ve verimlilikleri incelenmiştir. Her yöntem için uygulamalar yapılmış ve sonuç olarak kullanılan Genetik Algoritma ve AVS-M yöntemlerinin 79 literatürde bahsedilen veri setleri için ve hazırlanılan uygulama için en iyi çözüme ulaştığı görülmüştür. Hem AVS yöntemi hem de GA kullandığı algoritmada ürünlerin en yoğun olarak bulundukları makine öbeklerine atanmaları kısıtından dolayı ürün atamalarında zaman zaman verimliliği olumsuz etkileyecek şekilde düzenlemeler yapabilir ve en iyi çözümün elde edilmesine engel olabilir. 80 EKLER EK A: ÖBEKLEME İÇİN BİLGİSAYAR PROGRAMI Sub MatriseAl() Dim ArrDeger() As Double ShObek = ActiveSheet.Name Set Obek = Sheets(ShObek) IntObek = Val(InputBox("Kaçlı Öbeklemek Istersiniz =", "OBEK SAYISI")) Dim ArrObek() As Double Dim DigerKucuk() As Double Dim arr() As Double Dim Toplam() As Double Dim can As Double Dim ara, duzelt, yer, ObekListe As String For i = 2 To 1000 If Cells(2, i) = "" Then Exit For Next 'NoktaSayisi Kolon sayisi olarak saklanıyor.. NoktaSayisi = i ReDim ArrDeger(NoktaSayisi, NoktaSayisi) ReDim DigerKucuk(NoktaSayisi, NoktaSayisi) 81 ReDim ArrObek(IntObek + 1) ReDim arr(IntObek) ReDim Toplam(IntObek + 1) For Satir = 2 To 10000 If Obek.Cells(Satir, 1) = "" Then Exit For For Sutun = 2 To 10000 If Obek.Cells(1, Sutun) = "" Then Exit For ArrDeger(Satir - 1, Sutun - 1) = Obek.Cells(Satir, Sutun) Next Next ObekListe = "*" IptalKolon = "*" 'Ilk Obek sayısı kadar kolonu diziye atıyor.. For i = 1 To IntObek 'Satır numarası veriliyor.. ArrObek(i) = i ObekListe = ObekListe & ArrObek(i) & "*" Next 'Obeklemede denenmemiş tüm kolonları kontrol ediyor. For i = IntObek + 1 To Sutun - 2 82 'Obek içinde En küçük değer eskibul = 1 For k = 1 To IntObek Toplam(k) = 0 bul = InStr(eskibul + 1, ObekListe, "*") Eleman = Val(Mid(ObekListe, eskibul + 1, bul - eskibul - 1)) eskibul = Val(bul) 'Tum Satırlar için etkisini belirliyor... For j = 1 To Satir - 2 sayac = 0 'Obekteki değişen eleman dışındaki elemanlar için en küçük.. For l = 1 To IntObek If Eleman = ArrObek(l) Then Else can = ArrDeger(j, Val(ArrObek(l))) arr(sayac) = can sayac = sayac + 1 End If Next Diger = EnKucukBul(arr) DigerKucuk(j, k) = Val(Diger) 83 denenen = Val(ArrDeger(j, i)) cikan = Val(ArrDeger(j, ArrObek(k))) 'MsgBox ("DigerKucuk(" & j & "," & k & ")=" & Val(DigerKucuk(j, k)) & "-" & denenen & "-" & cikan) '*** 'denenen sayi hem cikan, hem de DigerKucuk' ten kucuk ise If denenen < cikan And denenen < DigerKucuk(j, k) Then ' en kucuk olan cikan mı idi..DigerKucuk değerleri içinde miydi kontrol et.. ' en kucuk ile farkı kadar iyileşme olur... If cikan <= DigerKucuk(j, k) Then Fark = cikan - denenen Else Fark = DigerKucuk(j, k) - denenen End If ' denenen sayi cikandan buyukse ElseIf cikan < denenen And cikan < DigerKucuk(j, k) Then ' en kucuk olan cikan miydi.. ' en kucuk ile farkı kadar bozulma olur... If denenen <= DigerKucuk(j, k) Then Fark = cikan - denenen Else 84 Fark = cikan - DigerKucuk(j, k) End If Else Fark = 0 End If Toplam(k) = Toplam(k) + Fark Next MsgBox ("Toplam(" & k & ")=" & Val(Toplam(k))) '*** Next sec = EnBuyukBul(Toplam) 'Pozitif saonuç elde ediliyorsa kolnoları değiştir.. If sec > 0 Then For m = 1 To IntObek If sec = Val(Toplam(m)) Then ara = "*" & Val(ArrObek(m)) & "*" duzelt = "*" & i & "*" yer = InStr(1, ObekListe, ara) If yer >= 1 Then Parca1 = Mid(ObekListe, yer + Len(ara), Len(ObekListe)) ObekListe = Mid(ObekListe, 1, yer - 1) & duzelt & Parca1 'ElseIf yer =1 Then 85 ' Parca1 = Mid(ObekListe, Len(ara), Len(ObekListe)) ' ObekListe = Mid(ObekListe, 1, yer - 1) & duzelt & Parca1 End If ArrObek(m) = i MsgBox ("Cikan " & m & " kolonu, giren " & i & "-" & ObekListe) IptalKolon = IptalKolon & m & "*" Exit For End If Next End If Next MsgBox (ObekListe) MachineGrup (ObekListe) End Sub Private Function EnKucukBul(ByRef Dizi() As Double) Dim kucuk As Double Dim i As Integer If IsArray(Dizi) Then kucuk = Dizi(0) For i = 1 To Val(UBound(Dizi)) - 2 If IsNumeric(Dizi(i)) Then 86 If kucuk > Dizi(i) Then kucuk = Dizi(i) End If End If Next i End If EnKucukBul = kucuk End Function Private Function EnBuyukBul(ByRef Dizi() As Double) Dim buyuk As Double Dim i As Integer If IsArray(Dizi) Then buyuk = Dizi(0) For i = 1 To Val(UBound(Dizi)) - 1 If IsNumeric(Dizi(i)) Then If buyuk < Dizi(i) Then buyuk = Dizi(i) End If End If Next i End If 87 EnBuyukBul = buyuk End Function Sub MachineGrup(Deger) Dim ArrMachine(1000) Dim Makine(1000) Dim Urun(1000) Dim ObekToplam(1000) ara = "*" baslangic = 2 sayac = 0 For i = 1 To 1000 yer = InStr(baslangic, Deger, ara) ArrMachine(i) = Val(Mid(Deger, baslangic, yer - baslangic)) baslangic = yer + 1 sayac = sayac + 1 If yer = Len(Deger) Then Exit For Next Obek = i For i = 1 To Obek ObekToplam(i) = 0 Next 88 For Satir = 2 To 10000 If Cells(Satir, 1) = "" Then Exit For enKucuk = Cells(Satir, Val(ArrMachine(1)) + 1) Makine(Satir - 1) = Val(ArrMachine(1)) Kolon = 1 For i = 2 To sayac a = Cells(Satir, Val(ArrMachine(i)) + 1) If enKucuk > a Then enKucuk = a Makine(Satir - 1) = Val(ArrMachine(i)) Kolon = i End If Next 'MsgBox (Satir - 1 & "-" & "kolon:" & Makine(Satir - 1) + 1 & " deger:" & Cells(Satir, Val(Makine(Satir - 1)) + 1)) 'Hangi Makine Hangi Obekte.. 'MsgBox (Satir - 1 & "-" & Kolon) 'SAYFA... 'Makine Öbeği Sheets("CLUSTER").Cells(Satir - 1, 1) = Kolon 'Makine 89 Sheets("CLUSTER").Cells(Satir - 1, 2) = Satir - 1 'Makine Öbeğinde Toplam Eleman ObekToplam(Kolon) = ObekToplam(Kolon) + 1 Next 'ReDim UrunObekDegerleme(Satir, i) Dim Product(100) As Double Pay = 0 Payda = 0 eksi = 0 Arti = 0 For i = 2 To 1000 If Sheets("PRODUCT&MACHINE").Cells(i, 2) = "" Then Exit For For k = 1 To Obek Product(k) = 0 Next 'Tum "1" olan kayıtları sayacak.. Tum = 0 For j = 2 To 1000 vvv = Sheets("PRODUCT&MACHINE").Cells(i, j) If vvv = "" Then Exit For 'Ürün x Makine matrisinde eşleşmeleri ara.. 90 If Sheets("PRODUCT&MACHINE").Cells(i, j) = "1" Then 'Her atama olan makinenin hangi obekte olduğunu tespit et ObekNo = Sheets("CLUSTER").Cells(j - 1, 1) Product(ObekNo) = Val(Product(ObekNo)) + 1 Tum = Tum + 1 End If Next 'En Buyuk deger kac.. Toplam = EnBuyukBul(Product) 'hangi öbekte gerçekleşiyor... 'eğer birden fazla ise yoğunluğun gerçekleştiği nokta..İlkini al!! sayac = 0 For k = 1 To Obek If Toplam = Product(k) And sayac = 0 Then Urun(i - 1) = k sayac = sayac + 1 End If Next 'MsgBox ("Ürün :" & i - 1 & "-Obek :" & Urun(i - 1) & "-Sıklık :" & Toplam) Sheets("CLUSTER").Cells(i - 1, 4) = i - 1 Sheets("CLUSTER").Cells(i - 1, 5) = Urun(i - 1) 91 Pay = Pay + Toplam eksi = Tum - Toplam + eksi Payda = Payda + Toplam Arti = ObekToplam(Urun(i - 1)) - Toplam + Arti Verimlilik = (Pay - eksi) / (Payda + Arti) 'MsgBox (Pay & "-" & eksi & "/" & Payda & "+" & Arti) Next MsgBox (Pay & "-" & eksi & "/" & Payda & "+" & Arti) MsgBox (Verimlilik) End Sub Sub ProductMachine() Set PM = Sheets("PRODUCT&MACHINE") Set mach = Sheets("SUMMARY") For machine = 2 To 100 If PM.Cells(1, machine) = "" Then Exit For For machine2 = 2 To 100 PM.Select If PM.Cells(1, machine2) = "" Then Exit For Toplam = 0 If machine = machine2 Then 92 mach.Cells(machine, machine2) = 0 GoTo Sonra End If For Product = 2 To 1000 If PM.Cells(Product, 1) = "" Then Exit For Deger = PM.Cells(Product, machine) deger2 = PM.Cells(Product, machine2) If Deger = deger2 And Deger = 1 Then 'Katsayiyi 2 yaptım... Toplam = Toplam - 2 End If If Deger <> deger2 Then Toplam = Toplam + 1 End If Next Sonra: mach.Cells(machine, machine2) = Toplam Cells(machine, machine2).Select Next Next Sheets("SUMMARY").Select End Sub 93 EK B : MATLAB PROGRAMI function [fitness_score] = fitness_scores(chromosomes, flows) ch_no = size(chromosomes,1); n = size(chromosomes,2); fitness_function=zeros(ch_no,1); for i=1:ch_no %her bir satir icin chromosomes da for j=1:n for k=1:j if chromosomes(i,j)==chromosomes(i,k) fitness_function(i,1)=fitness_function(i,1)-flows(j,k); else fitness_function(i,1)=fitness_function(i,1)+flows(j,k); end end end end worse_fit=max(fitness_function); %elitist strategy: en büyük fitness function luyu atama yapilmasin fitness_score=[]; for i=1:size(fitness_function,1) fitness_score(i,1)=fitness_function(i,1)-worse_fit; end sum_fit=sum(fitness_score); for i=1:size(fitness_function,1) fitness_score(i,1)=fitness_score(i,1)/sum_fit; end function [children] = crossover(selected,c) ch_no=size(selected,1); m=size(selected,2); 94 %tek point crossover random=rand(ch_no*200,1); crossover_position=zeros(ch_no-1,1); index=1; i=1; r=1; while index<ch_no+1 %her random number icin for j=1:m-1 i%aralik icin loop if random(i,1)>=0 & random(i,1)<(1/m) crossover_position(i,1)=1; children(index,:)=[selected(r,1:crossover_position(i,1)),... selected(r+1,crossover_position(i,1)+1:m)]; children(index+1,:)=[selected(r+1,1:crossover_position),... selected(r,crossover_position+1:m)]; end if random(i,1)>=j*(1/m) & random(i,1)<(j+1)*(1/m) crossover_position(i,1)=j+1; children(index,:)=[selected(r,1:crossover_position(i,1))... ,selected(r+1,crossover_position(i,1)+1:m)]; children(index+1,:)=[selected(r+1,1:crossover_position),... selected(r,crossover_position+1:m)]; end end class_set1=zeros(c,1); class_set2=zeros(c,1); for test=1:m for class=1:c if children(index,test)==class class_set1(class,1)=class_set1(class,1)+1; end 95 if children(index+1,test)==class class_set2(class,1)=class_set2(class,1)+1; end end end if size(find(class_set1),1)<c || size(find(class_set1),1)<c index=index; r=r; else index=index+2; r=r+1; end i=i+1; end function [best_chromosome,best_found_at, best_part, best]=genetic_algorithm(c,p_m,ch_no,generations, repetitions) %load production.txt; %production=production.txt; p=size(p_m,1); m=size(p_m,2); best=0; for nian=1:repetitions [chromosomes,cell]=initial_population(ch_no,p_m,c); %genetic algoritm begins with the cnstruction of input variables best_score=0; %for run=1:3 %best=1000000000000000; for(iter=1:generations) [fitness_score] = yeni_fitness(chromosomes,p_m,cell); [selected, max_fit,max_fitted_chromosome,cell,... max_fit_cell] = selection(chromosomes, fitness_score,cell) 96 if max_fit>best_score best_score=max_fit; best_found_at=iter; best_chromosome=max_fitted_chromosome; end [children,cell]=crossover2(selected,cell,max_fitted_chromosome); chromosomes=children; cell; %score(iter,1)=best_score; %iter=iter+1; end %plot(score); c=max(best_chromosome); chromosome=max_fitted_chromosome; [efficacy, clusters_of_parts]=deneme2(chromosome,c,p_m) if efficacy>best best=efficacy; best_chromosome=max_fitted_chromosome; best_part=clusters_of_parts; end score(nian,1)=best; %nian=nian+1; end function [chromosomes,cell]=initial_population(ch_no,p_m,c) %part machine binary matrix i olacak %machine to machine matrixin size i kadar chromozome sayisi olacak %chromosome length=m %number of cells desired=c %population yaratma isleminin baslangici %ch_no=m; m=size(p_m,2); 97 random=rand(ch_no*10,m); chromosomes=zeros(ch_no,m); n=1; kac=1; while kac < ch_no+1%kaçıncı kromozomdayim? for ch=1:m %kromozomun kacinci elemani? for i=0:(c-1) if 1-(c-i)*(1/c)<random(n,ch) & random(n,ch)<=(1/c)*(i+1) chromosomes(kac,ch)=i+1; end if i==0 if random(n,ch)==0.0000 chromosomes(kac,ch)=i+1; end end end end class_set=zeros(c,1); %kotu olusturulmus kromozomlarin cikarilmasi for test=1:m for class=1:c if chromosomes(kac,test)==class class_set(class,1)=class_set(class,1)+1; end end end if size(find(class_set),1)<c kac=kac; else kac=kac+1; end 98 n=n+1; end for o=1:ch_no cell(o,1)=c; end function [selected, max_fit,max_fitted_chromosome,cell,... max_fit_cell] = selection(chromosomes, fitness_score,cell) %weightleri belirlenmis her kromozom icin crossover a donmek icin %atamalarin yapilmasi ch_no=size(chromosomes,1); random=rand(ch_no,1); selected=zeros(ch_no,size(chromosomes,2)); [max_fit,ch_index]=max(fitness_score); max_fitted_chromosome=chromosomes(ch_index,:); max_fit_cell=cell(ch_index,1); fitness_score=[0;fitness_score];%indexler +1 olacak!!!! cumulative_fitness_score(1,1)=0; for i=2:size(fitness_score,1) cumulative_fitness_score(i,1)=cumulative_fitness_score(i-1,1)... +fitness_score(i,1); end for i=1:size(random,1)%her bir random sayı için for j=1:size(fitness_score,1)-1 if cumulative_fitness_score(j,1)<=random(i,1) & ... random(i,1)<cumulative_fitness_score(j+1,1) selected(i,:)=chromosomes(j,:); cell_selected(i,1)=cell(size(random,1),1); end if random(i,1)==1.0000 selected(i,:)=chromosomes(size(random,1),:); cell(i,1)=cell(size(random,1),1); end end end 99 KAYNAKÇA Süreli Yayınlar Özkan, Azzem , Esmeray : Murat “Bir Maliyet Kontrol Sistemi Olarak JIT Üretim Sistemi ve Muhasebe Uygulamaları”,C.Ü. İktisadi ve İdari Bilimler Dergisi, Cilt 3, Sayı 1, 2002. s.129. Sütçü,A., Tanrıtanır, E., : “Orman Ürünleri Endsütrisinde Benzetim Destekli Çalışmalar ve Bir Örnek Uygulama”, Süleyman Eroğlu, A., Koruca, H Demirel Üniversitesi Orman Fakültesi Dergisi, Seri : A, Sayı : 2, ISSN : 1302-7085, 2006. s.145. Güllü, Emin , Ulcay, Yusuf : “Kalite Fonksiyonu Yayılımı ve Bir Uygulama”, Uludağ Üniversitesi, Mühendislik-Mimarlık Fakültesi Dergisi, Cilt 7, Sayı 1, 2002. s.74. Ashayeri, J. , Heuts, R. : ,Tammel, B. “A Modified Simple Heuristic For The P-median Problem, With Facilities Design Applications”, Robotics and Computer-Integrated Manufacturing 21, 2005. s.452-457. Al-khedhairi, A. : “Simulated Annealing Metaheuristic for Solving P-Median Problem”, Int. J. Contemp. Math. Sciences, Vol. 3, , no. 28,2008. s.1358. Merino, E. Dominguez, . “Neural Network Algorithms for the p-Median ESANN'2003 proceedings - Perez, J. Munoz , Aragones, Problem”, J. Jerez European Symposium on Artificial Neural Networks Bruges (Belgium), d-side publi., ISBN 2-930307-03-X, 23-25 April 2003, s.2. 100 Kumar, Rajeev, Rockett : Peter “Multiobjective Genetic Algorithm Partitioning for Hierarchical Learning of High-Dimensional Pattern Spaces - A-Learning-Follows-- Decomposition Strategy”, IEEE Transactions On Neural Networks, VolL. 9, No. 5,September 1998, s.824. Karahan, Halil, Ayvaz, M. : Tamer, Gürarslan, Gürhan. “Şiddet-Süre-Frekans Bağıntısının Genetik Algoritma ile Belirlenmesi: GAP Örneği”, İMO Teknik Dergi,Yazı 290, 2008, s.4395. Değertekin, S. Özgür, : “Uzay Çelik Çerçevelerin Tabu Arama ve Genetik Ülker, Mehmet, Hayalioğlu, Algoritma Yöntemleriyle Optimum Tasarımı”, Sedat İMO Teknik Dergi,Yazı 259, 2006, s.3924. Köroğlu, Günay , Günel, : Tayfun “Sürekli Parametreli Genetik Algoritma Yardımı İle Geniş Bantlı ve Çok Katmanlı Radar Soğurucu Malzeme Tasarımı”, Havacılık ve Uzay Teknolojileri Dergisi Cilt 2 Sayı 1. Ocak 2005, s.72. Mahdavi, Iraj , Paydar, : “Genetic Algorithm Approach For Solving a Cell Mohammad Mahdi, Formation Problem in Cellular Manufacturing”, Solimanpur, Maghsud , Elsevier, Expert Systems with Applications, Heidarzade, Armaghan 2008, s.2,4. Cebesoy, T. : “Madencilikte Bilgisayara Dayalı Yapay Zeka Teknikleri Uygulamaları”, 14.Madencilik Kongresi / Türkiye 14th Mining Congress of Turkey, ISBN 975-395-150-7, 1995, s. 185. 101 Tosun, Nihat, Tosun, Gül : “Minimum Yüzey Pürüzlülüğü Koşulu İçin Delme Parametrelerinin, Genetik Algoritma İle Optimizasyonu”, F.Ü. Fen ve Mühendislik Bilimleri Dergisi, 16(2), 2004, s.307. İşçi, Öznur , Korukoğlu, : “Genetik Algoritma Yaklaşımı ve Yöneylem Araştırmasında Bir Uygulama”, Celal Bayar Serdar Üniversitesi İ.İ.B.F., Yönetim ve Ekonomi l Cilt:10 Sayı :2, 2003, s.194. Göloğlu, Cevdet, Arslan, : Yenal “Genetik Programlama İle İmalat İçin, Yüzey Pürüzlülük Modeli Geliştirilmesi”, Gazi Üniv. Müh. Mim. Fak. Der., Cilt 21, No 4, 2006, s.668. Gözütok, Sarper , Özdemir, : “Genetik Algoritma Yöntemi İle Su Şebekelerinde Hidrolik Kalibrasyonun Geliştirilmesi”, Gazi Osman N. Üniv. Müh. Mim. Fak. Der. Cilt 19, No 2, 125130, 2004, s.126. Keskintürk, Timur : “Diferansiyel Gelişim Algoritması”, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi Yıl: 5 Sayı: 9, Bahar 2006/1, s.87. Altunkaynak, B. , Esin, A. : “The Genetic Algorithm Method For Parameter Estimation in Nonlinear Regression”, G.Ü. Fen Bilimleri Dergisi 17 (2) 2004,s.48. 102 ISSN 1303 – 9709, Alataş, Bilal , Arslan, : Ahmet “Birliktelik Kurallarının Madenciliği İçin Genetik Algoritma ve Bulanık Küme Tabanlı Yeni Bir Yaklaşım”, F. Ü. Fen ve Mühendislik Bilimleri Dergisi, 17 (1), 2005, s.47. Güngör, İbrahim, : Küçüksille, Ecir Uğur “Küme Bölme Algoritmayla Problemlerinin Optimizasyonu: Genetik Türkiye İkinci Futbol Ligi Uygulaması”, Review of Social, Economic & Business Studies, Vol.5/6. s.388. Türkodlu, Ö. : “Genetik Algoritma Metodu İle Düzlemsel Yakın Alan Elde Etmek İçin Uygunluk Fonksiyonu Analizi”, Istanbul University Engineering Faculty Journal of Electrical & Electronics, , Volume:1, Number :2, 2001, s.262. Kulluk , S. , Türkbey, O. : “Tesis Yerleşimi Problemi İçin Bir Genetik Algoritma”, YA/EM’ 2004 Yöneylem Araştırması/Endüstri Mühendisliği – XXIV Ulusal Kongresi, Gaziantep – Adana, 15-18 Haziran 2004, s.2. Coşkun, A. : “Bir Optimizasyon Yöntemi : Genetik Algoritma – Molga Programı İle İterasyon Sayılarının Değerlendirilmesi”,Gazi Üniversitesi Endüstriyel Sanatlar Eğitim Fakültesi Dergisi Sayı :18, 2006, s.51. 103 Akansel, M. , İnkaya, T. : ”Akış Atölyesinde Kesikli Parti Bölme Problemi İçin Bir Genetik Algoritma Yaklaşımı”, YA/EM’ 2004 Yöneylem Mühendisliği – Araştırması/Endüstri XXIV Ulusal Kongresi, Gaziantep – Adana, 15-18 Haziran 2004, s.2. Vatandaş, Ergüven, Özkol, : “Kanat Dizaynında Dinamik İbrahim Ağ Genetik Yöntemlerinin Algoritma ve Birleştirilmesi”, itüdergisi/d mühendislik Cilt:5, Sayı:6, Aralık 2006, s.44. Özdağlar, D., Benzeden, : “Kompleks Su Dağıtım Şebekelerinin Genetik Algoritma ile Optimizasyonu”, İMO Teknik E., Kahraman, A. Murat Dergi, Yazı 253, 2006, s.3854-3855. Atabay, Şenay , Gülay, F. : “Genetik Algoritmalar ile Perdeli Yapı Sisteminin Maliyet Optimizasyonu”, itüdergisi/d Gülten mühendislik Cilt:3, Sayı:6, Aralık 2004, s.72,77. Keskintürk, Timur : “Permutasyon Kodlamalı Genetik Algoritmada, Operatörlerin Etkinliklerinin Araştırılması”, VI. Ulusal Üretim Araştırmaları Sempozyumu, İstanbul Kültür Üniversitesi, 22-23 Eylül 2006, s.1-7. Tunalıoğlu, N. , Öcalan, T. : “Üç Boyutlu Karayolu Güzargah Optimizasyonunda Karar Destek Sistemi Olarak Genetik Algoritmaların Kullanımı”, TMMOB Harita ve Kadastro Mühendisleri Odası 11. Türkiye Harita Bilimsel ve Teknik Kurultayı, Ankara, 2 – 6 Nisan 2007,s.5. 104 Hacıoğlu, A. , Özkol İ. : “Titreşimli Genetik Algoritma İle Hızlandırılmış Kanat profili Optimizasyonu”, Havacılık ve Uzay Teknolojileri Dergisi, Cilt 1 Sayı 1, Ocak 2003, s.1-10. Emel, Gül Gökay , Taşkın, : “Genetik Algoritmalar ve Uygulama Alanları”, Uludağ Üniversitesi İktisadî ve İdarî Bilimler Çağatan Fakültesi Dergisi, Cilt XXI, Sayı 1, s.129,136. Daş, R. , Türkoğlu, İ. , : “Genetik Algoritma Yöntemleriyle Internet Erişim Kayıtlarından Bilgi Çıkarılması”, SAÜ Fen Poyraz, M. Bilimleri Enstitüsü Dergisi 10. Cilt, 2. Sayı, 2006, s.67-72. Turğut, Arslan : “Sürekli Bir Kirişte Maksimum Momentlerin Genetik Algoritmalar İle Belirlenmesi”, DEÜ Mühendislik Fakültesi Fen ve Mühendislik Dergisi Cilt : 3 Sayı : 3 Ekim 2001, s.2,9. Er, Hakan , Çetin, M. Koray : “Finansta Evrimsel Algoritmik Yaklaşımlar : , Çetin, Emre İpekçi Genetik Algoritma Akdeniz Uygulamaları”, İ.İ.B.F. Dergisi (10), 2005, s.77. Küçük, Birgül , Keskintürk, Timur : “Montaj Hattı Dengelemede Genetik Algoritma Operatörlerinin Etkinliklerinin Araştırılması”, YA / EM 2006 – Yöneylem Araştırması / Endüstri Mühendisliği – XXVI. Ulusal Kongresi, Kocaeli, 3 – 5 Temmuz 2006, s.390-393. 105 Schleiffer, Ralf, : “Application of Genetic Algorithms for the Wollenweber, Jens , Design of Large-Scale Reverse Sebastian, Hans-Juergen, Networks in Europe’s Automotive Indsutry”, Golm, Florian, Kapoustina, Proceeding of the 37th Hawaii International Natasha Conferenece on System Sciences , 2004, s.2,6. Oktay, Selda , Engin, Orhan : “Scatter Search Method for Solving Industrial Problems : Literature Survey”, Logistics Journal of Engineering and Natural Sciences, 2006, s. 151. Saraç, Tuğba , Özçelik, : Feriştah ”Alternatif Hücrelerinin Rotaların Genetik Varlığında Algoritma Üretim Kullanılarak Oluşturulması ”, Endüstri Mühendisliği Dergisi, Cilt : 17, Sayı : 4, s.22-36. Chang, Yaw , Chen, Lin : “Solve the Vehicle Routing Problem With Time Windows Via a Genetic Algorithm”, Discrete and Continuous Dynamical Systems Supplement, 2007, s.240-249. James, Tabitha L. , Brown, : “A Hybrid Grouping Genetic Algorithm For The Cell B. Operations Research 34 ,2007, s. 2072-2074. Uyanık, Başar : Formation Problem”, Computers Evelyn C. , Keeling, Kellie & “A Thesis Submitted To The Graduate School Of Natural And Applied Sciences Of METU”, Master Of Science In Industrial Engineering, 2005, s.24-25. 106 Süresiz Yayınlar Hyer, Nancy Lea, : Capabilities of Group Technology, 1987, s.2. : Group Technology Production Methods In Wemmerlov, Urban Gallagher, C.C. , Knight, Manufacture , 1986, s.15. W.A Çelik, Mustafa : “Küreselleşme Hareketleri İçinde İşyeri Düzenlemesi ve Bir Matematiksel Model”, Dokuz Eylül Üniversitesi Sosyal Bilimler Enstitüsü Ekonometri Aanabilim Dalı Doktora Tezi, 1999, s.4. Doğan, M. Kaan : : “Optimum İmalat Programının Bilgisayar Benzeşimi”, İstanbul Üniversitesi Mühendislik Fakültesi Makine Mühendisliği Bölümü Bitirme Ödevi , 02.06.2000, s.13. Altunay, M. Akif : : “Çağdaş Maliyetleme Sistemlerinden Faaliyet Tabanlı Maliyetleme Sistemi ve Bir Tekstil İşletmesindeki Uygulaması”, Süleyman Demirel Üniversitesi Sosyal Bilimler Enstitüsü İşletme Ana Bilim Dalı Yüksek Lisans Tezi, 2007, s.4. Affenzeller, Michael , : Reconsidering the Selection Concept of Genetic Algorithms Wagner, Stefan : From a Population Genetics Inspired Point of View, 2001,s.3. Koza, John R : Genetic Programming on The Programming of Computers by Means of Natural Selection, 1992, s.17. 107 Taze, Barış : “Genetik Algoritmaların Uygulamaları”,Ankara Finansal Üniversitesi Sosyal Bilimler Enstitüsü İşletme Anabilim Dalı, Yüksek Lisans Tezi, 2004, s.10,12. Kalaycı, Tahir Emre : “Yapay Zeka Teknikleri Kullanan Üç Boyutlu Grafik Yazılımları İçin Extensible 3D (X3D) İle Bir Altyapı Oluşturulması ve Gerçekleştirilmesi”, Ege Üniversitesi Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, 2006, s.82-83. Belgin, Önder : Haberleşme Şebekelerinin Tasarımında Sezgisel Yaklaşımlar : Değişken Komşu Arama, Kuş Sürüsü Optimizasyonu, Optimizasyonu”, Gazi Karınca Kolonisi Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Yüksek Lisans Tezi, Temmuz 2007, s.30-31. 108