变异算法（共7篇）
变异算法 篇1
Karaboga于2005年基于蜜蜂采蜜的高效方式提出了用于解决函数优化问题的人工蜂群算法 (artificial bee colony algorithm, ABC) [1], 这是一种群体智能化算法并与经典的遗传算法 (GA) 、蚁群算法 (ACO) 和粒子群算法 (PSO) 等进行了比较, 确定了ABC在函数优化方面无与伦比的优越性。该算法具有较强的灵活性和鲁棒性且已得到全局最优解。然而作为一种新兴的算法, 它的相关研究还不是很成熟[2], 虽然文献[5]采用混沌搜索策略来自适应的调整搜索空间, 文献[6]使用boltzmann选择方式进行蜜源的选择, 文献[7]通过引入遗传交叉因子增加了种群多样性并依此来改变原蜜源的结构, 都在一定程度上降低了算法陷入局部最优的可能, 但也不得不受算法的时间精度限制。为此, 该文通过深入研究提出了一种新的基于变异机制的人工蜂群算法来有效解决上述问题, 并用了几个标准测试函数加以测试。
1 人工蜂群算法
ABC模拟实际蜜蜂高效的采蜜机制来处理函数优化问题, 将人工蜂群分为3类:引领蜂、跟随蜂和侦查蜂, 前两种蜜蜂用于蜜源的开采, 而侦查蜂为避免蜜源种类的过少[3]而不断的寻找新的蜜源并替代原来不需要或者说已经使用过的蜜源。每个食物源代表一个待求问题的解而该食物源花蜜的多少代表这个解的优劣程度。待找最优蜜源的过程如下:随机产生2N个位置, 通过简单的选择选取较优异的N个作为蜜源的位置, 引领蜂找到这些蜜源并标记他们记, 然后在这些标记蜜源附近按式 (1) 搜索新蜜源:
式中:Vij为新蜜源的位置, xij为已标记过蜜源的第i维位置, xkj为随机选择的不等于i的已标记过蜜源的第j维位置, Rij为[-1, 1]间的随机数。根据前后蜜源的花蜜数量选择较优的蜜源替代初始标记的蜜源, 并继续在标记蜜源附近用 (1) 式搜索新蜜源, 并与初始标记蜜源比较, 按照上述的方法反复循环迭代, 直到达到算法的终止条件。
2 基于随机选择的人工蜂群算法
众所周知ABC的优化效果较好, 但由于算法本身选择方式的局限性使其算法容易陷入局部最优, 在迭代的进程中【4】每代的最差解都必定会参与到新解的产生之中从而直接影响了算法的收敛速度且易使算法发生早熟。为此, 该文在最差蜜源的选择和对算法的早熟方面做了比较好的改进[5]。
2.1 最差蜜源的替换
在ABC迭代的过程中, 由于每代的最差蜜源按 (1) 式进行交叉操作而产生新的蜜源, 但是最差蜜源却几乎不可能对产生的最优蜜源做出贡献[6], 这就影响了算法的收敛速度。因此可用一个新的蜜源代替最差蜜源取消最差蜜源的破话作用。为此采取如下公式进行代替:
式中:Vij为新蜜源的位置, xij为最差蜜源的第j维位置, xkj为随机选择的不等于i的最差蜜源的第j维位置, c和d为[0, 1]间的随机数。在原来公式的基础上又增加了一个随机数【6】, 使得蜜源在相互交换时的变化更大, 从而大大的增加了蜜源变异的可能。
2.2 对算法早熟的解决
由于ABC采用轮盘赌的选择策略, 就不可避免的会早熟和陷入局部最优, 为解决这个问题, 该文在随机选择的基础上又引入了变异的思想[7]。
1) 变异机制的引入
虽然ABC在优化问题上的运用方面取得了较好的效果, 但易陷入局部最优。为有效解决这个问题而引入变异【8】的思想。ABC之所以会早熟就是因为在当前蜜源中找不到比此蜜源较优的蜜源, 而陷入局部最优并过早收敛。为了能找到较优的蜜源可以引入若干新的蜜源以替代原来被搜索过的蜜源;即改变整个蜜源的结构。伪代码如下:
2) 变异时替换蜜源的量的大小和limit的值
文中算法产生变异时选择替换的蜜源数是整个种群的10%, limit的值为50, 具体还要由具体实验来决定[9]。
3 实验仿真和结果分析
为了验证本文的一系列设想, 进行了大量的仿真测试。实验仿真是在Inter (R) Pentium (R) D, CPU 3.00GHZ、1.25G内存的计算机上实现, 程序采用Matlab7.10语言编程实现。为便于描述以VABC代表新提出的ABC, 为了验证本文提出的VABC的优化效果选用函数优化领域广泛采用的4个标准测试函数进行测试。前3个的理论最优值都为0, 最后一个的最优值为-4.1898n, 把本函数与原ABC的运行效果进行比较。
ABC相应参数设定如下:引领蜂、跟随蜂的数量都取N=40, 蜜源的数量取N/2=20, 测试函数和蜜源的维数都取100维, limit为50, 各个函数迭代8000次。各算法均随机运行50次, 并取这50次数据的平均值、方差、最优值、最差值、平均收敛代数和平均运行时间来考察算法的寻优性能。为了能够更好的证明的优越性各项数据与原ABC的运行结果相比较。具体结果见表1。
由表1中数据可以得出如下结论:
1) 在抑制早熟上VABC有着显著的效果, 反映在上表中就是收敛的代数比较大。
2) 在算法的精确度上VABC有着比较明显的提高, 从最优值、平均值和最差值上均优于原ABC, 且VABC的方差较小, 说明结果比较稳定。
3) 运行时间上两算法相差不大, 但是VABC在取得良好效果的同时时间不长可见优势明显。
4 结束语
针对ABC易陷入局部最优、收敛速度慢的缺点, 该文利用了变异的概念实现了局部替换, 由此提出了一种改进的人工蜂群算法—VABC。本算法跟传统的ABC相比在解决函数优化类问题上优势明显。
摘要：针对人工蜂群算法存在的收敛速度慢、易陷入局部最优的缺点, 利用变异方法来取代传统的选择模型。对4个标准测试函数的仿真表明本文提出的随机选择算法不仅能延长算法的收敛速度还能在算法的精度上有着明显的提高, 改进后的性能明显优于人工蜂群算法。
关键词：人工蜂群算法,变异,收敛速度
参考文献
[1]Karaboga D, Basturk B.On the performance of artificial bee colony (ABC) algorithm[J].Applied Soft Computing, 2008, 8 (1) :687-697.
[2]LIU Xingbao, CAI Zixing.Artificial bee colony programming made faster[J].Natural Computation, 2009 (8) :14-16.
[3]Kabboga D, Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony (ABC) algorithm[J].Journal of Global Optimization, 2007, 39 (3) :459-471.
[4]Tizhoosh H R.Opposition-based learning:a new scheme for machine intelligence[C]//Proceeding of International Computational for Modeling Control and Automation.Sydney, Australia, 2005:695-701.
[5]暴励志, 曾建湖.自适应收索空间的混沌蜂群算法[J].计算机应用研究, 2010, 27 (4) :1331-1335.
[6]丁海军, 冯庆娴.基于Boltzmann选择策略的人工蜂群算法[J].计算机工程与应用, 2009, 45 (31) :53-55.
[7]罗钧, 樊鹏程.基于遗传交叉因子的改进蜂群优化算法[J].计算机应用研究, 2009, 26 (10) :3751-3753.
[8]Penev K, Littlefair G, Free Search:a comparative analysis[J].Information Sciences, 2005, 172 (1) :173-193.
[9]Rahnamayan S, Tizhoosh H R, Salama M M A.opposition-Based differential evolution[J].IEEE Transaction on Evolutionary Computation, 2008, 12 (1) :64-79.
变异算法 篇2
关键词：差分演化算法,变异策略,基准函数,优化
1 引 言
自然界生物体优胜劣汰, 不断由低级向高级进化。人们通过观察发现适者生存的进化规律可以形式化而构成一些优化算法。优化算法研究的本质是在众多方案中寻找最优方案, 即在满足一定的约束条件下, 寻找一组参数值, 使得系统某些性能指标达到最大或最小。优化技术是用来求解优化问题的方法, 它作为一个重要的科学分支一直受到人们的广泛关注, 并在诸多领域得到应用, 如人工智能领域、模式识别领域、系统控制领域、工程设计领域等。应用一定的优化技术来求解优化问题具有很重要的意义, 国内外研究表明, 在同样条件下经过优化技术的处理, 对系统效率的提高、能耗的降低、资源的合理利用及经济效益提高均有显著的效果, 而且随着处理对象规模的增大, 这种效果也会更加显著[1]。
目前常用的优化算法有遗传算法 (Genetic Algorithm, GA) 、模拟退火算法 (Simulated Annealing, SA) 、粒子群算法 (Particle Swarm Optimization, PSO) 、蚁群算法 (Ant Colony Optimization, ACO) 、差分演化算法 (Differential Evolution, DE) 等。研究表明, 在数值函数优化方面, 差分演化算法的性能要优于上述其它的优化算法。
2 差分演化算法
差分演化是Storm和Rice提出的一种简单有效的算法, 目前差分演化算法在机器智能和控制领域很流行, 同时逐渐被应用到其它科学和工程领域, 如机械工程设计、信号处理和模式识别等。根据最近的研究报告表明[2], 差分演化算法在覆盖率以及解决一些全局优化问题上比遗传算法和粒子群算法具有更好的性能。
经典的差分演化算法通常有几个变异策略和三个控制参数, 控制参数分别为群体规模ps、比例因子F和交叉率CR。除了针对所有基于群体搜索算法的参数ps外, 差分变异策略、参数F和CR是经典的差分演化算法研究中最重要的部分。在这几个方向的研究中, 目前已开展了很多工作。Qin和Suganthan提出一种针对数值优化的自适应DE算法 (SaDE) [3], 这种算法主要研究参数CR和变异策略的自适应性;Brest提出一种针对SaDE采用参数集方法以减少参数影响的策略[4]。Ali和Torn提出一种针对参数F采用辅助群体和自动计算的方法[5]。Yang提出一种针对DE的相邻搜索策略 (NSDE) [6], 这种策略是从Gaussian和Cauchy分布随机数中产生F, 而不是事先定义一个常数F。在NSDE的基础上Yang结合了SaDE和NSDE提出新的DE改进模式[7], 即SaNSDE。
除了上述在控制参数上进行的工作外, 也进行了一些新的针对差分演化变异策略的工作。Sun结合DE和分布估计算法 (EDA) 提出了DE/EDA策略[8];Rahnamayan将OBL引入到DE, 形成了新的DE变异 (ODE) [9], 在此方法中, DE除了估计当前的搜索点外, 也要考虑其对立点, 通过同时评估当前的搜索点和对立点, 可获得更接近全局最优的结果。
本文通过改进经典DE的变异策略, 提出一种新型的DE算法。在此策略中, 每个个体学习它之前的最佳经验以及其他个体的经验。在十个著名的基准函数上进行仿真, 结果显示这种改进的方法, 相对经典的DE、SaDE和SaNSDE在大部分问题上都取得了更优效果。
3 经典差分演化算法
经典差分演化是一个基于群体和方向搜索的方法, 和其他的演化计算 (EA) 方法一样, 从一个初始群体个体出发, 这个初始群体个体是在没有可用的解空间情况下随机产生的。对DE有几种改进方法, 最流行的方法称作“DE/rand/1/bin”, 也是在参考文献[4]和[9]中常用的方法。
假设Xi, G (i=1, 2, …, ps) 是某一代G产生的解集, 其中ps是群体规模, 算法是基于DE策略。DE的主要思想是产生一个试验个体, 差分和交叉建立新的变异试验个体, 并决定哪一个个体能够进入下一代G。对于每一个G中的个体Xi, G, 变异个体Vi, G的定义为:
Vi, G=Xr1, G+F (Xr2, G-Xr3, G) (1)
式中:i=1, 2, …, ps;r1, r2, 和r3——当i从1到ps取不同值时所选的不同随机整数索引值。
与其他的演化算法一样, DE也采用交叉操作, 通过结合两个不同的个体来建立试验个体, 试验个体定义如下:
Ui, G= (U1i, G, U2i, G, …, Uji, G)
式中:j=1, 2, …, D (D为问题的维数) 且
undefined
式中:CR——预定义的交叉概率;randj (0, 1) ——针对i维的一个0～1的随机数;k——一个随机索引参数, k∈{1, 2, …, D}。
该方法必须决定某个个体 (Ui, G或Xi, G) 是否是下一个迭代G的成员。对于最大化问题, 最适合的个体将被选中。
经典的DE算法:
Begin
While NE
For每个独立的Xido
根据式 (1) 生成一个变异个体Vi;
根据式 (2) 生成一个试验个体Ui;
计算Ui个体的适应值;
NE++;
从Xi和Ui两个当中选取一个作为新的Xi;
End For
End While
End
其中:Xi——群体中的第i个个体;Vi——Xi的变异个体;Ui——试验个体;NE——评估函数列举的数值;MAXNE——评估函数的最大列举数值。
4 基于改进变异策略的差分演化算法
除了上面给出式 (1) 外, 还有如下几个变异策略:
DE/best/1:
Vi, G=Xbest, G+F (Xr1, G-Xr2, G) (3)
DE/target-to-best/1:
Vi, G=Xi, G+F (Xbest, G-Xi, G) +F (Xr1, G-Xr2, G) (4)
DE/best/2:
Vi, G=Xbest, G+F (Xr1, G-Xr2, G) +F (Xr3, G-Xr4, G) (5)
DE/rand/2:
Vi, G=Xr1, G+F (Xr2, G-Xr3, G) +F (Xr4, G-Xr5, G) (6)
式 (1) 和式 (4) 因其良好的性能, 在实际中用得最多。本文重点介绍对式 (4) “DE/target-to-best/1”策略进行改进。方法是采用一个随机个体和前面的最佳个体pbest代替当前个体Xi和最佳个体Xbest, 改进的方法描述如下:
Vi, G=Xr1, G+F (pbesti, G-Xi, G) +F (Xr2, G-Xr3, G) (7)
式中:r1, r2, r3——[1, ps]中三个不同的随机整数, ps——群体规模;pbesti——前面个体Xi的最佳个体。和其他变异策略一样, 我们用式 (7) 产生变异个体Xi, 再将算法1中的式 (1) 用式 (7) 替换。改进后算法描述如下:
改进的DE算法 (简称IDE) :
Begin
While NE
For每个独立的Xi do
根据式 (7) 生成一个变异个体Vi;
根据式 (2) 生成一个试验个体Ui;
计算Ui个体的适应值;
NE++;
从Xi和Ui两个当中选择一个合适的作为新的Xi;
End For
End While
End
5 仿真测试
5.1 测试函数
实验选取十个不同的全局优化问题, 包括四个峰函数 (f1～f4) 和六个多模函数 (f5～f10) , 在文献[3]中对这些函数已经进行了相关的研究。在本文中用到的所有函数都是最小化的, 测试基准函数的描述和全局优化如下:
f1=∑undefinedxundefined, 其中xi∈[-100, 100], D=30, 全局最优值是0;
undefined, 其中xi∈[-10, 10], D=30, 全局最优值是0;
f3=∑Di=1 (⎣xi+0.5」) 2, 其中xi∈[-100, 100], D=30, 全局最优值是0;
f4=∑undefinedixundefined+rand[0, 1) , 其中xi∈[-1.28, 1.28], D=30, 全局最优值是0;
undefined, 其中xi∈[-500, 500], D=30, 全局最优值是-12 569.5;
f6=∑undefined[xundefined-10cos (2πxi) +10], 其中xi∈[-5.12, 5.12], D=30, 全局最优值是0;
undefined, 其中xi∈[-32, 32], D=30, 全局最优值是0;
undefined, 其中xi∈[-600, 600], D=30, 全局最优值是0;
f9=0.1{sin2 (3πx1) +∑undefined (xi-1) 2[1+sin2 (3πxi+1) ]+ (xD-1) 2[1+sin2 (2πxD) ]}+∑undefinedu (xi, 10, 100, 4) , 其中xi∈[-50, 50], D=30, 全局最优值是0;
undefined, 其中xi∈[-50, 50], D=30, 全局最优值是0。
5.2 IDE和经典DE的比较
下面对改进的DE和经典DE进行比较, 参数设定如下:改进DE的控制参数CR, F分别设定为0.5和0.2, 对DE和IDE, 群体大小ps都设定为100, 最大列举函数MAXNE设定为100 000。此数值对所有测试函数适用。两个算法针对每个函数都运行30次。记录最佳值和结果的标准差。
表1中给出DE和IDE两种算法运行的结果, 其中“Mean”的含义是表示该函数最佳值, “Std Dev”表示标准偏差。从结果中可以看到, 除f3外, 在所有的测试案例中, IDE的性能均超过DE。在函数f3中, DE和IDE也达到了相同效果。IDE使得f2和f5性能得到显著提高。证明改进的变异策略是有效的。图1显示了IDE和DE在四个函数f1、f2、f4、f5中的演化过程, 可以看到, 在整个演化过程中, IDE的覆盖比DE更快。
5.3 IDE与SaDE、NSDE对比
将IDE与SaDE和NSDE进行比较, IDE中除MAXNE外, 其余参数值与前面设定相同, IDE、SaDE和NSDE的MAXNE对所有测试函数都设定为150 000。
经过十个基准函数仿真测试, 结果如表2所示, 其中“Mean”表示该函数最佳值。SaDE和NSDE的测试结果来自于文献[7]的表2和表3。从结果中可以得出, 在所有测试案例中, 除f3和f5外, IDE性能优于NSDE。而在f3和f5中, IDE和NSDE都能够找出全局优化值。SaDE在f6、f9和f10结果优于IDE, 而IDE在f1、f2、f4、f7和f8上优于SaDE, 对余下的函数IDE和SaDE几乎获得相同的性能。
6 总 结
本文从粒子群优化算法中个体学习之前的最优和其他个体的经验方法得到启示[10], 提出一个基于改进变异策略的DE算法 (IDE算法) 。为了验证IDE的性能, 在十个著名的基准函数上做了测试。仿真结果表明, 在测试主要问题上, IDE优于DE、NSDE和SaDE, 这表明我们提出的变异策略是有效的。然而IDE和DE一样, 在解决f6上没有很好的效果, 而NSDE和SaDE在f6上却能够达到比较好的效果。为了解决这一问题, 未来的工作可以放在将本文提出的变异策略与一个自适应控制参数进行结合上。
参考文献
[1]周艳平, 顾幸生.差分进化算法研究进展[J].化工自动化及仪表, 2007, 34 (3) :1-5.
[2]VESTERSTROMJ, THOMSEN R.A Comparative Study of Dif-ferential Evolution, Particle Swarm Optimization, and Evolution-ary Algorithms on Numerical Benchmark Problems[C]//Pro-ceedings of Congress on Evolutionary Computation.NewJersey:IEEE, 2004:1980-1987.
[3]QIN A K, SUGANTHAN P N.Self-adaptive Differential Evo-lution Algorithm for Numerical Optimization[C]//Proceedingsof Congress on Evolutionary Computation.New Jersey:IEEE, 2005:1785-1791.
[4]BRESTJ, GREINER S, BOSKOVIC B, et al.Self-adapting Con-trol Parameters in Differential Evolution:a Comparative Studyon Numerical Benchmark Problems[C]//Proceedings of Con-gress on Evolutionary Computation.New Jersey:IEEE, 2006:646-657.
[5]ALI M M, TORN A.Population Set-Based Global OptimizationAlgorithms:Some Modifications and Numerical Studies[J].Computers&Operations Research, 2004:1703-1725.
[6]YANG Z, HE J, YAO X.Advance in Metaheuristics for HardOptimization[M].Berlin:Springer Berlin Heidelberg, 2008:397-414.
[7]YANG Z, TANG K, YAO X.Self-adaptive Differential Evolutionwith Neighborhood Search[C]//Proceedings of Congress onEvolutionary Computation.New Jersey:IEEE, 2008:1110-1116.
[8]SUN J, ZHANG Q, TSANG E.DE/EDA:A New EvolutionaryAlgorithm for Global Optimization[J].Information Sciences, 2005, 169 (3-4) :249-262.
[9]RAHNAMAYAN S, TIZHOOSH H R.Opposition-based Differ-ential Evolution[C]//Transactions on Evolutionary Computa-tion, New Jersey:IEEE, 2008:64-79.
基于高斯变异的量子粒子群算法 篇3
由Eberhart和Kennedy等于1995[1]年提出的粒子群优化算法(Particle swarm optimization,PSO)是一种基于种群搜索的自适应进化计算技术,它源于对鸟群和鱼群群体觅食运动行为的模拟。与其他生物进化算法类似,PSO算法是一种基于迭代过程的优化方法。PSO作为一种并行优化算法,可以用于解决大量非线性、不可微和多峰值的复杂问题优化。目前在电路及滤波器设计、神经网络训练、机器人控制[2,3,4]等领域均取得了非常好的效果。
由于粒子群算法具有收敛速度快,计算简单,易于实现等优点,因此,当它提出以后就引起了进化计算领域学者们的广泛关注。但由于粒子群算法在对多模函数求解时出现了早熟收敛的现象,许多学者对它进行了改进。文献[5]中指出具有惯性因子的粒子群算法不仅有效的提高了原始PSO算法的收敛速度,而且在收敛精度上也优于原始PSO。因此现在对粒子群算法的研究大都是基于这个版本,在本文中我们称作基本PSO算法。量子-粒子群算法[6](QPSO)相对于标准粒子群算法来说,由于粒子随时具有跳出当前局部点的可能性,因此算法具有了更强的全局搜索能力。但QPSO在迭代后期由于粒子的聚集性,算法依然存在着早熟收敛的趋势。
本文首先针对QPSO算法的缺点,提出了基于高斯变异的量子粒子群算法(GQPSO)。该策略针对群体历史最优解能够有效地引导粒子群前进的方向,对群体历史最优解有效地运用了高斯变异因子。由于该策略在保证粒子有效的进行局部搜索的前提下,同时加大了允许粒子对整个搜索空间进行搜索的可能性,从而保证改进以后的量子粒子群算法能够更为快速有效的进行全局搜索。
1 基本粒子群算法介绍
全局优化问题(p)的多个可行解的一个集合称为一个种群(swarm)。种群中的每个元素(可行解)称为一个粒子(particle),微粒的个数称为种群规模(size)。用n维向量Xi来表示第i个粒子的位置,用Vid来表示第i个微粒第d维的速度。粒子在迭代过程中,它自身经历的最佳位置为Ppi=(Ppi1,Ppi2,…Ppin)T,微粒群所经历过的最佳位置用Pg表示。因此,微粒在每一次迭代中的速度和计算函数的评价函数的位置可通过如下两个公式计算:
其中:i=1,2…m;d=1,2…n;w称为惯性因子,根据文献[5]设置为大小随着迭代次数的减少由0.9下降到0.4;rand1和rand2是服从U(0,1)分布的随机数;学习因子C1和C2为非负常数,C1=C2=2;vid=[-Vmax,Vmax],Vmax是由用户设定的速度上限。
2 基于高斯变异的QPSO算法
文献[6]从量子力学的角度出发提出了一种新的PSO算法模型。该模型以DELTA势阱为基础,提出了量子粒子群算法。通过蒙特卡罗随机模拟的方式得到粒子的位置方程为:
其中u为[0,1]范围内变化的随机数,L被定义为
其中
式中β称为收缩扩张因子。第T次迭代时取为β=0.5*(MAXTIME-T)/MAXTIME,M为粒子的数目。pi为第i个粒子的历史最优解,可以由(6)式求得,φ为[0,1]范围内变化的随机数。
根据(4)式可以看出,在QPSO算法中,只有一个参数β决定粒子的位置,同标准粒子群算法相比较更少,QPSO算法更易于控制。另外由于QPSO算法中的粒子能够以一定的概率出现在整个搜索空间中,甚至是一个远离收敛点P的点,因此相对于标准粒子群算法来说具有着更强的全局搜索能力,图1为高斯概率密度分布图。
基于高斯变异因子的粒子群算法主要是借鉴遗传算法中的变异因子来改善粒子群算法的全局搜索能力。以原点为中心的Gaussian:
其中为了覆盖整个解空间,Gaussian的参数分别设置为σ=0.16。
其中t是在[-1,1]内的随机数。算法迭代过程描述为:
Step1:设置最大进化代数,随机初始化每个粒子的位置,初始化pp、p8。
Step2:repeat:
Step3:for each particle j∈[1…D]
Step4:利用(4),(5)式计算每个粒子的适应度值,并移动粒子到新的位置上。
对gbest使用(7)式进行变异并比较两者结果获得最优值。
Step6:until结束条件成立
3 对比试验
3.1 实验设计
本文设计了4类测试实验以分析提出的GQPSO的总体性能:
(1)PSO优化试验;
(2)GPSO优化试验,参数设置参考文献[7];
(3)QPSO[6];
(4)GQPSO,同时引入6个Benchmark优化问题来进行优化分析。根据文献[8]~[9]对测试函数和测试标准的规定,函数形式以及搜索范围的设置见表1。
本文测试的粒子群数目设置为20。基本PSO中使用的vmax设置为xmax。另外针对Matlab语言的特点,使用rand(‘state’,sum(i*30))语句以保证每种算法运行时对应的rand函数种子相同(其中i表示在算法中的当前运行次数),每一种算法独立运行50次。
测试函数中f1~f3是单模函数,对于单模函数来说,算法的收敛速度比实验结果更值得关注,因此本文在列出比较结果的同时也列出比较函数在单模函数上的收敛比较图;对于f4~f5这种高维的多模函数,实验结果的精度比收敛速度更值得关注,因此在本文中列出了各种比较算法解的平均值和标准方差。对于以上两种函数本文分别测试各种比较算法在10,20以及30维下的运行情况。f6是具有较少局部最优点的低维函数,用以测试比较算法在低维函数上的运行情况。所有测试函数的理论最优解都为0。
3.2 实验结果及分析
对于单模函数来说,由于GQPSO针对gbest使用了Gaussian变异因子,因此能够在当前历史最优解附近进行有效的搜索。根据表2的结果可以看出,在单模函数上相对于其他比较函数来说,GQPSO都获得了最优的成绩。另外,图2的结果论证了该算法在收敛速度上都优于比较函数。对于复杂的多模函数,由于GQPSO相对于其他比较算法来说粒子具有更强的跳出局部最小点的能力,同时由于gbest能够提供给粒子群更为有效的进化方向,因此相对于其他算法来说,GQPSO更为彻底的搜索了解空间。根据实验结果无论是全局搜索能力还是稳定性,GQPSO都获得了最好的成绩。对于低维函数的优化能力参考表3的结果,GQPSO依然获得了最好的结果。
4 结论
针对粒子群算法无法保证搜索到全局最优的缺点和搜索精度低的问题,提出了一种基于Gaussian变异的量子粒子群算法(GQPSO)。典型函数优化的仿真结果表明,该算法不仅可有效的避免标准PSO算法的早熟收敛,而且具有寻优能力强、搜索精度高、稳定性好等优点。同比其他使用变异因子的粒子群算法,GQPSO表现出极强的全局搜索能力和快速的收敛速度,接下来该算法的应用和推广将是研究的重点。
摘要：粒子群算法相对于其他优化算法来说有着较强的寻优能力以及收敛速度快等特点,但是在多峰值函数优化中,基本粒子群算法存在着早熟收敛现象。针对粒子群算法易于陷入局部最小的弱点,提出了一种基于高斯变异的量子粒子群算法。该算法使粒子同时具有良好的全局搜索能力以及快速收敛能力。典型函数优化的仿真结果表明,该算法具有寻优能力强、搜索精度高、稳定性好等优点,适合于工程应用中的函数优化问题。
关键词：粒子群,高斯,变异,全局搜索,收敛速度
参考文献
[1]J.Kennedy and R.C.Eberhart.Particle swarm optimization[C],In ProcIEEE Int.Conf.Neural Networks,IV,Perth:IEEE Press,1995.1942-1948.
[2]Jehad I.Ababneh,Mohammad H.Bataineh.Linear phase FIR filterdesign using particle swarm optimization and genetic algorithms[C].Digital Signal Processing,2008,vol.18(4),pp.657-668.
[3]张长胜,孙吉贵,欧阳丹彤,等.求解车间调度问题的自适应混合粒子群算法[J].计算机学报,2009,32(11):2137-2146.
[4]Saska,M.,Macas,M.,Preucil,L.,Lhotska,L..Robot Path Planning usingparticle swarm optimization of Ferguson Splines[C].IEEE Con.EmergingTech.and Factory Auto.,2006,vol.20(22),pp.833-839.
[5]Daniel Bratton,James Kennedy.Defining a standard for Particle SwarmOptimization[A].Proceedings of IEEE Swarm Intelligence Symposium(SIS),Honolulu,USA.2007:120-127.
[6]SUN J,XU WB.Particle Swarm Optimization with Particle HavingQuantum Behavior[A].IEEE Congress.Evolutionary Computation.2004.325-331.
[7]Andrews.P.S.An Investigation into Mutation Operators for ParticleSwarm Optimization[C].IEEE Cong.On Evolutionary Computation,pp.1044-1051,Sep.2006.
[8]M.M.Ali,C.Khompatraporn,Z.B.Zabinsky.A Numerical Evaluation ofSeveral Stochastic Algorithms on Selected Continuous Global Optimiza-tion Test Problems,Journal of Global Optimization[J].pp.635-672,Nov.2005.
遗传算法中的变异算子的述评 篇4
遗传算法于1969年由美国Michigan大学的Holland教授提出后, 在保持其基本框架的基础上, 许多学者提出了不同的改进方法, 如自适应遗传算法、混沌遗传算法、量子遗传算法、混合遗传算法等。但算法的改进和问题本身相关, 并且遗传算法的基础理论仍未根本解决, 在进行算法改进时缺少理论的指导, 所以改进的算法没有普遍的适用性。虽然遗传算法有自身的不足, 但因其具有较强的鲁棒性, 在如金融, 自动控制, 模式识别, 组合优化, 故障诊断等领域都有成功的应用。
在遗传算法中, 变异算子通过模拟生物遗传和进化过程中的变异环节对个体进行变异, 虽然发生变异的可能性比较的小, 但也是产生新物种的一个不可忽视的原因[1]。通过变异不断在交叉算子产生的新个体的基础上进行微调、增加种群的多样性、使遗传算法在交叉算子决定的全局搜索能力的基础上还具有一定的局部搜索能力。变异算子被认为是必不可少的产生新个体的辅助方法, 文献[2]认为变异算子能够成为一个重要的遗传算子, 特别体现在维持种群的多样性问题上。正是变异算子在遗传算法中的不可或缺性, 本文在总结相关文献资料的基础上, 从不同角度对变异算子的改进进行讨论, 并展望其发展方向, 为遗传算法中变异算子的进一步发展提供参考。
1 变异算子的发展
简单遗传以初始种群为基点, 经过选择、交叉、变异操作生成新的种群, 如此更新种群直到满足终止条件。遗传算法中变异算子的具体操作是以变异概率Pm用新的基因值替代原有的基因值, 产生新的个体。变异算子对个体编码串的基因做了局部的改变, 维持种群的多样性, 这样有利于防止出现早熟现象。
1.1 传统的变异算子
用遗传算法求解问题时, 对于变异算子的选择首先会考虑已有的成熟的变异算子。几种常用的变异算子主要有基本位变异、均匀变异和高斯变异等。
1.1.1基本位变异是指对个体的每一个基因座, 依变异概率Pm指定其为变异点, 对变异点的基因值进行反转或用其他等位基因值来代替。
1.1.2均匀变异操作是指分别用符合某一范围内均匀分布的随机数, 以某一较小的概率替换个体编码串中各个基因座上的原有基因值。
1.1.3高斯变异操作是指进行变异操作时, 用符合均值为μ、方差为σ的正态分布的一个随机数来替换原有基因值。
还有如边界变异、非均匀变异等等, 这里不赘述了。可以看出变异算子的设计会涉及变异点位置的确定和基因值的替换两个方面。这两个问题的解决与编码及所解决的问题是密切联系的。上述的变异算子对多值编码都适用, 但考虑问题的特殊性, 变异算子又不能一概简单进行操作。如对TSP问题, 若用数字代表城市, 如用52134编码串表示5个城市的一种旅行路线。因问题本身要求城市不能重复出现, 这使得变异时不能通过对基因座上的基因值进行替换来实现。出现了如倒位变异和交换变异等变异算子。倒位变异是指将随机选取的两个基因座之间的基因进行逆序排序。变换变异是指对于随机选取的基因座之间的基因值进行交换。
1.2 改进的变异算子
在成熟的传统变异算子的基础上不少学者做了大量的研究和探索, 从理论, 克服早熟现象和应用等方面提出了许多改进方法, 有效提高遗传算法的性能。
1.2.1 变异算子在理论方面的研究
变异算子在理论方面的深入研究不多, 文献[3]给出了基于模式定理的变异概率上限确定公式, 由公式可知, 可以通过选择适当的变异概率, 使得某模式所含个体数目经过选择、交叉和单点变异等操作后得到增长。文献[4]提出了基于位变异的模式遗传算法。直接把模式作为个体, 使用的编码策略本质上比SGA的编码策略更加直接。并对其收敛性进行了分析。
1.2.2 变异算子在克服早熟现象上的改进
对变异算子的改进主要是针对遗传算法的局部搜索能力较弱及存在早熟现象, 许多研究者提出了许多改进的方法, 下面对此做个总结。
文献[5]提出基于细分变异算子的遗传算法。将变异算子细分为最优调教算子和大步前进算子两种算子的形式。文献[6]提出了一种新的改进遗传算法双变异算子遗传算法。通过将所有产生的子代个体与父代个体混合作为下一代种群, 在种群选择前对适应度值较低的个体进行一次变异, 然后通过选择、交叉, 再一次变异产生新种群, 再利用自适应算法改变交叉和变异率及最优保存策略保护历代最优个体, 双变异算子的遗传算法能够最大限度使种群多样性, 这样最有可能得到最优解, 也易突破局部收敛的局限而达到全局最优。文献[7]提出了一种双变异率的改进遗传算法。在进化过程中, 引入广义海明距离这个概念, 当由广义海明距离控制的交叉操作产生个体数不足种群规模时, 对原种群进行局部小变异, 这样在避免近亲繁殖的同时又可扩大搜索空间, 增加种群多样性, 有效地抑制了早熟收敛;随后进行的全局大变异保证整个过程全局收敛。文献[8]提出了一种基于位变异的防止遗传算法过早收敛的算法。该算法通过种群熵来判断过早收敛的发生。当发生过早收敛时, 在单调系数的指导下进行有针对性的位变异, 从局部最优解的范围内摆脱出来, 算法重新具有进化能力。文献[9]提出一种采用新的解码方案的动态变异遗传算法。文献[10]根据个体适应度不同对变异概率进行自适应调整, 使群体中的优良模式不易被破坏, 同时又保证了种群个体的多样性, 从而提高了算法的搜索效率。算法中改变了交叉与变异的操作顺序, 避免了个体适应度的重复计算, 提高运行速度。文献[11]提出了一种将强制变异、最佳解保留和自适应交叉变异参数调整相结合的改进遗传算法。这种方法将进化过程中群体的平均适应度与最大适应度进行比较, 以确定是否需要对群体实施强制变异或采用自适应交叉、变异概率调整。这种方法可有效地克服早熟现象, 提高全局优化能力。
1.2.3 变异算子在TSP的改进
组合优化问题是遗传算法通常解决的应用问题, TSP是典型的组合优化问题, 属于NP难问题。其变异算子的设计有其特殊性, 有学者在这方面也做了相应的研究。
文献[12]通过分析TSP问题的特征, 结合以减少周游路线中交叉边为启发式信息, 引入了一个遗传算法中新的变异策略用于TSP求解。该变异策略能够引导算法通过有指导性的变异更快地收敛到更好的解。文献[13]也在遗传算法解决tsp问题中进行了改进。提出多步强化变异, 其是在单步强化变异策略的基础上进行了改进, 通过向前考察几步个体进化效果, 将该信息向回传递, 影响个体变异策略。
2 遗传算法中变异算子的未来研究方向展望
通过与遗传算法中变异算子相关的文献的整理, 我们知道变异算子的改进有助于遗传算法性能的提高, 在总结已有研究的基础上, 提出以下几点未来研究方向:
2.1 加强遗传算法基础理论的研究
几乎对遗传算法中变异算子的改变都是从处理的实际问题出发的, 这种改进对于处理其他问题的遗传算法是否有效值得商榷。这种改进还是受到遗传算法基础理论的薄弱的限制。从遗传算法的收敛性, 早熟机理等方面从数学角度进行分析, 剖析变异算子的作用机理, 更好地改进变异算子。
2.2 变异算子与其他技术的结合
从上述的研究看, 变异算子的改进还是集中在对算子本身的直接改进, 可以借鉴其他算法特别是优化算法, 与变异算子进行结合, 提高变异算子对算法搜索性能的作用。
2.3 相关应用问题的拓宽
遗传算法应用领域比较广泛, 对变异算子的改进主要应用于函数优化问题, 今后可以探讨变异算子在不同问题中的改进方法。
3 结束语
遗传算法提供解决问题的基本框架, 确实带来一定优势, 但基本遗传算法的性能有待提高。可以从不同的角度进行遗传算法的改进, 其改进的切入点不仅和所解决的问题相关, 也和所使用的编码, 遗传算子及相关的参数相关。本文从变异算子的角度介绍了对遗传算法的改进方法, 加强了变异算子对传统遗传算法的作用, 改善了算法的搜索效率, 克服过早收敛的缺点, 为今后的遗传算法的发展提供借鉴。
摘要：遗传算法中的变异算子是必不可少的产生新个体的辅助方法。本文首先简单介绍传统的变异算子, 既而结合文献分析和讨论改进的变异算子, 并展望其未来研究方向, 为遗传算法中变异算子的进一步发展提供参考。
变异算法 篇5
关键词：自适应,量子免疫算法,盲检测,交叉变异算子
优化问题在科学研究和工程应用的各个领域具有重要的理论意义和实践价值, 人工免疫算法具有搜索效率高、种群多样性程度高等特点, 目前已经被广泛地应用于智能计算领域, 成为解决复杂优化问题的有力工具。量子计算具有高度的并行性, 大存储数据量以及指数级别的加速能力。量子免疫算法 (Quantum Inmune Algorithm) 是汲取了量子进化算法和人工免疫算法的各自优势而形成的新的优化算法, 它继承了量子进化算法的概念原理, 同时又扩展了免疫理论更新选择概念。量子免疫算法能够保持抗体种群的多样性, 同时也具有较好的收敛速度与效果。
Hongjian等人将免疫系统概念引入量子进化算法[1], 免疫算子在保留原算法的特性下力图有选择地利用待求解问题的特征信息和先验知识, 抑或是避免求解问题中的一些冗余工作, 从而提高算法整体性能。Haoteng等[2]提出了基于混沌理论的量子免疫算法, 该算法应用了混沌免疫理论, 并且根据小生镜机制将初始个体进行实数染色体编码子群, 使得各子群应用免疫算子的局部搜索能力找出最优解。李阳阳等[3]提出了一种基于量子编码的免疫克隆算法求解SAT问题, 特别针对种群中的个体采取了量子染色体编码的格式, 采用了量子旋转门和旋转角策略对抗体进行演化, 目的是为了加速克隆算子的收敛, 利用其局部搜索能力强的特点, 并且利用量子交叉信息算子提高了种群的多样性, 防止早熟。
但是量子免疫算法也存在一些问题, 例如, 在变异过程中种群的多样性并不稳定, 并不能保证能快速收敛到最佳适应度的个体, 出现停滞现象[4]。研究相关参考文献[5-6], 发现在量子算法的改进策略上通常都是采用针对变旋转角Δθ采取动态变旋转角的策略。这些策略虽然均取得了较好的效果, 但策略自身也具有局限性, 如不具备通用性, 需要根据具体问题具体优化;参数构成复杂, 实现难度大, 这种变异策略牵涉的参数过多, 效果难以控制, 复杂度增加。
综上所述, 为了更好地应用于盲检测, 不仅仅可以在量子变旋转角上进行改进, 也可以在免疫变异策略和旋转角变化趋势上进行演进。
1 SIMO盲检测模型
忽略噪声时, SIMO离散时间信道的接收方程定义为
式中:XN是接收数据阵;S是发送信号阵;Γ是由信道冲激响应hjj构成的块Toeplitz矩阵;XN=[xL (k) , …, xL (k+N-1) ]T是N× (L+1) q接收数据阵, 其中xL (k) =Γ·sL+M (k) 。其中, 发送信号阵可表示为
式中:M为信道阶数;L为均衡器阶数;N为所需数据长度;sL+M (k) =[s (k) , …, s (k-L-M) ]T。其中, s∈{±1}, Γ=[h0, …, hM]q× (M+1) ;q是过采样因子, 取值为正整数。
对式 (1) , Γ满列秩时, 有Q=UcUcT满足QsN (k-d) =0, Uc是N× (N- (L+M+1) ) 酉基阵, 由奇异值分解中得到;U是奇异值分解中的N× (L+M+1) 酉基阵;0是 (N- (L+M+1) ) × (L+1) q零矩阵;V是 (L+1) q× (L+1) q酉基阵;D是 (L+M+1) × (L+1) q奇异值阵。
据此构造性能函数及优化问题为
式中:Q=UcUcT;d为延时因子, d=0, …, M+L。如此, 信号盲检测问题就成为了求解式 (3) 的全局最优解问题。
本文就是利用基于自适应交叉变异算子的量子免疫算法来解决这一问题。本文定义量子免疫算法的适应度函数为:采用基于自适应交叉变异算子的量子免疫算法进行寻优搜索, 将此适应度函数作为目标函数进行寻优, 将盲检测问题的求解等效为求适应度函数F的最小值, 即
2 基于自适应交叉变异算子的量子免疫盲检测算法设计 (SCOQIA)
在种群更新选择算子中, 交叉概率和变异概率是影响算法行为和性能的关键。量子免疫算法中, 量子交叉和量子变异由量子门控制。而在传统的免疫算法中, 则由交叉算子 (cross-over operator) 和变异算子 (mutation operator) 组成, 采用固定的交叉概率和变异概率。本文提出一个新的思路:采用传统免疫算法中交叉和变异算子策略, 又同时引入了基于自适应策略的量子免疫交叉与变异算子, 为更好地加强种群的进化程度, 算法利用量子交叉与量子变异进行进化。在一般情况下, 如果在算法初始阶段采用较小的交叉率和变异率, 很难产生优秀的新个体, 算法后期, 模式朝着高适应度方向演进, 如果仍采用较大的交叉率和变异率, 会对种群的优良性产生影响, 造成过度进化, 同样会使优化结果陷入局部极小。
针对上述问题, 固定的量子免疫交叉算子Pc和变异算子Pm不能适应种群变异的变化幅度, 容易陷入局部最小, 因此可以根据种群适应度变化的实际情况, 将交叉算子Pc和变异算子Pm进行动态调节。具体方法如下。
定义种群数量为Ns, 多样性因子Ms为
式中:fmax为适应度最大值;fave为平均适应度, 即
本文提出的自适应策略构造与分析如下。如果Ms=1, 则表明种群中抗体未变异, 种群基因相同, 多样性最低。为了避免早熟, 交叉算子Pc和变异算子Pm必须进行变化, 以增加种群的多样性, 即增大Pm, 减小Pc。
自适应交叉, 变异选择策略如表1所示。
其中交叉算子在算法中占主导因素, 默认取值范围为0.35
图1是基于自适应交叉变异算子的量子免疫算法流程图。
实施过程如下:
1) 设定初始化量子种群Q及相关参数, 如最大迭代次数等;
2) 对第一代种群进行观察操作, 得到第一代量子个体;
3) 对种群中每个量子个体计算其适应度, 并选择适应度最小的个体为抗体;
4) 识别抗原, 针对适应度函数寻优问题, 做免疫疫苗接种;
5) 按照自适应的变化概率, 即变异算子Pm对种群进行量子免疫变异操作;
6) 按照自适应的变化概率, 即交叉算子Pc对种群进行量子免疫交叉操作;
7) 对生成的个体进行适应度函数的评估, 并且对自适应算子做出动态调整;
8) 使用量子选择门对抗体种群进行更新;
9) 找出最佳个体, 如果符合程序结束条件, 则结束程序流程, 如果为否, 则进行最优解分析, 更新到抗体记忆库中;
10) 达到最大迭代次数时, 终止迭代, 输出全局最优解及适应度函数值。
3 仿真结果与分析
为了验证基于自适应交叉变异算子的量子免疫盲检测算法的性能, 本文利用MATLAB软件进行了仿真实验。发送信号调制方式为BPSK信号, 噪声为均值为0的高斯噪声。实验说明:1) 改进的量子免疫盲检测基本参数:序列长度60, 信道阶数为3, 仿真平台是MATLAB7.8.0.343 (R2010a) 。2) 所有仿真实验的数据是根据100次的Monte Carlo实验获得, 为了图像的可读性, 仿真实验图中误码率 (BER) 为0的处理为10-5[14]。
实验中主要采用3种经典信道, 信道1:按指定延迟delay=[0, 1/3]、权系数w=[1, -0.7]产生信道, 信道头尾各补q (过采样因子) 个零;信道2:文献中给出的含一个公零点, 权值和延时固定的合成信道;信道3:更能体现时变信道特点的权值和延时度变化的随机合成信道。
1) 实验1:改进的量子免疫算法在3种不同信道下的误码率与信噪比的关系。
基于自适应交叉变异算子的量子免疫算法 (SCO-QIA) 在不同信道下的信噪比-误码率 (SNR-BER) 性能曲线如图2所示。
由图2可知, SCOQIA算法在3种不同的信道条件下, 随着信噪比的增大, 误码率也呈现下降趋势, 最终都降为0, 说明改进后的量子免疫算法能够有效地进行盲检测, 表明了改进后算法对不同信道具有适用性, 对信道具有较强的鲁棒性。
2) 实验2:研究初始参数调节因子参数组{Vmax, Vmin, Pc, Pm}对自适应交叉变异算子的量子免疫算法 (SCOQIA) 盲检测性能的影响。
在仿真实验中观察不同参数对算法性能的影响大小。选取信道3作为测试环境。在本实验中, 选取不同的几组测试参数组, 设置为如下3组:U1={0.25, 0.05, 0.60, 0.15};U2={0.25, 0.05, 0.80, 0.25};U3={0.15, 0.03, 0.80, 0.25}。
由图3可以看出, 在选择不同参数的情况下误码率均随着信噪比的增加而降低, 对比参数组U1和U2, 其中U2较U1降低了交叉概率和变异概率, 而策略选择区间保持不变, 可以看出选择U1在8 d B误码率才降为0, 而U2在7 d B误码率就收敛为0, 因此可以推断交叉变异概率参数的选择对自适应交叉变异算子的量子免疫算法 (SCOQIA) 算法的盲检测效果影响较大, 根据实际试验选择合适变异概率能够在盲检测中取得较好的效果。
对比参数组U2和U3, 其中控制两组交叉概率和变异概率相同, 扩大了策略选择区间, 发现改进的SCOQIA算法在盲检测性能上变化不大, 信噪比均能在7 d B左右降为0。因此可以推断, 交叉概率Pc和变异概率Pm的初始取值会影响自适应策略变化的结果, 综合变异概率和交叉概率的优化效果, 在本实验环境中选取适当偏大的交叉概率Pc和变异概率Pm盲检测效果更佳。
3) 实验3:改进算法与基本算法误码性能的对比。
本实验在信道3条件下进行。实验主要目的是将自适应交叉变异算子的量子免疫算法 (SCOQIA) 与基本量子免疫算法 (QIA) 在同一信道环境中进行仿真模拟, 其信噪比-误码率性能曲线如图4所示。
图4可以看出改进的基于自适应交叉变异算子的量子免疫优化盲检测算法 (SCOQIA) 在信噪比为7 d B处降为0, 而基本量子免疫优化盲检测算法则在信噪比为8 d B处降为0, 由此证明了改进算法在性能上的优越性。
4 结论
本文提出了改进量子免疫优化盲检测算法:即基于自适应交叉变异算子的量子免疫优化算法。通过仿真实验验证了改进后算法在相同信噪比条件下误码率更低, 收敛速度更快, 即从盲检测算法的评价指标考虑, 均说明改进的算法具有一定的优越性, 表明本文提出的算法能够成功应用到盲信号检测中, 具有一定的研究价值。
参考文献
[1]QU Hongjian, ZHOU Fangzhao, ZHANG Xiangxian.An application of new quantum inspired immune evolutionary algorithm[C]//Proc.20091st International Workshop on Database Technology and Applications.Wuhan:IEEE Press, 2009:468-471.
[2]HAO Teng, YANG Bingyu, ZHAO Baohua.A new mutative scale chaos optimization quantum genetic algorithm[C]//Proc.Chinese Control and Decision Conference.Yantai:IEEE Press, 2008:1547-1549.
[3]李阳阳, 焦李成.求解SAT问题的量子免疫克隆算法[J].计算机学报, 2007, 30 (2) :176-183.
[4]吴秋逸, 焦李成, 李阳阳, 等.自适应量子免疫克隆算法及其收敛性分析[J].模式识别与人工智能, 2008 (5) :592-597.
[5]马颖, 田维坚, 樊养余.基于云模型的自适应量子免疫克隆算法[J].计算物理, 2013 (4) :627-632.
变异算法 篇6
遗传算法(Genetic Algorithm-GA)的产生最早归功于美国Michigan大学的Holland在20世纪60年代末、70年代初开创性工作[1],是模拟生物遗传和自然淘汰的生物进化过程的一种模型。与传统的优化算法有较大的不同,遗传算法有其自身的优点,主要表现在以下几方面[2](1) GA在每个时刻都可以对多个子空间进行搜索,对初始值不做要求。(2) 在GA中仅靠适应度来评价个体优劣,基本上不用搜索空间的知识或辅助信息。(3) GA具有很强的鲁棒性。虽然GA具有诸多的优点,但作为全局搜索算法,仍然存在无法全局收敛的情况,发生这种情况较为典型的是“早熟”现象。遗传算法“早熟”是指群体多样性遭到破坏,算法搜索停滞不前,最终收敛到一个局部最优解,而无法收敛到全局最优解。“早熟”现象的本质特征是因为群体多样性受到破坏。
在选择算子的作用下,优秀模式会大量增加,低劣模式会迅速减少,整个群体向好的方向进化,但是在选择算子的作用下,群体丧失了多样性,群体进化中后期就可能产生“早熟”现象。针对传统遗传算法“早熟”现象,许多的研究人员对其进行了改进,如文献[3]作者通过改进传统的选择算子,从而对传统GA进行了改进,文献[4]采用种群多样性算子产生较好的初始种群分布,并以该算子作为判断种群是否早熟收敛的依据。本文分析研究了“早熟”现象产生的原因,通过改进传统杂交算子和引入二元变异算子来替换传统变异算子对遗传算法进行了改进,实验结果证明,改进后的算法有效的抑制了“早熟”现象的出现。
1 简单遗传算法(Simple Genetic Algorithm)
标准遗传算法的运行过程为一个典型的迭代过程,其必须完成的功能工作内容及主要步骤如下:
1)选择合适的编码策略,把实际问题的参数集合X和域转化为位串结构空间S;
2)定义一个合适的适应度函数f(X);
3)确定所需要的遗传策略,其中包括选择群体大小N,选择交叉及变异方法,以及确定交叉概率pc、变异概率pm等相关的遗传参数;
4)随机初始化生成群体P;
5)计算群体中个体位串解码后的适应值f(X);
6)按照确定的遗产策略,运用相关的选择算子、交叉算子和变异算子作用于群体,形成下一代群体;
7)判断群体性能是否满足某一指标,或者已完成预定的迭代次数,不满足则返回步骤6),或者修改遗传策略再返回步骤6)。
2 算法改进
2.1 交叉算子的改进
在传统的遗传算法中,经常会出现“近亲繁殖”现象。所谓“近亲繁殖”现象即:一对父母A,B经过遗传操作后产生的一对子代为ab1、a1b、ab1、a1b随即被放入子代中。然而在进化到下一代或者下几代的时候,ab1、ab1很有可能作为新的父母进行遗传操作,此时即发生了“近亲繁殖”。这也是造成群体单一性的主要原因之一。
本文通过引入一个相似度系数(0到1之间的数)的概念,来改进交叉算子。其步骤为:
(1) 以一定概率随机选择两个个体作为父母。
(2) 对两个个体的相对应的基因位进行比较,用两者相同基因位的个数除以个体染色体总长度,把结果定为相似度,如果相似度小于0.5或者达到实际要求的标准,则可以进行交叉,否则返回步骤1。
(3) 反复执行以上两步操作,直到生成的子个体数量满足条件为止。
2.2 变异算子
传统的变异算子执行的是一元取反操作,操作数只需要一个基因,无法有效地保持同一基因位上等位基因的多样性[5],这也是产生“早熟”现象的主要原因。文献[5]中作者提出了一种新的二元变异算子,并通过实验验证了这种变异算子确实优于目前所采用的传统变异算子,所以本文采用这种二元变异算子来替换传统的变异算子。
传统的变异算子只需要对一条染色体进行操作,所执行的操作是一元取反操作,与传统变异算子不同,二元变异算子采用的是两条“染色体”进行参与,具体操作如下:
因为“同或/异或”的逻辑运算规律,运算后的两种逻辑状态是互补的,也就是说,同一基因位上的不同种类的基因经过变异后同时存在,从而有效的避免了基因位的缺失。
2.3 改进后算法流程和步骤
改进算法的流程图如图1。
基于相似度交叉算子和二元变算子的GA算法的执行步骤如下:
(1)种群初始化,计算个体适应度。
(2)遗传操作:
① 执行选择操作,选择一对父母。
② 执行相似度交叉操作,判断相似度,若相似度<0.5或者满足实际需求,则执行(3),否则返回(1)。
③ 执行二元变异操作。
(3) 计算适应值,若满足程序终止条件,则程序结束,进入下一个体或者下一代循环。
3 改进算法有效性实验
为了验证算法的有效性,本文采用两个典型函数对改进的算法进行测试,并与标准算法进行比较。
(1)f1=x sin(10πx)+2.0; -1≤x≤2。
此函数是一个一维连续的、包含三角函数的多峰值函数,其最大值为3.085 3,此测试函数是求最大值。
(2)f2(x)= exp(-0.001x)cos2(0.8x), x >0。 此函数其全局最大值是1.0,最大点为0。
为了更好的比较改进后的算法的有效性和正确性,分别对改进后的算法和标准GA算法进行仿真。改进算法的参数设置如下:采用两个规模为50的子群体,交叉概率设置为0.90,变异概率设置为0.01,进化代数为100代。标准算法的参数设置与改进算法相同,对两种算法各进行100次仿真。算法实验结果如表1。
本文采用目标函数作为适应值计算函数,进化代数为100代后终止进化。通过多次的实验仿真,我们从仿真结果中可以看到改进后的算法无论在最优解或者是收敛速度上都有明显的改进。
4 结语
针对标准GA算法的“早熟”现象,本文通过改进传统的交叉算子,避免了“近亲繁殖”的现象的出现,一定程度上保证了群体的多样性。采用二元变异算子替换传统的变异算子,保证了同一基因位上等位基因的多样性,起到了很大的局部微调的作用,上述的改进方法使得改进后的遗传算法在性能上大大的优于传统的GA算法。
参考文献
[1] Holland J H.Adaptation in natural and artificial systems.Ann Arbor:The University of Michigan Press,1975
[2]周育人.一类改进的遗传算法及其优化性能分析.2003;25(1):1—3
[3]陈有青,徐蔡星,钟文亮.一种改进选择算子的遗传算法.计算机工程与应用,2008;44(2):44—49
[4]林锐浩,陈晓龙.基于种群多样性指导的遗传算法.计算机工程与设计,2005;26(11):3100—3102
变异算法 篇7
随着Internet和多媒体技术的发展, 网络多媒体业务迅速增长, 对网络服务质量 (QoS) 提出了更高的要求, 如何充分利用网络资源来满足日益多样化的QoS要求已成为人们关注和研究的热点。QoS网络路由的目的就是在分布的网络中寻找一条最佳路径, 从源节点出发, 历经所有目的节点, 同时满足所有QoS约束以保证网络服务质量, 并且费用最小。目前, QoS路由的研究主要分为:单播路由 (Unicast Routing) 、组播路由 (Multicast Routing) 和选播路由 (Anycast Routing) 。文献[1]已经证明具有两个及以上约束条件的QoS路由问题是一个NP-完全问题。近几年来, 国内外许多研究人员相继提出了许多QoS路由算法, 如蚁群算法[2,3,4,5,6]、遗传算法[7,8,9,10]和模拟退火算法[11]等, 并取得了一定的成果。
蚁群算法是文献[12]提出的一种优化方法, 它以蚂蚁觅食行为为基础, 用蚂蚁的行走路线表示待求解问题的可行解, 不依赖于具体问题的数学描述, 具有很强的全局优化能力, 已广泛应用于组合优化中的NP-完全问题。但蚁群算法本身也存在一些缺点, 如收敛速度慢、易陷入局部最优。许多学者提出了一些改进策略, 并应用于QoS路由优化上, 取得了一定的成果[2,3,4,5,6]。本文针对基本蚁群算法的缺陷, 给出了一种改进的可选节点集优化的变异蚁群算法对QoS单播路由问题进行求解, 采用混合蚂蚁行为, 根据QoS约束条件以及当前的最优路径对可选节点集进行优化, 引入二次变异策略, 借助节点使用计数器, 进行二次蚁群搜索机制, 提高了收敛速度, 减少了陷入局部极值的可能性, 增强了寻优能力。
1 QoS单播路由问题模型
本文只讨论包含带宽、延时和费用三个QoS约束条件的网络模型, 如图1所示。
用一个无向赋权图G<V, E>表示网络, 其中V={V1, V2, …, VN}表示网络节点集, N表示网络节点数, E={e1, e2, …, eM}表示双向链路集, M表示网络链路数, 每条链路ei∈E上包含三个属性, 用三元组表示 (bandwidth, delay, cost) , 分别表示链路的带宽、延时和费用。对于任一链路ei∈E, 定义三种度量, 延时函数delay (e) :E→R+, 费用函数cost (e) :E→R+, 带宽函数bandwidth (e) :E→R+。对于给定的源节点s∈V, 目的节点t∈{V-{s}}, s和t组成的路径p (s, t) 存在下列关系:
(1)
(2)
(3) bandwidth (p (s, t) ) =min{bandwidth (e) , e∈p (s, t) }
QoS单播路由就是要寻找一条从源节点s到目的节点t∈{V-{s}}的一条路径p (s, t) , 满足:
(1) 延时约束 delay (p (s, t) ) ≤D
(2) 带宽约束 bandwidth (p (s, t) ) ≥B
(3) 费用约束 在所有满足 (1) 和 (2) 条件的路径中, cost (p (s, t) ) 最小。
其中, D和B分别是路径p (s, t) 规定的延时和带宽约束值, 即QoS约束条件。
2 基本蚁群算法
蚁群算法的基本思想是:蚂蚁在觅食过程中会在路径上释放出信息素, 后面蚂蚁根据遗留的信息素选择下步走要走的路径, 路径上的信息素值越高, 蚂蚁选择这条路径的概率越大, 从而构成一个正反馈过程[12]。
(1) 蚂蚁状态转移规则
在t时刻蚂蚁由当前节点i选择下一节点j的规则是:
其中sk表示蚂蚁k所选择的下一节点;τij (t) 表示t时刻链路 (i, j) 上的信息素强度;参数α表示信息素的重要程度;参数β表示启发信息的重要程度;allowedk表示t时刻蚂蚁可以选择的节点集;ηij (t) 表示启发函数;q为[0, 1]上的随机数;q0为参数 (0≤q0≤1) ;S是根据式 (2) 计算出的下一选择节点。
(2) 信息素局部更新规则
对于第k只蚂蚁, 如果节点r和s是其所选择路径上的两个相邻节点, 信息素τ (r, s) 按下式进行更新:
τ (r, s) = (1-a0) τ (r, s) +Δτ (3)
式中:
其中:0<a0<1, Q0为常数, Lk为蚂蚁k本一次循环中所走过的长度。
(3) 信息素全局更新规则
在每次循环结束后, 仅对全局最优的路径上的信息素进行更新。如果节点r和s是两个相邻节点, 信息素τ (r, s) 按下式进行更新:
τ (r, s) = (1-ρ) τ (r, s) +ρΔτ (r, s) (4)
式中,
其中0<ρ<1;Q为常数;表示节点之间信息素强度;Lbest表示所有蚂蚁在一次循环中的全局最优路径。
3 可选节点集优化的变异蚁群算法
针对基本蚁群算法在求解QoS单播路由问题时容易陷入局部最优和收敛速度慢的缺点, 本文提出了可选节点集优化的变异蚁群算法, 其改进策略如下:
(1) 使用节点计数器策略 增加一个节点使用计数器NodeSum (1, N) , 计数器中每个节点的使用次数初始化值都为0, 即NodeSum (1, j) =0, ∀j∈N, 蚂蚁爬行时每经过一个节点j一次, 该节点的计数值就增加1, 即:
NodeSum (1, j) =NodeSum (1, j) +1
(2) 可选节点集优化策略 在蚂蚁由当前节点选择下一节点前, 先对下一初始可选节点集进行判断和筛选, 把那些不符合QoS约束条件以及比当前最优路径差的初始可选节点从可选节点集中删除, 得到优化后可选节点集。这样做的目的是避免太多无效搜索, 使当前最优路径对后面蚂蚁产生除信息素更新外的又一个搜索方向指示信息, 使得后面搜索方向更明确, 以提高搜索效率。
例如, 有1个蚂蚁爬行到当前路径为Path, 当前搜索到的最优路径为Pathbest, 由当前节点选择下一节点的初始节点集为allowed= (V1, V2, V3, V4) , 根据上面的策略, 如果Path+Vi (i=1, 2, 3, 4) 不符合QoS约束条件或者目标函数Path+Vi劣于Pathbest, 则将Vi删除, 假如 (V1, V2) 不符合, 则由当前节点选择下一节点的可选节点集就变为allowed= (V3, V4) 。
(3) 变异前蚂蚁爬行策略 为了使变异前的蚂蚁爬行路径多样化, 受混合行为的蚁群算法[13]的启发, 定义了8种不同行为蚂蚁爬行策略, 保持了初始路径的多样化, 有利于后面的变异能在较宽的领域进行搜索。这8种蚂蚁行为分别定义为:
行为1 蚂蚁以随机方式选择下一节点;
行为2 蚂蚁以目标启发函数贪心方式选择下一节点;
行为3 蚂蚁以目标启发函数轮盘选择方式选择下一节点;
行为4 蚂蚁以信息素与目标启发函数结合的函数贪心方式选择下一节点;
行为5 蚂蚁以信息素与目标启发函数结合的函数轮盘选择方式选择下一节点;
行为6 蚂蚁以信息素贪心方式选择下一节点;
行为7 蚂蚁以信息素轮盘选择方式选择下一节点;
行为8 利用前面定义的节点使用计数器, 蚂蚁以爬行节点次数最少的方式选择下一节点。
(4) 变异时蚂蚁爬行策略 在t时刻蚂蚁由当前节点i选择下一节点s时, 并且不仅仅根据上式 (2) 来决定, 同时把上面所定义的节点使用计数器考虑进去, 在一定的概率下, 让蚂蚁选择节点计数值最小的节点, 即蚂蚁走过次数最小的节点, 使未被访问的节点有被访问的可能性。这样, 即保证蚂蚁往比较优的路径上爬行, 也在一定程度上有利于跳出局部极值。具体选择按下式进行:
其中, q1为参数 (0<q1<1) , 其余定义与式 (1) 和 (2) 相同。本文仿真中,
(5) 第一次变异 在设定的M只蚂蚁执行完一次搜索后, 对当前搜索到的符合QoS约束条件的从源点到目的节点的路径进行变异和二次蚁群算法搜索。具体策略如下:假设某条合格路径为Path= (1, 17, 3, 12, 20) , 该路径长度为length (Path) =5, 则其变异长度定义为L=round (length (Path) /3) , 即变异长度为接近总长度的1/3的整数, 这样使得变异前和变异后的路径差异不太大, 而且使得变异后的路径是在变异前的路径的基础上发生局部变化而进化得来的, 符合进化算法的思想。在本例中L (Path) =2, 即变异长度为2。Mutated为变异的次数, 固定为一常数, 每次根据变异长度L (Path) 随机产生两个变异点R1和R2, R2=R1+L, 然后按照上述蚂蚁爬行规则, 执行二次蚁群算法搜索R1和R2之间的路径。如果变异后搜索到的路径优于当前的最优路径, 则将变异后的路径替换当前的最优路径, 例如, 变异后的路径变为Pathmutated= (1, 17, 12, 20) , 然后比较Pathbest和Pathmutated, 若后者优于前者, 则用后者替换前者;如果变异后搜索到的路径优于变异前的路径, 则将变异后的路径替换变异前的路径;然后进行下一次变异, 如此重复, 直到执行完Mutated次变异。
(6) 第二次变异 在第一次变异执行完后, 对当前搜索到的最优路径按照第一次变异时的策略进行变异。
经过二次变异和二次蚁群搜索, 能够很大程度上跳出局部最优, 快速地向全局最优进化。
(7) 信息素局部更新 这里仅对符合约束条件的路径的链路的信息素进行局部更新, 对于那些死亡或者不符合约束条件的链路, 虽然蚂蚁也走过, 但不进行信息素局部更新。
(8) 如果在设定的k次迭代内找到的最优路径没有发生过改变, 则对所有的链路信息素进行重新设置, 具体为:
τ
式中τ
上述的改进策略即保证了在下一周期搜索时倾向于部分较优解附近, 提高算法的收敛速度, 又保证了使蚂蚁倾向于未搜索过的链路, 减少算法陷入局部极值的可能性, 增强了算法的全局寻优能力。
另外, 根据最大—最小蚂蚁系统[14]策略, 将每条链路信息素限制在[τmin, τmax]区间内, 具体策略如下:
利用本文算法求解QoS单播路由的详细步骤如下:
Step1 设置请求单播路由源节点Vs, 目的节点Vd, 带宽约束B, 延时约束D, 删除不满足QoS约束的链路, 得到新的网络拓扑图。
Step2 设置蚂蚁种群数量m, 最大迭代次数DiedaiNum, 设定的迭代次数shedingDiedai, 变异次数Mutated, 初始化各链路信息素强度τ, 节点使用计数器NodeSum, 参数α, β, q0, q1, a0, Q0, ρ, Q, 迭代次数l=0, 最优路径记录Pathbest。
Step3 迭代次数l=l+1, 在源点创建m只蚂蚁分组, 初始化禁忌表, 并将源点加入禁忌表, t=0, 节点使用计算器:
NodeSum (1, Vs) =NodeSum (1, Vs) +m
Step4t=t+1, i=1;对每只蚂蚁分组k, 由当前节点Vi选择下一节点Vj前, 先根据QoS约束条件和当前最优路径对可选节点集进行优化, 把不符合要求的可选节点从可选节点集中删除, 得到新的可选节点集。
Step5 变异前节点选择按上述改进策略 (3) 的方式进行, 变异时节点选择按上述改进策略 (4) 的方式进行, 由当前节点Vi选择下一节点Vj, 然后, 根据下面三种情况再进行判断 :
(1) 如果Vj∈ϕ, 且Vi≠Vd, 则蚂蚁死亡;
(2) 如果Vj∉ϕ, 且Vi≠Vd, 则继续搜索, 下一搜索Vi≡Vj;
(3) 如果Vi≡Vd, 则蚂蚁完成搜索。
然后, 把节点Vj加入禁忌表, 更新节点使用计数器:
NodeSum (1, Vj) =NodeSum (1, Vj) +1
Step6 重复执行Step 4直到蚂蚁死亡或者蚂蚁完成搜索。
Step7 记录完成从Vs到Vd搜索的路径p (Vs, Vd) 。
Step8 计算路径p (Vs, Vd) 的目标函数值, 对p (Vs, Vd) 的链路按式 (3) 进行信息素局部更新, 更新后按式 (7) 进行判断, 并与当前的最优路径进行比较, 如果优于当前的最优路径, 则更新当前的最优路径Pathbest=p (Vs, Vd) 。
Step9 对m只蚂蚁爬行找到的符合约束条件的路径p (Vs, Vd) 进行第一次变异和二次蚁群搜索, 变异次数为MutatedNum。具体方法, 如上改进策略 (5) 所述, 如果变异后的路径优于当前的最优路径, 则更新当前的最优路径。
Step10 对进行第一次变异后的当前最优路径进行第二次变异和二次蚁群搜索, 变异次数为MutatedNum。具体方法, 如上改进策略 (6) 所述, 如果变异后的路径优于当前的最优路径, 则更新当前的最优路径。
Step11 根据式 (4) 对执行二次变异后的当代最优路径Pathbest的链路进行全局信息素更新, 更新后按式 (7) 进行判断。
Step12 判断在设定的shedingDiedai次迭代内最优路径有无变化, 如果没有变化, 则根据式 (6) 对更新后的链路信息素进行重新设置。
Step13 转Step3, 进入迭代循环。
Step14DiedaiNum次迭代结束后, 输出当前的最优路径Pathbest, 算法结束。
4 仿真实验
本文算法用图1所示的网络模型进行仿真, 只考虑链路的带宽、延时和费用约束, 链路属性用三元组表示 (带宽, 延时, 费用) 。
有1个QoS单播路由请求, 源节点为“1”, 目的节点为“20”, 约束条件值分别为B=8, D=12。
本文算法和基本蚁群算法参数设置为:VS=1, Vd=20, M=8, DiedaiNum=20, shedingDiedai=3, Mutated=5, τ0=1, NodeSum0=0, α=1, β=1, q0=0.4, q1=0.7, a0=0.1, Q0=3, ρ=0.3, Q=10。仿真结果如表1和图2所示。
由仿真示例可见, 本文算法在10次迭代内就能收敛到全局最优解 (1, 17, 12, 20) , 收敛速度快;而基本蚁群算法在20次迭代内只收敛到局部最优解 (1, 17, 3, 16, 20) , 收敛速度慢, 陷入局部最优。仿真结果验证了本文算法是可行和有效的, 并且能够跳出局部最优, 快速收敛到全局最优解。
5 结束语
针对QoS单播路由问题, 本文提出了一种改进的可选节点集优化的变异蚁群算法。该算法采取混合蚂蚁行为, 优化可选节点集, 通过二次变异, 借助节点使用计数器, 引入二次蚁群搜索机制, 减少了算法陷入局部极值的可能性, 提高了算法的寻优能力和收敛速度。实验结果证明了上述结论。