Merhabalar, yüksek lisans eğitimimde aldığım evrimsel algoritmalar dersi için hazırladığım ödevin giriş kısmından yararlanarak bu konu ile ilgili bir içerik oluşturmaya karar verdim. Bu yazıda amacım, evrimsel algoritmaların tanımı ve temel çalışma mantığı hakkında bilgi vermek olup, daha derinlemesine bir yaklaşım için gerekli olan detay kavramlardan burada bahsetmeyeceğim.
Evrimsel Algoritmalar Nedir?
Canlıların yapılarını oluşturan hücreler içerisinde kromozomlar ve kromozomların da alt birimi olan genler bulunmaktadır. Çevresel faktörler ya da iç faktörler nedeniyle zamanla kromozomların yapısında değişimler meydana gelmektedir. Basitçe anlatılan bu senaryo çerçevesinde oluşturulan optimizasyon algoritmalarına (Kısaca; sahip olduğu çözümleri zamanla iyileştiren algoritmalar) evrimsel algoritmalar denir. Genetik algoritma, genetik programlama, evrimsel stratejiler, diferansiyel gelişim, büyük patlama büyük çöküş gibi evrimsel algoritma türleri vardır.
Genel Kavramlar
Sadece yukarıdaki tanıma bakarak algoritmaların çalışma mantığı üzerinde bir canlandırma yapmak mümkün değil. Kavramları anlaşılması basit olan bir optimizasyon problemi olan gezgin satıcı problemi üzerinden açıklayacağım. Gezgin satıcı probleminde bir satıcı uğraması gereken tüm noktalara bir kere uğrayarak turunu en kısa yol uzunluğunu giderek tamamlamak ister. İlk olarak anlamamız gereken popülasyon, kromozom, gen, fenotip, genotip ve encoding (kodlama) kavramlarına bakmak için aşağıdaki 6 değişkenli gezgin satıcı problemini inceleyelim.
Problem; Ankara, Kayseri, İstanbul, Amasya, Mersin ve Erzurum şehirlerine uğraması gereken bir gezgin satıcı için en kısa yolu giderek hangi sırayı izlemesi gerekmektedir? Buradaki 6 değişkenli basit bir örnek için bile 720 (6!) farklı çözüm üretilebileceği açıktır.
- Örneğin; gezgin satıcı sırası ile Ankara, İstanbul, Amasya, Kayseri, Erzurum, Mersin şehirlerini gezsin. Bu 720 olası çözümden bir tanesinin bizim anlayabileceğimiz şekilde gösterimi olan (Ankara, İstanbul, Amasya, Kayseri, Erzurum, Mersin) gösterim şekli fenotip gösterimidir. Çözümün gösterimi doğal yapılar tarafındaki kromozom terimine karşılık gelip, kromozomu (çözümü) meydana getiren her bir şehir değişkeni ise genlere karşılık gelmektedir.
- Tasarladığımız evrimsel algoritmalarda çözümler bu şekilde temsil edilmeyip farklı bir yapıya dönüştürülebilir. Mevcut problemde Ankara’nın 0, Kayseri’nin 1, İstanbul’un 2, Amasya’nın 3, Mersin’in 4 ve Erzurum’un 5 şeklinde kodlandığını varsayalım. Bir önceki maddede belirttiğim örnek çözüm (0, 2, 3, 1, 5, 4) halini alır. Buradaki yapılan işleme encoding, kromozomun (çözümün) bu şekildeki gösterimine ise genotip denmektedir.
- Popülasyon ise evrimsel algoritmaların iyileştirmeye çalıştığı kromozomlar (çözümler) topluluğudur. Örneğin; gezgin satıcı problemi gibi bir optimizasyon problemi üzerinde çalışan evrimsel algoritma başlangıç aşamasında 30 çözümlü bir popülasyon ile başlatılır. Daha sonra belirli bir iterasyon sayısı ya da şarta ulaşıncaya kadar popülasyonun çözümleri üzerinden yeni çözümler üretilerek daha optimum çözümlere ulaşılır.
Çalışma Mantığı Hakkında
Önceki başlıkta belirttiğim gibi algoritmaların her adımında çözümler üzerinde işlemler yapılarak yeni çözümler üretilir. Üretilen yeni çözümler adım sonunda değerlendirilerek (Çözümler uygunluk ve amaç fonksiyonları tarafından değerlendirilir.) popülasyona dahil edilir ya da edilmez. İşte burada yeni çözümleri oluşturmak için çaprazlama ve mutasyon işlemleri uygulanmaktadır. Mutasyon ve çaprazlama bazı evrimsel algoritmalarda beraber kullanılıyorken bazı evrimsel algoritmalarda ikisinden biri baskın olan operatör olabilmektedir. Temel amaç; probleme göre minimize ya da maksimize edilmeye çalışılan amaç fonksiyonunda değerlendirilen en iyi çözümleri aramaktır.
Çaprazlama mevcut kromozomlar kullanılarak yeni bir kromozomun üretilmesidir. Başka bir problem üzerinde aşağıdaki gibi kodlanmış kromozom 1’in ilk 3 geni ve kromozom 2’nin son 3 geni parçalarının çaprazlanması ile yeni bir kromozom oluşturularak bir çaprazlama örneği gösterilmiştir. Literatürde farklı türden çaprazlama teknikleri vardır.
- Kromozom 1: (0, 1, 1, 0, 0, 0), Kromozom 2: (1, 0, 1, 1, 0, 1)
- Yeni kromozom: (0, 1, 1, 1, 0, 1)
Mutasyon ise kromozomlar üzerinde yapılan rastgele değişimler ile yeni bir kromozomun üretilmesidir. Mutasyon ile çözüm uzayının çok farklı noktalarında olabilecek yeni çözümler üretilebilir. Aşağıda yine 0 – 1 ikili şekilde kodlanmış bir kromozoma ait mutasyon örneği gösterilmiştir. Aynı şekilde literatürde farklı türden mutasyon teknikleri vardır.
- Kromozom 1: (0 , 1, 0, 1, 1, 0)
- Yeni kromozom: (1, 0, 0, 0, 1, 1) (Karışım Mutasyonu)
Evrimsel algoritmalarda anlaşılması gereken diğer iki önemli kavram ise exploration (keşif) ve exploitation (sömürü) kavramlarıdır. Bir optimizasyon problemi üzerinde çalışan algoritmaların kullandığı popülasyonun içerisindeki çözümler optimum çözümlerden çok uzak olabilir. İşte bu nedenle çözüm uzayının çok farklı noktalarında rastgele olarak nitelendirilebilecek aramalar yapılmalıdır. Bu işleme exploration denmekte olup, mutasyon bir keşif mekanizmasıdır. Exploitation (sömürü) ise popülasyondaki mevcut çözümler etrafında optimum ya da en optimuma yakın olan çözümler olabileceği düşüncesinden yola çıkarak mevcut çözümlere yakın olan çözümler üretmektir. Çaprazlama mekanizması ise daha çok bununla ilgilidir.
Hem benim için bir tekrar olması hem de konu ile ilgili bilgilenmek isteyenlere fikir olması açısından yararlı bir içerik oldu. Benimle yasinatilgan60@gmail.com adresi üzerinden iletişime geçebilirsiniz. İyi günler…
Faydanılan Kaynaklar
https://www.tutorialspoint.com/genetic_algorithms/genetic_algorithms_mutation.htm
https://www.geeksforgeeks.org/crossover-in-genetic-algorithm/
Evrimsel Algoritmalar dersi ders notlarım, 2021
Comments are closed.