跨邻域搜索(ANS)
1. 概述
在当今世界,开发高效的优化方法对于解决从工程应用到机器学习以及人工智能领域科学研究中的各种问题起着重要的作用。在此背景下,元启发式进化算法是解决复杂优化问题的强大工具。然而,为了进一步提高其性能和效率,需要不断开发和改进现有方法,并开发新的算法。
在本文中,我将介绍一种在2014年由郭华武提出的优化算法——跨邻域搜索(ANS),该算法是基于数值优化的群体搜索方法。所开发的ANS算法在优化领域迈出了重要一步,有望以高效和准确的方式解决现实世界中的各种问题。我们将在下文验证其真实性。ANS的基本思想是对多智能体系统的行为进行建模,其中每个智能体在解空间中移动,与其邻居进行交互并交换信息。该方法通过将局部优化和全局优化相结合,实现了对搜索空间的良好探索。
我们将详细了解ANS算法的结构及其工作原理,并与现有的优化方法进行比较分析。所开发的ANS算法为优化领域开辟了新天地,使我们能够以高性能解决更多领域的问题。此外,在人工智能发展的背景下,值得注意的是,ANS算法是向创建更加灵活和智能的优化方法迈出的重要一步,使其能够考虑到问题的具体情况和环境的动态变化。
2. 算法实现
跨邻域搜索(ANS)算法是一种优化方法,它借鉴了进化算法和元启发式算法领域的思想,旨在问题参数空间中寻找最优解。
让我们标注ANS的主要特点:
- 邻域搜索 - 智能体探索当前解的邻域,这使他们能够更高效地找到局部最优解。
- 使用正态分布 - ANS使用正态分布来生成新的参数值。
- 解集合 - ANS使用最佳解的集合,这有助于算法同时向多个有前景的方向定位。
在ANS中,一组个体共同搜索解空间,以最优方式解决所考虑的优化问题。该算法的基本思想是维护和动态更新个体迄今为止找到的一组最优解。在每一代中,个体根据正态分布直接在邻域中搜索几个不同的解。通过这种方式,利用了同时拥有多个潜在优秀解的理念,因为事先不知道哪个解会是最优的。
下面我们将根据作者提出的概念,考虑ANS算法的完整描述,包括方程和阶段。ANS执行以下步骤:
1. 参数初始化:
- 种群规模m
- 最优解集合c
- 高斯分布的标准差sigma
- 搜索空间维度D
- 最大迭代次数MaxG
2. 种群初始化。在搜索空间中随机初始化种群中每个个体的位置。
3. 更新最优解。种群中的每个个体通过探索最优解集合中解的邻域(使用正态分布)来更新其当前位置。
4. 选择搜索坐标。选择n个随机数(跨搜索角度)来确定个体在解空间中当前位置的坐标。
5. 更新个体位置。根据上一步的结果更新个体i的位置。
方程与运算:
1. 更新第i个个体的位置pos_i(探索集合中解的邻域):
- 使用高斯分布更新个体i的位置:pos_i = r_g + G (r_g - pos_i),其中:
- G - 来自高斯分布的随机值
- r_g - 集合中最优解的位置
2. 更新第i个个体的位置pos_i(探索个体自身最优解的邻域):
- 使用高斯分布更新个体i的位置:pos_i = r_i + G (r_i - pos_i),其中:
- G - 来自高斯分布的随机值
- r_i - 个体最优解的位置
3. 更新最优解集合:
- 根据个体的新位置更新最优解集合。
因此,这些方程反映了在个体最优解r_i的邻域以及其他最优解r_g(来自R集合)的邻域中搜索第i个个体的机制。这些算法步骤代表了用于解决优化问题的ANS方法的基本逻辑。它包括参数初始化、个体位置的随机初始化、根据最优解的邻域更新个体位置以及更新最佳解集合。算法将持续运行,直到满足停止条件为止。
基于最优解或个体的搜索是群体策略算法中常见且频繁使用的搜索方法,尽管不同优化算法实现这种搜索机制的过程可能有所不同。在这种情况下,除了主要的智能体群体之外,还引入了一个新的群体——最优解集合(潜在的搜索方向)。该集合的大小由算法的外部参数定义,并且规模可以比主要群体小或大。
ANS算法中的搜索策略从填充最优解的集合开始,然后继续在集合中最佳解的邻域以及每个个体的最佳个体解的邻域中进行搜索。标准差sigma的大小在算法中起着关键作用。较小的sigma值令搜索空间的领域更广,而较高的值则通过缩小邻域范围来精炼解。此算法参数负责搜索强化和多样化之间的平衡。部分算法将这一平衡与当前迭代次数相关联,以允许在探索和精炼之间的平衡上实现动态变化,但在本例中,作者将平衡调整定义作为ANS的外部参数。
因此,ANS算法结合了对已发现最优解的利用(通过在其邻域内进行搜索)和对解空间的探索(通过在个体自身最优解的邻域内进行搜索)。从理论上讲,应该在搜索强化和多样化之间提供良好的平衡。
现在让我们继续编写和解析ANS算法的代码。定义S_ANS_Agent结构,该结构将用于表示ANS算法中的智能体。结构字段:
- c - 用于存储智能体坐标的数组。
- cBest- 用于存储最优智能体坐标的数组。
- f - 智能体的适应度值。
- fBest - 智能体的最优适应度值。
- Init(int coords) - 初始化方法,用于设置c和cBest数组的大小,并初始化f和fBest的值。
这部分代码代表了智能体的基本结构。智能体数组将代表ANS算法中的主要群体。
//—————————————————————————————————————————————————————————————————————————————— struct S_ANS_Agent { double c []; //coordinates double cBest []; //best coordinates double f; //fitness double fBest; //best fitness void Init (int coords) { ArrayResize (c, coords); ArrayResize (cBest, coords); f = -DBL_MAX; fBest = -DBL_MAX; } }; //—————————————————————————————————————————————————————————————————————————————
为了描述一组最优解决方案,我们设定结构S_Collection,该结构将用于存储搜索空间中最优坐标及其相应的适应度值的信息。该结构包含以下字段:
- c - 用于存储坐标的数组。
- f - 集合中针对某一给定问题的解决方案的适应度值。
- Init(int coords) - 初始化方法,该方法设置c数组的大小,并将f的初始值设定为double类型可能的最小值。
//—————————————————————————————————————————————————————————————————————————————— struct S_Collection { double c []; //coordinates double f; //fitness void Init (int coords) { ArrayResize (c, coords); f = -DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
声明一个名为C_AO_ANS的类,该类继承自基类C_AO并实现了ANS算法。以下是一些关键点:
- ao_name, ao_desc, ao_link - 描述ANS算法的属性。
- popSize - 种群规模。
- collectionSize, sigma, range, collChoiceProbab - ANS算法参数。
- SetParams() - 用于设置参数的方法。
- Init(), Moving(), Revision() - 用于初始化、移动智能体以及更新种群和解决方案集合的方法。
- S_ANS_Agent, S_Collection - 用于存储代理数据和集合的结构。
//—————————————————————————————————————————————————————————————————————————————— class C_AO_ANS : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_ANS () { } C_AO_ANS () { ao_name = "ANS"; ao_desc = "Across Neighbourhood Search"; ao_link = "https://www.mql5.com/en/articles/15049"; popSize = 50; //population size collectionSize = 20; //Best solutions collection sigma = 3.0; //Form of normal distribution range = 0.5; //Range of values dispersed collChoiceProbab = 0.8; //Collection choice probab ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "collectionSize"; params [1].val = collectionSize; params [2].name = "sigma"; params [2].val = sigma; params [3].name = "range"; params [3].val = range; params [4].name = "collChoiceProbab"; params [4].val = collChoiceProbab; } void SetParams () { popSize = (int)params [0].val; collectionSize = (int)params [1].val; sigma = params [2].val; range = params [3].val; } bool Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0); //number of epochs void Moving (); void Revision (); //---------------------------------------------------------------------------- int collectionSize; //Best solutions collection double sigma; //Form of normal distribution double range; //Range of values dispersed double collChoiceProbab; //Collection choice probab S_ANS_Agent agent []; private: //------------------------------------------------------------------- S_Collection coll []; S_Collection collTemp []; }; //——————————————————————————————————————————————————————————————————————————————
Init方法用于初始化ANS算法的参数。
- rangeMinP、rangeMaxP、rangeStepP - 分别代表搜索范围的最小值、最大值和步长的数组。
- epochsP - 迭代次数(代数)。
对于该方法而言:
- 使用StandardInit检查标准参数是否成功初始化。
- 创建智能体(agent)和集合(coll)数组(用于存储最优解决方案的第二种群),以及collTemp(用于排序集合的临时数组)。
- 对于每个智能体和集合,都通过调用Init方法来设置初始值。
该方法在准备ANS算法执行优化任务中起着重要作用。值得注意的是,coll和collTemp数组大小被初始化为collectionSize参数的两倍。这样做是为了将新添加到集合中的智能体置于数组的后半部分。随后的排序操作在整个集合上进行,但只有包含最优智能体的前半部分被用于后续工作。
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_ANS::Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0) //number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- ArrayResize (agent, popSize); for (int i = 0; i < popSize; i++) agent [i].Init (coords); ArrayResize (coll, collectionSize * 2); ArrayResize (collTemp, collectionSize * 2); for (int i = 0; i < collectionSize * 2; i++) { coll [i].Init (coords); collTemp [i].Init (coords); } return true; } //——————————————————————————————————————————————————————————————————————————————
在ANS算法中,Moving方法负责实现智能体的移动(位移)。让我们更详细地看一下这段代码:
1. 初始化(如果revision等于false):
- 如果这是第一步(第一个周期),那么对于每个智能体:
- 在rangeMin[c]到rangeMax[c]的范围内生成一个名为val的随机值。
- 应用SeInDiSp操作符考虑步长rangeStep[c]。
- 将val值赋给智能体的agent[i].c[c]坐标。
- 同样,将val值赋给智能体的最优坐标agent[i].cBest[c](在此阶段,智能体的适应度值是未知的,所以最优坐标等于当前的初始坐标)。
- 将val值也赋给智能体数组中的a[i].c[c]。
2. 如果revision等于true,则智能体的移动方式如下:
- 对于每个智能体及其每个坐标:
- 如果生成的随机数小于collChoiceProbab,则从集合中随机选择一个解决方案:
- 从集合中随机选择一个索引ind(直到找到一个非空的解决方案为止)。
- 从当前智能体的坐标中获取p值。
- 从集合中选定的解决方案中获取r值。
- 否则,使用最佳智能体坐标:
- 从当前智能体的坐标中获取p值。
- 从最佳智能体坐标中获取r值。
- 计算移动所需的dist距离以及(min和max)范围。
- min和max值被限制在rangeMin[c]和rangeMax[c]范围内。
- 使用r、min、max和sigma参数的正态分布。
- 将val值赋给智能体的agent[i].c[c]坐标。
- 将val值赋给智能体的agent[i].c[c]坐标。
该代码段用于更新ANS算法中智能体的坐标,同时考虑了智能体的最优坐标以及集合中的解决方案。
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ANS::Moving () { double val = 0.0; //---------------------------------------------------------------------------- if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { val = u.RNDfromCI (rangeMin [c], rangeMax [c]); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); agent [i].c [c] = val; agent [i].cBest [c] = val; a [i].c [c] = val; } } revision = true; return; } //---------------------------------------------------------------------------- double min = 0.0; double max = 0.0; double dist = 0.0; int ind = 0; double r = 0.0; double p = 0.0; for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < collChoiceProbab) { do ind = u.RNDminusOne (collectionSize); while (coll [ind].f == -DBL_MAX); p = agent [i].c [c]; r = coll [ind].c [c]; } else { p = agent [i].c [c]; r = agent [i].cBest [c]; } dist = fabs (p - r) * range; min = r - dist; max = r + dist; if (min < rangeMin [c]) min = rangeMin [c]; if (max > rangeMax [c]) max = rangeMax [c]; val = u.GaussDistribution (r, min, max, sigma); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); agent [i].c [c] = val; a [i].c [c] = val; } } } //——————————————————————————————————————————————————————————————————————————————
将Revision方法用于ANS算法中修订(更新)智能体和集合。以下是其关键点:
- 方法的第一部分:搜索一个适应度优于全局解决方案(其适应度为fB)的智能体,并将其坐标保存到数组cB中。
- 方法的第二部分:基于智能体的当前适应度a[i].f更新每个智能体的最优坐标agent[i].cBest。
- 方法的第三部分:根据代理的最佳坐标更新集合coll。
- 对集合进行排序。
该方法在算法执行过程中对于更新智能体和解决方案集合起着重要作用。智能体群体被置于集合的第二部分,对集合进行排序后,使用包含最优解决方案的前半部分的集合。
//—————————————————————————————————————————————————————————————————————————————— void C_AO_ANS::Revision () { //---------------------------------------------------------------------------- int ind = -1; for (int i = 0; i < popSize; i++) { if (a [i].f > fB) { fB = a [i].f; ind = i; } } if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); //---------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (a [i].f > agent [i].fBest) { agent [i].fBest = a [i].f; ArrayCopy (agent [i].cBest, a [i].c, 0, 0, WHOLE_ARRAY); } } //---------------------------------------------------------------------------- int cnt = 0; for (int i = collectionSize; i < collectionSize * 2; i++) { if (cnt < popSize) { coll [i].f = agent [cnt].fBest; ArrayCopy (coll [i].c, agent [cnt].cBest, 0, 0, WHOLE_ARRAY); cnt++; } else break; } u.Sorting (coll, collTemp, collectionSize * 2); } //——————————————————————————————————————————————————————————————————————————————
3. 测试结果
ANS测试台结果
ANS|Across Neighbourhood Search|50.0|100.0|8.0|1.0|0.6|
=============================
5 Hilly's; Func runs: 10000; result: 0.9494753644543816
25 Hilly's; Func runs: 10000; result: 0.8477633752716718
500 Hilly's; Func runs: 10000; result: 0.43857039929159747
=============================
5 Forest's; Func runs: 10000; result: 0.9999999999988883
25 Forest's; Func runs: 10000; result: 0.9233446583489741
500 Forest's; Func runs: 10000; result: 0.3998822848099108
=============================
5 Megacity's; Func runs: 10000; result: 0.709230769230769
25 Megacity's; Func runs: 10000; result: 0.6347692307692309
500 Megacity's; Func runs: 10000; result: 0.2309076923076936
=============================
总分:6.13394 (68.15%)
ANS在所有测试函数上都表现出了令人印象深刻的结果。让我们来看看该算法在测试台上运行的可视化效果。虽然ANS的结果确实令人惊叹,但在可视化时,也出现了一些问题。特别是种群的行为十分惊人——它们似乎从视线中消失了。解空间被清空,函数中没有了智能体。这只能说明一点——尽管该算法的结果非常优秀,但种群容易退化。优秀的解集合变得充斥着大量非常相似的解,而新的解无法产生,因为所有解都是已存在解的衍生物。
这样的种群动态可能表明需要改进维持种群多样性的机制。也许可以考虑添加变异算子或引入其他机制,以帮助在优化过程中保持解的多样性。这将有助于避免种群退化,并确保算法更稳定地运行。
ANS在Hilly测试函数上
ANS在Forest测试函数上
ANS在Megacity测试函数上
本文所讨论的算法在评分表中稳居第二位。该算法表现出令人瞩目的可扩展性,即使在处理高维问题时,也能保持强大的搜索能力。
# | AO | 说明 | Hilly值 | Hilly最终值 | Forest值 | Forest最终值 | Megacity (离散) | Megacity最终值 | 最终结果 | 最大百分比 | ||||||
10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
1 | BGA | 二进制遗传算法 | 0.99989 | 0.99518 | 0.42835 | 2.42341 | 0.96153 | 0.96181 | 0.32027 | 2.24360 | 0.91385 | 0.95908 | 0.24220 | 2.11512 | 6.782 | 75.36 |
2 | ANS | 跨邻域搜索 | 0.94948 | 0.84776 | 0.43857 | 2.23581 | 1.00000 | 0.92334 | 0.39988 | 2.32323 | 0.70923 | 0.63477 | 0.23091 | 1.57491 | 6.134 | 68.15 |
3 | CLA | 密码锁算法 | 0.95345 | 0.87107 | 0.37590 | 2.20042 | 0.98942 | 0.91709 | 0.31642 | 2.22294 | 0.79692 | 0.69385 | 0.19303 | 1.68380 | 6.107 | 67.86 |
4 | (P+O)ES | (P+O) 进化策略 | 0.92256 | 0.88101 | 0.40021 | 2.20379 | 0.97750 | 0.87490 | 0.31945 | 2.17185 | 0.67385 | 0.62985 | 0.18634 | 1.49003 | 5.866 | 65.17 |
5 | CTA | 彗星尾算法 | 0.95346 | 0.86319 | 0.27770 | 2.09435 | 0.99794 | 0.85740 | 0.33949 | 2.19484 | 0.88769 | 0.56431 | 0.10512 | 1.55712 | 5.846 | 64.96 |
6 | SDSm | 随机扩散搜索 M | 0.93066 | 0.85445 | 0.39476 | 2.17988 | 0.99983 | 0.89244 | 0.19619 | 2.08846 | 0.72333 | 0.61100 | 0.10670 | 1.44103 | 5.709 | 63.44 |
7 | ESG | 社会群体的进化 | 0.99906 | 0.79654 | 0.35056 | 2.14616 | 1.00000 | 0.82863 | 0.13102 | 1.95965 | 0.82333 | 0.55300 | 0.04725 | 1.42358 | 5.529 | 61.44 |
8 | SIA | 模拟各向同性退火 | 0.95784 | 0.84264 | 0.41465 | 2.21513 | 0.98239 | 0.79586 | 0.20507 | 1.98332 | 0.68667 | 0.49300 | 0.09053 | 1.27020 | 5.469 | 60.76 |
9 | ACS | 人工协同搜索 | 0.75547 | 0.74744 | 0.30407 | 1.80698 | 1.00000 | 0.88861 | 0.22413 | 2.11274 | 0.69077 | 0.48185 | 0.13322 | 1.30583 | 5.226 | 58.06 |
10 | TSEA | 龟壳演化算法 | 0.96798 | 0.64480 | 0.29672 | 1.90949 | 0.99449 | 0.61981 | 0.22708 | 1.84139 | 0.69077 | 0.42646 | 0.13598 | 1.25322 | 5.004 | 55.60 |
11 | DE | 差分进化 | 0.95044 | 0.61674 | 0.30308 | 1.87026 | 0.95317 | 0.78896 | 0.16652 | 1.90865 | 0.78667 | 0.36033 | 0.02953 | 1.17653 | 4.955 | 55.06 |
12 | CRO | 化学反应优化 | 0.94629 | 0.66112 | 0.29853 | 1.90593 | 0.87906 | 0.58422 | 0.21146 | 1.67473 | 0.75846 | 0.42646 | 0.12686 | 1.31178 | 4.892 | 54.36 |
13 | BSA | 鸟群算法 | 0.89306 | 0.64900 | 0.26250 | 1.80455 | 0.92420 | 0.71121 | 0.24939 | 1.88479 | 0.69385 | 0.32615 | 0.10012 | 1.12012 | 4.809 | 53.44 |
14 | HS | 和声搜索 | 0.86509 | 0.68782 | 0.32527 | 1.87818 | 0.99999 | 0.68002 | 0.09590 | 1.77592 | 0.62000 | 0.42267 | 0.05458 | 1.09725 | 4.751 | 52.79 |
15 | SSG | 树苗播种和生长 | 0.77839 | 0.64925 | 0.39543 | 1.82308 | 0.85973 | 0.62467 | 0.17429 | 1.65869 | 0.64667 | 0.44133 | 0.10598 | 1.19398 | 4.676 | 51.95 |
16 | (PO)ES | (PO) 进化策略 | 0.79025 | 0.62647 | 0.42935 | 1.84606 | 0.87616 | 0.60943 | 0.19591 | 1.68151 | 0.59000 | 0.37933 | 0.11322 | 1.08255 | 4.610 | 51.22 |
17 | BSO | 头脑风暴优化 | 0.93736 | 0.57616 | 0.29688 | 1.81041 | 0.93131 | 0.55866 | 0.23537 | 1.72534 | 0.55231 | 0.29077 | 0.11914 | 0.96222 | 4.498 | 49.98 |
18 | WOAm | 鲸鱼优化算法M | 0.84521 | 0.56298 | 0.26263 | 1.67081 | 0.93100 | 0.52278 | 0.16365 | 1.61743 | 0.66308 | 0.41138 | 0.11357 | 1.18803 | 4.476 | 49.74 |
19 | ACOm | 蚁群优化 M | 0.88190 | 0.66127 | 0.30377 | 1.84693 | 0.85873 | 0.58680 | 0.15051 | 1.59604 | 0.59667 | 0.37333 | 0.02472 | 0.99472 | 4.438 | 49.31 |
20 | BFO-GA | 细菌觅食优化 - ga | 0.89150 | 0.55111 | 0.31529 | 1.75790 | 0.96982 | 0.39612 | 0.06305 | 1.42899 | 0.72667 | 0.27500 | 0.03525 | 1.03692 | 4.224 | 46.93 |
21 | MEC | 思维进化计算 | 0.69533 | 0.53376 | 0.32661 | 1.55569 | 0.72464 | 0.33036 | 0.07198 | 1.12698 | 0.52500 | 0.22000 | 0.04198 | 0.78698 | 3.470 | 38.55 |
22 | IWO | 入侵杂草优化 | 0.72679 | 0.52256 | 0.33123 | 1.58058 | 0.70756 | 0.33955 | 0.07484 | 1.12196 | 0.42333 | 0.23067 | 0.04617 | 0.70017 | 3.403 | 37.81 |
23 | Micro-AIS | 微型人工免疫系统 | 0.79547 | 0.51922 | 0.30861 | 1.62330 | 0.72956 | 0.36879 | 0.09398 | 1.19233 | 0.37667 | 0.15867 | 0.02802 | 0.56335 | 3.379 | 37.54 |
24 | COAm | 布谷鸟优化算法 M | 0.75820 | 0.48652 | 0.31369 | 1.55841 | 0.74054 | 0.28051 | 0.05599 | 1.07704 | 0.50500 | 0.17467 | 0.03380 | 0.71347 | 3.349 | 37.21 |
25 | SDOm | 螺旋动力学优化 M | 0.74601 | 0.44623 | 0.29687 | 1.48912 | 0.70204 | 0.34678 | 0.10944 | 1.15826 | 0.42833 | 0.16767 | 0.03663 | 0.63263 | 3.280 | 36.44 |
26 | NMm | Nelder-Mead方法 M | 0.73807 | 0.50598 | 0.31342 | 1.55747 | 0.63674 | 0.28302 | 0.08221 | 1.00197 | 0.44667 | 0.18667 | 0.04028 | 0.67362 | 3.233 | 35.92 |
27 | FAm | 萤火虫算法 M | 0.58634 | 0.47228 | 0.32276 | 1.38138 | 0.68467 | 0.37439 | 0.10908 | 1.16814 | 0.28667 | 0.16467 | 0.04722 | 0.49855 | 3.048 | 33.87 |
28 | GSA | 引力搜索算法 | 0.64757 | 0.49197 | 0.30062 | 1.44016 | 0.53962 | 0.36353 | 0.09945 | 1.00260 | 0.32667 | 0.12200 | 0.01917 | 0.46783 | 2.911 | 32.34 |
29 | BFO | 细菌觅食优化 | 0.61171 | 0.43270 | 0.31318 | 1.35759 | 0.54410 | 0.21511 | 0.05676 | 0.81597 | 0.42167 | 0.13800 | 0.03195 | 0.59162 | 2.765 | 30.72 |
30 | ABC | 人工蜂群 | 0.63377 | 0.42402 | 0.30892 | 1.36671 | 0.55103 | 0.21874 | 0.05623 | 0.82600 | 0.34000 | 0.14200 | 0.03102 | 0.51302 | 2.706 | 30.06 |
31 | BA | 蝙蝠算法 | 0.59761 | 0.45911 | 0.35242 | 1.40915 | 0.40321 | 0.19313 | 0.07175 | 0.66810 | 0.21000 | 0.10100 | 0.03517 | 0.34617 | 2.423 | 26.93 |
32 | SA | 模拟退火 | 0.55787 | 0.42177 | 0.31549 | 1.29513 | 0.34998 | 0.15259 | 0.05023 | 0.55280 | 0.31167 | 0.10033 | 0.02883 | 0.44083 | 2.289 | 25.43 |
33 | IWDm | 智能水滴 M | 0.54501 | 0.37897 | 0.30124 | 1.22522 | 0.46104 | 0.14704 | 0.04369 | 0.65177 | 0.25833 | 0.09700 | 0.02308 | 0.37842 | 2.255 | 25.06 |
34 | PSO | 粒子群优化 | 0.59726 | 0.36923 | 0.29928 | 1.26577 | 0.37237 | 0.16324 | 0.07010 | 0.60572 | 0.25667 | 0.08000 | 0.02157 | 0.35823 | 2.230 | 24.77 |
35 | Boids算法 | 虚拟生物算法 | 0.43340 | 0.30581 | 0.25425 | 0.99346 | 0.35718 | 0.20160 | 0.15708 | 0.71586 | 0.27846 | 0.14277 | 0.09834 | 0.51957 | 2.229 | 24.77 |
36 | MA | 猴群算法 | 0.59107 | 0.42681 | 0.31816 | 1.33604 | 0.31138 | 0.14069 | 0.06612 | 0.51819 | 0.22833 | 0.08567 | 0.02790 | 0.34190 | 2.196 | 24.40 |
37 | SFL | 混合蛙跳算法 | 0.53925 | 0.35816 | 0.29809 | 1.19551 | 0.37141 | 0.11427 | 0.04051 | 0.52618 | 0.27167 | 0.08667 | 0.02402 | 0.38235 | 2.104 | 23.38 |
38 | FSS | 鱼群搜索 | 0.55669 | 0.39992 | 0.31172 | 1.26833 | 0.31009 | 0.11889 | 0.04569 | 0.47467 | 0.21167 | 0.07633 | 0.02488 | 0.31288 | 2.056 | 22.84 |
39 | RND | 随机 | 0.52033 | 0.36068 | 0.30133 | 1.18234 | 0.31335 | 0.11787 | 0.04354 | 0.47476 | 0.25333 | 0.07933 | 0.02382 | 0.35648 | 2.014 | 22.37 |
40 | GWO | 灰狼优化算法 | 0.59169 | 0.36561 | 0.29595 | 1.25326 | 0.24499 | 0.09047 | 0.03612 | 0.37158 | 0.27667 | 0.08567 | 0.02170 | 0.38403 | 2.009 | 22.32 |
41 | CSS | 人工电场算法 | 0.44252 | 0.35454 | 0.35201 | 1.14907 | 0.24140 | 0.11345 | 0.06814 | 0.42299 | 0.18333 | 0.06300 | 0.02322 | 0.26955 | 1.842 | 20.46 |
42 | EM | 类电磁算法 | 0.46250 | 0.34594 | 0.32285 | 1.13129 | 0.21245 | 0.09783 | 0.10057 | 0.41085 | 0.15667 | 0.06033 | 0.02712 | 0.24412 | 1.786 | 19.85 |
Figure 1. 根据相关测试,将算法的颜色等级大于或等于0.99的结果以白色突出显示。
图例2. 算法测试结果的直方图(标尺从 0 到 100,数字越大结果越好,
其中 100 是理论上的最大可能结果,将计算评级表格的脚本存档)
在文章前面的部分,我们注意到了ANS算法群体存在退化的趋势。为了解决这一主要缺点,我决定通过添加一个变异算子来修改算法。在这种情况下,变异将是在智能体最优解附近的某个新坐标点以高斯概率获得,但该新坐标点位于对应坐标可接受的最小值和最大值的范围内。为此,我们需要对“移动”方法做一些修改。
让我们来看一下代码做了哪些修改,并简要描述方法的逻辑:
- 如果随机数小于0.005,则使用正态分布发生变异。
- 否则,从集合中随机选择一个解,或者使用最佳智能体坐标。
- 计算正态分布的距离和范围。
- 使用正态分布来获得新的坐标值。
//---------------------------------------------------------------------------- double min = 0.0; double max = 0.0; double dist = 0.0; int ind = 0; double r = 0.0; double p = 0.0; for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < 0.005) { val = u.GaussDistribution (agent [i].cBest [c], rangeMin [c], rangeMax [c], sigma); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); } else { if (u.RNDprobab () < collChoiceProbab) { do ind = u.RNDminusOne (collectionSize); while (coll [ind].f == -DBL_MAX); p = agent [i].c [c]; r = coll [ind].c [c]; } else { p = agent [i].c [c]; r = agent [i].cBest [c]; } dist = fabs (p - r) * range; min = r - dist; max = r + dist; if (min < rangeMin [c]) min = rangeMin [c]; if (max > rangeMax [c]) max = rangeMax [c]; val = u.GaussDistribution (r, min, max, sigma); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); } agent [i].c [c] = val; a [i].c [c] = val; } }
在添加变异算子后,算法将继续探索搜索空间,持续任意数量的迭代周期,如图3所示(算法可视化的截图)。
图例 3. 智能体得到保留,群体未退化(参数mut = 0.005)
- 当mut为0.1时,变异算子对整体结果产生了负面影响。由于变异率如此之大(每个坐标操作总数的10%),我们观察到算法性能有所恶化。因此,我决定逐渐减小这个参数。减小参数值后,结果得到了改善,并最终确定了0.005的值。事实证明,这个比例足以防止群体退化,同时仍然能改进算法的性能,如下所示。
算法在变异率mut = 0.1下的运行结果:
=============================
总分:6.05103 (67.23%)
ANS|Across Neighbourhood Search|50.0|100.0|8.0|1.0|0.6|
=============================
5 Hilly's; Func runs: 10000; result: 0.9534829314854332
25 Hilly's; Func runs: 10000; result: 0.8136803288623282
500 Hilly's; Func runs: 10000; result: 0.31144979106165716
=============================
5 Forest's; Func runs: 10000; result: 0.9996561274415626
25 Forest's; Func runs: 10000; result: 0.81670393859872
500 Forest's; Func runs: 10000; result: 0.25620559379918284
=============================
5 Megacity's; Func runs: 10000; result: 0.8753846153846153
25 Megacity's; Func runs: 10000; result: 0.5778461538461539
500 Megacity's; Func runs: 10000; result: 0.13375384615384744
=============================
总分:5.73816 (63.76%)
算法在变异率mut = 0.01下的运行结果:
=============================
5 Hilly's; Func runs: 10000; result: 0.9073657389037575
25 Hilly's; Func runs: 10000; result: 0.871278233418226
500 Hilly's; Func runs: 10000; result: 0.3960769225373809
=============================
5 Forest's; Func runs: 10000; result: 0.989394440004635
25 Forest's; Func runs: 10000; result: 0.9513150500729907
500 Forest's; Func runs: 10000; result: 0.35407610928209116
=============================
5 Megacity's; Func runs: 10000; result: 0.7492307692307691
25 Megacity's; Func runs: 10000; result: 0.6387692307692309
500 Megacity's; Func runs: 10000; result: 0.19352307692307838
=============================
总分:6.05103 (67.23%)
算法在变异率mut = 0.005下的运行结果:
ANS|Across Neighbourhood Search|50.0|100.0|8.0|1.0|0.6|
=============================
5 Hilly's; Func runs: 10000; result: 0.949632264944664
25 Hilly's; Func runs: 10000; result: 0.871206955779846
500 Hilly's; Func runs: 10000; result: 0.40738389742274217
=============================
5 Forest's; Func runs: 10000; result: 0.9924803131691761
25 Forest's; Func runs: 10000; result: 0.9493489251290264
500 Forest's; Func runs: 10000; result: 0.3666276564633121
=============================
5 Megacity's; Func runs: 10000; result: 0.8061538461538461
25 Megacity's; Func runs: 10000; result: 0.6732307692307691
500 Megacity's; Func runs: 10000; result: 0.20844615384615534
=============================
总分:6.22451 (69.16%)
总结
现在我们已经看到了与变异算子协同工作的结果,由此可以得出以下结论:
1. 简单易实现。
2. 探索与开发之间的平衡。
3. 解决各种类型问题的效率。
4. 对不同任务的适应性。
5. 有进一步改进的潜力。
因此,ANS是一种简单而有效的优化算法,它在多领域的问题上表现出具有竞争力的结果,并且具有进一步发展的潜力。
ANS优缺点:
优势:
- 在各种类型的函数上具有良好的收敛性。
- 非常快速的EA。
- 实现简单。
- 出色的可扩展性。
缺点:
- 有时会陷入局部极值。
文章附有一个包含当前版本算法代码的归档文件。本文作者对标准算法描述的绝对准确性不承担责任。为提升搜索能力,已经对其中的许多算法进行了修改。文章中表述的结论和论断都是基于实验的结果。
本文由MetaQuotes Ltd译自俄文
原文地址: https://www.mql5.com/ru/articles/15049