一种改进的非支配排序遗传算法
2019-05-27王青松谢兴生周光临
王青松，谢兴生，周光临
(中国科学技术大学 信息科学技术学院，安徽 合肥 230026)
0 引言
在实际生活以及工程应用中，经常要求在给定的资源下，同时满足多个目标最优化，即多目标优化[1]。比如在部署虚拟机时，需要同时满足高利用率、低延迟以及高吞吐量等[2]；在交通信号配时中，需同时使得延误时间最小、通行能力最大以及停车次数最少[3]。对于多目标优化问题，传统的处理方法大多是加权法，即通过对不同的优化目标分配不同的权重，把多目标优化问题转化为单目标优化问题来求解。加权法的缺点主要有两点，一方面权重的设置具有主观性，需要对优化问题有充分的了解；另外一方面，优化目标之间通常不是线性相关的，因此求得的解通常来说不是全局最优解。对于多目标优化问题，由于几乎不存在单个全局最优解，因此通常是求解一系列非支配解[4](Pareto解集)。
非支配排序遗传算法[5](Non-dominated Sorting Genetic Algorithm II，NSGA-II)是DEB K等人提出的一种元启发式算法，由于NSGA-II算法在低维优化问题中表现优良，并且算法实现相对容易，因此被广泛使用。比如李晓青等人[6]针对发电功率，对风力发电子系统和光伏发电子系统一起使用NSGA-II算法进行协调控制，使得风能和太阳能更为合理地得到利用；AHMADI V等人[7]使用NSGA-II算法求解(Software Defined Network,SDN)体系结构中的控制器的部署位置，显著提高了网络的负载均衡能力、可靠性和容错性。然而，NSGA-II算法在求解时更关注解集质量，求出的解集在分布性方面相对较差。针对NSGA-II算法的不足，本文提出了一种改进的非支配排序遗传算法(INSGA-II)。
本文首先扩大了NSGA-II算法初始化种群规模，其目的是提高收敛性，然后为了提高解集的分布性，引入了概率选择算子。同时为了增大算法的搜索空间，提出了混合交叉算子。最后使用公开的多目标测试函数，以世代距离(Generational Distance，GD)、分布性(Δ)和反世代距离(Inverted Generational Distance，IGD)作为性能指标[8]，与NSGA-II算法和改进的多目标粒子群算法[9](Optimized Multi-Objective Particle Swarm Optimization，OMOPSO)算法进行比较。
1 NSGA-II算法相关概念
NSGA-II算法主要有三大核心概念：快速非支配排序、拥挤距离以及精英策略。
1.1 快速非支配排序
快速非支配排序算法根据种群中个体的优劣程度来对种群分层，目的是使得下一步搜索方向往Pareto最优解集靠近。令nt为支配个体t的个体数目，st为被个体t支配的所有个体，则具体步骤如下：
(1)把种群中满足nt=0的所有个体存入到当前非支配集合F1中。
(2)被F1中的个体i支配的个体集合记为Si。遍历集合Si，对于其中的每个个体l，将其支配数nl更新为nl-1，若nl=0，则把个体l保存到新的集合H中。
(3)此时，F1集合为第一级非支配个体集合，里面所有个体的非支配序均相同，而集合H重新作为当前非支配集合，重复上述步骤，直到所有个体均被赋予了非支配序。
1.2 拥挤距离
拥挤距离刻画了种群中个体的分散程度，令Ci为个体i的拥挤距离，则在边缘上的个体的拥挤距离为∞，其余个体的拥挤距离计算公式如下：
(1)
i>cj⟺irank
(2)
式中，irank表示个体i的非支配序。式(2)含义为个体i优于个体j，当且仅当个体i的非支配序小于个体j的非支配序或者个体i的非支配序等于个体j的非支配序且个体i的拥挤距离大于个体j的拥挤距离。
1.3 精英策略
精英策略的目的是避免优秀的Pareto解集丢失。首先将父代种群Pt和子代种群Qt组合成大小为2N的新种群Rt，然后对集合Rt进行快速非支配排序和拥挤距离计算，并按照非支配序从低到高排序，选择个体进入新种群Pt+1中，如果某个相同非支配序集合中的个体全部加入Pt+1超过了种群上限值N，则此时按照拥挤距离从该集合中进行优选，直到种群数量为N。
2 改进的NSGA-II算法
为了提高NSGA-II算法的收敛性和分布性，以获得更多和更好的解，提出以下三种改进策略。
2.1 新的初始化种群
在NSGA-II算法中，初始化种群P0是随机产生的，且种群的大小为N，而子代种群Q0则是基于种群P0经过选择、交叉和变异产生的。算法进行第一次迭代时，可以视为随机搜索。对于随机搜索，显然种群个体越多，找到最优解的概率就越大，但是个体也不能无限增加，否则可能会影响算法的收敛时间。在不影响算法复杂度的前提下，若种群个体为N，初始化种群的个体数目可以设置为1.5N～2N之间，其目的是提高第一轮子代种群Q0的质量，加速整个种群往最优解靠近。
2.2 概率选择算子
选择算子是算法的核心算子之一，作用是从当前种群中选择出优良的个体并用于后续交叉、变异以产生新的子代种群，它决定了当前种群的下一步走向。NSGA-II算法选择算子常采用的策略是二元锦标赛选择，即随机从种群中选择两个个体，让这两个个体互相比较，选择出最优个体，比较的策略是基于个体的非支配序和拥挤距离。由于选择算子对于算法的性能至关重要，因此选择算子的好坏会影响到所求的解集的质量。
NSGA-II的选择算子更关注解的质量，为了让选择算子在保证解的质量前提下提高所求解集的分布性，在原有的选择算子基础之上引入了概率操作。在种群进化初期，以较大的概率拒绝当前选出的最优个体，选择另外的个体，保证了算法初期的种群多样性，在进化后期，由于种群趋向于收敛，因此以较小的概率拒绝当前选出的最优个体，但是仍然保留选择另外个体的可能性。概率操作的计算公式为：
(3)
式中，w为概率选择算子参数，g为进化代数。
2.3 混合交叉算子
基本的NSGA-II算法中对实数编码采用了模拟二进制交叉(Simulated Binary Crossover，SBX)，SBX交叉算子实现起来比较简单，但是移动空间的范围比较小，因此搜索能力相对较弱，容易陷入局部最优解。针对SBX交叉算子存在的缺点，提出了混合交叉算子，即在SBX交叉算子基础上引入高斯分布交叉算子(Normal Distribution Crossover，NDX)，并自适应地调整这两种交叉算子权重。NDX交叉算子相对于SBX交叉算子的优势在于搜索空间更大，因此更容易跳出局部最优[10]。在算法初期，由于种群中的个体不知道最优解位于何处，因此应该加大搜索空间范围，让NDX交叉算子的权重更大。在算法迭代的后期，由于整个种群已经趋向于稳定，大部分个体都在最优Pareto解周围，因此可以缩小搜索空间，此时让SBX交叉算子权重变大，以加速算法收敛。令u为区间(0,1)上均匀分布所产生的随机数，r=|N(0,1)|为高斯分布随机变量的值，则当u≤0.5时，个体在混合交叉算子下的更新公式为：
(4)
当u>0.5时，个体在混合交叉算子下的更新公式为：
(5)
式(5)、(6)中，x1,i和x2,i为混合交叉算子产生子代个体第i个变量的值；M=p1,i+p2,i，N=p1,i-p2,i，p1,i和p2,i为父代个体第i个变量的值；g为当前迭代次数，G为总的迭代次数，ηc为交叉算子参数。
2.4 INSGA-II算法步骤
INSGA-II算法步骤如下：
(1)设置算法参数:种群规模N，初始化种群P0的规模N0=1.5N～2N，迭代次数G，概率选择算子参数w以及混合交叉算子参数ηc。
(2)随机产生N0个个体作为父代种群P0。
(3)当前迭代次数g=0，对父代种群P0进行概率选择、混合交叉和变异操作，生成子代种群Q0。
(4)合并父子代种群Pt和Qt为新种群Rt，对新种群Rt进行快速非支配排序。
(5)使用精英策略，从新种群Rt中选择出N个优良个体作为新的父代种群Pt+1。
(6)对新种群Pt+1进行概率选择、混合交叉和变异操作，生成新子代种群Qt+1。
(7)若当前迭代次数g不小于最大迭代次数G，则算法结束，否则g=g+1，并进入步骤(4)。
3 实验与分析
3.1 测试函数和参数设置
为了评估INSGA-II优化算法的有效性，使用四个公开的标准多目标测试函数来进行测试，分别是ZDT1、ZDT2、ZDT3和ZDT4函数[11]，具体表达式如公式(6)～公式(9)所示。为了公平且合理比较不同的多目标优化算法，种群规模的大小均设置为100，最大迭代次数均设置为1 000；NSGA-II算法和INSGA-II算法的变异算子参数以及交叉算子参数均为20，INSGA-II概率选择算子中的w参数设置为0.01；OMOPSO算法的变异概率为1/d，d为变量个数，存档的大小为100，惯性量权重系数W的值为random(0.1,0.5)；真实Pareto前沿的采样点个数为500。同时为了提高评价结果的稳定性，对每个测试函数使用优化算法重复求解50次，计算不同评价指标的平均值。
(6)
(7)
(8)
(9)
对于三个评价指标，收敛性评价指标GD的计算公式如下：
(10)
式中，di表示算法求解得到的Pareto前沿PF中的个体i和真实Pareto前沿集合的最短距离，值越小，表明解集质量越高。分布性评价指标SP的计算公式为：
(11)
(12)
式中，d(x,y)表示点x与点y之间的距离，IGD值越小，表明所求的最优解集组成的Pareto前沿PF越逼近真实的Pareto前沿PF*，算法的综合性能越好。
3.2 结果和分析
三种优化算法对四个测试函数求解得到的Pareto前沿的局部放大结果如图1～图4所示，其性能指标结果如表1所示。由图1到图4可以看出，INSGA-II算法能比较接近真实的Pareto前沿。从表1中的数据可知，INSGA-II算法在大多数情况下收敛性和分布性比NSGA-II算法要好，在ZDT1和ZDT3测试函数上，INSGA-II算法的GD略低于OMOPSO算法，但是INSGA-II算法的分布性却大大优于OMOPSO算法。相比于OMOPSO算法，INSGA-II算法在保证Pareto解集质量的前提下，同时保证了Pareto解集的分布性。这表明新的初始化种群、概率选择算子以及混合交叉算子有效地改善了NSGA-II算法的分布性和收敛性。
图1 ZDT1函数实验结果局部放大
图2 ZDT2函数实验结果局部放大
图3 ZDT3函数实验结果局部放大
图4 ZDT4函数实验结果局部放大
测试函数性能指标NSGA-IIINSGA-IIOMOPSOGD0.004 3620.001 4820.001 314ZDT1Δ0.555 3040.226 8270.604 015IGD0.048 6540.014 878 80.014 581GD0.006 2240.002 7280.005 436ZDT2Δ0.657 8260.422 9081.038 221IGD0.066 7810.026 2660.086 539GD0.001 4880.001 1510.001 135ZDT3Δ0.787 3830.804 6441.177 877IGD0.023 7010.021 0530.021 770GD0.000 9290.000 2460.000 291ZDT4Δ0.562 7740.231 5800.953 511IGD0.014 5740.003 8100.009 814
4 结论
本文提出了一种改进的非支配排序遗传算法，通过扩大初始化种群规模，来加速算法收敛；对选择算子引入概率操作，提高了种群的多样性；同时为了扩大算法的搜索空间，引入了混合交叉算子。最后，使用公开的多目标基准函数进行测试，并和基本的NSGA-II算法以及OMOPSO算法进行对比，验证了本文提出的INSGA-II算法能获得分布性和收敛性更好的Pareto前沿。未来的工作将考虑使用更复杂的公开测试函数来对INSGA-II算法进行测试，并在交通信号配时优化等实际工程问题中检验INSGA-II算法的性能。
