基于逐层演化的群体智能算法优化

工程科学学报，第39卷，第3期：462-473,2017年3月 Chinese Journal of Engineering,Vol.39,No.3:462-473,March 2017 DOI:10.13374/j.issn2095-9389.2017.03.020:http://journals.ustb.edu.cn 基于逐层演化的群体智能算法优化 张水平，王碧四，陈阳 江西理工大学信息工程学院，赣州341000 ☒通信作者，E-mail:happyeveryday._386@163.com 摘要为能彻底解决群体智能算法早熟问题的同时保持原算法主体不变且可与现有优化理论协同优化，在前期仿真实验 和理论证明的基础上，提出了一种逐层演化的改进策略.利用在原算法中构建基于搜索空间压缩理论的自适应系统，通过逐 层的压缩、选择、再初始化的操作，以包括压缩后搜索空间在内的社会信息作为遗传知识，指导寻优过程，从而实现最终解精 度的提升、避免早熟问题的出现.对基准函数进行仿真实验可以看出该策略在提升算法精度，增强后期个体活性方面具有良 好的表现. 关键词群体智能：搜索空间：逐层演化：早熟 分类号TP301.6 Optimization for swarm intelligence based on layer-by-ayer evolution ZHANG Shui-ping,WANG Bi,CHEN Yang) Faculty of Information Engineering,Jiangxi University of Science and Technology,Ganzhou 341000,China Corresponding author,E-mail:happyeveryday_386@163.com ABSTRACT A layer-by-ayer evolution strategy was proposed to deal with the premature convergence of swarm intelligence as a col- laborator with other existing researches based on pre-experiments and simple proofs.For promoting the precision of solution and eviting the premature convergence,the self-adaption system was constructed on the basis of the primal algorithm,operations such as compres- sion,selection and re-initialization using the technology of layer-by-ayer,and the social information was used including the com- pressed research space and the optimal solution.The improvements of precision of solution and the vitality of terminal individuals can be found in results of simulation experiments with benchmark functions. KEY WORDS swarm intelligence:search space:layer-by-ayer;premature convergence 群体智能算法是以多个体为探索主体，利用群组增加种群内个体数量和迭代次数.随之而来的是更加 之间的有效社会信息对个体演化产生影响，从而进行「 巨大的计算开销.同时，由于现有对各算法的改进优 最优解探索并保证算法收敛的一类优化算法，如遗传化成果众多，且有良好效果.但策略之间存在明显的 算法(GA)、粒子群优化算法(PS0)和差分进化(DE)非兼容性.如果不考虑对大多数现有优化策略的兼容 等.智能算法体系中，各类算法通过不同的演化策略 问题，无疑是对以往研究成果的一种巨大浪费.为此， 实现对全局最优解的定位，而在这过程中如何避免局 如何k在不改变原有算法收敛性的前提下，尽可能的 部最优解和早熟问题是二十余年来改进算法所不断研 改变收敛曲线在算法末期保持不变或变化较小的现 究的重点.然而，由于算法具有收敛性及强随机性，早 状，是本文希望解决的主要问题 熟问题并未得到良好的解决，其表现为收敛曲线随迭 在材料领域，layer-by-ayer(LBL)技术被用来对纳 代次数增加而趋于平滑.这是算法收敛性所带来的必 米薄膜进行组装0.通过利用浸泡(immersive)、离心 然结果，同时也使得在需要获得更加精确的解时，只能 旋转(spin)、喷洒(spray)、电解(electromagnetic)和液 收稿日期：20160509

工程科学学报，第 39 卷，第 3 期: 462--473，2017 年 3 月 Chinese Journal of Engineering，Vol． 39，No． 3: 462--473，March 2017 DOI: 10． 13374 /j． issn2095--9389． 2017． 03． 020; http: / /journals． ustb． edu． cn 基于逐层演化的群体智能算法优化 张水平，王 碧，陈 阳 江西理工大学信息工程学院，赣州 341000 通信作者，E-mail: happyeveryday_386@ 163． com 摘 要 为能彻底解决群体智能算法早熟问题的同时保持原算法主体不变且可与现有优化理论协同优化，在前期仿真实验 和理论证明的基础上，提出了一种逐层演化的改进策略． 利用在原算法中构建基于搜索空间压缩理论的自适应系统，通过逐 层的压缩、选择、再初始化的操作，以包括压缩后搜索空间在内的社会信息作为遗传知识，指导寻优过程，从而实现最终解精 度的提升、避免早熟问题的出现． 对基准函数进行仿真实验可以看出该策略在提升算法精度，增强后期个体活性方面具有良 好的表现． 关键词 群体智能; 搜索空间; 逐层演化; 早熟 分类号 TP301. 6 Optimization for swarm intelligence based on layer-by-layer evolution ZHANG Shui-ping1) ，WANG Bi1)  ，CHEN Yang1) Faculty of Information Engineering，Jiangxi University of Science and Technology，Ganzhou 341000，China  Corresponding author，E-mail: happyeveryday_386@ 163． com ABSTＲACT A layer-by-layer evolution strategy was proposed to deal with the premature convergence of swarm intelligence as a col￾laborator with other existing researches based on pre-experiments and simple proofs． For promoting the precision of solution and eviting the premature convergence，the self-adaption system was constructed on the basis of the primal algorithm，operations such as compres￾sion，selection and re-initialization using the technology of layer-by-layer，and the social information was used including the com￾pressed research space and the optimal solution． The improvements of precision of solution and the vitality of terminal individuals can be found in results of simulation experiments with benchmark functions． KEY WOＲDS swarm intelligence; search space; layer-by-layer; premature convergence 收稿日期: 2016--05--09 群体智能算法是以多个体为探索主体，利用群组 之间的有效社会信息对个体演化产生影响，从而进行 最优解探索并保证算法收敛的一类优化算法，如遗传 算法( GA) 、粒子群优化算法( PSO) 和差分进化( DE) 等． 智能算法体系中，各类算法通过不同的演化策略 实现对全局最优解的定位，而在这过程中如何避免局 部最优解和早熟问题是二十余年来改进算法所不断研 究的重点． 然而，由于算法具有收敛性及强随机性，早 熟问题并未得到良好的解决，其表现为收敛曲线随迭 代次数增加而趋于平滑． 这是算法收敛性所带来的必 然结果，同时也使得在需要获得更加精确的解时，只能 增加种群内个体数量和迭代次数． 随之而来的是更加 巨大的计算开销． 同时，由于现有对各算法的改进优 化成果众多，且有良好效果． 但策略之间存在明显的 非兼容性． 如果不考虑对大多数现有优化策略的兼容 问题，无疑是对以往研究成果的一种巨大浪费． 为此， 如何 k 在不改变原有算法收敛性的前提下，尽可能的 改变收敛曲线在算法末期保持不变或变化较小的现 状，是本文希望解决的主要问题． 在材料领域，layer-by-layer( LBL) 技术被用来对纳 米薄膜进行组装［1］． 通过利用浸泡( immersive) 、离心 旋转( spin) 、喷洒( spray) 、电解( electromagnetic) 和液

张水平等：基于逐层演化的群体智能算法优化 ·463· 体流动(luidic)等方式对纳米薄膜进行处理.为获得 l=X(ww+c51(p.-x)+c22（g-x)）, (1) 具有特定功能的薄膜材料，研究者们常常将薄膜依次 xl=x++l 通过不同的原液并利用上述方法使原液附着在薄膜表 式中，v为速度，w为权重，c,、C2为学习因子，x为当前 面从而形成新的功能材料.这一思想与群体智能算法 位置，P。g分别为该粒子自身的历史最优位置和当前 中的演化方式网相吻合.所不同的是，传统的智能算 已知的全局最优解，t为迭代次数，，r2∈(0,1)为随 法是将“薄膜”一直浸泡在同一种液体之中 机数X为收缩因子.在这一阶段，主要的优化策略包 本文采用搜索空间▣作为关键因素，来完成将 括，位置更新和边界约束.其中位置更新部分又可分 “薄膜”经过多次浸泡从而获得拥有更加良好表现的 为：参数优化6、公式更新0-0、拓扑结构2四改进 智能算法.搜索空间是对连续函数进行群体智能求解 这些优化策略是粒子群算法所特有的.而更具通用性 的必要参数，是与求解问题相关的，且会对算法最终输 的则是边界约束4-，然而，在其他群体智能算法实 出解精度产生影响.当“薄膜”每一次与“液体”充分 施过程中，由于进化策略的不同，并不一定会出现个体 接触后，将对其进行清洗，去除多余的“附着物”.之后 越界的情况出现，因此，这一策略依旧仅在粒子群算法 再次与“液体”进行接触，依次循环下去。直到获得预 中存在广泛应用研究.为了构建普适性更好的优化策 期的结果.“薄膜”便是我们最开始的搜索空间，也可 略，这些传统粒子群中的优化方法将作为参考依据而 以认为是当前的全局最优解“液体”则是各算法的进 非主要研究对象.搜索空间对于绝大多数智能算法而 化策略.此外，还需要对“充分接触”所代表的迭代次 言，与目标函数一样，是作为基本输入信息而存在的 数以及清洗策略做出具体定义. 搜索空间压缩策略是指，通过以某一基准点（策略不 为了将该思想进一步阐述清楚，文章在第1章将 同，所选取的点也不尽相同)为中心，并完成对当前搜 会对粒子群优化算法做一个简短的介绍.在第2章中 索空间的压缩，以此来提升算法效率的一种优化策略 则介绍了相关准备工作，从基本实验中展示出逐层演 公式(2)和公式(3)在文献6-17]中被提出.不难看 化模型的可行性.对于逐层演化在粒子群中的实现及 出二者都是通过计算粒子之间的距离来判断种群的收 其理论证明则在第3章中进行说明.最后，作为结论， 敛程度。除此之外，也有利用实验总结圆，得出种群 在第4章中对文中思想优势与不足做出了概述 收敛的大致节点.这些研究在完成种群多样性判别 1研究背景 后，都不约而同的以此作为标准，用来完成对粒子群速 度更新公式或权重的控制.而本文在后续论述中将公 1.1群体智能与搜索空间压缩 式(2)~(3)作为种群多样性判别标准进行对比讨论. 群体智能算法是指以多个体为探索主体，利用群 (xg-)2, (2) 组之间的有效社会信息对个体演化产生影响，从而进 行最优解探索并保证收敛的一类优化算法.算法的输 入为搜索空间与目标函数，输出则为搜寻得到的最优 (3) 解.在过去的二十余年中，这类优化算法得到了长足 其中，P、D和K分别是种群中个体数量、目标问题维 地发展，形成了如遗传算法(GA)、粒子群算法(PSO) 度和搜索空间边界最大距离 和差分进化(DE),并广泛地应用于众多研究与实践领 1.2层层组装技术 域.以粒子群算法为例，位置更新是粒子群算法进化 层层组装技术四是指在构建特定功能材料的时 迭代的核心.在本文中所提及的标准粒子群算法叼， 候，采用的一种处理工艺.其具体流程可由图1展示 采用下式来更新位置和速度： 研究人员首先将一块薄膜介质作为基础，浸入功能溶 基片 涂层1 涂层2 重复上述过 图1层层组装浸泡工艺流程示意图0 Fig.1 Layer-by-ayer assembly technologies

张水平等: 基于逐层演化的群体智能算法优化 体流动( fluidic) 等方式对纳米薄膜进行处理． 为获得 具有特定功能的薄膜材料，研究者们常常将薄膜依次 通过不同的原液并利用上述方法使原液附着在薄膜表 面从而形成新的功能材料． 这一思想与群体智能算法 中的演化方式［2］相吻合． 所不同的是，传统的智能算 法是将“薄膜”一直浸泡在同一种液体之中． 本文采用搜索空间［3］ 作为关键因素，来完成 将 “薄膜”经过多次浸泡从而获得拥有更加良好表现的 智能算法． 搜索空间是对连续函数进行群体智能求解 的必要参数，是与求解问题相关的，且会对算法最终输 出解精度产生影响． 当“薄膜”每一次与“液体”充分 接触后，将对其进行清洗，去除多余的“附着物”． 之后 再次与“液体”进行接触，依次循环下去． 直到获得预 期的结果． “薄膜”便是我们最开始的搜索空间，也可 以认为是当前的全局最优解; “液体”则是各算法的进 化策略． 此外，还需要对“充分接触”所代表的迭代次 数以及清洗策略做出具体定义． 为了将该思想进一步阐述清楚，文章在第 1 章将 会对粒子群优化算法做一个简短的介绍． 在第 2 章中 则介绍了相关准备工作，从基本实验中展示出逐层演 化模型的可行性． 对于逐层演化在粒子群中的实现及 其理论证明则在第 3 章中进行说明． 最后，作为结论， 在第 4 章中对文中思想优势与不足做出了概述． 1 研究背景 图 1 层层组装浸泡工艺流程示意图［1］ Fig． 1 Layer-by-layer assembly technologies［1］ 1. 1 群体智能与搜索空间压缩 群体智能算法是指以多个体为探索主体，利用群 组之间的有效社会信息对个体演化产生影响，从而进 行最优解探索并保证收敛的一类优化算法． 算法的输 入为搜索空间与目标函数，输出则为搜寻得到的最优 解． 在过去的二十余年中，这类优化算法得到了长足 地发展，形成了如遗传算法( GA) 、粒子群算法( PSO) 和差分进化( DE) ，并广泛地应用于众多研究与实践领 域． 以粒子群算法为例，位置更新是粒子群算法进化 迭代的核心． 在本文中所提及的标准粒子群算法［4--5］， 采用下式来更新位置和速度: v t + 1 = χ( ωv t + c1 r1 ( pg － x) + c2 r2 ( g － x) ) ， xt + 1 = xt + v { t + 1 ． ( 1) 式中，v 为速度，ω 为权重，c1、C2为学习因子，x 为当前 位置，pg、g 分别为该粒子自身的历史最优位置和当前 已知的全局最优解，t 为迭代次数，r1，r2∈( 0，1) 为随 机数，χ 为收缩因子． 在这一阶段，主要的优化策略包 括，位置更新和边界约束． 其中位置更新部分又可分 为: 参数优化［6--9］、公式更新［10--11］、拓扑结构［12--13］改进． 这些优化策略是粒子群算法所特有的． 而更具通用性 的则是边界约束［14--15］，然而，在其他群体智能算法实 施过程中，由于进化策略的不同，并不一定会出现个体 越界的情况出现，因此，这一策略依旧仅在粒子群算法 中存在广泛应用研究． 为了构建普适性更好的优化策 略，这些传统粒子群中的优化方法将作为参考依据而 非主要研究对象． 搜索空间对于绝大多数智能算法而 言，与目标函数一样，是作为基本输入信息而存在的． 搜索空间压缩策略是指，通过以某一基准点( 策略不 同，所选取的点也不尽相同) 为中心，并完成对当前搜 索空间的压缩，以此来提升算法效率的一种优化策略． 公式( 2) 和公式( 3) 在文献［16--17］中被提出． 不难看 出二者都是通过计算粒子之间的距离来判断种群的收 敛程度． 除此之外，也有利用实验总结［18］，得出种群 收敛的大致节点． 这些研究在完成种群多样性判别 后，都不约而同的以此作为标准，用来完成对粒子群速 度更新公式或权重的控制． 而本文在后续论述中将公 式( 2) ～ ( 3) 作为种群多样性判别标准进行对比讨论． d( P) = 1 P·K ∑ P i = 1 ∑ D j = 1 ( xij － xj ) 槡 2 ， ( 2) d( i) = 1 P － 1 ∑ P j = 1，j≠i ∑ D k = 1 ( xi，k － xj，k ) 槡 2 ． ( 3) 其中，P、D 和 K 分别是种群中个体数量、目标问题维 度和搜索空间边界最大距离． 1. 2 层层组装技术 层层组装技术［1］是指在构建特定功能材料的时 候，采用的一种处理工艺． 其具体流程可由图 1 展示． 研究人员首先将一块薄膜介质作为基础，浸入功能溶 · 364 ·

·464· 工程科学学报，第39卷，第3期 液中.等待一段时间至薄膜表面附着粒子后用清水洗 (1)利用标准粒子群算法，式(1)，作为核心演化 掉多余的.之后再浸入另一功能溶液中，如此往复，直 策略，并选取固定权值、随机权值网、线性权重四、非 至获得特定功能的薄膜.若将该技术应用于智能算法 线性权重四（后分别记为，~w:)作为对比参数： 之中，则主要问题在于切换不同溶液时，如何确定种群 (2)依次增加种群中粒子数量（由20增加到200） 所需携带的社会信息.虽然在整个寻优过程中，看似 而其他条件保持不变（维度D=30).对于任意权重策 只有已知全局最优点在对种群进化产生较大影响.但 略与种群数量的组合重复进行50次实验并记录迭代 在实际过程中，整个群体内的个体对于算法而言都是 信息； 至关重要的.为此，当出现分层技术时如何在切换不 (3)选取Ackley函数作为测试函数，进行寻优测试： 同层的过程中尽可能保证社会信息中的有效部分是十 (4)为防止出现由于粒子数量增加使得解精度提 分困难的：而不对信息进行删减，则等同于传统的求解 升、造成数据比对不便的原因，对最终结果进行归一化 过程，无法体现改进效果.为此，则需要选择具有良好 处理，形成最终结果 通用性、可继承性的社会信息作为遗传要素.而搜索 2.1种群多样性判别实验对比 空间无疑是一个良好的选择 策略1为式(2)所示的判别策略叨，策略2为式 2相关问题研究 (4)所示判别策略四，将实验中各组（按粒子数量分 类)实验中粒子在迭代过程中的具体位置作为输入， 张水平和王碧圆对粒子群算法可利用搜索空间压 进行计算两个策略在迭代过程中的适应度，并将所得 缩策略进行优化的基本条件做出了简单的描述.最为 适应度归一化处理，获得如图2和图3所示曲线图 关键的是需要被优化的算法具有良好的收敛性.而收 由于在本文中需要稳定的判别标准作为空间压缩的重 敛性的存在，可以为后续的压缩搜索空间提供良好的 要指标，而文献6]中的策略正如其文中所述一般， 指导.推广开来，与粒子群算法一般具有收敛性的群 具有很强的随机性，并不能很好的作为指示标准，故在 体智能算法对此优化策略也具有潜在可适用性.构建 此处不对其进行展开讨论 压缩搜索空间自适应系统的关键是拟定良好的收敛状 态判别条件.此判别条件需要具有随着迭代次数增加 ∑(Igl≤Blb,b.I) d(t)= (4) 而趋于稳定的特定；同时还需要在时间点上与收敛曲 线拐点相一致.为了选取合适的收敛判断，本文将对 式中，g为当前迭代中已知最优解：b,、b。分别为搜索 现有种群多样性判别曲线、最大迭代次数与收敛点的 空间的上下限：B=1×106为阌值，与‖b,b。‖一同构 相关性问题进行实验研究.实验设计如下： 成领域的判别标准. 1.0 10b 0.5 0.5 0 0 0.5 0.5 -1.0 -1.0 0 200 400600 800 1000 0 200 400 600 800 1000 选代次数 迭代次数 1.0f 10 d) 0.5 0.5 0 05 0.5 -1.0f -1.0 0 200 400600 800 1000 0 200 400 600 8001000 迭代次数 迭代次数 图2策略1种群多样性曲线(Ackley).(a)固定权值：(b)随机权值；(c)线性权重：(d)非线性权重 Fig.2 Illustrating the swarms diversity with strategy I (Ackley):(a)constant-weight:(b)random-weight:(c)linear-weight;(d)nonlinear- weight

工程科学学报，第 39 卷，第 3 期 液中． 等待一段时间至薄膜表面附着粒子后用清水洗 掉多余的． 之后再浸入另一功能溶液中，如此往复，直 至获得特定功能的薄膜． 若将该技术应用于智能算法 之中，则主要问题在于切换不同溶液时，如何确定种群 所需携带的社会信息． 虽然在整个寻优过程中，看似 只有已知全局最优点在对种群进化产生较大影响． 但 在实际过程中，整个群体内的个体对于算法而言都是 至关重要的． 为此，当出现分层技术时如何在切换不 同层的过程中尽可能保证社会信息中的有效部分是十 分困难的; 而不对信息进行删减，则等同于传统的求解 过程，无法体现改进效果． 为此，则需要选择具有良好 通用性、可继承性的社会信息作为遗传要素． 而搜索 空间无疑是一个良好的选择． 2 相关问题研究 张水平和王碧［3］对粒子群算法可利用搜索空间压 缩策略进行优化的基本条件做出了简单的描述． 最为 关键的是需要被优化的算法具有良好的收敛性． 而收 敛性的存在，可以为后续的压缩搜索空间提供良好的 指导． 推广开来，与粒子群算法一般具有收敛性的群 体智能算法对此优化策略也具有潜在可适用性． 构建 压缩搜索空间自适应系统的关键是拟定良好的收敛状 态判别条件． 此判别条件需要具有随着迭代次数增加 而趋于稳定的特定; 同时还需要在时间点上与收敛曲 线拐点相一致． 为了选取合适的收敛判断，本文将对 现有种群多样性判别曲线、最大迭代次数与收敛点的 相关性问题进行实验研究． 实验设计如下: ( 1) 利用标准粒子群算法，式( 1) ，作为核心演化 策略，并选取固定权值、随机权值［19］、线性权重［20］、非 线性权重［21］( 后分别记为 w1 ～ w4 ) 作为对比参数; ( 2) 依次增加种群中粒子数量( 由 20 增加到 200) 而其他条件保持不变( 维度 D = 30) ． 对于任意权重策 略与种群数量的组合重复进行 50 次实验并记录迭代 信息; ( 3) 选取 Ackley 函数作为测试函数，进行寻优测试; ( 4) 为防止出现由于粒子数量增加使得解精度提 升、造成数据比对不便的原因，对最终结果进行归一化 处理，形成最终结果． 2. 1 种群多样性判别实验对比 策略 1 为式( 2) 所示的判别策略［17］，策略 2 为式 ( 4) 所示判别策略［3］，将实验中各组( 按粒子数量分 类) 实验中粒子在迭代过程中的具体位置作为输入， 进行计算两个策略在迭代过程中的适应度，并将所得 适应度归一化处理，获得如图 2 和图 3 所示曲线图． 由于在本文中需要稳定的判别标准作为空间压缩的重 要指标，而文献［16］中的策略正如其文中所述一般， 具有很强的随机性，并不能很好的作为指示标准，故在 此处不对其进行展开讨论． d( t) = ∑ P i = 1 ( ‖xi，g‖ ≤ β‖bl，bu‖) P ． ( 4) 式中，g 为当前迭代中已知最优解; b1、bu 分别为搜索 空间的上下限; β = 1 × 10 － 6为阈值，与‖bl，bu‖一同构 成领域的判别标准． 图 2 策略 1 种群多样性曲线 ( Ackley) . ( a) 固定权值; ( b) 随机权值; ( c) 线性权重; ( d) 非线性权重 Fig． 2 Illustrating the swarms diversity with strategy 1 ( Ackley) : ( a) constant-weight; ( b) random-weight; ( c) linear-weight; ( d) nonlinear￾weight · 464 ·

张水平等：基于逐层演化的群体智能算法优化 ·465 1.0 1.0 % 0.5 0.5 0 05 -1.0 0 2004006008001000 0 200 4006008001000 迭代次数 迭代次数 1.0F (e) 1.0(d) 0.5 05 0.5 -0.5 -10 -1.0 0 200 400600 800 1000 0 200 400600 8001000 选代次数 迭代次数 图3策略2种群多样性曲线(Ackley).(a)固定权值：(b)随机权值：(c)线性权重：(d)非线性权重 Fig.3 lllustrating the swarms diversity with strategy 2 (Ackley):(a)constant-weight:(b)random-weight:(c)linear-weight:(d)nonlinear- weight 如图2所示，策略1所生成的曲线可以清楚展示 并依此绘制曲线.获得当适应度函数恒定但搜索空间 出判断标准所具有的稳定性，且各组种群粒子数量不 规模不同的情况下输出解精度的变化，如图4所示. 同的实验曲线趋势一致，由此可知，该策略在稳定性这 可以清楚的看出，当搜索空间规模下降时，最终解的精 一点上是可以应用于后续研究的.同样的性质也在策 度也会随之提升，即解精度与搜索空间规模成负相关， 略2中得到体现，如图3所示.策略2在收敛过程中的 如式(6)所示，其中G,和S分别是理论最优解和搜索 取值并不稳定，如图3中的黑色部分是由于取值的高 空间规模 低变化而造成的.相对来说，策略1更加的平稳一些， b1,b]°=b,b]/10, (5) 基本保持非增的曲线.由式(4)可知，策略2计算获得 1 Ig-Ga‖xs (6) 的值d应是百分数.在实际应用中，则需要设置一个 由此可知，如果能保证在压缩搜索空间过程中，全 成熟阈值y,其数值可以与种群清洗保留比例α相同， 局最优解并不会被丢弃，则压缩搜索空间的次数越多、 使得当满足d≥y时，触发搜索空间压缩，为保证粒子 搜索空间将越小的情况下，获得的解精度将会大大提 的收敛状态，则y应为较大值.在此前提下，策略2的 升.为此，后续研究均以这一特性为准则：在尽可能保 触发时间基本保证在策略1趋于稳定后.这就使得采 证不丢弃最优解的情况下，取得尽可能多的压缩次数 用策略2作为判别标准时，可能造成计算资源的浪费， 和压缩幅度，以确定一个极小的搜索空间.同时，策略 又或者采用策略1作为判别标准时，可能整个种群尚 2所需的计算复杂度为O(P)而策略1的则为0(P), 未完全进入稳态.为此，在后续实验中将会分别采用 策略2所需的计算资源更少一些 这两种策略对算法进行改进并对比优化.其中，策略1 将会设置较高的阈值，使得自适应系统在曲线近似收 3逐层演化的粒子群算法 敛的情况下触发；策略2则会在最先到达指定阈值的 3.1理论证明 时候触发自适应系统，完成空间压缩，以期得到一个良 为了进一步说明搜索空间压缩对于命中高适应度 好的判别标准来解决种群多样性的判别问题. 解概率的提升作用，如图5所示，将2维搜索空间划分 2.2搜索空间与最终解精度 为m个较大空间（灰色所示）并将每个较大空间再次 为进一步说明搜索空间大小与最终输出解精度的 划分为个较小的空间.不难得出，较小的空间在连 关系，利用式(5)设计实验对比，使得搜索空间范围随 续函数的情况下会包含更为精确的解.假设A和B分 着k值增大而逐渐减小.选择函数Ackley()作为测 别为较大空间和较小空间内搜寻的初始位置，0为最 试函数，在保证除搜索空间外其他条件不变的情况下， 优解所在位置. 对4种不同的权重策略进行50次重复实验，取平均值 假设粒子在空间内移动过程为齐次马尔科夫过

张水平等: 基于逐层演化的群体智能算法优化 图 3 策略 2 种群多样性曲线 ( Ackley) . ( a) 固定权值; ( b) 随机权值; ( c) 线性权重; ( d) 非线性权重 Fig． 3 Illustrating the swarms diversity with strategy 2 ( Ackley) : ( a) constant-weight; ( b) random-weight; ( c) linear-weight; ( d) nonlinear￾weight 如图 2 所示，策略 1 所生成的曲线可以清楚展示 出判断标准所具有的稳定性，且各组种群粒子数量不 同的实验曲线趋势一致，由此可知，该策略在稳定性这 一点上是可以应用于后续研究的． 同样的性质也在策 略2 中得到体现，如图3 所示． 策略2 在收敛过程中的 取值并不稳定，如图 3 中的黑色部分是由于取值的高 低变化而造成的． 相对来说，策略 1 更加的平稳一些， 基本保持非增的曲线． 由式( 4) 可知，策略 2 计算获得 的值 d 应是百分数． 在实际应用中，则需要设置一个 成熟阈值 γ，其数值可以与种群清洗保留比例 α 相同， 使得当满足 d≥γ 时，触发搜索空间压缩，为保证粒子 的收敛状态，则 γ 应为较大值． 在此前提下，策略 2 的 触发时间基本保证在策略 1 趋于稳定后． 这就使得采 用策略 2 作为判别标准时，可能造成计算资源的浪费， 又或者采用策略 1 作为判别标准时，可能整个种群尚 未完全进入稳态． 为此，在后续实验中将会分别采用 这两种策略对算法进行改进并对比优化． 其中，策略 1 将会设置较高的阈值，使得自适应系统在曲线近似收 敛的情况下触发; 策略 2 则会在最先到达指定阈值的 时候触发自适应系统，完成空间压缩，以期得到一个良 好的判别标准来解决种群多样性的判别问题． 2. 2 搜索空间与最终解精度 为进一步说明搜索空间大小与最终输出解精度的 关系，利用式( 5) 设计实验对比，使得搜索空间范围随 着 k 值增大而逐渐减小． 选择函数 Ackley ( f4 ) 作为测 试函数，在保证除搜索空间外其他条件不变的情况下， 对 4 种不同的权重策略进行 50 次重复实验，取平均值 并依此绘制曲线． 获得当适应度函数恒定但搜索空间 规模不同的情况下输出解精度的变化，如图 4 所示． 可以清楚的看出，当搜索空间规模下降时，最终解的精 度也会随之提升，即解精度与搜索空间规模成负相关， 如式( 6) 所示，其中 Greal和 S 分别是理论最优解和搜索 空间规模． ［bl，bu ］* =［bl，bu ］/10k ， ( 5) ‖g － Greal‖∝ 1 S ． ( 6) 由此可知，如果能保证在压缩搜索空间过程中，全 局最优解并不会被丢弃，则压缩搜索空间的次数越多、 搜索空间将越小的情况下，获得的解精度将会大大提 升． 为此，后续研究均以这一特性为准则: 在尽可能保 证不丢弃最优解的情况下，取得尽可能多的压缩次数 和压缩幅度，以确定一个极小的搜索空间． 同时，策略 2 所需的计算复杂度为 O( P) 而策略 1 的则为 O( P2 ) ， 策略 2 所需的计算资源更少一些． 3 逐层演化的粒子群算法 3. 1 理论证明 为了进一步说明搜索空间压缩对于命中高适应度 解概率的提升作用，如图 5 所示，将 2 维搜索空间划分 为 m 个较大空间( 灰色所示) 并将每个较大空间再次 划分为 n 个较小的空间． 不难得出，较小的空间在连 续函数的情况下会包含更为精确的解． 假设 A 和 B 分 别为较大空间和较小空间内搜寻的初始位置，O 为最 优解所在位置． 假设粒子在空间内移动过程为齐次马尔科夫过 · 564 ·

·466· 工程科学学报，第39卷，第3期 (a) -10 -10 -15 10 八0 0 5 -5 -10 -10 -15 0 0 10 图4搜索空间大小与最终解精度相关函数图.()固定权重：(b)随机权重：(c)线性权重：(d)非线性权重 Fig.4 Relations between the precision of the solution and the scale of the search space:(a)constant-weight:(b)random-weight:(c)linear- weight:(d)nonlinear-weight 程，一步概率转移矩阵如下式所示，为均匀分布 1 1 mn mn (7) 1 … 、mn mn 若第1+1次首次命中最优解邻域0（图5中所 示)，则分别计算无压缩空间机制即随机模式和压缩 空间机制下的概率p4 p点y 2 )(:)] X 图5划分搜素空间下的命中概率示意图 -=会)] Fig.5 Schematic diagram of the hitting probability based on the di- vided search space (8) 现令m=n→，则公式(8)可化简如下： f(t)≤f(1)=0. (9) P-9= 因此 [(-[)()]- p-g=(00，设： 造成最优解丢失的情况下，随着压缩次数增加而提升. 加之上文中的具体实验，可以证明，搜索空间压缩策略 f0=(m）- 是切实有效的.同时由于逐层演化思想的引入，可以 f0=()h(）-1<0(mx). 有效的组织各层之间对于所面临的不同问题，如是主 要进行全局探索还是进行局部搜索等，通过调整不同 即f(t)是t的单调减函数，由此可知 层内的进化策略进而到达提升解精度的目的

工程科学学报，第 39 卷，第 3 期 图 4 搜索空间大小与最终解精度相关函数图 . ( a) 固定权重; ( b) 随机权重; ( c) 线性权重; ( d) 非线性权重 Fig． 4 Ｒelations between the precision of the solution and the scale of the search space: ( a) constant-weight; ( b) random-weight; ( c) linear￾weight; ( d) nonlinear-weight 程，一步概率转移矩阵如下式所示，为均匀分布． pm × n = 1 mn … 1 mn    1 mn … 1            mn ． ( 7) 若第 t + 1 次首次命中最优解邻域 O( 图 5 中所 示) ，则分别计算无压缩空间机制即随机模式和压缩 空间机制下的概率 p、q． p = 1 mn· ( mn － 1 ) mn t ， q = 1 mn∑ t i = [ ( 0 m － 1 ) m ( i n － 1 ) n ] t －i ， p－q = 1 mn·( mn － 1 ) mn t － 1 mn∑ t i = [ ( 0 m － 1 ) m ( i n － 1 ) n ] t －i        ． ( 8) 现令 m = n→∞ ，则公式( 8) 可化简如下: p － q = 1 [ ( mn mn － 1 ) mn t － ∑ t i = [ ( 0 m － 1 ) m ( i n － 1 ) n t － ] ] i = 1 m2 ( m － 1 ) m [ ( t m + 1 ) m t － ] t ． 已知 1 m2 ( m － 1 ) m t ＞ 0，设: f( t) ( = m + 1 ) m t － t， f'( t) ( = m + 1 ) m t ( ln m + 1 ) m － 1 ＜ 0( m→∞ ) ． 即 f( t) 是 t 的单调减函数，由此可知 图 5 划分搜索空间下的命中概率示意图 Fig． 5 Schematic diagram of the hitting probability based on the di￾vided search space f( t) ≤f( 1) = 0． ( 9) 因此 p － q = 1 m2 ( m － 1 ) m t f( t) ≤0． ( 10) 由此可知，通过压缩搜索空间是可以在一定程度 上提升命中更优解的概率． 同时这一改变在保证不会 造成最优解丢失的情况下，随着压缩次数增加而提升． 加之上文中的具体实验，可以证明，搜索空间压缩策略 是切实有效的． 同时由于逐层演化思想的引入，可以 有效的组织各层之间对于所面临的不同问题，如是主 要进行全局探索还是进行局部搜索等，通过调整不同 层内的进化策略进而到达提升解精度的目的． · 664 ·

张水平等：基于逐层演化的群体智能算法优化 ·467 3.2算法基本思想 弃情况时，可以设为零，bs()为绝对值函数 多分组的粒子群在不同区域的搜索空间内，经过： [b:=g-max [abs(g-b)B,L], (13) 步迭代探索局部最优解后保留大部分适应度高的局部 b:=g+max [abs (g-b.)B,L] 最优解所在空间，并对其进行压缩：而其他空间则抛 (3)再次初始化. 弃，是该策略的主要思想 再次初始化时，可以将被淘汰群体中的粒子加入 (1)首次初始化时将搜索空间$划分为多个子空 保留群组中，进一步提升解精度：同样也可以直接放弃 间S,并随机分配给各个独立的粒子群P· 这部分粒子，从而提升算法的效率.如文献中提出的 若按照某一规则对所有维度进行划分，则划分的 策略一致，每次再初始化时需要保存必要的社会信息， 子空间数随着维度增加而逐渐增加，以简单的对半划 在粒子群算法中即保存已知最优解g,而初始化粒子 分为例，子空间的个数为2”，其中D为问题维度.为 则尽可能的进行均匀分配，也可以利用文献中提及的 此，在后续实验中，采用的是一种简单的随机划分空间 混沌遍历.通过再初始化可以有效地提升粒子的“活 策略，假设所需划分的子空间数量为e=e.·e,其中e. 力”，增加群内粒子多样性，改善依然趋于收敛的现 和e,为两个自然数，则用公式(11)进行划分子空间. 状.是利用搜索空间压缩进行优化的必要手段之一. 其中，i≤e,m,n≤D,m≠n为随机数，即随机挑选两个 其伪代码实现如表1所示 维度进行多项划分.若需要划分的维度为其他值，则 现对2维多峰值函数进行实验，并绘制各种群搜 可以适当调整即可 索空间范围，获得如图6所示结果，用来展示本文所提 策略的优化细节.其中，横纵坐标表示2维搜索空间 Bu.=b'LypJ,ypm.=1,ym = Tiles 范围，灰色黑边矩形表示一个独立种群的搜索子空间. mod (i,e)+1 y.= (11) 随着清洗过程的进行，子空间数量在逐渐减少，同时目 e 标空间范围也越来越小，即所搜索的空间范围精度提 (2)在浸泡阶段独立的粒子群P:进行空间探索， 高.这一演化过程与之前的设想基本吻合，可用于提 除粒子越过最初的搜索空间S外，不对各子空间进行 升算法精度. 越界处理 3.3实验设计与结果 (3)清洗过程则仅仅保留寻优效果较好的粒子群 选取了11个经典基准函数进行测试，在此处不对 组及其周围空间（已压缩），而其他搜索空间则被 表达式进行详细展开四，如表2所示.其中0为偏移 丢弃 量，此处设定o=10',仅作偏移，可以设置为其他值 (4)压缩过程将(3)所得空间进行压缩，保存新的 函数∫和∫及其转换形式均为单峰函数，而其他则 空间大小. 为多峰值函数 (5)再次初始化并不需要将剩余的空间再次划分 由于逐层演化的策略是将每一个独立的群体智能 为多个子空间，而是将被淘汰的群体中的粒子分配到 算法看作一次浸泡过程而不去改变原有算法的结构流 其他群组中去.除首次初始化外，整个空间中的群组 程，该策略的本质是如何去除在演化过程中无效或者 数量是随清洗次数递减的.如此直至最后输出. 效果较差的迭代、降低计算资源的浪费.故此，一个良 为实现这一设想，需要进行下列设置： 好的原算法由于具有良好的寻优能力，则在应用时可 (1)粒子群组的递减策略：保留比例α=0.7，该 以增加裁剪搜索空间的力度，极大程度上缩小搜索空 值不固定. 间范围，从而获得更高精度的解；：而相对于搜索能力较 保留机制采用best-first原则，保留最终适应度较 差的原算法，则需要注意搜索空间压缩力度，防止出现 高的一部分粒子群组.每次淘汰群组数量由下式计算 丢弃实际最优解的可能.考虑到这一特点，加之粒子 可得， 群算法优化策略众多且未有较为权威的标准，为此，选 R°=max(1,Ra). (12) 取SPSO田不仅可以保证原算法的易实现性.同时也 式中，R为群组数量.通过向上取整保证至少存在一 由于其常作为优化对照方案，查询效率低于大多数改 组粒子群在进行寻优探索 进算法，可以作为一个标尺，展现出本文策略的提升效 (2)搜索空间压缩策略：压缩比例B=0.5,可根据 果。而在应对更为精确的优化策略时，只需要相应的 清洗次数而定. 调整搜索空间压缩力度便可获得进一步提升. 由前文已然得出结论，更小的搜索空间可以提供 利用本文所提及的用于种群多样性判别策略对 更为精确的解，且算法收敛时粒子依附于当前已知最 SPS0因进行搭载测试，由于关于粒子群的具体更新策 优解g.为此，可以导出搜索空间压缩式(13).其中L 略并未发生变动，故此处不做特殊说明.具体设置 为最小搜索空间距离限制，当确定不会发生最优解丢 如下：

张水平等: 基于逐层演化的群体智能算法优化 3. 2 算法基本思想 多分组的粒子群在不同区域的搜索空间内，经过 t 步迭代探索局部最优解后保留大部分适应度高的局部 最优解所在空间，并对其进行压缩; 而其他空间则抛 弃，是该策略的主要思想． ( 1) 首次初始化时将搜索空间 S 划分为多个子空 间 Si，并随机分配给各个独立的粒子群 pi ． 若按照某一规则对所有维度进行划分，则划分的 子空间数随着维度增加而逐渐增加，以简单的对半划 分为例，子空间的个数为 2D ，其中 D 为问题维度． 为 此，在后续实验中，采用的是一种简单的随机划分空间 策略，假设所需划分的子空间数量为 e = ew ·eh，其中 ew 和 eh 为两个自然数，则用公式( 11) 进行划分子空间． 其中，i≤e，m，n≤D，m≠n 为随机数，即随机挑选两个 维度进行多项划分． 若需要划分的维度为其他值，则 可以适当调整即可． BUi = b·u ［yp］，yp≠m，n = 1，ym = 「i / eh ? ew ， yn = mod ( i，eh ) + 1 eh ． ( 11) ( 2) 在浸泡阶段独立的粒子群 pi 进行空间探索， 除粒子越过最初的搜索空间 S 外，不对各子空间进行 越界处理． ( 3) 清洗过程则仅仅保留寻优效果较好的粒子群 组及其周 围 空 间 ( 已 压 缩) ，而 其 他 搜 索 空 间 则 被 丢弃． ( 4) 压缩过程将( 3) 所得空间进行压缩，保存新的 空间大小． ( 5) 再次初始化并不需要将剩余的空间再次划分 为多个子空间，而是将被淘汰的群体中的粒子分配到 其他群组中去． 除首次初始化外，整个空间中的群组 数量是随清洗次数递减的． 如此直至最后输出． 为实现这一设想，需要进行下列设置: ( 1) 粒子群组的递减策略: 保留比例 α = 0. 7 ，该 值不固定． 保留机制采用 best-first 原则，保留最终适应度较 高的一部分粒子群组． 每次淘汰群组数量由下式计算 可得， Ｒ* = max ( 1，Ｒ·α) ． ( 12) 式中，Ｒ 为群组数量． 通过向上取整保证至少存在一 组粒子群在进行寻优探索． ( 2) 搜索空间压缩策略: 压缩比例 β = 0. 5，可根据 清洗次数而定． 由前文已然得出结论，更小的搜索空间可以提供 更为精确的解，且算法收敛时粒子依附于当前已知最 优解 g． 为此，可以导出搜索空间压缩式( 13) ． 其中 L 为最小搜索空间距离限制，当确定不会发生最优解丢 弃情况时，可以设为零，abs( ) 为绝对值函数． b* l = g － max ［abs( g － bl )·β，L］， b* u = g + max ［abs( g － bu { )·β，L］． ( 13) ( 3) 再次初始化． 再次初始化时，可以将被淘汰群体中的粒子加入 保留群组中，进一步提升解精度; 同样也可以直接放弃 这部分粒子，从而提升算法的效率． 如文献中提出的 策略一致，每次再初始化时需要保存必要的社会信息， 在粒子群算法中即保存已知最优解 g，而初始化粒子 则尽可能的进行均匀分配，也可以利用文献中提及的 混沌遍历． 通过再初始化可以有效地提升粒子的“活 力”，增加群内粒子多样性，改善依然趋于收敛的现 状． 是利用搜索空间压缩进行优化的必要手段之一． 其伪代码实现如表 1 所示． 现对 2 维多峰值函数进行实验，并绘制各种群搜 索空间范围，获得如图 6 所示结果，用来展示本文所提 策略的优化细节． 其中，横纵坐标表示 2 维搜索空间 范围，灰色黑边矩形表示一个独立种群的搜索子空间． 随着清洗过程的进行，子空间数量在逐渐减少，同时目 标空间范围也越来越小，即所搜索的空间范围精度提 高． 这一演化过程与之前的设想基本吻合，可用于提 升算法精度． 3. 3 实验设计与结果 选取了 11 个经典基准函数进行测试，在此处不对 表达式进行详细展开［22］，如表 2 所示． 其中 o 为偏移 量，此处设定 o = 10D ，仅作偏移，可以设置为其他值． 函数 f1、f2和 f5及其转换形式均为单峰函数，而其他则 为多峰值函数． 由于逐层演化的策略是将每一个独立的群体智能 算法看作一次浸泡过程而不去改变原有算法的结构流 程，该策略的本质是如何去除在演化过程中无效或者 效果较差的迭代、降低计算资源的浪费． 故此，一个良 好的原算法由于具有良好的寻优能力，则在应用时可 以增加裁剪搜索空间的力度，极大程度上缩小搜索空 间范围，从而获得更高精度的解; 而相对于搜索能力较 差的原算法，则需要注意搜索空间压缩力度，防止出现 丢弃实际最优解的可能． 考虑到这一特点，加之粒子 群算法优化策略众多且未有较为权威的标准，为此，选 取 SPSO［5］不仅可以保证原算法的易实现性． 同时也 由于其常作为优化对照方案，查询效率低于大多数改 进算法，可以作为一个标尺，展现出本文策略的提升效 果． 而在应对更为精确的优化策略时，只需要相应的 调整搜索空间压缩力度便可获得进一步提升． 利用本文所提及的用于种群多样性判别策略对 SPSO［5］进行搭载测试，由于关于粒子群的具体更新策 略并未发生变动，故此处不做特殊说明． 具体 设 置 如下: · 764 ·

·468· 工程科学学报，第39卷，第3期 表1LBL-PS0算法实现 Table 1 LBL-PSO approach 参数T为最大迭代次数：P为初始状态每个种群的粒子个数：D为问题维度：P:为第i(0≤i≤R)组粒子群信息：R为初始化种群数量：d (,)为第i个种群成熟度，对应文中策略1和2：a为种群清洗保留比例B空间压缩因子、y为成熟阈值，小于1的固定常数. 随机初始化每组粒子群的初始信息P: For t=1:T 3 c=0//计数变量，用来记录，当种群到达清洗阅值，则加一 For each Pi 5 fy≤d(p:) 6 c++ 7 End End 9 fy≤所 6 按照式(12)保留优秀种群总数R: 女 依据每个种群内的最优适应度进行排序，保留前R”个种群： 12 按照式(13)计算每个种群对应的搜索空间凸，b]·: 白 根据新的搜索空间对各种群进行位置初始化，但需要保留最优信息，即遗传信息： 14 R=R°：[b,b]=b1,b]·: 尔 Else 16 For each Pa 17 利用原群体智能策略进行粒子位置更新（此处可以为任意具有收敛性的群体智能策略）： 18 End g End 20 t++ 21 End 100n 第1次洁洗 100第2次消 2 [第3次清洗 50 50 0 0 0 -50 -50 1 一10900 -50 0 50 100 -10000 -50 50 100 -1 0 x轴搜索空间范围 轴搜索空间范围 x轴搜索空间范围 0.04[第4次清洗 6[第5次清洗 1.0[第6次清洗 4 0 0.5 0.02 2 0 0 -0.5 -1.0 0 0.05 -1.0 -0.5 00.5 1.0 5 5101520 x轴搜索空问范围 x轴搜索空问范围/103 轴搜索空间范围/10 图6逐层演化效果示意图 Fig.6 Diagram of LBL T=1000;P=10:R=5;a=y=0.7:B=0.5;L= 种群清洗保留比例，可以辅助控制压缩次数，假设实验 1×10,算法总参与计算的粒子数为PR=50:a作为 需要t次以上的压缩，则只需要保证Ra≤1即可：B为

工程科学学报，第 39 卷，第 3 期 表 1 LBL--PSO 算法实现 Table 1 LBL--PSO approach 参数 T 为最大迭代次数; P 为初始状态每个种群的粒子个数; D 为问题维度; pi 为第 i( 0≤i≤Ｒ) 组粒子群信息; Ｒ 为初始化种群数量; d ( pi ) 为第 i 个种群成熟度，对应文中策略 1 和 2; α 为种群清洗保留比例、β 空间压缩因子、γ 为成熟阈值，小于 1 的固定常数． 1 随机初始化每组粒子群的初始信息 Pi ; 2 For t = 1: T 3 c = 0 / /计数变量，用来记录，当种群到达清洗阈值，则加一 4 For each pi 5 If γ≤d( pi ) 6 c + + 7 End 8 End 9 If γ≤ c PＲ 10 按照式( 12) 保留优秀种群总数 Ｒ* ; 11 依据每个种群内的最优适应度进行排序，保留前 Ｒ* 个种群; 12 按照式( 13) 计算每个种群对应的搜索空间［bl，bu］* ; 13 根据新的搜索空间对各种群进行位置初始化，但需要保留最优信息，即遗传信息; 14 Ｒ = Ｒ* ; ［bl，bu］=［bl，bu］* ; 15 Else 16 For each pi 17 利用原群体智能策略进行粒子位置更新( 此处可以为任意具有收敛性的群体智能策略) ; 18 End 19 End 20 t + + 21 End 图 6 逐层演化效果示意图 Fig． 6 Diagram of LBL T = 1000; P = 10; Ｒ = 5; α = γ = 0. 7; β = 0. 5; L = 1 × 10 － 5，算法总参与计算的粒子数为 PＲ = 50; α 作为 种群清洗保留比例，可以辅助控制压缩次数，假设实验 需要 t 次以上的压缩，则只需要保证 Ｒαt ≤1 即可; β 为 · 864 ·

张水平等：基于逐层演化的群体智能算法优化 ·469 表2基准函数表 Table2 Benchmark functions used in this paper 名称 取值范围 极值点 最优解 Sphere [-100,100]D 8=0b fg)=0 Elliptic [-100,100]0 8=0b f(g)=0 f:Rastrigin [-5,5]D 8=00 f(g)=0 f:Ackley [-32,32]D 8=00 fg)=0 fs:Schwefel [-100,100]D 8=0b f八g)=0 fs:Rosenbrock [-100,100]D 8=10 f八g)=0 f方：Sf_Elliptic [-90,110]D g=0+g=10P fg)=0 s:Sft_Rastrigin 5,15]D g=0+g=100 fg)=0 Sft_Ackley [-22,42]D 8=0+g=100 f(g')=0 fio:Sft_Schwefel [-90,110]D 8=0+g=10b f(g)=0 f:Sft_Rosenbrock [-90,110]D g=0+g=11 fg)=0 空间压缩比例，依据预期压缩次数而定，可以进行调 多见.这一现象的存在很好的克服了早熟问题，也可 整：当所有种群中成熟种群数量超过一定比例y后，表 以在图7(e)、7(g)、7(h)和(j)得到体现.但是，正如 示整体成熟即浸泡完成，进行清洗：L仅做阈值使用， 之前所提及的，该策略对空间压缩中心点的定位具有 一般实验过程中不会触及，若最大迭代次数提高，则可 较强的依赖性.如图7()、7()和7(k)所示，可以清 以降低该值 楚的看到，如未能及早地确定最终解所在区域，将会出 图7记录了在权重为固定值，问题维度D=10和 现进化停滞.这是由于经过多次压缩空间使得搜索空 问题维度D=30的条件下，原粒子群算法与分别添加 间被控制在了一个错误的范围内，所探索到的只是在 种群多样性策略1和2作为收敛性判别条件进而构建 这个错误范围内的最优解虽然策略采用了多个群组 的逐层演化系统（图例中10和30为纬度，S1和S2对 的并行筛选策略，但由于初始粒子设置较少，所以无法 应策略1和策略2)，各独立进行100次重复实验，取 很好地完成搜索工作.但相较于原算法还是具有提 平均值获得的收敛曲线，其中，横轴为迭代次数，和纵 升的. 轴为最优解取对数后的值.为了验证实验的公平性， 此外，还采用相同的办法分别对采用的其他3种 标准粒子群算法和逐层演化策略搭载后的粒子群算法 权重策略即随机权值、线性权重和非线性权重也进行 使用了相同数量的粒子，虽然这些粒子会分布到几个 了仿真实验.通过图8可以进一步证明：当算法初期 可以并行的独立种群中去，在一定程度上影响了改进 寻优效果较好时，改进后的算法具有较强的进化能力. 后算法在初期的寻优效果，但也证实了改进策略的有 且不易出现早熟现象.表3中记录的是在问题维度等 效性. 于10时，100次实验解的相关数值特征.从表3的方 以图7(a)为例，可以看出无论是在10维或者30 差项可以看出，改进效果对最终结果的稳定性（方差） 维问题的处理时，逐层演化策略都能对结果的最终精 提升有较大帮助，且策略2的效果在大多数情况下要 度有一定提升.然而，这一策略最主要的提升还是对 优于策略1.同样，在均值方面也处于领先地位.进而 存在于传统粒子群算法中早熟问题的处理.可以看出 在表3中的最大和最小值也可以看出逐层演化策略对 两种不同的多样性判别标准所带来的曲线虽有一定的 算法的具体改进.尤其是在。和：中的提升效果是十 差异，但却都未出现停滞进化的现象.同样的情况也 分显著的.逐层演化策略的两种策略都能处于较好的 可以在图7(b)中得到体现.而在7(c)中则可以清楚 保证对最终解的寻找，但结合图7()和图7(k)可以 的发现在10维问题求解的改进曲线上，存在明显的精 发现，最终收敛曲线的效果不足是由于算法不能稳定 度提升过程.这一现象的产生原因是当算法在一段时 对该函数进行求解造成的 间内没有获得新的最优解，则大多数个体由于进化策 表4记录了维度为30的时候，固定权重进行100 略的影响，必将收敛于最优解附近，从而达到种群多样 次独立重复实验的数值特征.相对于10维问题的求 新判断的阈值，进而触发空间压缩策略 解来说，可以在表4中的方差一项清楚看出，求解效果 在图7()中同样可以发现曲线存在平缓后出现 的稳定性出现了较大的下滑.但算法的改进效果依然 快速下滑的情况，这在其他的粒子群改进策略中并不 十分明显.同样可以发现在对函数∫。和∫，进行求解时

张水平等: 基于逐层演化的群体智能算法优化 表 2 基准函数表 Table 2 Benchmark functions used in this paper 名称 取值范围 极值点 最优解 f1 : Sphere ［－ 100，100］D g = 0D f( g) = 0 f2 : Elliptic ［－ 100，100］D g = 0D f( g) = 0 f3 : Ｒastrigin ［－ 5，5］D g = 0D f( g) = 0 f4 : Ackley ［－ 32，32］D g = 0D f( g) = 0 f5 : Schwefel ［－ 100，100］D g = 0D f( g) = 0 f6 : Ｒosenbrock ［－ 100，100］D g = 1D f( g) = 0 f7 : Sft_Elliptic ［－ 90，110］D g* = o + g = 10D f( g* ) = 0 f8 : Sft_Ｒastrigin ［5，15］D g* = o + g = 10D f( g* ) = 0 f9 : Sft_Ackley ［－ 22，42］D g* = o + g = 10D f( g* ) = 0 f10 : Sft_Schwefel ［－ 90，110］D g* = o + g = 10D f( g* ) = 0 f11 : Sft_Ｒosenbrock ［－ 90，110］D g* = o + g = 11D f( g* ) = 0 空间压缩比例，依据预期压缩次数而定，可以进行调 整; 当所有种群中成熟种群数量超过一定比例 γ 后，表 示整体成熟即浸泡完成，进行清洗; L 仅做阈值使用， 一般实验过程中不会触及，若最大迭代次数提高，则可 以降低该值． 图 7 记录了在权重为固定值，问题维度 D = 10 和 问题维度 D = 30 的条件下，原粒子群算法与分别添加 种群多样性策略 1 和 2 作为收敛性判别条件进而构建 的逐层演化系统( 图例中 10 和 30 为纬度，S1 和 S2 对 应策略 1 和策略 2) ，各独立进行 100 次重复实验，取 平均值获得的收敛曲线，其中，横轴为迭代次数，和纵 轴为最优解取对数后的值． 为了验证实验的公平性， 标准粒子群算法和逐层演化策略搭载后的粒子群算法 使用了相同数量的粒子，虽然这些粒子会分布到几个 可以并行的独立种群中去，在一定程度上影响了改进 后算法在初期的寻优效果，但也证实了改进策略的有 效性． 以图 7( a) 为例，可以看出无论是在 10 维或者 30 维问题的处理时，逐层演化策略都能对结果的最终精 度有一定提升． 然而，这一策略最主要的提升还是对 存在于传统粒子群算法中早熟问题的处理． 可以看出 两种不同的多样性判别标准所带来的曲线虽有一定的 差异，但却都未出现停滞进化的现象． 同样的情况也 可以在图 7( b) 中得到体现． 而在 7( c) 中则可以清楚 的发现在 10 维问题求解的改进曲线上，存在明显的精 度提升过程． 这一现象的产生原因是当算法在一段时 间内没有获得新的最优解，则大多数个体由于进化策 略的影响，必将收敛于最优解附近，从而达到种群多样 新判断的阈值，进而触发空间压缩策略． 在图 7( d) 中同样可以发现曲线存在平缓后出现 快速下滑的情况，这在其他的粒子群改进策略中并不 多见． 这一现象的存在很好的克服了早熟问题，也可 以在图 7( e) 、7( g) 、7( h) 和( j) 得到体现． 但是，正如 之前所提及的，该策略对空间压缩中心点的定位具有 较强的依赖性． 如图 7( f) 、7( i) 和 7( k) 所示，可以清 楚的看到，如未能及早地确定最终解所在区域，将会出 现进化停滞． 这是由于经过多次压缩空间使得搜索空 间被控制在了一个错误的范围内，所探索到的只是在 这个错误范围内的最优解． 虽然策略采用了多个群组 的并行筛选策略，但由于初始粒子设置较少，所以无法 很好地完成搜索工作． 但相较于原算法还是具有提 升的． 此外，还采用相同的办法分别对采用的其他 3 种 权重策略即随机权值、线性权重和非线性权重也进行 了仿真实验． 通过图 8 可以进一步证明: 当算法初期 寻优效果较好时，改进后的算法具有较强的进化能力． 且不易出现早熟现象． 表 3 中记录的是在问题维度等 于 10 时，100 次实验解的相关数值特征． 从表 3 的方 差项可以看出，改进效果对最终结果的稳定性( 方差) 提升有较大帮助，且策略 2 的效果在大多数情况下要 优于策略 1． 同样，在均值方面也处于领先地位． 进而 在表 3 中的最大和最小值也可以看出逐层演化策略对 算法的具体改进． 尤其是在 f6和 f11中的提升效果是十 分显著的． 逐层演化策略的两种策略都能处于较好的 保证对最终解的寻找，但结合图 7( f) 和图 7( k) 可以 发现，最终收敛曲线的效果不足是由于算法不能稳定 对该函数进行求解造成的． 表 4 记录了维度为 30 的时候，固定权重进行 100 次独立重复实验的数值特征． 相对于 10 维问题的求 解来说，可以在表 4 中的方差一项清楚看出，求解效果 的稳定性出现了较大的下滑． 但算法的改进效果依然 十分明显． 同样可以发现在对函数 f6和 f11进行求解时 · 964 ·

·470 工程科学学报，第39卷，第3期 -5 -10 -10 1 -15 500 1000 500 1000 500 1000 迭代次数 迭代次数 迭代次数 (c) tttt+H 0 500 500 1000 500 1000 迭代次数 送代次数 迭代次数 1.0 (h) 0.5 -4 -0.5 -6 500 1000 500 1000 500 1000 迭代次数 迭代次数 迭代次数 6 (k) 0 HHHHHHHHHHHHHH 3 3 0 500 1000 500 1000 迭代次数 迭代次数 P3010-S1PS010 -S2PS010+—PS030 ·—S1S0300—S2PS030 图7固定权重收敛曲线.(a)f:(b):(c)5:(d):(e)65:(06:(g)万：(h):()6:()fo:(k)f1 Fig.7 Convergence performance of the constant weight:(a):(b)f:(c):(d)(e)f:(f)f:(g):(h)fs:(i)f (j)fo: (k)fu 存在着的问题.进一步，表4中的最值则可以更直观 (2)在原算法可以完成基本寻优的条件下，逐层 地体现出算法的该井效果.与之前表3中的不同，在 演化策略可以极大地提升算法效率.由于整个改进措 表4中并未能完成对函数∫6和∫，的求解工作. 施并未对算法主体进行调整，不会造成原点或某个点 的坍缩问题出现.本文策略通过不断对邻域地压缩， 4结论 逐渐搜寻到最优解. (1)压缩搜索空间切实可行，逐层演化的策略为 (3)该策略所带来的提升效果是具有广泛适用性 相同或者不同类型算法之间的协作提供了良好的接 的.由于该策略在具体设计时未涉及任何粒子群算法 口，是一种潜在的杂交算法模型框架. 所特有的演化策略，而是尽可能地考虑整个群体智能

工程科学学报，第 39 卷，第 3 期 图 7 固定权重收敛曲线 . ( a) f1 ; ( b) f2 ; ( c) f3 ; ( d) f4 ; ( e) f5 ; ( f) f6 ; ( g) f7 ; ( h) f8 ; ( i) f9 ; ( j) f10 ; ( k) f11 Fig． 7 Convergence performance of the constant weight: ( a) f1 ; ( b) f2 ; ( c) f3 ; ( d) f4 ; ( e) f5 ; ( f) f6 ; ( g) f7 ; ( h) f8 ; ( i) f9 ; ( j) f10 ; ( k) f11 存在着的问题． 进一步，表 4 中的最值则可以更直观 地体现出算法的该井效果． 与之前表 3 中的不同，在 表 4 中并未能完成对函数 f6和 f11的求解工作． 4 结论 ( 1) 压缩搜索空间切实可行，逐层演化的策略为 相同或者不同类型算法之间的协作提供了良好的接 口，是一种潜在的杂交算法模型框架． ( 2) 在原算法可以完成基本寻优的条件下，逐层 演化策略可以极大地提升算法效率． 由于整个改进措 施并未对算法主体进行调整，不会造成原点或某个点 的坍缩问题出现． 本文策略通过不断对邻域地压缩， 逐渐搜寻到最优解． ( 3) 该策略所带来的提升效果是具有广泛适用性 的． 由于该策略在具体设计时未涉及任何粒子群算法 所特有的演化策略，而是尽可能地考虑整个群体智能 · 074 ·

张水平等：基于逐层演化的群体智能算法优化 ·471 a b -15 -2 200 400600 8001000 200 40m600 8001000 2004006008001000 迭代次数 迭代次数 迭代次数 (d) e 0 0 -2 -4 -a 0 2004006008001000 0 2004006008001000 迭代次数 迭代次数 PS010 SI PSO_10 S2 PSO 10 PS030 +-S1PS030 9-S2PS030 图8不同权重策略下的收敛曲线.(a)随机权重下的f:(b)随机权重下的6：(c)线性权重下的：(d)线性权重下的：(e)非线 性权重下的万 Fig.8 Convergence performance of different weights:(a)f with random-weight:(b)with random-weight:(e)f with linear-weight:(d) with linear-weight:(e)f with nonlinear-weight 表3固定权重实验数据分析(10维) Table 3 Analysis of obtaining solutions under constant weight (D-10) 方差 均值 函数名 标准粒子群 策略1 策略2 标准粒子群 策略1 策略2 h 1.1282 6.0308×10-9 2.7901×10-14 1.0086 1.3991×10-9 8.3702×10-5 五 0.78058 1.4674×10-9 6.048×10-4 0.76403 4.0682×10-0 1.1099×10-14 5 1.3381 7.8044×10-4 7.1379×10-4 0.42132 9.999e-05 7.138×10-5 6 0.57477 0.31842 0.12189 0.78178 0.095221 0.023389 5 2.0476 2.6102×10-3 4.5881×10-3 1.9656 0.0012553 0.00085644 56 161.0897 8.0314 3.5044 100.6025 5.0168 4.8764 f行 0.85682 7.3719×10-6 2.4297×10-7 0.81468 1.3112×10-6 6.0403×10-8 后 1.3647 0.13995 0.4639 0.47642 0.020272 0.079874 6 0.60317 0.62451 0.52572 0.90764 0.37308 0.25052 fio 2.2414 0.021445 0.010979 2.2676 0.010439 0.0067982 110.1334 4.9742 14.8816 101.1201 5.6683 8.4738 最小值 最大值 函数名 标准粒子群 策略1 策略2 标准粒子群 策略1 策略2 斤 0.02147 8.8226×10-16 1.2554×10-7 7.2891 5.0411×10-8 2.0414×10-13 五 0.037832 1.1148×10-5 1.3055×10-n 3.8588 7.978×10-9 5.9928×10-3 fs 0.00012295 5.6843×10-14 0 10.0061 0.0076218 0.0071379 0.072415 5.0097x10-9 1.4619×10-9 2.6143 2.0137 1.1779 5 0.011101 2.5613×10-8 2.5145×10-2 11.255 0.018989 0.003329 fo 8.4583 1.5749×10-6 4.8059×10-6 1437.9891 75.8412 9.0918 f行 0.027766 2.0124×10-14 3.9477×10-5 5.0973 6.5277×10-5 2.3163×10-6 /s 0.00098887 9.0381×10-10 2.9715x10-1 10.0468 0.995 0.9995 6 0.018175 3.9303×10-6 2.2614×10-6 2.417 2.0133 1.6464 0.052696 1.9219×105 1.1726×10-5 11.8583 0.12581 0.053114 3.7844 1.05×10-6 9.2184×10-6 575.4213 39.1231 81.8209

张水平等: 基于逐层演化的群体智能算法优化 图 8 不同权重策略下的收敛曲线 . ( a) 随机权重下的 f1 ; ( b) 随机权重下的 f3 ; ( c) 线性权重下的 f3 ; ( d) 线性权重下的 f7 ; ( e) 非线 性权重下的 f7 Fig． 8 Convergence performance of different weights: ( a) f1 with random-weight; ( b) f3 with random-weight; ( c) f3 with linear-weight; ( d) f7 with linear-weight; ( e) f7 with nonlinear-weight 表 3 固定权重实验数据分析( 10 维) Table 3 Analysis of obtaining solutions under constant weight ( D--10) 函数名 方差 均值 标准粒子群 策略 1 策略 2 标准粒子群 策略 1 策略 2 f1 1. 1282 6. 0308 × 10 － 9 2. 7901 × 10 － 14 1. 0086 1. 3991 × 10 － 9 8. 3702 × 10 － 15 f2 0. 78058 1. 4674 × 10 － 9 6. 048 × 10 － 14 0. 76403 4. 0682 × 10 － 10 1. 1099 × 10 － 14 f3 1. 3381 7. 8044 × 10 － 4 7. 1379 × 10 － 4 0. 42132 9. 999e － 05 7. 138 × 10 － 5 f4 0. 57477 0. 31842 0. 12189 0. 78178 0. 095221 0. 023389 f5 2. 0476 2. 6102 × 10 － 3 4. 5881 × 10 － 3 1. 9656 0. 0012553 0. 00085644 f6 161. 0897 8. 0314 3. 5044 100. 6025 5. 0168 4. 8764 f7 0. 85682 7. 3719 × 10 － 6 2. 4297 × 10 － 7 0. 81468 1. 3112 × 10 － 6 6. 0403 × 10 － 8 f8 1. 3647 0. 13995 0. 4639 0. 47642 0. 020272 0. 079874 f9 0. 60317 0. 62451 0. 52572 0. 90764 0. 37308 0. 25052 f10 2. 2414 0. 021445 0. 010979 2. 2676 0. 010439 0. 0067982 f11 110. 1334 4. 9742 14. 8816 101. 1201 5. 6683 8. 4738 函数名 最小值 最大值 标准粒子群 策略 1 策略 2 标准粒子群 策略 1 策略 2 f1 0. 02147 8. 8226 × 10 － 16 1. 2554 × 10 － 17 7. 2891 5. 0411 × 10 － 8 2. 0414 × 10 － 13 f2 0. 037832 1. 1148 × 10 － 15 1. 3055 × 10 － 17 3. 8588 7. 978 × 10 － 9 5. 9928 × 10 － 13 f3 0. 00012295 5. 6843 × 10 － 14 0 10. 0061 0. 0076218 0. 0071379 f4 0. 072415 5. 0097 × 10 － 9 1. 4619 × 10 － 9 2. 6143 2. 0137 1. 1779 f5 0. 011101 2. 5613 × 10 － 8 2. 5145 × 10 － 12 11. 255 0. 018989 0. 003329 f6 8. 4583 1. 5749 × 10 － 6 4. 8059 × 10 － 6 1437. 9891 75. 8412 9. 0918 f7 0. 027766 2. 0124 × 10 － 14 3. 9477 × 10 － 15 5. 0973 6. 5277 × 10 － 5 2. 3163 × 10 － 6 f8 0. 00098887 9. 0381 × 10 － 10 2. 9715 × 10 － 11 10. 0468 0. 995 0. 9995 f9 0. 018175 3. 9303 × 10 － 6 2. 2614 × 10 － 6 2. 417 2. 0133 1. 6464 f10 0. 052696 1. 9219 × 10 － 5 1. 1726 × 10 － 5 11. 8583 0. 12581 0. 053114 f11 3. 7844 1. 05 × 10 － 6 9. 2184 × 10 － 6 575. 4213 39. 1231 81. 8209 · 174 ·