Genetik Algoritma #1
Genetik Algoritma Nedir?
Hızlı giriş: Genetik algoritma genetik biliminden esinlenilerek hazırlamış ve normalde cevabını bulunamayacak kadar karışık problemleri çözmeye yarayan bir algoritmadır.
Genetik Algoritma; içinde hem genetik hem algortima bulunan bir isim tamlaması ,insanların ilgisini aşırı seviyede çekerken, bu oradanda da korkutuyor ve kaçırıyor. Tamda bu yüzden bu gün en basitinden genetik algoritmanın ne kadar kolay ve anlaşılabilir olduğunu aktarmaya çalışacağım.
Öncelikle bilmemiz gereken konu Genetik Algoritma bir Sezgisel algoritmadır ve Sezgisel Algoritmalar Optimizasyon işlemlerinde kullanılırlar. Optimizasyon Bir işlemi daha az maliyete veya daha fazla verimlilik ile yapabilmeyi hedefler.
Güncelleme: Eğer Genetik algoritma terminolojisine ve kullanımına belirli seviyede hakimseniz Javascript ile Genetik Algoritma yazısına geçebilirsiniz. Hakim olmadığınızı düşünüyorsanız lütfen bu yazıyı bitirip öyle geçiniz. (Güncellem Tarihi: 08.01.2020)
Güncelleme 2: Golang ile Genetik Algoritma yazısına buradan ulaşabilirsiniz.
Terminoloji
Öncelikle birşeyin terim hali pek anlaşılır olmayabiliyor. Bundan dolayı yazının tamamını okumadan önyargılı davranmamaya özen gösteriniz
Genetik biliminden esinlenildiği için isim olarak genetik algoritma denildiğini söylememiz fayda sağlayacaktır. Öncelikle ilk bilmemiz gereken terim Popülasyon’dur. Popülasyon biolojide bir topluluğa verilen ad olarak kullanılırken, GA’da olası çözüm bilgilerini ifade eden bireylerin topluluğuna verilen isimdir. Popülasyonda ki her bireyimizin ismi Kromozomdur. Biolojide DNA gibi hayal edebiliriz. Son olarak Kromozomlarımız genlerden oluşmaktadır.
İşleyiş şöyledir:
Başlangıçta Kromozomlarımızın ideal kromozom olup olmadıkları için belirli testlere (fitness function) sokuyor ve puanlıyoruz, belirlenen yeni popülasyonumuzu bir kurallar yapısına sokuyor ve bu kromozonlardan tekrardan yeni kromozomlar oluşturuyoruz. Bu yeni kuşakta yine başarılı olanları türetiyor ve başarısız olanları popülasyonumuzdan uzaklaşmasını bekliyoruz (Bekliyoruz dedim çünkü direk uzaklaştırmak doğru bir yol olmayabiliyor.). Bu işlem sürekli belirli bir noktaya kadar devam ediyor. Bittiğinde elimizde en başarılı kromozom kalıyor. Bu en başarılı kromozomda bizim en ideal çözümümüze yakın olan çözüm oluyor (Sezgisel algoritmalarda en ideal değil ideal’e en yakın aranır.) ve çözümü bulmuş varsayıyoruz.
Yeni nesilleri türetme evresinde kullanabileceğimiz iki yöntemimiz bulunmaktadır. Bunlardan birincisi çaprazlama ve ikincisi mutasyondur.
Çaprazlama seçilmiş iki kromozomun belirlenmiş bir kural ile yeni gen oluşturmasıdır. Mutasyon ise belirlenmiş bir genin üzerine zorlama ile farklılaştırmaktır (Radyasyon gibi fazla (azdan biraz fazla) mutasyon bozulmalara neden olup popülasyonuza zarar verir.)
Bu kadar bilgiden sonra devam edelim…
Peki Yazılımda bu iş nasıl oluyor sorusunuda şöyle göstermem uygun olacaktır
Nasıl Çalışır?
Gezgin satışı problemi (TSP) genetik algoritmayı anlatmakta en kolay anlatım yoludur. Örneğin 5 adet şehirimiz var (A,B,C,D,E) ve her bir şehire sadece 1 defa gitmek zorundayız. Başlangıç Şehrimiz bizim şu anda oturduğumuz şehir olan A şehri olduğunu biliyoruz fakat sonrasında hangi şehre gideceğimizi karar vermemiz gerekiyor
A->B->C->D-E->A
A->C->B->D-E->A
A->D->B->C-E->A
A->C->E->B-D->A
...4 Şehir için 4x3x2x1 = 120 (4!) ihtimalimiz vardır en ideal yolu bulmak için, fakat eğer 50 şehir olsaydı bu sayı (50!) olacaktı yani yaklaşık olarak 65 basamaklı bir çözüm uzayımız olacak demekti. Bu kadar büyük bir uzayda aradığımızı bulmamızda imkansıza yakın veya çok zor olacaktı. (Sezgisel algoritmalar n! veya n^n gibi çözümü çok zor veya imkansız çözüm uzayları için idealdir.)
Şimdi geldik genetik algoritmada bunları nasıl çözeceğimize (Bu kısımda gelişi güzel şekilde anlatacağım, Bir sonraki bölümde daha detaylı gireceğim.)
Biz şehirleri birer gen gibi düşünerek bir kaç tane kromozom oluşturuyoruz ve oluşan kromozomların fitness function adı verdiğimiz bizim için ideal sonuca göre puanlama yapacak fonksiyona sokuyoruz. (Bu problemde çizilen rotanın toplam km hesabını yapmamız yeterli olacaktır).
1. A-B-C-D-E-A => 100 km
2. A-C-E-D-B-A => 10 km
3. A-D-B-C-E-A => 400 km
4. A-E-D-C-B-A => 1000 kmçıkan sonuçlara göre şimdi yaşamaları veya popülasyondan uzaklaşmaları lazım. Bu kısımda belirlenmiş farklı yöntemler vardır biz çark yöntemini kullanarak başarı oranının tersine göre hepsini çarkta belirli parçalara oturtuyoruz.
ve sonra bu çarkı çeviriyoruz, gelen numara kimse onu hemen popülasyonumuzdan uzaklaştırıyoruz (4 numaralı birey çok başarısız olduğu için büyük ihtimalde o gidecektir. Fakat 1 numaranın bile gitme ihtimali vardır.)
Bu işlemi elimizdeki popülasyona ve belirlediğimiz kurallara göre çok defa tekrarlayıp temizleme yapıyoruz (Bizde 3 ve 4 numara popülasyondan uzaklaşsın). Sonra elimizde kalan popülasyondan giden kişi kadar yeni bireyler oluşması için Çaprazlama ve Mutasyona uğratıyoruz.
Bu evrede belirlediğimiz bireyleri çaprazlayabilir veya mutasyona uğratabiliriz. Kural dizini tamamen bizim elimizdedir. (Biz en başarılı ilk ikiyi çaprazlayıp En kötüyü de mutasyona uğratıp yeni bireyler oluşturalım)
1. A-C-E-D-B-A => 10 km
2. A-B-C-D-E-A => 100 kmÇ1: A-C-E-B-D => 23 km(Çaprazlamada ilk iki bireyin ilkinin yarısını tuttuk ve sonrasında ikinci bireyin başından sonuna doğru bulunmayan genleri ekledik (C-E ilk bireyden geldi geriye kalan B-D arasından da ikinci bireyin B ilk geldiği için B-D ekleyerek yeni birey oluşturduk.)) (Eğer yapacak olsaydık bu bireyler için diğer çaprazlamamız şu şekilde olacaktı A-B-C-E-D-A)
M1: A-B-C-D-E-A => ..
A-*-C-*-E-A => ..
A-D-C-B-E-A => 75km (Mutasyon Örneği)
elimizde oluşan yeni popülasyonumuz şu şekildedir
1. A-C-E-D-B-A => 10 km
2. A-C-E-B-D => 23 km
3. A-D-C-B-E-A => 75km
4. A-B-C-D-E-A => 100 kmve bu işlemi sürekli tekrarlamak suretiyle belirtilen zaman veya koşula kadar devam eder. Bitirmek için üç koşulu ele alabiliriz.
- Belirlenen başarının üstüne çıkınca dur diyebiliriz.
- Belirtilen nesilde dur diyebiliriz.
- Belirlenen nesil kadar hiç en iyi birey değişmezse dur diyebiliriz.
Not: Örneğimiz sadece anlatım amaçlı olup 4 şehirden oluşan bir örnek bunun için ideal bir örnek değildir.
Ufak İpuçları
0. Popülasyondan Çıkartılan birey sayısı ile giren birey sayısı her zaman eşit olmak zorundadır
- Mutasyon seviyesini çok ufak bırakınız. (Popülasyon içerisinde %1'den daha küçük seviyede)
- Popülasyonunuz ne kadar büyükse o kadar iyi sonuçlar elde edersiniz
- Çaprazlama’da ortadan ikiye bölüp tekrarsız şekilde yapabileceğiniz gibi üç parçaya bölüp sadece ortadaki parçayı tekrarsız olarak da yapabilirsiniz
- Sabit genleri hesaba katlayınız
- Kurallarınızı değiştirerek belirli testler yapınız (Benim örneğimde Çaprazlama %70 Mutasyon %30(Yeni gelecek 100 bireyden sadece 30'unu ufak mutasyonlar uygulanmış olarak yeni bireylere dönüştürdüm.) uygulanmıştır )
Önerilen Kitap
Derviş Karaboğa — Yapay zeka optimizasyon algoritmaları
Önerilen Video Anlatım
Şadi Evren — Yapay Zeka 11: Genetik Algoritmalar
Son not: İlk örneğinizi yazdıktan sonra çok rahat şekilde anlayabileceğiniz bir algoritmadır. Lütfen aklınıza takılan soruları ve merak ettiklerinizi sorunuz.
Teşekkürler.
Duyuru!
Önerilen Yazılar
