Genetik Algoritmalar

Genetik Algoritmalar, canlıların çiftleşmesi sonucunda kendi özelliklerini bir sonraki nesle aktarma yeteneklerini, güçlü olanın yaşama şansının yüksek olması ve bazı durumlarda önceden nasıl olacağı bilinmeyen değişimlerin bir hesaplama yöntemi içerisinde bir arada kullanılması sonucunda ortaya çıkmış bir yöntemdir.

Genetik Algoritmalar (GA) yönetimi ilk olarak John Holland ve arkadaşlarının yaptığı çalışmalarda 1970’li yıllarda ortaya çıkmıştır.

Genetik algoritmaların temel amacı, fazla sayıda sınırlama içeren ve karmaşık optimizasyon sorunlarının çözümlerini, yazılımlar yardımıyla araştırmaktır.

Konuyla ilgili Goldberg, 1989 yılında “Genetic Algorithms in Search, Optimization, and Machine Learning” adlı klasik sayılacak eseri yayınlamıştır. Bu eserle birlikte, konu üzerine yapılan çalışmalar büyük hız kazanmıştır.

Genetik algoritmalar, rastsal arama tekniklerini kullanarak çözüm bulmaya çalışan, parametre kodlama esasına dayanan bir arama tekniğidir. Bir veri grubu içinde özel bir veriyi bulmak için kullanılır.

Genetik algoritmalar ve Klasik Optimizasyon Farkları

• Klasik optimizasyon yöntemlerinde var olan problemimizi değiştirerek algoritmaya uygun bir hale getirmemiz gerekirken Genetik Algoritmalarda ise algoritmayı problemimize göre değiştirerek istediğimiz bir hale getirebilmekteyiz. Böylelikle bizim problemimiz için daha doğru sonuçlar elde edebilmekteyiz.
• Genetik algoritmalar parametrelerin kendileri ile değil parametre takımının kodlanmış haliyle çözüme gitmeye çalışırlar.
• Genetik algoritmalar amaç fonksiyonunun türevlerini ve bir takım ek bilgilerini değil, doğrudan amaç fonksiyonun kendisini kullanırlar.
• Genetik algoritmalar aramaya tek bir noktadan değil, noktalar kümesinden başlar. Bu nedenle çoğunlukla yerel en iyi çözümde sıkışıp kalmazlar.
• Genetik algoritmalar’da deterministik değil rastlantısal geçiş kuralları kullanılır.

Genetik Algoritma Adımları:

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.

Genetik Algoritmaların Çalışma Prensibi

Goldberg; genetik algoritma, soyut temsiller olarak adlandırılan kromozomları en iyileme problemlerinde kullanan bir bilgisayar simülasyonu olarak kabul edilebileceğini belirtmiştir. Geleneksel olarak çözümlemeler 0’ lar ve 1’ lerden oluşan zincirlerden meydana gelir. Evrim rastgele bireylerden başlar ve nesilde kendini gösterir. Her nesilde çeşitli bireyler mevcut popülasyondan seçilir, yeni bir popülasyonu oluşturması için değiştirilir (mutasyona uğratılır ve yeniden kopyalanır) ve bu popülasyon algoritmanın bir sonraki tekrarında kullanılır. Anlaşılacağı üzere genetik algoritmaların yapısı oldukça kolay ve anlaşılabilirdir. Bundan dolayı problemlere kolaylıkla uygulanabilir. Neyin iyi olduğunu genetik algoritmaya bildirmek için bir uygunluk (amaç) fonksiyonu oluşturulması ve problemin değişkenlerinin kodlanmasıyla, her çeşit karmaşık problem genetik algoritmalar sayesinde çözüme ulaşabilir (Goldberg, 1989).

Genetik Algoritmalarda Çaprazlama ve Mutasyon İşlemleri

Çaprazlama operatörü, genetik algoritmanın performansını etkileyen önemli parametrelerinden biri olarak karşımıza gelmektedir. Çaprazlama, ana bireyde seçili genler üzerinde işlem yaparak yeni yavrular oluşturur. Bunun en basit şekli, rasgele bir kesme noktası (çaprazlama noktası) seçip, bu noktadan önceki her şeyi ilk atadan, sonraki her şeyi ikinci atadan alıp birleştirerek yavruyu oluşturmaktır (Fığlalı ve Engin, 2002). Çizelge1’ de iki bitlik bir çaprazlama örneği görülmektedir.

Çaprazlama yöntemi, genlerin mevcut potansiyellerini incelemek için kullanılır. Fakat kodlanmış bütün bilgiyi popülasyon içermez ise, çaprazlama yöntemi beklenilen çözümü üretemez. Bundan dolayı, mevcut kromozom ailesinden yeni kromozomlar üretme imkânına sahip bir operatör gerekmektedir. Bu olayı mutasyon gerçekleştirir. Mutasyon operatörü, çözümün kaybına karşı koruma sağlamaktadır (Goldberg, 1989). Örnek bir mutasyon Çizelge 2’ de gösterilmiştir.

Genetik Algoritmanın İşlem Adımları

Genetik algoritmanın işlem adımları sırasıyla şu şekildedir;

• Arama uzayındaki çözümlen imkânı olan bileşenler dizi olarak kodlanır. Her bireyin ne kadar iyi olduğu bulunur (uygunluk fonksiyonu). Genetik algoritmalar doğada yaşamını sürdürebilecek kuralına uygun olarak sürekli iyileşen yeni çözümler üretir.
• Belirlenmiş olan bireyler bir olasılık değerine göre rastsal olarak çoğalma işlemine tabi tutulur. · Seçilen bireyler, çaprazlama ve mutasyon işlemleri uygulanır.
• Daha önce belirlenen adım sayısı boyunca veya hata belli bir ön tanımdan küçük olana kadar yukarıdaki işlemler sırasıyla sürdürülür.
• Adım sayısı, belirlenen kuşak sayısına ulaşıncaya kadar sürer, ulaşınca işlem sonlandırılır. Hedef fonksiyonuna en uygun olan bireyi seçmek.