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.

optimizasyon metodudur, severiz. en basit tanımı saldım çayıra mevlam kayıra'dır.

Yeterince büyük veri tabanı oluştur, koşulları ayarla ve gerisini zamana bırak. Kendi işini kendi yapan algoritma.

Aşağıdaki adımlar uygulanarak oluşturulur:
1.Başlangıç popülasyonunu rastlantısal olarak üret.
2.Popülasyon içindeki tüm kromozomların amaç fonksiyonu değerlerini hesapla.
3.Tekrar üreme, çaprazlama ve mutasyon operatörlerini uygula.
4.Oluşturulan her yeni kromozomun amaç fonksiyonu değerlerini bul.
5.Amaç fonksiyonu değerleri kötü olan kromozomlar popülasyondan çıkar.
6.3-5 arasındaki adımlar tekrar et.

evrim teorisinin esaslarını*** kullanarak, çözülmesi geleneksel yollarla çok zor ya da imkansız olan bir problem için bize en güçlü sonucu ya da sonuçları üreten algoritma. problemin zorluğuna göre bilgisayar saatlerce loop'a girebilir. verdiği sonuçlar diğer optimizasyon yöntemlerine göre çok daha iyidir. tercih sebebidir*.

(bkz: sexual selection)

kısaca bir tanım yaparsak genetik algoritma (ya da kısaca ga), biyolojik evrimi, problem çözücü bir strateji olarak taklit eden bir programlama tekniğidir. çözülmek üzere ele alınan belli bir problem için ga’ya, belli bir tarzda kodlanmış potansiyel çözümler ile birlikte uygunluk fonksiyonu adı verilen ve her olasılığı, niceliğine dayanarak değerlendiren bir metrik girilir. bu olasılıklar, işe yaradığı önceden de bilinen çözümler olabilir, bu durumda ga’nın amacı onları geliştirmektir ama genellikle rastgele bir şekilde oluşturulurlar.

ga her olasılığı, uygunluk fonksiyonuna göre değerlendirir. rastgele bir araya getirilmiş olasılıklardan oluşan bir havuzda, tabii ki büyük bir kısmı hiç işe yaramayacak ve onlar silinecektir. yine de, sadece şansın yardımıyla, ufak bir kısmı umut vaadedebilir – problemin çözümüne dair zayıf ve kusurlu bile olsa, bir etki edebilirler.

bu umut vaadeden olasılıklar elde tutulurlar ve üremeleri sağlanır. bir çok kopyaları çıkartılır ama bu kopyalar mükemmel değildir; kopyalama sürecinde, rastgele değişiklikler yapılır. bu dijital döller daha sonra, yeni bir olası çözümler havuzu oluşturarak, bir sonraki nesile geçerler ve ikinci bir uygunluk değerlendirmesinden geçerler. kodlarında yapılan değişiklikler sonucunda, durumlarında bir ilerleme olmayan ya da daha da kötü olmuş olan olası çözümler yine silinirler ama tekrar, sadece şans faktörüyle, popülasyona sokulmuş olan rastgele varyasyonlar, kimi bireyleri onları daha iyi, daha eksiksiz ya da eldeki probleme daha etkili bir çözüm olacak şekilde geliştirmiş olabilir. yine, bu, galip gelen bireyler seçilir ve bir sonraki nesile, rastgele değişikliklerden geçirilerek kopyalanırlar ve süreç tekrar eder. ümit edilen, popülasyonun, ortalama uygunluğunun, her yeni denemede artacağı ve süreci yüzlerce ya da binlerce kez tekrar ederek probleme, en iyi çözümlerin bulunacağıdır.

insanoglunun gercek boyutta komlex problemleri cozmedeki acizligini kanitlayan kimine gore muhtesem kimine gore ise sinirli problem cozme teknigi. alternatif cozum sayisinin bir bilgisayar icin toplam cozum suresi bakimindan ihtiyaclari karsilamayacak durumda oldugunda ise yaradigi iddie edilen fakat en iyi cozumu vermesi durumu garanti olmayan yaklasimdir. kor bir strateji ile ilerler. en iyi cozume ulasmada eger hirsli degilsek yeterli bir cozum metodudur.

optimizasyon algoritmalarından metaheuristic sınıfına dahil parametrik bir çözüm aracıdır. (bkz: #20245445)

bir başlangıç çözümü ile uygun çözüm oluşturarak başlanması elzemdir. çeşitli operatörler (çaprazlama, mutasyon) kullanılarak rassal çözümler üreterek sürekli en iyiyi seçmeye dayalı strateji izler.

mesela sözlük bunun için güzel bir örnek olabilir. diyelim ki sözlük 100 kişi ile başladı ve bu 100 kişinin o an itibariyle en iyi yazarları. 100 sayısı hiç değişmeyecek öncelikle, sabit 100 kişi (probleme ve operatör seçimine göre değişebilir).
iyilik/en iyileme ölçütü de verilen pozitif oy ve favori ekleme olsun.

sözlüğün en kötü yazarları (oylama ile) belli dönemlerle yazarlıktan çıkarılarak yeni yazarlar sözlüğe alınıyor. bu işlemler belli bir süre tekrarlanarak devam ettiriliyor. ne olacaktır? hep en kötüleri popülasyondan çıkarıp, yeni yazarları sözlüğe dahil ederek zamanla 100 yazarın olabilecek en iyi yazarlar olduğunu garanti edilmiş olunacaktır.

genetik algoritma'nın her zaman optimum çözümü bulamadığını da hatırlatmak gerekir güncel problemler için. en iyiye yakın çözümler rahatlıkla diyebiliriz ama.
normal hesaplama taktikleri ile veya bilgisayarlarla çok uzun sürelerde çözülebilecek problemler genetik algoritma ile saniyeler içinde çözülebilir. rassallık (rastgelelik) en önemli hususudur bu algoritmanın.

yani rassal seçim stratejisine dayalı en iyileme diyebiliriz.

gece gece de bilgi amaçlı entry kasmak istemediğim için kolay anlatmaya çalıştım. anlamayanlar veya üzerinde çalışmak isteyenler irtibat kurabilir.

doğal evrimsel sürece benzer bir şekilde çalışan arama ve en iyiye döndürme yöntemidir. kompleks, çok boyutlu arama uzayında en iyinin hayatta kalması ilkesine göre bütünsel en iyi çözümü bulmaya çalışır. dil işlemede* çok sık kullanılır.
araştırmalara göre insan zekâsının doğrudan kavramlarla düşünmediği, dil ile düşündüğü, dil kodları* ile kavramlar arasında bağlantı kurduğu keşfedildi.bu sayede insan aklı kavramlar ile düşünen hayvan beyninden daha hızlı işlem yapabilmekteydi ve dil dizgeleri olan cümleler yani şablonlar ile etkili bir öğrenmeye ve bilgisini soyut olarak genişletebilme yeteneğine sahipti. hepsinden önemlisi ise dil işlemenin çalışma mantığıdır bence.
itü dil işleme topluluğu

yapay zeka ile alakalı bir konu. evrimsel süreci baz alan bir yapı geliştirmek üzere oluşturulan hesaplamalarda kullanılan bir çözüm aracıdır. biraz daha ileri gittiğimizde fuzzy logic ile genetik algoritmanın bileşimi ile genetik fuzzy sistemler oluşturulabiliyor. bu sistemlerde fuzzy logic algoritma tabanlı kontrol mekanizmaları kullanıldığından ötürü bir insandan kat ve kat daha hızlı ve herhangi bir durumda en doğru karar verebilecek ai'ler tasarlanmış oluyor. bir nevi mükemmel insanı taklit eden yapılar bunlar.

mesela şuradaki habere bakarsak, it dalaşı sırasında iki uçaktan birinde bu sistem mevcut ve böylece karşı uçakta fazlasıyla yetenekli olan pilot vuruş yapmak için karar aldığı sırada ai çoktan 250 kez hesaplama yapmış oluyor. yani tecrübeli bir pilottan 250 kat daha hızlı hareket edebiliyor. bu gerçekten müthiş:
http://www.popsci.com/ai-...gfight?src=SOC&dom=tw