Zeki Optimizasyon Teknikleri yazı dizimizin en son konusu olan Genetik Algoritma, diğer algoritmaların iyi yönlerini birleştiren modern ve etkili bir optimizasyon tekniğidir. Probleme göre en başarılı optimizasyon yöntemi değişmekle beraber Genetik algoritma günümüzde hemen her tür probleme başarı ile uygulanmaktadır. Hill Climbing gibi popülasyon tabanlı bir algoritmadır. Algoritmanın en önemli kısmı üretilen çözümü değerlendiren, fitness function olarak bilinen kısımdır.
Genetik algoritma doğal seçilimden esinlenmiştir. Bu nedenle genetik algoritmada kullanılan terminoloji genetik ile alakalıdır. Algoritma ile alakalı yayınları ve çözümleri okurken kolaylık olması açısından genetik algoritma terminolojisini verelim.
- Popülasyon: Çözüm adaylarından oluşan kümedir. Her birey geçerli bir çözüm olmakla birlikte değişik seviyeye sahiptir. Popülasyondaki tüm bireyler aynı şekilde kodlanmış olmalıdır. Probleme göre popülasyondaki birey sayısı büyük veya küçük tutulabilir. Her ikisinin de avantajları ve dezavantajları vardır. Genellikle popülasyondaki birey sayısına tecrübe ve/veya deneme yanılma yoluyla karar verilir.
Genetik algoritmada ileride anlatılacak tüm işlemler bir sonraki popülasyonu daha iyiye taşımaya yöneliktir.
- Kromozom: Popülasyon içerisindeki bireylerin(çözümlerin) her birine kromozom denir. Gerçek hayat problemlerinde genellikle çok sayıda değişkenin optimizasyonu yapılmak istenir. Bu durumda bir kromozom(çözüm) içerisinde pek çok değişken kodlanmış şekilde bulunur.
- Gen: Kromozom içerisindeki anlamlı en küçük bilgidir. Çok değişkenli optimizasyon problemlerimizde değişkenlerin her biri gen olarak adlandırılır. (Binary olarak kodlanmış kromozomlarda bir bit gen değildir. Bir kaç bitin oluşturduğu bir değişken bir gen dir.)
- Locus: Kromozom içinde genin bulunduğu konuma locus denir. Jenerasyon(nesil): Popülasyonun bir andaki durumudur. Bir iterasyon sonrasında daha iyi bir popülasyon(jenerasyon) oluşturulması amaçlanmaktadır.
- Eşleşme(Mating): Popülasyon içerisindeki kromozomların eşleşerek yeni bireyler(çözümler) oluşturma işlemidir. Yeni jenerasyona yeni oluşturulan çözümler aktarılır.
- Bir kromozomda tüm çözümü gösterecek şekilde uygun kodlamaya karar verilmesi.
- Başlangıç popülasyonunun oluşturulması. Rastgele veya tecrübe yardımıyla yapılabilir.
- Popülasyon içerisindeki kromozomların fitness function yardımıyla değerlendirilerek her birine kalite etiketi atanması.
- Popülasyon içerisinde daha kaliteli kromozomlara daha çok şans vermek suretiyle rastgeleliği yönlendirerek eşleşme, mutasyon, elitizm gibi operatörler ile yeni bir jenerasyon oluşturulması.
- Bu işlemlere belirlenen iterasyon sayısına ulaşana kadar ve yahut çözüm istenen kalite ölçüsüne erişinceye kadar devam edilir. Yukarıdaki her adımın pek çok değişik uygulama yöntemi bulunmaktadır.
Genetik algoritma uygulaması kolay bir yöntem olmakla birlikte yukarıdaki adımları detaylıca açıklamayacağız. Genetik algoritmayı detaylarıyla öğrenmek istiyorsanız Zekai Şen hocamızın dilimizde çok güzel bir kitabı var.(Genetik Algoritmalar ve En İyileme Yöntemleri) Buradan ulaşabilirsiniz.
Bluekid abimizin iki adet çalışması var. Bunlardan bir tanesi bir-kelime bir-işlem yarışmasındaki bir işlem sorusun genetik algoritma ile çözülmesine yönelik. Bir diğeri ise 4 bilinmeyenli bir denklemin genetik algoritma ile sezgisel çözümü şeklinde.
Linklerini verelim:
Linklerdeki projelerde genetik algoritma için FGA -Fast Genetic Algorithm kullanılmıştır. Kullanımı oldukça kolay ve etkili bir kütüphane olmasına rağmen kütüphane kullanmaya aşina değilseniz veya genetik algoritma kısmını kendiniz yazmak istiyorsanız:
http://www.generation5.org/content/2003/gahelloworld.asp adresinden aldığım aşağıdaki kod ile başlayabilirsiniz.
Bu örnekte çözüm olarak "Hello world!" stringine ulaşılmaya çalışılıyor. Operatörler ve genetik algoritmanın kullanımı çok iyi. Bu kod üzerinden istediğiniz probleme yönelik değişiklikler yapabilirsiniz.
Bu yazının hazırlanmasında hocam Doç.Dr. M.Ali Akcayol' un Zeki Optimizasyon Teknikleri Dersi ders notları kullanılmıştır.
0 yorum - yorum yaz:
Yorum Gönder