MetaTrader 5 / 例
English Русский 中文 Español Deutsch Português 한국어 Français Italiano Türkçe
preview
母集団最適化アルゴリズム：人工蜂コロニー(ABC)

母集団最適化アルゴリズム：人工蜂コロニー(ABC)

MetaTrader 5 — 例 | 25 1月 2023, 09:33
304 0
Andrey Dik
Andrey Dik

内容

  1. はじめに
  2. アルゴリズムの説明
  3. 修正版
  4. テスト結果


1.はじめに

社会性昆虫は、多くの単体の昆虫がおこなわない複雑な作業を数多くこなす、高度に進化した生物です。コミュニケーション、複雑な巣作り、環境制御、保護、分業などは、蜜蜂が社会的コロニーで繁栄するために進化してきた行動のほんの一例です。
蜜蜂は群れ生物に属し、最適な解決法を見つけることに並々ならぬ能力を発揮します。自然界では、巣の近くに花房を見つけ、蜜や花粉を集めます。その検索半径は数キロメートルまで広がることもあります。戻った蜜蜂は、即興の踊りを使ってその成果を報告します。

一見、不可能に思えますが、リズミカルな動きで地理的な位置の情報を伝え合うことができるのです。蜜蜂は仲間の踊りの激しさによって、指定した地点の花の数や蜜の推定量などを導き出します。潜在的な食べ物が多いほど、踊りはより盛大になります。この不思議な現象は、20世紀半ばに昆虫研究家のカール・フリッシュによって発見されました。

長い間、蜂の探索方法を研究しているのは生物学者だけでした。しかし、新しい最適化アルゴリズムの開発において、群れの行動を応用することへの関心が高まりました。2005年、Dervis Karaboga教授がこの研究結果に興味を持ちました。彼は科学論文を発表し、主に蜜蜂の踊りから着想を得た群知能のモデルを初めて説明しました。そのモデルは「人工蜂コロニー」と呼ばれました。


2.アルゴリズムの説明

人工蜂コロニーには多くの実装があり、巣の中の蜂の管理原理や領域探索のルールに違いがあります。今回は、古典アルゴリズムに対する私の解釈についてお話します。

アルゴリズムのアイデアは、できるだけ多くの蜜を得られる場所を探すときの蜂の行動に基づいています。まず、すべての蜜蜂が巣からランダムな方向に飛び出し、偵察隊となって蜜のある場所を探そうとします。その後、蜜蜂は巣に戻り、特別な方法で、どこでどれだけの蜜を見つけたかを他の蜜蜂に伝えます。

発見された場所に働き蜂が送られられます。蜜が多いと思われる場所ほど、より多くの蜂がその方向に飛んでいくのです。偵察隊は再び他の領域を探しに飛び立ちますが、すでに発見された領域の周辺にいます。このように、すべての蜂は、蜜を集める働き蜂と、新しい場所を探索する偵察蜂の2種類に分けられます。採蜜領域は、その中の蜜の量に対応した値を持ちます。下位の領域は、上位の領域に対して、その中心を通る線上で相対的にずれています。

働き蜂の領域別分布を図式化すると、図1のようになります。

ABC領域

図1：領域ランクに応じた蜜蜂の数

領域1はランクが高く、蜜の量が多いので、より多くの蜂が飛来する傾向があります。蜂の数によって、領域4が最も低いランク（値）であることが視覚的に判断できます。各領域の価値に関する情報は、蜜蜂が特殊な踊りという形で報告します。巣にはそれぞれ独自の踊りがあり、その領域の蜜の方向と量がプログラムされています。

仮に、大域的極値の位置が最も蜜の多い領域であり、そのような領域は1つしかないとします。他の場所にも、量は少ないが蜜があります。蜜蜂は多次元空間に生息しており、各座標は最適化すべき関数の1つのパラメータを表しています。最大値を求めるのであれば、見つかった蜜の量はこの時点の目的関数の値となります。最小値を求めるのであれば、目的関数に-1をかければ十分です。

採蜜領域には一定の数値が設定されているため、ランクが一番高い領域だけが蜜の濃度が一番高いポイントに移動（センターシフト）する権利を持ちます。ランクのより低い領域は、最も濃度の高い中心にシフトされ、ランクのより高い領域との交差が確認されます。このように、ある狭い小領域に蜂が集中することを避け、探索空間をできるだけ効率よく働き蜂に奉仕させることで、餌の枯渇を防いでいるのです。最適化から言うと、これは、極値で行き詰まることをなくす、あるいは最小限に抑えることができるのです。領域が分散され、その最適値に向かうランクの連鎖に沿って相対的にシフトされた後、その近傍がさらに偵察蜂によって調査されます。

多くの養蜂家は、探索空間のランダムな領域に偵察蜂を送ることを推奨しますが、私の経験では、そのような「偵察」の実用的価値はゼロに近く、一次元と二次元にしか役に立ちません。つまり、多次元空間であれば、自由度は幾何級数的に増加し、より貴重な蜜源に偶然出くわすことは非常に困難です。巣の資源が無駄になるだけです。すでに知られている探索領域の近辺に偵察蜂を送り、座標が散在することなく、蜜源となりうるゾーンに特別に集中させる方がはるかに有効です。

領域が交差する場合は、中心をシフトして領域が境界線にのみ接するようにする必要があります。これを図2に示します。

ABCcrossArea

図2：下位の領域をシフトさせる

領域のランクは厳密に決まっているわけではなく、動的に形成されています。偵察蜂の発見は、彼らが飛んだ近辺の領域に割り当てられます。さらに貴重な食料源が発見された場合は、そこに中心をシフトすることになります。新たな最高の採蜜地の中心になるかもしれませｎ。残りの領域は、これと相対的にシフトされるようになります。つまり、ランクチェーンに沿って相対的にシフトすることになります。

蜜蜂の踊りと呼ばれる情報伝達の方法は、巣全体の戦略を考える上で欠かせない要素です。処理領域には巣の利用可能な資源を最も合理的に配分する必要があるため、送り込む蜂の数は領域の価値に比例する必要があります。つまり、同じ数の蜜蜂が同じ価値のある領域に送られることになります。

アルゴリズムそのものに話を移しましょう。実行手順を以下に示します。

  1. すべての蜂は偵察機として探索空間に沿ってランダムに飛行する。
  2. 各蜂から受け取った花蜜の量を測定する。
  3. 蜜蜂を並び替える。
  4. 蜜蜂から得た蜜量情報をもとに、領域を割り当てる。
  5. 働き蜂を送り込む。蜜の量が多ければ多いほど、蜜蜂はたくさん飛んでくる。
  6. 無作為に選んだ領域の近辺に偵察蜂を送る。
  7. 各蜜蜂から受け取った花蜜の量を測定する。
  8. 蜜の量によって領域をランク付けする。
  9. 停止基準に達するまで4から繰り返す。

視覚的にわかりやすいように、図3のようなアルゴリズムのブロック図を作ってみましょう。


ABCsceme

図3：アルゴリズムブロック図

蜂コロニーアルゴリズムのコードをより詳しく説明しましょう。

蜂は、アルゴリズムの初歩的かつ基本的な論理単位で、構造体で記述することができます。蜜蜂の位置は、座標、蜜を集めた領域との関連、蜜の量によって設定されていることはご記憶に新しいと思います。巣の蜂は配列で表現されて、それぞれはインデックスでアクセスできます。

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

2つ目の大きな論理単位は、蜜を採取する領域です。蜜が最も集中する中心・点によって定義され、その蜜の量が領域の価値を決定します。最高ランク（リストの最初）の領域では、中心の座標と蜜の濃度の最高点が一致します。リストの2位以下の領域については、シフトされているため、一致しない場合があります。領域の初期化は、蜜量指標をリセットし、最適化された関数の対応する数のパラメータに座標を割り当てることで終了します。

//——————————————————————————————————————————————————————————————————————————————
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
};
//——————————————————————————————————————————————————————————————————————————————

蜜蜂の踊りを構造体として表現してみましょう。その配列は領域の数に対応することになります。

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

探索領域、蜜蜂、最適な座標、全反復で見つかった最大の蜜の量を設定するクラスとして巣を記述します。また、蜂や領域の振り分け、蜂や領域の相対的な移動など、必要なメソッドはすべてここで定義されます。ここにあるのは、すでにおなじみの、均等に分布する乱数の生成、範囲への拡大縮小、範囲からのステップによる数値の選択という、これまでのアルゴリズムの関数宣言です。

//——————————————————————————————————————————————————————————————————————————————
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
};
//——————————————————————————————————————————————————————————————————————————————

新しい最適化は、必ずクラスの初期化から始める必要があります。蜜の量の値は、巣全体と蜂個体、および領域ごとにリセットされます。

//——————————————————————————————————————————————————————————————————————————————
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;
  }
}
//——————————————————————————————————————————————————————————————————————————————

最もシンプルでオープンなクラスメソッドは、蜜蜂にタスクを分配することです。すべてがシンプルです。まだ探索されていない領域があれば、巣全体の蜜価をリセットして、領域の印付けを開始します。各エポックにおいて、適合度関数の値が得られるまで、このメソッドを呼び出します。

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

2番目のpublicメソッドはエポックごとに呼び出されます。起動は、フィットネス関数の値を取得した後におこなう必要があります。この場合、探査がまだおこなわれていなければ、蜜の値で並び替え、リストの最初の蜂の座標と蜜の量を対応する領域にコピーします。すでに探査がおこなわれている場合は、探査結果が向上していることを条件に、座標と蜜を採取した場所の蜜の量をコピーします。また、巣全体の最適な結果を更新します。

//——————————————————————————————————————————————————————————————————————————————
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 ()メソッドについては、詳細に検討する価値があります。コードをパーツに分解してみましょう。

領域が探索され、蜜を集める花を見つける情報がないうちに、すべての蜂を送り込んで予備探索をおこないます。この段階では、すべての蜜蜂が偵察蜂の役割を果たします。蜜の情報はないので、座標の範囲に均等に分布する乱数を発生させ、ランダムな方向に偵察蜂を送ります。

//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]);
    }
  }
}

領域を探索した後、蜜の最大濃度の座標を領域の中心にコピーする必要があります。つまり、より良い場所に移動させることが必要なのです。この操作をおこなった後は、その領域が上位ランクの領域と交差していないことを確認する必要があります。面積の中心間の距離を測定することで、面積の交わりを確認することができます。中心間の距離が2つの半径（アルゴリズムパラメータの1つ）より小さい場合、領域は交差します。交差点が検出された場合、最も良い結果が得られた座標（最大蜜濃度の座標）はそのままに、半径2つ分の距離にあるポイントに領域が移されます。このように、領域は常に動いています。最高の領域は、他を強制的にシフトさせます。残りの部分は、シフトしながら、より豊かな食料源にたどり着くことができ、並び替え後のベストになるのです。これは次の方法でおこなわれます。

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]);
      }
    }
  }
}

ここで蜜蜂の踊りが繰り広げられます。領域内の蜜の方向と量の情報を用い、ランダム成分を適用して、次の反復で蜂がある領域を選択する確率がその領域の蜜の量に比例するように乱数の分布領域をマークします。つまり、数直線上に、各領域の蜜価の差に相当する長さのセグメントを、最も悪い領域との間にプロットします。

//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;
  }
}

この部分のメソッドコードでは、働き蜂の踊りによって伝達される確率で、ランダムに領域が選択されます。そのために、数直線上に踊りで印を付けて作った範囲の乱数を発生させます。偵察蜂はどの領域の近くでも等しい確率で飛ぶので、踊りは関係なく、蜂戦略の探索能力を拡大することができます。自然界と同じように、巣の参加者はそれぞれ役割を果たしながら、一定の価値を持っています。

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]);
  }
}

このprivateメソッドは、蜂の飛行を実装しています。一見、わけがわからず複雑そうに見えますが、ここではすべてがシンプルです。蜜蜂は、中心により近い3乗確率シフトの領域に飛んでいきます。そのため、領域中心から境界にかけて確率が低下します。これは領域の中心であり、先ほど見つけた最高の位置ではないことに留意してください。この単純な行動からも、蜜蜂の戦略が読み取れ、新たな餌を探し続けることができるのです。

//——————————————————————————————————————————————————————————————————————————————
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]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

従来の方法とは異なり、ここでは偵察蜂の飛行について説明します。蜂はアルゴリズム設定で指定された半径内の領域外を飛行します。設定は同じでも、座標範囲が異なる場合があるので、半径はあらかじめクラスの初期化時に計算しておき、適切な半径を設定します。偵察蜂を飛行させるためには、領域の半径から領域の半径と探査の半径の和までの範囲で乱数を生成し、その結果の値を領域の中心に単純加算する必要があります。このような単純な方法では、偵察蜂は偶然にその付近にいることになる一方、座標は探索空間に散らばることはありません。

//——————————————————————————————————————————————————————————————————————————————
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]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

アルゴリズムの具体的な方法としては、蜂の並び替えと領域の並びかえの2つがあります。単純なバブルソートに過ぎないので、説明は必要ありません。私はほとんどすべての最適化アルゴリズム (ソートが必要な場合) でバブルソートを使用します。この方法は単純で、特定のタスクに合わせて簡単に変更でき、すべてのソート方法の中で最高の速度を提供する方法の1つだからです。

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

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

検討したコードをすべて集めて、コンパイルします。テストスタンドの実行後、以下のようなアニメーションが表示され、蜂アルゴリズムの挙動を確認することができます。蜜蜂は別々の場所ではっきりと観察されます。領域が互いに入れ替わりながら移動している様子がわかります。精度と特異な「群」の数は、アルゴリズムの設定に依存します。

Skin

Skinテスト関数のACO

Forest

Forestテスト関数のACO

Megacity

Megacityテスト関数のACO

以下は、テスト関数でのアルゴリズム結果です。

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

このアルゴリズムは、2つの2変数テスト関数に対して完全に収束しています。残りの結果を評価するのは時期尚早です。結果を表にして、他の最適化アルゴリズムとの比較で結論を出すのがよいでしょう。


3.修正版

最適化アルゴリズムを開発・設計する際、必ずと言っていいほど疑問に思うことがあります。「アルゴリズムが意図したとおりに動くのか、それともコードのどこかにエラーがあるのか」ということです。 確率的探索過程は、その性質上ランダムであるため、アルゴリズムによって最適化結果が得られたのか、それともどこかに誤りがあって本当に非ランダムな結果になってしまったのか、はっきりしないのではないでしょうか。蜂コロニーアルゴリズムを開発する際にも、同じような現象に遭遇しました。テストセットの5つのテストのうち、最初のテストでは、アルゴリズムは明らかに収束しようとせず、探索を開始した地点で止まってしまいました。このバグは、論理的にはまったく信じられない方法で解決されました。エポック開始前にすでに初期化されていたにもかかわらず、最初のエポックでさらに2回目の巣クラスの初期化をおこなっただけでした（Test_AO_ABC.mq5の文字列142）。この謎を解き明かした方がいらっしゃたら、ぜひコメントで教えてください。

上記の理由と、最初のテストでは全く満足のいく結果が得られなかったこともあり（後にアルゴリズム設定の実験が必要であることが明らかになった）、私は蜂の探索戦略を変更することを思いついたのです。オリジナル版では、面積値に比例して蜂が飛びます。新しいアルゴリズムでは、各領域に決まった数の蜜蜂がいるようにします。つまり、面積のランクに関係なく、それぞれに常に同じ数の蜂があるようにします。そこで、この領域を「蜂の群れ」という概念でロジカルに表現しました。

領域の構造体に代わって、次のような構造体になります。

//——————————————————————————————————————————————————————————————————————————————
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
};
//——————————————————————————————————————————————————————————————————————————————

この構造体も初期化関数を持ちますが、さらにbees[]配列が存在します。

一般に、残りのコードは古典版と非常によく似ているので、あまり重視しない方がよいでしょう。コードは以下のアーカイブに添付されています。特に注目すべきは、アルゴリズムのロジックの違いです。ステップバイステップでいうと、こんな感じです。

  1. 最初の群れの中心を作り、その周りに蜜蜂を配置する。
  2. 後続の群れの中心を作り、中心から前の群れまでの距離がR*2（2つの半径）以上であることを確認し、中心付近に蜜蜂を配置する。
  3. それぞれの蜂が他の群よりR（半径）以上の距離で離れるように偵察蜂を送り込む。
  4. すべての蜂の適応度関数の値を取得する。
  5. 群れを並び替える。
  6. 各群の中心の周りに蜂を配置する。
  7. 停止条件が満たされるまで、4から繰り返す。

お気づきのように、検索戦略には根本的な違いがあります。古典版では、領域ごとに蜂の数が異なることがありましたが、ここでは常に同じ大きさの蜂の群れが出現します。これは、食料源が枯渇しても探査を続けられるようにするためで、ハイパースペースでの探査をより綿密におこなうことができます。テストでは、このアプローチの正当性が確認されました。結果が向上しています。偵察蜂は領域近辺を飛行せず、空間のフリー領域に落下し、しかも古典版と同様に領域のルールに従います。古典版の蜂の場合、偵察蜂は既探索領域に入れることを気にせず完全にランダムな方向に散らばるため、説明したような挙動をせず、最も基本的な探索を失います。配列の最後の群れは偵察蜂の群れです。この群れには、「他人のスペースに入らない」というルールも適用されますが、偵察蜂の群れ全体ではなく、単体に対してです。

以下は、修正版の結果です。

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

修正したアルゴリズムは、2つの変数を持つ2つの関数で成功を繰り返し、100%の収束を示したことがわかります。概して、結果は改善され、最終的なスコアは高くなりました。0.50836です。残念ながら、これは大きな成果の向上とは言えません。変数数の多い関数に対する収束問題は、古典版のアルゴリズム実装と同等です。

ちなみに、修正版では、巣の再初期化を必要とするバグはありません。


4.テスト結果

AO

実行

Skin

Forest

Megacity（discrete）

最終結果

2パラメータ（1F）

40パラメータ（20F）

1000パラメータ（500F）

2パラメータ（1F）

40パラメータ（20F）

1000パラメータ（500F）

2パラメータ（1F）

40パラメータ（20F）

1000パラメータ（500F）

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


まとめてみましょう。驚くべきことに、蜂コロニーアルゴリズムは、2つのテスト関数（滑らかなSkin関数とMegacity離散関数）に対して、5つのテストすべてで100%の収束を示し、驚異的な速度と収束の質を実証しました。ただし、これは2つの変数を持つ関数にのみ適用されます。拡張性という点では、このアルゴリズムは他の評価表のメンバーに劣ります。複数の変数を持つ関数は、間違いなく蜂コロニーの得意とするところではありません。このことは、テストスタンドのアニメーションと、表で提供される結果の両方で確認することができます。

ABCアルゴリズムでは、群サイズ、偵察蜂の数、領域半径など、いくつかのパラメトリック設定をいじる必要があります。これらの設定が特定の適用に対して適切に選択されていない場合、アルゴリズムは早期に収束するか、全く収束しない可能性があります。また、ABCには、複雑な関数に対する収束が遅い、局所的な解の捕捉、平凡な探索特性といった欠点があります。

賛成：
1.比較的速い
2.少数の変数を持つ滑らかな離散関数に対する現象的収束

反対：
1.アルゴリズムのパラメータが結果に強く影響する
2.汎用でない
3.極値にはまる
4.平均的な拡張性


MetaQuotes Ltdによってロシア語から翻訳されました。
元の記事: https://www.mql5.com/ru/articles/11736

添付されたファイル |
ZIPをダウンロード
94_The_world_of_AO_qABCn.zip (44.93 KB)
警告: これらの資料についてのすべての権利はMetaQuotes Ltd.が保有しています。これらの資料の全部または一部の複製や再プリントは禁じられています。

この著者による他の記事

ディスカッションに移動
母集団最適化アルゴリズム：灰色オオカミオプティマイザー(GWO) 母集団最適化アルゴリズム：灰色オオカミオプティマイザー(GWO)
最新の最適化アルゴリズムの1つである灰色オオカミオプティマイザについて考えてみましょう。テスト関数の元々の動作により、このアルゴリズムは、以前に検討されたものの中で最も興味深いものの1つになります。これは、ニューラルネットワークの訓練に使用される最も優れたアルゴリズムの1つであり、多くの変数を持つ滑らかな関数です。
非線形指標 非線形指標
今回は、非線形指標を構築する方法と取引での使用について、いくつか考えてみたいと思います。MetaTraderの取引プラットフォームには、非線形なアプローチを使用する指標がかなりあります。
DoEasy - コントロール（第28部）：ProgressBarコントロールのバースタイル DoEasy - コントロール（第28部）：ProgressBarコントロールのバースタイル
今回は、ProgressBarコントロールでのプログレスバーの表示スタイルと説明テキストを開発します。
MQL5を使った線の扱い方 MQL5を使った線の扱い方
今回は、MQL5によるトレンドラインや支持線と抵抗線といった、最も重要な線の扱い方についてご紹介します。