Genetik Algoritmalar

Mehmet Ali Aytekin

“En azından 3 çeşit aramadan söz edilir:

1)Bilgisayarda saklı olan bir veriyi arama

2)Çözüme giden yolu arama(8 puzzle problemindeki gibi)

3)Çözümü arama(TSP gibi problemler için. GA için en iyi uygulama alanı)”

Arama uzayının çok büyük olduğu durumlarda tüm uzayı taramamız mümkün olmayabilir. Bu durumda idare eder gibi görünen bir sonuç işimize yarar. İşte tam bu noktada genetik algoritmalar devreye girer.
İlk önce temel kavramlara bir göz atalım:

“Her hücre DNA dizisi olarak adlandırılan kromozomlardan oluşmuştur. Bir kromozom özel proteinlerin kodu olan genlere bölünebilir. Genler ise kişisel özelliklerin belirlenmesinde rol oynar. Bir özelliğin farklı olabildiği durumlar alellik olarak adlandırılır.

Bir genin kromozom üzerindeki konumu ise lokus olarak adlandırılır.”

Şimdi ise Genetik algoritmaların temel elemanlarına bir göz atalım:
“Gen ve Kromozom”:Her çözüm belli bir alfabeye ait elemanlardan oluşan diziler şeklinde ifade edilir. Burada çözümün her harfine gen, çözümün tamamına ise kromozom denir. Örneğin bizim alfabe kümemiz 0 ve 1 olsun.5 genden oluşan kromozomumuz ise şöyle olabilir:1-0-0-1-0.
“Uygunluk Fonksiyonu”:Kromozomun problemi çözme yeteneğini ölçen bir fonksiyondur. Diyelim ki üzerinde uğraştığımız problem TSP olsun. Herhangi bir kromozomumuz ise 5-9-7-2-1-3-4-6-8 şeklinde olsun. Burada her rakam bir gendir ve

bu kromozom bir çözümü temsil eder. Bu problemde bizim uygunluk fonksiyonumuz birinci gen ile ikinci gen,ikinci gen ile üçüncü gen,n inci gen ile n+1. gen arasındaki uzakların toplamını bulan bir fonksiyondur. Sonuç, bu şehirlerden geçtiğimizde toplam yol uzunluğudur.

“Seçim Fonksiyonu”:O anki popülasyonda kimlerin bir sonraki nesli üreteceğine karar veren bir fonksiyondur.Çeşitleri vardır.İleride değineceğiz.
“Çaprazlama Fonksiyonu”:Var olan iki kromozomla yeni bir kromozomun nasıl üretileceğini belirler. Diyelim ki ilk kromozomumuz 5-9-7-2-1-3-4-6-8 olsun. İkinci kromozomumuz ise 8-5-7-6-4-1-9-2-3 olsun. İlk kromozomun ilk 4 genini, ikinci kromozomun ise son 5 genini alarak yeni bir kromozom oluşturalım (5-9-7-2-4-1-9-2-3) ve bu kromozomda tekrar eden genleri olmayan genler ile değiştirelim. Son durumda oluşan yeni kromozomumuz şu olacaktır:5-9-7-2-4-1-6-8-3.Çaprazlama için de çeşitli teknikler vardır.

“Mutasyon”:Belli zamanlarda popülasyondaki herhangi bir kromozomda meydana gelen değişimlerdir. 5-9-7-2-1-3-4-6-8 kromozomunda ilk gen ile son gen yer değiştirdiğinde (8-9-7-2-1-3-4-6-5) mutasyon meydana gelmiş olur. Mutasyon uygulamaktaki amaç populasyonun yerel optimuma takılmasını engellemektir. Mutasyonda 2 opt,3 opt, Lin-Kernighan gibi optimizasyon teknikleri de uygulanabilir.

Genetik algoritmalar doğal seleksiyon ve genetik teorisinden esinlenerek ortaya atılmış bir yaklaşımdır. Genetik algoritmalar, her biri çözüm adayı olan kromozom topluluğuyla-ki bu nüfus olarak adlandırılır- işe başlar. Kendine has işlemleri(mutasyon, çaprazlama vs…) kullanarak var olan popülasyondan yeni bir popülasyon üretmeye çalışır. Yani bu işlemlerin temel felsefesi var olan durumları kullanarak yeni durumlar elde etmektir.

Bir problem için genetik algoritmaları uygulamadan önce şu sorulara cevap vermemiz gerekecektir:

Kromozomlar nasıl temsil edilecek?

Uygunluk fonksiyonu ne olacak?

Kromozomlar yeni popülasyon üretmek için nasıl seçilecek?

Yeni üretim nasıl olacak?

Basit bir genetik algoritma şu aşamalardan oluşur:

1)Rasgele olarak kromozomlar topluluğu(popülasyon) üretilir.

2)Her bir kromozomun uygunluk değeri hesaplanır.

3)n nesil ilerleyene kadar şunlar tekrar edilir:

a)Ebeveyn olacak kromozomlar seçim fonksiyonuna göre seçilir.

b)Bunlar çaprazlanır.

c)Mutasyon gerekiyorsa gerçekleştirilir.

4)Yeni popülasyon eskisi ile değiştirilir.

5)2.adıma gidilir.

Bir sonraki yazımızda küçük bir problem üzerinde genetik algoritmalar nasıl çalıştırılır(Java uygulamasıyla) tartışacağız. Görüşmek üzere…

(Sorularınız,eleştirileriniz ve önerileriniz için:harezmiii@yahoo.com)