[ThinkerBeLL]

Genetik Algoritmaların Çalışma Prensibi

Genetik algoritmanın çalışmasını şöyle özetleyebiliriz:

GA_diyagram.PNG

Şekil 1. Genetik algoritmanın akış diyagramı


GA_adimlari.PNG
Tablo 1. Genetik algoritma adımları

İşlemleri adım adım açıklamak gerekirse:

Adım-1.
Bu adıma toplumda bulunacak birey sayısını belirleyerek başlanmaktadır. Kullanılacak sayı için bir standart yoktur. Genel olarak önerilen 100-300 aralığında bir büyüklüktür. Büyüklük seçiminde yapılan işlemlerin karmaşıklığı ve aramanın derinliği önemlidir. Toplum bu işlemden sonra rasgele oluşturulur.Kromozomun temsil ettiği çözüm hakkında bilgiyi herhangi bir yollla içermesi gerekir. En çok kullanılan kodlama ikili stringtir.

2li_kodlama.PNG
Tablo 2. İkili kodlama

Her kromozom bir ikili stringe sahiptir. Bu stringteki her bit çözümün belli karakteristiğini temsil eder, veya tüm string bir sayıyı temsil eder. Tabiki bir çok kodlama yolu vardır. Bu daha çok çözülen probleme bağlıdır. Mesela tam sayı veya reel sayı olarak kodlanabilir, bazen de bazı permutasyonları kodlamak kullanışlı olabilir.

1. Permutasyon kodlama
Düzenleme problemlerinde kullanılır. Satıcı gezici problemi veya Task Ordering Probleminde. Burada her kromozom sayıları bir sırada temsil eden bir sayılar stringidir.

P_kodlama.PNG
Tablo 3. Permutasyon kodlamalı kromozom örnekleri

Permutasyon kodlama sadece ordering problemleri için kullanışlıdır.

2. Değer kodlama
Reel sayılar gibi komplike değerlerin kullanıldığı problemlerde direk değer kodlanması kullanılabilir. Bu tip problemler için ikili kodlama işi çok zordur.

D_kodlama.PNG
Tablo 4. Değer kodlamalı kromozom örnekleri

Bu bazı özel problemler için çok iyidir. Diğer taraftan bu tip kodlama için probleme özel yeni bazı mutasyon ve çaprazlamalar geliştirmek lazımdır.

3. Ağaç kodlama
Bu, gelişen değişen programlar veya ifadeler için kullanılır (Genetik programlama). Ağaç kodlamada her her kromozom bazı nesnelerin, mesela fonksiyonlar ya da programlama dilindeki komutlar gibi, bir ağacıdır şeklinde verilebilir.

A_kodlama.PNG
Şekil 2. Ağaç kodlamalı kromozomlar örneği

LISP programlama dili bunu çok kullanır

Adım-2.
Kromozomların ne kadar iyi olduğunu bulan fonksiyona uygunlukfonksiyonu denir. Bu fonksiyon işletilerek kromozomların uygunluklarının bulunmasına ise hesaplama (evaluation) adı verilir. Bu fonksiyon genetik algoritmanın beynini oluşturmaktadır. Genetik algoritmada probleme özel çalışan tek kısım bu fonksiyondur. Uygunluk fonksiyonu kromozomları problemin parametreleri haline getirerek onların bir bakıma şifresini çözmektedir (decoding), sonra bu parametrelere göre hesaplamayı yaparak kromozomların uygunluğunu bulur. Çoğu zaman genetik algoritmanın başarısı bu fonksiyonun verimli ve hassas olmasına bağlı olmaktadır.

Adım-3.
Kromozomların eşlenmesi kromozomların uygunluk değerlerine göre yapılır. Bu seçimi yapmak için rulet tekerleği seçimi (roulette wheel selection) , turnuva seçimi (Tournament Selection) gibi seçme yöntemleri vardır. Örnek olarak bu çalışmada kullanılan rulet tekerleği seçimi aşağıda açıklanmıştır:

1- Tüm bireylerin uygunluk değerleri bir tabloya yazılır.
2- Bu değerler toplanır.
3- Tüm bireylerin uygunluk değerleri toplama bölünerek [0,1] aralığında sayılar elde edilir. Bu sayılar bireylerin seçilme olasılıklarıdır. Sayıların hepsi bir tabloda tutulur.
4- Seçilme olasılıklarını tuttuğumuz tablodaki sayılar birbirine eklenerek rasgele bir sayıya kadar ilerlenir. Bu sayıya ulaşıldığında yada geçildiğinde son eklenen sayının ait olduğu çözüm seçilmiş olur.

Bu yönteme rulet tekerleği seçimi ismi, bir daireyi, çözümlerin uygunluklarına göre dilimleyip çevirdiğimizde olacakların benzeşimi olduğu için verilmiştir.
Rulet tekerleği seçimi çözümlerin uygunluk değerlerinin negatif olmamasını gerektirir. Çünkü olasılıklar negatif olursa bu çözümlerin seçilme şansı yoktur. Çoğunluğunun uygunluk değeri negatif olan bir toplumda yeni nesiller belli noktalara takılıp kalabilir.

İkili kodlamada çaprazlama
Gen takası (crossover) genetik algoritmanın motoru kabul edilir. Basitçe olay iki ebeveyn kromozomun arasında belirlenen parçaların takasıdır.
Tek noktalı

tek_noktali.PNG
Şekil 3. İkili kodlamada tek noktalı çaprazlama

İki noktalı

2_noktali.PNG
Şekil 4. İkili kodlamada iki noktalı çaprazlama

Düzenli

duzenli.PNG
Şekil 5. İkili kodlamada düzenli çaprazlama

Aritmetik

aritmetik.PNG
Şekil 6. İkili kodlamada aritmetik çaprazlama

İkili kodlamada mutasyon

2li_kodlama_M.PNG
Şekil 7. İkili kodlamada mutasyon

Permutasyon kodlamada çaprazlama
Tek noktalı çaprazlamada bir nokta seçilir ilk ebeveynden bu permutasyonun kopyalandığı noktaya kadar,sonra ikinci ebeveyn okunur ve sayı çocukta hala yoksa o eklenir.

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) => (1 2 3 4 5 6 8 9 7)

Permutasyon kodlamada mutasyon

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Değer kodlamada çaprazlama
İkili kodlamadaki tüm çaprazlamalar kullanılabilir.

Değer kodlamada mutasyon
Reel değer kodlama için seçilen değere küçük bir sayı eklenir ya da çıkarılır.

(1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)

Ağaç kodlamada çaprazlama

A_kodlama_C.PNG
Şekil 8. Ağaç kodlamada çaprazlama

Seçilen düğümler değiştirilir. Operatorlar sayılar değiştirilir. Gen takası toplumda çeşitliliği sağlar. İyi özelliklerin bir araya gelmesini kolaylaştırarak en iyiye yaklaşmayı sağlar. Değiştirme kromozomun bir parçasının dışarıdan değiştirilmesi şeklinde tanımlanır. Değiştirme görünüşte genetik algoritmanın dayanak noktasıdır, ancak etkisi bir çözüm üzerindedir. Bu da yalnız başına başarılı olmasını zorlaştırır. İkilik dizilerde değiştirme rasgele bir bit’in değiştirilmesiyle sağlanabilir. Çok düşük bir değiştirme olasılığı toplumda bazı özelliklerin kaybolmasına neden olabilir. Bu da en iyi sonuçların bulunmasına engeldir. Ancak yüksek bir değiştirme olasılığı da eldeki çözümleri bozarak sonuca ulaşmayı zorlaştırır. Gen takası ve değiştirmenin olasılıkları için kesin bir sayı yoktur. Değiştirme (mutasyon) olasılığı 0.01-0.001, gen takası (cross-over) olasılığı 0.5-1.0 aralığında tavsiye edilir.

Adım-4.
Eski kromozomlar çıkartılarak sabit büyüklükte bir toplum sağlanır.

Adım-5.
Tüm kromozomlar yeniden hesaplanarak yeni toplumunun başarısı bulunur.

Adım-6.
Genetik algoritma defalarca çalıştırılarak çok sayıda toplum oluşturulup hesaplanır.

Adım-7.
Toplumların hesaplanması sırasında en iyi bireyler saklandığı için o ana kadar bulunmuş en iyi çözüm çözümdür. Genetik algoritmanın yaptığı işleri temelini akış diyagramı olarak Şekil 9'de görebiliriz:

GA_temel.PNG
Şekil 9. Genetik algoritmanın temeli

Basit bir genetik algoritma, L uzunluğundaki homojen bir çubuğun momentinin 0 (sıfır) olduğu noktayı bulmak için kurabiliriz.

L_Moment.PNG
Şekil 10. L uzunluklu çubuğun momenti

L uzunluğuna bağlı olarak ara uzunluk x1 ve x2 0 ile 255 cm arasında işaretsiz bir tamsayı alınacaktır. F(x)=x1.m1-x2.m2 minimum değeri, aynı zamanda uygunluk fonksiyonudur. Dolayısıyla özgül kütleleri aynı olduğundan, doğrudan uzunluklara bağlı olacaktır. Yani uygunluk fonksiyonunu daha basit bir şekilde F(x)=x1-x2=0 olarak verebiliriz. Burada x2=L-x1 olduğundan F(x1)=2.x1-L=0 alınabilir. Örnek basit seçildiğinden sonucun matematik bilgisine göre 127.5 cm olacağı açıkça görülmektedir. 0 ile 255 arasındaki sayıları gösterebilmek için 8 bit uzunluğunda bir bilgiye ihtiyacımız vardır.

0................ 00000000
255............ 11111111

İlk olarak başlangıç topluluğu bu sayılar arasından rasgele olarak seçilebilir. Bunun için 8 birey oluşturulsun (N=8). Bunlar {0, 40, 80, 120, 160, 200, 220, 255} alınırsa:

0................ 00000000
40.............. 00101000
80.............. 01010000
120............ 01111000
160............ 10100000
200............ 11001000
220............ 11011100
255.............11111111

Değerleri başlangıç topluluğu olarak belirlenir. Bireylerin uygunluk değerleri, sayının ondalık karşılığının uygunluk fonksiyonuna verdiği cevapla bulunabilir. Uygunluk değeri sayının alabileceği değerler ile orantılı olursa, bunun için max uygunluk değeri olarak 255 ve minimum olarak ta 0 uygunluk değeri alınmalıdır. Eğer elde edilen uygunluk değeri 255 ten çıkarılırsa max uygunluğa 255 sayısının karşılık düştüğü görülebilir.
Örnek:

x=00000000 için F(x)=255-ABS(255–0)=0
x=00101000 için F(x)=255-ABS(255–80)=80 şeklinde belirlenebilir.

GA_manuel.PNG
Tablo 5. GA' nın el ile uygulaması I

Bireylerin uygunluk değerlerinin rulete yansımasından kaç adet kopya oluşturulacağı veya hiç kopya alınmayacağı belirlenir. Yukarıdaki tabloya göre 80,120 ve 160 sayılarından 2 şer kopya alınacaktır. 0 ve 255 sayılarından hiç kopya alınmayacak ve diğer sayılardan 1 er kopya alınacaktır. Buna göre çaprazlama operatörü yardımıyla yeni bireyler üretmeden önce başlangıç topluluğu tekrar oluşturulmalıdır.

GA_manuel_II.PNG
Tablo 6. GA' nın el ile uygulaması II

Yukarıdaki işlemlerde, bir nesilden diğer nesle kromozomlar aktarılırken, uygun kromozomların iyi özellikleri tekrar üreme adımında kullanılarak en iyi kromozomlar elde edilebilir. Elle yapılabilecek bu örnekte üç nesil sonra çözüm olabilecek bireylerin çözüm uzayını yeterince daraltarak birbirlerine daha çok benzeyecekleri görülecektir.

[ThinkerBeLL]

Genetik Algoritmaların Kullanılma Nedenleri

Öncelikle niye diğer yöntemlerin kullanılmadığı belirtilmelidir. Denklem en iyilemesinde (optimization);

1. Türev-İntegral hesabına (calculus) dayananlar
2. Numaralamaya (enumeration) dayananlar
3. Rastgele aramalar (random searches)

olmak üzere üç tip çözümden bahsedilir.
Genetik algoritmaların yeri Şekil 1.'de görülebilir.

arama_metodlari.PNG
Şekil 1. Arama metodları

Türev-İntegral hesaplamalarına dayanan hesaplama yöntemleri çok derinlemesine çalışılmıştır. Bu yöntemler fonksiyonun türevinin köklerinin fonksiyonun en küçük ve en büyük değer veren noktaları olmasından yararlanır. Gerçek problemler için sıfır veren noktaları bulmak da ayrı bir problemdir.
Diğer bir yöntem ise alınan bir noktadan sadece yukarı ilerleyerek en iyi sonucu bulmayı hedefler. Tepe tırmanma (hill climbing) denen bu yöntem fonksiyon grafiğinin tepelerini tırmanır. Ancak çok sayıda dönme noktası içeren bir fonksiyonda çok sayıda tepe oluşur. Hangi tepenin en iyi çözüm olduğunu bilenemez. Numaralama yöntemleri ise oldukça alışılagelmiştir. Sürekli olan gerçel sayı aralıkları belli sayıda parçaya ayrılarak parçalar denenir. Ancak problemler böyle çözmek için büyük olabilir. Bu yöntemin biraz daha geliştirilmiş şekli Dinamik Programlamayla (dynamic programming) oluşturulur. Parçalar arasından iyi görünenler seçilir. Bu parçalar parçalara ayrılarak işlem tekrarlanır. Bu yöntem de tepe tırmanma yöntemi gibi yanlış tepeleri araştırabilir. Dinamik Programlama tepelerin olmadığı aralıklarda başarılı ve hızlıdır.
En iyilemenin;

• Bir işin daha iyi yapılması
• En doğru şekilde yapılması

olmak üzere iki amacı vardır.
Günümüzde rasgele aramaların kullanımı artmaktadır. Bu tip aramalar en iyilemenin daha iyi yapma amacını sağlamakta daha başarılıdırlar. İnsanların bilgisayarlardan genel beklentisi mükemmellik olduğu için bu tip aramalar başarısız görünebilir. Genetik algoritmalar klasik yöntemlerin çok uzun zamanda yapacakları işlemleri kısa bir zamanda çok net olmasa da yeterli bir doğrulukla yapabilir.

[ThinkerBeLL]

Genetik Algoritmaların Farkları

1. Genetik algoritma parametrelerin kodlarıyla uğraşır. Parametreler kodlanabildiği sürece fark etmez.
2. Genetik algoritma bir tek yerden değil, bir grup çözüm içinden arama yapar.
3. Genetik algoritma ne yaptığı konusunda bilgi içermez, nasıl yaptığını bilir. Bu nedenle bir kör arama (blind search) metodudur.
4. Genetik algoritmalar olasılık kurallarına göre çalışır. Programın ne kadar iyi çalışacağı önceden kesin olarak belirlenemez. Ama olasılıkla hesaplanabilir.

Şema Teorisi (Schemata Theorem)
Genetik algoritmalarda oluşan başarılı bireyler incelenirse, bu bireyler arasındaki benzerlikler bulunabilir. Bu benzerliklerden yola çıkarak şemalar oluşturulabilir. İkilik dizi kodlaması için aşağıdaki yöntem önerilebilir.
0, 1 ve # (‘#’ o konumda 0 veya 1 olmasının önemsiz olduğunu gösterir).
Örnek olarak ikinci ve dördüncü bitleri 1, altıncı biti 0 olan çözümlerin başarılı olduğu bir toplumda şu şema oluşturulabilir:

#1#1#0

Tablo 1. Şema

Bu şemaya uygun aşağıdaki ikilik diziler yazılabilir:

010100, 010110, 011100, 011110, 110100, 110110, 111100, 111110.

Görüldüğü gibi şemaların katılması ikilik dizilerle gösterilen arama aralığını büyütmektedir. Arama aralığının büyümesinin sonucun bulunmasını zorlaştırması beklenir ancak durum böyle değildir. Seçilim ve yeniden kopyalama ile iyi özellikler daha çok bir araya gelerek daha iyi değerlere sahip şemalara uygun çözümler elde edilir.
Genetik algoritma kendi içinde sanal olarak şemaları oluşturur. Toplumun bireyleri incelenerek bu şemalar ortaya çıkarılabilir. Genetik algoritmalar şemaları oluşturmak için toplum üyelerinin kodları dışında bir bilgi tutmaz. Genetik algoritmaların bu özelliğine içsel paralellik (implicit parallelism) denir. Her nesilde, iyiyi belirleyen şemalardaki belirsiz yada önemsiz elemanlar azalır. Böylece genetik algoritmalar sonuca doğru belli kalıplar içinde ilerler.

GA’nın Performansını Etkileyen Nedenler
Kromozom sayısı
Kromozom sayısını arttırmak çalışma zamanını arttırırken azaltmak da kromozom çeşitliliğini yok eder.
Mutasyon Oranı
Kromozomlar birbirine benzemeye başladığında hala çözüm noktalarının uzağında bulunuyorsa mutasyon işlemi GA’nın sıkıştığı yerden kurtulmak için tek yoludur. Ancak yüksek bir değer vermek GA’yı kararlı bir noktaya ulaşmaktan alıkoyacaktır.
Kaç Noktalı Çaprazlama Yapılacağı
Normal olarak çaprazlama tek noktada gerçekleştirilmekle beraber yapılan araştırmalar bazı problemlerde çok noktalı çaprazlamanın çok yararlı olduğunu göstermiştir.
Çaprazlamanın sonucu elde edilen bireylerin nasıl değerlendirileceği
Elde edilen iki bireyin birden kullanılıp kullanılamayacağı bazen önemli olmaktadır.
Nesillerin birbirinden ayrık olup olmadığı
Normal olarak her nesil tümüyle bir önceki nesle bağlı olarak yaratılır. Bazı durumlarda yeni nesli eski nesille birlikte yeni neslin o ana kadar elde edilen bireyleri ile yaratmak yararlı olabilir.
Parametre kodlanmasının nasıl yapıldığı
Kodlananın nasıl yapıldığı en önemli noktalardan biridir. Örnek vermek gerekirse kimi zaman bir parametrenin doğrusal yada logaritmik kodlanması GA’nın performansında önemli bir farka yol açabilir.
Kodlama gösteriminin nasıl yapıldığı
Bu da nasıl olduğu yeterince açık olmamakla beraber GA’nın performansını etkileyen bir noktadır. İkilik düzen, kayan nokta aritmetiği ya da gray kodu ile gösterim en yaygın yöntemlerdir.
Başarı değerlendirmesinin nasıl yapıldığı
Akıllıca yazılmamış bir değerlendirme işlevi çalışma zamanını uzatabileceği gibi çözüme hiçbir zaman ulaşmamasına neden olabilir.

[ThinkerBeLL]

Genetik Algoritmanın Matematiksel Modeli

1. Şema modeli
Şema modeli, ikili düzen kullanıldığında, { 0,1,* } alfabesi üzerinde tanımlı bir desen olarak da tanımlanabilir.

• Şema, bireyi değil bireyin özelliklerini kodlayan bir yapıdır.

Örnek:

***01**1 bireyin taşıdığı bir özelliği temsil eder.

• GA’ da bireyler, ikilik düzende sabit uzunluklu katarlar olarak ifade edilirler.
• Desende, 0 ve 1' ler tanımlayıcı bitler (defining bits) olarak adlandırılır.

2. Şema mertebesi
Şema Mertebesi tanımlayıcı bitlerin sayısıdır ve - order o[H] - olarak ifade edilir.
Örnek:

**0*11**1 ile ifade edilen H şemasının mertebesi: order o[H]=4

3. Tanımlayan uzunluğu
En sol ve en sağ tanımlayıcı bitler arasındaki uzaklık olarak ifade edilir.
Örnek 1:

011*1** ile ifade edilen H şemasının mertebesi 4,

Tanımlayan Uzunluğu defining length d[H] = 4'tür. Çünkü, ilk tanımlayıcı bit olan 0'ın pozisyonu 1, son tanımlayıcı bit olan 1'in katardaki pozisyonu 5 ve d[H]=5-1=4
Örnek 2:

0****** ile ifade edilen H şeması için tanımlayan uzunluğu;
d[H]=1-1=0'dır.

Eğer bir X katarının bit değerleri ve katardaki yerleri H şemasının tanımlayıcı bitleri ile aynı konumda ise, X katarı S şemasının bir örneğidir.
Örnek:

00011 ve 00110 katarları 00*1* şemasının örnekleridir.

[ThinkerBeLL]

Genetik operatörlerin şema üzerine etkileri

1. Çoğalmanın etkisi

cogalma_etkisi.PNG

2. Çaprazlamanın etkisi

caprazlama_etkisi.jpg

3. Mutasyonun etkisi

mutasyon_etkisi.PNG