Kategori arşivi: Yapay Zeka ve Optimizasyon

Deep Learning Heroes / Derin Öğrenme Kahramanları

Bu yazıda Derin Öğrenme (Deep Learning) deyince akla gelen kişilerden bazılarını vermek istiyorum. Listedeki kişiler araştırılıp ne yaptıkları öğrenilebilir ve derin öğrenme heveslisi kişilere bir kapı aralanabilir düşüncesiyle bu listeyi hazırladım. Liste zamanla genişleyebilir.

  • Andrew NG
  • Geoffrey Hinton (Boltzman Machines)
  • Pieter Abbeel
  • Ian Goodfellow
  • Yoshua Bengio
  • Yuanqing Lin
  • Andrej Karpathy
  • Ruslan Salakhutdinov
  • Yann LeCun (LeNet-5)
  • Terry Sejnowski
  • Alex Krizhevsky (AlexNet)
  • Ilya Sutskever
  • Karen Simonyan (VGG-16)
  • Andrew Zisserman
  • Kaiming He (ResNet)
    • Xiangyu Zhang
    • Shahqing Ren
    • Jian Sun
  • Christian Szegedy (Inception Network – GoogLeNet)
    • Wei Liu
    • Yangqing Jia
    • Pierre Sermanet
    • Scott Reed
    • Dragomir Anguelov
    • Dumitru Erhan
    • Vincent Vanhoucke
    • Andrew Rabinovich
  • Russ Girshik (R-CNN)
    • Jeff Donahue
    • Trevor Darnell
    • Jitendra Malik
  • Shaoqing Ren (Faster R-CNN)
    • Kaiming He
    • Ross Girshick
    • Jian Sun
  • Yaniv Taigman (Deepface)
    • Ming Yang
    • Marc’Aurelio Ranzato
    • Lior Wolf
  • Florian Schroff (FaceNet)
    • Dimitry Kalinichenko
    • James Philbin
  • Mathew Zeiler (visualizing and understanding CNNs)
    • Rob Fergus
  • Leon A. Gatys (A neural algorithm of artistic style)
    • Alexander S. Ecker
    • Matthias Bethge

Derin Öğrenme Coursera Notları (Deep Learning Coursera Notes)

Coursera’dan aldığım derin öğrenme kurslarından anahtar kelimeleri daha sonrası için hafızada tutmak amacıyla bu yazıda paylaşmak istiyorum.


NEURAL NETWORK AND DEEP LEARNING

  • Supervised learning with neural network
  • Binary classification (örn: logistic regression)
  • Logistic regression, SVM -> traditional learning algorithms
  • Cost function
  • Gradient descent
  • Derivatives
  • Vectorization and broadcasting
  • Numpy, iPython, Jupyter
  • Activation functions (Softmax, ReLU, leaky ReLU, tanh (hiberbolik tanjant), swish (a self-gated activation function))
  • Forward / Back propagation
  • Random initialization
  • Shallow neural networks
  • CNN (for image)
  • Recurrent NN (Sequence data)
  • Deep reinforcement learning
  • Regression (Standart NN)
  • Structured data – Database, Unstructured data – audio, image, text
  • Tensorflow, Chainer, Theano, Pytorch
  • Normalization
    • Standart score
    • T test
    • Standardized moment
    • Coefficient of variance
    • Feature scaling (min-max)
  • Circuit Theory
  • Parameters
    • W, b
  • Hyperparameters
    • learning rate
    • #iterations
    • #hidden layers
    • #hidden units
    • activation function
    • momentum
    • minibatch size
    • regularization

IMPROVING DEEP NEURAL NETWORKS: HYPERPARAMETER TUNING, REGULARIZATION AND OPTIMIZATION

  • Dataset -> Training / Dev (hold-out validation) / Test sets
    • Büyük veri setleri için dağılım 98/1/1 olabilir. Geleneksel olarak 70/30 veya 60/20/20’dir.
  • Bias / variance.
    • high bias = underfitting
      • bigger network (her zaman işe yarar)
      • train longer (NN architecture search) (her zaman işe yaramaz)
    • high variance = overfitting
      • more data
      • regularization
        • L1 regularization
        • L2 regularization (lambd) – daha çok tavsiye ve tercih edilir.
        • Dropout regularization (keep prob)
        • Data augmentation
        • Early stopping
      • NN architecture search
  • Speed-up the training
    • normalizing the inputs
      • subtract mean
      • normalize variance
    • data vanishing / exploiding gradients
    • weight initializion of deep networks
      • xavier initialization
      • HE initialization
    • gradient checking -> backpropagation control
      • dont use in training
      • dtheta, dtheta approx.
      • remember regularization
      • does not work with dropout
  • Optimization algorithms
    • (stochastic) gradient descent
    • momentum
    • RMSProp
    • Adam
  • Mini batch
  • Exponentially weighted averages
  • Bias correction
  • Learning rate decay
  • The problem of local optima
  • HYPERPARAMETER TUNING
    • try random values
    • confonets, resnets
    • panda babysitting (sistem kaynakları kısıtlı ise) or baby fish (caviar) approach (değilse)
    • batch normalization
    • covariate shift
    • softmax regression
    • hardmax biggest 1, the others 0
  • Frameworks
    • Caffe/Caffe2
    • CNTK
    • DL4J
    • Keras
    • Lasagne
    • mxnet
    • PaddlePaddle
    • Tensorflow
    • Theano
    • Torch

STRUCTURING MACHINE LEARNING PROJECTS

  • Orthogonalization (eğitimin yeterince başarılı olması için gereklidir) (radyo ayarlama) (developer set (training)
    • fit training set well in cost function
      • bigger NN or better optimization algorithms
    • fit dev. set well on cost function
      • regularization or bigger training set
    • fit test set well on cost function
      • bigger dev set
    • performs well in real world
      • dev set is not set correctly, the cost function is not evaluating the right thing
  • Single number evaluation metric
    • P (precision) (toplam doğruluk, %95 kedidir)
    • R (Recall) (kedilerin %90’ı doğru bilindi.
    • F1 Score – average of precision and recall (F1 değeri yüksek olan daha başarılıdır)
  • Satisficing and optimizing metric
    • hangisi satisficing hangisi optimizing olacak.
  • Train/dev/test sets distribution
  • When to change dev/test sets and metrics
  • Human level performance
    • avoidable bias / bayes optimal error (best possible error)
    • reducing bias/variance
    • surprassing human-level performance
  • ERRORS
    • training
      • variance
      • more data
      • regularization (lz, dropout, augmentation)
      • NN architecture / hyperparameter search
    • dev
    • human-level errors
      • avoidable bias
      • train bigger model
      • train longer
      • train better optimization algorithms (momentum, RMSProb, Adam)
      • NN architecture
      • Hyperparameter search
      • RNN/CNN

Yapay Zeka – Zeki Programlama Teknikleri

  • Yapay Zeka, insan ve doğadaki zeki davranışların taklit edilerek problemlerin çözümünde kullanılmasıyla ilgili bilim dalıdır.
  • Birçok farklı alanda kullanılabilir.
  • Yapay zeka algoritmalarında başlangıçlar hep aynı olsa da sonuç farklı olabilir. Hatta büyük bir ihtimalle farklı olacaktır (yakın olabilir).
  • bağımlı Değişken = f (bağımsız değişkenler, parametreler, zorlayıcı fonksiyonlar) –> matematiksel model
  • İstenen çalışma şartları belirlendiğinde parametrelerin olması gereken değerlerini bulmak zordur.
  • Optimizasyon, verilen bir zaman içinde bir problemin mümkün olan en iyi çözümünü bulmaya çalışma sürecidir. Başka bir ifade ile belirli şartları sağlayacak şekilde bir problemin parametre değerlerinin belirlenmesi işlemidir. Probleme göre minimizasyon veya maksimizasyon olarak da nitelendirilebilir.
  • Modern optimizasyon yöntemleri belirleyici bir yöntemle en iyi çözümü bulmayı amaçlar. Başlangıç çözümü seçilir, ihtimalci ve bulgucu stratejilerle bu çözüm geliştirilir.
  • Kısıtların girmesi olayı daha zora sokmaktadır.
  • min = -max
  • Çok Amaçlı Optimizasyon Problemi – İki fonksiyonu birden optimize etmeye çalışıyoruz.
    • f [f1 f2]
  • feasible region (uygulanabilir bölge)
  • Sibernetik – Canlı organizmaların taklidi ve sentezi
  • Zeka (Yapay Zeka) – Bilgi temsil yeteneği, sezgisel muhakeme yeteneği, öğrenme yeteneği, algılama vs.

Klasik Optimizasyon Yöntemleri

Ayrık/sürekli –> Kısıtlamalı/kısıtlamasız olarak sınıflandırabiliriz. Birden fazla minimum veya maksimum varsa çok modlu olarak isimlendirilir. Karmaşıklık hususu bu yöntemlerde önem arz etmektedir. Karmaşıklığın az olması maliyeti düşürecektir (O(logn), O(n), O(nlogn), O(n^2), O(n^3)).

Optimizasyon yöntemlerinde aşamalar; 1) parametre setinin tanımlanması, 2) amaç fonksiyonunun tanımlanması (min/max), 3) sınırlamaların tanımlanması.

    • 1-Boyutlu Kısıtlamasız Optimizasyon Yöntemleri
      • Golden Bölme
      • 2. Derece İnterpolasyon
      • Newton
    • 2-Boyutlu Kısıtlamasız Optimizasyon Yöntemleri
      • Doğrudan Yöntemler
        • Rasgele Arama
        • Benzer Değişim
        • Model Aramaları
      • Gradyen Yöntemler (Türeve Dayalı)
    • Kısıtlamalı Optimizasyon Yöntemleri
      • Doğrusal Programlama
        • Grafik Çözüm
        • Simpleks
      • Doğrusal Olmayan Kısıtlamalı
        • Gradyen

Gradyen Yöntem

Gradyen yöntem türeve dayalıdır. Yani eğim söz konusudur. Birinci türev eğim (optimuma ne zaman ulaşacak), ikinci türev ise minimum, maksimum bilgisi. Gradyen yani türeve dayalı yöntemlerde yerele yakınsama olumludur, ancak globalden ıraksama problemi vardır.


Optimizasyon Yöntemleri

  • Problem düzeyinde, YSA (Yapay Sinir Ağları)
  • Problem üstü düzeyde ise İleri-Geri Beslemeli Yapay Sinir Ağları

Arama Yöntemleri

  • Yorucu Arama (Tüm kombinasyonlar incelenir.)
  • Rasgele Arama (Random)
  • Aç gözlü arama (Greedy)
  • Tepe Tırmanma (Hill Climbing)
  • Sezgisel (Heuristic) — Akıllı tahminlere dayalı buluş yöntemi veya yeni çözümlerin keşfine götüren bulgulara dayalı arama yöntemidir. En iyi sonucu garanti etmez.
  • Belirleyici (Deterministic) — Probleme özel statik yöntemlerdir
  • İhtimalci (Stochastic) — Farklı problemlere yöneliktir, dinamik yöntemlerdir.

Problem Çözümleme

  1. Problemin Tanımlanması
  2. Strateji
  3. Başlangıç Durumu
  4. Operatörler
  5. Komşuluk
  6. Durum Uzayı
  7. Hedef Testi
  8. Yol Maliyeti

Algoritma Değerlendirme Kriterleri

  • Tamlık (Çözüm garantisi)
  • Uzay Karmaşıklığı (hafıza)
  • Zaman Karmaşıklığı
  • Dinçlik (Her başlangıçta iyi çözüm?)
  • Esneklik (Adaptasyon)

Bilginin Temsili

  • Binary (bit sayısı ve hassasiyet)
  • Gerçel
  • Sembolik veya Permütasyon Kodlama

Seri Algoritmalar

  • Tabu Arama
  • Tavlama Benzetimi

Popülasyon Tabanlı Algoritmalar

  • Genetik
  • Karınca Koloni
  • Memetik..

Göçmen Kuş Algoritması

  • Göçmen kuşlar güneşe göre hareket ederler (Yön ve Işık).
  • Besin depolama – belirli yerler seçilir ve oralarda beslenirler.
  • Yaklaşan fırtınadan kaçma – ses duyuları gelişmiştir. Modellediğimizde fırtınadan kaçma kötü değer olarak düşünülebilir.
  • İyi değer ise ışığa göre güneye gitme olarak düşünülebilir.
  • Uygunluk fonksiyonu uygun değere geldiğinde güneye gelinmiş olur.
  • Uygulamada göç zamanını biz belirliyoruz. Göç zamanı en iyi değer olarak da düşünülebilir. Göç zamanı gelmiş olur.
  • mobilbahisodeme.net

Bu problemde üzerinde çalışılan bölge (uzay) dünya olarak düşünülmeli. Amaç kuzeyden güneye göç olarak algılanmalıdır. Bulunduğumuz başlangıç noktası kuzey, algoritmaya girilen şart ise güney olarak düşünülmelidir.

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.

Parçacık Sürüsü Optimizasyon Algoritması (Particle Swarm Optimization Algorithm)

Parçacık Sürüsü Optimizasyon Algoritması(PSO), kuş sürülerinin davranışlarından esinlenilerek ortaya çıkarılmış bir algoritmadır. Popülasyon tabanlıdır ve skotastik bir yapıya sahiptir. Sosyal sistemler bireyin çevresiyle ve diğer bireylerle olan etkileşimini ve davranışını incelemektedir. Bu davranışlara sürü zekası denmektedir. Sürülerden esinlenilerek ortaya çıkarılan iki popüler optimizasyon yöntemi vardır. Bunlar; Karınca Koloni Optimizasyonu ve Parçacık Sürü Optimizasyonudur.PSO sürünün besin kaynağı ararken ortaya koyduğu davranış üzerine kuruludur. PSO, evrimsel algoritmalarla bir çok benzerlik göstermektedir. PSO’nun adımları aşağıdaki gibidir. taşıma şirketi

Algoritmada bahsedilen parçacıklar sürüdeki bireylere işaret etmektedir.

PSO KONTROL PARAMETRELERİ

  • Parçacık Sayısı : Problemin çeşidine göre ayarlanmalıdır. Bazı problemlerde 10 parçacık yeterliyken, bazılarında 20-40, bazılarında ise 100-200 değerleri gerekmektedir.
  • Parçacık Boyutu : Optimize edilecek probleme göre değişir.
  • Parçacık Aralığı :Probleme göre farklı boyut ve aralıklarda ayarlanabilir.
  • Vmax : Bir iterasyonda bir parçacıkta meydana gelecek maksimum hızı belirler. Genellikle parçacık aralığına göre ayarlanır.
  • Öğrenme Faktörleri : Denklemde görülen c değerleridir. Genellikle 2 olarak seçilirler. Fakat farklı değerler de alabilirler. Yaygın olarak [0,4] aralığında alınır.
  • Durdurma Kriteri : İki şekilde yapılabilir; Birincisi başlangıçta maksimum iterasyon sayısı belirlenir ve algoritma bu sayıya ulaştığında sonlandırılır. İkincisi ise değerlendirme fonksiyonu istenilen değere ulaştığından algoritma sonlandırılır.

Algoritmanın Pseudo Code’u aşağıdaki gibidir.

Begin
   While Durdurma kriteri sağlanmıyorsa do
      Begin
      for i = 1 to parçacık sayısı 
         Uygunluk Değeri := f(Xi); 
         Pi ve gi’yi güncelle;
         I denklemini kullanarak hızı güncelle;
         Parçacığın koordinatını güncelle;
         i= i+1;
   end while
end

Parçacık Sürüsü Algoritması bir başlangıç popülasyonuyla başlatılır ve algoritmanın çalışmasıyla, çözümler güncellenir ve optimum çözüm bulunmaya çalışılır. Her döngüde parçacıkların konumları, iki en iyi(best) değere göre güncellenir. Bu değerlerden ilki pbest, o ana kadar parçacığın elde ettiği en iyi çözümü sağlayan konum koordinatlarıdır. Diğer değer ise popülasyon tarafından elde edilen en iyi çözümü sağlayan konum koordinatlarıdır. Diğer değeri local en iyi(best) olarak kabul edersek, bu değer ise global en iyi olarak kabul edilir.

Aşağıda D adet parametrede oluşmuş, n adet parçacığın oluşturduğu popülasyon görülmektedir.

Popülasyon matrisine göre i. parçacık   Xi = [ Xi1,Xi2,…,…,X1D] şeklinde ifade edilir. En iyi değeri veren parçacığın pozisyonu için de pbest  şeklinde bir matris oluşturulur. Yine aynı şekilde yukarıdaki denklemde verilen hız parametresi de vektörle ifade edilir.

Denklemler de geçen C değerleri öğrenme faktörleridir. Bu değerler her parçacığı en iyi konuma çeken stokastik hızlanma terimlerini ifade eden sabitlerdir. İlk c değeri parçacığın kendi tecrübesine göre hareket etmesini, diğeri ise sürüdeki diğer parçacıkların tecrübelerine göre hareket etmesini sağlar. Bu sabitlerin değerleri belirlenirken dikkat edilmelidir. Düşük değerler seçilmesi durumunda hedefe doğru dolaşarak gider, böylelikle farklı yerler gezilerek, farklı kaynak bulma imkanı doğabilir. Fakat bu durum hedefe ulaşma süresini uzatır. Bu değerlerin yüksek seçilmesinde ise hedefe doğru hızla gidilir fakat bu durumun, hedefin atlanıp geçilmesine de sebep olabileceği unutulmamalıdır. Yapılan çalışmalar sonrasında elde edilen verilere göre en uygun c değerleri 2 olarak bulunmuştur. Ayrıca denklemde bulunan rand değerleri [0,1] arasında düzgün dağılımı rastgele değerlerdir. Denklemlerde geçen k değerleri ise iterasyon sayısını bildirmektedir.

PARÇACIKLARIN HIZ VE KOORDİNATI

Parçacıkların hız ve koordinat hesaplamaları yukarıda verdiğim I ve II numaralı denklemler ile yapılmaktadır. Yeni konum yeni hız ve bir önceki koordinat bilgisiyle hesaplanmaktadır. İkinci denklem bunu göstermektedir. x(k+1) bir sonraki koordinat bilgisi, mevcut koordinat bilgisi x(k) ile parçacığın o andaki hızı ile toplanarak bulunmakta.

İlk denklem ise mevcut hızı hesaplamaktadır. c1 ve c2 değerleri global en iyiye gidiş için önem arz etmektedir. Bu yüzden dikkatli seçilmelidir. Daha önce bahsettiğim gibi bu değerler genelde 2 seçilirler.

Yukarıda görüldüğü üzere verilen hız denklemi pbest ve gbest  değerlerine bağımlıdır. Bu yüzden tüm elemanlar hesaba katılmamaktadır. Bu yüzden formülü aşağıdaki şekildeki gibi de kullanabiliriz. Bu şekildeki kulanım sayesinde yeni  hız bulunurken sadece en iyilerin kullanımından kurtarılmış olacaktır. Formüldeki x değeri orantı sabiti, qi değeri ise pbest değerlerinin ağırlıklı toplamı olarak kullanılmaktadır.

Parçacık Sürüsü Optimizasyonu Algoritması’nda bir diğer önemli nokta da komşuluk seçimidir. Üzerinde çalıştığımız probleme göre komşuluk seçimi stratejisi belirlenir. Komşuluk seçimi için genel olarak kullanılan birkaç metod vardır.

KAYNAKLAR

  • Particle Swarm Optimization and Differential Evolution Algorithms: Technical Analysis, Applications and Hybridization Perspectives
  • Parçacık Sürüsü Optimizasyon Algoritması ve Benzetim Örnekleri – Seçkin Tamer-Cihan Karakuzu
  • Parçacık Sürü Optimizasyonunda Yeni Bir Birey Davranış Biçimi Önerisi – Ö.Tolga Altınöz-A.Egemen Yılmaz
  • http://www.swarmintelligence.org
  • http://wikipedia.org

Diferansiyel Gelişim Algoritması (Differential Evolution Algorithm)

Diferansiyel Gelişim Algoritması (DGA), popülasyon tabanlı sezgisel bir optimizasyon tekniğidir. Global optimizasyon için basit ama güçlü bir tekniktir. Özellikle sürekli verilerin söz konusu olduğu problemlere yönelik olarak geliştirilmiştir ve rastlantısal bir yapıya sahiptir. Temeli genetik algoritmaya dayanır. Benzer operatörleri kullansalar da bu operatörlerin yapısı ve kullanım şekilleri birbirinden farklıdır. Genel anlamda algoritmanın adımları aşağıdaki gibidir.

Algoritmanın adımlarını sırasıyla inceleyelim;

1. Kontrol Parametrelerinin Değerlerini ve Sınırlarını Atama

Temel anlamda parametrelerimiz aşağıdaki gibidir;

  • Değişken Sayısı (D) : minimum 1 olmak üzere istenilen sayı verilebilir. Kromozomdaki gen sayısı olarak düşünülebilir. (1,2,…….,j)
  • Maksimum Jenerasyon Sayısı (Gmax) : Oluşturulacak olan popülasyonun kaç jenerasyon boyunca mutasyon, rekombinasyon ve seleksiyona tabî tutulacağını belirtir. (1,2,…….Gmax)
  • Popülasyon büyüklüğü (NP) : Popülasyonun büyüklüğünün ne kadar olacağını belirtir. Bu da kromozom sayısı olarak düşünülebilir.
  • Ölçekleme Faktörü (F) : Ölçekleme faktörüdür, kullanıcı belirleyecektir.
  • Çaprazlama Oranı (CR) : Olasılığı temsil eder bu yüzden 0 ile 1 arasında değer alır.
  • Xlo ve Xhi  değerleri ise parametre sınırlarını belirtmektedir.

Kontrol parametrelerinin  değerlerinin atanması işlemi şu şekilde temsil edilir;

NP üçten büyük olmalıdır, çünkü Diferansiyel Gelişim Algoritması’nda yeni kromozomların üretilebilmesi için mevcut kromozon dışında üç adet kromozom gerekmektedir. NP adet D boyutlu kromozomdan meydana gelen başlangıç popülasyonun oluşturulma şekli aşağıdaki gibidir.

2. Başlangıç Popülasyonunun Oluşturulması

Mevcut popülasyon gelecek jenerasyonu oluşturmak için kullanılacağından dolayı başlangıç popülasyonu  iyi tanımlanmış sınırlamalara sahip bir araştırma uzayından uniform dağılımla rastgele elemanlar seçilerek oluşturulur.

3. Değerlendirme Fonksiyonu

Yeni bir birey üretildiğinde popülasyona girip girmeyeceğine değerlendirme fonksiyonuyla karar verilir. Hedef kromozomumuzun uygunluk değeri bilinmektedir. Yeni birey onunla karşılaştırılır ve popülasyona girip girmeyeceğine karar verilir. Böylelikle yeterince uygun olmayan bireyler popülasyona eklenmeyerek popülasyonun bozulmaması sağlanır.

4. Mutasyon İşlemi

Mutasyon işlemi parametre optimizasyonu açısından büyük önem  taşır. Kromozomun genleri üzerinde rasgele değişiklikler yapmaktır. Mutasyon sayesinde çözüm noktası çözüm uzayında hareket etmektedir. Bir anlamda mutasyon arama uzayını genişletmektedir. Böylelikle daha çok bölgeye ulaşılıp farklı çözümlere ulaşılabilme ihtimali ortaya çıkar. Mutasyondan beklenen çözümün, çözüm uzayında doğru yönde ve  doğru miktarda hareket etmesidir. Bu sayede bir yerde takılıp kalınmaz. Fakat bu hareketin beklenen şekilde doğru yönde ve doğru miktarda olması garanti edilemez. Mutasyona tabî tutulacak kromozom dışında birbirinden farklı üç kromozom seçilir. () İlk ikisinin farkı alınır ve ölçekleme faktörüyle çarpılır. F genellikle 0 ile 2 arasında değerler almaktadır. Ağırlıklandırılmış fark kromozomu ile üçüncü kromozom toplanır. Amacı amaç vektörleri doğru yönde hareket ettirecek artışları üretmektir.

5. Rekombinasyon İşlemi

Mutasyon işlemi temel olarak yeni araştırma bölgelerinin araştırılmasından sorumludur. Rekombinasyon ya da çaprazlama işleminin amacı ise var olan amaç vektör parametrelerinden yararlanarak yeni vektörler oluşturmak suretiyle araştırmanın başarılı olması için yardımcı olmaktır. Rekombinasyon önceki jenerasyonla başarılı çözümleri birleştirir. Daha iyi bireyler üretmek için eldeki bireyler çaprazlanır.  Mutasyon işlemini gerçekleştirirken elde ettiğimiz fark kromozomu ve Xi,g kromozomu kullanılarak yeni deneme kromozomu (Ui,G+1) üretilir. Deneme kromozomuna genler CR olasılıkla fark kromozomundan 1-CR olasılıkla mevcut kromozomdan seçilir. j=jrand koşulu, en az bir tane genin üretilen yeni kromozomdan alınmasının garanti olması için kullanılır.

6. Seleksiyon İşlemi

Yeni üretilen bireylerin hangi şartlar altında popülasyona girebileceğini tanımlayan kriterdir. Buradaki seleksiyon yöntemi aç gözlü olarak seçilmiştir. Bilindiği üzere diğer evrimsel algoritmalarda kullanılan Deterministik, Rulet Tekerleği, Rasgele ve Turnuva gibi seleksiyon metodları bulunmaktadır. Çalışılan probleme göre bu metodlarda biri de burada tercih edilebilir. Deterministik te belirli sayıdaki en iyi bireyler ile yeni popülasyon oluşturulur, kötü bireyler popülasyona katılmaz. Rulet tekerleğinde, her bireyin çözüme uygunluk derecesi arttıkça yeni popülasyona aktarılma şansı artar. Rasgele seçimde bireylerin uygunluk dereceleri seçilme şanslarını etkilemez. Turnuva metodunda, rasgele seçilen iki birey arasında uygunluk derecesi yüksek olan popülasyona katılırken diğer birey popülasyona kabul edilmez.

Mutasyon, rekombinasyon ve seleksiyon işlemleri durdurma kriteri sağlanana kadar tekrar sırasıyla devam ettirilir. Diferansiyel gelişim algoritmasını maksimum jenerasyon sayısına ulaşana denk çalışır ve ulaştığında algoritma durdurulur. Buna ek algoritmanın çalışması maksimum jenerasyon sayısı ile değil belirlenen durdurma kriterine göre de belirlenebilir. Bu durumda en iyi ve en kötü bireylerin arasındaki farkın belirlenen miktara kadar düşmesi durumunda algoritma sonlandırılır.

Diferansiyel Gelişim Algoritması sürekli parametreleri söz konusu olduğu durumlarda oldukça başarılı sonuçlar veren bir algoritmadır.

KAYNAKLAR

  • Particle Swarm Optimization and Differential Evolution Algorithms : Technical Analysis, Applications and Hybridization Perspectives
  • Yapay Zeka Optimizasyon Algoritmaları – Derviş Karaboğa
  • Diferansiyel Gelişim Algoritması – Timur Keskintürk
  • http://tr.wikipedia.org
  • Diferansiyel Gelişim Algoritması Kullanılarak Sinyal Kesimine Yönelik Adaptik SDY Süzgeç Tasarımı
  • An Introduction to Differential Evolution – Kelly Fleetwood
  • Differential Evolution : A Simple Evolution Strategy for Fast Optimization – Napapan Piyasatian

Yapay Arı Koloni Algoritması (Artificial Bee Colony – ABC Algorithm)

Giriş

Bu yazıda önce Yapay Arı Koloni Algoritmasının (Artificial Bee Colony – ABC) temelini teşkil eden gerçek arıların yiyecek arama davranışı açıklanacaktır. Sonra yapay arı algoritması ve bu algoritmanın örnek bir problem için uygulamada kullanılması gösterilecektir.

Gerçek Arıların Davranışları

Doğal bir arı kolonisinde yapılacak işler o iş için özelleşmiş arılar tarafından yapılır. Yani yapılacak işlere göre arılar arasında bir iş bölümü vardır ve kendi kendilerine organize olabilmektedirler. İş bölümü yapabilme ve kendi kendine organize sürü zekâsının iki önemli bileşenidir. Arıların minimal yiyecek arama modelinde temel üç bileşen vardır. Bunlar; yiyecek kaynakları, görevli işçi arılar ve görevsiz işçi arılar.

Yiyecek kaynakları

Arıların nektar, polen veya bal elde etmek için gittikleri kaynaklardır. Kaynağın değeri, çeşidi, yuvaya yakınlığı, nektar konsantrasyonu veya nektarın çıkarılmasının kolaylığı birçok etkene bağlı olabilir. Ama kaynağın zenginliği tek ölçüt olarak alınabilir.

Görevli İşçi Arılar

Daha önceden keşfedilen belli kaynaklara ait nektarın kovana getirilmesinden sorumludur. Ayrıca ziyaret ettikleri kaynağın kalitesi ve yeri ile ilgili bilgiyi kovanda bekleyen diğer arılarla da paylaşırlar.

Görevsiz İşçi Arılar

Nektarın toplanacağı kaynak arayışı içerisindeki arılardır. Görevi belirsiz iki çeşit işçi arı bulunmaktadır. Bunlar; rastgele kaynak arayışında olan kâşif arılar ve kovanda bekleyen ve görevli arıları izleyerek bu arılar tarafından paylaşılan bilgiyi kullanarak yeni kaynağa yönelen gözcü arılardır.

Görevli arıların yiyecek kalitesi ve yeri ile ilgili bilgi paylaşımı dans alanında olmaktadır. Bir arı dans ederken diğer arılar ona antenleri ile dokunur ve bulduğu kaynağın tadı ve kokusu ile ilgili bilgiyi alır.

Danslar

Kaynağın kovana olan mesafesine göre çeşitli danslar mevcuttur: dairesel dans, kuyruk dansı ve titreme dansı gibi.

Daire Dansı Belirlenen yiyecek kaynağının kovana olan uzaklığı maksimum 50-100 metre civarında olduğundan bu dans yön ve uzaklık bilgisi içermez.

Titreme Dansı Arıların petek üzerinde düzensiz tarzda ve yavaş tempoda bacaklarını titreterek ileri, geri, sağa ve sola hareketleri söz konusudur. Arı zengin bir nektar kaynağı bulduğunu ancak kovana işlenebileceğinden fazla nektar geldiğini ve bundan dolayı nektar işleme görevine geçmek istediğini belirtmektedir. Bu dansın amacı kovan kapasitesi ve yiyecek getirme aktivitesi arasındaki dengeyi sağlamaktır.

Kuyruk Dansı 100 metreden 10 kilometreye kadar olan geniş bir alan içerisinde bulunan kaynaklarla ilgili bilgi aktarımında kullanılır. Bu dans 8 rakamına benzeyen figürlerin yapıldığı dans çeşididir. Dansı izleyen arıların bir titreşim oluşturması ile dansa son verilir. Dansın her 15 saniyede tekrarlanma sayısı, nektar kaynağının uzaklığı hakkında bilgi vermektedir. Daha az tekrarlanma sayısı daha uzak bölgeleri ifade etmektedir.

Yön bilgisi Şekil-1’deki gibi 8 rakamı şeklindeki dansın açı bilgisinden elde edilir. Şekilde verilen örnekte dansı izleyen arılar, danstan güneşle yiyecek arasındaki açının 45o olduğunu anlamaktadırlar.

Şekil-1 Arılarda Dans

Tüm zengin kaynaklarla ilgili bilgiler dans alanında gözcü arılara iletildiğinden, gözcü arılar birkaç dansı izledikten sonra hangisini tercih edeceğine karar verir. Yiyecek arayıcı arıların daha iyi anlaşılabilmesi için Şekil-2’deki verilen modelin incelenmesi faydalı olacaktır.

A ve B ile gösterilen iki keşfedilmiş kayna bölgesi olduğunu varsayılım. Araştırma başlangıcında potansiyel yiyecek arayıcı, görevi belirsiz bir işçi arı olarak araştırmaya başlayacak ve bu arı kovan etrafındaki kaynakların yerinden haberdar degildir. Bu durumdaki arı için iki olası durum söz konusudur.

  1. Bu arı kaşif arı olabilir ve içsel ve dışsal etkilere bağlı olarak yiyecek aramaya başlayabilir (Şekil-2’de S ile gösterilmiştir).
  2. Bu arı kuyruk dansını izleyen gözcü arı olabilir ve izlediği dansla anlatılan kaynağa gidebilir (Şekil-2’de R ile gösterilmektedir). Bir kaynak keşfedildikten sonra arı imkanları dahilinde bu kaynağın yerini hafızaya alır ve hemen nektar toplamaya başlar. Bu arı artık nektarın zenginliğine göre görevli arı haline gelmiş olur. İşçi arı nektarı aldıktan sonra kovana döner ve bunu yiyecek depolayıcılara aktarır. Nektar aktarıldıktan sonra arı için üç seçenek ortaya çıkmaktadır:
  • Gittiği kaynağı bırakarak bağımsız işçi olabilir (Şekil-2’de UF ile gösterilmiştir).
  • Gittiği kaynağa dönmeden önce dans eder ve kovandaki arkadaşlarını da aynı kaynağa yönlendirebilir ( Şekil-2’de EF1 ile gösterilmiştir).
  • Diger arıları yönlendirmeden direkt kaynağa gidebilir (Şekil-2’de EF2 ile gösterilmiştir).

Şekil-2 Yiyecek Arama Çevrimi

Yapay Arı Kolonisi Algoritması

Doğada var olan zeki davranışlar içeren süreçlerin incelenmesi araştırmacıları yeni optimizasyon metotları geliştirmeye sevk etmiştir. Derviş Karaboğa, arıların yiyecek arama davranışını modelleyerek Yapay Arı Kolonisi(ABC) algoritması geliştirilmiştir.

Derviş Karaboğa’nın ABC algoritmasının temel aldığı modelde bazı kabuller yapılmaktadır. Bunlardan birincisi her bir kaynağın nektarının sadece bir görevli arı tarafından alınıyor olmasıdır. Yani görevli arıların sayısı toplam yiyecek kaynağı sayısına eşittir. İşçi arıların sayısı aynı zamanda gözcü arıların sayısına eşittir. Nektarı tükenmiş kaynağın görevli arısı artık kâşif arı haline dönüşmektedir. Yiyecek kaynaklarının yerleri optimizasyon problemine ait olası çözümlere ve kaynakların nektar miktarları ise o kaynaklarla ilgili çözümlerin kalitesine (uygunluk) karşılık gelmektedir. Dolayısıyla ABC optimizasyon algoritması en fazla nektara sahip kaynağın yerini bulmaya çalışarak uzaydaki çözümlerden problemin minimumu yada maksimumunu veren noktayı bulmaya çalışmaktadır.

Bu Modele ait süreç adımları aşağıdaki gibi verilebilir.

  1. Yiyecek Arama surecinin başlangıcında, kaşif arılar çevrede rastgele arama yaparak yiyecek aramaya başlarlar.
  2. Yiyecek kaynakları bulunduktan sonra, kaşif arılar artık görevli arı olurlar ve buldukları kaynaklardan kovana nektar taşımaya başlarlar. Her bir görevli arı kovana donup getirdiği nektarı boşaltır ve bu noktadan sonra ya bulduğu kaynağa geri döner ya da kaynakla ilgili bilgiyi dans alanında sergilediği dans aracılığıyla kovanda bekleyen gözcü arılara iletir. Eğer faydalandığı kaynak tükenmiş ise görevli kaşif arı haline gelir ve yeni kaynak arayışına yönelir.
  3. Kovanda Bekleyen gözcü arılar zengin kaynakları işaret eden dansları izlerler ve yiyeceğin kalitesi ile orantılı olan dans frekansına bağlı olarak bir kaynağı tercih ederler.

ABC algoritmasının bu süreçleri ve temel adımları ise şu şekilde sıralanabilir;

  1. Başlangıç yiyecek kaynağı bölgelerinin üretilmesi
  2. Repeat
  3. İçi arıların yiyecek kaynağı bölgelerine gönderilmesi
  4. Olasılıksal seleksiyonda kullanılacak olasılık değerlerinin görevli arılardan gelen bilgiye göre hesaplanması
  5. Gözcü arıların olasılık değerlerine göre yiyecek kaynağı bölgesi seçmeleri
  6. Kaynağı bırakma kriteri:limit ve kaşif arı üretimi
  7. Until çevrim sayısı=Maksimum çevrim sayısı

Yiyecek arayan arılarda görülen zeki davranış ile bu davranışı simule eden ABC algoritmasının temel birimleri aşağıda açıklanmaktadır.

1.Başlangıç Yiyecek Kaynağı Bölgelerinin Üretilmesi

Arama uzayını yiyecek kaynaklarını içeren kovan çevresi olarak düşünürsek algoritma arama uzayındaki çözümlere karşılık gelen rastgele yiyecek kaynağı yerleri üreterek çalışmaya başlamaktadır. Rastgele yer üretme sureci her bir parametrelerinin alt ve üst sınırları arasında rastgele değer üreterek gerçeklenir (Eşitlik-1).

Burada i=1… SN, J=1…D ve SN yiyecek kaynağı sayısı ve D is optimize edilecek parametre sayısıdır. Xmin j parametrelerin alt sınırıdır.

2. İsçi Arıların Yiyecek Kaynağı Bölgelerine Gönderilmesi

Daha öncede belirtildiği gibi her bir kaynağın bir görevli arısı vardır. Dolayısıyla yiyecek kaynakların sayısı görevli arıların sayısına eşittir. İşçi arı çalıştığı yiyecek kaynağı komşuluğunda yeni bir yiyecek kaynağı belirler ve bunun kalitesini değerlendirir. Yeni kaynak daha iyi ise bu yeni kaynağı hafızasına alır. Yeni kaynağın mevcut kaynak komşuluğunda belirlenmesinin benzetimi Eşitlilik-2 tanımlanmaktadır.

xi ile gösterilen her bir kaynak için bu kaynağın yani çözümünün tek bir parametresi (rastgele seçilen parametresi, j) değiştirilerek xi komşuluğunda vi kaynağı bulunur. Eşitlik 2 de j,[1,D] aralığında rastgele üretilen bir tamsayıdır. Rastgele seçilen j parametresi değiştirilirken, yine rastgele seçilen xk komsu çözümünün ( k E {1,2,SN} ) j. parametresi ile mevcut kaynağın j parametresinin farkları alınıp [-1 1 ] arasında rastgele değer alan  sayısı ile ağırlandırıldıktan sonra mevcut kaynağın j parametresine eklenmektedir.

Eşitlik-2’den de görüldüğü gibi  xi,j ve xk,j arasındaki fark azaldıkça yani çözümler birbirine benzedikçe xi,j parametresindeki değişim miktarı da azalacaktır. Böylece bölgesel optimal çözüme yaklaştıkça değişim miktarı da adaptif olarak azalacaktır.

Bu işlem sonucunda üretilen vi,j‘nin daha önceden belli olan parametre sınırları asması durumunda j. parametreye ait olan alt veya üst sınır değerlerine ötelenmektedir (Eşitlik-3).

Sınırlar dâhilinde üretilen vi parametre vektörü yeni bir kaynağa temsil etmekte ve bunun kalitesi hesaplanarak bir uygunluk değeri atanmaktadır (Eşitlik-4).

Burada fi ve vi kaynağının yani çözümünün maliyet değeridir. xi ve vi arasında nektar miktarlarına yani uygunluk değerlerine göre bir açgözlü (greddy) semce işlemi uygulanır. Yeni Bulunan vi çözümü daha iyi ise görevli arı hafızasından eski kaynağın yerini silerek vi kaynağının yerini hafızaya alır. Aksi takdirde görevli arı xi kaynağına gitmeye devam eder ve xi çözümü geliştirilemediği için xi kaynağı ile ilgili geliştirememe sayacı (failure) bir artar, geliştirdiği durumda ise sayaç sıfırlanır.

3. Gözcü Arıların Seleksiyonda Kullanacakları Olasılık Değerlerinin Hesaplanması (Dans Benzetimi)

Tüm görevli arılar bir çevrimde araştırmalarını tamamladıktan sonra kovana donup buldukları kaynakların nektar miktarları ile ilgili gözcü arılara bilgi aktarırlar. Bir gözcü arı dans aracılıyla paylaşılan bilgiden faydalanılarak yiyecek kaynaklarının nektar miktarları ile orantılı bir olasılıkla bir bölge(kaynak) seçer. Bu ABC‘nin altında çoklu etkileşim sergilendiğinin bir örneğidir. Olasılıksal seçme işlemi, algoritmada nektar miktarlarına karşılık gelen uygunluk değerleri uygulanarak yapılmaktadır. Uygunluk değerine bağlı seçme işlemi rulet tekerliği,sıralamaya dayalı, stokastik ,örnekleme, turnuva yöntemi yada diğer seleksiyon şemalarından herhangi biri ile gerçeklenir.Temel ABC algoritmasında bu seleksiyon işlemi rulet tekerliği kullanılarak yapılmıştır. Tekerlekteki her bir dilimin açısı uygunluk değeri toplamına oranı o kaynağın diğer kaynaklara göre nispi seçilme olasılığı olduğunu vermektedir (Eşitlik-5).

Burada  kaynağın kalitesini SN görevli arı sayısını göstermektedir. Bu olasılık hesaplama işlemine göre bir kaynağın nektar miktarı arttıkça (uygunluk değeri arttıkça) bu kaynak bölgesini seçecek gözcü arı sayısı da artacaktır. Bu özellik ABC’ nin pozitif geri besleme özelliğine karşılık gelmektedir.

4. Gözcü Arıların Yiyecek Kaynağı Bölgesi Seçmeleri

Algoritma da olasılık değerleri hesaplandıktan sonra be değerler kullanılarak rulet tekerleğine göre secim işleminde her bir kaynak için [0.1] aralığında rastgele sayı üretilen ve pi değeri bu üretilen sayıdan büyükse görevli arılar gibi gözcü arı da Eşitlik-2’yi kullanarak bu kaynak bölgesinde yeni bir çözüm üretir. Yeni çözüm değerlendirilir ve kalitesi hesaplanır. Sonra yeni çözümle eski çözümün uygunluklarının karşılaştırıldığı en iyi olanın seçildiği açgözlü seleksiyon işlemine tabi tutulur. Yeni çözüm daha iyi ise eski çözüm yerine bu çözüm alınır ve çözüm geliştirememe sayacı (failure) sıfırlanır. Eski çözümün uygunluğu daha iyi ise bu çözüm muhafaza edilir ve geliştirememe sayacı (failure) bir artırılır. Bu süreç,tüm gözcü arılar yiyecek kaynağı bölgelerine dağılana kadar devam eder.

5. Kaynağı Bırakma Kriteri: Limit ve Kaşif Arı Üretimi

Bir çevrim sonunda tüm görevli ve gözcü arılar arama süreçlerini tamamladıktan sonra çözüm geliştirememe sayaçları (failure) kontrol edilir. Bir arının bir kayaktan faydalanıp faydalanmadığı, yani gidip geldiği kaynağın nektarının tükenip tükenmediği çözüm geliştirememe sayaçları aracılığıyla bilinir. Bir kaynak için çözüm geliştirememe sayacı belli bir eşik değerinin üzerindeyse, artık bu kaynağın görevli arısının tükenmiş olan o çözümü bırakıp kendisi için başka bir çözüm araması gerekir. Bu da biten kaynakla ilişkili olan görevli arının kâşif arı olması anlamına gelmektedir. Kâşif arı haline geldikten sonra, bu arı için rastgele çözüm arama sureci başlar (Eşitlik-1). Kaynağın terk ettiğinin belirlenmesi için kullanılan eşik değeri ABC algoritmasının önemli bir kontrol parametresidir ve “limit” olarak adlandırılmaktadır. Temel ABC algoritmasında her çevrimde sadece kâşif arının çıkmasına izin verilir.

Tüm bu birimler arasındaki ilişki ve döngü Şekil-3’deki gibi bir akış diyagramı ile şematize edilebilir.

6. Seleksiyon Mekanizmaları

ABC algoritması 4 farklı seleksiyon işlemi kullanmaktadır.Bunlar ;

  1. Potansiyel iyi kaynaklarının belirlenmesine yönelik eşitlik 5 olasılık değerlerinin hesaplandığı global olasılık temelli seleksiyon sureci.
  2. Görevli ve gözcü arıların renk,şekil,koku gibi nektar kaynağının turunu belirlenmesi sağlayan görsel bilgiyi kullanarak bir bölgede kaynağın bulunmasına vesile olan bölgesel olasılık tabanlı seleksiyon işlemi (Eşitlik-2).
  3. İşçi ve gözcü arıların daha iyi olan kaynağı belirlemek amacıyla kullandıkları açgözlü seleksiyon.
  4. Kâşif Arılar tarafından eşitlik 1 aracılıyla gerçekleştirilen rastgele seleksiyon.

Bütün bu seleksiyon metotların bir arada kullanılmasıyla ABC algoritması hem iyi bir global araştırma hem de bölgesel araştırma yapabilmektedir.

ABC Algoritması Akış Şeması

7. ABC Algoritmasının Adımları

Önceki bölümlerde genel hatları ile ABC algoritmasının adımları ve her bir adımda yapılan işlemler tarif edilmişti ancak bu adımları sözde kod seklinde baştan aşağı yazmak faydalı olacaktır.

  1. Eşitlik 1 aracılıyla tüm xi,j i=1…SN,j =1…D, çözümlerine başlangıç değerlerinin atanması ve çözüm geliştirememe sayaçlarının  sıfırlanması failurei=0
  2. fi=f(xi) fonksiyon değerlerinin ve bu değerlere karşılık gelen uygunluk değerlerin  hesaplaması
  3. Repeat
  4. for i=1 to Sn do
  5. Eşitlik 2 kullanarak xi çözümünün görevli arısı için yeni bir kaynak üret vi ve f(vi)’yi (4) eşitliğinde yerine koyarak bu çözümün uygunluk değerini hesapla
  6. xi ve vi arasında açgözlü seleksiyon işlemi uygula ve daha iyi olanı seç
  7. xi çözümü gelişememişse çözüm geliştireme sayacını bir artır failurei= failurei+1, gelişmemişse sıfırla, failurei=0
  8. End For
  9. Eşitlik 5 ile gözcü arıların seçim yaparken kullanacakları uygunluk değerine dayalı olasılık değerlerini pi hesapla
  10. t=0 i=1
  11. Repeat
  12. if random<pi then
  13. Eşitlik 2 ‘i kullanarak gözcü arı için yeni bir kaynak, vi üret
  14. xi ve vi arasında açgözlü seleksiyon işlemi uygula ve daha iyi olanı seç.
  15. xi çözümü gelişememişse çözüm geliştirememe sayacını bir artır failurei= failurei+1, gelişmemişse sıfırla, failurei=0
  16. t=t1
  17. End İf
  18. Until t=SN
  19. if max (failurei) > limit then
  20. xi eşitlik 1 ile üretilen rastgele bir çözümle değiştir.
  21. End İf
  22. En İyi Çözümü hafıza da tut
  23. Until Durma kriteri

ABC’nin Temel Özellikleri

ABC algoritmasının temel özellikleri şu şekilde sıralanabilir;

  1. Oldukça esnek ve basittir.
  2. Gerçek yiyecek arayıcı arıların davranışlarına oldukça yakın şekilde simule eder.
  3. Sürü zekâsına dayalı bir algoritmadır.
  4. Nümerik problemler için geliştirilmiştir ama ayrık problemler içinde kullanılabilir.
  5. Oldukça az kontrol parametresine sahiptir
  6. Kâşif Arılar tarafından gerçekleştirmen küresel ve görevli ve gözcü arılar tarafından gerçekleştirilen bölgesel araştırma kabiliyetine sahiptir ve ikisi paralel yürütülmektedir.

UYGULAMA VE DENEY SONUÇLARI

Algoritmanın performansını Rastrigin Problemi üzerinde görmeye çalıştık. Bu anlamda bu fonksiyonu çözmeye çalıştık. Deney sonuç ve performanslarına geçmeden önce Rastrigin Problemi ve Fonksiyonu nedir ve ne işe yarar bundan bahsetmek istiyorum. Rastrigin fonksiyonu içerisinde birçok lokal minimumu içeren ve bu yüzden de optimizasyon tekniklerinin performansını ölçmek için ideal olan bir test fonksiyonudur. Fonksiyonun global minimumu iki boyutlu uzay için [0,0] noktası, üç boyutlu bir uzay için ise [0,0,0] noktasıdır. Fonksiyonun grafik üzerindeki görünümü aşağıdaki şekildeki gibidir.

Kullandığım demo uygulama http://mf.erciyes.edu.tr/abc/ web sitesinden alınmıştır. Çeşitli optimizasyon problemleri üzerinde ABC Algoritması’ nın performansını gözlemektedir. Biz yukarıda da bahsettiğimiz üzere bu fonksiyonlardan Rastrigin Fonksiyonunu kullandık. Demo uygulamanın genel görünümü aşağıdaki gibidir.

Öncelikle uygulamanın parametrelerine bakalım. Demo üzerinde parametreler ve açıklamaları aşağıda sırasıyla verilmiştir.

  • # of parameter: Üzerinde çalışılan uzayın boyutu. Biz uygulamamızda anlaşılması ve gözlemi kolay olması maksadıyla 2 boyutlu uzayda çalışmayı tercih ettik.
  • Colony Size: Kolonide bulunan arı miktarı.
  • Parameter Range: Algoritmanın çalışmasını istediğimiz aralık. Yukarıdaki görülen şekilde aralık [-5,5] olarak seçilmiştir. Böylelikle alan daraltılarak arıların hareketi daha rahat görülmektedir.
  • # of Cycle: Algoritmanın durdurma kriteri olarak çalışma sayısı belirtilmiştir.
  • Limit: Her döngüde görevli ve gözcü arılar arama süreçlerini tamamladıktan sonra çözüm geliştirememe sayaçlarına bakarlar eğer ki limit değeri aşılmışsa yani algoritma belli bir süre boyunca artık iyi değer vermemeye başlamışsa bu bölgeden vazgeçilir. Limit değeri bu sayacı belirtmektedir.
  • # of Runs: Algoritmanın baştan itibaren kaç defa çalışacağı. Biz her defasında varsayılan değer kabul edilen bir kez çalıştırdık.

Ayrıca demo şekil üzerinde görülen Obtained kısmı algoritmanın bulduğu en iyi değerleri, Desired kısmı fonksiyonun beklenilen değerlerini, üst soldaki grafik Rastrigin Fonksiyonu’nun grafiksel olarak üç boyutlu görünümünü, üst sağdaki grafik fonksiyon grafiğinin üstten görünümünü, sol alttaki grafik en iyi değerin kaçıncı döngüde bulunduğunu ve bulunan değerlerin ortalama iyiliğini göstermektedir. Sağ alttaki grafik ise arıların hareketini her döngüde izleme imkânı sunmaktadır. Buradaki mavi noktalar, görevli işçi arılar;  yeşil noktalar, kaşif; kırmızı noktalar, beklenen değer; ve son olarak da mor noktalar, o ana kadar ki bulunan en iyi çözüm noktasını göstermektedir.

Deney Sonuçları: Yaptığımız deneylerde Colony Size, Cycle Sayısı ve Limit Sayısı parametrelerinin algoritmanın performansı üzerindeki etkilerine baktık. Her deney çeşidi için en az 5’er adet deney yapılmıştır.

Colony Size Deneyi

            Sabit Değerler: Parameter Range (-5,5), Cycle (100), Limit (20)

  1. Deney Colony Size Değeri: 30
  2. Deney Colony Size Değeri: 50
  3. Deney Colony Size Değeri: 60
  4. Deney Colony Size Değeri: 75
  5. Deney Colony Size Değeri: 100

Deney Değerlendirmesi: Bulunan en iyi değerlere bakıldığında yaptığımız deney için Colony Size değişimi çok etki etmemiştir fakat Colony Size’ın artışı algoritmanın daha az döngüde en iyi değerlere ulaşmasını sağlamıştır. Yani koloni büyüklüğü problemin daha kısa sürede çözülmesini sağlamaktadır. Bu durumda eğer ki Colony Size’ı artırma imkânımız yoksa döngü (cycle) sayısının yüksek tutulması gerekir. Aksi takdirde en iyi çözüme çok yakın olan çözümlere ulaşamayabiliriz.

# of Cycle Deneyi (Döngü Sayısı)

            Sabit Değerler: Colony Size(50), Parameter Range (-5,5), Limit (20)

  1. Deney Cycle Değeri: 10
  2. Deney Cycle Değeri: 20
  3. Deney Cycle Değeri: 50
  4. Deney Cycle Değeri: 70
  5. Deney Cycle Değeri: 100

Deney Değerlendirmesi: Colony Size deneyinde 10 ile 100 döngü arasında deneyler yaptık. 10 beklenen değerler için çok bir sayı oldu ve hata oranı çok fazla çıktı. Belirlenen parametrelerde için bu deneyde cycle değerini artırmaya başladık ilk anlamlı sonuç 20’de çıkmıştır ve beklenen değere yüzde bir oranında hataya sahip değerler bulunmuştur. Bundan sonraki artışlar hata oranını giderek düşürmeye başlamış fakat yaklaşık 70 cycle’dan sonra hata oranında çok fazla bir değişim olmamaya başlamıştır. Belirlenen sabit parametrelere göre bu deney için yaklaşık 70 cycle değeri uygun bir değer olarak belirlenmiştir. Cycle değeri belli bir yere kadar olumlu etki etmekte, belli bir yerden sonra ise etmemektedir.

# Limit Deneyi

            Sabit Değerler: Colony Size(50), Parameter Range (-5,5), Cycle(80)

  1. Deney Limit Değeri: 5
  2. Deney Limit Değeri: 10
  3. Deney Limit Değeri: 20
  4. Deney Limit Değeri: 40
  5. Deney Limit Değeri: 50
  6. Deney Limit Değeri: 60
  7. Deney Limit Değeri: 70

Deney Değerlendirmesi: Limit deneyinde diğer parametreler sabit kalmak koşuluyla limit değeri olarak 5’ten 70’e kadar deneyler yaptık. 5 değerinde yüksek cycle değerlerinde beklenen değere yakın değerler elde ettik. Limit değerini artırmaya başladık ve yavaş yavaş daha az cycle’da beklenen değerlere çok yakın değerler elde etmeye başladık. Fakat sabit değerlerle birlikte yaklaşık 20 limit değerinden sonraki değerlerde çok tutarlı sonuçlar elde edemedir. Yani 20 için daha az iken, 40 ta cycle değeri arttı, ama 50’de yine azaldı. Bu deneyler sonucunda limit değerinin cycle sayısına göre ayarlanması gerektiğiniz düşünüyoruz. Çünkü bu deneyde cycle 80 iken limit değerini 70’e kadar artırdık. Belli bir noktadan sonra anlamsız sonuçlar elde ettik. Bu sebeple limit için bizim düşüncemiz cycle sayısının yaklaşık yüzde 10’u ile %25’i arasında bir değer alması ideal olacaktır.

KAYNAKLAR