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

3354 Journal of Software 软件学报 Vol.31, No.11, November 2020

代个体之间的协作,虽然父代个体对子代产生新个体有一定的引导作用,但它对产生优秀个体的指导性不强,会
造成算法的收敛速度缓慢,影响算法应用的运行效率.粒子群算法通过与个体极值与全局极值来完成种群的更
新,具有收敛速度快的优点 [18] ,而这种更新规则恰好弥补了 PES 算法的个体间协作的不足.本文把这种思想融于
标准的 PES 算法之中,将通过选择与当前代层内种群的最优个体与整个种群的最优个体的协作来完成每一层
个体的更新,提出了一种基于择优协作策略的 PES 算法,每一层个体的更新规则如下.
x i k + 1 = x + k i rand R× i k × [(w pBest − i k x i k ) (1 w+ − )(gBest − k x k i )] (9)
k
k
其中, x i k + 1 是第 k 代第 i 层产生的新个体, x 是第 i 层的父代个体,rand 是指在[0,1]之间的一个随机数, R 是当前
i
i
k
k
代的搜索半径, pBest 是第 k 代第 i 层的最优个体,gBest 是第 k 代整个种群的最优个体,0<w<1 反映了新个体偏
i
k
k
向个体 pBest 方向探索的大小,1−w 则反映了对 gBest 方向的偏向程度.
i
基于择优协作的策略,可以让父代个体沿着个体极值与全局极值协同产生的合力方向进行搜寻探索,不仅
加强了层内个体间的相互协作,而且建立了各层内的个体与全局最优的个体之间的联系,在层与层之间的协
作、个体间的择优协作的策略之下,加快了 PES 算法的收敛的速度,提高了算法的寻优效率.
因此,基于择优协作策略的 PES 算法不仅继承了标准 PES 算法跳出局部最优的特点 [17] ,还提高了算法收敛
速度.基于择优策略的 PES 算法的操作流程见算法 1.
算法 1. 基于择优协作策略的 PES 算法.
k
Step 1. 初始化参数,设置最大迭代次数 M,种群规模 N,各层初始搜索半径 Ri = 1,2,3,4) 等.
(
i
0
Step 2. 随机产生种群规模为 N 的初始种群 X ,并置迭代次数 k=0.
k
k
k
(
Step 3. 计算种群 X 的适应度值,依据适应度值 F(X )的大小将种群分为 4 个子种群 Xi = 1,2,3,4) ,并记
i
k
k
录当代个体极值 pBest 与全局极值 gBest .
i
k
Step 4. 按公式(9)为第 i(i=1,2,3,4)层的个体 x 产生新个体 x i k + 1 ,并从每一层选择相应数目的个体传递至
i
上一层,依公式(9)完成培养工作,将产生的新个体、传递个体以及父代个体整合在一起,从中选择
k
相应层数的种群数目的个体作为该层的更新群体 X .
i
k
Step 5. 将更新后的每一层群体 X ,整合为第 k 代产生的新种群 X k+1 .
i
k
Step 6. 判断停机条件.当迭代次数达到最大迭代次数 M 时,则输出 gBest ,算法停止;否则,置 k=k+1,并更
k
(
新各层搜索半径 Ri = 1,2,3,4) .
i
3 基于择优协作策略的 PES 算法在整数规划问题上的应用
整数规划的一般形式 [19] 可展开为
min ( )fx ⎫
⎧ gx 0, i = 1,...,m ⎪
( )≤
⎪
i
⎪ hx 0, i = m + 1,...,n ⎪
( ) =
⎪
⎪ ⎪ i ⎬ (10)
x
s.t. l ⎨ ≤≤ u ⎪
⎪ x = ( ,..., ), x ∈ , Z i = 1,...,n ⎪
⎪ x 1 x n i ⎪
l
l
u
u
⎩ l ⎪= ( ,..., ), u = ( ,..., ) ⎪ ⎭
1
n
n
1
其中,g i (x)与 h i (x)所在的不等式称为性能约束条件;l 与 u 是变量的上下界,所在不等式称为边界约束.如果要求的
是目标函数 f(x)的最大值,只需在相同的约束条件下,求−f(x)的最小值即可.
标准的 PES 算法优化的函数的决策变量是连续型的,因而它不能直接用于求解整数规划问题.本文将提出
的基于择优策略的 PES 算法扩展应用到求解整数规划问题上,其设计如下:
3.1 适应度值函数
首先利用罚函数的方法处理约束条件,定义一族罚函数 [20] {p i (x)}.