多目标进化算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,郑金华,多目标进化算法简介,多目标进化算法历史,1967,年,Rosenberg,就建议采用基于进化的搜索来处理多目标优化问题。,1984,年，,David Schaffer,首次在机器学习中实现了向量评估遗传算法。,1989,年,David Goldberg,在其著作,Genetic algorithms for search, optimization, and machine learning,中，提出了用进化算法实现多目标的优化技术。,从,2001,年以来，每二年召开一次有关多目标进化的国际会议,(EMO,：,evolutionary multi-criterion optimization),国际刊物“,IEEE Transactions on Evolutionary Computation”(1997,年创刊,),Evolutionary Computation (1993,年创刊,),Genetic Programming and Evolvable Machines (1999,年,),基本概念,进化算法,(evolutionary algorithm, EA),得到了非常广泛应用。,现实中，一般对多个目标同时优化，往往优化的多个目标之间是相互冲突。,如：企业生产中，产品质量与生产成本的关系。,为达到总目标的最优化，对各子目标进行折衷，出现了多目标进化算法,(multi-objective EA,MOEA),。,一般描述,给定决策向量，它满足下列约束：,设有r个优化目标，且这r个优化目标是相互冲突的，优化目标可表示为：,寻求 ，使 在满足约束(1)和(2)的同时达到最优。,例子,决策变量,x,满足约束条件：,-3x 3,设有,2,个优化目标：,f(x)=(f,1,(x),f,2,(x),其中,f,1,=x,2,f,2,=(x-2),2,求解,x*,使得,f(x*),同时达到最小。,值空间分布图,X f1f2,-3.000 9.000 25.000,-2.9008.41024.010,-2.8007.84023.040,-2.7007.29022.090,-2.6006.76021.160,-2.5006.25020.250,-2.4005.76019.360,2.0004.0000.000,2.1004.4100.010,2.2004.8400.040,2.3005.2900.090,2.4005.7600.160,2.5006.2500.250,2.6006.7600.360,2.7007.2900.490,2.8007.8400.640,2.9008.4100.810,.,Pareto最优解基本定义,多目标优化的最优解称为,Pareto,最优解。,(1896,年,Vilfredo Pareto,）,定义,1,：给定一个多目标优化问题 ，它的最优解,x*,定义为：,(3),其中：,(4),这里,为满足式,(1),和式,(2),的可行解集，即：,我们称,为决策变量空间,(,简称决策空间,),，向量函数 将 映射到集合 ，,是目标函数空间,(,称目标空间,),。,决策空间和目标空间,X,决策空间,-3,-2.9,2.9,3,f1,目标空间,9,8.41,8.41,9,f2,目标空间,25,24.01,0.81,1,定义2：给定一个多目标优化问题 ，称 是最优解(即Pareto optimal solution)， 若 ，满足下列条件：,或者 (5),或至少存在一个 ，I=1，2，r,使：,(6),其中满足式(1)和式(2)的可行解集，即：,定义3：给定一个多目标优化问题 ，,若 ，且不存在其它的 使得：,成立，且其中至少一个是严格不等式，,则称X*是 的Pareto最优解。,Pareto最优解,X f1f2,004,0.10.013.61,0.20.043.24,0.30.092.89,0.40.162.56,0.50.252.25,0.60.361.96,0.70.491.69,0.80.641.44,0.90.811.21,111,1.11.210.81,1.21.440.64,1.31.690.49,1.41.960.36,1.52.250.25,1.62.560.16,1.72.890.09,1.83.240.04,1.93.610.01,240,定义,4,：给定一个多目标优化问题 ，设,如果 ，则称 比 优越；,如果 ，则称 比 更优越；,定义 ：,若,X*,比更优越的 不存在，则称,X*,为弱,Pareto,最优解。,若,X*,比任何 都优越，则称,X*,为完全,Pareto,最优解。,若比,X*,优越的 不存在，则称,X*,为强,Pareto,最优解。,定义,5,：给定一个多目标优化问题 ，它的最优解集定义为：,多目标进化算法的优化过程是，针对每一代进化群体，寻找出其当前最优个体,(,即当前最优解,),，称一个进化群体的当前最优解为非支配解,(non-dominated solution),，或称为非劣解,(non-inferior solution),；所有非支配解的集合称之为当前进化群体的非支配集,(,NDS,：,non-dominated solutions),，并使非支配集,NDS,不断逼近真正的最优解集，最终达到最优，即使,NDSet,*X*,，,NDSet,*,为算法运行结束时所求得的非支配集 。,Pareto最优边界,定义6：给定一个多目标优化问题 和它的最优解集X*，它的Pareto最优边界定义为：,区别：Pareto最优解集，Pareto最优边界,实心点,A,、,B,、,C,、,D,、,E,、,F,均处在最优边界上，它们都是最优解,(Pareto points) ,是非支配的,(non-dominated),；空心点,G,、,H,、,I,、,J,、,K,、,L,落在搜索区域内，但不在最优边界上，不是最优解，是被支配的,(dominated),，它们直接或间接受最优边界上的最优解支配。,个体之间的支配关系,对两个变量,(,个体,)x,和,y,进行比较时，可能存在三种关系：,x,大于,y,，,x,等于,y,，,x,小于,y,。在多目标情况下，由于每个个体有多个属性，比较两个个体之间的关系不能使用简单的大小关系。如两个目标的个体,(2, 6),和,(3, 5),，在第一个目标上有,2,小于,3,，而在第二个目标上又有,6,大于,5,，这种情况下个体,(2, 6),和,(3, 5),之间的关系是什么呢？另一种情况，如个体,(2, 6),和,(3, 8),，它们之间的关系又是什么呢？当目标数大于,2,时，又如何比较不同个体之间的关系呢？,定义,8,(,个体之间的支配关系,),设,p,和,q,是进化群体,Pop,中的任意两个不同的个体，我们称,p,支配,(dominate)q,，则必须满足下列二个条件：,(1),对所有的子目标，,p,不比,q,差,即 ；,(2),至少存在一个子目标，使,p,比,q,好,即 ，使 。,其中,r,为子目标的数量。,此时称,p,为非支配的,(non-dominated),，,q,为被支配的,(dominated),。表示为,p q,，其中“ ”是支配关系,(dominate relation),。,定义,9,(,目标空间中的支配关系,),设 和 是目标空间中的两个向量，称,U,支配,V(,表示为,),，当且仅当： 且 ，使 。,据定义,9,，我们便可以得出结论：,(2, 6),支配,(3, 8),，,(2, 6),和,(3, 5),之间互相不支配。,区别：,决策空间支配关系，目标空间支配关系,多目标进化算法,为了便于理解，我们这里给出一类基于,Pareto,的多目标进化算法的一般流程，首先产生一个初始种群,P,，接着选择某个进化算法,(,如遗传算法,),对,P,执行进化操作,(,如交叉、变异和选择,),，得到新的进化群体,R,。然后采用某种策略构造,PR,的非支配集,Nset,，一般情况下在设计算法时已设置了非支配集的大小,(,如,N),，若当前非支配集,Nset,的大小大于或小于,N,时，需要按照某种策略对,Nset,进行调整，调整时一方面使,Nset,满足大小要求，同时也必须使,Nset,满足分布性要求。之后判断是否满足终止条件，若满足终止条件则结束，否则将,Nset,中个体复制到,P,中并继续下一轮进化 。,在MOEA中，保留上一代非支配集，并使之参入新一代的多目标进化操作是非常重要的，这类似于进化算法中保留上一代的最优个体，从而使新一代的非支配集不比上一代差，这也是算法收敛的必要条件。这样，一代一代的进化下去，进化群体的非支配集不断地逼近真正的最优边界(true pareto optimal front)，最终得到满意的解集(不一定是最优解集)。,MOEA分类,按选择机制的不同(Coello Coello et al. 2004)，可以将MOEA 分为：,聚集函数(aggregating functions),基于群体的方法(population-based approaches),基于Pareto的方法(pareto-based approaches),按决策方式的不同，Coello Coello等将多目标进化算法分为三大类(Coello Coello et al. 2002)：,前决策技术(priori technique),交互决策技术(progressive technique),后决策技术(posteriori technique),进一步研究,更一般的，更通用的，更接近于自然进化的,MOEA,模型,基于进化环境的多目标进化模型,。,MOEA,在有限时间内的收敛性,。,构造多目标最优解集的最少时间复杂度,。,进化过程中，个体循环地进入归档集问题,。,MOEA,在不同参数时的比较研究,。,MOEA,进化过程中，非支配集变化规律的研究,。,MOEA,运行的统一框架。,不确定多目标优化问题,。,NSGA_II,1993年 Deb提出NSGA（The Non-dominated Sorting Genetic Algorithm ）,NSGA主要有三个方面的不足：一是构造Pareto最优解集的时间复杂度太高；二是没有最优个体(elitist)保留机制；三是共享参数大小不容易确定。,2000年，Deb等在NSGA的基础上，提出了NSGA-II。,非支配集构造,设群体,Pop,的规模大小为,N,，将群体,Pop,按某种策略进行分类排序为,m,个子集,P1,、,P2,、,、,Pm,，且满足下列性质：,(1),(2),(3) P1 P2 Pm,，即,Pk+1,中的个体直接受,Pk,中个体的支配，,(k=1,2,m-1),。,对群体,Pop,进行分类排序的目的是为了将其划分成若干个满足上述三个性质的互不相交的子群体，分类排序依据个体之间的支配关系来进行。,sort(Pop), for each pPop /,第一部分：计算,ni,和,si, for each qPop, if (p dominated q) then,sp=sp q ,else if (q dominated p) then,np=np + 1;,end for q,if ( np=0) then,P1=P1 p ,end for p,i=1;,while (Pi) /,第二部分：求,P1,、,P2,、,P3,、,Pm, H=;,for each pPi, for each qsp,nq=nq 1;,if (nq=0) then H=H q ,end for p,i=i + 1;,Pi=H;,end for while,end for sort,保持种群多样性,在产生新群体时，通常将优秀的同时聚集密度比较小的个体保留并参与下一代进化。聚集密度小的个体其聚集距离反而大，一个个体的聚集距离可以通过计算与其相邻的二个个体在每个子目标上的距离差之和来求取。,一般情况，当有,r,个子目标时个体,i,的聚集距离为：,Pidistance=(Pi+1. f1 - Pi-1. f1 )+(Pi+1. f2 - Pi-1. f2 ),crowding-distance-assignment(P), N=|P|; /N,为群体大小,for each i, Pidistance=0; /,初始化每个个体的聚集距离,for each objective m /,针对每个子目标进行如下操作, P=sort(P, m); /,对子目标,m,的函数值进行排序,for i=2 to (N-1) /,针对边界点之外的解,Pidistance= Pidistance+(Pi+1. m - Pi-1. m ),end for objective m,P0distance= PNdistance=; /,给边界点一个最大值以确保每次它们均能入选下一代,Deb 的MOEA,Debs main loop of NSGA-II,/,初始时随机产生一个初始群体,P,0,，,Q,0,make-new-pop(P,0,),t=0/, R,t,=P,t,Q,t,/,将,Pt,和,Qt,并入到,Rt,中,F,=fast-nondominated-sort(R,t,) /,产生所有边界集,F,=(,F,1,F,2,.),P,t+1,=,and i=1 / Pt+1,赋空集,Until (|P,t+1,|+|,F,i|N) /,选择个体到,Pt+1,中，直至填满,Crowding-distance-assignment(,F,i) /,计算第,i,层边界集中个体的聚集距离,P,t+1,=P,t+1,F,i /,将第,i,层边界集并入到新群体,P,t+1,中,i=i+1 (end of until),Sort(,F,i,) /,对第,i,层边界集建立偏序关系,P,t+1,=P,t+1,F,i1: (N-|P,t+1,|) /,在第,i,层边界集选取个体填满,P,t+1,Q,t+1,make-new-pop(P,t+1,) /,在,P,t+1,上执行选择、交叉和变异操作,t=t+1 ,种群构造示意图,SPEA,1999,年,Zitzler,提出,SPEA(strength Pareto evolutionary algorithm),，采用聚类方法降低非支配集大小。,产生一个初始群体,Pop,，同时设置一个空的非支配集,NDSet(,或称归档集,(archive set),；, 将,Pop,中的非支配个体复制到,NDSet,中；, 删除,NDSet,中的支配个体；, 如果,NDSet,中的个体数目超过约定值，则用聚类方法,(clustering procedure),降低,NDSet,的大小；, 计算,Pop,和,NDSet,中个体的适应度；, 采用锦标赛选择法从群体,Pop,和非支配集,NDSet,中选择个体进入配对库，直至配对库满；, 对群体,Pop,执行进化交叉和变异操作；, 若不满足结束条件则转，否则结束。,SPEA中个体的适应度,SPEA,中个体的适应度又称之为,strength,，,NDSet,中个体的适应度定义如下：,(10),式,(10),中,iNDSet,，,N,为群体,Pop,的大小，,ni,为个体,i,在群体,Pop,中所支配的个体数：,ni,jPop| i dominates j,，,iNDSet,(11),进化群体,Pop,中个体适应度定义如下：,用聚类方法降低非支配集大小,(1),初始化聚类集,C,，使 ，其中,i NDSet,。,(2),若 则转,(5),，否则转,(3),。,(3,） ，计算,C,1,和,C,2,之间的距离,d:,式中 为两个个体之间的距离，这里为,Euclidean,距离。,(4),将,C,中距离最小的两个子类,C,1,和,C,2,合并，即，,转,(2),。,(5),在,C,中，从每个子类中选出一个具有代表性的个体，组成新的非支配集。,SPEA2,N,为进化群体,P,规模，,M,为归档集,Q(archive set),大小，,T,为预定的进化代数,(1),初始化：产生一个初始群体,P,0,，同时使归档集,Q,0,为空，,t,0,。,(2),适应度分配：计算,P,t,和,Q,t,中所有个体的适应度。,(3),环境选择：将,P,t,和,Q,t,中所有非支配个体保存到,Q,t+1,中。若,Q,t+1,的大小超过,M,，则利用修剪过程,(archive truncation procedure),降低其大小；若,Q,t+1,的大小比,M,小，则从,P,t,和,Q,t,中选取支配个体填满,Q,t+1,。,(4),结束条件：若,tT,，或其它终止条件满足，则将,Q,t+1,中的所有非支配个体作为返回结果，保存到,NDSet,中。,(5),配对选择：对,Q,t+1,执行锦标赛选择,(binary tournament selection),。,(6),进化操作：对,Q,t+1,执行交叉、变异操作，并将结果保存到,Q,t+1,中，,t=t+1,，转,(2),。,适应度计算,在,SPEA2,中，计算个体适应度的方法在,SPEA,的基础上做了很大的改进，,SPEA2,计算个体适应度的方法为：,(13),式,(13),中：,为个体,i,到其第,k,个邻近个体之间的距离。为此，需要计算个体,i,到进化群体,P,和归档集,Q,中其它所有个体之间的距离，并按增序排列。,环境选择,环境选择时，首先选择适应度值小于,1,的个体进入归档集,Q,中，即：,(14),此时若,Q,t+1,中个体数少于约定值,M,，即,|,Q,t+1,|M,，则按下列方法依次选择个体,i,从,Q,t+1,中删除：,(15),直至,|,Q,t+1,|=M,。,在此 表示个体,i,与归档集,Q,t+1,中第,k,个个体之距离。也就是说，依次选择距离最近的个体删除之。当有多个个体在与其前,l,(0,l,k,，,0,k,|Q,t+1,|),个邻近个体具有相同的最小距离时，而与其第,k,个邻近个体具有不同的距离时，则选取一个具有最小距离的个体删除。如图所示，为二个目标求最大值的归档集修剪示例，并设归档集的规模,M,为,5,，图中删除了三个个体，并标明了删除次序分别为,1,、,2,和,3,。,