张水平等：基于逐层演化的群体智能算法优化 ·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 ·