MetaTrader 5 / Örnekler
English Русский 中文 Español Deutsch 日本語 Português 한국어 Français Italiano
preview
Popülasyon optimizasyon algoritmaları: Yapay arı kolonisi (Artificial Bee Colony, ABC)

Popülasyon optimizasyon algoritmaları: Yapay arı kolonisi (Artificial Bee Colony, ABC)

MetaTrader 5 — Örnekler | 12 Temmuz 2023, 15:50
408 0
Andrey Dik
Andrey Dik

İçindekiler

  1. Giriş
  2. Algoritma tanımı
  3. Değiştirilmiş versiyon
  4. Test sonuçları


1. Giriş

Sosyal böcekler, tek tek böcekler tarafından gerçekleştirilemeyen çok sayıda karmaşık görevi yerine getirebilen son derece evrimleşmiş canlılardır. İletişim, karmaşık yuva inşası, çevre kontrolü, koruma ve iş bölümü, bal arılarının sosyal kolonilerde hayatta kalmak için evrimleştirdiği davranışlardan sadece birkaçıdır.
Arılar sürü haline yaşayan canlılardır ve optimum çözümler bulma konusunda olağanüstü yetenekler sergilerler. Doğada, nektar ve polen toplamak için kovanın yakınında çiçek kümeleri ararlar. Bazen arama yarıçapı birkaç kilometreye kadar çıkabilir. Geri dönen arılar bulgularını doğaçlama bir dansla arı ortamına rapor eder.

İlk bakışta bu imkansız gibi görünse de coğrafi konumlarla ilgili bilgileri ritmik hareketlerle birbirlerine iletebilirler. Arılar, diğer arıların dansının yoğunluğuna bağlı olarak, belirli bir noktadaki çiçek sayısı ve tahmini nektar miktarı hakkında sonuçlar çıkarır. Ne kadar çok potansiyel yiyecek olursa, dans o kadar aktif bir şekilde gerçekleşir. Bu olağandışı fenomen, 20. yüzyılın ortalarında böcek araştırmacısı Karl von Frisch tarafından keşfedilmiştir.

Uzun yıllar boyunca arı arama yöntemleri yalnızca biyologlar tarafından araştırılmıştır. Yeni optimizasyon algoritmalarının geliştirilmesinde sürü davranışının uygulanmasına olan ilgi zamanla artmıştır. 2005 yılında da Prof. Dr. Derviş Karaboğa araştırma sonuçlarıyla ilgilenmeye başlamıştır. Bilimsel bir makale yayınlamıştır ve arı dansından ilham alan bir sürü zekası modelini açıklayan ilk kişi olmuştur. Bu modele yapay arı kolonisi adı verilmiştir.


2. Algoritma tanımı

Arıları kovanda yönetme ilkeleri ve alan keşif kuralları bakımından farklılık gösteren birçok yapay arı kolonisi uygulaması vardır. Makalede, algoritmanın klasik versiyonuna yorumumuzu katarak değiştirilmiş bir versiyonunu uygulayacağız.

Algoritma fikri, arıların mümkün olduğu kadar çok nektar elde edebilecekleri yerleri ararkenki davranışlarına dayanmaktadır. İlk olarak, tüm arılar kovandan rastgele bir yöne doğru uçar. Gözcü olarak görev yaparak nektar bulunan alanları bulmaya çalışırlar. Sonrasında kovana geri dönerler ve özel bir şekilde birbirlerine nerede ve ne kadar nektar bulduklarını söylerler.

Devamında, işçi arılar bulunan alanlara gönderilir. Bir alanda ne kadar çok nektar mevcutsa, o yöne doğru o kadar çok arı uçar. Gözcüler, başka alanlar aramak için tekrar uçarlar ve halihazırda bulunmuş alanların yakın çevresini keşfederler. Böylece, tüm arılar iki türe ayrılır: nektar toplayan işçi arılar ve yeni alanlar keşfeden gözcü arılar. Nektar toplama alanları, içlerindeki nektar miktarına karşılık gelen değerlere sahiptir. Daha düşük mertebeli alanlar, alanların merkezlerinden geçen bir çizgi boyunca daha yüksek mertebeli alanlara doğru yer değiştirir.

Şematik olarak, işçi arıların alanlara göre dağılımı Şekil 1'deki gibi görselleştirilebilir.

ABCarea

Şekil 1. Alan mertebelerine bağlı olarak alanlardaki arı sayısı

1. alan daha yüksek bir mertebeye sahiptir (en fazla nektarı içerir), bu nedenle daha fazla arı oraya uçma eğilimindedir. Arı sayısına göre, 4. alanın en düşük mertebeye (değere) sahip olduğunu görsel olarak belirleyebiliriz. Her bir alanın değeri hakkındaki bilgi arılar tarafından özel bir dans şeklinde rapor edilir. Her kovanın, alandaki nektarın yönünün ve miktarının programlandığı kendi dansı vardır.

Global ekstremumun konumunun en fazla nektarın bulunduğu alan olduğunu varsayalım. Böyle sadece bir alan vardır. Diğer yerler ise daha az nektar miktarına sahiptir. Arılar, her koordinatın optimize edilmesi gereken fonksiyonun bir parametresini temsil ettiği çok boyutlu uzayda yaşarlar. Bulunan nektar miktarı, eğer global maksimumu arıyorsak, amaç fonksiyonunun değeridir. Eğer global minimumu arıyorsak, amaç fonksiyonunu -1 ile çarpmamız yeterli olacaktır.

Nektar toplama alanları belirli bir değere sahip olduğundan, yalnızca en yüksek mertebeye sahip alan en yüksek nektar konsantrasyonuna sahip noktaya hareket etme (merkezinin bu noktaya yerleşmesi) hakkına sahiptir. Daha düşük mertebeli alanlar en yüksek konsantrasyonun merkezine doğru kaydırılacaktır, ancak daha yüksek mertebeli bir alanla kesişip kesişmediği kontrol edilecektir. Bu şekilde, arıların dar ve küçük alanlarda yoğunlaşmasına izin verilmez ve arama uzayı işçi arılar tarafından mümkün olduğunca verimli bir şekilde kullanılır, böylece besin kaynağının tükenmesi önlenir. Optimizasyon açısından bu, yerel ekstremumlara takılmayı ortadan kaldırır veya en aza indirir. Alanlar mertebe zinciri boyunca birbirlerine göre optimumlarına doğru kaydırıldıktan sonra, çevreleri gözcü arılar tarafından ek olarak araştırılacaktır.

Birçok arıcı, gözcü arıların arama uzayının rastgele bölgelerine gönderilmesini tavsiye eder, ancak deneyimlerim bu tür "gözcülüğün" pratik değerinin sıfıra yakın olduğunu ve yalnızca bir ve iki boyut için yararlı olduğunu göstermektedir. Başka bir deyişle, çok boyutlu uzaylardan bahsediyorsak, serbestlik derecesi geometrik olarak artar ve dolayısıyla tesadüfen daha değerli bir nektar kaynağına rastlamak inanılmaz derecede zor hale gelir. Kovanın kaynakları sadece boşa harcanacaktır. Gözcüleri halihazırda bilinen arama alanlarının çevrelerine göndermek çok daha yararlıdır. Böylece koordinatların dağınık olmaması ve özellikle olası nektar kaynaklarının bulunduğu bölgelerde yoğunlaşması sağlanacaktır.

Alanlar kesişiyorsa, alanlar yalnızca sınırlara temas edecek şekilde merkezi kaydırmak gerekir. Bu durum Şekil 2'de gösterilmektedir.

ABCcrossArea

Şekil 2. Daha düşük mertebeye sahip alan kaydırılmalıdır

Alanların mertebeleri katı bir şekilde belirlenmez, dinamik olarak düzenlenir. Gözcü arıların bulguları uçtukları alanlara atanacaktır. Daha değerli bir besin kaynağı keşfedilmesi durumunda, alanın merkezi oraya kaydırılacaktır. Hatta bu alan yeni en iyi nektar toplama merkezi haline de gelebilir. Devamında, kalan alanlar da ona göre kaydırılacaktır. Başka bir deyişle, mertebe zinciri boyunca ona göre kaydırılacaklardır.

Arıların dansı olarak ifade edilen bilgi aktarma yöntemi, bir bütün şekilde kovanın stratejisinin temel bir unsurudur. Kovanın mevcut kaynaklarının arama alanlarına en rasyonel şekilde dağıtılması gerekir, bu nedenle gönderilen arı sayısı alanın değeriyle orantılı olmalıdır. Bu, eşit değerdeki alanlara eşit sayıda arı gönderileceği anlamına gelir.

Algoritmanın kendisine geçelim. Uygulama adımları aşağıda listelenmiştir:

  1. Tüm arılar gözcü olarak arama uzayında rastgele uçarlar.
  2. Her bir arıdan elde edilen nektar miktarı ölçülür.
  3. Arılar sıralanır.
  4. Arılardan elde edilen nektar miktarı bilgisine göre alanlar atanır.
  5. İşçi arılar bu alanlara gönderilir. Alanda ne kadar çok nektar varsa, ilgili alana o kadar çok arı gönderilecektir.
  6. Rastgele seçilen bir alanın çevresine gözcü arılar gönderilir.
  7. Her bir arıdan elde edilen nektar miktarı ölçülür.
  8. Alanlar nektar miktarına göre sıralanır.
  9. Durma kriteri karşılanana kadar 4. adımdan itibaren tekrarlanır.

Görsel algıyı kolaylaştırmak adına algoritmanın blok diyagramını çizelim (Şekil 3).


ABCsceme

Şekil 3. Algoritmanın blok diyagramı

Arı kolonisi algoritmasının kodunu daha ayrıntılı olarak tanımlayalım.

Arı, algoritmanın temel ve basit mantıksal birimidir. Bir yapı ile tanımlanabilir. Hatırlayacağınız gibi, arının konumu nektar miktarına göre belirlenen nektar toplama alanın koordinatlarıyla ayarlanır. Kovandaki arılar daha sonra bir dizi ile temsil edilecektir. Her birine indeksiyle erişilebilir.

//——————————————————————————————————————————————————————————————————————————————
struct S_Bee
{
  double c []; //coordinates
  int    aInd; //area index
  double n;    //nectar
};
//——————————————————————————————————————————————————————————————————————————————

İkinci, daha büyük mantıksal birim ise nektar toplama alanıdır. Nektarın en yoğun olduğu merkez ve alanın değerini belirleyen nektar miktarı ile tanımlanır. En yüksek mertebeye sahip alanda (listedeki ilk), merkezin koordinatları ve en yüksek nektar konsantrasyonu çakışır. Listedeki ikinci ve daha alt mertebelerdeki alanlar, kaydırıldıkları için eşleşmeyebilir. Alanın başlatılması, nektar miktarı göstergesinin sıfırlanmasından ve koordinatların optimize edilen fonksiyonun ilgili parametre sayısına dağıtılmasından oluşur. 

//——————————————————————————————————————————————————————————————————————————————
struct S_Area
{
  void Init (int coordinatesNumber)
  {
    n = -DBL_MAX;

    ArrayResize (cC, coordinatesNumber);
    ArrayResize (cB, coordinatesNumber);
  }

  double cC   []; //center coordinates
  double cB   []; //best coordinates
  double n;       //nectarAmount
};
//——————————————————————————————————————————————————————————————————————————————

Arıların dansını, dizisi alan sayısına karşılık gelecek bir yapı olarak tanımlayalım.

//——————————————————————————————————————————————————————————————————————————————
struct S_BeeDance
{
  double start;
  double end;
};
//——————————————————————————————————————————————————————————————————————————————

Kovanı; arama alanlarını, arıları, en iyi koordinatları ve tüm yinelemelerde bulunan en yüksek nektar miktarını belirleyen bir sınıf olarak tanımlayacağız. Ayrıca, arıları ve alanları sıralamak ve arıları ve alanları birbirlerine göre hareket ettirmek için gerekli tüm metotlar burada tanımlanacaktır. Burada, önceki algoritmalardan tanıdığımız fonksiyon bildirimlerini görebiliriz: eşit olarak dağıtılan rasgele sayılar üretme, bir aralığa ölçekleme ve bir aralıktan bir adımla bir sayı seçme.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ABC //Bees Hive
{
  //============================================================================
  public: S_Area areas     []; //nectar collection areas
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: S_Bee  bees      []; //all the bees of the hive
  public: double cB        []; //best coordinates
  public: double nB;           //nectar of the best coordinates

  public: void InitHive (const int    coordinatesP,      //number of opt. parameters
                         const int    beesNumberP,       //bees number
                         const int    workerBeesNumberP, //worker bees number
                         const int    areasNumberP,      //areas number
                         const double collectionRadiusP, //collection radius
                         const double scoutAreaRadiusP); //scout area radius

  public: void TasksForBees ();
  public: void CollectingNectar ();

  //============================================================================
  private: void   BeeFlight      (double &cC [] , S_Bee &bee);
  private: void   ScoutBeeFlight (double &cC [] , S_Bee &bee);
  private: void   MarkUpAreas    ();
  private: void   SortingBees    ();
  private: void   SortingAreas   ();
  private: double SeInDiSp       (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI      (double Min, double Max);
  private: double Scale          (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool Revers);

  private: int    coordinates;      //coordinates number
  private: int    beesNumber;       //the number of all bees
  private: int    workerBeesNumber; //worker bees number
  private: int    areasNumber;      //areas number
  private: S_Bee  beesT       [];   //temporary, for sorting
  private: S_Area areasT      [];   //temporary, for sorting
  private: int    indA        [];   //array for indexes when sorting
  private: double valA        [];   //array for nectar values when sorting
  private: int    indB        [];   //array for indexes when sorting
  private: double valB        [];   //array for nectar values when sorting
  private: double areasRadius [];   //radius for each coordinate
  private: double scoutRadius [];   //scout radius for each coordinate

  private: double collectionRadius;   //collection radius
  private: double scoutAreaRadius;    //scout area radius
  private: double hypersphereRadius;  //hypersphere radius
  private: double distHyperspCenters; //distance hyperspheres centers
  private: double scoutHyperspRadius; //scout hypersphere radius
  private: bool   scouting;           //scouting flag

  private: S_BeeDance beeDance [];    //bee dance
};
//——————————————————————————————————————————————————————————————————————————————

Her yeni optimizasyon mutlaka sınıf başlatma ile başlamalıdır. Nektar miktarının değeri tüm kovan ve tek tek arıların yanı sıra alanlar için de sıfırlanır.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::InitHive (const int    coordinatesP,      //number of opt. parameters
                         const int    beesNumberP,       //bees number
                         const int    workerBeesNumberP, //worker bees number
                         const int    areasNumberP,      //areas number
                         const double collectionRadiusP, //collection radius
                         const double scoutAreaRadiusP)  //scout area radius
{
  MathSrand (GetTickCount ());
  scouting = false;
  nB       = -DBL_MAX;

  coordinates      = coordinatesP;
  beesNumber       = beesNumberP;
  workerBeesNumber = workerBeesNumberP;
  areasNumber      = areasNumberP < 3 ? 3 : areasNumberP;

  collectionRadius = collectionRadiusP; //collection radius
  scoutAreaRadius  = scoutAreaRadiusP;  //scout area radius

  ArrayResize (areas,  areasNumber);
  ArrayResize (areasT, areasNumber);
  for (int i = 0; i < areasNumber; i++)
  {
    areas  [i].Init (coordinates);
    areasT [i].Init (coordinates);
  }

  ArrayResize (beeDance, areasNumber);

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);
  ArrayResize (cB,        coordinates);

  ArrayResize (indA, areasNumber);
  ArrayResize (valA, areasNumber);

  ArrayResize (areasRadius, coordinates);
  ArrayResize (scoutRadius, coordinates);
  for (int i = 0; i < coordinates; i++)
  {
    areasRadius [i] = (rangeMax [i] - rangeMin [i]) * collectionRadius;
    scoutRadius [i] = (rangeMax [i] - rangeMin [i]) * scoutAreaRadius;
  }

  double sqr = 0.0;
  for (int i = 0; i < coordinates; i++) sqr += areasRadius [i] * areasRadius [i];
  hypersphereRadius  = MathSqrt (sqr) * collectionRadius;

  distHyperspCenters = hypersphereRadius * 2.0;

  sqr = 0.0;
  for (int i = 0; i < coordinates; i++) sqr += scoutRadius [i] * scoutRadius [i];
  scoutHyperspRadius = MathSqrt (sqr) * scoutAreaRadius;

  ArrayResize (indB, beesNumber);
  ArrayResize (valB, beesNumber);

  ArrayResize (bees,  beesNumber);
  ArrayResize (beesT, beesNumber);
  for (int i = 0; i < beesNumber; i++)
  {
    ArrayResize (bees  [i].c, coordinates);
    ArrayResize (beesT [i].c, coordinates);
    bees  [i].n = -DBL_MAX;
    beesT [i].n = -DBL_MAX;
  }
}
//——————————————————————————————————————————————————————————————————————————————

En basit ve aynı zamanda açık sınıf metodu, görevlerin arılara dağıtılmasıdır. Burada her şey basittir. Alanlar henüz keşfedilmemişse, tüm kovan için nektar değerini sıfırlar ve alanları işaretlemeye başlarız. Uygunluk fonksiyonunun değeri elde edilene kadar metodu her yinelemede çağırırız.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::TasksForBees ()
{
  if (!scouting)
  {
    nB = -DBL_MAX;
  }
  MarkUpAreas ();
}
//——————————————————————————————————————————————————————————————————————————————

Her yinelemede çağrılan ikinci public metot. Uygunluk fonksiyonunun değeri elde edildikten sonra başlatma gerçekleştirilmelidir. Bu durumda, keşif henüz yapılmamışsa, arıları nektar değerine göre sıralarız ve listedeki ilk arıların koordinatlarını ve nektar miktarını ilgili alanlara kopyalarız. Keşif yapılmışsa, sonuçların iyileşmesi koşuluyla nektarın toplandığı alandaki koordinatları ve nektar miktarını kopyalarız. Ayrıca, tüm kovan için en iyi sonuçları güncelleriz. 

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::CollectingNectar ()
{
  if (!scouting)
  {
    SortingBees ();

    for (int a = 0; a <areasNumber; a++)
    {
      ArrayCopy (areas [a].cB, bees [a].c, 0, 0, WHOLE_ARRAY);
      areas [a].n = bees [a].n;
    }

    scouting = true;
  }
  else
  {
    //transfer the nectar to the hive---------------------------------------------
    for (int b = 0; b < beesNumber; b++)
    {
      if (bees [b].n > areas [bees [b].aInd].n)
      {
        ArrayCopy (areas [bees [b].aInd].cB, bees [b].c, 0, 0, WHOLE_ARRAY);
        areas [bees [b].aInd].n = bees [b].n;
      }

      if (bees [b].n > nB)
      {
        ArrayCopy (cB, bees [b].c, 0, 0, WHOLE_ARRAY);
        nB = bees [b].n;
      }
    }

    SortingAreas ();
  }
}
//——————————————————————————————————————————————————————————————————————————————

MarkUpAreas () metodu ayrıntılı olarak ele alınmaya değerdir. Kodu parçalara ayıralım.

Alanlar keşfedilmeden ve nektar toplamak için çiçek bulma konusunda bilgi olmadan önce, tüm arıları ön keşif yapmaya göndereceğiz. Bu aşamada tüm arılar gözcü rolündedir. Nektar hakkında hiçbir bilgi olmadığından, koordinat aralığına eşit olarak dağıtılan rastgele sayılar üreterek rastgele yönlere gözcüler gönderiyoruz.

//if the areas is not scouting - send all the bees to scouting----------------
if (!scouting)
{
  for (int b = 0; b < beesNumber; b++)
  {
    for (int c = 0; c < coordinates; c++)
    {
      bees [b].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      bees [b].c [c] = SeInDiSp  (bees [b].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Alanlar keşfedildikten sonra, maksimum nektar konsantrasyonunun koordinatlarını alanın merkezine kopyalamak gerekir. Başka bir deyişle, alanı daha iyi bir yere taşımak gerekir. Bu işlemi gerçekleştirdikten sonra, alanın daha yüksek mertebeli bir alanla kesişmediğinden emin olmalıyız. Alanların kesişip kesişmediğini, merkezleri arasındaki mesafeyi ölçerek kontrol edebiliriz. Merkezler arasındaki mesafe iki yarıçaptan (algoritma parametrelerinden biri) daha azsa alanlar kesişmektedir. Kesişme tespit edilirse, elde edilen en iyi sonucun koordinatları (maksimum nektar konsantrasyonunun bulunduğu koordinatlar) aynı yerde kalırken, alan iki yarıçaplık mesafedeki başka bir noktaya taşınır. Böylece alanlar sürekli hareket halindedir. En iyi alanlar diğerlerini değişime zorlar. Diğer alanlar yer değiştirdikçe daha zengin bir besin kaynağına ulaşabilir ve bir sonraki metotta gerçekleşen sıralama yapıldıktan sonra en iyisi haline gelebilir.

for (int s = 0; s < areasNumber; s++)
{
  //move the center of the area to the best point in with more nectar-------
  ArrayCopy (areas [s].cC, areas [s].cB, 0, 0, WHOLE_ARRAY);

  //ordinary area-----------------------------------------------------------
  if (s != 0)
  {
    //check if there is no intersection of a region with a region of higher rank
    //measure the distance from the centers of the regions
    double centersDistance = 0.0;

    for (int c = 0; c < coordinates; c++) centersDistance += pow (areas [s].cC [c] - areas [s - 1].cC [c], 2.0);
    centersDistance = MathSqrt (centersDistance);

    //the areas intersect, then need to move the current area
    if (centersDistance < distHyperspCenters)
    {
      double incrementFactor = (distHyperspCenters - centersDistance) / centersDistance;
      double coordDistance   = 0.0;

      for (int c = 0; c < coordinates; c++)
      {
        coordDistance = areas [s].cC [c] - areas [s - 1].cC [c];
        areas [s].cC [c] = areas [s].cC [c] + (coordDistance * incrementFactor);

        areas [s].cC [c] = SeInDiSp (areas [s].cC [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
}

Burası arıların dansının gerçekleştiği yerdir. Alanlardaki nektarın yönü ve miktarı hakkındaki bilgileri kullanarak ve bir rastgele bileşen uygulayarak, bir rastgele sayının dağılım alanını, bir arının bir sonraki yinelemede bir alanı seçme olasılığı bu alandaki nektar miktarıyla orantılı olacak şekilde işaretliyoruz. Basit bir ifadeyle, sayı doğrusu üzerinde, uzunlukları ‘her bir alanın nektar değeri’ ile ‘en kötü alanın nektar değeri’ arasındaki farka karşılık gelen segmentleri çiziyoruz.

//send bees to the marked areas-----------------------------------------------
double r = 0.0;

beeDance [0].start = bees [0].n;
beeDance [0].end   = beeDance [0].start + (bees [0].n - bees [areasNumber - 1].n);

for (int a = 1; a < areasNumber; a++)
{
  if (a != areasNumber - 1)
  {
    beeDance [a].start = beeDance [a - 1].end;
    beeDance [a].end   = beeDance [a    ].start + (bees [a].n - bees [areasNumber - 1].n);
  }
  else
  {
    beeDance [a].start = beeDance [a - 1].end;
    beeDance [a].end   = beeDance [a    ].start + (bees [a - 1].n - bees [a].n) * 0.1;
  }
}

Metot kodunun bu bölümünde, işçi arıların dansı tarafından iletilen olasılıkla rastgele bir alan seçimi gerçekleştirilir. Bunu yapmak için, sayı doğrusu üzerinde dansla işaretleme yapılarak oluşturulan aralıkta rastgele bir sayı üretiyoruz. Gözcüler için dans önemli değildir, çünkü herhangi bir alanın yakınında eşit derecede olasılıkla uçarlar, böylece arı stratejisinin arama yeteneklerini genişletirler. Doğada olduğu gibi, her kovan katılımcısı bir rol oynarken belirli bir değere sahiptir.

for (int b = 0; b < beesNumber; b++)
{
  if (b < workerBeesNumber)
  {
    r = RNDfromCI(beeDance [0].start, beeDance [areasNumber - 1].end);
        
    for (int a = 0; a < areasNumber; a++)
    {
      if (beeDance [a].start <= r && r < beeDance [a].end)
      {
        bees [b].aInd = a;
        break;
      }
    }

    BeeFlight (areas [bees [b].aInd].cC, bees [b]);
  }
  else
  {
    //choose the area to send the bees there
    r = RNDfromCI (0.0, areasNumber - 1);

    bees [b].aInd = (int)r; //area index

    ScoutBeeFlight (areas [bees [b].aInd].cC, bees [b]);
  }
}

Bu private metot, bir arının uçuşunu uygular. İlk bakışta anlaşılmaz ve karmaşık görünse de burada her şey basittir. Arı, merkeze yaklaştıkça olasılıkta kübik kayma meydana gelen bir alana uçar. Böylece, olasılık alan merkezinden sınırlarına doğru azalır. Buranın alanın merkezi olduğunu ve daha önce bulunan en iyi konum olmadığına dikkat edin. Bu basit eylemde bile arının stratejisi izlenebilir ve sürekli yeni besin kaynakları aranması sağlanabilir.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::BeeFlight (double &cC [] , S_Bee &bee)
{
  double r = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    r  = RNDfromCI (0.0, 1.0);
    r  = r * r * r;
    r = Scale (r, 0.0, 1.0, 0.0, areasRadius [c], false);
    r *= RNDfromCI (0.0, 1.0) > 0.5 ? 1.0 : -1.0;

    bee.c [c] = SeInDiSp  (cC [c] + r, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Önceki metottan farklı olarak, burada gözcü arının uçuşu tanımlanmaktadır. Arı, algoritma ayarlarında belirtilen yarıçap içerisindeki alanın dışarısına uçar. Ayar aynı olmasına rağmen, sınıf başlatıldığında yarıçaplar önceden hesaplanır, çünkü koordinat aralıkları farklı olabilir, bu nedenle yarıçaplar uygun olmalıdır. Bir gözcü arısını uçuşa geçirmek için, ‘alanın yarıçapı’ ile ‘alanın yarıçapı ve keşif yarıçapının toplamı’ aralığında rastgele bir sayı üretmemiz ve ardından elde edilen değeri alanın merkezine eklememiz gerekir. Bu kadar basit bir şekilde, gözcü arısı tesadüfen alanın yakınında olacak ve koordinatlar arama uzayında dağılmayacaktır.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ABC::ScoutBeeFlight (double &cC [] , S_Bee &bee)
{
  double r = 0.0;

  for (int c = 0; c < coordinates; c++)
  {
    r  = RNDfromCI (areasRadius [c], areasRadius [c] + scoutRadius [c]);
    r *= RNDfromCI (0.0, 1.0) > 0.5 ? 1.0 : -1.0;

    bee.c [c] = SeInDiSp  (cC [c] + r, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Algoritmada iki özel metot vardır - arı sıralaması ve alan sıralaması. Onları açıklamanın bir anlamı yoktur, sadece basit bir kabarcık sıralamasıdır. Bu metodu neredeyse tüm optimizasyon algoritmalarında (sıralamanın gerekli olduğu yerlerde) kullanıyorum, çünkü bu metot basittir ve belirli görevler için kolayca modifiye edilebilir ve ayrıca tüm sıralama metotları arasında en iyi hızlardan birini sağlamaktadır.

//——————————————————————————————————————————————————————————————————————————————
//Sorting of bees
void C_AO_ABC::SortingBees ()
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Sorting of areas
void C_AO_ABC::SortingAreas ()
//——————————————————————————————————————————————————————————————————————————————

Ele alınan tüm kodları birleştirme ve derleme zamanı. Test ortamını çalıştırdıktan sonra, arı algoritmasının davranışını yansıtan aşağıdaki animasyonları görüyoruz. Arılar ayrı alanlarda net bir şekilde gözlemlenmektedir. Alanların nasıl yer değiştirerek birbirinin yerini aldığını görebiliyoruz. Hassasiyet ve tuhaf "sürüler"in sayısı, algoritma ayarlarına bağlıdır.

Skin

Skin test fonksiyonu üzerinde ABC.

Forest

Forest test fonksiyonu üzerinde ABC.

Megacity

Megacity test fonksiyonu üzerinde ABC.

İşte test fonksiyonları üzerindeki algoritma sonuçları:

2022.11.21 13:14:06.669    Test_AO_ABC1 (EURUSD,M1)    =============================
2022.11.21 13:14:28.483    Test_AO_ABC1 (EURUSD,M1)    1 Skin's; Func runs 1000 result: 14.018634225602678; Func runs 10000 result: 14.06060189007221
2022.11.21 13:14:28.483    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.99772; Score2: 1.00000
2022.11.21 13:14:50.310    Test_AO_ABC1 (EURUSD,M1)    20 Skin's; Func runs 1000 result: 7.459929501115262; Func runs 10000 result: 8.320771456653533
2022.11.21 13:14:50.310    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.64085; Score2: 0.68769
2022.11.21 13:15:30.049    Test_AO_ABC1 (EURUSD,M1)    500 Skin's; Func runs 1000 result: 4.69267387794685; Func runs 10000 result: 4.838631770950824
2022.11.21 13:15:30.049    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.49029; Score2: 0.49823
2022.11.21 13:15:30.049    Test_AO_ABC1 (EURUSD,M1)    =============================
2022.11.21 13:15:51.880    Test_AO_ABC1 (EURUSD,M1)    1 Forest's; Func runs 1000 result: 15.063567301715784; Func runs 10000 result: 15.912087696850861
2022.11.21 13:15:51.880    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.94435; Score2: 0.99755
2022.11.21 13:16:13.721    Test_AO_ABC1 (EURUSD,M1)    20 Forest's; Func runs 1000 result: 3.0207584941876133; Func runs 10000 result: 4.1918977577943295
2022.11.21 13:16:13.721    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.18937; Score2: 0.26279
2022.11.21 13:17:01.467    Test_AO_ABC1 (EURUSD,M1)    500 Forest's; Func runs 1000 result: 1.2004991531402736; Func runs 10000 result: 1.288357831462411
2022.11.21 13:17:01.467    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.07526; Score2: 0.08077
2022.11.21 13:17:01.467    Test_AO_ABC1 (EURUSD,M1)    =============================
2022.11.21 13:17:23.227    Test_AO_ABC1 (EURUSD,M1)    1 Megacity's; Func runs 1000 result: 10.4; Func runs 10000 result: 15.0
2022.11.21 13:17:23.227    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.69333; Score2: 1.00000
2022.11.21 13:17:44.936    Test_AO_ABC1 (EURUSD,M1)    20 Megacity's; Func runs 1000 result: 1.5499999999999998; Func runs 10000 result: 2.31
2022.11.21 13:17:44.936    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.10333; Score2: 0.15400
2022.11.21 13:18:29.588    Test_AO_ABC1 (EURUSD,M1)    500 Megacity's; Func runs 1000 result: 0.6180000000000001; Func runs 10000 result: 0.6568
2022.11.21 13:18:29.588    Test_AO_ABC1 (EURUSD,M1)    Score1: 0.04120; Score2: 0.04379
2022.11.21 13:18:29.588    Test_AO_ABC1 (EURUSD,M1)    =============================
2022.11.21 13:18:29.588    Test_AO_ABC1 (EURUSD,M1)    All score for C_AO_ABC: 0.49447371765340953

Algoritma, iki değişkenli iki test fonksiyonu için tamamen yakınsamıştır ve bu da mükemmel bir yakınsama göstergesidir. Kalan sonuçları değerlendirmek için erken olacaktır. Sonuçları bir tabloya koymak ve diğer optimizasyon algoritmalarıyla karşılaştırarak sonuçlar çıkarmak daha iyidir.


3. Değiştirilmiş versiyon

Herhangi bir optimizasyon algoritması geliştirirken ve tasarlarken, her zaman şu soru ortaya çıkar: "Algoritma amaçlandığı gibi çalışıyor mu yoksa kodun bir yerinde bir hata mı var?" Stokastik arama süreci doğası gereği rastgeledir, bu nedenle optimizasyon sonuçlarının algoritma tarafından elde edilip edilmediği veya bir yerlerde bir hata olup sonucun gerçekten rastgele olup olmadığı net değildir. Arı kolonisi algoritmasını geliştirirken de benzer bir olguyla karşılaştım. Test kümesindeki beş testten ilki sırasında, algoritma açıkça hiç yakınsamaya çalışmadan aramaya başladığı noktalarda takılıp kaldı. İlginç bir şekilde, bu hata pek mantıklı olmayan bir şekilde çözüldü. Tek yapmam gereken, ilk yinelemede kovan sınıfını ikinci kez başlatmaktı (sınıf, yinelemelerin başlangıcından önce zaten başlatılmış olmasına rağmen) (Test_AO_ABC.mq5 dosyasında 142. dizge). Bir kişi bu gizemi çözmeyi başarırsa, çözümü makalenin yorumlarında duymaktan memnuniyet duyarım.

Kısmen yukarıdakiler, kısmen de ilk testlerin pek de tatmin edici olmayan sonuçları nedeniyle (daha sonra algoritma ayarlarıyla denemeler yapmam gerektiği anlaşıldı), arı arama stratejisini değiştirme fikrini ortaya çıkardım. Orijinal versiyonda, arılar alan değeriyle orantılı olarak uçarlar. Yeni algoritmada ise her alanda sabit sayıda arı bulunmalıdır. Başka bir deyişle, alanın mertebesi ne olursa olsun, her biri her zaman aynı sayıda arıya sahiptir. Dolayısıyla alan mantıksal olarak “arı sürüsü” kavramına dönüşmüştür.

Şimdi, alan yapısı yerine aşağıdaki yapı olacaktır:

//——————————————————————————————————————————————————————————————————————————————
struct S_BeesSwarm
{
  void Init (int coordinatesNumber, int beesNumber)
  {
    ArrayResize (bees, beesNumber);

    for (int i = 0; i < beesNumber; i++)
    {
      ArrayResize (bees [i].c, coordinatesNumber);
      bees [i].n = -DBL_MAX;
    }

    n = -DBL_MAX;

    ArrayResize     (cC, coordinatesNumber);
    ArrayInitialize (cC, -DBL_MAX);
  }

  S_Bee  bees []; //bees
  double cC   []; //center coordinates
  double cB   []; //best coordinates
  double n;       //nectarAmount
};
//——————————————————————————————————————————————————————————————————————————————

Bu yapının da bir başlatma fonksiyonu vardır, ancak ek olarak bees [] dizisine sahiptir.

Genel olarak, kodun geri kalanı klasik versiyona çok benzerdir, dolayısıyla ona çok fazla odaklanmamalısınız. Kod aşağıdaki arşive eklenmiştir. Algoritmaların mantığındaki farklılıklar özellikle dikkat etmeye değerdir. Adım adım form halinde şu şekilde görünmektedir:

  1. İlk sürü için bir merkez oluşturulur ve arılar merkeze yerleştirilir.
  2. Sonraki sürüler için bir merkez oluşturulur, merkezden önceki sürülere olan mesafenin r*2'ye (iki yarıçap) eşit veya daha büyük olduğu kontrol edilir ve arılar merkeze yerleştirilir.
  3. Gözcü arıları, arıların her biri diğer sürülerden r'ye (yarıçap) eşit veya daha büyük bir mesafe kadar uzakta olacak şekilde gönderilir.
  4. Tüm arılar için uygunluk fonksiyonunun değeri alınır.
  5. Sürüler sıralanır.
  6. Arılar her bir sürünün merkezine yerleştirilir.
  7. Durma kriteri karşılanana kadar 4. adımdan itibaren tekrarlanır.

Fark etmiş olabileceğiniz gibi, arama stratejisinde temel bir farklılık vardır. Klasik versiyonda her alan farklı sayıda arıya sahip olabilirken, burada sürüler her zaman aynı büyüklüktedir. Bu, besin kaynağı kurusa bile alanların keşfedilmeye devam etmesine olanak tanımak ve böylece hiperuzayda yüzeyin daha kapsamlı bir şekilde keşfedilmesini sağlamak için yapılır. Testler bu yaklaşımın geçerliliğini doğrulamaktadır. Sonuçlar iyiye gitmektedir. Gözcü arılar, klasik versiyonda olduğu gibi alanların çevresinde uçmazlar, ancak alanların kurallarına uyarak boş alanlara girerler. Şunu belirtmek gerekir ki, klasik versiyonda gözcüler tanımlandığı gibi davranmazlar, çünkü daha önce keşfedilmiş alanlara girebileceklerini umursamadan tamamen rastgele bir yöne dağılırlar, böylece en temel keşiflerini kaybederler. Dizideki son sürü gözcü sürüsüdür. "Başkasının alanına girmeme" kuralı bu sürü için de geçerlidir, ancak bir bütün olarak sürü için değil, bireysel olarak gözcü arılar için geçerlidir.

Aşağıda değiştirilmiş versiyonun sonuçları yer almaktadır:

2022.11.21 21:53:19.695    Test_AO_ABCm (EURUSD,M1)    =============================
2022.11.21 21:53:25.104    Test_AO_ABCm (EURUSD,M1)    1 Skin's; Func runs 1000 result: 14.009060385607679; Func runs 10000 result: 14.060603974847265
2022.11.21 21:53:25.104    Test_AO_ABCm (EURUSD,M1)    Score1: 0.99720; Score2: 1.00000
2022.11.21 21:53:30.452    Test_AO_ABCm (EURUSD,M1)    20 Skin's; Func runs 1000 result: 7.826824877236677; Func runs 10000 result: 8.735832346695558
2022.11.21 21:53:30.452    Test_AO_ABCm (EURUSD,M1)    Score1: 0.66082; Score2: 0.71028
2022.11.21 21:53:40.060    Test_AO_ABCm (EURUSD,M1)    500 Skin's; Func runs 1000 result: 4.645933304640949; Func runs 10000 result: 4.844246724239038
2022.11.21 21:53:40.060    Test_AO_ABCm (EURUSD,M1)    Score1: 0.48774; Score2: 0.49853
2022.11.21 21:53:40.060    Test_AO_ABCm (EURUSD,M1)    =============================
2022.11.21 21:53:45.363    Test_AO_ABCm (EURUSD,M1)    1 Forest's; Func runs 1000 result: 15.44507700105064; Func runs 10000 result: 15.662273922787355
2022.11.21 21:53:45.363    Test_AO_ABCm (EURUSD,M1)    Score1: 0.96827; Score2: 0.98188
2022.11.21 21:53:50.697    Test_AO_ABCm (EURUSD,M1)    20 Forest's; Func runs 1000 result: 3.6397442648278924; Func runs 10000 result: 4.759146560755886
2022.11.21 21:53:50.697    Test_AO_ABCm (EURUSD,M1)    Score1: 0.22818; Score2: 0.29836
2022.11.21 21:54:01.111    Test_AO_ABCm (EURUSD,M1)    500 Forest's; Func runs 1000 result: 1.2349621811342104; Func runs 10000 result: 1.4191098624570897
2022.11.21 21:54:01.111    Test_AO_ABCm (EURUSD,M1)    Score1: 0.07742; Score2: 0.08897
2022.11.21 21:54:01.112    Test_AO_ABCm (EURUSD,M1)    =============================
2022.11.21 21:54:06.434    Test_AO_ABCm (EURUSD,M1)    1 Megacity's; Func runs 1000 result: 12.0; Func runs 10000 result: 15.0
2022.11.21 21:54:06.434    Test_AO_ABCm (EURUSD,M1)    Score1: 0.80000; Score2: 1.00000
2022.11.21 21:54:11.768    Test_AO_ABCm (EURUSD,M1)    20 Megacity's; Func runs 1000 result: 1.7; Func runs 10000 result: 2.35
2022.11.21 21:54:11.768    Test_AO_ABCm (EURUSD,M1)    Score1: 0.11333; Score2: 0.15667
2022.11.21 21:54:22.235    Test_AO_ABCm (EURUSD,M1)    500 Megacity's; Func runs 1000 result: 0.572; Func runs 10000 result: 0.67
2022.11.21 21:54:22.235    Test_AO_ABCm (EURUSD,M1)    Score1: 0.03813; Score2: 0.04467
2022.11.21 21:54:22.235    Test_AO_ABCm (EURUSD,M1)    =============================
2022.11.21 21:54:22.235    Test_AO_ABCm (EURUSD,M1)    All score for C_AO_ABCm: 0.508357869056105

Değiştirilmiş algoritmanın iki değişkenli iki fonksiyon üzerinde %100 yakınsama göstererek başarısını tekrarladığı görülmektedir. Genel olarak sonuçlar iyileşmiş, nihai puan daha da yükselmiştir: 0.50836. Ne yazık ki, bu, sonuçlarda önemli bir gelişme değildir. Çok sayıda değişkene sahip fonksiyonlar üzerindeki yakınsama sorunları, algoritma uygulamasının klasik versiyonuyla benzerdir.

Bu arada, değiştirilmiş versiyonda kovanın yeniden başlatılmasını gerektiren bir hata yoktur.


4. Test sonuçları

Optimizasyon algoritması

Çalıştırma sayısı

Skin

Forest

Megacity (ayrık)

Nihai sonuç

2 parametre (1 F)

40 parametre (20 F)

1000 parametre (500 F)

2 parametre (1 F)

40 parametre (20 F)

1000 parametre (500 F)

2 parametre (1 F)

40 parametre (20 F)

1000 parametre (500 F)

ACOm

1000

0.99502

0.69826

0.50498

0.99087

0.22374

0.08408

0.78667

0.11667

0.04224

0.54688

10,000

0.99599

0.86403

0.58800

0.99302

0.65571

0.17442

0.78667

0.26133

0.08208

RND

1000

0.98744

0.61852

0.49408

0.89582

0.19645

0.14042

0.77333

0.19000

0.14283

0.51254

10,000

0.99977

0.69448

0.50188

0.98181

0.24433

0.14042

0.88000

0.20133

0.14283

ABCm

1000

0.99720

0.66082

0.48774

0.96827

0.22818

0.07742

0.80000

0.11333

0.03813

0.50836

10,000

1.00000

0.71028

0.49853

0.98188

0.29836

0.08897

1.00000

0.15667

0.04467

ABC

1000

0.99772

0.64085

0.49029

0.94435

0.18937

0.07526

0.69333

0.10333

0.04120

0.49447

10,000

1.00000

0.68769

0.49823

0.99755

0.26279

0.08077

1.00000

0.15400

0.04379

PSO

1000

0.98436

0.72243

0.65483

0.71122

0.15603

0.08727

0.53333

0.08000

0.04085

0.47695

10,000

0.99836

0.72329

0.65483

0.97615

0.19640

0.09219

0.82667

0.10600

0.04085


Değerlendirmeye geçelim. Şaşırtıcı bir şekilde, arı kolonisi algoritması iki test fonksiyonunda (düzgün Skin ve ayrık Megacity) beş testin tamamında %100 yakınsama göstererek olağanüstü bir yakınsama hızı ve kalitesi ortaya koymuştur. Ancak, bu yalnızca iki değişkenli fonksiyonlar için geçerlidir. Ölçeklenebilirlik açısından, algoritma derecelendirme tablosunun diğer üyelerine göre daha düşüktür. Çok değişkenli fonksiyonlar kesinlikle bir arı kolonisinin güçlü noktası değildir. Bu hem test ortamının animasyonunda hem de tablodaki sonuçlarda görülebilmektedir.

ABC algoritması, kullanıcının sürü büyüklüğü, gözcü sayısı ve alan yarıçapı gibi çeşitli parametre ayarlarıyla oynamasını gerektirir. Bu ayarlar belirli bir uygulama için uygun şekilde seçilmezse, algoritma zamanından önce yakınsayabilir veya hiç yakınsamayabilir. Buna ek olarak, ABC karmaşık fonksiyonlarda yavaş yakınsama, yerel çözüm yakalama ve pek iyi olmayan arama özellikleri gibi dezavantajlara sahiptir.

Avantajları:
1. Nispeten hızlıdır.
2. Az değişkenli düzgün ve ayrık fonksiyonlar için harika yakınsama gösterir.

Dezavantajları:
1. Algoritma parametrelerinin sonuç üzerinde güçlü etkisi vardır.
2. Evrensel değildir.
3. Yerel ekstremumlarda takılıp kalabilir.
4. Ölçeklenebilirlik ortalama düzeydedir.


MetaQuotes Ltd tarafından Rusçadan çevrilmiştir.
Orijinal makale: https://www.mql5.com/ru/articles/11736

Ekli dosyalar |
ZIP indir
94_The_world_of_AO_qABCn.zip (44.93 KB)
Uyarı: Bu materyallerin tüm hakları MetaQuotes Ltd.'a aittir. Bu materyallerin tamamen veya kısmen kopyalanması veya yeniden yazdırılması yasaktır.

Bu yazarın diğer makaleleri

Tartışmaya git
Sıfırdan bir ticaret Uzman Danışmanı geliştirme (Bölüm 20): Yeni emir sistemi (III) Sıfırdan bir ticaret Uzman Danışmanı geliştirme (Bölüm 20): Yeni emir sistemi (III)
Yeni emir sistemini uygulamaya devam ediyoruz. Böyle bir sistemin oluşturulması, MQL5'e iyi hakim olmanın yanı sıra MetaTrader 5 platformunun gerçekte nasıl çalıştığını ve hangi kaynakları sağladığını anlamayı gerektirir.
Popülasyon optimizasyon algoritmaları: Karınca kolonisi optimizasyonu (Ant Colony Optimization, ACO) Popülasyon optimizasyon algoritmaları: Karınca kolonisi optimizasyonu (Ant Colony Optimization, ACO)
Bu sefer karınca kolonisi optimizasyonu algoritmasını analiz edeceğiz. Bu algoritma çok ilginç ve karmaşıktır. Makalede, yeni bir ACO türü oluşturma girişiminde bulunacağız.
Sıfırdan bir ticaret Uzman Danışmanı geliştirme (Bölüm 21): Yeni emir sistemi (IV) Sıfırdan bir ticaret Uzman Danışmanı geliştirme (Bölüm 21): Yeni emir sistemi (IV)
Sonunda görsel sistem çalışmaya başlayacak... tam olarak tamamlanmış şekilde olmasa da. Burada ana değişiklikleri yapmayı bitireceğiz. Çok sayıda değişiklik olacaktır ve onların hepsi gereklidir. Tüm çalışma oldukça ilginç olacaktır.
Bear’s Power göstergesine dayalı bir ticaret sistemi nasıl geliştirilir? Bear’s Power göstergesine dayalı bir ticaret sistemi nasıl geliştirilir?
En popüler teknik göstergelere dayalı ticaret sistemlerinin nasıl geliştirileceğine ilişkin serimizin yeni makalesine hoş geldiniz. Bu makalemizde Bear’s Power teknik göstergesine odaklanacağız.