Etiket arşivi: balık kolonisi algoritması

Evrimsel Optimizasyon Yöntemleri

Bu yazıda Evrimsel Optimizasyon Yöntemleri ile alakalı, zamanında tuttuğum notlar yer almaktadır.


  • Optimizasyon birşeyi en iyi yapma çapasıdır. En iyiden kastımız problemimize ve ne beklediğimize bağlıdır. Bu faydayı en maksimumda tutmaya çalışırken, zararı minimumda tutmaktır. Maliyet problemlerinde maliyeti en aza indirmektir. Matematiksel olarak da bir fonksiyonun minimum veya maksimum yapılması olarak nitelendirilebilir.
  • Newton prensiplerine göre fonksiyonda 1 tane bilinmeyen varsa (f(x)) o fonksiyonun ekstremum (minimum – maksimum) noktalarını bulmak için fonksiyonun türevi alınır.
    • d f(x) / dx = 0 => Xo
  • Birden fazla değişken olduğu durumda (2 değişken olsun mesela) hem x, hem de y’ye göre türev alıp ikisini birden sağlayan nokta ekstremum noktasını verir.
  • Konu ile ilgili farklı bir problem türev alınamayabilir olması durumudur.
  • İkiden fazla parametre olduğu durumda çözüm yavaş yavaş imkansıza doğru gitmektedir (hiperparaboloid).
  • Maliyet fonksiyonunda dibe doğru inilmeye çalışılır (türev = 0, eğim = 0). Türevde global minimumu bulmak yerine lokal minimuma takılınabilir. Olayın temeli de zaten bu lokal minimumları aşmaktır.
  • Levenberg-Marquardt Algoritması
  • Karıncalar 20 dakikada olayı çözerler. => TACO (gezgin karınca algoritması) – feromon
    • Karınca koloni algoritmasının ders programı hazırlamaya uygulanması.
    • Burada engeller yani yollar, sınıf-saat, saat-ders, ders-hoca.
  • Balık Kolonisi Algoritması – Çok hedefli optimizasyon. Dengeyi en iyi koruyan en uzun yaşar.
  • Genetik Algoritma
  • Parçacık Sürü Algoritması
    • Her kuş parçacıktır. Kuş topluluğu ise sürüdür.
    • Hem en iyi korunur, hem de kendi en iyisi (yerel gibi) korunur.
  • Elitizm
  • Çinli Postacı Problemi
  • Kafe Zinciri Problemi
    • Arama uzayı 8 olsun (2^3).
    • Popülasyon 4 olsun (4 adet kafe).
    • Örnek bir popülasyon = [ 3 1 6 2]
    • Buna göre; Total = 12, Worst = 1, Best = 6, Average = 3.0
  • 4 nokta çember problemi
  • Örnek bir test fonksiyonu olarak Rastrigin (Ras(x)).
  • John Koza – Genetik algoritmanın yazarı
  • Evrimsel optimizasyon yöntemlerini kullanmak ve tasarlamak üzere Matlab ve Mathematica programlarından faydalanılabilir.
  • Bu konu üzerine çalışan bazı hocalar; Derviş Karaboğa, Şeref Sağıroğlu, Erkan Beşdok, Mehmet Emin Yüksel.

TÜREVE DAYALI YÖNTEMLER İLE EVRİMSEL (Evolutionary) YÖNTEMLERİN KARŞILAŞTIRILMASI

  • TÜREVE DAYALI YÖNTEMLER
    • Türev kullanırlar.
    • Bir adet çözüm adayı vardır. Bir p seçilip mimimum p bulunmaya çalışılır.
    • Lokal minimumlara takılma riski yüksektir.
    • Hızlıdır.
    • Cluster yapısını uygun değildir.
  • EVRİMSEL YÖNTEMLER
    • Türev kullanmazlar. Sistemli olarak rasgele arama vardır.
    • n adet çözüm adayı vardır (popülasyon).
    • Lokal minimum’a takılma riski düşüktür.
    • Türeve dayalı yöntemlere göre oldukça yavaştırlar.
    • Cluster yapısını uygundur (paralelleştirme için) ama maliyetlidir.

EVRİMSEL OPTİMİZASYON YÖNTEMLERİNİN ADIMLARI

  1. Başlangıç popülasyonunu oluştur.
  2. Her bireyin uygunluk (or) değerini bul. Uygunluk değerleri belirlenen değerden küçükse 6. adıma git.
  3. Uygunluk/maliyet değerlerine göre elit bireyleri belirle.
  4. Elit bireylerden sonraki popülasyonu oluştur.
  5. 2. adıma git.
  6. Bitir.