Page 162 - 《软件学报》2021年第12期

3826 Journal of Software 软件学报 Vol.32, No.12, December 2021

分布在决策空间中范围较大,很容易搜索到不同方向的解,即在不同参考向量上的解,这就使训练集 A 的大小超
过 11d−1,增加了一定的建模时间.
从运行时间上来看,DSAEA 运行速度不亚于目前较为流行的算法.
由此可见,相比对比算法,DSAEA 在限制评估次数的情况下可以更加有效地解决实验选用的测试问题,主
要分析有以下几点.
• 首先,DSAEA 引入参考向量的最小相关解来保持多样性.DSAEA 中,候选解生成算子不是按照支配关
系迭代优化候选解,而是按照多样性,即会出现淘汰非支配解但保留支配解的情况.例如,x 1 支配 x 2 ,但 x 1
所在参考向量已存在最小相关解且优于 x 1 ,而 x 2 所在参考向量不存在相关解,则 x 1 会被淘汰,而 x 2 会被
保留.值得一提的是:由于这里是采用模型评估,而模型评估总是存在一定的误差,所以在模型评估下的
非支配解在真实评估下可能是支配解;反之亦然.此外,按照多样性保留解可以增加探索范围,避免陷入
探索单一方向.因此,DSAEA 中候选解生成算子更有可能找到更多有希望的解,即,候选解生成算子迭
代优化的目标是在模型评估下表现优秀的解以及未探索区域内的解;
• 其次,DSAEA 中的选择算子把解按照周围是否存在活跃参考向量进行划分筛选.一方面,DSAEA 会保
留相比周围参考向量的最小相关解更好的解,以保留在真实评估下可能比现有解更好的解,从而提高
当前解的收敛性;另一方面,DSAEA 会保留周围没有活跃参考向量的解,以对此未探索区域进行探索,
从而提高当前解的多样性.在筛选后,DSAEA 对保留的解进行聚类,选出μ个代表解进行真实评估,进行
批量的真实评估大大提升算法运行速度.这样,DSAEA 的选择算子对最终解的收敛性和多样性会有所
帮助;
• 最后,由于测试问题决策变量数量较大,属于大规模问题,而模型精度有限,所以每次迭代后对训练集的
更新是十分必要的.算法 6 先对所有真实评估过的解,即种群 P,计算其最小相关解加入训练集.若此时
的训练集大小仍小于 11d−1,则在剩下的解中按照参考向量上的解的密度继续选择,优先选择密度小的
参考向量上的最小相关解加入训练集.这样做可以得到在目标空间内分布较为广泛且多样性较好的
训练集,在此基础上,训练的模型会较好地拟合较大的范围,并且随着迭代次数的增加,训练集会更加靠
近真实 PF 区域,模型也就可以更好地拟合真实 PF 附近区域.也就是说,随着迭代的进行,不仅进化算法
会朝着真实 PF 附近区域搜索,而且模型也会朝着真实 PF 附近区域靠拢.
4 总 结

本文提出了基于多样性的代理辅助进化算法(DSAEA)来解决昂贵多目标优化问题.DSAEA 采用 Kriging
模型近似每个目标.候选解生成算子分配解到对应的参考向量来计算最小相关解集,以达到迭代优化候选解的
目的.选择算子筛选出无活跃邻居参考向量的解,以及表现比大多数邻居参考向量的相关解更好的解.然后对筛
选出的解 K-means 聚类,从每个簇中选择一个最好的解进行真实评估.另外,DSAEA 使用一个大小下限为 11d−1
的训练集 A 作为代理模型的训练集,删除价值不大的样本以降低建模时间.实验部分选用大规模 ZDT,DTLZ 测
试问题,与目前流行的 MOEA/D-EGO,K-RVEA 和 ParEGO 算法进行对比实验.结果表明:DSAEA 在大多数选用
的测试问题上,要比以上几个算法表现更好.因此,本文的方法是有效可行的.
在实验中,对于大规模问题来说,决策变量的数量设置较小,但仍有部分测试问题没有很好地收敛.当决策
变量的量变得更大时,搜索和建模压力会随之上升,这对进化算法的选择和建模方法是一个巨大的挑战.另外,
由于随着目标数量的增加,需要更多的解来近似表示 PF,而昂贵问题中真实评估次数十分有限,所以如何用有限
的点来有效地表示 PF,也是一个严峻的挑战.