GENETİK ALGORİTMALAR

Genetik Algoritma Kavramı

Genetik algoritmalar, karmaşık düzenli problemlerin çözümünü gerçekleştirmek amacıyla, kromozomların yeni diziler üretme esasını temel alan, sezgisel bir araştıma yöntemidir. Genetik algoritmalar, matematiksel fonksiyonların global optimizasyonunu hedeflerler. Genetik algoritmaları diğer araştırma yöntemlerinden ayıran özellik İse, bir çözüm seti ile başlandıktan sonra, geliştirme için biyolojik evrimi esas alan bir prosesin kullanılmasıdır. Bu prosesin sonunda da en iyi kromozoma ulaşma amaçlanmaktadır.Problemle ilgili parametreler, genler halinde bir araya gelerek kromozomu oluşturmakta; en iyi kromozoma ulaşma ise, genlerin kromozom içindeki dizilişini değiştirerek; yani, yeni nesiller yaratılarak gerçekleştirilmektedir. Genetik algoritmaların, problem çözümünde uygulanabilmeleri için, problemin çözüm uzayı olarak, her bir problemin mümkün çözümlerinden olan yapılardan (ya da organizmalardan) oluşan bir popülasyon ortaya konmaktadır. İlk neslin oluşması için, öncelikle belirli bir sayıda organizma seçildikten sonra, yeni bir neslin yaratılması için, mevcut nesilden seçilen aiie'lere bazı genetik oparatörler uygulanır. Burada "iyi çocuklar iyi aileden doğar" fikrine uygun olarak, mevcut nesil içinde yüksek uygunluk değerine sahip organizmaların aile olarak seçilme şansları da doğal olarak yüksektir.

Genetik algoritmaların özellikleri

Çeşitli problemlerin çözümünde kullanılan genetik algoritmlar, aşağıdaki özellikleri taşırlar.
a) Uygun çözümler için bir veya daha fazla "popülasyon" mümkündür.
b) Önceden bilinen çoklu çözümlerin özelliklerini bir araya getirerek, yeni uygun çözümler üreten bir mekanizmaya sahiptir.
c) Önceden bilinen bir çözümün düzenini rast gele (tesadüfi) bir şekilde değiştirerek, yeni uygun bir çözüm üreten bir mekanizmaya sahiptir.
d) Popülasyon içinden, öncelik vererek, ayrı çözümleri seçen bir mekanizmaya sahiptir.
e) Popülasyon içinden bazı çözümleri dışarı çıkaran bir mekanizmaya sahiptir.

Genetik algoritmaların sahip olması gereken koşullar

Genetik algoritmaların etkin bir şekilde kullanılabilmeleri için, aşağıdaki koşulların sağlanması gerekmektedir.
a) Araştırma uzayı parametreleri, ikili (0-1) sistemde veya alfabetik bir şekilde kodlanarak belirli bir uzunlukta kromozom-gen düzeni oluşturulmalıdır.
b) Uygun çözüm sayısını azaltmak için problemin amacı doğrultusunda bir uygunluk fonksiyonu kullanılmalıdır.
c) Paralel ve global araştırmaya imkân sağlanması açısından, araştırma uzayı içindeki her nokta taranmalıdır.
d) Bir araştırma uzayından diğerine bir gelişme sağlanabilmesi için, olasılıklı geçiş (değişim) kuralı kullanılmalıdır.

Genetik Operatörler

Genetik algoritmalardaki kromozom yapıların kopyalanması işleminde üç temel operatör kullanılmaktadır. 

Yeniden üretim (reproduction)
Her bireyi, bir nesilden diğerine aynen kopyalama işlemidir. Uygunluk derecesi yüksek olan kromozomlar üşütün nitelikli çocuk üretiminde kullanılmak üzere bu yöntemle çoğaltılırlar.

Çapraz değişim (crossover)
İki veya daha fazla kromozomdan (aile'den), yeni bir kromozom (çocuk) meydana getirme işlemidir. Burada da amaç, daha iyi niteliklere sahip çocuklara ulaşmaktır.

Dahili değişim (mutation)
Kromozom yapısı içinde değişikler yapma işlemidir. Mustasyon işlemi ile yeni uygun çözümler elde edilmeye çalışılır.

Nümerik Kodlama

Problemdeki parametreleri temsil eden, kromozom yapısı içindeki genlerin dizilişinin gösterimi, daha çok ikili sistem (0-1 sistemi) veya diğer rakamların da kullanılmasıyla gerçekleştirilmektedir. Rakamların ikili sistem dışında kullanımında, problemin paremetreleri gereği, sıralı veya sırasız rakamların birer defa kullanımının yanısıra, aynı rakamların birden çok kullanımına da rastlanmaktadır.

Çapraz değişim uygulamaları

Çapraz değişim ile ilgili olarak rastlanılan ilk uygulama şeklinde, önce kromozom yapı üzerinde rast gele bir ayrım noktası belirlenmektedir. Kromozonlar, çapraz değişim işleminde bu ayrım noktası öncesindeki gen yapısını aynen korurlarken, ayrım noktası sonrasındaki gen yapısını ise karşılıklı olarak değiştirmektedirler. Takip eden örnekte de görüleceği gibi, ayrım sonrası genleri (1100) ve (1010) karşılıklı olarak yer değiştirmiş.

Bazı uygulamalarda ise, iki ayrım noktası kullanılmaktadır. Ayrım noktalarının belirlenmesi ve karşılıklı değiştirilecek parçaların belirlenme işlemleri yine rast gele olmaktadır. Takip eden örnekte, iki ayrım noktası arasındaki (001) ve (011) genleri karşılıklı yer değiştirmiştir

Bazı çapraz değişim uygulamalarında, ailedeki kalıtsal özelliklerin çocuğa taşındığı durumlara ratslanmaktadır. Tahip eden örnekte ile işaretlenen kalıtsal özelliklerin, çocuk (A)'ya ne şekilde taşındığı gösterilrnektedir.

Bazı uygulamalarda, çapraz değişimin hemen arkasında bir onarma işlemine ihtiyaç olmaktadır. Bunu, takip eden örnekte görebiliriz.

iki ayrım arasındaki genler karşılıklı değiştirildiğinde, elde edilen sonucun uygun olmadığı açıkça gözükmektedir. Takip eden örnekteki onarma
işleminde, birinci sıradaki genler karşılıklı değiştirilerek uygunluk sağlanmıştır.

Görüldüğü gibi çapraz değişimle ilgili çok çeşitli uygulamalar söz konusudur. Burada önemli olan uygunluk derecesi yüksek olan aileleri bir araya getirerek, uygunluk derecesi daha yüksek çocuklar elde etmeye çalışmaktır. Bu arada, uygunsuz olan sonuçların ortaya çıkması durumunda, onarım işlemi uygulanmalıdır.

Dahili değişim (mutasyon) uygulamaları

Kromozom yapısı üzerindeki dahili değişim, genellikle rast gele bir şekilde belirlenen bir gen'in değiştirilmesiyle gerçekleştirilmektedir. Yani, 1 ise O'la veya 0 ise 1'le değiştirilmektedir.
İkili sistem yerine, problemin paremetreleri gereği, sıralı veya sırasız rakamların birer defa ya da aynı rakamların birden çok kullanımının söz konusu olduğu durumlarda, rast gele belirlenmiş herhangi bir gene ait rakam, yine rast gele belirlenmiş diğer rakamla yer değiştirmektedir. Takip eden örnekte ise, kromozomda ile işaretlenmiş gen rast gele bir şekilde belirlenerek değiştirilmiş, böylelikle mutasyon işlemi tamamlanrnıştır.

Bazen de kromozom üzerinde iki gen rast gele seçilerek, karşılıklı olarak yer değiştirmeleri sağlanır. Takip eden örnekte, 3. ve 8. sıradaki genler rast gele seçilerek, yerleri değiştirilmiştir.

Bazı uygulamalarda ise, rast gele seçilen gen bulunduğu sıradan alınarak, yine rast gele olarak belirlenen başka bir sıradan yapıya dahil edilir.
Takip eden örnekte de gösterildiği gibi, 7. Sırada bulunan gen (2), sırasından çıkarılarak 1. Sıradan tekrar yapıya dahil edilmiştir.

Alfabetik Kodlama

Prablemdeki parametreleri temsil eden, kromozom yapısı içindeki genlerin dizilişinin gösterimi, alfabetik sembollerin kullanılmasıyla da gerçekleştirilmektedir. Bu gösterim şeklinde, rakamlarla gösterim şeklinde de olduğu gibi, sıralı veya sırasız harflerin birer defa ya da birden çok kullanımına rastlanmaktadır.
Çapraz değişim ile ilgili uygulamalar incelendiğinde, en çok rastlanı- lanların, takip eden dört örnekteki gibi olduğu görülecektir.
Takip eden örnekte, tek ayrım noktasının söz konusu olması durumundaki çapraz değişim gösterilmektedir. Görüldüğü gibi, Aile (1)'den alman (ABC) genleri, Çocuk'ta aynı sırada ve aynı pozisyonda yer alırken; (EHDGH) genleri ise, Aile (2)'den alınarak yine aynı sıra ile sıralanmaktadır.

iki ayrım noktasının olması durumunda, takip eden örnekte de görüldüğü gibi, Aile (1)'den alınan (AB) ve (GH) genleri aynı pozisyonda Çocukta da yer alırken; Aile (2)'den alınan diğer genler (EDCF) de aynı sıra içersinde Çocuk'ta da yer almaktadır.

Yine iki ayrım noktasının olması durumunda, ancak bu defa Aile (1)'den alınan (CDEF) genleri aynı pozisyonda olmak üzere Çocuk'ta yer alırken; Aile (2)'den alınan diğer genler de aynı sırada Çocuk'ta yer almaktadır.

Takip eden örnekte ise, Aile (1)'den rast gele seçilen işaretli genler, Çocuk'ta kalıtımsal olarak ayın pozisyonlarda yer alırken; Aile (2)’den alınan diğer genler (ADGF) de, kalan pozisyonları yine aynı sırada doldurmuştur.

Dahili değişim (mutasyon) uygulamaları

Dahili değişim (mutasyon) ile ilgili uygulamalar incelendiğinde, en çok rastlanıîanların, genellikle takip eden dört örnekte gösterildiği gibi olduğu görülecektir. Takip eden ilk örnekte, rast gele seçilen iki komşu genin, karşılıklı olarak değiştirilmesiyle mutasyon gerçekleştirilmektedir.

Takip eden diğer örnekte de gösterildiği gibi rast gele seçilen iki gen, karşılıklı olarak da değiştirilebilmektedir.

ilk iki örneğin özel bir durumu olarak nitelendirebileceğimiz üçüncü örnekte, üç gen rast gele seçilerek, yine rast gele sırada yeniden sıralanmaktadır.

Takip eden bu son örnekte ise, rast gele geçilen bir gen, yine rast gele bir şekilde seçilen poziyonda araya sokulmakta; değer genler ise ok istikametinde kaydırılmaktadır.

Değerlendirme

Yeniden üretim (reproduction), çapraz değişim (crossover) ve dahili değişim ya da mutasyon (mutitation) aşamalarının her tamamlanışında,
sonuçların öncekilerle karşılaştırılması gerekmektedir. Buradaki amaç en iyi kromozomu elde etmek; başka bir ifade ile, en iyi çözüme ulaşmaktır. Bu nedenle, her çevrimde elde edilen yeni kromozomların uygunluk dereceleri belirlenerek, sıralamaya dahil edilirler. En iyiler "Aile" görevi ile yeni nesil üretimine devam ederek, daha iyi nitelikli "çocuk" elde edilmesine çalışırlar. Bu süreç, amaç gerçekleşinceye kadar devam eder.

Genetik Algoritmaların Kullanım Alanları
Genetik algoritmalar, özellikle 1985 yılından sonra, gittikçe artan bir ilgiyle geniş bir kullanım alanına sahip olmaya başlamıştır. Bu kısımda özellikle son yıllarda gerçekleştirilen genetik algoritma uygulamaları tanıtılmaya çalışılmıştır.

GA'lann doğrusal olmayan tam sayılı programlamada kullanımı
Bu konuda yapılan çalışmalara, Yokota ve arkadaşlarının, 1995 yılında yayınlanan iki makalesinde rastlan maktadır. Bu çalışmalarda, optimum sistem güvenilirliği ile ilgili doğrusal olmayan tam sayılı programlama problemi, aralık katsayıları kullanılmadan; doğrudan, amaç fonksiyonunun doğrusal olmama durumu da korunarak, genetik algoritmaların kullanılmasıyla çözülmüştür.

GA'ların Hücresel imalat problemlerinde kullanımı

Bu konuda yapılan çalışmalardan bir tanesinde (1996), Joines ve arkadaşları (Culbreth & King), hücresel imalat tasarımı probleminin çözümünde, tam sayılı programlama ve genetik algoritmaları beraberce kullanmışlardı r(JolneS). Hwang ve arkadaşı (Sun) ise yine 1996 yılında yayınlanan makalede, hücre oluşumu probleminin çözümü için, genetik algoritma tabanlı, iki fazlı sezgisel bir çözüm önermişlerdir.

GA'lann motaj hattı dengeleme problemlerinde kullanımı
Bu konuda, Gen ve Tsujimura ile arkadaşlarının Gerçekleştirdikleri çalışmalarla ilgili olarak 1995 yılında yayınlanan makalelerinde; her bir iş istasyonundaki toplam işlem zamanlarını minimize etmeyi hedefleyen genetik algoritma amaç fonksiyonu ile bulanık küme mantığı beraberce kullanılarak, montaj hattı dengeleme problemlerinin çözümü gerçekleşti rilmiştir.

GA'lann yerleşim (layout) problemlerinde kullanımı
Yerleşim konusunda çalışma yapan Cheng ve arkadaşlarının (Gen & Tosowa) 1995 yılında yayınlanan makalelerinde, makinaların dairesel olarak yerleştirildiği ve malzeme hareketinin tek bir yöne doğru gerçekleştirildiği durum ile ilgili problemin, genetik algoritmalar ile sezgisel bir yöntem kullanarak çözülebileceğini göstermişlerdir(Cheng). Yerleşim konusundaki bir diğer çalışma ise Gen ve arkadaşları tarafından 1995 yılındaki makalelerinde sunulmuştur. Bu makalede, makinalar arası toplam taşıma maliyetlerinin minimize edilmesinin hedeflendiği, çok hatlı makine yerleşim problemi, bulanık küme mantığı ile genetik algoritmalar kullanılarak çözülmüştür.

GA'lann atama problemlerinde kullanımı
Bu konuda araştırma yapan Chu & Beasly, 1996 yılında yayınlanan makalelerinde, minimum maliyetli atamanın hedeflendiği problem için genetik algoritmaların kullanıldığı bir çözüm önermişlerdir(Chu). Bu konudaki diğer bir çalışma da, Tate ve Smith tarafından 1994 yılında yayınlanan makalelerinde sunulmuştur. Bu çalışmada, kuadratik atama probleminin çözümü genetik algoritmalar ile gerçekleştirilmiştir(Tate). Yine bu konudaki başka bir çalışmada, Zhao ve arkadaşları 1995 yılında yayınlanan makalelerinde, iş istasyonu atama problemi (ve robot seçimi) için genetik algoritmaları kuilanmışlardır.

GAİarın sıralama problemlerinde kullanımı
Bu konuda yapılan çalışmalarda, Reeves 1994 yılında yayınlanan makalesinde, genetik algoritmaları n-adet iş ve m-adet makine'nin söz konusu olduğu akış atölyesi sıralama probleminin özümünde kullanılmasını tanıtmıştır. Bir başka çalışmada ise, Yip-Hoi ve Dutta, 1996 yılında yayınlanan makalede, bir tezgahın iki farklı talaş kaldırma işlemi yapabilmesi durumunda, proses planlamadaki sıralama probleminin çözümü için genetik algoritmaları kullanmışlardır. Kim ve arkadaşlarının (Hyun & Kim), karışık model montaj hatlarındaki sıralama problemi için, 1996 yılında yayınlanan makalelerinde, önerdikleri genetik algoritmalar yaklaşımı, büyük çaplı sıralama problemlerinin çözümünde, makul bir hesaplama süresi içinde optimuma yakın sonuçlar verrnektedir. Yine aynı konuda gerçekleştirilen bir diğer çalışmada da, Leu ve arkadaşları (Matheson & Rees) tarafından gerçekleştirilmiştir. Bu araştırma ile ilgili olarak 1996 yılında yayınlanan makalede, kullanılan yapay zeka tabanlı genetik algoritma yöntemi ile iyi bir sonuç elde edildiği vurgulanmaktadır. Bir başka çalışmada ise Rubin ve Ragatz, tek makina-n-adet iş, sıralama probleminin çözümü için 1994 yılında yayınlanan makalelerinde, önerdikleri genetik algoritmalar yaklaşımının, dai- sınır algoritması kadar iyi sonuç vermese de, kullanımını tavsiye etmektedirler. Bir diğer çalışmada ise Usher ve Bovvden, 1996 yılında yayınlanan makalelerinde, bilgisayarla bütünleşik proses planlamada operasyon sıralama pobieminin çözümü için genetik algoritmaların kullanılması ile iyi bir performans sağladıklarını vurgulamaktadırlar.

GA’ların çizelgeleme problemlerinde kullanımı
Bu konuda yapılan çalışmalarda, Chen ve arkadaşlarının (Nepalli & Aljaber) 1996 yılında yayınlanan makalelerinde, akış atölyesi çizelgeleme probleminin çözümü için genetik algoritmalar esaslı sezgisel bir yöntem önerilmiştir. Yine bu makaledeki uygulamada, genitik algoritmaların çizelgeleme problemlerinde kullanımının (daha da geliştirilebilir) iyi sonuçlar verdiği vurgulanmaktadır. Bir başka çalışmada ise, Murata ve arkadaşları (ishibuchi & Tanaka) 1996 yılında yayınlanan bir makalelerinde, akış atölyesi çizelgeleme probleminin çözümü için iki hibrit genetik algoritma önerilmiştir. Aynı ekibin bir başka makalesinde ise, bu defa çok- amaçlı genetik algoritmaları, akış atölyesi çizelgeleme probleminin çözümü için önermektedirler. Çok-amaçlı genetik algoritmaların; tek-amaçlı genetik algoritmalardan ve Schaffer'in önerdiği VEGA’dan (Vector Evaluated Genetic Algorithm) daha iyi sonuç verdiği vurgulanmaktadır. Çizelgeleme konusunda yapılan bir başka çalışmada ise, Sakawa ve arkadaşları (Kato & Mori) 1996 yılında yayınlanan makalelerinde, uygulanan genetik algoritmaların, çözümü istenen probleme uygun olması gerektiğini belirterek; esnekliğin göz önüne alındığı, uygun bir genetik algoritmayı, bir işleme merkezindeki çizelgeleme problemi için önermişlerdir. Croce ve arkadaşlarının (Tadei & Volta) yaptığı çalışma ise, sipariş atölyesi çizelgeleme probleminin çözümü ile ilgilidir. 1994 yılında yayınlanan makalelerinde önerdikleri genetik algoritmanın, gerek önceki GA uygulamaları gerekse de diğer bazı sezgisel yöntemlere üstünlüğü vurgulanmaktadır. Bir diğer araştırmada, Sikora tarafından yapılan çalışma 1996 yılında yayınlanan makalesinde tanıtılmıştır. Bu çalışmada, parti hacmi ve sıralama kararlarını beraberce içeren bir çizelgeleme problemi üzerinde durulmuştur. Önerilen genetik algoritma ile bu zor problemin çözümü gerçekleştiril-
miştir.

GA'lann diğer kullanım alanları
Bu makalede tanıtma imkanı bulunamayan daha bir çok konuda da, genetik algoritmaların kullanımına rastlanmaktadır. Bunlar, bilgisayarla bütünleşik tasarım, gezgin-satıcı problemi, tamir-bakım politikası, tahmin yöntemleri, dağıtım ve transport poblemleri, Araç-rota problemleri, Paketleme problemleri ve vb. gibi konulardır.