【深度】北京工业大学乔俊飞教授等：一种基于均匀分布策略的NSGAII算法

2019 年 8 月 22 日 中国自动化学会

CAA

智慧起航，共创未来

【导读】基于均匀分布的NSGAII多目标优化算法是指：针对局部搜索类改进型非劣分类遗传算法 (Nondominated sorting genetic algorithm II, NSGAII) 计算过程中种群分布不均的问题, 提出一种基于均匀分布的NSGAII多目标优化算法.

乔俊飞, 李霏, 杨翠丽. 一种基于均匀分布策略的NSGAII算法. 自动化学报, 2019, 45(7): 1325-1334.

大多数的工程和科学应用, 如工业制造、城市运输、污水处理和资本运算等, 几乎每个重要的现实生活中的决策都存在多目标优化问题。这些目标往往是不可比较, 甚至是相互冲突的。因此多目标优化问题 (Multiobjective optimization problem, MOP) 一直是近几年主要的研究课题之一。为了解决该问题, 多目标进化算法 (Multiobjective evolutionary algorithm MOEAs) 已被广泛研究。其中Schaffer提出了向量评估遗传算法 (Vector evaluated genetic algorithm, VEGA), 该算法对单目标遗传算法进行了改进. 但VEGA只能找到Pareto前端的始末端, 产生不了均匀分布的解。为此Carlos等人提出了多目标遗传算法 (Multiobjective gene- tic algorithm, MOGA), 这种算法效率较高, 而且易于实现。但该算法的不足在于如果小生境数目信息是基于目标函数的, 那么两个具有相同目标函数向量的不同个体无法在同一代种群中存在. 为了解决该问题, Deb等提出了非劣分类遗传算法 (Nondominated sorting genetic algorithm, NSGA), 该算法先按解个体的非劣关系进行排序, 再按照共享机制来保持进化的多样性。但是该算法计算效率较低, 计算复杂度大, 且共享参数σ需要预先确定。为了减小算法的计算复杂度, Deb[4] 等提出了改进型非劣分类遗传算(Nondominated sorting genetic algorithm II, NSGAII), 该算法采用非支配排序进行分级, 通过计算拥挤距离选择最优解, 并将其作为精英解保存起来. 但该算法是一种类随机搜索算法, 存在操作次数多收敛速度慢和解分布特性较差的问题。

ZDT2优化效果 ZDT4优化效果

ZDT3优化效果图 ZDT6优化效果

DTLZ7优化效果图 DTLZ2优化效果图

基于以上问题, 本文提出了一种基于均匀分布的NSGAII (NSGAII-UID) 多目标优化算法. 该算法受文献[12]的启发, 将种群映射到目标值对应的超平面上, 并在该平面上聚类. 但是[12]中提出的算法仍然存在种群分布不均的问题, 从而影响了种群的多样性, 为了解决该问题, 本文将映射平面均匀分区. 当对应区间的分布性不满足时, 分布性加强模块激活. 由于种群在迭代的过程中对应区间会出现种群个体不足或缺失的状况, 此时需要在该区间内放入一些个体. 为了解决该问题, 本文将所选聚类子群体中拥挤距离最大的点进行局部搜索, 采用极限优化变异[13]的方法产生新的个体. 实验结果表明, 该方法综合评价指标 (Inverted generational distance, IGD) 值和分布性评价指标 (Spacing, SP) 值均高于其它算法. 因此表明该方法具有较好的种群多样性和分布性, 且收敛速度较快.

由图可视, 对于凹、凸和非连续的多目标函数, NSGAII-UID可以较好地逼近pareto前端且分布较均匀。且具有较好的精度和收敛性。

作者简介