群体优化算法

“宇宙中根本什么都没有发生
其中某种最大或最小规则从未出现过”
莱昂哈德·欧拉（Leonhard Euler），18世纪

内容:

1. 历史视角
2. 优化算法（OA）分类
3. 收敛和收敛率。 收敛稳定性。 优化算法可扩展性
4. 测试函数，构建复杂的 OA 评估准则
5. 测试基台
6. 使用 RNG 的简单 OA
7. 结果

 

1. 历史视角

优化算法是允许在函数域中查找函数所能达到其最小或最大极值的算法。

古希腊的智者已经知道：

— 给定周长的所有形状之中，圆的面积最大。

— 给定边数且给定周长的所有多边形之中，正规多边形的面积最大。

— 给定面积的所有三维图形之中，球体的体积最大。

第一个具有可变分解的问题也大约在同一时间被提出。 根据传说，这发生在公元前 825 年左右。 狄多，腓尼基城邦推罗之王的妹妹，搬到了地中海南部海岸，并向当地一个部落索要一块可用一张牛皮覆盖的土地。 部落人给了她一块皮子。 这位足智多谋的女孩把它剪成细带，并结成一条绳子。 用这根绳子，她覆盖了海岸附近的领土，并在那里建立了迦太基城。

该问题在于查找最有效曲线，即，以给定长度的闭合平面曲线所能覆盖的最大表面积。 此问题中的最大面积由半圆圈定的区域表示。

 

 

 

现在，我们跳过一大段历史，包括地中海的古代文化、宗教裁判所的压迫、和中世纪的庸医，直到文艺复兴时期的新思维和新理论的自由翱翔。 1696 年 6 月，约翰·伯努利（Johann Bernoulli）为《教师学报》的读者发表了以下声明：“我，约翰·伯努利，向世界上最杰出的数学家致敬。 对于聪明的人来说，没有什么比一个坦诚的、具有挑战性的问题更有吸引力的了，可能的解决方案将带来名声，并留下一座永恒的纪念碑。 以帕斯卡（Pascal）、费马（Fermat）、等人为榜样，我希望通过向我们这个时代最优秀的数学家提出一个问题来测试他们的方法和智力力量，从而获得整个科学界的感激之情。 如果有人向我沟通所提问题的解决方案，我将公开宣布他值得赞扬”。

约翰·伯努利的最速降线问题：

“给定垂直平面上的两个点 A 和 B，跟踪仅受重力作用的点所经过的曲线，自 A 点开始，哪一条到达 B 点的时间最短”。 值得注意的是，早在伯努利发表之前，伽利略（Galileo）于 1638 年就试图解决类似的问题。 答案是：从一点到另一点的最快路径不是最短的路径，就好似乍一看，这不是一条直线，而是一条曲线 — 曲线的每个点处的曲率都确定的摆线。

 最速降线

所有其它解决方案，包括牛顿的解决方案（当时没有透露），都是基于查找每个点处的梯度。 艾萨克·牛顿（Isaac Newton）提出的解决方案，其方法的背后构成了变分计算的基础。 变分计算的方法通常用于求解问题，其中最优性准则以泛函的形式呈现，其解是未知函数。 此类问题通常出现在具有分布式参数过程的静态或动态优化问题当中。

变分计算中的一阶极值条件由伦纳德·欧拉（Leonard Euler）和约瑟夫·拉格朗日（Joseph Lagrange）的《欧拉-拉格朗日方程》获得。 这些方程广泛用于优化问题，并与稳态作用原理一起应用于力学轨迹的计算。 然而，很快，人们就清楚地发现，这些方程的解并不能始终给出一个真实的极值，这意味着需要足够的条件来保证它的发现。 这项工作继续推进，勒让德（Legendre）和扎克比（Jacobi）推导出二阶极值条件，之后是后者的学生 — 黑森（Hesse）。 变分计算中存在解的问题最早是由魏尔斯特拉斯（Weierstrass）在 19 世纪下半叶提出的。

到 18 世纪下半叶，寻找问题的最佳解决方案形成了数学基础和优化原则。 不幸的是，直到 20 世纪下半叶，优化方法在许多科学和技术领域实际上作用甚微，因为实际运用该数学方法需要庞大的计算资源。 现代世界新计算技术的出现，令实现复杂的优化方法最终成为可能，从而催生出了各种各样的可用算法。

1980 年代，见证了爆发式随机优化算法类的密集开发，这是从自然社会借取建模的结果。

 

2. 优化算法（OA）分类

 分级 AO

在优化交易系统时，最令人兴奋的是启发式优化算法。 它们不需要了解正在优化的函数公式。 它们的收敛性与全局最优值的关联并未得到证实，但它已由实验性建立，在大多数情况下，它们给出了一个相当优良的方案，这对于一定数量的问题来说已经足够了。

许多优化算法都是从自然社会中借取的模型。 这样的模型也被称为行为、种群或群体，例如鸟群中鸟类的行为（粒子群算法），或蚁群行为原理（蚂蚁算法）。

群体算法涉及同时处理求解优化问题的若干个选项，并且代表了基于运动轨迹的经典算法的替代方案，在求解问题时其搜索区域只有一个候选算法。

 

3. 收敛和收敛率。 收敛稳定性。 优化算法可扩展性

效率、速度、收敛性，以及问题条件和算法参数的影响，需要针对每个算法的实现，和每类优化问题进行仔细分析。

3.1) 收敛和收敛率

 

迭代算法的属性，在有限步数内达到、或足够接近目标函数的最佳值。 在上面屏幕截图的右侧，我们看到测试函数计算生成结果的迭代构造图。 基于这两幅图像，我们能得出结论，收敛性受到函数表面复杂性的影响。 越复杂，找到全局极值就越困难。

算法收敛率是衡量优化算法品质的最重要指标之一，也是优化方法的主要特征之一。 当我们听到一种算法比另一种算法快时，多数情况下，这意味着收敛率。 结果越接近全局极值，得到的速度越快（意味着算法的早期迭代），此参数值就越高。 注意，方法的收敛率通常不超过二次方收敛率。 在极少数情况下，该方法也许具有三次方收敛率。

3.2) 收敛稳定性

达成结果所需的迭代次数不仅取决于算法本身的搜索能力，还取决于所研究的函数。 如果函数的特征具有表面的高度复杂性（存在急弯、离散性、不连续性），那么算法可能会变得不稳定，根本无法提供可接受的精度。 此外，收敛稳定性可以理解为连续进行多次测试时，优化结果的可重复性。 如果结果值差别很大，则算法的稳定性较低。

3.3) 优化算法可扩展性

优化算法的可伸缩性是随着问题维度的递增而维持收敛的能力。 换言之，随着优化函数变量数量的增加，收敛性应保持在实际目标可接受的水平。 与经典算法相比，搜索优化的群体算法具有不可否认的优势，尤其是在解决高维和形式化低劣的问题之时。 在这些条件下，群体算法可以提供优化函数定位全局极值的高概率。

在平滑和单峰优化函数的情况下，群体算法通常不如任意的经典梯度方法有效。 还有，群体算法的缺点包括其效率对自由度（调谐参数的数量）的强烈依赖性，在大多数算法中占相当数量。

 

4. 测试函数，构建复杂的 OA 评估准则

没有普遍可接受的方法来测试和比较优化算法。 然而，在不同的年代，研究人员提出了许多测试函数。 我们将用之前我创建并贴在第一篇文章里的函数。 这些函数可在终端文件夹 MQL5ExpertsExamplesMath 3DFunctions.mqh 和 MQL5ExpertsExamplesMath 3D MorpherFunctions.mqh 当中找到。. 这些函数满足 OA 测试的所有复杂性准则。 此外，还开发了 Forest 和 Megacity 函数，从而提供了对 OA 搜索能力的更全面研究。

Skin 测试函数:

该函数在其整个域中都是平滑的，并有许多差别不特明显的局部最大值/最小值（收敛陷阱），这会导致算法在尚未达到全局极值时就卡住。

Skin

Forest 测试函数:

该函数呈现出若干个最大值，在它们之间没有差别。 因此，优化算法可能很难证明结果，其健壮性的关键取决于所研究函数的平滑性。

Forest

Megacity 测试函数:

形成“区域”的离散函数（其中更改变量不会导致函数值发生重大变化）。 因此，它给需要梯度的算法带来了困扰。

Megacity

5. 测试基台

为了全面比较优化算法，尝试创建一个通用评估准则。 该想法的复杂性在于事实上不清楚如何比较算法，因为对于相应的问题类别，每个算法都有自己擅长方式。 例如，一种算法收敛迅速，但伸缩性不好；而另一种算法伸缩性良好，但不稳定。 

•  收敛：为了研究收敛性，我们利用上面介绍的三个函数。 它们的最大值和最小值被转换为从 0.0（最差结果）到 1.0（最佳结果）的范围，这将令我们能够评估算法针对不同类型问题确保收敛的能力。
• 收敛率：该算法的最佳结果是在测试函数的第 1000 次和第 10,000 次运行时量得的。 因此，我们可以看出 OA 的收敛有多快。 收敛越快，收敛图曲线越朝向最大值。
•   稳定性：每个函数运行五次优化，并计算 0.0 到 1.0 范围内的平均值。 这是必要的，因为某些算法可能每次运行结果都有很大不同。 五次测试中每次测试的收敛性越高，稳定性就越高。
•   伸缩性：一些 OA 只能在具有少量变量的函数上展现出实际结果，例如，不超过两个，有些 OA 甚至无法支持一个以上的变量。 此外，还有一些算法能够操控拥有上千个变量的函数。 这种优化算法可用作神经网络的 OA。  

为了方便使用测试函数，我们编写一个父类和一个枚举器，允许我们将来选择相应子类对象的测试函数：

//——————————————————————————————————————————————————————————————————————————————  class C_Function  {    public: //====================================================================    double CalcFunc (double &args [], //function arguments                     int     amount)  //amount of runs functions    {      double x, y;      double sum = 0.0;      for (int i = 0; i < amount; i++)      {        x = args [i * 2];        y = args [i * 2 + 1];          sum += Core (x, y);      }        sum /= amount;        return sum;    }    double GetMinArg () { return minArg;}    double GetMaxArg () { return maxArg;}    double GetMinFun () { return minFun;}    double GetMaxFun () { return maxFun;}    string GetNamFun () { return fuName;}      protected: //==================================================================    void SetMinArg (double min) { minArg = min;}    void SetMaxArg (double max) { maxArg = max;}    void SetMinFun (double min) { minFun = min;}    void SetMaxFun (double max) { maxFun = max;}    void SetNamFun (string nam) { fuName = nam;}      private: //====================================================================    virtual double Core (double x, double y) { return 0.0;}        double minArg;    double maxArg;    double minFun;    double maxFun;    string fuName;  };  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  enum EFunc  {    Skin,    Forest,    Megacity,      };  C_Function *SelectFunction (EFunc f)  {    C_Function *func;    switch (f)    {      case  Skin:        func = new C_Skin (); return (GetPointer (func));      case  Forest:        func = new C_Forest (); return (GetPointer (func));      case  Megacity:        func = new C_Megacity (); return (GetPointer (func));            default:        func = new C_Skin (); return (GetPointer (func));    }  }  //——————————————————————————————————————————————————————————————————————————————

         

然后子类将如下所示：

//——————————————————————————————————————————————————————————————————————————————  class C_Skin : public C_Function  {    public: //===================================================================    C_Skin ()    {      SetNamFun ("Skin");      SetMinArg (-5.0);      SetMaxArg (5.0);      SetMinFun (-4.3182);  //[x=3.07021;y=3.315935] 1 point      SetMaxFun (14.0606);  //[x=-3.315699;y=-3.072485] 1 point    }      private: //===================================================================    double Core (double x, double y)    {      double a1=2*x*x;      double a2=2*y*y;      double b1=MathCos(a1)-1.1;      b1=b1*b1;      double c1=MathSin(0.5*x)-1.2;      c1=c1*c1;      double d1=MathCos(a2)-1.1;      d1=d1*d1;      double e1=MathSin(0.5*y)-1.2;      e1=e1*e1;       double res=b1+c1-d1+e1;     return(res);    }  };  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  class C_Forest : public C_Function  {    public: //===================================================================    C_Forest ()    {      SetNamFun ("Forest");      SetMinArg (-50.0);      SetMaxArg (-18.0);      SetMinFun (0.0);             //many points      SetMaxFun (15.95123239744);  //[x=-25.132741228718345;y=-32.55751918948773] 1 point    }      private: //===================================================================    double Core (double x, double y)    {      double a = MathSin (MathSqrt (MathAbs (x - 1.13) + MathAbs (y - 2.0)));      double b = MathCos (MathSqrt (MathAbs (MathSin (x))) + MathSqrt (MathAbs (MathSin (y - 2.0))));      double f = a + b;        double res = MathPow (f, 4);      if (res < 0.0) res = 0.0;      return (res);    }  };  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  class C_Megacity : public C_Function  {    public: //===================================================================    C_Megacity ()    {      SetNamFun ("Megacity");      SetMinArg (-15.0);      SetMaxArg (15.0);      SetMinFun (0.0);   //many points      SetMaxFun (15.0);  //[x=`3.16;y=1.990] 1 point    }      private: //===================================================================    double Core (double x, double y)    {      double a = MathSin (MathSqrt (MathAbs (x - 1.13) + MathAbs (y - 2.0)));      double b = MathCos (MathSqrt (MathAbs (MathSin (x))) + MathSqrt (MathAbs (MathSin (y - 2.0))));      double f = a + b;        double res = floor (MathPow (f, 4));      return (res);    }  };  //——————————————————————————————————————————————————————————————————————————————

为了检查在测试基台上获得的 OA 测试结果的有效性，我们可用一个脚本来列举以 Step 为步长的 X 和 Y 函数。 选择步长时要小心，因为太小的步长会导致计算花费太长时间。 例如，Skin 函数的参数范围是 [-5;5]。 分别沿 X 轴取步长为 0.00001，则它是 (5-(-5))/0.00001=1’000’000（百万）步，Y 轴的数字相同，测试函数计算每个点的值所需运行总次数等于 1’000’000 х 1’000’000= 1’000’000’000’000（10^12，万亿）。

有必要理解 OA 的任务有多艰难，因为它需要在 10,000 步中找到最大值（在 MetaTrader 5 优化器中大约是取这个值）。 请注意，此计算是针对拥有两个变量的函数进行的，测试中将用到的最大变量数量为 1000。

//——————————————————————————————————————————————————————————————————————————————  input EFunc  Function          = Skin;  input double Step              = 0.01;    //——————————————————————————————————————————————————————————————————————————————  void OnStart ()  {    C_Function *TestFunc = SelectFunction (Function);      double argMin = TestFunc.GetMinArg ();    double argMax = TestFunc.GetMaxArg ();      double maxFuncValue = 0;    double xMaxFunc     = 0.0;    double yMaxFunc     = 0.0;        double minFuncValue = 0;    double xMinFunc     = 0.0;    double yMinFunc     = 0.0;        double fValue       = 0.0;      double arg [2];      arg [0] = argMin;    arg [1] = argMin;      long cnt = 0;      while (arg [1] <= argMax && !IsStopped ())    {      arg [0] = argMin;        while (arg [0] <= argMax && !IsStopped ())      {        cnt++;          fValue = TestFunc.CalcFunc (arg, 1);          if (fValue > maxFuncValue)        {          maxFuncValue = fValue;          xMaxFunc = arg [0];          yMaxFunc = arg [1];        }        if (fValue < minFuncValue)        {          minFuncValue = fValue;          xMinFunc = arg [0];          yMinFunc = arg [1];        }          arg [0] += Step;                if (cnt == 1)        {         maxFuncValue = fValue;         minFuncValue = fValue;        }      }        arg [1] += Step;    }        Print ("======", TestFunc.GetNamFun (), ", launch counter: ", cnt);    Print ("MaxFuncValue: ", DoubleToString (maxFuncValue, 16), " X: ", DoubleToString (xMaxFunc, 16), " Y: ", DoubleToString (yMaxFunc, 16));    Print ("MinFuncValue: ", DoubleToString (minFuncValue, 16), " X: ", DoubleToString (xMinFunc, 16), " Y: ", DoubleToString (yMinFunc, 16));               delete TestFunc;  }    //——————————————————————————————————————————————————————————————————————————————

我们来编写一个测试基台：

#include <CanvasCanvas.mqh>  #include <MathFunctions.mqh>  #include "AO_RND.mqh"    //——————————————————————————————————————————————————————————————————————————————  input int    Population_P       = 50;  input double ArgumentStep_P     = 0.0;  input int    Test1FuncRuns_P    = 1;  input int    Test2FuncRuns_P    = 20;  input int    Test3FuncRuns_P    = 500;  input int    Measur1FuncValue_P = 1000;  input int    Measur2FuncValue_P = 10000;  input int    NumberRepetTest_P  = 5;  input int    RenderSleepMsc_P   = 0;    //——————————————————————————————————————————————————————————————————————————————  int WidthMonitor = 750;  //monitor screen width  int HeighMonitor = 375;  //monitor screen height    int WidthScrFunc = 375 - 2;  //test function screen width  int HeighScrFunc = 375 - 2;  //test function screen height    CCanvas Canvas;  //drawing table  C_AO_RND AO;     //AO object    C_Skin       SkiF;  C_Forest     ForF;  C_Megacity  ChiF;    struct S_CLR  {      color clr [];  };    S_CLR FunctScrin []; //two-dimensional matrix of colors  double ScoreAll = 0.0;    //——————————————————————————————————————————————————————————————————————————————  void OnStart ()  {    //creating a table -----------------------------------------------------------    string canvasName = "AO_Test_Func_Canvas";    if (!Canvas.CreateBitmapLabel (canvasName, 5, 30, WidthMonitor, HeighMonitor, COLOR_FORMAT_ARGB_RAW))    {      Print ("Error creating Canvas: ", GetLastError ());      return;    }    ObjectSetInteger (0, canvasName, OBJPROP_HIDDEN, false);    ObjectSetInteger (0, canvasName, OBJPROP_SELECTABLE, true);      ArrayResize (FunctScrin, HeighScrFunc);    for (int i = 0; i < HeighScrFunc; i++)    {      ArrayResize (FunctScrin [i].clr, HeighScrFunc);    }        //============================================================================    //Test Skin###################################################################    Print ("=============================");    CanvasErase ();    FuncTests (SkiF, Test1FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrLime);    FuncTests (SkiF, Test2FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrAqua);    FuncTests (SkiF, Test3FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrOrangeRed);        //Test Forest#################################################################    Print ("=============================");    CanvasErase ();    FuncTests (ForF, Test1FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrLime);    FuncTests (ForF, Test2FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrAqua);    FuncTests (ForF, Test3FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrOrangeRed);        //Test Megacity#############################################################    Print ("=============================");    CanvasErase ();    FuncTests (ChiF, Test1FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrLime);    FuncTests (ChiF, Test2FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrAqua);    FuncTests (ChiF, Test3FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrOrangeRed);        Print ("All score for C_AO_RND: ", ScoreAll / 18.0);  }  //——————————————————————————————————————————————————————————————————————————————    void CanvasErase ()  {    Canvas.Erase (XRGB (0, 0, 0));    Canvas.FillRectangle (1,                1, HeighMonitor - 2, HeighMonitor - 2, COLOR2RGB (clrWhite));    Canvas.FillRectangle (HeighMonitor + 1, 1, WidthMonitor - 2, HeighMonitor - 2, COLOR2RGB (clrWhite));  }    //——————————————————————————————————————————————————————————————————————————————  void FuncTests (C_Function &f,                  int        funcCount,                  double     minFuncVal,                  double     maxFuncVal,                  double     xBest,                  double     yBest,                  color      clrConv)  {    DrawFunctionGraph (f.GetMinArg (), f.GetMaxArg (), minFuncVal, maxFuncVal, f);    SendGraphToCanvas (1, 1);    int x = (int)Scale (xBest, f.GetMinArg (), f.GetMaxArg (), 0, WidthScrFunc - 1, false);    int y = (int)Scale (yBest, f.GetMinArg (), f.GetMaxArg (), 0, HeighScrFunc - 1, false);    Canvas.Circle (x + 1, y + 1, 10, COLOR2RGB (clrBlack));    Canvas.Circle (x + 1, y + 1, 11, COLOR2RGB (clrBlack));    Canvas.Update ();    Sleep (1000);      int xConv = 0.0;    int yConv = 0.0;      int EpochCmidl = 0;    int EpochCount = 0;      double aveMid = 0.0;    double aveEnd = 0.0;      //----------------------------------------------------------------------------    for (int test = 0; test < NumberRepetTest_P; test++)    {      InitAO (funcCount * 2, f.GetMaxArg (), f.GetMinArg (), ArgumentStep_P);        EpochCmidl = Measur1FuncValue_P / (ArraySize (AO.S_Colony));      EpochCount = Measur2FuncValue_P / (ArraySize (AO.S_Colony));        // Optimization-------------------------------------------------------------      AO.F_EpochReset ();          for (int epochCNT = 1; epochCNT <= EpochCount && !IsStopped (); epochCNT++)      {        AO.F_Preparation ();          for (int set = 0; set < ArraySize (AO.S_Colony); set++)        {          AO.A_FFcol [set] = f.CalcFunc (AO.S_Colony [set].args, funcCount);        }          AO.F_Sorting ();          if (epochCNT == EpochCmidl) aveMid += AO.A_FFpop [0];          SendGraphToCanvas  (1, 1);          //draw a population on canvas        for (int i = 0; i < ArraySize (AO.S_Population); i++)        {          if (i > 0) PointDr (AO.S_Population [i].args, f.GetMinArg (), f.GetMaxArg (), clrWhite, 1, 1, funcCount);        }        PointDr (AO.S_Population [0].args, f.GetMinArg (), f.GetMaxArg (), clrBlack, 1, 1, funcCount);          Canvas.Circle (x + 1, y + 1, 10, COLOR2RGB (clrBlack));        Canvas.Circle (x + 1, y + 1, 11, COLOR2RGB (clrBlack));          xConv = (int)Scale (epochCNT,       1,          EpochCount, 2, WidthScrFunc - 2, false);        yConv = (int)Scale (AO.A_FFpop [0], minFuncVal, maxFuncVal, 1, HeighScrFunc - 2, true);          Canvas.FillCircle (xConv + HeighMonitor + 1, yConv + 1, 1, COLOR2RGB (clrConv));          Canvas.Update ();        Sleep (RenderSleepMsc_P);      }        aveEnd += AO.A_FFpop [0];        Sleep (1000);    }      aveMid /= (double)NumberRepetTest_P;    aveEnd /= (double)NumberRepetTest_P;      double score1 = Scale (aveMid, minFuncVal, maxFuncVal, 0.0, 1.0, false);    double score2 = Scale (aveEnd, minFuncVal, maxFuncVal, 0.0, 1.0, false);        ScoreAll += score1 + score2;      Print (funcCount, " ", f.GetNamFun (), "'s; Func runs ", Measur1FuncValue_P, " result: ", aveMid, "; Func runs ", Measur2FuncValue_P, " result: ", aveEnd);    Print ("Score1: ", DoubleToString (score1, 5), "; Score2: ", DoubleToString (score2, 5));  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  void InitAO (const int    params,  //amount of the optimized arguments               const double max,     //maximum of the optimized argument               const double min,     //minimum of the optimized argument               const double step)    //step of the optimized argument  {    AO.F_Init (params, Population_P);    for (int idx = 0; idx < params; idx++)    {      AO.A_RangeMax  [idx] = max;      AO.A_RangeMin  [idx] = min;      AO.A_RangeStep [idx] = step;    }  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  void PointDr (double &args [], double Min, double Max, color clr, int shiftX, int shiftY, int count)  {    double x = 0.0;    double y = 0.0;        double xAve = 0.0;    double yAve = 0.0;        int width  = 0;    int height = 0;        color clrF = clrNONE;        for (int i = 0; i < count; i++)    {      xAve += args [i * 2];      yAve += args [i * 2 + 1];               x = args [i * 2];      y = args [i * 2 + 1];            width  = (int)Scale (x, Min, Max, 0, WidthScrFunc - 1, false);      height = (int)Scale (y, Min, Max, 0, HeighScrFunc - 1, false);            clrF = DoubleToColor (i, 0, count - 1, 0, 360);      Canvas.FillCircle (width + shiftX, height + shiftY, 1, COLOR2RGB (clrF));    }        xAve /= (double)count;    yAve /= (double)count;      width  = (int)Scale (xAve, Min, Max, 0, WidthScrFunc - 1, false);    height = (int)Scale (yAve, Min, Max, 0, HeighScrFunc - 1, false);      Canvas.FillCircle (width + shiftX, height + shiftY, 3, COLOR2RGB (clrBlack));    Canvas.FillCircle (width + shiftX, height + shiftY, 2, COLOR2RGB (clr));  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  void SendGraphToCanvas (int shiftX, int shiftY)  {    for (int w = 0; w < HeighScrFunc; w++)    {      for (int h = 0; h < HeighScrFunc; h++)      {        Canvas.PixelSet (w + shiftX, h + shiftY, COLOR2RGB (FunctScrin [w].clr [h]));      }    }  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  void DrawFunctionGraph (double     min,                          double     max,                          double     fMin,                          double     fMax,                          C_Function &f)  {    double ar [2];    double fV;      for (int w = 0; w < HeighScrFunc; w++)    {      ar [0] = Scale (w, 0, HeighScrFunc, min, max, false);      for (int h = 0; h < HeighScrFunc; h++)      {        ar [1] = Scale (h, 0, HeighScrFunc, min, max, false);        fV = f.CalcFunc (ar, 1);        FunctScrin [w].clr [h] = DoubleToColor (fV, fMin, fMax, 0, 250);      }    }  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  //Scaling a number from a range to a specified range  double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool Revers = false)  {    if (OutMIN == OutMAX) return (OutMIN);    if (InMIN == InMAX) return ((OutMIN + OutMAX) / 2.0);    else    {      if (Revers)      {        if (In < InMIN) return (OutMAX);        if (In > InMAX) return (OutMIN);        return (((InMAX - In) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);      }      else      {        if (In < InMIN) return (OutMIN);        if (In > InMAX) return (OutMAX);        return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);      }    }  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  color DoubleToColor (const double in,    //input value                       const double inMin, //minimum of input values                       const double inMax, //maximum of input values                       const int    loH,   //lower bound of HSL range values                       const int    upH)   //upper bound of HSL range values  {    int h = (int)Scale (in, inMin, inMax, loH, upH, true);    return HSLtoRGB (h, 1.0, 0.5);  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  color HSLtoRGB (const int    h, //0   ... 360                  const double s, //0.0 ... 1.0                  const double l) //0.0 ... 1.0  {    int r;    int g;    int b;    if (s == 0.0)    {      r = g = b = (unsigned char)(l * 255);      return StringToColor ((string)r + "," + (string)g + "," + (string)b);    }    else    {      double v1, v2;      double hue = (double)h / 360.0;      v2 = (l < 0.5) ? (l * (1.0 + s)) : ((l + s) - (l * s));      v1 = 2.0 * l - v2;      r = (unsigned char)(255 * HueToRGB (v1, v2, hue + (1.0 / 3.0)));      g = (unsigned char)(255 * HueToRGB (v1, v2, hue));      b = (unsigned char)(255 * HueToRGB (v1, v2, hue - (1.0 / 3.0)));      return StringToColor ((string)r + "," + (string)g + "," + (string)b);    }  }  //——————————————————————————————————————————————————————————————————————————————  //——————————————————————————————————————————————————————————————————————————————  double HueToRGB (double v1, double v2, double vH)  {    if (vH < 0) vH += 1;    if (vH > 1) vH -= 1;    if ((6 * vH) < 1) return (v1 + (v2 - v1) * 6 * vH);    if ((2 * vH) < 1) return v2;    if ((3 * vH) < 2) return (v1 + (v2 - v1) * ((2.0f / 3) - vH) * 6);    return v1;  }  //——————————————————————————————————————————————————————————————————————————————

为了将双精度数值从范围转换为颜色，采用了 HSL 转换为 RGB 的算法（MetaTrader 5 的颜色系统）。

测试基台在图表上显示一幅图像。 它被划分成两半。

• 测试函数显示在左侧。 其三维图形投影到平面上，其中红色表示最大值，而蓝色表示最小值。 显示点在群体中的位置（颜色对应于变量数在 40 和 1000 之间的测试函数的序号，两个变量的函数则不执行上色），坐标落于平均范围的点标记为白色，而最佳点标记为黑色。 
• 收敛图显示在右侧，拥有 2 个变量的测试函数标记为绿色，拥有 40 个变量的测试函数标记为蓝色，而拥有 1000 个变量的测试函数为红色。 每个测试运行五次（每种颜色的收敛图为 5 张）。 在此处，我们可以观察到 OA 的收敛性随变量数量增加而恶化的程度。

6. 使用 RNG 的简单 OA

我们实现最简单的搜索策略作为测试示例。 它没有实用价值，但它在某种程度上将成为比较优化算法的标准。 该策略经由 50/50 随机选择生成一组新的函数变量：既有从群体中随机选择的父集里复制的变量，亦有从最小/最大范围生成的变量。 收到测试函数的数值后，生成的新变量集将复制到群体的下半部分，并进行排序。 因此，新集合不断取代群体的一半物种，而最好的集合汇集到另一处。

下面是基于 RNG 的 OA 代码：

//+————————————————————————————————————————————————————————————————————————————+  class C_AO_RND  {    public: //||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||      struct ArrColony    {        double args [];    };      //----------------------------------------------------------------------------    double    A_RangeStep []; //Step ranges of genes    double    A_RangeMin  []; //Min ranges of genes    double    A_RangeMax  []; //Max ranges of genes      ArrColony S_Population []; //Population    ArrColony S_Colony     []; //Colony      double    A_FFpop [];      //Values of fitness of individuals in population    double    A_FFcol [];      //Values of fitness of individuals in colony      //----------------------------------------------------------------------------    // Initialization of algorithm    void F_Init (int argCount,       //Number of arguments                   int populationSize) //Population size    {      MathSrand ((int)GetMicrosecondCount ()); //reset of the generator        p_argCount  = argCount;      p_sizeOfPop = populationSize;      p_sizeOfCol = populationSize / 2;        p_dwelling  = false;        f_arrayInitResize (A_RangeStep, argCount, 0.0);      f_arrayInitResize (A_RangeMin,  argCount, 0.0);      f_arrayInitResize (A_RangeMax,  argCount, 0.0);        ArrayResize (S_Population, p_sizeOfPop);      ArrayResize (s_populTemp, p_sizeOfPop);      for (int i = 0; i < p_sizeOfPop; i++)      {        f_arrayInitResize (S_Population [i].args, argCount, 0.0);        f_arrayInitResize (s_populTemp [i].args, argCount, 0.0);      }        ArrayResize (S_Colony, p_sizeOfCol);      for (int i = 0; i < p_sizeOfCol; i++)      {        f_arrayInitResize (S_Colony [i].args, argCount, 0.0);      }        f_arrayInitResize (A_FFpop, p_sizeOfPop, -DBL_MAX);      f_arrayInitResize (A_FFcol, p_sizeOfCol, -DBL_MAX);        f_arrayInitResize (a_indexes, p_sizeOfPop, 0);      f_arrayInitResize (a_valueOnIndexes, p_sizeOfPop, 0.0);    }      //----------------------------------------------------------------------------    void F_EpochReset ()   //Reset of epoch, allows to begin evolution again without initial initialization of variables    {      p_dwelling = false;      ArrayInitialize (A_FFpop, -DBL_MAX);      ArrayInitialize (A_FFcol, -DBL_MAX);    }    //----------------------------------------------------------------------------    void F_Preparation ();  //Preparation    //----------------------------------------------------------------------------    void F_Sorting ();      //The settling of a colony in population and the subsequent sorting of population      private: //|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||    //----------------------------------------------------------------------------    void F_PopulSorting ();      //----------------------------------------------------------------------------    ArrColony          s_populTemp      []; //Temporal population    int                a_indexes        []; //Indexes of chromosomes    double             a_valueOnIndexes []; //VFF of the appropriate indexes of chromosomes      //----------------------------------------------------------------------------    template <typename T1>    void f_arrayInitResize (T1 &arr [], const int size, const T1 value)    {      ArrayResize     (arr, size);      ArrayInitialize (arr, value);    }      //----------------------------------------------------------------------------    double f_seInDiSp         (double In, double InMin, double InMax, double step);    double f_RNDfromCI        (double min, double max);    double f_scale            (double In, double InMIN, double InMAX, double OutMIN, double OutMAX);      //---Constants----------------------------------------------------------------    int  p_argCount;   //Quantity of arguments in a set of arguments    int  p_sizeOfCol;  //Quantity of set in a colony    int  p_sizeOfPop;  //Quantity of set in population    bool p_dwelling;   //Flag of the first settling of a colony in population  };  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  void C_AO_RND::F_Preparation ()  {    //if starts of algorithm weren't yet - generate a colony with random arguments    if (!p_dwelling)    {      for (int person = 0; person < p_sizeOfCol; person++)      {        for (int arg = 0; arg < p_argCount; arg++)        {          S_Colony [person].args [arg] = f_seInDiSp (f_RNDfromCI (A_RangeMin [arg], A_RangeMax [arg]),                                                      A_RangeMin  [arg],                                                      A_RangeMax  [arg],                                                      A_RangeStep [arg]);        }      }        p_dwelling = true;    }    //generation of a colony using with copying arguments from parent sets--------    else    {      int parentAdress = 0;      double rnd       = 0.0;      double argVal    = 0.0;        for (int setArg = 0; setArg < p_sizeOfCol; setArg++)      {        //get a random address of the parent set        parentAdress = (int)f_RNDfromCI (0, p_sizeOfPop - 1);          for (int arg = 0; arg < p_argCount; arg++)        {          if (A_RangeMin [arg] == A_RangeMax [arg]) continue;            rnd = f_RNDfromCI (0.0, 1.0);            if (rnd < 0.5)          {            S_Colony [setArg].args [arg] = S_Population [parentAdress].args [arg];          }          else          {            argVal = f_RNDfromCI (A_RangeMin [arg], A_RangeMax [arg]);            argVal = f_seInDiSp (argVal, A_RangeMin [arg], A_RangeMax [arg], A_RangeStep [arg]);              S_Colony [setArg].args [arg] = argVal;          }        }      }    }  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  void C_AO_RND::F_Sorting ()  {    for (int person = 0; person < p_sizeOfCol; person++)    {      ArrayCopy (S_Population [person + p_sizeOfCol].args, S_Colony [person].args, 0, 0, WHOLE_ARRAY);    }    ArrayCopy (A_FFpop, A_FFcol, p_sizeOfCol, 0, WHOLE_ARRAY);      F_PopulSorting ();  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  // Ranging of population.  void C_AO_RND::F_PopulSorting ()  {    //----------------------------------------------------------------------------    int   cnt = 1, i = 0, u = 0;    int   t0 = 0;    double t1 = 0.0;    //----------------------------------------------------------------------------      // We will put indexes in the temporary array    for (i = 0; i < p_sizeOfPop; i++)    {      a_indexes [i] = i;      a_valueOnIndexes [i] = A_FFpop [i];    }    while (cnt > 0)    {      cnt = 0;      for (i = 0; i < p_sizeOfPop - 1; i++)      {        if (a_valueOnIndexes [i] < a_valueOnIndexes [i + 1])        {          //-----------------------          t0 = a_indexes [i + 1];          t1 = a_valueOnIndexes [i + 1];          a_indexes [i + 1] = a_indexes [i];          a_valueOnIndexes [i + 1] = a_valueOnIndexes [i];          a_indexes [i] = t0;          a_valueOnIndexes [i] = t1;          //-----------------------          cnt++;        }      }    }      // On the received indexes create the sorted temporary population    for (u = 0; u < p_sizeOfPop; u++) ArrayCopy (s_populTemp [u].args, S_Population [a_indexes [u]].args, 0, 0, WHOLE_ARRAY);      // Copy the sorted array back    for (u = 0; u < p_sizeOfPop; u++) ArrayCopy (S_Population [u].args, s_populTemp [u].args, 0, 0, WHOLE_ARRAY);      ArrayCopy (A_FFpop, a_valueOnIndexes, 0, 0, WHOLE_ARRAY);  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  // Choice in discrete space  double C_AO_RND::f_seInDiSp (double in, double inMin, double inMax, double step)  {    if (in <= inMin) return (inMin);    if (in >= inMax) return (inMax);    if (step == 0.0) return (in);    else return (inMin + step * (double)MathRound ((in - inMin) / step));  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  // Random number generator in the custom interval.  double C_AO_RND::f_RNDfromCI (double min, double max)  {    if (min == max) return (min);    double Min, Max;    if (min > max)    {      Min = max;      Max = min;    }    else    {      Min = min;      Max = max;    }    return (double(Min + ((Max - Min) * (double)MathRand () / 32767.0)));  }  //——————————————————————————————————————————————————————————————————————————————    //——————————————————————————————————————————————————————————————————————————————  double C_AO_RND::f_scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX)  {    if (OutMIN == OutMAX) return (OutMIN);    if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));    else    {      if (In < InMIN) return (OutMIN);      if (In > InMAX) return (OutMAX);      return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);    }  }  //——————————————————————————————————————————————————————————————————————————————

7. 结果

AO	运行	Skin			Forest			Megacity (离散)			最终结果
		2 参数 (1 F)	40 参数 (20 F)	1000 参数 (500 F)	2 参数 (1 F)	40 参数 (20 F)	1000 参数 (500 F)	2 参数 (1 F)	40 参数 (20 F)	1000 参数 (500 F)
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

在测试基台上运行测试后，RND OA 的验证结果出乎意料。 该算法能够以非常高的精度查找两变量函数的最优值，而在 Forest 和 Megacity 的情况下，结果明显更差。 另一方面，我有关多变量函数搜索能力弱的推测也得到了确认。 在 40 个参数时，结果非常平庸。 最终累积值仅为 0.51254。

在随后的文章中，我将分析并测试众所周知、且被广泛运用的优化算法，并继续填写构成 OA 评级的结果表格。

附加的文件 |