Popülasyon optimizasyon algoritmaları: Bakteri yiyecek arama optimizasyonu (Bacterial Foraging Optimization, BFO)

İçindekiler

1. Giriş
2. Algoritma tanımı
3. Test sonuçları

1. Giriş

Bakteri yiyecek arama optimizasyonu (Bacterial Foraging Optimization, BFO) algoritması, son derece karmaşık veya imkansız sayısal fonksiyon maksimizasyon/minimizasyon problemlerine yaklaşık çözümler bulmak için kullanılabilen büyüleyici bir optimizasyon tekniğidir. Algoritma, dağıtılmış optimizasyon ve kontrol için global bir optimizasyon algoritması olarak yaygın bir şekilde tanınmaktadır. BFO, Escherichia coli'nin sosyal yiyecek arama davranışından esinlenmiştir. BFO, çeşitli uygulama alanlarında ortaya çıkan gerçek dünya optimizasyon problemlerini çözmedeki etkinliği nedeniyle araştırmacıların dikkatini çekmiştir. E. coli'nin yiyecek arama stratejisinin arkasındaki biyoloji özgün bir şekilde taklit edilmiş ve basit bir optimizasyon algoritması olarak kullanılmıştır.

E. coli veya salmonella gibi bakteriler gezegendeki en başarılı organizmalar arasındadır. Bu çevik bakteriler, flagella adı verilen yarı sert uzantılara sahiptir ve bu uzantılarla kendilerini bir kıvrılma hareketiyle ilerletirler. Tüm flagellalar saat yönünün tersine döndüğünde, bir pervane etkisi yaratılır ve bakteri hemen hemen doğrusal bir yönde hareket eder. Bu durumda bakteri yüzme adı verilen bir hareket gerçekleştirir. Tüm flagellalar aynı yönde döner.

Flagella, E. coli bakterisinin yiyecek arama sırasında gerçekleştirdiği iki ana işlem olan takla atmasına veya yüzmesine yardımcı olur. Flagellalar saat yönünde döndüğünde, her bir flagella hücreyi iter. Flagellalar farklı yönlerde döndükçe, bakteri kendi etrafında dönerek bir takla hareketi gerçekleştirir. Bakteri uygun bir ortamda daha az takla atarak hareket ederken, zararlı bir ortamda besin gradyanını bulmak için sık sık takla atar. Flagellaların saat yönünün tersine hareketi bakterinin çok yüksek bir hızda yüzmesine yardımcı olur.

Yukarıdaki algoritmada, bakterilerin davranışı, bakteriyel kemotaksis adı verilen ve bu mikroorganizmaların çevredeki kimyasal bir uyarıcıya motor reaksiyonu olan bir mekanizma tarafından belirlenir. Bu mekanizma, bakterinin çekici maddelere (çoğunlukla besin maddeleri) doğru hareket etmesini ve itici maddelerden (bakteri için potansiyel olarak zararlı maddeler) uzaklaşmasını sağlar. Çekici ve itici maddeleri tespit eden reseptörler bakterinin kutuplarında bulunur.

Bakterinin küçük boyutu nedeniyle, kutuplar arasındaki yararlı ve zararlı madde konsantrasyonlarındaki farkı yakalayamaz. Bakteriler, hareket sırasında konsantrasyonlarındaki değişiklikleri ölçerek bu maddelerin gradyanlarını belirler. Bu hareketin hızı saniyede onlarca bakteri uzunluğuna ulaşabilir. Örneğin, Escherichia coli genellikle saniyede kendi uzunluğunun 10-20'si kadar bir hızla hareket eder.

Şekil 1. Replikasyon: orijinal (hareket vektörünün korunması) ve klonlanmış (hareket vektöründe değişiklik) bakterilere bölünme.
Takla - bakterinin hareket vektöründe bir değişiklik.

Bakteri tarafından seçilen hareket yönü, çekici maddenin konsantrasyonundaki bir artışa (itici maddenin konsantrasyonundaki bir azalmaya) karşılık gelirse, bir sonraki taklaya kadar geçen süre artar. Bakterinin küçük boyutu nedeniyle, hareketi Brownian hareketinden güçlü bir şekilde etkilenir. Sonuç olarak, bakteri ortalama olarak sadece faydalı maddelere doğru ve zararlı maddelerden uzak yönlerde hareket eder.

Söz konusu bakteri hareketi mekanizması tek değildir. Bazı bakterilerin tek flagellası vardır. Bu durumda bakteri hareketinin varyantları, farklı dönme ve durma modları sağlar. Ancak, her durumda, bakteri doğru yönde hareket ederse, bu hareketin süresi artar. Bu nedenle, genel olarak, bakteriyel kemotaksis, bakterilerin yüksek besin konsantrasyonuna sahip yerlerde kalmasını ve kabul edilemez zararlı madde konsantrasyonlarından kaçınmasını sağlayan yüzme ve takla atmanın karmaşık bir kombinasyonu olarak tanımlanabilir.

Bir arama motoru optimizasyon problemi bağlamında, bakteriyel kemotaksis, bir bakteri tarafından bilinen gıda kaynaklarının kullanımını optimize etmek ve yeni, potansiyel olarak daha değerli alanları aramak için bir mekanizma olarak da yorumlanabilir. Yeterli bolluktaki bir bakteri popülasyonu, karmaşık uzay-zamansal yapılar oluşturabilir - bakteri popülasyonlarında yapı oluşumunun etkisi. Bu etki hem kemotaksis hem de diğer birçok nedenden kaynaklanabilir.

Bazı bakteriler için bu tür yapıların oluşumu, metabolik ürünlerinin düzenleyici özellikleri ile açıklanmaktadır. Benzer bir etki manyetotaksis (manyetik alana duyarlılık), biyokonveksiyon, negatif jeotaksis (mikroorganizmaların yerçekimi yönüne karşı tercihli hareketi) ve diğer fenomenlere dayalı olarak da mümkündür. Kural olarak, bakteriler dostane bir ortamda daha uzun bir mesafe kat ederler. Yeterince yiyecek bulduklarında boyları uzar ve doğru sıcaklıkta ortadan kırılarak kendilerinin birebir kopyasına dönüşürler.

Bu olgu Passino'ya BFO'ya üreme olayını eklemesi için ilham vermiştir. Ortamdaki ani değişiklikler veya bir saldırı nedeniyle kemotaktik süreç bozulabilir ve bakteri grubu başka bir yere gidebilir. Bu, gerçek bir bakteri popülasyonunda, bölgedeki tüm bakterilerin öldüğü veya bir grup bakterinin çevrenin yeni bir bölümüne dağıldığı bir elenme ve dağılma olayını temsil eder. Buna ek olarak, kemotaksis ve üreme prosedürleri, çok ekstremumlu amaç fonksiyonunun global maksimumunu bulmak için genellikle yetersizdir, çünkü bu prosedürler bakterilerin buldukları bu fonksiyonun yerel maksimumlarını terk etmelerine izin vermez. Elenme ve dağılma prosedürü bu eksikliğin üstesinden gelmek için tasarlanmıştır. Doğal seçilime (en uygun olanın hayatta kalması) göre, uygunluğu düşük olan bakteriler elenecek ve daha yüksek uygunluğa sahip bakteriler kendilerini yeniden üretecektir.

2. Algoritma tanımı

BFO'nun kanonik versiyonu aşağıdaki ana adımları içerir:

1. Bir bakteri kolonisi başlatma.
2. Kemotaksis.
3. Sürü oluşturma.
4. Üreme.
5. Elenme ve dağılma.

      
1. Parametreyi başlatma.
Bakteriler bazı yarı katı besin maddelerinde karmaşık, istikrarlı uzay-zamansal örüntüler oluşturabilir ve başlangıçta merkezde bir araya geldiklerinde bir ortamda hayatta kalabilirler. Dahası, belirli koşullar altında hücreler arası çekici sinyaller salgılayarak kümelenmelerini ve birbirlerini korumalarını sağlarlar.

2. Kemotaksis.
Bakterilerin yiyecek arayışındaki hareketlerinin özellikleri iki şekilde belirlenebilir, yani birlikte yüzme ve takla atma kemotaksis olarak bilinir. Bir bakterinin doğru yönde hareket ediyorsa "yüzdüğü", kötüleşen bir ortama doğru hareket ediyorsa "takla attığı" söylenir.

3. Sürü oluşturma.
Bakterilerin gıda açısından en zengin yere ulaşması için, en uygun bakterinin, arama dönemindeki bir noktaya kadar, diğer bakterileri çekmeye çalışması ve böylece istenen yerde daha hızlı bir şekilde bir araya gelmeleri arzu edilir. Bunu yapmak için, orijinal maliyet fonksiyonuna, her bir bakterinin bu arama süresine kadar en uygun bakteriye olan göreceli uzaklığına dayanan bir ceza fonksiyonu eklenir. Son olarak, tüm bakteriler karar noktasında birleştiğinde, bu ceza fonksiyonu sıfır olur. Sürü oluşturmanın etkisi, bakterilerin gruplar halinde toplanması ve yüksek bakteri yoğunluğuna sahip eşmerkezli örüntülerde hareket etmesidir.

4. Üreme.
Birkaç kemotaktik aşamadan geçen ilk bakteri kümesi üreme aşamasına ulaşır. Burada en iyi bakteri seti iki gruba ayrılır. Daha sağlıklı olan yarısının yerini, yiyecek bulma kabiliyetleri azaldığı için yok olan bakterilerin diğer yarısı alır. Bu da bakteri popülasyonunun evrim sürecinde sabit kalmasını sağlar.

5. Elenme ve dağılma.
Evrim sırasında, pürüzsüz evrim sürecini büyük ölçüde değiştirebilecek ve birçok bakterinin ortadan kalkmasına (elenmesine) ve/veya yeni bir ortama dağılmasına neden olabilecek ani ve öngörülemeyen bir olay meydana gelebilir. İronik bir şekilde, bu bilinmeyen olay bir bakteri kümesinin normal kemotaktik büyümesini bozmak yerine, daha yeni bir bakteri grubunu gıdanın olduğu yere daha yakın bir yere yerleştirebilir. Geniş bir perspektiften bakıldığında, elenme ve dağılma, bir popülasyonun uzun vadeli davranışının bir parçasıdır. Optimizasyona uygulandığında bu, bu tür paralel arama algoritmalarında sıklıkla görülen durgunluğu azaltmaya yardımcı olur.

Benim BFO uygulamam kanonik versiyondan biraz farklıdır. Kodun belirli bölümlerini ele alırken, bu değişikliklere duyulan ihtiyacın gerekçelerine ek olarak farklılıklar üzerinde de duracağım. Genel olarak, uygulamamdaki değişiklikler önemli olarak kabul edilemez, bu nedenle algoritmanın adına "m" (değiştirilmiş sürüm) işaretini atamayacağım. Sadece uygulanan değişikliklerin sonuçları iyileştirdiğini not edeceğim.

Şimdi de benim uygulamamın algoritmasına ve koduna bakalım.

Algoritma adımları:

1. Bakteri kolonisini başlatma.
2. Bakteri sağlığının ölçülmesi (uygunluk).
3. Replikasyon olacak mı?
3.1. Evet. Replikasyon gerçekleştir.
3.2. Hayır. Adım 4’e ilerle.
4. Eski mi (yaşam sınırına ulaşıldı mı)?
4.1. Evet. Bir takla at (hareket vektörünü değiştir).
4.2. Hayır. Adım 5’e ilerle.
5. Doğru yönde ilerleniyor mu?
5.1. Evet. Aynı vektörle hareket etmeye devam et.
5.2. Hayır. Bir takla at (hareket vektörünü değiştir).
6. Bakteri sağlığını (uygunluğunu) ölç.
7. Durma kriteri karşılanana kadar 3. adımdan itibaren tekrarla.

Algoritmanın mantıksal şeması Şekil 2'de gösterilmektedir.

Şekil 2. BFO algoritmasının mantıksal blok diyagramı

Kod incelemesine geçelim.

Bir bakteriyi tanımlamanın en iyi yolu, koordinat dizileri ve hareket vektörleri içeren bir yapıdır. Bakterinin mevcut ve önceki sağlık değerleri ve yaşam sayacı. Özünde, yaşam sayacı, yaşam sınırına ulaşıldığında bakterinin yok edileceği ve arama uzayında rastgele bir yerde yeni bir bakterinin yaratılacağı orijinal versiyondan farklı olarak, tek bir yönde sıralı hareket miktarını sınırlamak için gereklidir. Ancak, bu konuya daha önceki makalelerde değindiğimiz gibi, rastgele bir yerde yeni bir temsilci oluşturmanın pratik bir anlamı yoktur ve yalnızca arama yeteneklerini kötüleştirir. Bu durumda, ya en iyi çözümün bulunduğu yerde yeni bir temsilci oluşturmak ya da mevcut konumdan hareket etmeye devam etmek, ancak yön vektörünü değiştirmek daha iyidir. İkinci seçenek daha iyi sonuçlar vermiştir.

Kanonik versiyon sabit bir hareket vektörü kullanır. Çok sayıda yaşamla birlikte bu, bakterilerin arama uzayında düz bir çizgi boyunca hareket etmesine yol açacaktır. Eğer bu çizgi herhangi bir daha iyi ekstremumdan geçmeseydi, o zaman bu doğrusal hareket süreci sonsuza kadar gerçekleşirdi, ancak burada sayaç, bakterinin yaşamı boyunca doğrusal hareketten kaçınmasını sağlayan zorunlu bir takla rolü oynar. Gradyanı olmayan alanlara sahip fonksiyonlarda, eninde sonunda yine de uygunluğunu geliştirmeye başlayabileceği bir yere götürecektir.

//——————————————————————————————————————————————————————————————————————————————
struct S_Bacteria
{
  double c  [];   //coordinates
  double v  [];   //vector
  double f;       //current health
  double fLast;   //previous health
  double lifeCNT; //life counter
};
//——————————————————————————————————————————————————————————————————————————————

BFO algoritma sınıfını C_AO_BFO olarak bildirelim. Sınıf, bakteri kolonisinin bildirimini, arama uzayının sınırlarını, en iyi çözümün değerini ve en iyi çözümün koordinat dizisini içerir. Ayrıca, algoritma parametrelerinin sabit değerlerini de bildirelim.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_BFO
{
  //----------------------------------------------------------------------------
  public: S_Bacteria b     []; //bacteria
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates

  public: void Init (const int    paramsP,         //number of opt. parameters
                     const int    populationSizeP, //population size
                     const double lambdaP,         //lambda
                     const double reproductionP,   //probability of reproduction
                     const int    lifeCounterP);   //life counter

  public: void Swimming   ();
  public: void Evaluation ();

  //----------------------------------------------------------------------------
  private: double NewVector (int paramInd);
  private: S_Bacteria bT []; //bacteria
  private: double v      [];
  private: int    ind    [];
  private: double val    [];
  private: int    populationSize; //population size
  private: int    parameters;     //number of optimized parameters
  private: double lambda;         //lambda
  private: double reproduction;   //probability of reproduction
  private: int    lifeCounter;    //life counter
  private: bool   evaluation;

  private: void   Sorting ();
  private: double SeInDiSp             (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI            (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

public Init () metodu sabit değişkenleri başlatmak, dizi büyüklüklerini dağıtmak ve bayrakları ve en iyi çözümün değerini sıfırlamak içindir.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BFO::Init (const int    paramsP,         //number of opt. parameters
                     const int    populationSizeP, //population size
                     const double lambdaP,         //lambda
                     const double reproductionP,   //probability of reproduction
                     const int    lifeCounterP)    //life counter
{
  fB = -DBL_MAX;
  evaluation = false;

  parameters      = paramsP;
  populationSize  = populationSizeP;
  lambda          = lambdaP;
  reproduction    = reproductionP;
  lifeCounter     = lifeCounterP;

  ArrayResize (rangeMax,  parameters);
  ArrayResize (rangeMin,  parameters);
  ArrayResize (rangeStep, parameters);
  ArrayResize (v,         parameters);

  ArrayResize (ind,       populationSize);
  ArrayResize (val,       populationSize);

  ArrayResize (b,  populationSize);
  ArrayResize (bT, populationSize);

  for (int i = 0; i < populationSize; i++)
  {
    ArrayResize (b [i].c,  parameters);
    ArrayResize (b [i].v,  parameters);
    b [i].f  = -DBL_MAX;
    b [i].fLast = -DBL_MAX;

    ArrayResize (bT [i].c,  parameters);
    ArrayResize (bT [i].v,  parameters);
  }

  ArrayResize (cB, parameters);
}
//——————————————————————————————————————————————————————————————————————————————

Her yinelemede çağrılması gereken ilk public metot - Swimming () veya bakteri yüzmesi, algoritmanın tüm ana mantığını içerir.

void C_AO_BFO::Swimming ()
{}

Metodu ayrıntılı olarak ele alalım. İlk yinelemede, değerlendirme bayrağı 'false' olarak ayarlandığında, bakterileri tüm arama uzayına tekdüze bir dağılımla rastgele dağıtırız. Bu aşamada, mevcut sağlık (uygunluk) ve bir önceki sağlık bilinmemektedir. DBL_MAX değerini ilgili değişkenlere atayalım. Rastgele elde edilen koordinatların sınırların ötesine geçip geçmediğini kontrol ederiz ve optimize edilen parametreleri değiştirme adımını uygularız. Bu yinelemede, NewVector () private metodunu kullanarak her bakteri için ayrı bir yer değiştirme vektörü ayarlamak gerekir (buna aşağıda değineceğim). Tüm bakteriler, değişim için gerekli koşullar sağlanana kadar aynı bireysel vektörle düzgün bir şekilde ileri ve düz bir çizgide yüzer.

//----------------------------------------------------------------------------
if (!evaluation)
{
  fB = -DBL_MAX;

  for (int s = 0; s < populationSize; s++)
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].c [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);

      v [k] = rangeMax [k] - rangeMin [k];

      b [s].v [k] = NewVector (k);

      b [s].f  = -DBL_MAX;
      b [s].fLast = -DBL_MAX;

      b [s].lifeCNT = 0;
    }
  }

  evaluation = true;
}

İkinci ve sonraki yinelemelerde, yaşam sınırına ulaşıldığında bakterilerin yüzmesi, takla atması, çoğalması ve yok edilmesi işlemleri gerçekleştirilir. Mantıktaki ilk işlem üreme işlemidir (parametrelerde belirtilen olasılıkla). Bu, bakteri kolonisinin bir önceki yinelemede sağlık değerinin azalan sırasına göre sıralandığı anlamına gelir.

Algoritmada üreme önemli bir işlevi yerine getirir: bakteri kolonisinin "gen havuzunu" geliştirerek algoritmanın yakınsamasını hızlandırır. İşlem, bakterilerin hayali olarak iki parçaya bölünmesidir ve koloninin yalnızca ilk, daha iyi olan yarısının bölünmesine izin verilir. Koloninin ilk yarısı ikiye bölünür, orijinal ebeveyn sürümü koloninin ikinci yarısına yerleştirilir. Ebeveyn bakteri, klonunun aksine aynı vektörle hareket etmeye devam edecektir. Klon kolonideki yerinde kalır ve ona yeni bir hareket vektörü atanır. Ebeveyn ve klonu, uzayda bölünmenin gerçekleştiği noktadan hareket etmeye devam edecektir.

r = RNDfromCI (0.0, 1.0);

//==========================================================================
if (r < reproduction)
{
  int st = populationSize / 2;
  for (int s = 0; s < st; s++)
  {
    //bacterium original--------------------------------------------------
    for (int k = 0; k < parameters; k++)
    {
      b [st + s].v [k] = b [s].v [k];
      b [st + s].c [k] = b [s].c [k] + b [s].v [k];
      b [st + s].c [k] = SeInDiSp (b [st + s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [st + s].fLast = b [s].f;
      b [st + s].lifeCNT++;
    }

    //bacterium clone-------------------------------------------------------
    for (int k = 0; k < parameters; k++)
    {
      b [s].v [k] = NewVector (k);
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT = 0;
    }
  }
}

Replikasyon olasılığı uygulanmazsa, bakteri ömrünün sınırına ulaşılıp ulaşılmadığına dair bir kontrol yapılır. Algoritmanın kanonik versiyonunda, "eski" bakteri yok edilmeli ve yerine bakteri listesinde, arama uzayının rastgele bir yerinde yeni bir bakteri oluşturulmalıdır. Genel durumda, üreme ve kemotaksis işlemleri çok ekstremumlu uygunluk fonksiyonunun global maksimumunu bulmak için yeterli değildir, çünkü bu prosedürler bakterilerin buldukları yerel minimumları terk etmelerine izin vermez.
Elenme prosedürü bu eksikliğin üstesinden gelmek üzere tasarlanmıştır. Ancak, bu ve diğer algoritmalarla yapılan deneylerin gösterdiği gibi, bu durumda hareket vektörünü değiştirmek daha verimlidir. Yaşam sayacı sıfırlanır. Sayaç, belirli sayıda adımdan (yaşam) sonra hareket yönünü değiştirmek için bir tetikleyicidir. Replikasyon ve elenme sonucunda toplam bakteri sayısı sabit kalır.

if (b [s].lifeCNT >= lifeCounter)
{
  for (int k = 0; k < parameters; k++)
  {
    b [s].v [k] = NewVector (k);
    b [s].c [k] = b [s].c [k] + b [s].v [k];
    b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    b [s].fLast = b [s].f;
    b [s].lifeCNT = 0;
  }
}

Yaşam sınırı tükenmemişse, bakterinin uygunluk fonksiyonunun gradyanını iyileştirmeye doğru ilerleyip ilerlemediğini kontrol edeceğiz. Başka bir deyişle, iki sağlık değerini kontrol ediyoruz - mevcut yinelemedeki ve bir öncekindeki. Sağlık iyileşmişse, hareket vektörü korunur, aksi takdirde bakteri bir takla atmalıdır (hareket vektörünü değiştirmelidir).

Kanonik versiyonda, mevcut ve önceki sağlık kontrolünde katı bir "daha büyük mü?" kontrolü yapılırken, benim versiyonumda "daha büyük veya eşit mi?" uygulanmaktadır, bu da bakterinin incelenen yüzeyin tamamen "yatay" bir bölümünde bile hareket etmeye devam etmesine izin verir, burada uygunluk fonksiyonu gradyanı yoktur, aksi takdirde bakteri tek bir yerde sonsuza kadar takla atar (sağlıkta bir değişiklik yoktur, bu da yüzme yönü olmadığı anlamına gelir). Bu aşamada, alınan yeni koordinatların arama uzayının sınırlarının ötesine çıkıp çıkmadığını da kontrol etmemiz gerekir.

else
{
  if (b [s].f >= b [s].fLast)
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT++;
    }
  }
  else
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].v [k] = NewVector (k);
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT++;
    }
  }
}

NewVector () - hareket vektörünü değiştirmek (takla) için private bir metottur. Metot her koordinat için uygulanır. Buradaki fikir basittir: ilgili v koordinatı için arama sınırları arasındaki fark [-1.0;1.0] aralığından rastgele bir r sayısı ile çarpılır ve ayrıca lambda ölçek faktörü (algoritma parametrelerinden biri) ile çarpılır. Bakteri, yaşam sınırı tükenene kadar (aynı yerde yeni bir bakteri yaratılır, ancak yeni bir hareket vektörü ile), replikasyon sırasında (klonun yeni bir vektörü vardır) ve sağlığın bozulması sırasında (daha uygun yeni bir ortam bulma girişimi yapılır) hareket vektörünü değiştirmeden kullanır.  

//——————————————————————————————————————————————————————————————————————————————
double C_AO_BFO::NewVector (int paramInd)
{
  double r = RNDfromCI (-1.0, 1.0);
  return lambda * v [paramInd] * r;
}
//——————————————————————————————————————————————————————————————————————————————

Her yinelemede çalıştırılması gereken ikinci public Evaluation () metodu, sıralama metodunu çağırır, sıralanan kolonideki en iyi bakterinin sağlığını bulunan en iyi çözümle karşılaştırarak global çözümün güncellemelerini kontrol eder.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BFO::Evaluation ()
{
  Sorting ();

  if (b [0].f > fB)
  {
    fB = b [0].f;
    ArrayCopy (cB, b [0].c, 0, 0, WHOLE_ARRAY);
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Test sonuçları

BFO test ortamı sonuçları:

Kesin sonuçlara varmak için henüz çok erken. Sonuçları öncelikle diğer test katılımcılarıyla ilişkili olarak analiz etmek gerekir.

  Rastrigin test fonksiyonu üzerinde BFO

Forest test fonksiyonu üzerinde BFO

Megacity test fonksiyonu üzerinde BFO

Test görselleştirmesine dikkat edelim. Animasyon, algoritmamızdaki "daha büyük mü?" işaretini "daha büyük veya eşit mi?" ile değiştirme kararının doğruluğunu teyit etti. Bu, bakterilerin test fonksiyonlarının yatay bölümlerinde hareket etmeye devam etmesini sağladı. Bu durum özellikle Forest ve Megacity fonksiyonlarında göze çarpmaktadır. Bakteriler, hiçbir fonksiyon gradyanının olmadığı yerlerde bile ilerlemeye çalışıyor. Algoritma alt kolonilerin oluşumu için herhangi bir mantıksal metot içermese de, bir bakteri kolonisinin görsel olarak ayrı yerel ekstremumlara bölünmüş birkaç ayrı koloniye bölünme yeteneğine de dikkat etmek gerekir; bu, açıkça olumlu bir özellik olarak kabul edilebilir. Genel olarak, herhangi bir yönde keskin bir sıçrama yapma girişiminde bulunmadan bakterilerin arama uzayında tekdüze bir hareketi fark edilmektedir, bu da tekdüze bir artışlı hareket - kemotaksis ile açıklanır.

Şimdi test sonuçlarını analiz etme zamanı. BFO, mevcut katılımcı algoritmalar listesinde 55'in biraz üzerinde bir toplam puanla derecelendirme tablosunun ortasında yer almaktadır. Sonuçlar etkileyici değil ama kötü de değildir. Özellikle, 10 değişkenli Rastrigin fonksiyonu üzerinde iyi sonuçlar elde edilmiştir. 50 ve 1000 değişken durumunda, sonuçlar belirgin şekilde daha kötüdür. Ayrıca, algoritma Forest fonksiyonunda iyi performans göstermemiştir. Ayrık Megacity fonksiyonu üzerindeki nispeten iyi davranış şaşırtıcıdır, çünkü algoritmada bu tür fonksiyonlar üzerinde çalışmak için herhangi bir mekanizma yoktur. Ayrıca, diğer algoritmalara kıyasla iyi bir ölçeklenebilirlik vardır (1000 parametreli Megacity ile test).

BFO, çok çeşitli olanaklara sahip bilimsel bir alandır. Bakterilerde yiyecek aramanın ve genel olarak hayvanlarda yiyecek aramanın optimizasyon performansını artırmak için modellenebilecek bir dizi yönü vardır. BFO algoritması için, kontrol parametrelerinin otomatik adaptasyonu özellikle önemli olabilir, çünkü çok fazla parametre vardır ve ek deneyler için bir neden olan gelişmiş performans sağlayabilir.

BFO, başlatma ve parametrelerin seçimi sırasında koordinatların başlangıç değerlerine karşı düşük hassasiyet, iyi güvenilirlik, mantık basitliği, uygulama kolaylığı, paralelleştirme ve global arama imkanı gibi bir dizi avantaja sahiptir. Böylece, BFO algoritması çok çeşitli optimizasyon problemlerini çözmek için kullanılır. Bununla birlikte, BFO'nun yavaş yakınsama, bazı durumlarda yerel optimumların ötesine geçememe ve sabit bir adım uzunluğu gibi bir dizi dezavantajı da vardır. BFO bir metasezgiseldir, yani algoritma versiyonları geliştirmek için kullanılabilecek kavramsal bir çerçevedir. Burada sunduğum BFO versiyonu birçok olasılıktan sadece bir tanesidir ve konuyla ilgili son sözden ziyade deneyler için bir başlangıç noktası olarak görülmelidir.

Algoritma test sonuçlarının histogramı aşağıda verilmiştir.

Şekil 3. Algoritmaların nihai test sonuçlarının histogramı

Bakteri yiyecek arama optimizasyonu (BFO) algoritmasının özelliklerine ilişkin sonuçlar: