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

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

规划问题以及文献[23]的 3 个整数规划问题进行了测试,将结果与文献[22]中的遗传算法(GA)、模拟退火算法
(SA)、遗传模拟退火算法(GSA)、混合遗传算法(HGA)和文献[23]中的混沌搜索的混合粒子群算法(CLSPSO)
以及将粒子群优化算法与混沌搜索相结合的其他 6 种混合算法(CLSPSO、CLSPSO1、CLSPSO2、CLSPSO3、
CLSPSO4、CLSPSO5)作了对比.
本实验所选择的测试问题包含多种类别:前两个问题是仅含边界约束的测试算例,后 6 个测试算例含有性
能约束条件.从峰值点的角度来看,这些测试算例的目标函数均含有多个峰值点,其中,问题 1、问题 2、问题 6、
问题 7 具有多个局部最优点,但仅含一个全局最优点.对于其他问题,均存在多个局部最优点,这些局部最优点的
存在很容易“欺骗”算法陷入局部最优,从而这些算例对测试算法跳出局部最优的性能具有重要的参考意义.
4.2.1 参数设置
基于择优策略的 PES 算法对实验的 8 个实验算例均将最大迭代次数设置为 1 000,种群规模 50,分层比例设
为 0.1,0.2,0.3,0.4,由上至下层与层之间的传递比例设为 0.2,0.4,0.6,收缩因子α设为 1,偏向权重 w 设为 0.5.由于
问题规模不同,故初始各问题的各层搜索邻域半径不同.其中,问题 1 设为[1,2,4,6],问题 2 与问题 3 设为[1,2,3,4],
问题 4 设为[1,2,3,6],其他问题均设为[1,2,4,8].问题 2~问题 6 给定的初始全局最优个体分别设为(0,0,0,0,0,0,0),
(1,1,1,1,1,1,1,1,1,1),(0,0,0,0,0,0,0,0,0,0),(20,20,20,20,20),问题 7 的前 20 个元素为 10,后 20 个元素为 20;问题 8
的初始全局最优个体为原点.
4.2.2 实验结果与分析
以下各表中,P b 表示问题的编号,min,max 分别指求问题的最小与最大值.为了更好地与文献中的其他算法
做出对比,表 1 中基于择优策略的 PES 所对应最佳值也是独立算得 5 次取最好所得到的结果,消费时间是指 5
次运行消耗的总时间.
Table 1 Comparison results of five algorithms
表 1 5 种算法比较结果
P b 指标 GA SA GSA HGA 本文算法
最佳值 6 857 059 3 528 572 6 426 002 6 857 179 6 857 179
1(max)
消耗时间 65.7 177.3 152.2 55.4 23.39
最佳值 855.947 4 1 907.9 1 908.2 1 908.2 1 908.2
2(max)
消耗时间 416.6 125.1 315.2 166.4 57.40
最佳值 74 84 84 86 90
3(max)
消耗时间 109.2 47.5 103.6 28.1 33.63
最佳值 1 586.3 1 685.8 1 604.6 1 713.5 1 720.404
4(max)
消耗时间 177.3 80.5 164.2 73.5 52.65
最佳值 − 230 127 285 312
5(max)
消耗时间 − 168.2 204.2 271.8 49.027 6
从表 1 中可以发现:
• 在最优值这个指标上,对于问题 1 与问题 2,本文算法与 HGA 所得结果相同,它们均找到了全局最优
点,而 GA、SA、GSA 都陷入了局部最优;对于问题 3~问题 5,本文算法比其他 4 种算法所得到的结果
要好,说明本文算法比其他算法跳出局部最优的能力要强.
• 在运行时间这个指标上,除了问题 3 以外,其他算法运行 5 次的所消耗的总时间都至少比本文算法出
高出 1 倍.
表 2 是问题 6~问题 8 测试得到的结果,本文算法所对应的也是独立算得 50 次的结果.在对比指标中,若得
到的目标函数值在已知最优值的 0.1%以内,则视为一次成功.“标准差”是 50 次运行的结果的标准差.
从表 2 可以发现:
• 在最佳目标函数值这个指标上:本文算法对 3 个测试问题均能找到目前所知道的全局最优点;而其他
6 种算法却陷入了局部最优,未能找到全局最优点(如问题 8).即便能找到,成功率也不是很高(如问题
7),而本文算法却能达到 100%的成功率.