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