Page 37 - 《软件学报》2020年第11期

王占占 等:基于择优协作策略的 PES 算法在整数规划问题上的应用 3353

的群体 X′按公式(2)与公式(3)将种群划分为 4 个部分,每一部分的个体数目满足公式(4),即由优秀个体组成的群
体 X 1 的数目最少,由最劣个体组成的群体 X 4 的数目最多.标准的 PES 算法将群体 X 1 称为开采层,X 2 与 X 3 称
k
k
为传递层,X 4 称为探索层.每一层的个体 x 在各自的层内由公式(5)按照不同的搜索邻域 R 完成群体的更新,每
i
i
一层的邻域大小满足公式(6),即开采层在较小的邻域内按[−1,1]之间的随机数σ产生一个搜索步长,重点是完成
种群的开采工作;而探索层则在大的邻域内去挖掘潜在的优秀个体.随着迭代次数 k 的进行,每一代的种群逐
渐靠向全局最优解,因此,每一层的搜索半径 R i k + 1 也自适应地按公式(7)以收缩因子 0<α<1 进行更新,从而提高寻
优效率.在每一层产生新的个体之后,PES 算法将层与层之间进行了协作,即将探索层的优秀个体以及传递层的
优秀个体分别向开采层与探索层传递,被传递的这些个体在接收层内被培养,并将这些个体按公式(8)以加速步
长λ沿着新个体的产生方向进行了加速操作,得到加速后的个体 x.
1.2 PES算法的机理分析
从第 1.1 节的寻优过程可以发现,如图 1 所示,从开采层至探索层,它们的数量、搜索邻域的大小、种群适
应度值的大小自上而下地呈现金字塔形状,每一层内的个体之间通过相互竞争来获得向上一层传递的机会,依
据层与层之间的传递来达到群与群之间的协作交流.整个金字塔模型与一个国家的组成架构非常相似,少数的
优秀个体视为国家的领导层,部分个体视为管理层,大多数个体视为基层.在国家的发展中,个体所处的位置不
同,赋予的职能也就不同:领导层负责宏观调控,做出一些大型决策;管理层负责接收命令以及传递命令;基层负
责进行实现.层与层之间通过信息交互、互相协作来促进国家的发展,层内个体之间一方面通过相互竞争来获
取晋升的目的,另一方面通过相互协作来完成上级的任务.随着国家的逐步发展,个体的特性会因社会环境以及
以往的经验与学习得以改变,社会分工也会因之改变.如果个体业绩优秀,他将成为同层之中的佼佼者,拥有极
大的上升的机会;反之,则有可能不适应所处环境而被淘汰.因此,依据个体的特性,PES 将种群划分为开采层、传
递层 1、传递层 2、探索层这 4 个层次,对不同层的个体赋予不同的职能:开采层主要负责深入挖掘已存在的优
秀个体所在区域;传输层一方面兼并开采与探索的工作,另一方面通过传递操作构建开采层与探索层之间的桥
梁;探索层负责探索发现新的潜在优秀个体所存在的区域.PES 算法通过这种明确的分工解决了开采与探索的
矛盾.

Transfer21 第 1 层:开采层
Transfer32 第 2 层:传递层 1
第 3 层:传递层 2
Transfer43
第 4 层:探索层
Fig.1 PES structure frame diagram [17]
图 1 PES 结构框架图 [17]

对于传统的群智能算法,它们大都忽略了种群个体以及群体之间的竞争与协作的矛盾,如遗传算法的个体
通过杂交将父代优秀基因传递给子代进行更新;粒子群算法的个体依靠全局极值与当局部极值个体对该个体
产生的驱动力进行更新;蚁群算法的个体通过群体产生的信息素来进行分工协作进行更新.这些算法只涉及到
极少个体之间的协作,忽略了群体之间的协作,缺乏信息交换传递.PES 算法运用了层内竞争与层间协作策略解
决了上述矛盾.对于层内竞争而言,层内个体不仅因适者生存的压力不断的改善自身,也会因个体间的晋升机制
而相互竞争,通过单精英轮盘赌策略以及与父代个体的协作完成各层的更新,这种更新策略为算法的收敛性提
供了理论基础.除了内部协作之外,PES 算法还通过层与层之间个体的传递来完成群体间的交流,这种层内竞
争、层间协作的策略大大提升了算法探寻全局最优的能力.

2 基于择优协作策略的 PES 算法

标准的 PES 算法包含两种协作:一种是层与层之间的群体协作,加强了种群间的交流;一种是层内个体与父