群体优化算法：智能水滴（IWD）算法

MetaTrader 5 — 示例 | 26 六月 2024, 11:02

252

Andrey Dik

1.概述

河床是大自然最优雅的杰作之一，每一滴水都在其生命独特的舞蹈中扮演着自己的角色。每走一公里，河流都会形成新的边界，雄伟地散发出它的能量和智慧。就像这种自然现象一样，智能水滴优化算法利用自组织和粒子间相互作用的原理，努力实现其功能的和谐与完美。这种算法反映了大自然的宏伟及其创造和保持平衡的能力，使其成为优化和解决复杂问题的重要工具。

任何河流都有自己的河谷，这些河谷是在地表水和地下水的影响下由侵蚀过程形成的。这个河谷的最低部分，被河流切割成地面，被称为河床。河流的主要水流和底层沉积物都沿着它流动。

河床的起伏不断变化。被水俘获的石块和沙子会形成脊和裂隙，以尖角穿过河床。在弯道处，河流会冲刷出一条新路，形成牛轭湖 - 旧河道的一部分逐渐变成一个拥有自己生态系统的湖泊，最终干涸或变成沼泽。

当我们观察大自然中的河流时，我们会注意到它们的路径上有很多曲折。问题来了，为什么会出现这些转折，背后有什么逻辑或原因吗？如果是的话，我们能利用河流中出现的机制吗？我们能基于这些机制设计和开发智能算法吗？IWD算法试图对自然河流中发生的一些过程进行建模，然后将其作为一种算法来实现。

IWD 算法是群体智能领域中相对较新的算法之一。它模拟河流系统的动力学。IWD 是一种基于群体的算法，其中每个水滴代表一个解决方案，并且在搜索过程中共享水滴会产生更好的解决方案。

2007 年，伊朗科学家 Hamed Shah-Hosseini 开发了一种智能水滴行为算法。IWD 算法的特点是有几滴人造水滴，通过相互作用，它们能够改变环境，从而沿着阻力最小的路径找到最佳途径。IWD 算法是一种构造性的面向群体的优化算法。

2.算法

IWD 是一种模型，其中水滴通过改变河道来找到到达目的地的最佳路径。三个重要参数有助于实现这一目标。由于水滴自身的速度，它们能够从河底捕获土壤。速度越快，每一滴水滴所能携带的泥土量就越大，后面的水滴也就越能畅通无阻。在没有土壤需要清理的地方，流速会增加。最佳路径是包含最少土壤量的路径，其中可以达到最高速度。在 IWD 的帮助下，可以实现一种优化策略，其中随机代理以这样一种方式智能地相互作用，即它们共同改变河道并创建一条最优路径，在该路径中根本不会遇到土壤，并且代理的流速变得尽可能高。

基本原则

水滴更喜欢泥土较少的路径
当水滴从源头到目的地的途中被迫在几条路线中做出选择时，它更喜欢较短的路径。
路径的难易程度取决于路径上土壤的多少。土多的路难走，土少的路好走。

在自然界的河流中，可以观察到许多水滴，它们形成巨大的水团（水滴群）。自然河流流经的路径是由成群的水滴形成的。水滴群（河流）是环境的一部分，环境已被水滴群显著改变，未来也会发生变化。此外，环境本身对水滴的路径也有很大影响。它们面临着河岸的阻力。例如，构成硬土的环境部分比构成软土的环境部分对水滴群的阻力更大。河流的自然流向是水滴与环境竞争的结果，环境会阻碍水滴的运动。

水滴流入河流的特征之一是它的速度，另一个特征是土壤，每条河流都能承载一定量的土壤。就是这样，一滴水能够将一定量的土壤从一个地方输送到另一个地方。这种土壤会从快速颗粒转移到慢速颗粒。这意味着被湍急的水流带走的泥土会在水流缓慢的地方沉淀下来。

在这一转移时期，将发生三个明显的变化：

水滴速度增加
土壤中的饱和水滴增加
在这两点之间，河床中的土壤量减少

上文指出，每一滴水都有自己的速度。这种速度对河床中泥土的聚集起着直接作用。速度快的水滴比速度慢的水滴能带走更多的泥土。因此，与流速较慢的水滴相比，流速较快的水滴从河底带走的泥土更多。因此，土壤的清除与水滴的速度有关。

在土层较低的路径上，水滴的速度比在土层较高的路径上更快。因此，在泥土较少的路径上，流动的水滴可以收集到更多的泥土，并且速度也会更快；而在泥土较多的路径上，速度则会下降。

因此，在 IWD 算法中，水滴有两个主要特征：

speed（速度）
soil（土壤）

在算法运行过程中，这两种属性都可能发生变化。IWD 中的水滴从源头流向目的地，并以初始速度和地面零高度开始其旅程。水滴在移动过程中会经过一个环境，其中的一些泥土会被清除，水滴的速度也会增加。假定 IWD 是迭代进行的。水滴速度从当前位置到下一个位置的增加量与两个位置之间土壤的倒数成非线性比例：

vel = vel (t-1) + Av / [Bv + Cv * soil^2(i,j)]

其中：Av、Bv、Cv 是速度比（输入），而 soil(i,j) 是图顶点之间的土壤量。

因此，与土壤较多的路径相比，土壤较少的路径能让 IWD 水滴移动得更快。

IWD 水滴在环境中移动时会收集土壤。这些土壤将从连接两地的道路上清除。添加到 IWD 水滴中的土壤量与 IWD 从当前位置移动到下一个位置所需的时间成非线性比例。这个时间间隔是利用直线运动的简单物理定律计算出来的：

time(i,j,vel) = R / vel

其中 R 是两点之间的距离。

加到水滴中的土壤量：

dSoil(i,j) = As / [Bs + Cs * time(i,j,vel)]

其中：As、Bs 和 Cs 是 土壤内冲洗比。

各点之间路径上的新土壤量将如下所示：

soil (i+1,j+1) = Po * soil(i,j) + Pn * dSoil(i,j)

其中，Po 和 Pn 是改变土壤量的比率。

另外，移动时间与移动速度成反比，与两点之间的距离成正比。换句话说，土壤是环境信息的量化指标。这些公式决定了水滴选择低吸水路径而不是高吸水路径的偏好。这种路径选择是通过对可用路径进行均匀随机分布来实现的。选择下一条路径的概率与可用路径的土壤水平成反比。因此，初始水平较低的路径被 IWD 水滴选中的几率更高。

最初的 IWD 算法开发者是为了解决最优路径问题，如图搜索问题和旅行推销员问题。然而，这种算法并不适合解决我们在测试中要探讨的问题。因此，有必要调整 IWD 算法来解决我们的优化问题。相比之下，群体优化算法文章中描述的算法能够解决任何类型的问题，包括图搜索问题。前几篇文章已经介绍了一种类似的需要修改的高度专业化算法，即 "蚁群（Ant Colony，ACO）"。

要使 IWD 具备解决任何优化问题的能力，并使 IWD 能够在群体算法竞赛中胜出，首先必须确定如何应用土壤沉积和移动过程。我们不能沿用 ACO 算法中的方法，即信息素等同于适应度函数值。就 IWD 而言，土壤是一个动态参数，与适应度并不成正比。

于是产生了将坐标划分为若干区段的想法，类似于将河谷划分为面积相同的区段。其原理是，如果水滴（代理）的位置得到改善，那么沿所有坐标方向相应区域的土壤量就会减少。土壤的定量变化将根据所有水滴最后两次迭代的适应度函数变化差值来确定，即适应度变化的最大值和最小值之差。

水滴移动行为将基于随机选择土壤量最少的区域，即概率与相应区域的土壤量成正比。我们将在全局"河床"库中存储所有地区的最佳坐标。水滴选择一个区域后，将尝试改进存储区中的坐标，使新坐标的概率服从二次定律，即新坐标接近前一坐标的概率高于远离前一坐标的概率。新坐标所在区域的宽度由外部参数决定，以区域大小的一部分表示。图 1 显示了将坐标分解成区域的过程以及新坐标的概率分布。

iwd

图 1.将坐标划分为区域，以及在已知坐标附近选择新坐标的概率分布

根据上述规定和 IWD 算法的概念，我们可以按以下几个步骤组织伪代码：

随机生成水滴（第一次迭代）
计算 FF（适应度函数）
更新全局最佳结果
随机生成水滴（第二次迭代）
计算 FF（适应度函数）
更新全局最佳结果
计算每个水滴的高度变化（当前高度和之前高度）
按区域更新高度
新水滴（概率性地选择一个区域，在已知洞口附近滴下来）
计算 FF（适应度函数）
更新全局最佳结果
重复第 7 步

让我们继续分析代码。

将"水滴 "搜索代理表示为一个 S_Drop 结构，其中包含以下字段：

Init（int coords）：该函数以 "coords "坐标数为参数初始化一个结构对象。在该函数中，"c "和 "rSection "数组的大小会根据指定的坐标数发生变化。f"、"fPrev "和 "altChange "变量也已初始化
c: 用于存储坐标的数组
rSection：用于存储河流区域的数组
f：给定水滴的适应度指标
fPrev：先前的适应度值
altChange：高度的变化

struct S_Drop
{
  void Init (int coords)
  {
    ArrayResize (c,            coords);
    ArrayResize (rSection,     coords);
    f         = -DBL_MAX;
    fPrev     = -DBL_MAX;
    altChange = 0.0;
  }
  double c            []; //coordinates
  int    rSection     []; //river section          (number of cells: number of coordinates, cell value: sector index on the coordinate)
  double f;               //fitness
  double fPrev;           //previous fitness
  double altChange;       //change in altitude
};

我们需要一个存储空间来描述河流的情况（深度的最佳坐标以及深度本身），我们将该结构称为 S_Riverbed：

riverbedDepth：用于存储河床深度的数组，数组中单元格的数量与坐标上的区域数一致，每个单元格的值为相应区域的河床深度
coordOnSector：用于存储区域上最深处特定坐标的数组，数组中单元格的数量与坐标上的区域数相对应，每个单元格的值为相应区域上的坐标。

//——————————————————————————————————————————————————————————————————————————————
struct S_Riverbed //riverbed
{
  double riverbedDepth []; //riverbed depth 
  double coordOnSector []; //coordinate on the sector
};
//——————————————————————————————————————————————————————————————————————————————

让我们声明 C_AO_IWDm 类（m - modified - 表示已修改），它实现了一种基于水滴的人工优化算法。下面是每个类元素的说明：

类属性：

cB：用于存储最佳坐标的数组
fB：存储最佳坐标的目标函数值
p：颗粒（水滴）数组
"rangeMax"、"rangeMin "和 "rangeStep "数组用于定义搜索范围

类方法：

Init：用给定的参数初始化 C_AO_IWDm 类对象："coordsP" - 坐标数，"popSizeP" - 群体大小，"sectorNumberP" - 区域数，"waterViscosityP" - 水粘度。
Moving：移动水滴
Revision：对水滴状态进行修改

类的私有属性：

coords：坐标数
popSize：水滴数
sectorNumbe：区域数
waterViscosity：以区域面积为单位的水粘度比
sectorSpace：区域大小
rb：描述河床的坐标数组
iterationCounter
revision：表示需要修订的标志

类的私有方法：

SeInDiSp：以给定步长计算给定范围内的新坐标值
RNDfromCI：在给定区间内生成随机数
Scale：按指定范围缩放数字

//——————————————————————————————————————————————————————————————————————————————
class C_AO_IWDm
{
  //----------------------------------------------------------------------------
  public: double cB  [];       //best coordinates
  public: double fB;           //FF of the best coordinates
  public: S_Drop p   [];       //particles (drops)

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search

  public: void Init (const int    coordsP,          //coordinates number
                     const int    popSizeP,         //population size
                     const int    sectorsNumberP,   //sectors number
                     const double waterViscosityP); //water viscosity (>= 1)

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int    coords;           //coordinates number
  private: int    popSize;          //population size

  private: int    sectorsNumber;    //sectors number
  private: double waterViscosity;   //water viscosity
  private: double sectorSpace [];   //sector space
  private: S_Riverbed      rb [];   //riverbed

  private: int    iterationCounter;

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

Init 方法用指定的参数初始化 C_AO_IWDm 类对象：坐标数、水滴数、区域数、水粘度。

方法执行如下操作：

1.重置随机数生成器。
2.使用"-DBL_MAX "值初始化目标函数 "fB "的值
3.将迭代计数器置零
4.将 "coords "坐标数和 "popSize "人口数设置为给定值
5.将 "sectorsNumber "和 "waterViscosity "设置为指定值
6.将 "sectorSpace "数组的大小改为 "coord"。
7.将 "p "数组的大小改为 "popSize"，并初始化 "p "数组中的每个水滴
8.将 "rangeMax"、"rangeMin"、"rangeStep "和 "cB "数组大小更改为 "coods"。
9.将 "rb "数组的大小更改为 "coords"，并初始化 "rb "数组的每个元素，包括 "riverbedDepth "和 "coordOnSector "数组，将它们设置为默认值

//——————————————————————————————————————————————————————————————————————————————
void C_AO_IWDm::Init (const int    coordsP,          //coordinates number
                      const int    popSizeP,         //population size
                      const int    sectorsNumberP,   //sectors number
                      const double waterViscosityP)  //water viscosity (>= 1)
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB               = -DBL_MAX;
  iterationCounter = 0;

  coords  = coordsP;
  popSize = popSizeP;

  sectorsNumber  = sectorsNumberP;
  waterViscosity = waterViscosityP;
  ArrayResize (sectorSpace, coords);

  ArrayResize (p, popSize);
  for (int i = 0; i < popSize; i++) p [i].Init (coords);

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

  ArrayResize (rb,        coords);
  for (int i = 0; i < coords; i++)
  {
    ArrayResize     (rb [i].riverbedDepth, sectorsNumber);
    ArrayResize     (rb [i].coordOnSector, sectorsNumber);
    ArrayInitialize (rb [i].riverbedDepth, 0.0);
    ArrayInitialize (rb [i].coordOnSector, -DBL_MAX);
  }
}
//——————————————————————————————————————————————————————————————————————————————

让我们来看看 Moving() 方法的各个部分。

该代码块仅在第一和第二次迭代中执行。它为每个坐标计算并设置每个 "sectorSpace" 区域的大小。区域大小由 "rangeMax - rangeMin" 值范围除以 "sectorNumber" 区域数决定。

然后，根据均匀分布的指定范围内的随机值对水滴进行初始化。

//----------------------------------------------------------------------------
  if (iterationCounter == 0)
  {
    for (int i = 0; i < coords; i++) sectorSpace [i] = (rangeMax [i] - rangeMin [i]) / sectorsNumber;
  }

  //1,4-------------------------------------------------------------------------
  if (iterationCounter == 0 || iterationCounter == 1)
  {
    double min = 0.0;
    double max = 0.0;
    int    s   = 0;

    for (int i = 0; i < popSize; i++)
    {
      p [i].fPrev = p [i].f;

      for (int c = 0; c < coords; c++)
      {
        s = (int)(RNDfromCI (0, sectorsNumber));
        if (s >= sectorsNumber) s = sectorsNumber - 1;

        p [i].rSection [c] = s;

        min = rangeMin [c] + sectorSpace [c] * s;
        max = min + sectorSpace [c];

        p [i].c [c] =  SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    for (int i = 0; i < popSize; i++) p [i].fPrev = p [i].f;

    return;
  }

然后，代码片段会计算并规范化群体中每个水滴的 altChange 值。这段代码中唯一的微妙之处是检查高度的最大和最小变化是否相等，以避免除以 "0"。在这种情况下，我们假设水滴的高度没有变化。

每个水滴的 "altChange "值都是作为规范化值计算的，规范化值的范围是 0 到 1。将 "altChange "减去 "minAltChange"，再将结果除以 "maxAltChange "和 "minAltChange "之差，就完成了规范化。

//7---------------------------------------------------------------------------
double maxAltChange = -DBL_MAX;
double minAltChange =  DBL_MAX;
double altChange    = 0.0;
double randSC       = 0.0; //random selection component
double maxRC        = 0.0;
double nowRC        = 0.0;
int    indSector    = 0;

for (int i = 0; i < popSize; i++)
{
  altChange = fabs (p [i].f - p [i].fPrev);
  p [i].altChange = altChange;
  if (altChange < minAltChange) minAltChange = altChange;
  if (altChange > maxAltChange) maxAltChange = altChange;
}

if (minAltChange == maxAltChange)
{
  for (int i = 0; i < popSize; i++)
  {
    p [i].altChange = 0.0;
  }
}
else
{
  for (int i = 0; i < popSize; i++)
  {
    altChange = p [i].altChange;
    p [i].altChange = (altChange - minAltChange) / (maxAltChange - minAltChange);
  }
}

下面的代码片段会更新每个坐标的河床深度，前提是当前的适应度函数值大于相应水滴的上一个值。这样，我们就能考虑到高度的变化并影响河床的形状。因此，每当水滴的位置有所改善，我们就会认为河床发生了变化。

//8---------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    if (p [i].f > p [i].fPrev)
    {
      for (int c = 0; c < coords; c++)
      {
        rb [c].riverbedDepth [p [i].rSection [c]] += p [i].altChange;
      }
    }
  }

下面的代码片段执行了两个基本操作，以更改提供搜索策略的代理的坐标：

一个水滴从群体中随机选择另一个水滴，并从它那里借用区域编号，这样就确保了算法的组合特性
水滴按照每个河段的已知深度比例随机选择一个河段

选定区域后，如果该区域是从另一个水滴中提取的，我们就为该水滴生成一个新坐标，该坐标采用均匀分布；如果该扇形是从河床中存储的信息中提取的，则采用二次函数分布。每个坐标的结果值都会进入可接受范围。

//9---------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      n = (int)(RNDfromCI (0, popSize));
      if (n >= popSize) n = popSize - 1;

      if (p [n].f > p [i].f)
      {
        p [i].rSection [c] = p [n].rSection [c];

        min = rangeMin [c] + sectorSpace [c] * p [i].rSection [c];
        max = min + sectorSpace [c];

        p [i].c [c] = SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]);
      }
      else
      {
        randSC = RNDfromCI (0.0, 1.0);

        nowRC = rb [c].riverbedDepth [0] * randSC;
        maxRC = nowRC;
        indSector = 0;

        for (int r = 1; r < sectorsNumber; r++)
        {
          nowRC = rb [c].riverbedDepth [r] * randSC;
          if (nowRC > maxRC)
          {
            maxRC     = nowRC;
            indSector = r;
          }
        }

        if (rb [c].coordOnSector [indSector] == -DBL_MAX)
        {
          min = rangeMin [c] + sectorSpace [c] * indSector;
          max = min + sectorSpace [c];

          p [i].c [c] = RNDfromCI (min, max);
        }
        else
        {
          double x = RNDfromCI (-1.0, 1.0);
          double y = x * x;
          double pit = 0.0;

          double dif = Scale (y, 0.0, 1.0, 0.0, sectorSpace [c] * waterViscosity, false);

          pit = rb [c].coordOnSector [indSector];
          pit += x > 0.0 ? dif : -dif;

          p [i].c [c] = pit;
        }

        min = rangeMin [c] + sectorSpace [c] * indSector;
        max = min + sectorSpace [c];

        p [i].c [c] = SeInDiSp (p [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
        p [i].rSection [c] = indSector;
      }
    }
  }

接下来，如果目标函数 "f "的当前值大于之前的值，我们就会更新每个水滴之前的适应度值 "fPrev"。这样，我们就能跟踪目标函数的变化，并在算法中利用这些信息做出选择下一步的决策。

for (int i = 0; i < popSize; i++)
  {
    if (p [i].f > p [i].fPrev)
    p [i].fPrev = p [i].f;
  }

最后，让我们来看看 Revision 方法。它设计用于更新最佳解决方案 "cB "和相应的适应度函数值。如果在当前迭代中找到了更好的解决方案，我们就会保存相应区域的坐标。因此，河床会记住每个坐标上每个区域中最深的地方。在这个方法中，我们将迭代计数器 "iterationCounter "增加一，这样在 Moving 方法中，我们就可以继续执行与迭代相对应的操作。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_IWDm::Revision ()
{
  //3,6,11----------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    if (p [i].f > fB)
    {
      fB = p [i].f;
      ArrayCopy (cB, p [i].c, 0, 0, WHOLE_ARRAY);

      for (int c = 0; c < coords; c++)
      {
        rb [c].coordOnSector [p [i].rSection [c]] = p [i].c [c];
      }
    }
    else
    {
      for (int c = 0; c < coords; c++)
      {
        if (rb [c].coordOnSector [p [i].rSection [c]] == -DBL_MAX)
        {
          rb [c].coordOnSector [p [i].rSection [c]] = p [i].c [c];
        }
      }
    }
  }

  iterationCounter++;
}
//——————————————————————————————————————————————————————————————————————————————

3.修改版 SDSm

我们稍后将探讨 IWDm 算法的结果，但这些结果促使我们产生了改进另一种算法的想法，即评级中的最佳算法--SDS，因为 IWDm 和 SDS 都使用类似的实体（分别是区域和餐馆）。在 IWD 中使用的方法，即使用四元概率分布进行位置细化，有助于使 SDS 更好：最佳位置细化方法对最终测试结果有很大影响。唯一不同的是，在 SDSm 中，如果配送到邻近的餐厅，配送就会被截断。

对 SDS 算法的 Revision 方法进行了修改，由于餐厅内新坐标的分布（以前是均匀分布）和测试结果发生了重大变化，该算法被赋予了 "m "指数。

在代码中，我们可以看到 Research 函数现在负责随机变量的分布，它的参数包括分布宽度比、餐厅地址、餐厅大小、沿坐标可能的最小值、沿坐标的步长、上一步的适应度以及我们要改进的坐标。

在 SDSm 算法中，我们尝试改进三种坐标（餐馆中的菜肴）：

最佳候选者坐标
随机选择的餐厅中的最佳坐标（就像 IWDm 中的河床一样，在 SDSm 中，我们存储了所有餐厅的最佳坐标 - 这就像存储了一份城市中所有餐厅的最佳菜肴列表）
我们自己的相应餐厅的坐标

概率分布宽度的比率可以包含在外部参数中，但我没有这样做，我认为这样设置的值是最好的。

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDSm::Revision ()
{
  /*
  here is the old code, no changes
  */

  for (int i = 0; i < populationSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      n = (int)(RNDfromCI (0, populationSize));
      if (n >= populationSize) n = populationSize - 1;

      if (cands [n].fPrev > cands [i].fPrev)
      {
        cands [i].raddr [c] = cands [n].raddrPrev [c];

        Research (0.25,
                  cands     [i].raddr [c],
                  restSpace [c],
                  rangeMin  [c],
                  rangeStep [c],
                  cands     [n].cPrev [c],
                  cands     [i].c     [c]);
      }
      else
      {
        rnd = RNDfromCI (0.0, 1.0);

        if (rnd < probabRest)
        {
          n = (int)(RNDfromCI (0, restNumb));
          if (n >= restNumb) n = restNumb - 1;
          cands [i].raddr [c] = n;

          Research (1.0,
                    cands     [i].raddr         [c],
                    restSpace [c],
                    rangeMin  [c],
                    rangeStep [c],
                    rb        [c].coordOnSector [n],
                    cands     [i].c             [c]);
        }
        else
        {
          cands [i].raddr [c] = cands [i].raddrPrev [c];

          Research (0.25,
                    cands     [i].raddr [c],
                    restSpace [c],
                    rangeMin  [c],
                    rangeStep [c],
                    cands     [i].cPrev [c],
                    cands     [i].c     [c]);
        }
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

这就是 "神奇 "的 "Research" 函数，它使之前的测试领先者提高了 12% 以上。

该函数完成如下任务：

生成一个范围为 [-1.0;1.0] 的随机数、
得出的数值会根据餐厅的大小使用分配系数按比例递增
添加到当前的升级坐标
餐厅边界的确定
按照优化参数的步骤，将数字转换为可接受的值，并沿餐厅边界进行修剪

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDSm::Research (const double  ko,
                          const int     raddr,
                          const double  restSpaceI,
                          const double  rangeMinI,
                          const double  rangeStepI,
                          const double  pitOld,
                          double       &pitNew)
{
  double x = RNDfromCI(-1.0, 1.0);
  double y = x * x;
  double pit = pitOld;
  double min = 0.0;
  double max = 0.0;

  double dif = Scale(y, 0.0, 1.0, 0.0, restSpaceI * ko, false);

  pit += x > 0.0 ? dif : -dif;

  min = rangeMinI + restSpaceI * raddr;
  max = min + restSpaceI;

  pitNew = SeInDiSp (pit, min, max, rangeStepI);
}
//——————————————————————————————————————————————————————————————————————————————

4.测试结果

IWD 试验台结果：

C_AO_IWDm:50;10;3.0
=============================
5 Rastrigin's; Func runs 10000 result:63.304838882364926
Score:0.78438
25 Rastrigin's; Func runs 10000 result:49.20424466627239
Score:0.60967
500 Rastrigin's; Func runs 10000 result:39.68464591598694
Score:0.49172
=============================
5 Forest's; Func runs 10000 result:0.6975685023058024
Score:0.39458
25 Forest's; Func runs 10000 result:0.19878497533879688
Score:0.11244
500 Forest's; Func runs 10000 result:0.0569274044494088
Score:0.03220
=============================
5 Megacity's; Func runs 10000 result:3.44
Score:0.28667
25 Megacity's; Func runs 10000 result:1.088
Score:0.09067
500 Megacity's; Func runs 10000 result:0.28480000000000005
Score:0.02373
=============================
All score:2.82606

不客气地说，对比表中的结果低于平均水平。

SDSm 试验台结果：

C_AO_SDSm:100;100;0.05
=============================
5 Rastrigin's; Func runs 10000 result:80.65976429448276
Score:0.99942
25 Rastrigin's; Func runs 10000 result:79.95659847225565
Score:0.99071
500 Rastrigin's; Func runs 10000 result:57.23107170601535
Score:0.70913
=============================
5 Forest's; Func runs 10000 result:1.7241883676504082
Score:0.97529
25 Forest's; Func runs 10000 result:1.497160007591401
Score:0.84687
500 Forest's; Func runs 10000 result:0.29481739063639945
Score:0.16676
=============================
5 Megacity's; Func runs 10000 result:10.559999999999999
Score:0.88000
25 Megacity's; Func runs 10000 result:6.824000000000001
Score:0.56867
500 Megacity's; Func runs 10000 result:1.2384
Score:0.10320
=============================
All score:6.24004

SDSm 的成果确实令人印象深刻。

IWDm 算法的可视化动画显示出一定程度的聚类潜在良好搜索区域的能力，这在 Rastrigin 函数中尤为明显。但收敛图中的长平段显示了算法有明显卡住的地方。

rastrigin

Rastrigin 测试函数上的 IWDm。

forest

Forest 测试函数上的 IWDm。

megacity

Megacity 测试函数上的 IWDm。

本文对 IWDm 算法进行了研究，该算法在 22 种算法中排名第 19 位，即倒数第 4 位，超过了著名的 PSO 算法。IWDm 在平滑函数上显示出最佳效果。所有三个测试函数的收敛图都在持续改善，这给人们带来了希望，即随着迭代次数的增加，算法将继续收敛，但其使用的实际意义和便利性也随之消失。测试条件非常严格，必须迭代 10,000 次，不能多也不能少。

此外，值得注意的是，修改后的 SDSm 算法在 9 个可能的第一名中占据了 7 个。该算法是优化算法中名副其实的 "全能选手"。与传统的 SDS 相比，SDSm 在 "尖锐"的 Forest 函数和复杂的离散 Megacity 函数上的结果改进尤为明显（在后一种函数上，使用 1000 个参数，改进幅度接近 30%）。因此，除了文章的主题 "IWD"之外，我们还看到了一位新的贵宾 - SDSm。您可以在这里观看 SDS 运行动画。要了解 SDSm 是如何工作的，请运行 SDS 文件夹中存档的测试脚本。

#	AO	描述	Rastrigin			Rastrigin 最终	Forest			Forest 最终	Megacity (discrete)			Megacity 最终	最终结果
#	AO	描述	10 p（5 F）	50 p（25 F）	1000 p（500 F）	Rastrigin 最终	10 p（5 F）	50 p（25 F）	1000 p（500 F）	Forest 最终	10 p（5 F）	50 p（25 F）	1000 p（500 F）	Megacity 最终	最终结果
1	SDSm	随机扩散搜索 M（stochastic diffusion search M）	0.99809	1.00000	0.69149	2.68958	1.00000	1.00000	1.00000	3.00000	1.00000	1.00000	1.00000	3.00000	100.000
2	SDS	随机扩散搜索（stochastic diffusion search）	0.99737	0.97322	0.58904	2.55963	0.96778	0.93572	0.79649	2.69999	0.78696	0.93815	0.71804	2.44315	88.208
3	SSG	树苗播种和生长（saplings sowing and growing）	1.00000	0.92761	0.51630	2.44391	0.72654	0.65201	0.83760	2.21615	0.54782	0.61841	0.99522	2.16146	77.678
4	HS	和声搜索（harmony search）	0.99676	0.88385	0.44686	2.32747	0.99882	0.68242	0.37529	2.05653	0.71739	0.71842	0.41338	1.84919	70.647
5	IWO	入侵性杂草优化（invasive weed optimization）	0.95828	0.62227	0.27647	1.85703	0.70690	0.31972	0.26613	1.29275	0.57391	0.30527	0.33130	1.21048	48.267
6	ACOm	蚁群优化M（ant colony optimization M）	0.34611	0.16683	0.15808	0.67103	0.86785	0.68980	0.64798	2.20563	0.71739	0.63947	0.05579	1.41265	47.419
7	MEC	思维进化计算（mind evolutionary computation）	0.99270	0.47345	0.21148	1.67763	0.60691	0.28046	0.21324	1.10061	0.66957	0.30000	0.26045	1.23002	44.061
8	COAm	布谷鸟优化算法 M（cuckoo optimization algorithm M）	0.92400	0.43407	0.24120	1.59927	0.58309	0.23477	0.13842	0.95629	0.52174	0.24079	0.17001	0.93254	37.845
9	FAm	萤火虫算法 M（firefly algorithm M）	0.59825	0.31520	0.15893	1.07239	0.51012	0.29178	0.41704	1.21894	0.24783	0.20526	0.35090	0.80398	33.152
10	ABC	人工蜂群（artificial bee colony）	0.78170	0.30347	0.19313	1.27829	0.53774	0.14799	0.11177	0.79750	0.40435	0.19474	0.13859	0.73768	29.784
11	BA	蝙蝠算法（bat algorithm）	0.40526	0.59145	0.78330	1.78002	0.20817	0.12056	0.21769	0.54641	0.21305	0.07632	0.17288	0.46225	29.488
12	CSS	带电系统搜索（charged system search）	0.56605	0.68683	1.00000	2.25289	0.14065	0.01853	0.13638	0.29555	0.07392	0.00000	0.03465	0.10856	27.914
13	GSA	重力搜索算法（gravitational search algorithm）	0.70167	0.41944	0.00000	1.12111	0.31623	0.25120	0.27812	0.84554	0.42609	0.25525	0.00000	0.68134	27.807
14	BFO	细菌觅食优化（bacterial foraging optimization）	0.67203	0.28721	0.10957	1.06881	0.39655	0.18364	0.17298	0.75317	0.37392	0.24211	0.18841	0.80444	27.549
15	EM	类电磁算法（electroMagnetism-like algorithm）	0.12235	0.42928	0.92752	1.47915	0.00000	0.02413	0.29215	0.31628	0.00000	0.00527	0.10872	0.11399	18.981
16	SFL	混合蛙跳（shuffled frog-leaping）	0.40072	0.22021	0.24624	0.86717	0.20129	0.02861	0.02221	0.25211	0.19565	0.04474	0.06607	0.30646	13.201
17	MA	猴子算法（monkey algorithm）	0.33192	0.31029	0.13582	0.77804	0.10000	0.05443	0.07482	0.22926	0.15652	0.03553	0.10669	0.29874	11.771
18	FSS	鱼群搜索（fish school search）	0.46812	0.23502	0.10483	0.80798	0.12825	0.03458	0.05458	0.21741	0.12175	0.03947	0.08244	0.24366	11.329
19	IWDm	智能水滴 M（intelligent water drops M）	0.26459	0.13013	0.07500	0.46972	0.28568	0.05445	0.05112	0.39126	0.22609	0.05659	0.05054	0.33322	10.434
20	PSO	粒子群优化（particle swarm optimisation）	0.20449	0.07607	0.06641	0.34696	0.18873	0.07233	0.18207	0.44313	0.16956	0.04737	0.01947	0.23641	8.431
21	RND	随机（random）	0.16826	0.09038	0.07438	0.33302	0.13480	0.03318	0.03949	0.20747	0.12175	0.03290	0.04898	0.20363	5.056
22	GWO	灰狼优化器（grey wolf optimizer）	0.00000	0.00000	0.02093	0.02093	0.06562	0.00000	0.00000	0.06562	0.23478	0.05789	0.02545	0.31812	1.000

总结

最初的 IWD 算法是作者开发用于解决寻找最短路径的问题的，如运输物流、网络路由和寻找地理信息系统中的最优路径。这篇文章并没有考察其在这些特定任务中的能力和性能，而作为通用算法提出的新的改进型 IWDm 算法也未能显示出令人印象深刻的结果。遗憾的是，增加区域数量并没有提高算法的效率。

然而，IWDm 算法的运行给我留下的感觉是，这一优雅算法的全部潜力尚未得到充分发挥。根据河床土壤运动模型，将搜索空间划分为若干区域并探讨其等级的想法似乎非常有趣。结果表明，这种类似的方法，例如存储每家餐厅的最佳菜肴，还有或许使用新点在前一个点附近的概率偏差，大大提高了 SDS 算法的性能。

如果我们增加新 SDSm 中餐厅的数量（默认参数为 100），并将坐标划分为更小的区域（SDS 参数为 1000），结果就会变得更糟。这意味着，采用这种方法后，单个餐厅的选择变得更加重要，而餐厅附近的特定点则不再重要（算法变成了普通的 SDS）。这意味着二次概率分布对坐标上一定大小的区域具有最大的影响。这是算法中各种方法之间的一种平衡，这些方法的目标各不相同。

从这篇文章中得到的最重要的启示是，我们不可能确切地说，个别搜索策略中使用的哪种方法最好或最差。使用不同的方法既能使某些算法变差，也能显著改善其他算法。重要的是优化算法中使用的方法组合，而不是方法本身。