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

工程科学学报，第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=(0<0 (10) ()-小 由此可知，通过压缩搜索空间是可以在一定程度 上提升命中更优解的概率.同时这一改变在保证不会 已知（片）>0，设： 造成最优解丢失的情况下，随着压缩次数增加而提升. 加之上文中的具体实验，可以证明，搜索空间压缩策略 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 ·