基于跨邻域搜索的连续域蚁群优化算法

夏 媛，李 俊，周 虎

(1.武汉科技大学计算机科学与技术学院，湖北 武汉，430065；2. 武汉科技大学智能信息处理与实时工业系统湖北省重点实验室，湖北 武汉，430065)

蚁群算法利用蚁群在搜索食物源的过程中所体现出的寻优能力来解决离散型组合优化问题[1]，如旅行商问题[2]、车辆路径问题[3]、作业车间调度问题[4]等。由于越来越多的实际应用被描述为连续域优化问题，因此将经典的离散型蚁群算法拓展到连续域成为一个新的研究方向。Bilchev等[5]最先提出连续域蚁群算法，通过将连续搜索空间离散成有限个区域来求解连续函数优化问题。该算法虽然有一定的寻优能力，但也存在容易陷入局部极值点、寻优精度差的问题。

针对以上不足，国内外研究者提出了各种改进方法。文献[6]提出的连续域蚁群优化改进算法首先利用全局搜索策略进行预处理，提高算法的收敛速度和收敛精度，然后利用随机搜索策略来增强搜索能力。文献[7]将启发式信息与连续域蚁群优化算法相融合，并应用于神经网络训练中，在减小分类误差的同时提高了收敛速度。文献[8]利用混合连续域蚁群优化技术来逼近最优解，并根据互相学习方案中的同化、顺应、变异等操作，使群体能够相互交换和容纳群体间的部分信息，并在全局范围内搜索信息，扩大搜索空间。文献[9]用高斯核函数作为概率密度函数来生成新解，通过替换档案中的解来更新信息素，利用高斯函数的随机性扩大种群搜索范围，避免算法陷入局部最优。文献[10]提出了一种信息分享机制，将当前解与其他所有解的平均距离以及当前解与目前最优解的距离相结合，同时采用一种新的解更新方式对档案中的解进行信息素挥发，并且自适应调整其挥发速率，更好地平衡收敛速度和收敛精度。文献[11]提出一种人工蜂群算子在全局信息素更新过程中产生候选解，同时引入替代机制来选择指导解，不仅可以节约计算时间，而且尽可能地保持了搜索的多样性。

以上改进算法或利用算法融合，或提出优化策略，所有改进方式的侧重点都在每一代的较优解上。这样虽加强了逼近最优解的能力，但探索未知区域的能力却相对较弱，容易陷入局部极值中。为了平衡寻优过程中逼近最优解和探索未知区域的能力，本文提出一种基于跨邻域搜索(across neighborhood search,ANS)的连续域蚁群优化算法。该算法采用自适应方式将种群划分为多个区域，其中主体区域分为较优解组和较差解组；其次让较差解组根据自主选择学习算子来选择对象进行学习，不断扩大种群规模，避免算法陷入局部最优；再者对较优解组采用全局跨邻域搜索方式，引导蚂蚁向全局最优解靠近，加快收敛速度；最后对处理后的解档案进行重排序，选取最优解做为指导解，并利用局部跨邻域的方式在小范围内进行细致搜索，通过贪心机制，对比新解和旧解，更新解档案，寻找最优解。

1 连续域蚁群优化算法

在连续空间寻优问题的求解中，解空间是以区域性方式而不是离散点来表示的，因此不能采用经典的离散型蚁群算法。与离散型蚁群优化算法不同的是，连续域蚁群算法的优化目标是所求问题的目标函数值达到最优，因此在信息素的更新方式和状态选择规则中均有所不同，其主要是根据目标函数值来更新信息素浓度，以微调的前进方式来代替状态选择规则。

连续优化问题描述如下：设蚂蚁个数为m，解个数为K，Xi=(Xi1,…,Xij,…,Xin)表示所求问题的一个解，Xij表示第i个解中第j维的值，n为问题的维数，K个解构成一个K×n的解矩阵。连续域蚁群优化算法要解决的是如何根据每个目标函数值的信息素浓度，通过相应的转移方式不断引导算法向最优解靠近。本文提出一种基于跨邻域搜索的改进连续域蚁群算法(命名为ANS-Ant)来解决连续优化问题。

2 ANS-Ant算法

2.1 自适应种群划分

最早提出的连续域蚁群优化算法通过初始化随机产生种群，每次迭代只将最优解作为可行解，不好的解即被舍弃。因此，种群个体在迭代期间只会往同一个方向进行寻优，容易导致算法陷入局部最优。文献[12]指出，通过不断获得失败经验，可以引导蚁群在优化过程中探索未知空间。因此本文提出一种自适应划分方式，根据当前迭代次数来分割优解和劣解的种群数量，具体公式如下：

(1)

式中：p为优解的种群数量；h为劣解的种群数量；kmax为最大迭代次数；k为当前迭代次数。

通过这种自适应划分方式，使得算法在迭代初始阶段优解较少，而且数量增长得较慢，这样能保证算法在迭代初期以较快速度收敛到全局较优解；在迭代的中后期，扩大了优解的数量，这样能抑制早熟，避免算法落入局部极值点。同时，前期劣解数量较多，可以在一定程度上扩大种群的探索空间；在迭代中后期，劣解数量逐渐减少，这样能加快算法收敛。

2.2 自主选择学习算子

自适应种群划分将解档案区分为优解和劣解。针对劣解，基于教与学算法[13]中同学之间可以互相交流学习、一个同学通过随机选择另一位同学进行学习来提高成绩的思想，本文让劣解同时具有较优解可以进行互相学习的类似学习能力。然而，对于每一个劣解而言，如果选择的对象也为劣解，则相互学习不仅无法提高成绩，还会浪费学习时间。故对劣解采取随机选择策略进行学习的不稳定因素太大，不仅无助于提高收敛精度，还会占据计算时间。一般来说，人们倾向于让成绩不好的学生向优秀学生学习，以达到提升整体学习水平的目的。同理，让劣解向最优解进行学习可提升解档案的整体水平。但如果所有的劣解同时向最优解进行学习，算法又很容易陷入局部最优。因此，本文提出一种自主选择学习算子，具体公式如下：

Xnew=Xbad+rand(0,1)(Y-Xbad)

(2)

式中：Xnew为较差解经过自主选择学习后产生的新解；Xbad为h个较差解；Y为上次迭代产生的p个较优解中任意一个。该算子旨在让每一个劣解在较优解群体中自主选择对应的较优个体进行学习，这样能在一定程度上扩大种群多样性，避免产生局部最优。

2.3 跨邻域搜索机制

跨邻域搜索是一种较新且简便的数值优化算法[14]，其具体方法为：以个体i与当前最好解决方案之间的长度为搜索区域，利用高斯分布影响因子来平衡算法的开发和勘探能力。每个个体不仅可以搜索其他解周围的邻域，还可以搜索最优解周围的邻域。结合跨邻域搜索算法的优点，本文在连续域蚁群算法中针对较优解组引入其良好的勘探能力，针对指导解引入其良好的逼近最优解能力。

2.3.1 全局搜索

扩大种群多样性可以避免算法陷入局部最优，但如果只对较差解组进行更新，则不能确保更新后的解对收敛精度的影响因子大小，换句话说，如果更新后的解优于当前迭代产生的较优解，可能会导致搜索方向出现偏差，无法找到更好的解。为了避免这种情况的发生，本文引入全局跨邻域搜索机制，旨在让p个较优解在处理了较差解组的基础上分别随机选择一个解进行学习，具体公式如下：

Xnew=Xgood+G(0,δ2)|Xgood-posi|

(3)

式中：Xnew为较优解经过全局搜索后产生的新解；Xgood为p个较优解；posi为随机选择的任意解；G(0,δ2)为高斯分布因子，表示在高斯分布范围内选取邻域，该因子提供的搜索范围较广，波动幅度较小，且符合连续域蚁群优化算法的微调式前进方式。

从式(3)可以看出，由于选择的学习对象不同，每个个体搜索的范围也不一致，从而实现了较优解组里面的每一个解都可以在不同的邻域范围内进行探索的全局搜索模式，在确保种群多样性的同时加快向全局最优解的收敛。

2.3.2 局部搜索

连续域蚁群算法中以函数的适应度值作为当前的信息素浓度值，适应度值越小，表示信息素浓度越大，则蚂蚁更倾向于往该处的解转移。因此要对处理后的解档案进行重新排序，选择信息素浓度最大也就是适应度值最小的解作为指导解，对指导解周围进行细致的局部邻域搜索，引导蚂蚁向最优解靠近。具体实现方式如式(4)所示：

Xbest=Xobject+G(0,δ2)|Xobject-posi|

(4)

式中：Xbest是经过局部搜索后产生的新解；Xobject为指导解；G(0,δ2)同为高斯分布因子，旨在局部范围内进行范围广、波动幅度较小的搜索。跨邻域局部搜索可以提高算法的收敛精度，并使其具有较好的开发能力。

2.4 ANS-Ant算法基本步骤

步骤1初始化NP个解并排序。

步骤2针对排序后的解，根据式(1)自适应地选出当前的较优解组和较差解组。

步骤3根据式(2)提出的自主选择学习算子，让较差解组中的每个个体自主选择较优解组中的解进行学习。

步骤4在执行了较差解组的处理的基础上，利用式(3)针对迭代产生的较优解组进行全局跨邻域范围内的搜索，更新较优解组。

步骤5将经过步骤3和步骤4处理后的解档案进行重排序，并选取最好的解作为指导解。

步骤6根据式(4)对指导解周围进行局部跨邻域细致搜索，利用贪心机制，对比旧解和新解，更新解档案。

步骤7若达到最大迭代次数，则选取解档案中的最优值为最终解，否则返回步骤2。

3 算法测试及结果分析

3.1 测试函数

选择CEC2017收录的29个标准测试函数[15]检验改进算法ANS-Ant的有效性和适用性(函数f2稳定性不好，被CEC2017排除，本文不对其进行测试)，具体定义如表1所示，其中f1、f3

表1 标准测试函数

为单峰函数，f4～f10为简单多峰函数，f11～f20为混合函数，f21～f30为复合函数。

3.2 实验参数

实验中使用Matlab R2016a软件编程，系统运行环境为：Win 7双核，Intel(R) Core(TM) i5处理器，8 GB内存，3.2 GHz CPU。实验参数设置如下：种群个数NP=100，最大迭代次数itermax=10 000，问题维度分为30和50，每个函数在两种维度下分别独立运行20次。通过与文献[9]中提出的ACOR算法和文献[11]中提出的ABC-ACOR算法在参数设定一致的情况下进行收敛精度和速度的比较，来验证本文算法的优越性。

3.3 实验结果及分析

3.3.1 收敛精度

为了更直观地进行数据对比，本文各算法的收敛精度均定义为计算得到的适应度值Fitness减去测试函数的最优解。表2所示为固定评价次数时3种算法的收敛精度对比，包括在30维情况下的平均值、最小值和方差，其中最好结果用粗体标出。

表2 3种算法的收敛精度(D=30)

从表2中可以看出，本文提出的改进算法在除f9以外的28个测试函数中取得的平均值相对于另外两个算法来说均较优或基本持平(f27,f28)。从最小值来看：对于单峰函数，本文算法优于ACOR和ABC-ACOR；在简单多峰函数中，本文算法除在函数f9上取得的值稍逊于ACOR外，其余均较优；对于混合函数，本文算法在函数f11上取得的值稍逊于ABC-ACOR；对于复合函数，本文算法与另外两个算法在函数f27、f28上的结果持平，在f22上的结果与ABC-ACOR持平，优于ACOR，虽在f25、f26上稍逊于ABC-ACOR，但比ACOR要好。从方差来看，本文算法在接近一半的函数中优于另外两种算法，且在f3上表现优异。综上所述，本文算法在针对低维问题时总体上具有较好的寻优能力和稳定性。

图1为各算法在低维情况下求解测试函数的收敛曲线，分别取单峰函数、简单多峰函数、混合函数和复合函数中的一种作为示例。

(a)单峰函数f3

(b)简单多峰函数f8

(c)混合函数f15

(d)复合函数f21

图1 3种算法的收敛曲线(D=30)

Fig.1 Convergence curves of three algorithms(D=30)

从图1可以看出，与ACOR和ABC-ACOR相比，ANS-Ant算法在这几个函数上的寻优能力明显较高，且收敛较快。总的来看，ANS-Ant解决低维连续域优化问题时在收敛速度和精度上的优势明显。

为验证ANS-Ant算法对高维问题的寻优能力，对比了固定评价次数时3种算法在50维条件下的收敛精度，如表3所示，其中最好结果用粗体标出。从最小值来看，ANS-Ant在f1、f4、f16、f23和f25上的结果不如ABC-ACOR，但两者相差不大，在其他测试函数上，ANS-Ant的取值均优于另外两种算法，且在f3和f6上得到的结果几乎接近于函数最优解；从平均值来看，ANS-Ant只在f1、f4、f15和f25函数上稍逊一筹；从方差来看，ANS-Ant在接近40%的测试函数上占有优势。总体来说，在高维情况下，ANS-Ant算法依然具有较好的寻优能力，保持了一定的稳定性。

表3 3种算法的收敛精度(D=50)

续表3

函数编号ACOR平均值最小值方差 ABC-ACOR平均值最小值方差 ANS-Ant平均值最小值方差f217.87E+027.53E+023.10E+023.95E+023.54E+024.57E+023.12E+022.86E+022.26E+02f221.59E+041.55E+045.28E+041.35E+041.31E+047.25E+046.13E+034.74E+034.77E+05f231.05E+039.85E+027.84E+026.11E+025.07E+024.20E+035.90E+025.26E+021.43E+03f241.14E+031.09E+037.52E+027.33E+026.90E+029.51E+026.94E+026.33E+021.35E+03f254.45E+033.83E+033.27E+054.40E+024.31E+022.49E+024.83E+024.44E+026.00E+02f266.68E+036.06E+031.17E+056.92E+034.03E+031.62E+061.87E+031.37E+037.11E+04f275.00E+025.00E+022.10E-095.00E+025.00E+024.10E-095.00E+025.00E+022.70E-08f285.00E+025.00E+029.24E-095.00E+025.00E+022.67E-095.00E+025.00E+024.55E-04f291.50E+048.31E+038.25E+061.40E+038.13E+028.46E+041.01E+035.54E+027.84E+04f301.05E+095.45E+085.07E+162.07E+031.01E+037.58E+051.68E+032.92E+021.49E+06

图2为各算法在高维情况下求解测试函数的收敛曲线，同样各取单峰函数、简单多峰函数、混合函数和复合函数中的一种作为示例。

(a)单峰函数f3

(b)简单多峰函数f6

(c)混合函数f11

(d)复合函数f21

图2 3种算法的收敛曲线(D=50)

Fig.2 Convergence curves of three algorithms(D=50)

从图2可以看出，与ACOR和ABC-ACOR相比，ANS-Ant算法在单峰和简单多峰函数上的寻优能力明显较优，所得解与函数最优解十分接近，且收敛较快；ANS-Ant在混合函数上也有较好的寻优能力和较快的收敛速度；ANS-Ant在复合函数上的寻优结果与函数最优解的相对偏差虽然有13.6%，但相比于另外两种算法还是有一定的优势。总之，ANS-Ant应用于高维测试函数时仍然具有较高的收敛速度和精度。

3.3.2 收敛速度

为了更加全面地检验改进算法的性能，本文采用限定精度的方法来评估其收敛速度，即在有限的评估精度内比较各算法的进化次数。以30维为例，针对每一个函数设置一个相应的评估精度VTR，该值取3种优化算法所得平均值中的最差值，如表4所示。针对每一个函数的预设收敛精度，3种算法均独立运行20次，设置最大迭代次数为10 000，最后将平均评估次数列于表5。

表4 预设收敛精度VTR

表5 预设收敛精度下各算法的评估次数

通过表5可以看出，相比于其他两个算法，ANS-Ant在29个测试函数的22个中可以更快地达到预设收敛精度，表明本文提出的改进方式有效提高了连续域蚁群优化算法的收敛速度。

4 结语

针对连续域蚁群算法寻优能力差、容易陷入局部最优的问题，本文提出了一种基于跨邻域搜索的改进蚁群算法ANS-Ant。该算法利用不可行解不断获取历史经验，针对不可行解群体，利用自主选择学习算子选择对象进行学习，不断扩大种群规模，避免算法早熟收敛。利用自适应群体划分方法，计算出可行解群体，并采取全局跨邻域搜索的方式，引导蚂蚁向全局最优解靠近，加快收敛速度。最后对解档案进行重排序，并利用局部跨邻域的方式引导蚂蚁在小范围内进行细致搜索，提高收敛精度。通过对CEC2017测试函数在低维和高维情况下的对比实验，证明ANS-Ant算法在解决连续优化问题时具有较好的寻优能力和稳定性，能有效克服经典蚁群算法容易陷入局部最优的缺点。