进化算法与混合动力系统优化中的测试与分析成果

1.测试问题、评价标准与参数设置

选用多目标0/1背包问题测试算法性能。考虑目标数目分别为n_T=2、3、4，物品数量分别为n_A=100、150、200、500、800的多目标0/1背包问题。背包a的容量规定为C_a，物品b相对于包a的重量为m_ab，效益值为p_ab，m_ab与p_ab均初始化为区间[10，100]上的随机整数，每个候选解采用长度为l位的二进制编码表示。背包a的容量计算公式为

进化最大代数为8000，按概率替换记忆抗体群中亲和度低的抗体，替换概率P=0.15，交叉概率和变异概率分别为0.8和0.01，交叉时采用单点交叉。种群规模、背包数量和物品规模的取值等参数设置见表3-4。表中，N为进化种群规模，N´为外部种群规模。

表3-4 试验参数设置与实验统计结果

（续）

2.评价准则

采用RG-IEA算法与CSA-SPEA算法结束时所获得的外部种群中非重复的最优解的数目I_RG和I_CSA以及最优解多样度的增量来衡量算法维持种群多样性的能力，最优解多样度的增量的计算公式为

同时采用算法结束时所获得的外部种群中非重复最优解的相对质量R_RG与R_CSA考查解的精度。记Q_CAS与Q_RG分别为CSA-SPEA与RG-IEA所获得的无重复解，则相对质量计算方法为

考虑到判定解质量的好坏可以用该解离目标空间中原点距离的远近来测度，根据在某个层面上全体非劣解到原点的平均距离d测量该层非劣解的平均质量，并根据平均距离的增长趋势衡量算法的收敛速度。

3.测试结果与分析

对随机生成的0/1背包问题独立运行RG-IEA算法（实现了抗体优良片断重用机制）、CSA-SPEA算法（无抗体优良片断重用机制）各20次。20次运行结束后，相对质量、最优解多样度增量的统计结果见表3-4。从表3-4中的数据可知，对测试的所有0/1背包问题，从最优解质量角度分析，采用RG-IEA获得的解，对于n_T=2、3、4的测试问题分别以54%、51%、68%以上的概率优于CSA-SPEA获得的解；n_A=500、800的测试问题，RG-IEA获得的解以99%以上的绝对优势优于CSA-SPEA算法。从所获得的最优解规模的角度来分析，RG-IEA算法所获得的解规模对于2目标的测试问题能够以1.04倍以上的增量大于CSA-SPEA算法所得到的最优解规模；对于3目标的测试问题能够以0.08倍以上的增量大于CSA-SPEA算法所得到的最优解规模；对于4目标的测试问题也能够以0.02倍以上的增量大于CSA-SPEA算法所得到的最优解规模。RG-IEA算法搜索到最优解的规模明显优于CSA-SPEA算法，且最大最优解多样度的增量达到2.02倍。

(www.xing528.com)

图3-10 最优解分布对比图（n=2）

图3-11 最优解分布对比图（n=3）

对于2目标测试问题，当n_A=200、500、800时，各随机抽取一次运行结果，非劣解在目标空间的分布如图3-10所示。观察图3-10的三组图可知，RG-IEA所得最优解形成的曲线均处于CSA-SPEA所得最优解形成的曲线斜上方。对于3目标测试问题，当n_A=200、500、800时，各随机抽取一次运行结果，所得非劣解在目标空间形成的曲面如图3-11所示。观察图3-11两种算法形成的重叠曲面可知，RG-IEA获得的最优解曲面比CSA-SPEA所获得的最优解曲面要大，RG-IEA所获得的非重复Pareto解大多数在CSA-SPEA所得解之上。这些图及表3-4的数据表明：RG-IEA搜索到的Pareto非劣解比CSA-SPEA的Pareto非劣解更多且质量更优。

分别对n_T=2、3、4，n_A=200的问题统计进化过程中平均距离的算术平均值，其变化趋势如图3-12所示。可见，各个趋势线在搜索的初始阶段均有较快的收敛速度，但当趋势线进入平缓阶段之后，RG-IEA所得各个趋势线分布均在CSA-SPEA趋势线之上，这就从统计的角度表明RG-IEA算法在搜索的后期阶段能够生成质量更好的Pareto非劣解，重用抗体优良片断的克隆选择算法的引入有利于增强算法的可持续搜索能力。

针对n_T=3、n_A=200的问题，将其进化过程中非劣解到目标空间原点的距离进行方差统计，方差值随进化代数的变化情况如图3-13所示。可见，RG-IEA对应的曲线处于下方，且随进化代数的增加整个曲线平缓下降而向0趋近；而CSA-SPEA算法所对应的曲线，在进化的全过程曲线的波动都较大，而且最终方差值也较大。

图3-14是针对表3-4中各问题，运用RG-IEA算法与CSA-SPEA算法所获得的外部种群中非重复的最优解的数目而得的箱线图。观察图可知：

1）基于CSA-SPEA算法的数据所得的箱体体积大，而且数据偏向于1/4分点，同时具有比较长的“须”，而基于RG-IEA算法的数据所得的箱体在多个问题上具有较小的体积甚至趋于一条直线。大多数情况下CSA-SPEA算法比RG-IEA算法出现偏离中心值以外的值要多。

2）比较盒式图中矩形盒子的高度，可以清晰地看出CSA-SPEA算法比RG-IEA算法获得的解数量分布更离散。

3）所有问题中CSA-SPEA算法比RG-IEA算法获得的解数量要少。

这表明：RG-IEA算法比CSA-SPEA算法的收敛性要好且稳定性更高，能够获得更多的可选解。

综上可知，抗体优良片断重用机制的实现，有利于提高算法搜索的稳定性与鲁棒性。

图3-12 非劣解到目标空间原点的平均距离增长趋势

图3-13 进化过程中Pareto非劣解方差变化趋势