基于克隆多尺度协同开采的离散微粒群算法(1).pdf

第 26 卷 第 5 期 Vol. 26 No. 5 控制与决策 ControlandDecision 2011 年 5 月 May 2011 基于克隆多尺度协同开采的离散微粒群算法 文章编号 1001-0920201105-0700-07 陶新民1, 徐晶2, 王妍1, 刘玉1 1. 哈尔滨工程大学 信息与通信工程学院，哈尔滨 150001；2. 黑龙江省科技学院 数力系，哈尔滨 150027 摘要 提出一种克隆多尺度协同开采的离散微粒群算法. 多尺度变异概率根据粒子适应值大小进行动态调节, 在 算法初期通过大尺度概率变异增加算法多样性, 后期通过逐渐减小的小尺度变异提高算法在最优解附近的局部精确 解搜索性能, 对当前最优解进行克隆选择, 可进一步增强算法逃出局部极小解的能力以及所求解的精度. 将算法应用 于5个benchmark函数优化问题并与其他算法比较, 结果表明该算法不仅能增强全局解搜索性能, 同时最优解的精度 也有所提高. 关键词 离散微粒群；克隆；多尺度；协同开采 中图分类号 TP18文献标识码 A Discrete particle swarm optimization based on clone multi-scale cooperative exploitation TAO Xin-min1, XU Jing2, WANG Yang1, LIU Yu1 1. College of Ination and Communication Engineering，Harbin Engineering University，Harbin 150001，China; 2. Department of Mathematics and Mechanics，Heilongjiang Institute of Science and Technology，Harbin 150027，China. CorrespondentTAO Xin-min，E-mailtaoxinmin AbstractA discrete particle swarm optimizationDPSO algorithm based on multi-scale cooperative clone mutation MSPSO is proposed. The clone mutation operator with multi-scale possibilities is introduced on the current optimical solution, which can not only improve the ability of local search, but also keep the abilities of global space search and escaping fromlocaloptima. Themutationoperatorwithlarge-scalepossibilitiescanbeutilizedtoquicklylocalizetheglobaloptimized space at the early evolution. The scale-changing strategy produces a smaller multi-scale mutation operators according to the variation of the fi tness value and makes mutation operators with smaller-scale possibilities implement local accurate minima solution search at the late evolution. The experiment studies on 5 standard benchmark functions, and the experimental results show the proposed can not only effectively solve problem of lack of local search ability, but also signifi cantly speed up the convergence and improve the stability. Key words discrete particle swarm optimization；clone；multi-scale；cooperative exploitation 1引引引言言言 微粒群优化PSO是Kennedy和Eberhart于1995 年提出的一种新兴的基于群体智能理论的演化计算 技术. 它源于对鸟群觅食运动行为的模拟, 相对于遗 传算法而言, PSO具有运算简单、 易于实现、 需要调 节的参数少以及较强的全局收敛能力和鲁棒性好等 优势. 目前已广泛应用于科学和工程领域, 如函数优 化、 神经网络训练和模糊分类、 系统控制等[1-2]. PSO 最初是为解决非线性连续优化问题而设计的, 具有连 续本质. 为了将其应用于解决离散问题, Kennedy于 1997年提出了解决0-1规划问题的离散微粒群优化算 法DPSO, 这里称之为传统离散微粒群算法[3-5]. 由于传统离散微粒群算法同样具有收敛精度 低、 易陷入局部最优解等问题[6-7], 国内外学者提出了 多种算法来改进传统离散微粒群算法的优化性能, 一 方面是将对连续微粒群算法的改进直接应用到离散 微粒群算法中. 例如 1 设置自适应的控制参数来改 进离散PSO的性能. 如文献[8]采用惯性权重线性下 收稿日期 2010-02-01；修回日期 2010-05-21. 基金项目 国家自然科学基金项目61074076；中国博士后科学基金项目20090450119；中国博士点新教师基金项 目20092304120017；黑龙江省博士后基金项目LBH-Z08227. 作者简介 陶新民1973−, 男, 副教授, 从事智能信号处理、 智能计算等研究；徐晶1974−, 女, 副教授, 从事模式识别 的研究. 第 5 期陶新民 等基于克隆多尺度协同开采的离散微粒群算法701 降法, 使算法在搜索初期有效地探索较大区域, 随着 搜索过程的深入, 逐渐开始精细搜索. [9]则设计了自 适应的最大速度阈值参数, 使粒子在搜索过程初期倾 向于全局搜索, 在算法后期倾向于当前最优解附近 的局部搜索, 有效地实现了粒子全局和局部搜索性 能的平衡VCDPSO. 2 增强粒子局部极值的逃逸能 力. 如[10]通过对惯性因子采用自适应扰动机制来增 强微粒群跳出局部最优的能力DDPSO. 3 增加微粒 群多样性, 摆脱群体陷入局部极值的可能, 提高算法 性能[11-12]. 上述改进算法没有考虑到DPSO算法的进 化过程与连续PSO算法截然不同这一重要区别, 直接 将对连续算法的改进应用到离散微粒群算法中, 因此 上述改进算法并不适用于离散微粒群算法, 没有真 正达到弥补离散微粒群算法不足的目的[13]. 另一方 面是直接对离散微粒群算法进行分析, 例如[14]分析 了DPSO中微粒速度的变化, 提出一种双速度状态跟 踪的DPSO算法简称NDPSO, 消除了原有算法对参 数敏感的不足, 但由于算法增加了微粒状态改变的随 机性, 其全局优化性能同样受到影响. [15]对DSPO算 法微粒状态转移情况进行了分析, 提出一种改进的离 散化方法MDPSO, 降低了微粒在最优解附近发散 的可能, 然而该算法在降低微粒发散度的同时, 也使 得其易陷入局部最优解. 因此如何在提高算法局部搜 索能力的同时不影响算法逃出局部最优解的能力值 得深入研究. 本文在分析传统DPSO算法微粒状态转移情况 的基础上, 提出一种克隆多尺度协同开采的离散微粒 群算法MSPSO. 该算法在克隆当前微粒的基 础上进行多尺度概率变异, 并且变异概率算子随着适 应值的提升而逐渐减少, 这样既可提高对解空间的开 采能力, 又可保持算法的勘探能力, 使其能有效逃出 局部最优解, 保证了算法的收敛性能. 将该算法应用 到各种不同优化函数并与其他改进的DPSO算法进 行比较, 试验结果表明本文算法具有优良的优化性能. 2离离离散散散微微微粒粒粒群群群算算算法法法描描描述述述 连续微粒群优化算法的基本思想是模拟鸟群捕 食的行为, 将优化问题的每个潜在解看作搜索空间的 一个“微粒”, 所有的微粒都由一个适应函数来决定其 适应值. 此外, 每个微粒还有一个速度决定它的运动 方向和移动距离. PSO算法初始化一群随机微粒随 机解, 然后通过迭代找到最优解. 在每次迭代中, 微 粒通过跟踪2个“极值”来更新自己 1 微粒本身所找 到的最优解, 这个解称为个体极值; 2 整个种群或者 该微粒的某个邻域范围目前找到的最优解. 连续算 法的机制适合于求解无约束的连续型最优化问题, 并 且取得了良好效果. 为拓展微粒群优化算法的应用范 围, Kennedy和Eberhart对连续微粒群算法进行修正, 提出一个二进制离散微粒群算法[3], 用于处理离散型 优化问题. 设微粒群含有𝑀个微粒, 每个微粒相当于𝑂维 离散空间的一个活动点. 微粒𝑖在时刻𝑡的速度、 位 置、 个体最好位置和全局最好位置分别用𝒗𝑗𝑡,𝒙𝑗𝑡, 𝒙𝑝 𝑗 𝑡,𝒙𝑔 𝑗 𝑡表示, 则微粒𝑖的速度和位置的各维分 量迭代公式如下[3] 𝑤𝑗𝑘𝑡 1 𝑥𝑤𝑗𝑘𝑡 𝑑1𝑟1𝑘𝑡𝑦𝑝 𝑗𝑘 𝑡 − 𝑦𝑗𝑘𝑡 𝑑2𝑟2𝑘𝑡𝑦𝑔 𝑗𝑘 𝑡 − 𝑦𝑡 𝑗𝑘 ;1 𝑦𝑗𝑘𝑡 1 ⎧ ⎨ ⎩ 0, 𝜌⩾Sig𝑤𝑗𝑘𝑡 1; 1, 𝜌 1, 则微粒会随着迭代而保持原有 的状态, 变异的可能性降低, 趋于陷入局部极值解; 如 果𝑥⩽1, 则随着迭代次数的增加,𝑥会使处于当前 最优的微粒的速度趋于零, 使得当前微粒产生变异的 概率趋于0.5, 且很快发散出去, 无法在最优解附近进 行深度的局部搜索. 因此有效控制算法中处于当前 最优解的微粒搜索的发散性, 提高算法局部精确解 的搜索能力, 同时保持局部最优解的逃逸能力是传 统DPSO算法需要解决的首要问题. 3克克克隆隆隆多多多尺尺尺度度度协协协同同同开开开采采采的的的离离离散散散微微微粒粒粒群群群算算算法法法 3.1多多多尺尺尺度度度概概概率率率变变变异异异算算算子子子 增加变异操作能帮助算法逃出局部最优解, 但大 的变异概率无法保证逃逸后的新位置位于全局最优 702控制与决策第 26 卷 解的附近, 即新位置的适应值不一定优于现有的最优 解. 这样通过单纯的大尺度概率变异无法得到更优的 位置, 进而在重新迭代的过程中, 因迭代次数的限制 可能使其无法收敛到全局最优解. 由PSO算法的产生 机理可知, 在算法进化的后期, 问题的最优解往往存 在于当前最优解周围, 因此有必要在最优解周围进行 精确的局部最优解搜索. 小的变异概率有利于进行局 部搜索, 即增强算法的开采能力, 但其又易陷入局部 极值解. 因此如何设计变异概率是协调离散微粒群算 法勘探和开采能力的关键. 本文采用多尺度变异概率 算子, 进化初期采用大尺度概率变异使得算法在搜索 空间中进行分散式搜索, 同时变异算子随着适应值的 提升而逐渐减小, 使得算法在进化后期的局部搜索能 力增强, 提高了最优解的精度, 保证了算法的收敛性 能. 算法具体描述如下 设尺度个数为𝑁,𝐿为迭代次数. 首先根据适应 值的大小对种群中的微粒由小到大进行排序、 组合, 生成𝑁个子群, 每一个子群的微粒个数为𝑃 𝑂/𝑁, 𝐿为当前迭代次数. 计算每一个子群的适应值 Fit𝑋𝐾 𝑚 𝑃 ∑ 𝑗1 𝑓𝑦𝑚 𝑗 /𝑃, 𝑖 1,2,⋅⋅⋅ ,𝑁,3 其中𝑓是微粒的适应值函数. 初始化多尺度概率变异 算子的初始值 𝒑0 𝑝0 1 ,𝑝0 2 ,⋅⋅⋅ ,𝑝0 𝑀 .4 初始值可随机设定为0∼1间的随机数, 随着迭代次数 的增加, 不同尺度概率变异算子之间相互竞争, 根据 适应能力的不同而设置不同的变异能力. 第𝑚个变 异概率算子的值为 𝑝𝐾 𝑚 𝑝𝐾−1 𝑚 exp 𝑁 ⋅ Fit𝑋 𝐾 𝑚 − 𝑀 ∑ 𝑚1 Fit𝑋𝐾 𝑚 Fit𝑋max− Fit𝑋min , 5 Fit𝑋max max 1⩽𝑗⩽𝑀Fit𝑋 𝐾 𝑗 , Fit𝑋minmin 1⩽𝑗⩽𝑀Fit𝑋 𝐾 𝑗 .6 由于多尺度概率变异算子的进化是一个递归过 程, 某一尺度变异概率算子的值可能很大, 因此对变 异算子的标准差做如下规范 如果𝑝𝑙 𝑗 𝑇,则 𝑝𝑙 𝑗 𝑇 − 𝑝𝑙 𝑗 . 7 𝑇为变异概率算子的阈值, 这里设置为0.7, 重复式7 直到满足𝑝𝑙 𝑗 𝑇. 当𝑁 5时不同尺度概率变异算 子随迭代次数的变化如图1所示, 通过本文的多尺度 概率变异算子能实现变异概率空间的覆盖. 其中大尺 度有利于实现解空间的粗搜索, 可以逃逸出局部极小 值, 快速定位到最优解区域, 具有一定的空间勘探能 力; 小尺度能在进化后期实现最优解附近的局部精确 解深度搜索, 具有较强的开采能力. 0.6 0.8 0.4 0.2 00 5101520 “ 当𝑥 −1时, 速度会随着迭代而减小, 最终使得Sig𝑤𝑗𝑘 0, 微粒位变成0的概率增加. 因此文献[8-10]对惯 性参数采用自适应或扰动机制来改善离散微粒群算 法并不可取, 本文算法中取𝑥 1实现折衷. 3.4MSPSO算算算法法法流流流程程程 1 算法的参数初始化设定; 2 按照离散微粒群进化公式1进化; 3 根据式2进行微粒状态的计算; 4 计算当前最优解及每个微粒的个体极值解; 5 根据式3∼7计算多尺度概率变异算子值; 6 克隆变异选择算法; 7 循环直到终止条件. 4克克克隆隆隆多多多尺尺尺度度度协协协同同同开开开采采采的的的离离离散散散微微微粒粒粒群群群算算算法法法 为了更有效地说明算法优化的机理, 设优化函数 𝑓𝑦只有一个自变量函数, 如图2所示. 本文算法中 种群的某一个微粒经过多次迭代后到达𝑏点, 经过 小尺度概率克隆变异深度搜索后, 向下“下山”找到 个体𝑏′, 经过DPSO算法的进化, 进化到𝑏′′; 然后经 第 5 期陶新民 等基于克隆多尺度协同开采的离散微粒群算法703 过大尺度概率克隆变异操作后找到适应值更高的 微粒𝑐, 则微粒𝑐被选入下一世代. 经过DPSO若干代 进化以及小尺度概率克隆变异操作后, 找到微粒𝑐′. 微粒𝑐′经过大尺度概率克隆变异操作找到了微粒𝑑, 则𝑑被选入下一个世代, 经过DPSO进化和小尺度概 率克隆变异操作最终找到最优解𝑑′. x f x a a′ a″ b b′ c c′ 图 2多尺度概率克隆变异的优化机理 由上可知, 多尺度概率克隆变异操作将整个解 空间看作一个山谷, 经过大尺度概率克隆变异操作进 行“下山”以寻求适应值更高的区域𝑏′′→ 𝑐,𝑐′→ 𝑑. 大尺度概率克隆变异操作用于搜索全局解空间, 是粗 搜索. 若大尺度概率克隆变异操作找到了适应值更高 的区域, 则DPSO进化操作和小尺度概率克隆变异操 作能通过小区域搜索在该区域进行局部深度搜索以 寻求更高精度的解𝑏 → 𝑏′,𝑏′→ 𝑏′′,𝑐 → 𝑐′,𝑑 → 𝑑′, DPSO进化操作和小尺度概率克隆变异操作用于搜索 局部解空间. 因此本文算法是一个勘探和开采能力相 互交替进行的搜索算法, 具有全局和局部两层邻域搜 索机制, 从而保证算法全局和精确的局部寻优性能. 5对对对比比比实实实验验验结结结果果果及及及分分分析析析 5.1测测测试试试数数数据据据及及及实实实验验验设设设计计计 为分析本文提出的新算法的全局搜索性能、 收 敛速度和算法的稳定性, 本文选择DPSO和其改进 的离散微粒群算法DDPSO, NDPSO[14], MDPSO[15]及 VCDPSO[9]对5个benchmark优化问题进行对比实 验. 无特殊说明, 所有算法中𝑥选择在[0.9,0.4]之间 随代数线性递减.𝑑1和𝑑2均为1, DDPSO的扰动参 数𝑃𝑣 0.12, VCDPSO算法的最大速度限制值的内 部协调参数为1.2, 本文MSPSO算法𝑁 5, 初 始多尺度概率变异算子𝑝0随机设定为0∼1的范围, 每一个尺度的克隆规模为20, 所有实验的种群规模 为20, 函数维度设置为20, 每一位变量的编码长度 为20, 每次运行2000代. 为了排除算法内部随机操作 对性能的影响, 对每一个函数独立运行30次试验并 对其统计结果进行分析. 本文选择DPSO算法经常使用的5个benchmark 函数问题进行数值实验, 并根据函数性质分为具有单 一极小点单模态和多个极小点多模态两大类, 下 列公式给出了函数的定义及取值范围和全局最优解. 单模态函数定义如下 DeJong函数 𝑓1 𝑛 ∑ 𝑗1 𝑦2 𝑗, 8 取值范围为[−50, 50], 维度为20, 最小值和位置为 00,⋅⋅⋅ ,0. Rosenbrock函数 𝑓2 𝑛 ∑ 𝑗1 100𝑦𝑗1− 𝑦2 𝑗 𝑦𝑗− 1 2, 9 取值范围为[−50, 50], 维度为20, 最小值和位置为 01,⋅⋅⋅ ,1. 多模态函数定义如下 Griewank函数 𝑓3 1 4000 𝑛 ∑ 𝑗1 𝑦𝑗2− 𝑛 ∏ 𝑗1 cos𝑦𝑗/√𝑖 1,10 取值范围为[−50, 50], 维度为20, 最小值和位置为 00,⋅⋅⋅ ,0, Rastrigrin函数 𝑓4 𝑛 ∑ 𝑗1 𝑦2 𝑗 − 10cos2π𝑦𝑗 10,11 取值范围为[−50, 50], 维度为20, 最小值和位置为 00,⋅⋅⋅ ,0. Ackley函数 𝑓5 − 20exp − 0.2 √ 1 𝑛 𝑛 ∑ 𝑗1 𝑦2 𝑗 − exp [1 𝑛 𝑛 ∑ 𝑗1 cos2π𝑦𝑗 ] 20 𝑒,12 取值范围为[−50, 50], 维度为20, 最小值和位置为 00,⋅⋅⋅ ,0. 函数𝑓1和𝑓2是单模态函数, 其中Rosenbrock函 数是一个经典的复杂优化问题, 它的全局最优点位 于一个平滑、 狭长的抛物线形山谷内. 由于函数为优 化算法, 只提供了少量信息, 使得算法很难辨别搜索 方向, 以至于找到全局最小点的机会微乎其微. 因此, Rosenbrock函数通常用来评价优化算法的执行效率. 多模态函数选择了3个经典的非线性多模态函数, 它 们具有广泛的搜索空间、 大量的局部极小点和高大的 障碍物, 通常被认为是很难处理的复杂多模态问题[2]. 5.2单单单模模模态态态函函函数数数优优优化化化性性性能能能对对对比比比实实实验验验 为了验证本文提出的算法针对单模态函数优化 问题的有效性, 首先对DeJong函数进行优化性能对 比实验, 实验结果如图3所示. 从图3的结果可以看 出, 本文算法随着迭代次数的增加迅速向着最优解区 域靠近, 体现了大尺度概率变异算子强劲的全局搜索 能力, 同时利用小尺度概率变异算子实现了局部精确 704控制与决策第 26 卷 051015 20 -20 -10 0 10 MSPSO DDPSO MDPSO NDPSO VCDPSO “/10 2 图 3不同DPSO算法DeJong函数优化性能对比 解的搜索, 大大提高了算法在当前最优解附近的开采 能力. 对于复杂单模态Rosenbrock函数优化问题, 本文 算法同样在算法的初期具有很强的全局解定位能力. 由于Rosenbrock 函数的山谷仅给算法提供了很少量 的信息, 使传统DPSO进化算法很难在短时间内辨别 搜索方向, 极易陷入局部最优解. 而本文算法采用了 多尺度概率克隆变异, 能够有效地逃逸出这些局部极 值点, 实现最优解区域的准确定位, 使得算法能在短 时间内找到正确的搜索方向, 并具有较快的下降速度. 同时在算法后期, 通过小尺度概率克隆变异使算法在 最优解附近进行更加详尽的局部搜索, 提高了算法局 部搜索性能及所求解的精度. 051015 20 5 10 20 25 “/10 2 MSPSO DDPSO MDPSO NDPSO VCDPSO 15 图 4不同DPSO算法Rosenbrock函数优化性能对比 表1显示了单模态benchmark问题的对比实验 结果, 从各个算法的最优值和最差值的实验结果可 以看出, 本文提出的算法在所有函数上均取得了较 好的实验结果, 具有较好的局部精确解搜索能力. 这 是由于本文的MSPSO算法通过多尺度概率克 隆变异操作能实现勘探能力和开采能力的协调, 增 加了算法在最优解附近对局部精确解的搜索能力 的同时保持了全局解搜索性能. 实验中还可发现, 由 于DPSO算法在种群初始化和通过速度确定微粒当 前的状态过程中均具有随机性, 使得算法的结果具 有一定的随机性. 表1的实验结果显示, 对于复杂的 Rosenbrock函数问题, 很难确定最优解搜索方向, 因 此各个算法单次结果存在较大差异. 由于函数的特 殊性质以及随机变异的引入, 降低了DDPSO算法的 搜索性能, 反而陷入了局部极小点. VCDPSO由于 采用了固定的权重系数以及变化的速度极值, 经过 一定的迭代也逃出了局部极小解. 而本文提出的 MSPSO算法能够在算法的初始阶段通过多尺度 概率克隆变异逃出局部最优解, 从而定位到全局最优 解区域, 找到进化方向, 并通过小尺度概率克隆变异 操作进行局部精确解搜索. 5.3多多多模模模态态态函函函数数数优优优化化化性性性能能能对对对比比比实实实验验验 对于多模态Griewank函数, 本文提出的算法能 够在开始阶段寻找到全局最优解区域, 其全局搜索 能力明显优于其他算法, 能够有效逃出局部极小点 找到全局最小点. 由表2可知, MSPSO算法的中 值、 平均值和标准方差等各项数据均显著优于其他算 法, 显示了新算法的稳定性和健壮性. 多模态Rastrigrin函数是一个典型的用来测试算 法全局搜索性能的函数, 从图5和表2可以看出, 本 文MSPSO算法具有良好的全局搜索性能和较 快的搜索速度. 虽然表2中本文算法没有在有限次的 运行都找到近似全局最优解0, 但是, 只要给予足够长 的迭代次数, MSPSO算法总能通过多尺度概率 克隆变异操作逃出局部极小点, 找到精确的全局最优 解. 图6显示了20维Ackley函数的运行结果, 本文的 MSPSO算法同样能在算法的初期寻找到全局最 表 1MSPSO和其他DPSO算法在单模态benchmark问题上的数值对比 FunctionAlgorithmMinMedianMeanDeviationMax Delong DPSO3.1181e0034.5297e0034.5036e003543.71105.3847e003 DDPSO3.2210e0034.4788e0034.5078e003586.21276.0274e003 MDPSO281.1879583.3715555.7693143.6680825.0658 NDPSO128.5048265.4348296.1904133.1682623.3578 VCDPSO0.94623.45073.49491.55627.5628 MSPSO4.5475e-0084.5475e-0084.5475e-00804.5475e-008 Rosenbrock DPSO8.6292e0071.9751e0081.9777e0085.6273e0073.1696e008 DDPSO6.8070e0072.1141e0082.0147e0084.9957e0072.7629e008 MDPSO1.7053e0065.6571e0066.5027e0064.9237e0062.3307e007 NDPSO5.5214e0051.9296e0063.0872e0063.3494e0061.3759e007 VCDPSO342.1967913.01801.6377e0031.5434e0036.1432e003 MSPSO17.481877.8967360.1322773.49554.1120e003 第 5 期陶新民 等基于克隆多尺度协同开采的离散微粒群算法705 表 2MSPSO和其他DPSO算法在多模态benchmark问题上的数值对比 FunctionAlgorithmMinMedianMeanDeviationMax Griewank DPSO1.72722.10282.08460.16322.2753 DDPSO1.76752.17612.14950.11992.3285 MDPSO1.06201.14481.14740.05201.3211 NDPSO0.99231.07231.07030.03121.1312 VCDPSO0.08420.22990.23390.09710.4538 MSPSO4.1015e-0090.01130.01900.02600.1235 Rastrigrin DPSO3.2010e0034.6108e0034.5713e003474.25585.2275e003 DDPSO3.6635e0034.8941e0034.8505e003430.52545.5154e003 MDPSO506.2958698.5828743.3146173.98311.2188e003 NDPSO279.2323438.1666470.6544142.2222829.9385 VCDPSO50.994772.357574.469313.4358101.9827 MSPSO8.382524.643525.85729.856348.9653 Ackley DPSO8.6292e0071.9751e0081.9777e0085.6273e0073.1696e008 DDPSO20.080020.563520.51570.164520.7130 MDPSO13.327017.425017.40261.705520.6242 NDPSO10.592914.127214.66502.896320.0099 VCDPSO1.64252.85032.93470.62594.5745 MSPSO1.9086e-0041.9086e-0041.9086e-00401.9086e-004 051015 20 8 10 “/10 2 MSPSO DDPSO MDPSO NDPSO VCDPSO 4 6 图 5不同DPSO算法Rastrigrin函数优化性能对比 051015 20 0 4 “/10 2 -8 -4 MSPSO DDPSO MDPSO NDPSO VCDPSO 图 6不同DPSO算法Ackley函数优化性能对比 优解区域, 然后利用DPSO进化和小尺度概率克隆变 异操作实现最优解附近的局部精确解搜索. 从表2的结果可以看出, 本文提出的算法在各个 方面都大大改善了算法全局解寻优能力, 并提高了最 优解精度. 这是由于本文算法采用了多尺度概率克隆 变异算子, 使得算法能在搜索空间内进行分散式的搜 索, 加快全局最优解的搜索速度的同时, 在进化后期 有效实现最优解的深度搜索. 从表2中最优解和最差 解实验结果之间的差异可以看出, 无论是DPSO还是 其他改进算法都不具备稳定性, 而本文算法相对于其 他算法而言稳定性大大提高, 这是因为算法在进化前 期能迅速定位到全局最优解区域. 6结结结论论论 1 针对传统离散微粒群算法状态转移过程中存 在最优解区域局部搜索能力差的不足, 提出一个多尺 度概率变异算子, 该算子可以有效实现在最优解附近 精确的局部搜索, 同时在算法初期利用大尺度概率克 隆变异操作可以使微粒群进行发散式的全局搜索, 从 而快速定位到全局最优解区域; 算法后期, 在小尺度 概率克隆变异操作进行局部精确解搜索的同时, 利用 大尺度概率变异的震荡性质可以帮助算法逃逸出局 部极小解, 实现算法勘探及开采能力的有机协调. 2 采用本文算法及其改进算法, 对5个经典 benchmark函数进行优化, 实验结果表明本文算法在 全局搜索性能及最优解精度方面都有显著提高. 需要 指出的是, 本文算法的计算复杂度相对其他算法而言 略有增加, 但这也是符合智能算法中“没有免费午餐” 定理的. 参考文献References [1]PoliR,KennedyJ,BlackwellT.Particleswarm optimization An overview[J]. Swarm Intell, 2007, 11 33-57. [2]陶新民, 徐晶. 改进的多种群协同进化微粒群优化算 法[J]. 控制与决策, 2009, 249 1406-1411 Tao X M, Xu J. Multi-species cooperative particle swarm optimization algorithm[J]. Control and Decision, 2009, 249 1406-1411. [3]Kennedy J, Eberhart R C. A discrete binary version of the particle swarm algorithm[C]. Proc of the World MulticonferenceonSystemics,Cybemeticsand Inatics. Orlando, 1997 4104-4109. [4]Pan Q K, Tasgetiren M F, Liang Y C. A discrete particle 706控制与决策第 26 卷 swarm optimization algorithm for the no-wait fl ow shop scheduling problem[J]. Computers Operations Research, 2008, 359 2807-2839. [5] Liu Y, Gu X P. Skeleton-network reconfi guration based on topological characteristics of scale-free networks and discrete particle swarm optimization[J]. IEEE Trans on Power Systems, 2007, 223 1267-1274. [6]潘全科, 王凌, 高亮. 离散微粒群优化算法的研究进展 [J]. 控制与决策, 2009, 2410 1441-1449. Pan Q K, Wang L, Gao L. The state-of-art of discrete particle swarm optimization algorithms[J]. Control and Decision, 2009, 2410 1441-1449. [7]张国富, 蒋建国, 夏娜. 基于离散粒子群算法求解复杂联 盟生成问题[J]. 电子学报, 2007, 352 323-327. Zhang G F, Jiang J G, Xia N. Solutions of complicated coalition generation based on discrete particle swarm optimization[J]. Acta Electronica Sinica, 2007, 352 323- 327. [8]钟一文, 宁正元, 蔡荣英. 一种改进的离散粒子群优化算 法[J]. 小型微型计算机系统, 2006, 2710 1893-1896. Zhong Y W, Ning Z Y, Cai R Y. An improved dscrete particle swarm optimization algorithm[J]. Mini- micro Systems, 2006, 2710 1893-1896. [9]黄艳新, 周春光. 一种求解类覆盖问题的混合算法[J]. 软 件学报, 2005, 164 513-522. Huang Y X, Zhou C G. A hybrid algorithm on class cover problems[J]. J of Software, 2005, 164 513-522. [10] Alberto G V, Rafael P. Introducing dynamic diversity into a discrete particle swarm optimization[J]. Computer and Operation Research, 2009, 363 951-966. [11] 钟一文, 蔡荣英. 求解二次分配问题的离散粒子群优化 算法[J]. 自动化学报, 2006, 2710 1893-1896. ZhongYW,CaiRY.Discreteparticleswarmoptimization algorithm for QAP[J]. Acta Automatica Sinica, 2006, 2710 1893-1896. [12] 吕强, 汤贤铭, 愈金寿. 基于信息素机制的离散粒子群算 法及其应用[J]. 系统仿真学报, 2008, 202 395-398. Lv Q, Tang X M, Yu J S. Discrete particle swarm optimization algorithm and its application based on pheromone mechanism[J]. J of System Simulation, 2008, 202 395-398. [13] 余伶俐, 蔡自兴. 改进混合离散粒子群的多种优化策略 算法[J]. 中南大学学报, 2009, 404 1047-1053. Yu L L, Cai Z X. Multiple optimization strategies for improving hybrid discrete particle