提出一种新的约束优化粒子群算法。该算法采用非固定多段映射罚函数法处理约束条件。在进化过程中，利用混沌序列初始化种群，选取最优粒子进行局部一维搜索，增强了在最优点附近的局部搜索能力，以加快算法的收敛速度;引入维变异方法保持种群的多样性。数值实验结果表明了该算法的有效性。
第3期 吴华伟,等:一种改进的约束优化粒子群算法 861 大),使得后期收敛速度明显变慢,同时算法收敛到一定精庋法除冋题g8取得相似的结果外.其余5个问题得到的解要明 时,无法继续优化,进而陷入局部最优解。因此,为f指高显劣于 ICOPSO算法。 CHMPSO算法在间题01和8上找到 解的质量,当粒子群收敛到一定程度时就要进行变异,即以一了最优解,其他4个问題得到的结果要明显劣于IOPO算 定的几率让所有粒子在这一维上的值均匀分布,在以后的迭代法。除了高维多峰测试问题g02和含等式约束的g11外,PE 过程中可能找到更好的解,增加跳岀局部最优或得到更高精度SO算法对其他4个测试问题也一致地找到全局最优解,问题 解的机会 gl1得到的结果也接近理论最优解。与PESO算法相比,ICOP 很多参数都可以表示粒子群的收敛程度,它们的大小和变S0算法在测试问题g02和g11上得到的结果要优,而在测试 化情况都可以作为确定变异的依据。在此,选用式(14)来衡问题s01、04、s06和8上取得了相似的结果。 VRPSO算法 量种群的多样性: 除了问题g和g11没有找到最优解外,在其他4个问题上全 部找到了最优解。基于以上比较和分析,COO算法要优于 div(p) IP|x(|P-1)×|L (P1-pk)2(14) 或相似于其他算法。 其中:P为种群;P为种群个体数目;n为问题的维数;L|为 表1五种算法对6个问题的寻优结果比较 搜索空间S的最长半径;P和p分别为种群中第i个和第j个 问题最优值 状态 个体的第k个基因。在对神群的多样性进行衡量后,在这里预 CPsoL15] CUMPSO 16 PESO[ I7] RVPSOL17] ICOPSD 先定义一个阈值dv(不同的问题其值不同),当种群多样性值1100平均果1501150 5.C0 14.4l87 15.000 div(P)<div时,进行维变异,即随机对种群中的某一维重新初 始化 最好结果-0.8013880.8034920.792608-C.6640280.803619 020.803619平均结果0.765300.790106-0.721749-C.4132570.792163 最差结果0.091700.7503930.6141350.2599800.75012 2.4算法步骤 最好结果-30665.65930655.500-30665.538-306553830665.538 665.538平均结果-30665.656-30655.500-30665.538-30665538-30665.538 综上所述,本文提出的结合非同定多段映射罚两数的约束 最盖结果 b5.626-30655.500-30665.538-30665.:38-3665.538 优化粒子群算法的步骤如下 最好结果 6961.8256)61.810661.814 6961.8146)61.814 06-6961.814平均结果6875.940-6961.810-6961.814-6951.814-6961.814 a)设置算法参数。初始化种群规模,一般为参数维数的 最差结果-6482.755-6952.810-0961.814-0961.814-6961.814 10倍。在每个变量的定义域内,利用混沌序列产生初始种群。 最好结果 0958250.0058750095825-0.095875-0.09582 80.095825平均结果0.C958250.0958250.0958250.0958250.095325 b)按式(5)~(7)分别计算各粒子每个约束条件的惩罚因 最差结果0.C958250.0958250.0958250.0958250.0958 最好结果3.7490 0.7499 749 0.7499 0.7499平均结果3.7505 0.749 c)按式(4)分别计算每个粒子的所有约束条件的惩罚因 量结果.4466 0.749 0.:49y9 子H(x)。 d)根据式(3)计算出每个粒子的适应度值,求出最优适4结束语 度值及最优个体。 e)判断惩罚因子m(x)是否达到精度要求或是否达到最 本文采用非固定多段映射罚函数法对约束条件进行处理 大迭代次数,若是则退出;否则执行步骤f)。 提出一种改进的约束优化粒子群优化算法。根据约束条件的 「)粒了按照式(11)~(13)进行达代,产生新的粒子;对最 违背程度,自适应地选择不同的惩罚力度,将约束优化问题转 优粒子进行局部一维搜索和进行维变异后产生新的粒子,合并 换为一系列的无约束优化问题,然后利用改进的粒子群算法进 所有粒子后返同步骤b)。 行优化。嵌入局部一维搜索技术增加算法的局部搜索能力。 几个标准测试问题的实验结果表明,该算法具有较强的通用性 3数值实验及分析 和稳定性。 参考文献 为了测试本文算法的性能,从文献[1]的13个标准测试 [1 RUNARSSON T P, YAO Xin. Stochastic ranking for constrained evo 问题中选取∫6个优化问题,即g01、g02、g04、g06、g08和gl1 lutionary optimization[J]. IEEE Trans on Evolutionary Computa- 进行测试,各测试问题的具体表达式见文献1]。将本文算法 tion,2000,4(3):284-294 记为 ICOPSO,并与 CPSO、CHMO、PEs"和 RVPSO12|王翔,董晓马,阎瑞霞,等,改进 DE/EDA算法在求解难约束优 算法得到的结果进行比较。在比较实验中, ICOPSO算法的 化问题中的应用研究[J].计算机应用研究,2010,27(11) 参数设置为:种群规模N取为每个问题参数变量个数的10 4114-4117 儐,vna=0.9,m=0.2,容忍值σ=0.0001,种群多样性值3] MICHALEWICZ Z, SCHOENAUER M. Evolutionary algorithm for div根据不同问题具体设定。对所有的测试问题,适应值评价 constraint parameter optimization problems[J]. Evolutionary Com- 次数均设置为350000次。其他算法的参数设置分别见其各 putation,1996,4(1):1-32 自的文献。每个测试问题在相同条件下独立运行30次实验, [4 KENNEDY J, EBERHART R C. Particle swarm optimization[C]// 记录其最好结果、平均结果和最差结果。 Proc of International Conference on Neural Networks. Piscataway 表1给出了在上述参数设置下,五种算法对6个标准测试 IEEE PIess,1995:1942-1948 [5]吴亮红,王耀南,周少武,等,采用非固定多段映射罚函数的非 问题的寻优结果比较。 线性约束优化差分进化算法[J].系统工程理论与实践,2007, 从表1可知,本文所提出的 ICOPSO算法对6个问题30次 27(3):128-133 实验中一致地找到全局最优解,且具有较强的稳定性CPSO[6] PARSOPOULOS K E, VRAHATIS M N. Particle swarm optimization 算法除了问题g01和g08找到最优解,在其他4个问题上得到 method for constrained optimization prcblems J. Computer and In 的解离理论最优解相差较远。与 ICOPSO算法相比,CFSO算 formation science,2011,181(1):1153-1153.(下转第864页) 864 计算机应用研究 第29卷 x21+x22+x23+x24+x25=1 现时间不长,理论基础尚禾很好地奠定,渐近收敛性、鲁棒性等 x31+x2+x3+34 性质的严格数学证明有待于以后更深入地工作研究。 x41+x42+x43+x4+x45+x46+x47+x48=1 x51+x52+x53+x5a4+x55+x5+x57=1 表1算法比较 L61+x62+x63+x64+x65 算法 最优解 最优值频率 x71+x72+x73+x4+75+xn6+x7+x78=1 ro +3o +ro +%o + ros + xo=1 11,4,5,5,6,3,5,3 遗传算法[8,4,5,5,2,5,5,3 0.675 由于多选择背包问题通常是以费用最小化为目标函数,即 [8,4,5,5,6,5,4,3 求f(x)m的最小值。上式中,不等式约束表示背包的重量约束 [1,4,5,5,6,3,5,3 条件,等式约東表示每类物品中只能选一件。在计算求解中,种 MEDA [8,4,5,5,2,5,5,3 8,4,5,5,6,5,4,3 群数量S=40,最大迭代次数G=100,imi=5,跟随蜂个数\o= 8,4,5,5,6,5,4 5,初始化种群 colony(:,j)= unidad(mm(j),S,1),1≤j≤8的 ABC算法[8,4,5,5,2,5,5, 整数。可求得该问题的最优值为34,相应的最优解为1,4,5,5, [1,4,5,5,6,3,5,3 6,3,5,3],[8,4,5,5,2,5,5,3],[8,4,5,5,6,5,4,3]。 根据优化变量代表的含义,上述解可以写为 4结束语 (x1,324,x33,x45,x56,x63,x735,x83)约条件:6+5+4+4+8+ ABC算法作为一种新的智能优化算泆,其有收敛快、鲁棒 2+9+2=40≤40 性强等特点。多选择背包问题属丁组合优化问题,且是NP难 (x18,x24,x3,x45,x32,x65,x73,x83)约条件:3+5+4+4+7+ 题。本文就多选择背包问题的特点设计了基于 MATLAB环境 6+9+2=40≤40 (x1s,x23,x35,x*5,xo,x6,x,x)约条件:3+5+4+4+8+的人工蜂群算法,编写了算法程序。测试结果表明,ABC算法 6+8+2=40≤40 对MCKP求解是可行的,为有效求解多选择背包问题提供了 目标函数值随迭代次数的变化曲线如图3所示。 种新的可行方法,同时乜拓展了人工蜂群算法的应用领域。 参考文献: [1]玄光男,程润伟,于歆杰,等,道传算法与工栏优化[M].北京:清 华大学出版社,2004:56-59 I 2 GEN M, CHENG R, SASAKI M. Multiple-choice knapsack problem Engineerin Automation Research,1998.1127-1132 [3]賀毅朝,寇应展,陈致明。求解多选择背包问題的改进差分演化 102034050607o8001o 算法[J].小型微型汁算机系统,2007,28(9):1682-1685 迭代次数 [4 KARABOGA D. An idea based on honey bee swarm for numerical 图3目标函数值随迭代次数的变化曲线 timization, Technical Report TRO6L R. Turkey Computer Enginee 以下是遗传算法、改进的差分演化算法(MEA)3与ABC ring Department, Erciyes University, 2005 算法就该问题的对比结果,如表1所示 [5 KARABOGA D, BASTURK B. On the performance of artificial bee 由表1可以看出,三种方法都可以求得该实例的最优解 colony(ABC)algorithm[J]. Applied Soft Computing, 2008, 8 1) 但遗传算法的频率(求得最优解次数/运行总次数)比较低。 在文献[3中,改进的差分演化算法平均需9.3次选代即可求 6|樊小毛,马良.0-1背包问题的蜂群优化算法|J|.数学的实践与 得最优值34,即f(x)m=34。由图3可知,人工蜂群算法需15 认识,2010,40(6):155-160 [7 SINGH A. An artificial bee colony algorithm for the leaf-constrained 次迭代即可求得最优值34,取得了比较满意的效果。经大量 minimum spanning tree problem[ J. Applied Soft Computing 计算实验,算法体现了令人满意的性能,但由于这类算法思想出 2009.9(2):625-631 (上接第861页) 群优化算法[J].计算机应用研究,2009,26(9):3279-3281 [7]刘悛梅,高舌林,非线性浥合盤欻规划问題的改进差分进化算法[13]龙文,梁昔明,萤淑华,等·动态调簦槚性杈重的粒子群优化算 J].L程数学学报,2010,27(6):967-974 法[冂].计算机应用,2009,29(8):2240-2242 [8]任子武,伞冶,实数遗传算法的改进及性能斫究[J.电子学报,[14] LACEVIC B, KONJICIJA S, AVDAGIC Z. Population diversity 2007,35(2):269-274 measure based on singular values of the distance matrix[ C]//Prcc of [9]梁昔明,龙文,龙祖强,等。自适应梯度指导交又的进化算法 Congress on Evolutionary Computation. Singapore: IEEE Press [J].小型微型计算机系统,2011,39(7):1331-133 2007:1863-1869 [10] SHI Y, EBERHART R C. Empirical study of particle swarm optimi [15] CAGNINA L C, ESQUIVEL S C, COELLO. A. A particle swarm zation[ C]//Proc of Congress on Evolutionary Computation. Piscat- optimization for constrained numeric al optimization]//Lecture Notes in Computer Science, vol 4193. 2006: 910-919 away: IEEE Press, 1999: 1945-1950 [16] PULIDO G T, COELLO C. A. A constraint-handling mechanism for I 11 RATNAWEERA A, HALGAMUGE SK. WATSON H C. Self-orga- Article sw arm opitimization [C] //Proc of Congress on Evolutionary nizing hierarchical particle swarm optimizer with time-varying accele- Computation [S 1.]: IEEE Press, 2004: 1396-1403 ration coefficients [JJ. IEEE Trans on Evolutionary Computation, [17] LU Hai-yan, CHEN Wei-qi. Dynamic-objective particle swarm opti 2004,8(3):240-255 mization for constrained optimization problems| J I. Journal of Com [12]龙文,梁昔明,董淑华,等.嵌入局部一维搜索技术的混合粒子 binational Optimization, 2006, 12(4): 409-419