结合变尺度法的改进类电磁机制算法

印 峰，王耀南，杨易旻，曹文明

(湖南大学电气与信息工程学院，湖南长沙410082)

在求解函数优化问题过程中，如果待优化问题的目标函数较为复杂，或其一、二阶信息难以获取时，一般传统的优化方法不再适合求解这类问题.而启发式的随机搜索方法是求解此类全局优化问题的有效途径之一，至今已得到广泛应用的模拟退火算法、遗传算法及蚁群算法等都采用了随机搜索的思想［1-2］.近年来，Birbil等学者受电磁学中带电粒子间“排斥－吸引”力的启发，提出一种新的用于求解含有界变量约束问题的全局收敛算法——类电磁算法［3］，通过选取15个函数组成的综合测试函数集对EM(electromagnetism-like mechanism)算法性能进行了测试，并与经典优化方法进行了比较，测试结果表明EM算法可收敛到问题的最优解，并且显示出更好的优化性能.文献［4］进一步从理论上证明了EM算法依分布全局收敛于问题的ε-最优解.目前，EM算法在函数优化、神经网络训练、TSP以及项目调度问题上已得到了初步的应用，并取得了很好的优化结果［3，5-6］.

虽然对EM算法的研究在理论和工程应用上已取得了一定的进展，但和遗传算法、蚁群算法等传统优化方法相比，目前对于EM算法的研究还非常有限.本文所做的工作是:围绕算法初值敏感性问题、种群规模选取及其对算法的收敛速度影响、算法收敛速度及停滞等问题对EM法开展了深入的研究.结合本文的研究结果提出了一种优化的计算框架，采用该混合优化策略可将EM法和DFP法二者的优势相结合，保证计算的有效性和实时性.

1 类电磁机制算法的原理

EM法首先随机地从可行域中产生一组初始解，并将每一个解想象成空间中的一个带电粒子;通过模拟电磁理论中带电粒子间吸引－排斥机制使得粒子种群朝最优解区域移动，每个粒子下一步的移动方向通过计算其他粒子施加给当前粒子的合力方向来确定，同电磁力的计算方式一样，该合力是通过将来自其他粒子的力进行矢量叠加得到的.这样，每完成一次迭代计算就产生一组新的更优解.一个n维变量约束优化问题可用如下方程描述:

采用EM算法求解上述优化问题主要包括以下4个基本步骤:初始化、局部搜索、电荷量和合力计算以及移动粒子的过程.

1.1 初始化

在进行迭代计算前，需要进行初始化，即从可行域内均匀地随机抽取m个样本点{x1，x2，…，xm}作为初始解，其中，i=1，2，…，m.随机抽样过程可采用式(1)实现:

抽取到所有样本点后，计算出每个样本点对应的目标函数值，并将目标函数值最优的样本点记为xbest.

1.2 局部搜索

局部搜索过程用来改进当前样本点，即搜索样本点邻域范围内的更优解，如果这样的更优样本点存在，则用更优样本点代替当前已搜索到的样本点.局部搜索的对象可以是整个样本点，也可以只对当前最优样本点进行局部搜索.

1.3 电荷量及合力矢量计算

EM算法通过计算施加到每个粒子上的合力获取下一步的搜索信息.首先需要确定每个粒子的电荷量，构造公式如下:

根据式(2)，目标函数较优的粒子将拥有较大的电荷量.同时规定:两粒子之间使目标函数更优的粒子对另一个粒子保持更强的吸引力.仿照电磁理论中带电粒子间电磁力计算公式得:

根据式(3)，每2个粒子间使目标函数较优的粒子将吸引另一个粒子，由于当前最优粒子xbest的目标函数值最小，因此充当着一个绝对吸引粒子，吸引着粒子群中其他所有粒子朝当前最优粒子位置移动.

1.4 移动粒子

计算合力矢量后，按在［0，1］区间内随机分布的步长λ沿合力的方向移动粒子i，计算公式如下:

式中:R为一个向量，对于第i个粒子，其分量表示对应的向上边界uk或下边界lk移动的可行步长.

计算完以上4个步骤，每个粒子的位置得到了更新，也就完成了一次EM算法的迭代过程.

2 EM算法的收敛速度分析

已有研究证明［4］，当迭代次数趋于极限时，种群中至少有一个粒子以概率1移动到全局最优解附近.然而现在还未见有文献对EM法的收敛速度开展专门的研究，围绕着EM法的收敛速度问题，有以下3个方面需要关注:

1)种群规模的设置.对于粒子算法，种群数m设置大虽然可以提高搜索过程中发现最优解的概率，但同时又会增加算法的计算耗时.特别地，对于高维函数优化问题，单纯的增加搜索种群数目反而有可能影响计算效率.对于搜索的粒子数目m取何值时既能保证算法搜索效率，同时计算耗时较小?这一问题值得研究.

2)算法初值敏感性EM算法在每一次迭代过程中，通过吸引其他粒子向当前最优位置移动来搜索更优解.如果在移动过程中找到一个更优位置，则以该粒子为下一次迭代计算的吸引粒子，如此反复直至找到全局最优解.这样就提出一个问题，如果在初始化过程中随机确定的起始搜索粒子偏离最优解位置会否影响算法的搜索效率，特别当搜索空间较大时，这一问题显得更为重要.

3)算法停滞问题.遗传算法存在“早熟”问题，由于局部信息素过多会引起蚁群算法停滞.虽然现有文献证明了EM法必然收敛，但并没有对EM法的停滞问题开展专门的研究.EM法是否存在停滞问题，如果存在，可能的原因是什么，如何解决，这一问题也值得重点研究.

围绕上述3个问题，本节通过2个典型的测试函数对EM法的收敛特性展开了深入的研究.所选取的测试函数及其全局最优解如下［7］:

测试函数1:Six-Hump Camel-back function.

已知最优解为

测试函数2:Sphere function.

最优解为

式中:测试函数1为六峰值驼背函数，该函数共有6个局部极小点，其中2个为全局最小点;测试函数2为球函数，该函数是一个典型的高维单峰值函数.

2.1 EM算法求解

EM算法的初始化过程即首先选取粒子数m，并在问题的可行域内随机指定粒子的初始位置，同时找到使得函数值最小的当前最优粒子，使它充当算法第一次迭代计算中的初始“吸引粒子”.为了测试种群数目及初始最优粒子位置对于EM算法收敛速度的影响，本文对测试函数1取不同粒子数下的收敛性进行了仿真研究，计算结果见图1.

图1 测试函数1取不同粒子数时最优解的进化曲线Fig.1 The solution curves of the best evolution with different particle numbers for test function 1

由图1可知，当所取粒子数较大时(m=50)，经初始化过程确定的起始“吸引粒子”位置较接近于最优解位置.当粒子数种群数较少时，起始“吸引粒子”位置具有随机性.即由初始化过程确定的起始搜索位置有可能接近于最优解空间，也有可能远离最优解空间范围.这一结论也可根据算法初始化含义很容易得出.

对于一般迭代算法，其收敛速度受搜索的起始位置影响较大，为提高算法收敛速度，一般要求设置的起始点尽可能地接近于最优解位置.而对于EM法其收敛速度几乎不受起始“吸引粒子”位置的影响，由图1可知，即使起始“吸引粒子”位置远离最优解空间，EM算法也可以在极短的迭代步数内收敛到最优解邻近空间.这说明EM算法具有非常强的全局搜索能力.以变量区间长度为10的测试函数1为例，经本文多次测试，在最多不超过10次迭代步数内，问题的搜索解空间都将收敛到距离最优解非常小的区间内，这里将搜索解空间大小定义为

式中:f*为当前最优解，fglob为全局最优解.另外，从本文对测试函数2的实验结果(图2所示)可以得出与前述测试函数1相似的结论，这说明当目标函数变量区间取值范围较大时，EM算法同样保持了非常强的全局搜索能力.

由图1和图2可知，当EM算法搜索到最优解邻近区域时，算法的搜索速度明显减慢甚至出现停滞.原因之一是当前最优解已接近于全局最优解，其收敛幅度相应会减小.另外，从算法本身构造分析不难发现，粒子群向最优解区域聚积过程也可能影响算法的收敛速度.图3所示为测试函数1经30次EM算法迭代计算前种群(m=10)初始位置和更新后的位置分布.因为在最优解的“吸引”下，粒子群将逐渐向最优解区域聚积，随着最优解邻近区域内粒子密度的增大，粒子之间极易达成一种动态力平衡状态，此时加载在粒子上的“合力”将趋于0.由于EM算法是通过计算“合力”获取下一步的搜索信息，合力趋于0时显然不利于最优解的搜索.

图2 测试函数2取不同粒子数时最好解的进化曲线Fig.2 The solution curves of the best evolution with different particle numbers for test function 2

图3 EM迭代计算前后粒子位置的分布Fig.3 The distribution of particle positions before and after the iterative calculation

2.2 基于EM算法和变步长法组合计算

由上述分析可知，在EM算法搜索后期，由于粒子聚集有可能造成算法收敛速度下降甚至出现停滞.虽然在EM算法中引入局部搜索机制可改善这一情况，但由于计算所得合力非常小，从而造成全局搜索信息的丢失，此时EM算法主要依靠局部搜索过程寻优，这势必会影响算法的求解效率.

注意到EM算法前期收敛速度非常快，并且可确保收敛到问题的近似最优解.而对于一般迭代算法，如果设置的搜索起始点已接近于最优，则可极大地提高其优化速度.为解决算法后期搜索停滞问题，一种可行的策略是摒弃EM算法的后期搜索过程，通过其他优化方法对EM算法前期优化结果进行二次优化搜索问题的最优解.

假设目标函数一阶信息可求，为实时求出问题的精确解，采用变尺度法对EM算法前期优化结果进行二次优化.即首先采用EM算法快速搜索问题真实解的邻域解，如果该解满足问题求解的精度要求，则停止计算;否则，以该近似解为初始值，采用变尺度法进一步搜索问题的精确解.测试函数仍选取测试函数1，程序流程见图4.其中，种群数m取10，EM算法计算程序最大迭代步数取30，计算中矩阵H采用如下公式计算［8］:

图4 EM-DFP算法计算流程Fig.4 The flow chart of EM-DFP algorithm

在实际计算中，本文只进行了1次二次搜索过程，即变尺度法计算的最大迭代步长取1.对测试函数1连续测试15次，每个计算序列经EM算法一次优化和变尺度法二次优化所得的函数最小值见图5.由图5所示结果可知，经二次优化后的求解精度得到较大的提高;并且与EM算法后期搜索过程相比(见图1、图2)，二次优化的寻优效率大大超过了EM算法.在本文的计算实例中，即使只进行1次二次搜索过程，也可以迅速地逼进问题的最优解.

图5 对连续15次计算结果进行二次优化的结果Fig.5 Quadratic optimization results for the results of continuous 15

3 优化参数选取及EM算法改进

根据实验结果，可得如下结论:

1)种群数的选择应综合考虑搜索效率和计算耗时.由前述分析可知，种群数目m取值较大时，虽然起始搜索位置相对较接近最优解位置，但增加种群数m会增加计算量，特别地，对于高维优化问题，单纯增加种群数m反而可能降低算法的计算效率.另外，如果初始粒子数过多，在粒子向最优区域聚积过程中，粒子之间达成动态力平衡状态的机率大大增加，由前文分析可知，这一状态不利于最优解的搜索.

根据前文结果可知，EM算法对于起始搜索位置并不敏感，即EM算法具有较强的全局搜索能力.以图1结果为例，虽然不同粒子数目收敛到近似最优解的迭代步数约15步，但m取50时计算耗时要远远大于其他m取值较小的情况.对于种群数m的选择目前还没有一个固定的标准.基于以上的结果，笔者认为对于一般的连续函数优化问题，采用EM算法计算的搜索种群数目在［2，10］整数区间上取值即可满足计算效率和精度的要求.在计算过程中，考虑到问题的维数及方程的复杂度等因素可适当地增加搜索粒子数量m.

2)EM算法搜索过程具有随机性且算法搜索后期可能出现停滞.EM算法的前期收敛速度非常快，在粒子移动过程中，如果某个粒子更新后的位置刚好落到最优解位置，则此时可以迅速地确定问题的最优解.但更一般的情况是各个粒子向最优解区域聚积的过程中，由于粒子间相互排斥和吸引，使得计算合力F可能等于0或趋近于0，此时EM算法法的收敛机制基本失效，粒子位置的更新完全依赖于局部信息，从而造成算法收敛非常缓慢甚至出现停滞，从近似最优解逼近于全局最优解所需的迭代步数大大增加，算法搜索效率较低.

3)结合二次搜索策略可显著提高算法的收敛速度和精度.在粒子聚积过程中，合力F为0的情况难以避免，因此依靠EM算法本身的收敛机制无法解决这一问题.一种有效的解决方式是将EM算法和其他优化方法相结合，采取组合的计算方式.由于此时只需要EM算法计算问题的近似最优解，因此可只保留EM算法前期搜索计算过程，从而进一步地提高了计算效率.

从EM算法本身构造考虑，可从以下2个方面对算法进行改进:

1)局部搜索.在实际优化问题中，如果只需要知道其近似最优解，为了提高计算效率，在计算过程中可考虑忽略局部搜索过程，必要时候只对当前最优粒子进行局部搜索，另外也可从改进局部搜索性能角度加快算法的收敛速度.

2)合力计算和粒子的移动方向.标准EM算法采用式(3)计算合力F，显然，只要保证粒子在力的作用下朝更优粒子区域移动，该力的构造公式并不是惟一的，同时式(3)也不是最优的.考虑这样一种情况:对于当前粒子，当另外2个粒子同时吸引该粒子时，如果较优粒子距离当前粒子相对较远，根据式(3)，其对当前粒子的“吸引力”将被减弱，此时当前粒子就有可能朝较劣粒子区域移动.这一过程可以用图6来说明.如图6所示，拉大粒子之间的距离虽然不改变两者之间作用力的方向，但力大小将降低，此时将使得合力方向偏向另一个粒子(F1偏向F2)，图6(b)显然不利于最优解的搜索，解决办法之一是弱化或忽略计算公式中粒子间的距离项，即式(3)的分母项;或者通过其他强化较优粒子作用力的方式使得合力的方向偏向较优粒子区域以提高算法的收敛速度.

图6 力矢量合成及粒子移动方向Fig.6 Composition of forces and particle direction of movement

4 结束语

利用EM算法前期收敛速度快，且易于与其他优化方法相结合的特点，将EM算法与其他局部优化方法混合，或与其他性能强大的搜索方法相结合，可从根本上解决算法搜索后期收敛速度缓慢问题.另外，对于算法中力的计算方式及参数进行优化调整，可进一步提高算法的优化性能.目前，通过一些实验和比较已经显示出了EM算法的强大性和优越性，对EM算法及其应用开展深入的研究是一个非常有意义的研究方向.

［1］赵云丰，尹怡欣，付冬梅，等.禁忌免疫网络算法及其在函数优化中的应用［J］.智能系统学报，2008，3(5):394-400.ZHAO Yunfeng，YIN Yixin，FU Dongmei，et al.Application of a Tabu immune network algorithm in function optimizations［J］.CAAI Transactions on Intelligent Systems，2008，3(5):394-400.

［2］周建新，杨卫东，李擎.求解连续函数优化问题的改进蚁群算法及仿真［J］.系统仿真学报，2009，21(6):1685-1688.ZHOU Jianxin，YANG Weidong，LI Qing.Improved ant colony algorithm and simulation for continuous function optimization［J］.Journal of System Simulation，2009，21(6):1685-1688.

［3］BIRBIL S I，FANG S C.An electromagnetism-like mechanism for global optimization［J］.Journal of Global Optimization，2003，23(3):263-282.

［4］BIRBIL S L，FANG S C，SHEU R L.On the convergence of a population-based global optimization algorithm ［J］.Journal of Global Optimization，2004，30(2):301-318.

［5］WANG Xiaojuan，GAO Liang，ZHANG Chaoyong.Electromagnetism-like mechanism based algorithm for neural network training［J］.Lecture Notes in Computer Science，2008，5227:45-47.

［6］DIETER D，De REYCK B，LEUS R，et al.A hybrid scatter search/electromagnetism meta-heuristic for project scheduling［J］.European Journal of Operational Research，2006，169(2):638-653.

［7］YAO Xin，LIU Yong，LIN Guangming.Evolutionary programming made faster［J］.IEEE Transactions on Evolutionary Computation，1999，3(2):82-102.

［8］陈宝林.最优化理论与算法［M］.北京:清华大学出版社，2005:372-375.