为了改善粒子群优化算法的收敛速度，在布朗运动和伊藤过程的启示下，提出了一种混合布朗运动和粒子群优化算法这两种思想的改进算法。通过对布朗运动和伊藤过程进行抽象，设计了漂移算子和波动算子。漂移算子保留了粒子的位置属性，但没有了速度属性，并引入了吸引子的概念，借鉴差分变异算子设计了波动算子。通过解决典型的复杂函数优化问题，实验结果表明，改进算法具有收敛速度快的特点，并具有良好的健壮性和稳定性。
第7期 徐星,等:基于布朗运动的改进短子群优化算法 2441 b)计算每个粒子的适应度值,并根据适应度值确定出个 表1列出了在五个测试函数上两种算法的性能统计信息, 体最优值、个体最优值对应的个体与全局最优值、全局最优值包括成功收敛的比率(算法获得的最优解与真实最优解的值 对应的个体。 小于1e-6,本文认为收敛)50次中最差的、平均的以及最好 c)对每个粒子,比较其适应度值和它经历过的最好位置p.的结果和标准差。图1~5给出了在F、F2、F3和F4和F5上 的适应度值。如果该粒子的适应度值比p对应的适应度值更两种算法的最佳适应值收敛曲线。 好,则更新p。 表1 BMPSO和PSO的实验统计结果 d)对每个粒子,比较它的适应度值和群体经历过的最好数第法最优解最差解均值 标准差收敛比率 1.1355 37.4914 位置p的适应度值。如果该粒子的适应度值比p对应的适 7.55636.6796090/ BMPs05.4103e-381.0759e-358.0689e-361.7092a-3550/50 应度值更好,则更新P2。 5452e-028968e-013.2050e-0l|.8962a-0lD:50 e)对每个粒子:for(d=0;i<D;d-+) 6.6954e+0l2.86yle+021.882le+024.5089g+UlU/5U BMPSO if (rando)< CR) 2.0326e+0l2.1157e+012.0899e+0l1.8448g-01 根据式(4)调整粒子的位置Ⅹ; F∠ BMPSO5.8872e-165.8872e-165.8872e-16L.9921e-3150/50 L.0000 0.99028410.9995463.9645-0347/50 BMPSO 1.0000 0.99999950.99999992.4164-0750/50 Xd保持不变 7111A)量2 其中:D表示粒子的维数;rand()是在[0,1]内满足均匀分布的 随机数;CR是一个概率阈值。 f)如果达到结束条件,则结東;否则转步骤b)。 3实验仿真与结果分析 04080120160200 04080120160200 图1 BMPSO和PsO 图2 BMPSO和PSO 3.1测试函数 在F1上的适应值变化曲线 在F2上的适应值变化曲线 在文的实验屮,使用了五个经典的测试函数,这些函数 经常被国内外很多学者用来测试优化算法的性能和可靠性。 用本文提出的BMⅣO算法和标准粒子群算法同时求解优化问 题,以对比考察各种算法的性能。 测试函数如下 F1(x)=∑x2,-100≤x;≤100 04080120160200 04080120160200 generation F2(x) ∑x2-∏cos( 1,-100≤x;≤100 图3 BMPSO和PsO 图4BMPS0和PsO 4000 在F3上的适应值变化曲线 在F4上的适应值变化出线 F:(x)=∑(x-10cos(2x;)+10),-100≤x;≤100 -0.965 F4(x)=-20exp(-0.2 ∑x2) exp N ∑cos(2丌x;))+ 0.97 -0.975 32≤x1≤32 F 1-0.001(x2+x2) 0.5.-100≤ -0.995 其中:F1为单峰两数,F2、F3和F为多峰数,存在多个局部 0400800120016002000 最优解,并且其局部最优解的个数随着维数的增加呈指数增 图5BMPS0和PS0在F上的适应值变化曲线 加。这四个函数均在(0,0,…,0)处取得全局最优解。F5在 从以上的实验数据可以作出如下的分析和判晰: (0,0)点处取得全局极小值-1,而在距该点约3.14范围内隆 表1中收敛比率清晰地展示了RMFO算法的稳定性 起部的无穷多个次全局极小点,次全局极小值约为-0.990 BMPSO算法的收敛比率远高于PSO,注意到 BMPSO算法在五 284。出于F的强烈震荡性质以及它的全局最优点被次最优 点所包围的特性,使得一般算法难以找到它的仝局最优解。 个测试问题上的各50次运行中都能保证100%成功地收敛到 全局最优解。 BMPSO算法的收敛精度和搜索得到解的质量方 3.2实验结果与分析 面要优于PSO算法;同时,BMRO算法比PSO算法所得的方 前四个函数的维数为30,标准Ⅳ0算法中,和群大小均设差要小,这说明BMSO算法具有更强的鲁棒性和稳定性。 置为20,迭代次数设置为20,标准SO中惯性权重ω从1.0 由图1~5可见,BM"S算法对应的目标函数下降曲线比 线性递减到0,速度最大值为20; BMPSO算法中,种群大小设O算法对应的下降曲线具有更快的下降速度和更好的下降 置为20,达代次数设置为200,m取固定值0.6,c1和e2取值均释度, BVPSO算法基本上在迭代次数接近100代时,逼近了函 为0.5,波动系数8取值也为0.5。函数F5的维数为2,两个算数的理论最优值,而FO算法在100代之后基本陷入停滞状 法的迭代次数为200,其余参数设置不变。两种算法在所有态或者最优解的改进不明显,表明 BMPSO算法比PSO算法具 的测试例上都运行50次,所有实验均在一台 Pentium42.0有更好的有效性和快速性 GHz CPU/1GB内存的计算机上进行。 以上分析表明, BVPSO算法对于解决上述复杂函数优化 2442 计算机应用研究 问题是非常有效和可靠的,是标准PSO算法的有效改进,再次 on Evolutionary Computation [S1.: IEEE Press, 2002: 1588-1593 说明∫漂移算∫和波动算∫对PO算法性能的提升起到∫关[5]徐星,李元香,吴昱.基于扩机制的双种群籼子群优化算法[J」 键的作用。 计算机应用研究,2010,27(8):2882-2885,2898 [6]伊藤清.随机过程[M].刘璋溫,译.上海:上海科学技术出版社 4结束语 1961 7]佘莉.基于伊藤算法的仿真优化理论及应用研究[D].武汉:武 本文通过对布朗运动以及伊藤过程进行分析和抽象得到 汉大学,2009 漂栘和波动两个特征。结合粒子群优化算法的特点,赋予了漂[8]胡旺,李志蜀.一种更简化而高效的粒了群优化算法[冂.软件学 栘和波动这两个过程特殊的涵义,设计了漂移算子和波动算 报,2007,18(4):861-868 ∫。基于此,提出了一种基于布朗运动的且具有漂移算」和差9」 HENDTLASS T. A com bined swarm diff 分波动算子的改进粒子群优化算法(BMP=O)。实验结果表 optimization prablems[ C]//Proc of the 14 th International Conference 明, BMPSO算法具有良好的性能,能够有效地解决一些典型 nn Industrial and Engineering A plications of Artificial Intelligence 的、复杂的全局优化问题,而且 BMPSO算法具有稳定性良好和 and Expert Systems: Engineering of Intelligent Systems. Berlin 收敛速度较快的特点。 Springer-Verlag, 2001: 11-18 [ 10] ZHANG Wen jun, XIE Xiao-feng. DEPSO: Hybrid particle swarm with 参考文献: differential evolution operator[C//Proc of IEEE International Con [I KENNEDY J, EBERHART R C, SHI Yu-hui Swarm inte lligence ference on Systems, Man and Cybernetics. Washington DC: IEEE IM. San Francisco: Morgan Kaufmann, 2001 Press,2003:3816-3821 [2 EBERHART R C, SHI Yu-hui. Guest editorial special issue an parti 11 DAS S, KONAR A, CHAKRABORTY L K Improving particle swarm cle swarm optimization[ J]. IEEE Trans on Evolutionary Compu optimization with differentially perturbed velocity C]//Prac of Ge- tation,2004,8(3):201-203 netic and Evolutionary Computation Conference. Washington DC [3 XIE. Xiao-feng, ZHANG Wen-jun, YANG Zhi-lian. A dissipative parti ACM Press,2005:177-184 cle swarm optimization[ C //Proc of Congress on Evolutionary Com 12 HAO Zhi-feng, GUO Guang-han, HUANG Han. A particle swarm opti- putation. S. L.I: IEEE Press, 2002: 1456-1461 mization algorithm with differential evolution C1//Proc of the 6th In 4 LOVBJERG M, KRINK T Extending particle swarm optimisers with ernational Conference on Machine Learning and Cybernetics. S self-organized criticality[C]//Proc of IEEE International Conference 1.]: IEEE Pres,2007:1031-1035 (上接第2426页)长度,分别对系统初始稳定、节点数分别为20 [J]. Computer Networks,2006,50(13):2127-2159 和100的情况下,节点数变为0到200后系统再次变为稳定所2]王华奎,李艳萍张立毅,等,修动通信原理与技术[M].北京:清 需的时隙数进行仿真,仿真结果如图8所示。从仿真结果可以 半大学出版社,2009 看出,当变化节点数小丁初始稳定情况下节点数的一半时,系3] CLARE L I. Control procedures for slotted ALOHA systems that a 统调节时间随节点数的差值增大而增大;但是当变化后的节点 chieve stability. ACM SIGCOMM Computer Communication 数小于初始稳定情况下节点数的一半时,其调节时间基本限定 Review,1986,16(3):302-309 4]李健东,信息网络理论基础[M],西丙安:丙安电子科技大学出版 在一定范围內。其原因是由于空闲和功慨率增加,即f(β) 社,2001 较大,调节时间相应变短。 [5]曹小华,陶德馨,李文锋,时隙 ALOHA防冲突算法的马尔可夫链 ※600 50盛3 模型研究[J].武汉理工大学学报:交通科学与工程版,2007,31 0.6 [6 KOMPALLI S C, MAZUMDAR RR On a positive recurrence criterian 0.4 for multidimensional Markov chains with application to the stability of 100 4080120160200 slotted-ALOHA with a finite number of queues[ C]// Proc of the 21st 突发节点个数 ITC on Teletraffic. 2009.1-8 图8调节时隙数与突发 图7信道状态概率与B的关系图 节点个数关系图 [7]AkarN.MultipleaccesscommunicationsR/olj.http://www.ee 3结束语 18 HL Ying bo, YANG Wei-wei. Throughput analysis of slotted ALOHA operative transmission uing successive interference cancellation 在使用伪贝叶斯算法作为时隙AOHA稳定性调节算法 [JI. Science in China Series F-Information Sciences, 2009, 52 时,其能够保证系统的稳定性,但是当系统负载量波动较大时, (12):2354-2359 该算法调整时间较长;当变化率0.5<B<2时,其调整时间会91NQYc. On the stablity of slotted ALOHA system[ J., lEEE Trans 估计成近似线性关系,且其吞吐量与最大稳定吞吐量相差较 on Communications, 1980,28(3): 1936-1939 小。该算法可应用于系统负荷变化较小的系统屮,否则需要使 [10 MA Liang-ping, HAN Xiao-feng, SHEN C C Dynamic open spectrum 用其他于段使其差值快速收敛到0.5~2。 sharing MAC Protocol for wireless Ad hoc network C]//Proc of the st IEEE International Sy mposium on New Frontiers in Dynamic Spec 参考文献: trum Access networks. 2005. 203-213 [1] AKYILDκIF,IEWY, VURAN M C,na.NeX! generation/dy-[11]王勇,胡以华,时隙 ALOHA系统稳定性分所[J].计算机应用研 namic spectrum access/cognitive radio wireless networks: a survey 究,2008,25(4):1175-1177