基于邻域正交交叉算子的混合蛙跳算法.doc

基于邻域正交交叉算子的混合蛙跳算法孟庆莹1 王联国2（1.甘肃农业大学工学院，兰州，730070 2.甘肃农业大学信息学院，兰州，730070）摘要：混合蛙跳算法(SFLA)是一种全新的群体智能优化算法。针对基本混合蛙跳算法优化精度低、收敛速度慢的缺点，引入邻域正交交叉算子的概念，提出了一种基于邻域正交交叉算子的混合蛙跳算法(SFLA-OCO)。通过对基准函数进行测试，实验结果证明改进的算法提高了算法的收敛速度，增强了算法的寻优能力。关键词：混合蛙跳算法；群体智能；正交交叉算子 Shuffled Frog Leaping Algorithm based on Local Orthogonal Crossover OperatorMeng Qingying1 Wang Lianguo2(1. College of Engineering, Gansu Agricultural University, Lanzhou 730070, China2. College of Information Science Technology, Gansu Agricultural University, Lanzhou 730070, China)Abstract: Shuffled Frog Leaping Algorithm(SFLA) is a new swarm intelligence optimization algorithm.Since basic Shuffled Frog Leaping Algorithm has low optimization precision and slow convergence speed ,this paper proposes a Shuffled Frog Leaping Algorithm based on local orthogonal crossover operator（SFLA-OCO）. The test of benchmark function shows that the new algorithm improved not only the convergence speed but also the abilities of searching the global excellent result.Keywords:Shuffled Frog Leaping Algorithm;Swarm Intelligence;Orthogonal Crossover Operator1 引言混合蛙跳算法（Shuffled Frog Leaping Algorithm ,SFLA）是2003年由 Eusuff和 Lansey提出，根据模拟青蛙觅食过程中信息共享和交流的特点而产生的一种基于群体智能的算法。作为一种全新的生物进化算法，它结合了基于基因进化的模因演算法（Memetic Algorithm,MA）和基于群体行为的粒子群算法（Particle Swarm Optimization,PSO）两者的优点，具有概念简单，参数少(具有比 PSO更少的算法参数)，计算速度快，全局寻优能力强，易于实现的特点。目前该算法已经不断得到完善和应用，如水资源网络分配问题1-3、车间调度问题4、函数优化5-6、旅行商问题7-9、成品油管网优化设计10等。然而在基本混合蛙跳算法的求解过程中，对于一些复杂的问题依然存在着收敛速度较慢、优化精度较低的缺点，而且随着维数的增加，这种变化就越大，最终影响了算法的效率。因此研究者用不同的方法进行了相应的改进，如文献5提出了一种基于阈值选择策略的改进混合蛙跳算法，在一定程度上改善了基本混合蛙跳算法的性能；文献6利用生物学中的吸引排斥思想更新策略，一定程度上提高了算法的收敛速度。本文将邻域正交交叉算子引入到基本混合蛙跳算法中,提出了一种基于邻域正交交叉算子的混合蛙跳算法(Shuffled Frog Leaping Algorithm based on Local Orthogonal Crossover Operator，SFLA-OCO)，提高了算法的优化精度。2 混合蛙跳算法基本原理2.1 行为描述在一片湿地中生活着一群青蛙，湿地内离散地分布着许多石头，青蛙通过寻找不同的石头进行跳跃去找到食物较多的地方。每个青蛙通过寻找不同的石头提高自己寻找食物的能力，而青蛙个体之间通过思想的交流实现信息的交换。在子群体中的每个个体有自己的文化，并被定义为问题的一个解，影响着其它个体，并随着子群体的进化而进化。当子群体进化到一定阶段以后，各个子群体之间再进行思想的交流实现子群体间的混合运算，一直到所设置的条件满足为止。在混合蛙跳算法中，群体(解集)由一群具有相同结构的青蛙(解)组成。整个群体被分为多个子群体，不同的子群体被认为是具有不同思想的青蛙的集合。族群中青蛙按照一定策略执行解空间中的局部深度搜索。在已定义的局部搜索迭代次数结束之后，思想在混合过程中进行了交换。局部搜索和混合过程一直持续到定义的收敛条件结束为止。全局信息交换和局部深度搜索的平衡策略使得算法能够跳出局部极值点向着全局最优的方向进行，这也成为混合蛙跳算法最主要的特点。2.2 数学模型随机生成F只青蛙(问题的解)组成初始群体，第i只青蛙表示问题的解为Xi=(xi1，xi2，xis)，其中 s表示变量的个数即解空间的维数。在生成初始群体之后，将种群内青蛙个体按适应度降序排列。然后将整个青蛙群体分成m个族群，每个族群包含 n只青蛙，满足关系F=mn。其中，第1只青蛙分入第1族群，第2只青蛙分入第2族群，第m只青蛙分入第m族群，第m+1只青蛙分入第1族群，第 m+2只青蛙分入第 2族群，依次类推，直到全部青蛙划分完毕。对于每一个族群，具有最好适应度的解表示为Xb，最差适应度的解表示为Xw，而所有族群中具有全局最好适应度的解表示为Xg。然后对每个族群进行局部深度搜索，即对族群中的Xw循环进行更新操作，更新策略为： (1) (2)DmaxDj-Dmax，其中，Dj表示分量 j上移动的距离，rand( )表示0和1之间的随机数，Dmax表示青蛙所允许改变位置的最大值。在经过更新后，如果得到的解newXw优于原来的解oldXw，则取代原来族群中的解。如果没有改进，则用Xg取代Xb重复执行更新策略(1)、(2)。如果仍然没有改进，则随机产生一个新的解取代原来的Xw。重复这种更新操作，直到设定的迭代次数。当所有族群的局部深度搜索完成后，将所有族群的青蛙重新混合并排序和划分族群，然后再进行局部深度搜索，如此反复直到满足终止条件。3 基于邻域正交交叉算子的混合蛙跳算法3.1 正交试验原理正交试验设计(Orthogonal experimental design)是数理统计中的一个重要内容，正交设计是利用预先编制好的正交表来合理的安排多因素试验，以便通过少量的试验次数来获得满意的结果，同时对试验数据进行统计分析，是一种高效率、快速、经济的实验设计方法。正交交叉算子是文献11提出的一种新的算子，用较少的试验次数来产生新的较优个体，它具有均衡分散性和整齐可比性。在数学上把均衡分散性和整齐可比性称为正交性，凡具有这特性的试验设计方法都称为正交设计法。正交表是一整套规则的设计表格，它遵循概率统计规律，依照一定的原则（如正交拉丁）生成的，通常表示成La(tq), 其中L表示正交表的代号，a表示试验的次数，t表示因素的水平数，q表示正交表的列数，即正交表最多能安排的因素数。3.2 邻域正交交叉算子定义1 设个体进行N-1点交叉运算，则交叉的个体分量个数为N,将这N个分量看成N个因素。定义2 将个体的每一个交叉分量，设置为同一水平，这样两个个体的交叉运算，就是一个N因素、2水平试验。定义3 用N因素、2水平正交试验表安排某个体与邻域极值个体的分量交叉，得到2N个子个体，通过适应度函数选取一个适应度最大的子个体，代替该个体，而极值个体保持不变。该过程称为邻域正交交叉算子。本文对该正交交叉算子进行了简化，随机将邻域极值中的一部分分量与最差个体中的对应的分量进行交叉，形成新的个体，并用新个体代替原来的个体12。设Xw=(xw1,xw2,xwD)为最差个体Xw在D维空间中的当前位置，Xb=(xb1,xb2,xbD)为邻域最优极值，首先从邻域最优极值Xb中随机选择其中的一部分分量和最差个体Xw中的对应的分量进行交叉，得到交叉后的个体Xw，然后计算其适应度，从中选择交叉后适应度最优的个体Xw来代替个体Xw。最差个体Xw在D维空间中的当前位置Xw=(xw1,xw2,xwD)按（3）式产生。（3）其中，k=1，2，D；pc为k维分量交叉的概率；U(0，1)为0，1上的随机数。 3.3 算法流程Step1: 随机产生种群F=mn只青蛙，设置混合迭代次数G和族群内迭代次数N；Step2: 对每只青蛙，计算其适应度，找出全局最优个体Xg；Step3: 将F只青蛙按照适应度将序排列，划分为m个子群体，每个子群体中包含n只青蛙, 找出每个子群体中的最优个体Xb和最差个体Xw；Step4: 根据新的局部更新策略，按照公式（1）和公式（2）更新Xw值；Step5: 按照邻域正交交叉概率pc,根据公式（3）对最差个体Xw执行正交交叉算子;Step6：判断终止条件是否满足? 如果满足，结束迭代，输出最优解Xg，否则转Step2。4 实验与仿真以求5个基准测试函数的最小值为例，进行仿真实验，测试软件平台为Visual C+和Windows XP，机器主频为P4 (1.99Ghz)，内存为1GB。 算法性能评价采用如下方法：（1）固定进化迭代次数，评价算法的收敛速度和精度；（2）固定收敛精度，评价算法达到该精度所需要的迭代次数。 4.1 固定进化迭代次数下算法的收敛速度和精度在算法性能测试中，采用文献6中建议的参数设置：青蛙总数P=200，族群数M=20，其中每个族群中I=10只青蛙，组内迭代次数N=10，混合迭代次数G=500，函数变量维数为V=30。将连续运行30次所得的函数全局平均最优值、标准差以及运行时间作为算法性能的衡量指标。函数的初始化范围以及实验结果如表1所示。从表1可以看出基于邻域正交交叉算子的混合蛙跳算法（SFLA-OCO）的结果优于基本蛙跳算法以及文献6中的改进算法ISFLA，提高了算法的收敛性能。图1图5是函数f1f5采用SFLA、文献6中的ISFLA和SFLA-OCO运行30次后得到的平均最优值进化曲线，从图中可以看出，SFLA-OCO收敛速度快，同时优化精度有显著的提高。表1实验结果函数算法平均最优值标准差平均运行时间/sf1SFLA0.0107290.0102810.84ISFLA0.0029490.0007173.78SFLA-OCO0.0000090.0000171.25f2SFLA15.9583315.8085121.08ISFLA9.7574873.2457857.99SFLA-OCO9.3870103.1769092.58f3SFLA0.7952420.2101611.19ISFLA0.0855870.08471713.2SFLA-OCO0.0433050.0324152.16f4SFLA1.3981516.1117031.11ISFLA0.0407410.0101857.86SFLA-OCO0.0026060.0042651.86f5SFLA29.0899127.9807472.91ISFLA16.1075194.24175035.72SFLA-OCO7.7188624.8501359.41图1函数f1的平均最优值进化曲线图2函数f2的平均最优值进化曲线图3函数f3的平均最优值进化曲线图4函数f4的平均最优值进化曲线图5函数f5的平均最优值进化曲线4.2 固定收敛精度目标值下算法需要的迭代次数参数设置如下：最大迭代次数为2000，邻域正交交叉概率pc=0.25，交叉次数T=20，f1f5目标收敛阈值分别为10-7、101、10-1、10-3、101，其它参数同上。 表2 在固定误差精度下的进化迭代次数函数算法成功率%平均迭代次数最小迭代次数最大迭代次数f1SFLA63183015941999SFLA_OCO100614438730f2SFLA476942931548SFLA_OCO10049715994f3SFLA907525421146SFLA_OCO97331204492f4SFLA23177515821953SFLA_OCO100503371593f5SFLA109796331271SFLA_OCO100399401108表2为5个测试函数在固定收敛误差精度下独立运行30次后的迭代次数，其中，成功率=达到目标精度的实验次数总实验次数。从表2可以看出，改进的算法对5个函数达到97%以上的成功率，基本的SFLA算法对函数f1f5的成功率分别达到63%、47%、90%、23%、10%；改进算法对5个测试函数达到目标精度的平均迭代次数均在614次以内，说明SFLA_OCO算法具有更稳定的收敛性能。5 结论针对混合蛙跳算法在根据局部更新策略更新个体最差值Xw时带有一定的盲目性，寻优结果精度低收敛速度慢等缺点，对其进行了改进，提出了一种基于邻域正交交叉算子的混合蛙跳算法，改善新个体的部分分量值，从而提高种群的多样性，加速算法的收敛，较好的平衡了算法的全局搜索能力和局部搜索能力，提高了算法的优化速度和计算精度。实验证明，基于邻域正交交叉算子的混合蛙跳算法在参数设置相同的情况下，对复杂的高维函数的优化结果均优于基本的混合蛙跳算法。参考文献1 EUSUFF M ,LANSEY K E. Optimization of water distribution network design using the shuffled frog leaping algorithmJ.Water Resources Planning and Management ,2003 ,129 (3) :210 2252 SHIE Y H ,ATIQUZZAMAN M. Optimal design of water distribution network using shuffled complex evolutionJ.The Institution of Engineers ,2004 ,44 (1) :93 1073 MUZAFFAR E ,KEVIN L ,FAYXUL P. Shuffled frog-leaping algorithm:a memetic metaheuristic f