第5卷第3期 智能系统学报 Vol.5 No.3 2010年6月 CAAI Transactions on Intelligent Systems Jun.2010 doi:10.3969/i.issn.1673-4785.2010.03.008 结合变尺度法的改进类电磁机制算法 印峰，王耀南，杨易旻，曹文明 (湖南大学电气与信息工程学院，湖南长沙410082)》 摘要：标准类电磁机制算法处理连续函数优化问题时存在最优参数选取和收敛速度问题.数值实验研究表明类电 磁算法不具备初值敏感性，并在搜索后期算法收敛速度缓慢甚至可能出现停滞.数值实验分析指出粒子之间达成动 态力平衡状态是造成算法停滞的可能原因之一，提出一种解决策略是摒弃EM算法后期搜素过程，结合变尺度法对 EM算法前期搜索到的近似最优值进行二次优化.该混合计算方法将二者的优势相结合，实验结果表明新方法在保 证计算实时性的同时，取得了较高的计算精度.最后，对EM算法本身构造提出一些改进意见，并初步建立用于连续 函数优化的EM算法计算框架，为后续更深入的研究EM算法提供参考. 关键词：连续函数优化；类电磁算法；变尺度法；二次优化 中图分类号：TP301.6文献标识码：A文章编号：16734785(2010)03025406 An improved electromagnetism-like mechanism algorithm combined with the DFP method YIN Feng,WANG Yao-nan,YANG Yi-min,CAO Wen-ming (College of Electrical and Information Engineering,Hunan University,Changsha 410082,China) Abstract:When optimizing a continuous function using a standard electromagnetism-like mechanism (EM),there are known problems,including selection of optimal parameters and convergence speed.Numerical simulations indi- cate that EM is not sensitive to initial values,but algorithm convergence is slow and may even stagnate in the latter part of a search.One of the possible causes for stagnation is the equilibrium of dynamic forces between particles.In order to improve the performance of the EM,instead of the latter search process,a quadratic optimization method was proposed.When combined with the Davidon-Fletcher-Powell (DFP)method,it optimized the approximate op- timal results obtained by a pre-search with the EM algorithm.This hybrid method fully exploits the strengths of the EM method and the DFP method.Experimental results showed it to be more efficient and precise.Finally,some improvements were made to the construction of the EM and a framework for the EM method was established that al- lows continuous function optimization.These results provide a reference for more in-depth study of the EM algo- rithm. Keywords:continuous function optimization;electromagnetism-like algorithm;Davidon-Fletcher-Powell method; quadratic optimization 在求解函数优化问题过程中，如果待优化问题想[12].近年来，Birbil等学者受电磁学中带电粒子 的目标函数较为复杂，或其一、二阶信息难以获取间“排斥-吸引”力的启发，提出一种新的用于求解 时，一般传统的优化方法不再适合求解这类问题.而 含有界变量约束问题的全局收敛算法—类电磁算 启发式的随机搜索方法是求解此类全局优化问题的 法3]，通过选取15个函数组成的综合测试函数集对 有效途径之一，至今已得到广泛应用的模拟退火算 EM(electromagnetism-like mechanism)算法性能进 法、遗传算法及蚁群算法等都采用了随机搜索的思 行了测试，并与经典优化方法进行了比较，测试结果 表明EM算法可收敛到问题的最优解，并且显示出 收稿日期：2009-12-15. 更好的优化性能.文献[4]进一步从理论上证明了 基金项目：国家科技支撑计划资助项目(2008BAF36B01):国家“863” 计划资助项目(2008AA04Z214). EM算法依分布全局收敛于问题的ε-最优解.目前， 通信作者：印峰.E-mail:yinfeng83@126.com EM算法在函数优化、神经网络训练、TSP以及项目
第3期 印峰，等：结合变尺度法的改进类电磁机制算法 .255. 调度问题上已得到了初步的应用，并取得了很好的 e(x)-e(xbom 优化结果3,561 g=exp (2) ∑(e(t)-e(x) 虽然对EM算法的研究在理论和工程应用上已 取得了一定的进展，但和遗传算法、蚁群算法等传统 根据式(2)，目标函数较优的粒子将拥有较大 优化方法相比，目前对于EM算法的研究还非常有 的电荷量.同时规定：两粒子之间使目标函数更优的 限.本文所做的工作是：围绕算法初值敏感性问题、 粒子对另一个粒子保持更强的吸引力.仿照电磁理 种群规模选取及其对算法的收敛速度影响、算法收 论中带电粒子间电磁力计算公式得： 敛速度及停滞等问题对EM法开展了深入的研究. xi,e)<e() 结合本文的研究结果提出了一种优化的计算框架， F 采用该混合优化策略可将EM法和DP法二者的 e(x)≥ex). 优势相结合，保证计算的有效性和实时性， (3) 1类电磁机制算法的原理 根据式(3)，每2个粒子间使目标函数较优的粒 子将吸引另一个粒子，由于当前最优粒子x的目标 EM法首先随机地从可行域中产生一组初始 函数值最小，因此充当着一个绝对吸引粒子，吸引着 解，并将每一个解想象成空间中的一个带电粒子；通 粒子群中其他所有粒子朝当前最优粒子位置移动， 过模拟电磁理论中带电粒子间吸引一排斥机制使得 1.4移动粒子 粒子种群朝最优解区域移动，每个粒子下一步的移 计算合力矢量后，按在[0,1]区间内随机分布 动方向通过计算其他粒子施加给当前粒子的合力方 的步长入沿合力的方向移动粒子，计算公式如下： 向来确定，同电磁力的计算方式一样，该合力是通过 将来自其他粒子的力进行矢量叠加得到的.这样，每 = FR,i=12,…,m（4) 完成一次迭代计算就产生一组新的更优解.一个 式中：R为一个向量，对于第i个粒子，其分量表示 维变量约束优化问题可用如下方程描述： 对应的向上边界“或下边界移动的可行步长 min f(x),s.l.x∈[l,u], 计算完以上4个步骤，每个粒子的位置得到了 [l,4]:={x∈R"|l%≤xe≤%，k=1,2,…,n. 更新，也就完成了一次EM算法的迭代过程. 采用EM算法求解上述优化问题主要包括以下 4个基本步骤：初始化、局部搜索、电荷量和合力计 2 EM算法的收敛速度分析 算以及移动粒子的过程 已有研究证明41，当迭代次数趋于极限时，种 1.1初始化 群中至少有一个粒子以概率1移动到全局最优解附 在进行迭代计算前，需要进行初始化，即从可行 近.然而现在还未见有文献对EM法的收敛速度开 域内均匀地随机抽取m个样本点{x,x2,…,x}作 展专门的研究，围绕着EM法的收敛速度问题，有以 为初始解，其中x=(x,x,…,x),i=1,2,…,m 下3个方面需要关注： 随机抽样过程可采用式(1)实现： 1)种群规模的设置.对于粒子算法，种群数m x*=lk+rand(k-lk),k=1,2,…,n.(1) 设置大虽然可以提高搜索过程中发现最优解的概 抽取到所有样本点后，计算出每个样本点对应的目 率，但同时又会增加算法的计算耗时.特别地，对于 标函数值，并将目标函数值最优的样本点记为x. 高维函数优化问题，单纯的增加搜索种群数目反而 1.2局部搜索 有可能影响计算效率，对于搜索的粒子数目m取何 局部搜索过程用来改进当前样本点，即搜索样 值时既能保证算法搜索效率，同时计算耗时较小？ 本点邻域范围内的更优解，如果这样的更优样本点 这一问题值得研究 存在，则用更优样本点代替当前已搜索到的样本点. 2)算法初值敏感性EM算法在每一次迭代过程 局部搜索的对象可以是整个样本点，也可以只对当 中，通过吸引其他粒子向当前最优位置移动来搜索 前最优样本点进行局部搜索。 更优解.如果在移动过程中找到一个更优位置，则以 1.3电荷量及合力矢量计算 该粒子为下一次迭代计算的吸引粒子，如此反复直 EM算法通过计算施加到每个粒子上的合力获 至找到全局最优解。这样就提出一个问题，如果在初 取下一步的搜索信息，首先需要确定每个粒子的电 始化过程中随机确定的起始搜索粒子偏离最优解位 荷量，构造公式如下： 置会否影响算法的搜索效率，特别当搜索空间较大
·256 智能系统学报 第5卷 时，这一问题显得更为重要， 1.5f 一m=50 3)算法停滯问题.遗传算法存在“早熟”问题， 1.0 由于局部信息素过多会引起蚁群算法停滞.虽然现 ® 0.5 有文献证明了EM法必然收敛，但并没有对EM法 0 的停滞问题开展专门的研究.EM法是否存在停滞 -0.5 问题，如果存在，可能的原因是什么，如何解决，这一 -1.0 问题也值得重点研究. 围绕上述3个问题，本节通过2个典型的测试 1.50 1015202530 函数对EM法的收敛特性展开了深人的研究.所选 迭代数 取的测试函数及其全局最优解如下刀： (b)取较大粒子数 测试函数l:Six-Hump Camel--back function. 图1测试函数1取不同粒子数时最优解的进化曲线 Fig.1 The solution curves of the best evolution with differ- 斤=4城-2.1财+写+x-4城+4， ent particle numbers for test function 1 xe[-5,5]. 由图1可知，当所取粒子数较大时(m=50), 已知最优解为 经初始化过程确定的起始“吸引粒子”位置较接近 min(f)=-1.0316285, 于最优解位置.当粒子数种群数较少时，起始“吸引 xmim=(0.08983,-0.7126), 粒子”位置具有随机性.即由初始化过程确定的起 (-0.08983,0.7126). 始搜索位置有可能接近于最优解空间，也有可能远 测试函数2：Sphere function. 离最优解空间范围.这一结论也可根据算法初始化 含义很容易得出. f(x)= ∑号，-100≤x≤100， 对于一般迭代算法，其收敛速度受搜索的起始 最优解为 位置影响较大，为提高算法收敛速度，一般要求设置 的起始点尽可能地接近于最优解位置.而对于EM min(f2)=f2(0,…,0)=0. 法其收敛速度几乎不受起始“吸引粒子”位置的影 式中：测试函数1为六峰值驼背函数，该函数共有6个 响，由图1可知，即使起始“吸引粒子”位置远离最 局部极小点，其中2个为全局最小点；测试函数2为球 优解空间，EM算法也可以在极短的迭代步数内收 函数，该函数是一个典型的高维单峰值函数 敛到最优解邻近空间.这说明EM算法具有非常强 2.1EM算法求解 的全局搜索能力.以变量区间长度为10的测试函数 EM算法的初始化过程即首先选取粒子数m, 1为例，经本文多次测试，在最多不超过10次迭代 并在问题的可行域内随机指定粒子的初始位置，同 步数内，问题的搜索解空间都将收敛到距离最优解 时找到使得函数值最小的当前最优粒子，使它充当 非常小的区间内，这里将搜索解空间大小定义为 算法第一次迭代计算中的初始“吸引粒子”.为了测 d=lf°-fb1. 试种群数目及初始最优粒子位置对于EM算法收敛 式中：f°为当前最优解，fb为全局最优解.另外，从 速度的影响，本文对测试函数1取不同粒子数下的 本文对测试函数2的实验结果（图2所示）可以得 收敛性进行了仿真研究，计算结果见图1. 出与前述测试函数1相似的结论，这说明当目标函 数变量区间取值范围较大时，EM算法同样保持了 6 一m=6 非常强的全局搜索能力. ,-m=8 4 .+m=10 由图1和图2可知，当EM算法搜索到最优解 3 邻近区域时，算法的搜索速度明显减慢甚至出现停 驃 : 滞.原因之一是当前最优解已接近于全局最优解，其 收敛幅度相应会减小.另外，从算法本身构造分析不 0 难发现，粒子群向最优解区域聚积过程也可能影响 算法的收敛速度.图3所示为测试函数1经30次 0 1015202530 EM算法迭代计算前种群(m=10)初始位置和更新 迭代数 后的位置分布.因为在最优解的“吸引”下，粒子群 (a)取较少粒子数 将逐渐向最优解区域聚积，随着最优解邻近区域内 粒子密度的增大，粒子之间极易达成一种动态力平
第3期 印峰，等：结合变尺度法的改进类电磁机制算法 257 衡状态，此时加载在粒子上的“合力”将趋于0.由于 2.2基于EM算法和变步长法组合计算 EM算法是通过计算“合力”获取下一步的搜索信 由上述分析可知，在EM算法搜索后期，由于粒 息，合力趋于0时显然不利于最优解的搜索。 子聚集有可能造成算法收敛速度下降甚至出现停 3.0X10 滞.虽然在EM算法中引入局部搜索机制可改善这 一m=5 一情况，但由于计算所得合力非常小，从而造成全局 2.5 ·m=10 ·-m=50 搜索信息的丢失，此时EM算法主要依靠局部搜索 2.0 过程寻优，这势必会影响算法的求解效率。 扫 1.5日 注意到EM算法前期收敛速度非常快，并且可 图 1.0 确保收敛到问题的近似最优解.而对于一般迭代算 0.5 法，如果设置的搜索起始点已接近于最优，则可极大 地提高其优化速度.为解决算法后期搜索停滞问题， 04 10 2030 40 50 种可行的策略是摒弃EM算法的后期搜索过程， 迭代数 通过其他优化方法对EM算法前期优化结果进行二 图2测试函数2取不同粒子数时最好解的进化曲线 次优化搜索问题的最优解. Fig.2 The solution curves of the best evolution with differ 假设目标函数一阶信息可求，为实时求出问题 ent particle numbers for test function 2 5r 的精确解，采用变尺度法对EM算法前期优化结果 ·初始位置 4 o最优解 进行二次优化.即首先采用EM算法快速搜索问题 3 +更新位置 真实解的邻域解，如果该解满足问题求解的精度要 1 求，则停止计算；否则，以该近似解为初始值，采用变 0+ p 尺度法进一步搜索问题的精确解.测试函数仍选取 11 测试函数1，程序流程见图4.其中，种群数m取10， -2 3 EM算法计算程序最大迭代步数取30，计算中矩阵 45 H采用如下公式计算[81： H1=I, k=1; 图3EM迭代计算前后粒子位置的分布 Fig.3 The distribution of particle positions before and after H.(pc qrHg,’ k≠1. the iterative calculation 开始 「初始化各粒子 给定初始点x=x 对当前粒子进行局部搜索 令H=L计算x”处的梯度值 更新当前粒子位置 g=Velx) 搜 根据式2)、3)计算每个 粒子代表的电荷及所受合力 根据式(4)更新粒子位置 计算第次送代搜索方向-山，g 计算搜索步长1 达到最大迭代次数 或满足指定精 xxd 精搜索 Y 输出问题近似最优解x I7exI≤e> N g=ve),p qK)=gk1-8& 输出结果：r=x 计算Hk=k+I 图4EM-DFP算法计算流程 Fig.4 The flow chart of EM-DFP algorithm
·258 智能系统学报 第5卷 在实际计算中，本文只进行了1次二次搜索过 增加搜索粒子数量m, 程，即变尺度法计算的最大迭代步长取1.对测试函 2)EM算法搜索过程具有随机性且算法搜索后 数1连续测试15次，每个计算序列经EM算法一次 期可能出现停滞.EM算法的前期收敛速度非常快， 优化和变尺度法二次优化所得的函数最小值见图 在粒子移动过程中，如果某个粒子更新后的位置刚 5.由图5所示结果可知，经二次优化后的求解精度 好落到最优解位置，则此时可以迅速地确定问题的 得到较大的提高；并且与EM算法后期搜索过程相 最优解.但更一般的情况是各个粒子向最优解区域 比（见图1、图2），二次优化的寻优效率大大超过了 聚积的过程中，由于粒子间相互排斥和吸引，使得计 EM算法.在本文的计算实例中，即使只进行1次二 算合力F可能等于0或趋近于0，此时EM算法法 次搜索过程，也可以迅速地逼进问题的最优解。 的收敛机制基本失效，粒子位置的更新完全依赖于 局部信息，从而造成算法收敛非常缓慢甚至出现停 -0.80 中·一次优化于 滞，从近似最优解逼近于全局最优解所需的迭代步 -0.85 二次优化： 数大大增加，算法搜索效率较低。 3)结合二次搜索策略可显著提高算法的收敛 -0.9( 11 11 速度和精度.在粒子聚积过程中，合力F为0的情 1 -0.95 1 况难以避免，因此依靠EM算法本身的收敛机制无 -1.00 法解决这一问题.一种有效的解决方式是将EM算 法和其他优化方法相结合，采取组合的计算方式.由 -1.0 0 0 于此时只需要EM算法计算问题的近似最优解，因 计算序列 此可只保留EM算法前期搜索计算过程，从而进一 图5 对连续15次计算结果进行二次优化的结果 步地提高了计算效率 Fig.5 Quadratic optimization results for the results of con- 从EM算法本身构造考虑，可从以下2个方面 tinuous 15 对算法进行改进： 3 优化参数选取及EM算法改进 1)局部搜索.在实际优化问题中，如果只需要 知道其近似最优解，为了提高计算效率，在计算过程 根据实验结果，可得如下结论： 中可考虑忽略局部搜索过程，必要时候只对当前最 1)种群数的选择应综合考虑搜索效率和计算耗 优粒子进行局部搜索，另外也可从改进局部搜索性 时.由前述分析可知，种群数目m取值较大时，虽然 能角度加快算法的收敛速度。 起始搜索位置相对较接近最优解位置，但增加种群数 2)合力计算和粒子的移动方向.标准EM算法 m会增加计算量，特别地，对于高维优化问题，单纯增 采用式(3)计算合力F,显然，只要保证粒子在力的 加种群数m反而可能降低算法的计算效率另外，如 作用下朝更优粒子区域移动，该力的构造公式并不 果初始粒子数过多，在粒子向最优区域聚积过程中， 是惟一的，同时式(3)也不是最优的.考虑这样一种 粒子之间达成动态力平衡状态的机率大大增加，由前 情况：对于当前粒子，当另外2个粒子同时吸引该粒 文分析可知，这一状态不利于最优解的搜索 子时，如果较优粒子距离当前粒子相对较远，根据式 根据前文结果可知，EM算法对于起始搜索位 (3),其对当前粒子的“吸引力”将被减弱，此时当前 置并不敏感，即EM算法具有较强的全局搜索能力. 粒子就有可能朝较劣粒子区域移动.这一过程可以 以图1结果为例，虽然不同粒子数目收敛到近似最 用图6来说明.如图6所示，拉大粒子之间的距离虽 优解的迭代步数约15步，但m取50时计算耗时要 然不改变两者之间作用力的方向，但力大小将降低， 远远大于其他m取值较小的情况.对于种群数m的 此时将使得合力方向偏向另一个粒子(F,偏向 选择目前还没有一个固定的标准.基于以上的结果， F2),图6(b)显然不利于最优解的搜索，解决办法 笔者认为对于一般的连续函数优化问题，采用EM 之一是弱化或忽略计算公式中粒子间的距离项，即 算法计算的搜索种群数目在[2,10]整数区间上取 式(3)的分母项；或者通过其他强化较优粒子作用 值即可满足计算效率和精度的要求.在计算过程中， 力的方式使得合力的方向偏向较优粒子区域以提高 考虑到问题的维数及方程的复杂度等因素可适当地 算法的收敛速度
第3期 印峰，等：结合变尺度法的改进类电磁机制算法 ·259 较优粒子 1685-1688. ● [3]BIRBIL S I,FANG S C.An electromagnetism-like mecha- F nism for global optimization[J].Journal of Global Optimiza- F tion,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]. 当前粒子 较劣粒子 Joumal of Global Optimization,2004,30(2):301-318. (a)偏向较优粒子 [5]WANG Xiaojuan,GAO Liang,ZHANG Chaoyong.Electro- magnetism-like mechanism based algorithm for neural net- 较优粒子 work training[J].Lecture Notes in Computer Science, ● 2008,5227:4547. [6]DIETER D,De REYCK B,LEUS R,et al.A hybrid scat- ter search/electromagnetism meta-heuristic for project scheduling[J].European Joural of Operational Research, 2006,169(2):638653. ● [7]YAO Xin,LIU Yong,LIN Guangming.Evolutionary pro- 当前粒子 较劣粒子 gramming made faster[J].IEEE Transactions on Evolution- (b)偏向较劣粒子 ary Computation,1999,3(2):82-102. 图6力矢量合成及粒子移动方向 [8]陈宝林.最优化理论与算法[M]北京：清华大学出版 Fig.6 Composition of forces and particle direction of move- 社，2005：372-375， ment 作者简介： 印峰，男，1983年生，博士研究 4结束语 生，主要研究方向为机器人控制及人工 利用EM算法前期收敛速度快，且易于与其他 智能计算。 优化方法相结合的特点，将EM算法与其他局部优 化方法混合，或与其他性能强大的搜索方法相结合， 可从根本上解决算法搜索后期收敛速度缓慢问题， 另外，对于算法中力的计算方式及参数进行优化调 王耀南，男，1957年生，教授、博士 整，可进一步提高算法的优化性能.目前，通过一些 生导师，湖南大学电气与信息工程学院 实验和比较已经显示出了EM算法的强大性和优越 院长，国家高效磨削工程技术研究中心 性，对EM算法及其应用开展深入的研究是一个非 副主任，教育部输变电新技术工程研究 常有意义的研究方向. 中心主任，国际EEE高级会员，国际自 动控制联FAC会员，中国人工智能学 参考文献： 会、自动化学会、电机工程学会理事.主要研究方向为智能机 器人、智能信息处理和智能控制.目前在研国家级科研项目 [1]赵云丰，尹怡欣，付冬梅，等.禁忌免疫网络算法及其在 函数优化中的应用[J].智能系统学报，2008,3(5)： 共5项，获国家科学技术进步二等奖3项，湖南科学技术进 步一等奖等其他奖励多项.发表学术论文300余篇，出版专 394400. ZHAO Yunfeng,YIN Yixin,FU Dongmei,et al.Applica- 著和教材4部. tion of a Tabu immune network algorithm in function optimi- 杨易旻，男，1982生，博士研究生， zations [J].CAAI Transactions on Intelligent Systems, 主要研究方向为机器人智能控制、智能 2008,3(5):394400. 信息处理。 [2]周建新，杨卫东，李擎.求解连续函数优化问题的改进蚁 群算法及仿真[J].系统仿真学报，2009,21(6)：1685- 1688. ZHOU Jianxin,YANG Weidong,LI Qing.Improved ant colony algorithm and simulation for continuous function opti- mization[J].Journal of System Simulation,2009,21(6):
