多目标进化算法——NSGA-II（python实现）

暮水流情

目录前言NSGA-II非支配排序支配关系非支配关系非支配排序算法算法思想算法伪代码伪代码释义Python代码实现过渡1拥挤度距离排序算法思想算法伪代码Python代码实现过渡2二元锦标赛精英选择策略选择交叉变异生成新种群选择交叉变异Python代码实现整体流程图测试函数与结果其他前言  由于NSGA-II是基于遗传算法的，所以在讲解NSGA-II之前，我们先对遗传算法有一些基本的了解——遗传算法经常用于单目标优化问题，所进行操作的基本流程如下通过解的二进制值进行交叉变异产生不同的解依据适应度函数，得到每个解的适应值根据适应值的大小来对当前解集合，进行排序筛选。再对筛选出的个体进行新一轮的交叉变异，循环往复使得解集合越来越逼近真实的优化目标。  NSGA-II所做的其实就是把排序的依据改变——就是“如何评判一个解的优劣”，在传统遗传算法中，使用的是适应度函数值，这也是因为传统遗传算法多用在单目标的优化问题中，使用能够使用这一个指标来判断。下面是遗传算法中一些名词的对应关系：数学概念生物概念当前的解集合当前的种群解集合中的每个解种群中的个体NSGA-II但对于一个多目标优化问题来说，它的最优解不再是一个值，而是在多维空间中的一个pareto前沿：一个最优解的集合。因此对于迭代过程中未到达pareto前沿的解来说，评判其优劣应当从两个方面来入手——收敛性——解靠近pareto前沿的程度（或速度）分布性——当前解集是否尽可能地覆盖到了pareto前沿。所以NSGA-II的作者Deb提出了评价当前解集合优劣的两个指标：非支配排序拥挤度距离排序下面为了方便讲解，我们以双目标的最小化优化问题举例说明，因为这样能够在几何意义上，放在二维平面图中帮助我们去理解。minF(x)={f1(x),f2(x)}Tst.x∈XX⊂R2min\quadF(x)=\{f_1(x),f_2(x)\}^T\\st.\quadx\inX\\\quad\quadX\subset\mathbbR^2minF(x)={f1​(x),f2​(x)}Tst.x∈XX⊂R2非支配排序支配关系  首先，需要了解两个解的支配关系。我们举例来说明，如果两个目标都是最小化目标的话，说明目标函数值越小，越好。则假设给定个体x0x_0x0​，目标函数值F(x0)=(f1(x0),f2(x0))=(1,1)F(x_0)=(f_1(x_0),f_2(x_0))=(1,1)F(x0​)=(f1​(x0​),f2​(x0​))=(1,1)再给定另外的个体x1x_1x1​，目标函数值F(x1)=(f1(x1),f2(x1))=(2,2)F(x_1)=(f_1(x_1),f_2(x_1))=(2,2)F(x1​)=(f1​(x1​),f2​(x1​))=(2,2)  我们可以发现，在两个目标函数方向（objective），x0x_0x0​所求的目标函数值(1,1)(1,1)(1,1)都比x1x_1x1​的目标函数值(2,2)(2,2)(2,2)小，而同时两个优化方向都是最小化。所以x0x_0x0​所得解的效果要要好于x1x_1x1​，即x0x_0x0​支配x1x_1x1​。  同样的，当一个方向上相等，支配关系又另一个方向目标函数值的大小来决定，例如：(1,2)(1,2)(1,2)支配(2,2)(2,2)(2,2)。  如果在二维平面图上用几何意义来理解的话，就是由原点开始向外做同心圆，内侧圆上的点支配外侧圆上的点。（当然仅限于两个目标，且优化方向都是最小化）非支配关系  但是我们会遇到另外一种情况，例如(1,2)(1,2)(1,2)和(2,1)(2,1)(2,1)，显然在一个方向上2>1,但在另一个方向上1v2[i]:return0#但凡有一个位置是v1大于v2的直接返回0,如果相等的话比较下一个目标值return112345678非支配排序算法算法思想  由上，显然支配关系能够作为一个指标来衡量这个解的优劣程度，因此我们利用个体间的支配关系，将现有种群进行分层。最靠近pareto前沿的解它的等级（rank）最高，为第一层。然后依次判断每个个体处在第几层中，给每个个体的rank赋值。几何上来看，类似于画同心圆，看看这个解在第几个同心圆中。然后依据每个个体的rank值来进排序选择。算法伪代码下面是原文作者的伪代码：伪代码释义  这里面需要了解其中几个变量的含义——npn_pnp​：解ppp被几个解所支配，是一个数值（左下部分点的个数）SpS_pSp​：解ppp支配哪些解，是一个解集合（右上部分点的内容）FiF_iFi​：第iii层的解集合（显然同一层内的解互相都是非支配解）prankp_{rank}prank​：解ppp所在层的等级（越小越好）伪代码主要进行了两步：所有个体的npn_pnp​，SpS_pSp​都算出来了，但只有最前沿的个体rank确定下来，该层的所有个体的rank值设为1，再将其放入了F1F_1F1​层中。用F1F_1F1​中个体ppp的SpS_pSp​（里面放着后面的点），取其中每个个体q(∈Sp)q(\inS_p)q(∈Sp​)，该个体每被前一层的p支配过一次，该个体属性nnn的值就减1。则，当该层的ppp都支配过qqq一次后，若np=0n_p=0np​=0。说明qqq就是紧邻该层的下一层，则把qqq放入F2F_2F2​中，个体qqq的属性rank=2重复2.的步骤用于F2F_2F2​，得到F3F_3F3​，…Python代码实现deffast_non_dominated_sort(P):"""非支配排序:paramP:种群P:returnF:F=(F_1,F_2,...)将种群P分为了不同的层，返回值类型是dict，键为层号，值为List类型，存放着该层的个体"""F=defaultdict(list)forpinP:p.S=[]p.n=0forqinP:ifpind2.distanceelseind2else:#如果rank和拥挤度都相同，返回任意一个都可以returnind112345678910111213精英选择策略  首先，在传统的遗传算法中，在某一次迭代中，只有该次迭代的父代参与选择交叉变异，从而产生子代，作为下一次迭代的父代。  而在NSGA-II中，为了保证最优解的不丢失，提高算法的收敛速度，作者提出了“精英选择策略”，即将父代PtP_tPt​和子代QtQ_tQt​种群，合并为一个种群RtR_tRt​，对其整体进行非支配排序和拥挤度距离计算，根据上述方法进行排序和选择作为下一届的父代Pt+1P_{t+1}Pt+1​。父代再通过一般的方法进行选择交叉排序产生子代Qt+1Q_{t+1}Qt+1​。  这里同样也是循环的主流程所在！选择交叉变异生成新种群选择  随机从种群中选择两个个体，让其进行过渡2所说的“二元锦标赛”，获胜的作为父本1；同样操作，再得到一个父本2。之后，为了避免遗传算法中的早熟现象，多增加一步判断，使得父本1和父本2不相同。交叉  对得到的两个父本进行交叉，产生两个子代。这里选择的交叉算子是“模拟二进制交叉（SBX）”变异对于得到的两个子代，其中一个进行变异操作，另一个不变（千万不要两个都变，会引起一种早熟现象——所有的个体都过早的陷于某几个极值而停止变化，具体原因未明，待解决），这里选择的变异算子是“多项式变异”(PM)xj=xj+Δj  Δj={(2μi)1η+1μi非支配排序fast_non_dominated_sort(P)Q=make_new_pop(P,eta,bound_min,bound_max,objective_fun)P_t=P#当前这一届的父代种群Q_t=Q#当前这一届的子代种群forgen_curinrange(generations):R_t=P_t+Q_t#combineparentandoffspringpopulationF=fast_non_dominated_sort(R_t)P_n=[]#即为P_t+1,表示下一届的父代i=1whilelen(P_n)+len(F[i])