基于分子动力学模拟的改进混合蛙跳算法.DOC

1、基于分子动力学模拟的改进混合蛙跳算法张潇丹，胡峰，赵力，邹采荣（东南大学 信息科学与工程学院 水声信号处理教育部重点实验室 南京 210096）摘要：针对基本的混合蛙跳算法（shuffled frog leaping algorithm, SFLA）后期搜索速度变慢，容易陷入局部最优解的缺点，借鉴分子动力学（molecular dynamics, MD）模拟的思想，本文提出一种基于分子动力学模拟的改进的混合蛙跳算法。该算法将种群中的粒子等效成分子，并提出一种新的分子间作用力计算方法来代替两体间经典的Lennard-Jones 作用力计算方法，利用 Velocity-Verlet 算法和高斯变异

2、算子代替基本混合蛙跳算法的更新策略，有效地平衡了种群的多样性和搜索的高效性。高维多峰函数测试的结果表明，基于分子动力学模拟的改进混合蛙跳算法能提高算法后期跳出局部极值的能力，全局寻优能力明显优于基本的混合蛙跳算法。关键词：分子动力学, 混合蛙跳算法, 分子间作用力，Velocity-Verlet 算法，高斯变异中国分类号：TP301Improved Shuffled Frog Leaping Algorithm Based On Molecular Dynamics SimulationsZhang Xiao-dan , Hu Feng, Zhao Li, Zou Cai-rong(Key L

3、aboratory of Underwater Acoustic Signal Processing of Ministry of Education, School of Information Science and Engineering, Southeast University, Nanjing, 210096, China)Abstract: In order to overcome the defects of shuffled frog leaping algorithm (SFLA) such as slow searching speed in the late evolu

4、tion and easily trapping into local extremum, an Improved Shuffled Frog Leaping Algorithm (ISFLA) based on the basic ideas of Molecular Dynamics (MD) simulations is put forward in this paper in which the population is regarded as molecular system. We propose a new intermolecular force instead of the

5、 classic two-body Lennard-Jones force and use Velocity-Verlet algorithm and Gaussian mutation instead of the original SFLA update strategy, which balance the population diversity and search efficiency effectively. The test results on high-dimensional and multi-modal optimization problems indicate th

6、at ISFLA improves the capacity of escaping from local maximum and the global searching performance is superior to SFLA.Key words: Molecular Dynamics (MD), Improved Shuffled Frog Leaping Algorithm (ISFLA), intermolecular force, Velocity-Verlet algorithm, Gaussian mutation1. 引 言混合蛙跳算法（Shuffled Frog Le

7、aping Algorithm, SFLA） 1-3是 2003 年由 Eusuff 和 Lansey 提出的一种基于群体智能的后启发式计算技术。全局信息交换和局部深度搜索的平衡策略使得 SFLA 能够跳出局部极值点，但是在进化后期 SFLA 容易陷入局部最优解，对于多峰值函数寻优这种较复杂的问题，很难搜索到最优解，计算精度也不高。混合蛙跳算法提出时间不长，无论在理论还是实践方面都处于起步阶段。文献4提出基于阈值选择的策略，减小个体空间差异，改善算法性能；文献5在局部搜索策略中引入调整序思想，同时在全局信息交换中加入变异操作。这些算法都不同程度的提高了算法的收敛速度和精度，但效果并不理想。分子

8、动力学（Molecular Dynamics, MD）是用来研究物质在原子尺度下物理性质的有效手段 6-7，利用原子间的相互作用力计算并确定位形的转变，得出平衡体系随时间演变的规律。文献8利用 MD 模拟了不同温度下气体混合物在纳米管道内的流动，文献9利用MD 方法研究了 SiO2 体系中 Si、O 原子电荷转移的问题，文献10采用 MD 方法描述了 C 纳米管内 C 原子之间的相互作用，文献11研究了类金刚石薄膜的纳米压痕分子动力学过程。本文将种群中的个体等效成分子，将分子动力学引入到 SFLA 算法中，利用分子间的吸引力求解分子的牛顿运动方程，得到微观粒子的运动轨迹，同时为了保证种群的多样

9、性，避免早熟问题，引入高斯变异算子，从而代替原有的 SFLA 算法进化策略，构建出了一种改进的混合蛙跳算法（Improved Shuffled Frog Leaping Algorithm, ISFLA） 。仿真结果表明， ISFLA 计算精度高、收敛速度快，具有较强的鲁棒性，寻优性能较 SFLA 有明显的提高。2. 改进的混合蛙跳算法2.1.SFLA 算法概述SFLA是 2003年由 Eusuff和Lansey 提出的一种新的群体智能优化算法，它概念简单，参数少，计算速度快，全局寻优能力强。在一个 维的目标搜索空间中，随机生成 只青DP蛙（解）组成初始群体，第 只青蛙表示问题的解为i。青蛙个

10、体按适应度值从优到劣排12(,.)iiiXx列，将整个群体分为 个子群体。其中排名第1的青M蛙分入第1子群体，排名第2的青蛙分入第2子群体，第只青蛙分入第 子群体，第 +1只青蛙分入第1子群体，第 +2只青蛙分入第2子群体，依次类推，直到全部青蛙划分完毕。每个子群体进行局部深度搜索，即在子群体的每次迭代中，首先确定当前迭代中子群体的最差个体 、wX最好个体 和全局最好个体 ，只对该子群体当前bXgX最差的个体 进行更新，更新策略为：w(1)maxax()()ibwiDrandD位置更新为：(2)wieX其中，rand()是均匀分布在0,1之间的随机数；表示青蛙所允许更新步长的最大值。如果max

11、D的适应度值优于原来的 ，则取代原来种群中wneXw的解。如果没有改进，则用 取代 重复执行更新gXb策略（1） （2） 。如果仍没有改进，则随机产生一个新的解取代原来的 。重复这种更新操作，直至满足子w群体的更新代数。当所有子群体的局部深度搜索完成以后，将所有的青蛙个体重新混合排序并再次划分子群体，然后再进行局部深度搜索，如此反复直到满足混合迭代次数。2.2.分子动力学模型从 SFLA 的更新策略可以看出，最差个体实际上是在局部最优个体或者全局最优个体的吸引下，不断朝着更优的方向进化，其余个体并不对最差个体的进化产生任何影响。因此在分子动力学模型中我们仅仅需要考虑最差和最优个体相互之间的吸引

12、力，并且距离越大，吸引力越强。在动力学研究中，经典的 Lennard-Jones 力模拟两分子间的作用力：(3)137(|)Frr其中， 为两分子间的位移矢量， 为两分子间的距r |离， 为常数。从物理意义上讲公式（3）括号中的,第一项对应于两体在近距离时以斥力为主，第二项对应于两体在远距离时以吸引力为主，因此不适合本文所提算法的要求。在 SFLA 算法中分子间只存在引力吸引，且随着距离的增大，引力增强。本文仅考虑最差个体与全局最优个体之间的引力，提出如下的策略：(4)|rFe式（4）中 为比例系数，常数； 为最差和全局最优个体间的位移矢量， 为分子间的距离。假设各粒子|r的质量 相等且为 1

13、，则加速度矢量为：m(5)|/raFmeVerlet 算法是分子动力学研究里使用最广泛的算法12。它的思想基于对原子位置 进行 Taylor 展开到三r阶，计算原子的下一时刻的位置和速度。Verlet 算法中速度的误差与时间步长的二次项有关，位置的误差却与步长的四次项有关，且整个计算量庞大，不易实现。Swope 提出的 Velocity-Verlet 算法可以同时给出位置、速度与加速度，并且不牺牲精度 13，计算量适中。(6)(1)()0.5()1rkvkavk其中 、 和 为当前时刻最差个体的位置、()()a速度和加速度。2.3.改进的 SFLA 算法本文将 Velocity-Verlet

14、算法引入到混合蛙跳算法中，作为局部深度搜索的更新策略。同时利用高斯变异的来代替原策略中的随机更新操作。变异公式如式（7）所示：(7)()1(0,)mutaionxN其中 表示期望为 0，标准差为 1 的正态分布随(0,1)N机数。改进混合蛙跳算法的主要步骤如下：(1) 初始化蛙群，种群个体总数 N，个体的维数m，子种群的个数 M，子群局部搜索迭代次数 cyc，全局交换迭代次数 all_cyc，个体 的初始位置,1i和初始速度 ，比例系数 。(0)ir(0)iv(2) 将当前所有个体的适应度值从优到劣排序，依次将个体划分到各子种群。(3) 对当前子种群的最差个体按照式（5） （6）进行更新，如果

15、更新的个体适应度值优于更新前个体，则用更新后的个体代替更新前的个体。如果没有改进，则利用式（7）进行更新，并取代更新前的个体。确定当前时刻的全局最优个体，并跳转至步骤（3） ，直至子种群内的迭代次数满足事先给定的要求 cyc。(4)当所有子种群完成以上的更新操作后，若当前最优个体满足收敛条件，则进化过程成功结束，返回全局最优解；若不满足全局迭代次数 all_cyc，则跳转步骤(2)；否则输出全局最优解。3. 算法收敛性分析定理1：改进SFLA算法的种群序列 是有,0kr限齐次马尔可夫链，其中k表示进化代数。证明：本文中初始化种群是有限的，同时算法中各个更新策略均与进化代数k无关，因此 仅与 有

16、1krk关，即 是有限齐次马尔可夫链。证毕。,0kr设规模为N的群体认为是状态空间 中的某个点，S是 中的第i个状态，其中 。设isS12,.i Nsr是 上的适应度函数， 为全局最佳值，令f f,称 为最优解集。|(),srfrSs定理2：对于改进SFLA算法的马尔可夫链序列的种群最优值序列是单调不减的，即对于任意的k0，。1()(kkfrf证明：在改进SFLA算法中，只有最优个体的适应度值超过原最优个体时，原最优个体才会被取代，这样保证了每代都拥有的最优个体都不差于前一代，因此对于任意的k0 ，有 。证毕。1()(kkfrf定理 3：改进 SFLA 算法以概率 1 收敛。证明：本算法的状态

17、转移由马尔可夫链来描述， 表ikr示在第 k 代种群 处于状态 ，随机过程 的转移概krisk率为 。设1()/jiijkpP|iI(1) 当 时，由定理 2 可得,Ij(8)()0ijpk即当父代出现最优解时，不论经历多少代的优化最优解都不会退化。(2) 当 时，由定理 2 可得 ，,iIj1()(kkfrf所以(9)()0ijpk设 为种群 处于状态 的概率， , 由()ipkkris()kiiIp马尔可夫链的性质可知：(10)1()()ikiijsSjIiij iijiIj iIjpkppk由于(11)()()kiij iijiIj iIjpkpk因此(12)()()iijkiijiIj

18、 iIjkpk将式(12)代入式(10) 可得(13)1()()kkiij iijiIj iIjppkk将式(8) (9)代入式(13) 可得(14)10kkp因此(15)limk又因为 lim1li()1lik i kk kIPfpp 因此(16)likkPf故算法以概率 1 收敛于全局最优解。3. 算法仿真本文采用 4 个标准测试函数对 ISFLA 进行研究，这些函数经常被国内外学者用来测试优化算法的性能和可靠性 15。Sphere 函数： ，目标函数最优值为10,ix0，可接受解的阈值为 0.01，(17)211()nifxRastrigin 函数： ，目标函数最优5.,ix值为 0，可

19、接受解的阈值为 100，(18)221()00cos()ni iif xAckley 函数： ，目标函数最优值为5,ix0，可接受解的阈值为 0.1，(19)23 11()20exp(.)exp(cos2)0eDDi if xGriewank 函数： ，目标函数最优60,i值为 0，可接受解的阈值为 0.05，(20)2411()cos()0nniiixfxx以上4个函数均在（0,0,0）处取得最优值，其中Sphere函数是单模态函数，有助于研究优化算法在问题维度上的效果；Rastrigin和Ackley是具有大量局部极优点的多峰函数；Griewank函数各维之间显著相关，只有各维同时变化才能

20、优化函数值。在算法性能测试中，参照文献14中建议的参数设置和经过多次的仿真实验，I SFLA 的参数设置如下：种群大小 200，每个子群内个体数量 20，子群体内迭代次数 20，全局迭代次数 150，比例系数为 4。SFLA的全局迭代次数 200，优化 Ackley 函数时全局迭代次数为 1000。测试函数的维数 n 依次取 10、20 和 30。为了进一步对比算法的性能，选择文献15中的 MMT-PSO 算法同时求解优化问题。对每个函数随机连续运行 50 次，然后取平均值。表 1 是 ISFLA 算法、SFLA算法和 MMT-PSO 算法对函数 50 次独立实验最优解的平均值；表 2 是标准

21、差，用来反映算法的稳定性。表 1 3 种算法最优解的平均值函数 算法 10维 20维 30维MMT-PSO 4.04e-54 5.13e-33 2.79e-29SFLA 4.3112e-11 5.9895e-07 2.6234e-05SphereISFLA 4.4043e-76 8.3125e-69 2.6829e-73MMT-PSO 6.368 22.394 53.737SFLA 8.9546 19.8992 52.7330RastriginISFLA 0 0 0MMT-PSO -5.91e-11 -5.90e-11 -5.90e-11SFLA 2.1866e-06 2.3168 1.501

22、7AckleyISFLA 12.6935 16.4830 4.7073e-14MMT-PSO 7.37e-2 2.31e-2 1.47e-1SFLA 0.1353 0.0074 0.0124GriewankISFLA 0 0 0由表 1 和表 2 的结果可知，对于简单的单峰函数F1，分别在 10、20 和 30 维的前提下，ISFLA 方法得到的最优解的平均值和标准差较 SFLA 所获得的结果有 45 个数量级以上的提高，即使与文献所提方法相比也有很大的提升。同时也可以看出随着维数的增加，对函数的优化也越来越困难，所得解的精度也逐渐下将，因为维数的增加导致了搜索空间的增大。对于多峰函数 F2

23、和 F4，在函数维数为 10、20 和 30 时，ISFLA 都能获得理论上的最优解，并且标准差为 0，体现出了极强的鲁棒性。相比之下 SFLA 和 MMT-PSO算法都陷入了局部最优值，出现早熟问题，搜素精度和算法稳定性明显弱于 ISFLA。对于函数 F3，SFLA表现出了良好的搜索性能，相比之下 CSFLA 的搜索精度更高，算法更稳定。表 2 3 种算法最优解的标准差函数 算法 10维 20维 30维MMT-PSO 1.78e-44 2.22e-30 1.12e-28SFLA 2.77e-19 4.56e-15 2.31e-12SphereISFLA 6.89e-66 2.36e-62 6

24、.89e-66MMT-PSO 3.756 8.902 1.487SFLA 2.8192 7.3294 13.8967RastriginISFLA 0 0 0MMT-PSO 1.09e-15 1.59e-15 2.44e-15SFLA 5.09e-15 3.55e-14 2.30e-10AckleyISFLA 3.25e-18 3.21e-18 3.19e-18MMT-PSO 2.41e-2 2.22e-2 5.96e-1SFLA 5.64e-11 1.99e-2 5.20e-2GriewankISFLA 0 0 0因此综合表 1 和表 2 的结果可以看出，ISFLA 增强了算法摆脱局部极值的能

25、力，具有更好的的全局搜索能力和算法的稳定性，有效地改善了混合蛙跳算法的寻优能力。图 1-4 分别是函数 F1、F2、F3 和 F4 的最佳适应度值的对数随进化代数变化的曲线图（50 次独立运行的平均） 。(a) ISFLA (b) SFLA图 1 Sphere 函数的收敛曲线(a) ISFLA (b) SFLA图 2 Rastrigin 函数的收敛曲线(a) ISFLA (b) SFLA图 3 Ackley 函数的收敛曲线(a) ISFLA (b) SFLA图 4 Griewank 函数的收敛曲线表 3 ISFLA 和 SFLA 的寻优时间函数 算法 10 维 20 维 30 维SFLA 6.

26、985122S 11.238497S 15.306723SSphereISFLA 4.146509S 8.378344S 12.962330SSFLA 7.164266S 13.057496S 15.657408SRastriginISFLA 3.743382S 7.494179S 12.629906SSFLA 16.705199S 25.498485S 35.629841SAckleyISFLA 6.060525S 11.677796S 18.149654SSFLA 8.026433S 12.700300S 19.510937SGriewankISFLA 4.378075S 8.394438

27、S 13.439299S图 1-4 反映了算法的收敛过程，其中图 1-4（b）小图里最上面一条曲线是 30 维时算法的收敛曲线，中间一条是 20 维时算法的收敛曲线，最下面的则是 10维时算法的收敛曲线。图 2 和图 4 中出现截断情况表示已搜索到全局最优解。从图竖坐标的刻度就可以看出，在相同维数时，ISFLA 的收敛速度和精度明显优于 SFLA 方法。虽然随着维数的增大，ISFLA 算法对函数寻优的速度会逐步下降，但搜索效率依然令人满意。图 1-4 中 ISFLA 的收敛曲线基本由折线段构成，而 SFLA 则由平滑的曲线构成，这是因为 ISFLA 的收敛策略本质是在求解牛顿方程。因此从 4

28、个函数寻优的结果可以看出，ISFLA 的改进机制，使算法具有高效的搜索性和跳出局部极值的能力，与 SFLA 相比，具有更强的全局搜索能力、更高的搜索精度、更快的收敛速度和更好的鲁棒性。表 3 是 ISFLA 和 SFLA 寻优时间的比较，ISFLA 的寻优时间明显优于 SFLA 的，可以快速找到精度更高的最优解。实验仿真过程中，因为改进算法的收敛策略中引入了求解牛顿方程，所以 ISFLA 的运行时间略大于 SFLA，其算法复杂度略高于基本蛙跳算法，但是比起改进算法的其它显著优越性其算法复杂度可以忽略不计。同时，因为本论文主要考虑的是改进后算法的性能，对于如何降低算法所消耗的内存等资源将是下一步

29、研究的方向。4. 结 论本文针对混合蛙跳算法在进化后期存在早熟收敛的缺陷，提出一种改进混合蛙跳算法，该算法仅仅考虑最差个体和最优个体间的吸引力，通过分子动力学模拟种群的进化策略，并证明了改策略的全局收敛性。仿真结果表明本文所提算法比基本的混合蛙跳算法具有更好的防早熟收敛的能力和全局搜索能力，收敛速度和精度性能更优。由于测试函数有限，改进的混合蛙跳算法用于其它基准函数如离散函数的有效性，以及如何确定算法参数以得到更好的优化效果是我们下一步研究的重点。参考文献1 Alireza R V, Ali Hossein M. Solving a bi-criteria permutation flow-s

30、hop problem using shuffled frog-leaping algorithm J. Soft Computing, 2008, 12(5): 435-452.2 Eusuff M M, Lansey K E. Shuffled frog-leaping algorithm: A memetic meta-heuristic for discrete optimization J. Engineering Optimization, 2006, 38(2): 129-154.3 Alireza R V, Ali Hossein M. A hybrid multi-objec

31、tive shuffled frog-leaping algorithm for a mixed-model assembly line sequencing problem J. Computers & Industrial Engineering, 2007, 53(4): 642-666.4 李英海, 周建中, 杨俊杰等. 一种基于阈值选择策略的改进混合蛙跳算法J. 计算机工程与应用, 2007, 43(35): 19-21. Li Ying Hai, Zhou Jian Zhong, Yang Jun Jie et.al. Modified shuffled frog leaping

32、algorithm based on threshold selection strategy J. Computer Engineering and Applications, 2007, 43(35): 19-21.5 罗雪晖, 杨晔, 李霞. 改进混合蛙跳算法求解旅行商问题J. 通信学报, 2009, 30(7): 130-135. Lu Xue Hui, Yang Ye, Li Xia. Modified shuffled frog leaping algorithm to solve travelling salesman problem J. Journal of Communic

33、ations, 2009, 30(7): 130-135.6 M P Allen, D J Tildesley. Computer Simulation of Liquid M. New York: Oxford University Press, 1987.7 D Frenkel, S Berend. Understanding Molecular Simulation M. San Diego: Academic Press, 1996.8 解辉, 刘朝, 高虹. 分子动力学模拟纳米通道内混合气体流动的温度效应J. 工程热物理学报 , 2010, 31(6): 921-924. Xie H

34、ui, Liu Zhao, Gao Hong. Effects of Temperature on gas mixture flow in nanochannels by molecular dynamics simulations J. Journal of Engineering Thermophysics, 2010, 31(6): 921-924.9 丁元法, 张跃, 张大海等. 石英玻璃分子动力学模拟中的原子电荷转移与系综选择J. 物理化学学报, 2010, 26(6): 1651-1656. Ding Yuan Fa, Zhang Yue, Zhang Da Hai et.al.

35、Atomic charge transfer and ensemble selection in molecular dynamics simulation of vitreous silica J. Acta Phys.-Chim. Sin., 2010, 26(6): 1651-1656.10 王伟, 张凯旺, 孟利军等. 多壁碳纳米管外壁高温蒸发的分子动力学模拟J. 热物理学报 , 2010, 59(4):2672-2678. Wang Wei, Zang Kai Wang, Meng Li Jun, et.al. Molecular dynamics simulation of the

36、 evaporation of the surface wall of multi-wall carbon nanotubes at high temperature J. Acta Physica Sinica, 2010, 59(4): 2672-2678.11 权伟龙, 李红轩, 吉利等. 类金刚石薄膜力学特性的分子动力学模拟J. 物理学报, 2010, 59(8): 5687-5691. Quan Wei Long, Li Hong Xuan, Ji Li, et.al. Molecular dynamics simulation on the mechanical property

37、of hydrogenated diamond-like carbon films J. Acta Physica Sinica, 2010, 59(8): 5687-5691.12 Verlet L. Computer “Experiments” on Classical Fludis. Thermodynamical Properties of Lennard-Jones Molecules J. Phys. Rev, 1967, 159(1): 98-103.13 Swope W C, Andersen H C, Berens P H, et al. A computer simulat

38、ion method for the calculation of equilibrium constants for the formation of physical clusters of molecules: Application to small water clusters J. Journal of Chemical Physics, 1982, 76(1): 637-649.14 Elbeltagi E, Hegazy T, Grierson D. Comparison among five evolutionary-based optimization algorithms

39、 J. Advanced Engineering Informatics, 2005, 19(1): 43-53.15 徐星, 李元香, 姜大志等. 一种基于分子动理论的改进粒子群优化算法J. 系统仿真学报 , 2009, 21(7):1904-1907. Xu Xing, Li Yuan Xiang, Jiang Da Zhi, Tang Ming Duan, Fang Shen Lin. Improved Particle Swarm Optimization Algorithm Based on Theory of Molecular Motion J. Journal of System Simulation, 2009, 21(7): 1904-1907.作者简介第一作者：张潇丹（1988.09- ） ，女，博士研究生，研究方向：群体智能优化算法，语音情感识别等，Email: zhangdaqing_；第二作者：胡峰（1985.02-） ，男，硕士研究生，研究方向：群体智能优化算法及其应用等；第三作者：赵力（1958.01-） ，男，教授，博士生导师，研究方向：语音信号处理等；第四作者：邹采荣（1963.12- ） ，男，教授，博士生导师，研究方向：图像与视频信号处理、情感信息处理和多维数字信号处理理论及其应用的研究等。