Genetik Algoritmaların Çalışma Prensibi
Genetik algoritmanın çalışmasını şöyle özetleyebiliriz:
Şekil 1. Genetik algoritmanın akış diyagramı 
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.
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.
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.
Tablo 4. Değer kodlamalı kromozom örnekleri
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.
Şekil 2. Ağaç kodlamalı kromozomlar örneği
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ı
Şekil 3. İkili kodlamada tek noktalı çaprazlama
Şekil 4. İkili kodlamada iki noktalı çaprazlama 
Şekil 5. İkili kodlamada düzenli çaprazlama 
Şekil 6. İkili kodlamada aritmetik çaprazlama
İkili kodlamada mutasyon
Ş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
Ş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:
Şekil 9. Genetik algoritmanın temeli
Ş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.
Tablo 5. GA' nın el ile uygulaması I
Tablo 6. GA' nın el ile uygulaması II
