genetik algoritma

evrim teorisyenlerinin savlarını güçlendirdiği düşünülen bir algoritmadır. en basit anlatımıyla, bir problemin çözümünün gitgide evrimleşerek en iyiye doğru ulaşmaya çabalayan sanal bireylerin kromozomlarına yüklenmesidir. her birey, problem için uygunluk değeri olan bir çözüm önerisidir. en uygun çözümler çaprazlanıp daha iyi çözümler elde edilmeye çalışılır. umulmadık bir çeşitlilik yaratması için bazı çözümler üzerinde mutasyon da meydana getirilebilir. oldukça iyi olanlar ayıklanıp yanlışlıkla devre dışı bırakmanın önüne geçilebilir. buna elitizm denir. birer çözüme karşılık gelen bireylerden oluşan popülasyondan her nesilde bireyler uygunluk dereceleriyle doğru orantılı olarak seçilip çaprazlanarak yeni nesli oluşturacak bireyleri doğururlar. bu nokdada mutasyon ve elitizm uygulanır ve süreç başa döner. popülasyondaki en iyi çözüm kabul edilebilir olana dek döngü devam eder. genetik algoritmalarda önemli bir konu daha vardır: çözümler nasıl kodlanacak? bunu bir örnekle gösterelim. problem bir amaç fonksiyonunun maksimizasyonu olsun diyelim ki. x^2 gibi bir fonksiyon verilsin. çözümler 0-255 sayı aralığıyla sınırlandırılsın. yani çözüm önerileri örneğin; 1, 5, 27, 98, 163, 206 gibi bireyler olabilir. ancak bu şekilde bir doğrudan kodlama çaprazlama açısından kullanışlı olmaz. çünkü burada her birey sadece bir sayıyla temsil edilir. yani her bireyin bir kromozomu vardır. tıpkı gerçek genlerde olduğu gibi içsel kodlama yani genotipler dışsal özelliklerin yani fenotiplerin yansıttıkları gerçek değeri aynen analog olarak değil, dijital olarak "az sembollü uzun kelimelerle" kodlamalıdır. bunun için en yaygın kullanım ikili kodlamadır. bu durumda bireylerimiz 0-255 aralığını temsil edebilmek için 8 bitlik bir kodlamayla tarif edilecek, yani 8 kromozomdan oluşacaktır: 00000001, 00000101, 00011011, 01100010, 10100011, 11001110 gibi.

genetik algoritmanın aşamaları:
1-rasgele bireylerin üretilmesi
00000001, 00000101, 00011011, 01100010, 10100011, 11001110
2-bireyler için uygunluk değerlerinin hesaplanması
00000001 (1), 00000101 (25), 00011011 (729), 01100010 (9604), 10100011 (26569), 11001110 (42436)
3-çaprazlama için birey çiftlerinin uygunluk değerleri nispetinde seçilmesi
00000101 (25)
10100011 (26569)
----------------
11001110 (42436)
01100010 (9604)
----------------
4-her birey çifti için kromozom üzerinde çaprazlama noktasının seçilerek çaprazlama işleminin yapılması
000001/01 (25) 00000111 (49)
101000/11 (26569) 10100001 (25921)
----------------
110/01110 (42436) 11000010 (37636)
011/00010 (9604) 01101110 (12100)
----------------
5-mutasyon uygulanması
rasgele seçilen birey: 11000010 (37636)
rasgele seçilen mutasyon noktası: 11[0]00010 (37636)
mutasyon sonrası durum: 11100010 (51076)
6-elitizm uygulama
bir önceki neslin en iyi bireyi: 11001110 (42436)
7-yeni nesli oluşturma:
11100010 (51076)
00000111 (49)
10100001 (25921)
01101110 (12100)
11001110 (42436)
8-popülasyonun en iyi bireyinin uygunluğu yeterli mi? evet ise bitir hayır ise 2. aşamaya git.

not: 8. aşamada bir yeterlilik sorgulaması yapılmayabilir. bunun yerine verilen bir iterasyon sayısı kadar da 2-8 arası aşamalar işletilebilir.