Genetik algoritmalar açıklandı

Evrim; gözleri, kanatları ve beyinleri bir tasarımcı olmadan, yalnızca işe yarayanı koruyup onu çeşitlendirerek üretmiştir. Genetik algoritma bu fikri bilgisayarda problem çözmek için ödünç alır. Problemi anlaması gerekmez; daha iyi bir cevabı daha kötüsünden ayırt edebilmesi yeterlidir. Bu da onu, olası cevapların uzayı başka bir yolla aranamayacak kadar büyük ve tuhaf olduğunda güçlü bir araç yapar.

Bir alanın altından kalkıp bir duvarın etrafından dolaşarak yeşil bir hedefe uçan roketler; en iyi uçuş kesikli çizgiyle gösterilmiş
Bir alanın altından kalkıp bir duvarın etrafından dolaşarak yeşil bir hedefe uçan roketler; en iyi uçuş kesikli çizgiyle gösterilmiş

Fikir

1960'lı ve 1970'li yıllarda Michigan Üniversitesi'nden John Holland, Darwin'in kuramını bir algoritmaya dönüştürdü ve bunu 1975 tarihli Adaptation in Natural and Artificial Systems adlı kitabında anlattı. Aynı dönemde Almanya'da Ingo Rechenberg ve Hans-Paul Schwefel mühendislik tasarımı için evrim stratejilerini geliştirdi. Ortak tarif şudur: aday çözümlerden oluşan bir popülasyon tutun, onları puanlayın, daha iyilerinin çeşitlenerek üremesine izin verin ve bunu birçok nesil boyunca tekrarlayın.

Genetik algoritmaları 1975 tarihli Adaptation in Natural and Artificial Systems kitabında tanımlayan John Holland.
Genetik algoritmaları 1975 tarihli Adaptation in Natural and Artificial Systems kitabında tanımlayan John Holland.

Genler ve popülasyon

Her aday bir kromozomla, yani bir gen listesiyle tanımlanır. Oyun alanında bir roketin genleri, uçuşunun her anı için bir tane olmak üzere itmeleridir; başka problemlerde bunlar bir sayının bitleri, bir rotadaki şehirlerin sırası ya da bir tasarımdaki parçaların boyutları olabilir. İlk nesil rastgeledir; bu da cevap uzayını geniş biçimde keşfettiği ama neredeyse hiç iyi cevap içermediği anlamına gelir.

Uygunluk fonksiyonu

Uygunluk, bir adayın ne kadar iyi olduğunu söyleyen tek sayıdır ve algoritmanın problem hakkında bildiği tek şeydir. Roketler için en çok erken varışı, ardından hedefe yakın bitirmeyi ödüllendirir ve çarpışmayı cezalandırır. İyi seçilmiş bir uygunluk fonksiyonu aramayı iyi cevaplara doğru sorunsuzca yönlendirir; özensiz seçilmiş biri ise yanlış şeyi ödüllendirir ve algoritma açık bıraktığı her boşluktan yararlanır.

Seçim

Ebeveynler, daha uygun adayların daha çok yavrusu olacak şekilde seçilir, ancak daha zayıf olanlar da bir şans bulur, çünkü genleri işe yarar parçalar taşıyor olabilir. Rulet tekerleği seçimi her adaya, uygunluğuyla orantılı büyüklükte bir tekerlek dilimi verir; turnuva seçimi ise rastgele birkaç aday seçip içlerinden en iyisini alır. Daha güçlü seçim ilerlemeyi hızlandırır ama popülasyonu birbirine daha çok benzetir; bu da aramayı fazla erken bitirebilir.

Çaprazlama ve mutasyon

Çaprazlama iki ebeveyni birleştirir: burada bir yavru genlerinin ilk kısmını bir ebeveynden, geri kalanını diğerinden alır; böylece bir roketin erken manevraları bir başkasının geç manevralarıyla buluşabilir. Mutasyon birkaç geni rastgele değiştirir. Çaprazlama popülasyonda zaten var olanı yeniden birleştirir; mutasyon ise popülasyonda hiç olmamış olanı getirir. Holland'ın şema teoremi, iyi genlerden oluşan kısa yapı taşlarının bu seçim ve rekombinasyon karışımı altında popülasyona nasıl yayıldığını açıklar.

Elitizm, keşif ve sömürü

En iyi birkaç adayı değiştirmeden sonraki nesle kopyalamak, yani elitizm, en iyi cevabın asla kaybolmamasını garanti eder. Her genetik algoritma, arama uzayının yeni bölgelerini denemek anlamına gelen keşif ile zaten iyi olanı iyileştirmek anlamına gelen sömürü arasında denge kurmak zorundadır. Çeşitlilik çok azsa popülasyon vasat tek bir cevapta birleşir; çok fazlaysa hiçbir zaman durulmaz. Popülasyon büyüklüğü, mutasyon oranı ve seçim baskısı bu dengeyi ayarlayan düğmelerdir.

Yerel optimumlar

Bir genetik algoritma yalnızca uygunluğu izler, bu yüzden yanıltılabilir. En iyi cevaba giden yol önce daha kötü cevaplardan geçtiğinde, popülasyon en yakın tepeye tırmanır ve orada kalır: yerel optimum. Oyun alanındaki kademeli duvarların arkasında, hedefin altında çarpan roketler, boşluğu bulmak için yön değiştiren roketlerden daha yüksek puan alır; bu yüzden popülasyon duvarın dibine yığılır. Çareler arasında daha büyük popülasyonlar, daha yüksek mutasyon, popülasyonu çeşitli tutmak ve her şeyden önce daha iyi bir uygunluk fonksiyonu vardır.

Kendiniz keşfedin

Roketleri tek bir duvarın, bir boşluğun, sütunların, kademeli duvarların ya da kendi çizdiğiniz duvarların etrafından dolaşacak şekilde evrimleştirmek için genetik algoritma oyun alanını açın. Popülasyonu, mutasyon oranını, ömrü ve seçim yöntemini değiştirin, elitizmi açıp kapatın ve hedefe ulaşan roketlerin oranının ne kadar hızlı arttığını ya da neden artmadığını grafikte takip edin.

Sık sorulan sorular

Genetik algoritma bir tür yapay zeka mıdır?

Bir arama ve optimizasyon yöntemi olarak daha geniş yapay zeka ve makine öğrenmesi alanına aittir. Bir sinir ağı gibi örneklerden öğrenmez; aday çözümleri deneme ve seçim yoluyla iyileştirir. İkisi sık sık birleştirilir; örneğin sinir ağlarının yapısı veya ağırlıkları evrimleştirilir. Bu yaklaşıma nöroevrim denir.

Genetik algoritma her zaman en iyi cevabı bulur mu?

Hayır. Sezgisel bir yöntemdir: zor problemlere genellikle iyi cevaplar bulur, ama en iyisini bulacağını garanti etmez ve bulduğu cevabın en iyisine ne kadar yakın olduğunu kanıtlamaz. Kesin bir yöntemin yeterince hızlı olduğu problemlerde o yöntem daha iyidir.

Genetik algoritma ile evrim stratejileri arasındaki fark nedir?

İkisi de evrimsel algoritmadır. Klasik genetik algoritmalar dizi benzeri kromozomlar üzerinde çaprazlamayı ön plana çıkarır; evrim stratejileri ise ağırlıklı olarak gerçek sayılar üzerinde mutasyonla çalışır ve çoğu zaman kendi mutasyon büyüklüklerini ilerledikçe uyarlar. Modern yöntemler her ikisinin fikirlerini harmanlar.

Roketler başta neden bu kadar beceriksiz?

İlk genleri tamamen rastgele itmelerdir; bu yüzden ortalamada birbirlerini götürürler ve roketler sürüklenir. Koordineli uçuşlar ancak seçim, tesadüfen kabaca doğru yöne iten nadir roketleri tuttuktan ve çaprazlama onların iyi bölümlerini birleştirdikten sonra ortaya çıkar.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Genetik algoritma oyun alanını aç