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

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

[2]
难问题 ,长期以来一直是受到应用数学、运筹学、管理科学、决策科学、系统科学、经济学等学科关注的前
[3]
沿课题 ,研究整数规划问题对社会的发展有着重大的研究意义.但是,尽管众多学者投身于对整数规划问题的
研究,由于求解整数规划问题的难度远比求解一般规划问题要大,因而至今仍缺乏有效的通用算法.
[4]
[6]
[5]
目前,用于求解整数规划问题的方法 除了传统的分支定界法 、填充函数法 等和经典的群智能优化算
[8]
[7]
法(如遗传算法(genetic algorithm,简称 GA) 、粒子群优化(particle swarm optimization,简称 PSO)算法 、蚁群
[9]
优化(ant colony optimization,简称 ACO)算法 等)之外,近几年来涌现出了大量的新算法.如在 2013 年,吴炅等
人 [10] 采用截断取整的方法,将基本布谷鸟搜索算法用于求解整数规划问题;魏林等人 [11] 采用和声搜索更新种群
策略和个体扰动策略改善了蚁群算法过早收敛的问题,提出了用和声蚁群耦合算法求解整数规划问题;在 2014
年,Fahim 等人 [12] 以变邻域搜索为核心,提出了用混合分散搜索算法求解整数规划问题;在 2015 年,Wu 等人 [13]
采用新的人口初始化技术和动态非线性比例因子提高算法的优化能力,提出了用改进的差分进化算法求解整
数规划问题;谢瑜等人 [14] 采用截断取整的方法,将花授粉算法扩展到求解整数规划问题;在 2016 年,Mohamed 等
人 [15] 将社会蜘蛛算法与 Nelder Mead 方法结合起来,提出了用单纯形社会蜘蛛算法求解整数规划问题;在 2018
年,石礼堂等人 [16] 将滤子方法融合于填充函数法中,提出了用滤子填充函数算法求解整数规划问题等等.这些算
法都经过数值仿真实验证明了对求解整规划问题的性能,但它们仍然存在自身的缺陷.如文献[10]中的算法虽
然具备跳出局部最优的能力,但其需要很大的迭代次数才能实现.文献[11]中的算法虽然改善了和声搜索算法
过早收敛的缺点,但还是没有克服鲁棒性差的特点.因此,研究整数规划问题仍然是一个需要继续探索的工作.
传统的群智能演化算法有着共同的缺点,即未能解决种群内部个体或者种群之间的探索与开采、竞争与协作
的矛盾.在 2018 年,谈庆在其硕士学位论文 [17] 中提出了一种基于金字塔结构的群智能演化策略(swarm
intelligence evolution strategy based on pyramid structure,简称 PES),通过理论分析以及实验仿真,验证了该算法能
够很好地解决上述两大矛盾.但该算法在内部合作上,新产生的个体仅考虑了与旧个体之间的协作关系,而未考
虑与当前种群最优个体以及全局最优个体之间的协作关系,使得算法在收敛速度上较慢.因此,本文提出了基于
择优协作模型的 PES 算法,通过改变算法的内部协作方式来提高算法的收敛速度.此外,PES 算法是针对连续性
函数优化提出的一种群智能算法,当所研究的问题的决策变量是离散型时,该算法就不能直接被用于求解.因
此,本文设计了基于择优协作策略的 PES 算法去求解整数规划问题,拓展了 PES 算法的应用领域.
本文第 1 节给出研究的相关工作,介绍了标准的 PES 算法,对算法的机理作了深入分析.第 2 节介绍基于择
优协作策略的 PES 算法.第 3 节介绍该算法求解整数规划问题的实现过程.第 4 节对所提出的算法进行探索实现
和对比实验,通过实验结果分析算法对求解整数规划的性能.第 5 节总结全文并进行展望.

1 相关工作

1.1 标准的PES算法

标准的 PES 算法是针对函数优化提出的一种群智能演化算法,在文献[17]中,它主要由以下几个公式完成
对全局最优解的探索.
[F′,I]=sort(F) (1)
X′=X[I]=[X 4 ,X 3 ,X 2 ,X 1 ] (2)
∑ 4 i= 1 length (X = length ( )X (3)
)
i
length(X i )<length(X i+1 ),i=1,2,3 (4)
x i k + 1 = x + k i R × i k σ (5)
k
R ≤ R k i+ 1 ,i = 1,2,3 (6)
i
R i k + 1 = R × i 0 α k (7)
x = x i k + 1 + λ (x i k + 1 − x i k ) (8)
公式(1)是依据种群 X 的适应度值 F 的大小进行升序排序,得到排序后的适应度值 F′以及索引 I.把排序后