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

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

⎧ max{0, ( )}, 1gx ≤≤ m
i
px i (11)
() = ⎨
i +
i
⎩ | ( ) |, 1hx m ≤≤ n
i
n
viol ()x = p i (),x i = ∑ 1,...,n (12)
i= 1
viol(x)反映了个体 x 偏离可行解的程度.以此偏离程度作为惩罚的大小,适应度函数 F(x)的定义如下.
⎧ − f ( ), if x x∈ D
Fx (13)
() = ⎨
) viol
(
⎩ FgBest − ( ),x if x∈ D
其中,gBest 是上代群体中最佳个体,D 是可行解区域, D 是不可行解区域.
从以上定义可知:如果 x∈D,则偏离程度为 0,不对它进行惩罚,以目标函数值的相反数作为它的适应度值;
如果 x∈ D ,则以上代中最佳个体 gBest 的适应度值 F(gBest)作为该个体的基础适应度值,以偏离可行解的程度
viol(x)作为惩罚值.对于任意两个个体 x 1 ,x 2 ,如果 x 1 ,x 2 ∈D,则 F(x)越大,个体越优;如果 ,x x ∈ D ,则 viol(x)越小,个
2
1
体越优.如果 x ∈ 1 , Dx ∈ 2 D ,可以分析得知,F(x 1 )并非一定比 F(x 2 )大,从而在依据适应度值选择个体时,就保留了
部分不可行解.由于不可行解的位置有可能非常靠近全局最优解所在的区域,在它们周围进行开采与探索,就能
很快地寻找到最优解.因此,保留一部分的不可行解是有必要的.当然,我们的目的是寻求可行解,因此为了保证
所得的最大适应度的个体是一个可行解,故将 F(gBest)作为不可行解不能逾越的上界.
3.2 初始化种群
标准的 PES 算法所求解问题的决策变量是连续型的,它不能直接应用于求解整数规划问题.因此,本文应用
基于择优策略的 PES 算法在边界约束条件内产生规模为 N 的初始种群 X 0 的规则如下.
X 0 =l+randint(0,u−l) (14)
其中,randint(0,u−l)是在指在区间[0,u−l]内产生含有 n 个随机整数的向量.

3.3 更新种群
k
设 x 是第 k 代种群依据公式(4)划分的第 i 层的任意一个个体,每层的更新由层内探索、层间传递以及确定
i
每层这 3 个步骤完成.
首先,将公式(9)的决策变量转化成整数,则每层个体的探索规则如下.
x i k + 1 = x + k i round {rand R× i k × [ (w pBest − i k x i k ) (1 w+ − )(gBest − k x i k )]} (15)
其中,round{⋅}是一个取整操作.
然后,从上一层的群体中选取一定比例的个体向下一层进行传递,这里按照联赛规模为 2 的随机联赛的规
则选取每一个被传递的个体.
接着,将每一层产生的所有新个体、传递个体和父代个体,按适应度值从大到小所整合在一起,从该群体中
选择相应层数的个数的个体作为该层的个体,每个个体按照保留精英策略的轮盘赌规则进行选择.
最后,将更新后的每层个体整合在一起作为新种群.由于新种群中可能出现相同的个体,为了更好地体现种
群多样性以及更有效率的寻优,这里只保留所有相同个体中的一个,其他个体用公式(14)随机产生的个体进行
替代.找出当前种群中的全局最优个体 gBest 以及所对应的目标函数值 f(gBest).
4 仿真实验

实验工具:Matlab R2016a.实验环境:Windows 10 操作系统,Intel 处理器 1.80GHz,8GB 内存.
4.1 PES探索实验
此实验的目的是通过附录中的仿真问题 [21] 作为实验算例,来验证基于择优协作策略的 PES 算法有着跳出
局部最优、探寻到全局最优的特点.该算例的全局最优解为(0,0),最优函数值为 0.该算例中的目标函数是一个不
可分离的多峰函数,图 2 是它的三维图形,从图中可以发现,由于全局最优与最好的局部最优相距很远,因此搜索
算法往往朝着错误的方向进行收敛,该函数带有一定的欺骗性.用 PES 求解该问题的参数设置为:最大迭代次数