基于MIMIC算法和RPCA的混合蚁群优化算法

官娟 刘国华 刘天祺 秦健 张淼森

0 引言

元启发式算法是一类优化技术,在过去几年中得到了越来越快的发展,并被应用于许多问题．蚁群算法是一类比较典型和重要的元启发式算法,最早由Colorni等在1992年提出[1],算法主要针对自然界的蚂蚁觅食做了经典实验,通过将真实蚂蚁的行为模型化,得出了人工蚂蚁解决多目标决策问题的思路．基于此思想,Dorigo等开创性地提出了蚁群算法[2]．蚁群算法的本质是一个复杂的智能系统——蚂蚁系统(AS),它具有较强的鲁棒性、优良的分布式计算机制,以及易于与其他算法相结合等优点.

虽然蚁群算法具有许多优点,在低维问题中可取得较好的效果,但对于大规模问题全局寻优性能急剧下降,存在一些缺陷,如收敛速度慢、容易陷入局部最优解等,同时这也是大部分优化算法所面临的问题．针对此现状,近年来许多学者在蚁群算法的改进方面进行了研究,并提出了许多改进的蚁群算法,包括蚁群优化 (ACO) 的元启发式方法[3]、蚁群系统(ACS)[4]、基于Q-学习的自适应蚁群算法[5]、最大最小蚂蚁系统(MMAS等)[6]．这些改进的算法主要从信息素释放方式、信息素更新规则、路径选择策略、参数的选择等方面入手,对蚁群算法进行了不同程度的改进,但仍存在一个很大的问题,即随机性对解搜索带来的较强干扰,使得解变量之间的相关性和抽样求解的效率太低、冗余度过高,严重制约了蚁群算法在高维空间中的优化性能．已有的蚁群优化算法中缺少对关于随机变量间相关性的研究,Socha等[7]在研究连续域上的蚁群算法中有过相关问题的探讨,但并未对算法中变量相关性做进一步的研究.

为更有效地处理大规模优化问题,提高算法性能,本文在蚁群算法中,加入变量相关性分析并根据决策变量的相关性定义,提出一种新的关于解分量之间的相关性定义——有效相关性与冗余相关性;然后,根据得到的有效相关性矩阵,运用MIMIC(Mutual Information Maximization for Input Clustering)分布估计算法对解存档建立决策变量间的概率图模型,并根据概率模型采样获得新的解存档,来提高蚁群优化算法的全局搜索能力;接着,利用RPCA(Robust Principal Component Analysis)技术找到新的解存档的低秩结构矩阵,优化搜索空间、降低计算复杂度,进而在蚁群算法框架下,更新解存档;最后,通过实验仿真测试算法性能,将所得结果与连续域上的蚁群优化算法相比较,表明该算法可降低多个解分量之间的冗余相关性,在寻优能力和收敛性方面都有显著提高.

1 连续域上的蚁群优化算法

连续域上的蚁群优化算法ACOR(Ant Colony Optimization for Continuous Domains)[7]均匀随机产生k个解作为初始解存档,如图1所示．每个解都是一个D维向量,其实值解决策分量xi∈[xmin,xmax],其中i=1,…,D．本文假定优化问题中只存在box有界约束．根据目标函数值从优至劣对解存档中k个解进行排序,每个解Sk都关联了一个权重ωk．该权重使用高斯函数计算,如下所示:

(1)

其中r(j)是排序解存档中解Sj的序号,q是算法的一个参数.

2 基于MIMIC算法和RPCA的混合蚁群算法

2.1 变量相关性

现有的蚁群优化算法中,随机性对解的搜索带来了较强的干扰,使得解变量之间的相关性太低、抽样求解的效率太低、冗余度过高,严重制约了蚁群算法的优化性能．因此,显著提高蚁群算法的优化性能就必须克服抽样解选取过程中的相关性问题.

基于以上考虑,本文首先根据决策变量间的相关性定义,给出解分量之间的有效相关性和冗余相关性的定义.

2.1.1 解分量与解分量之间的相关性

根据文献[8-9],两个决策变量xi和xj被称为相关,如果∃x=(x1,x2,…,xn),x′i,x′j满足下列条件:

f(x1,…,xi,…,xj,…,xn)

f(x1,…,xi,…,x′j,…,xn)>f(x1,…,x′i,…,x′j,…,xn)，

(2)

其中x是候选决策向量,x′i,x′j分别被第i和第j个决策变量替换,“∧”表示逻辑符号“且”.

2.1.2 解分量与解分量之间的有效相关性

设X为当前解,samplei为对第i个分量进行采样的采样算子,>opt代表更优化的比较算子,即只要存在一个可行解,满足式(2),则说明解分量xi与解分量xj关于目标函数f存在相关性,然而式(2)只刻画了变量间相关性的存在性,并未指出对优化过程具有有效促进作用的部分相关性,因此定义一个有效相关性如下:

∃x=(x1,x2,…,xn),x′i=samplei(X),x′j

s.tf(x1,…,x′i,…,x′j,…,xn)>opt

f(x1,…,xi,…,x′j,…,xn)

∨

∃x=(x1,x2,…,xn),x′i,x′j=samplei(X)

s.tf(x1,…,x′i,…,x′j,…,xn)>opt

f(x1,…,x′i,…,xj,…,xn)

(3)

其中“∨”表示逻辑符号“或”.

2.1.3 解分量与解分量之间的冗余相关性

相应地,称:

∃x=(x1,x2,…,xn),x′i=samplei(X),x′j

s.tf(x1,…,x′i,…,x′j,…,xn)

f(x1,…,xi,…,x′j,…,xn)

∧

∃x=(x1,x2,…,xn),x′i,x′j=samplei(X)

s.tf(x1,…,x′i,…,x′j,…,xn)

f(x1,…,x′i,…,xj,…,xn)

(4)

为解分量xi与xj关于f的冗余相关部分.

分布估计算法[10-11]是一种基于种群的搜索算法．它利用解存档建立概率分布模型,然后根据概率分布模型来指导个体进行搜索,其过程是一个不断更新概率模型,从而使概率模型越来越能反映优秀个体分布的过程．所以,分布估计算法具有比较强的全局搜索能力.

蚁群优化算法搜索时间长,易陷入局部最优解是其最为突出的缺点.为了提高蚁群算法的寻优能力,可以在蚁群优化算法中混合分布估计算法.

2.2.1 MIMIC算法

MIMIC算法,即输入聚类的最大互信息算法,最早由美国MIT人工智能实验室的de Bonet 等提出的一种基于双变量相关模型的分布估计算法[12]．在MIMIC算法中,变量之间的关系可以用链式有向图表示(图2).

设决策变量集合x=(x1,x2,…,xn)的联合概率分布为p(x)=p(x1,x2,…,xn),且

p(x)=p(x1|x2,…,xn)p(x2|x3,…,xn)…p(xn-1|xn).

(5)

算法中解空间的概率模型可以描述为

xin)…pl(xin-1|xin),

(6)

其中π=(i1,i2,…,in)表示变量x1,x2,…,xn的一个排列,pl(xij|xij+1)表示第ij+1个变量取值为xij+1时第ij个变量取值为xij的条件概率.

(7)

其中:

对于优化变量x=(x1,x2,…,xn),存在一个最优排列π=(i1,i2,…,in)使得条件概率之积fπ(x)=f(xi1|xi2)…f(xin-1|xin)·f(xi1)与解存档的概率分布f(x)之间的K-L距离达到最小.

2.3 RPCA

如果搜素空间的维数过高,会严重影响蚁群算法的性能,需要一种技术来降低解分量之间的冗余相关性．在连续域上的蚁群优化算法和MIMIC算法中,候选解是根据高斯密度函数进行采样的,所以如果要对高维空间进行降维处理,并且降低解分量之间的冗余相关性,最常使用的技术是主成分分析(PCA)技术[14],但由于PCA技术的鲁棒性较差,在寻优过程中容易出现停滞的状况．所以本文选择使用RPCA技术,既可以降低解分量之间的冗余相关性,也可以保证蚁群系统的鲁棒性.

RPCA(Robust PCA)[15]是在PCA基础上加入一个可以测量在各个维度以内异常点的鲁棒函数,并且想办法去除异常点和修正恢复主要结构空间的一种方法．它很好地解决了传统PCA在处理大误差时不具有鲁棒性的问题.

2.3.1 RPCA模型

设新的解矩阵S′=B+E,其中B是低秩矩阵,E为稀疏(噪声)矩阵[16]．RPCA模型解决的问题是从带有稀疏大噪声的数据中精确地恢复出低秩矩阵．此模型可以表示为

min‖B‖*+λ‖E‖1, s.t.S′=B+E,

(8)

其中‖·‖1为矩阵的1范数,‖·‖*为矩阵的和范数,是需要恢复的低秩结构矩阵，E是未知的噪声矩阵，S′是包含噪声的新的解矩阵.

2.3.2 RPCA模型求解[17]

对模型(8)构建拉格朗日函数得:

Lμ(B,E,Z)=‖B‖*+λ‖E‖1+

(9)

迭代低秩矩阵B为

Dμ-1{S′-E+μ-1Z}，

(10)

迭代稀疏矩阵E为

Sλμ-1{S′-B+μ-1Z}，

(11)

其中矩阵Z是拉格朗日乘子,μ为一个正数.

2.4混合蚁群优化算法

蚁群算法在低维问题中取得了较好的效果,具有较强的局部搜索能力,但对于大规模问题全局优化性能急剧下降,而MIMIC算法的全局寻优能力强,局部搜索能力较弱,RPCA可以恢复高维空间的低维结构空间,并保持系统的鲁棒性,所以在ACOR算法的整体框架下加入MIMIC分布估计算法和RPAC以提高算法的寻优能力和效率．在ACOR算法中,决策变量分量之间相互独立,未考虑解分量之间的相关性,导致抽样效率不高,所以在混合蚁群算法中,建立初始解存档之后,我们根据提出的有效相关性定义计算解存档的有效相关性矩阵指导后续算法采样．整个更新解存档的具体步骤如下:

对于解存档

(12)

根据定义式(3),计算解分量之间的有效相关性矩阵:

(13)

samsolkl=(sk1,…,samplei(s),…,slj,…,skn),

3)根据有效相关性矩阵,计算概率分布fπ(s)=f(si1|si2)f(si2|si3)…f(sin-1|sin)f(sin).

步骤4.对步骤3得到低秩结构矩阵B的解分量进行评估,并更新解的目标函数值.

步骤5.将m条新的解所对应的目标函数值与原来的解存档空间的k个解的目标函数值重新进行由优至劣的顺序排序,选取前k个解,作为新的解存档.

3 数值实验

3.1 测试函数

为测试算法的性能,并与连续域上的蚁群优化算法进行比较,本文对下面6个标准的测试函数进行测试.

Sumcan函数:

Sphere函数:

Giewangk函数:

Schwefel函数:

Rastrigin函数:

Easom函数:

f(x)=-cos(x1)cos(x2)e-((x1-π)2+(x2-π)2),-100≤x1,x2≤100;minf(x)=f(π,π)=-1.

3.2 参数设置

在实验中,算法的参数设置如下:蚂蚁个数m=50,保留最优解个数k=10,最大迭代次数为50,精度为10-6,调试不同启发因子q与信息素挥发率τ,分别进行10次实验.

3.3 实验结果与分析

为测试混合蚁群优化算法的性能,本文采用下列4种性能指标对实验结果进行分析,其中设定函数的维数n=10.

1)在固定最大迭代次数内算法得到的最优值及平均最优值如表1所示．由表1知,混合ACOR算法对6个测试函数进行10次实验后都可以很快地找到函数的最优值,并且与函数实际理论的最优值相同,说明混合ACOR算法在固定的最大迭代次数内能够得到很好的优化结果,算法是可行的．同时,也可由表1看出,混合ACOR算法的最优值和平均值都优于原来的ACOR算法,这是由于混合ACOR算法考虑变量之间的相关性,结合全局寻优能力强的MIMIC分布估计算法和RPCA技术,降低了变量之间的冗余相关性和陷入局部最优值的概率,收敛速度加快,在寻优能力上有了很大的提高.

表1 50次迭代内算法优化结果Table 1 Optimization results of algorithms within 50 iterations

2)表2是混合ACOR算法与标准ACOR算法达到理论最优值时的平均迭代次数的比较结果,其中Sumcan函数的最优值为-105,Sphere、Giewangk、Schwefel和Rastrigin函数最优值为0,Easom函数最优值为-1,“50+”代表算法在50次迭代后仍未达到理论最优值．由表2可以看出,对于6个测试函数,混合ACOR算法的平均迭代次数远远优于标准ACOR算法,平均迭代次数都很小,很快就达到了迭代次数少、收敛速度快的理想状态.

表2 到达理论最优值的平均迭代次数Table 2 Average number of iterations reaching the theoretical optimal value

所有函数的标准ACOR算法在最大迭代次数内没有达到理论最优值,部分函数后续迭代的最优值都在某个值上停留,所以认为算法很大可能已经陷入局部最优值．这说明与标准ACOR算法相比,混合ACOR算法收敛速度非常快,陷入局部最优解的概率非常小,基本能在最大迭代次数内收敛到最优值,大大减少收敛时的迭代次数,提高了解更新效率.

3)达标率指算法达到理论最优值的次数与实验总次数的比例．表3给出了标准ACOR算法和混合ACOR算法达到理论最优值时达标率的比较结果．由表3可以看出,对于6个测试函数,在混合ACOR算法中都成功找到了函数理论最优值,达标率为100%,即算法寻优过程中,陷入局部最优解的概率非常小;而标准的ACOR算法除了Easom函数在10次实验中9次达到最优值,其他函数均未在固定迭代次数内找到理论最优值,达标率为0,也就是说,标准的ACOR算法在固定迭代次数内,函数收敛于局部最优值的概率较大,特别容易在寻优过程中发生停滞的现象．混合ACOR算法的达标率远远优于标准ACOR算法的达标率,这说明混合ACOR算法有很高的有效性和可靠性.

表3 到达理论最优值的次数与实验次数的比例Table 3 Ratio of the number of arrivals at the theoretical optimal value to the number of experiments %

图3a—3f分别为6个函数的标准ACOR算法和混合ACOR算法在相同迭代次数下的函数值的仿真实验结果．从图中可以很清晰地看出,与标准的ACOR算法相比,混合的ACOR算法可以在最初的几次迭代中快速成功找到函数的理论最优值,甚至如果选择合适的参数,对于部分函数,算法在第一次迭代就能成功找到函数的全局最优值,进而快速收敛;相比之下,标准的ACOR算法在固定迭代次数内,全局寻优能力和收敛速度上都不是很理想.

4)在迭代次数不变的条件下,改变函数维数,比较两种算法的寻优性能(表4和表5)．下面是测试函数维数分别为10维和30维的情况下,标准ACOR算法和混合ACOR算法函数最优值与平均值的比较,实验结果可以体现不同维数对两种算法的影响．表4是不同维度下两种算法最优值的比较,表5是不同维度下两种算法平均值的比较,其中本次实验的固定迭代次数为50次.

由表4和表5可以看出,随着测试函数维数的增多,标准ACOR算法寻找最优值的能力在减弱,但是混合ACOR算法并没有表现出明显的寻优能力下降的趋势,不管是30维还是10维,混合ACOR算法在实验中得出的最优值和平均值都比标准的ACOR算法要好得多,且维数越高,优势越明显．这是由于当函数维数增大时,混合ACOR算法考虑了变量之间的相关性,并且利用RPCA技术尽可能精确地保留有效相关系数大的解分量,去除大的异常解分量和冗余的解分量,所以,虽然函数维数增大,但是最终得到的对函数值起主要作用的解分量并没有增加,反而因为维数的增加,优化了搜索空间,可以更容易找到全局最优值的搜索邻域,从而提高算法的寻优性能.

表4 不同维度下两种算法最优值的比较Table 4 Comparison of optimal values between the two algorithms under different dimensions

表5 不同维度下两种算法平均值的比较Table 5 Comparison of the average values between the two algorithms under different dimensions

4 结束语

本文针对标准的ACOR算法存在的不足,考虑算法中决策变量之间的相关性,根据变量有效相关性的定义,提出一种基于MIMIC算法和RPCA的混合蚁群算法．经仿真实验结果验证,与标准ACOR算法相比,混合ACOR算法可以十分精确地找到最优值,且到达理论最优值时的迭代次数和达标率都远远优于标准算法．混合蚁群优化算法有MIMIC算法全局搜索能力强的优点,又包含蚁群算法的局部求精能力强、收敛速度快的优点;对于高维空间上的寻优过程,由于混合ACOR算法加入RPCA技术,在保证变量之间的有效相关性和系统鲁棒性的同时,保留主要解空间结构,降低计算复杂度与解变量之间的冗余相关性,优化搜索空间,使得该算法在解决高维优化问题时仍具有很强的寻优能力.