多目标进化算法专业知识讲座

多目标进化算法历史1967年Rosenberg就建议采用基于进化的搜索来处理多目标优化问题。1984年，DavidSchaffer首次在机器学习中实现了向量评估遗传算法。1989年DavidGoldberg在其著作《Geneticalgorithmsforsearch,optimization,andmachinelearning》中，提出了用进化算法实现多目标的优化技术。从2001年以来，每二年召开一次有关多目标进化的国际会议(EMO：evolutionarymulti-criterionoptimization)国际刊物“IEEETransactionsonEvolutionaryComputation”(1997年创刊)EvolutionaryComputation(1993年创刊)GeneticProgrammingandEvolvableMachines(1999年)基本概念进化算法(evolutionaryalgorithm,EA)得到了非常广泛应用。现实中，一般对多个目标同时优化，往往优化的多个目标之间是相互冲突。如：企业生产中，产品质量与生产成本的关系。为达到总目标的最优化，对各子目标进行折衷，出现了多目标进化算法(multi-objectiveEA,MOEA)。一般描述给定决策向量，它满足下列约束：设有r个优化目标，且这r个优化目标是相互冲突的，优化目标可表示为：寻求，使在满足约束(1)和(2)的同时达到最优。例子决策变量x,满足约束条件：-3≤x≤3设有2个优化目标：f(x)=(f1(x),f2(x)),其中f1=x2f2=(x-2)2求解x*,使得f(x*)同时达到最小。值空间分布图X f1 f2-3.000 9.000 25.000-2.900 8.410 24.010-2.800 7.840 23.040-2.700 7.290 22.090-2.600 6.760 21.160-2.500 6.250 20.250-2.400 5.760 19.3602.000 4.000 0.0002.100 4.410 0.010…………2.200 4.840 0.0402.300 5.290 0.0902.400 5.760 0.1602.500 6.250 0.2502.600 6.760 0.3602.700 7.290 0.4902.800 7.840 0.6402.900 8.410 0.810………..Pareto最优解基本定义多目标优化的最优解称为Pareto最优解。(1896年VilfredoPareto）定义1：给定一个多目标优化问题，它的最优解x*定义为：

(3)其中：(4)这里Ω为满足式(1)和式(2)的可行解集，即：我们称Ω为决策变量空间(简称决策空间)，向量函数将 映射到集合，∏是目标函数空间(称目标空间)。决策空间和目标空间X决策空间-3-2.9…2.93f1目标空间98.41…8.419f2目标空间2524.01…0.811定义2：给定一个多目标优化问题，称 是最优解(即Paretooptimalsolution)，若，满足下列条件：或者(5)或至少存在一个，I={1，2，…r},使：(6)其中Ω满足式(1)和式(2)的可行解集，即：定义3：给定一个多目标优化问题，若，且不存在其它的使得：成立，且其中至少一个是严格不等式，则称X*是的Pareto最优解。Pareto最优解Xf1 f20 0 40.1 0.01 3.610.2 0.04 3.240.3 0.09 2.890.4 0.16 2.560.5 0.25 2.250.6 0.36 1.960.7 0.49 1.690.8 0.64 1.440.9 0.81 1.211 1 11.1 1.21 0.811.2 1.44 0.641.3 1.69 0.491.4 1.96 0.361.5 2.25 0.251.6 2.56 0.161.7 2.89 0.091.8 3.24 0.041.9 3.61 0.012 4 0定义4：给定一个多目标优化问题，设如果，则称比优越；如果，则称比更优越；定义：若X*比更优越的不存在，则称X*为弱Pareto最优解。若X*比任何都优越，则称X*为完全Pareto最优解。若比X*优越的不存在，则称X*为强Pareto最优解。定义5：给定一个多目标优化问题，它的最优解集定义为：多目标进化算法的优化过程是，针对每一代进化群体，寻找出其当前最优个体(即当前最优解)，称一个进化群体的当前最优解为非支配解(non-dominatedsolution)，或称为非劣解(non-inferiorsolution)；所有非支配解的集合称之为当前进化群体的非支配集(NDS：non-dominatedsolutions)，并使非支配集NDS不断逼近真正的最优解集，最终达到最优，即使NDSet*⊆{X*}，NDSet*为算法运行结束时所求得的非支配集。Pareto最优边界定义6：给定一个多目标优化问题和它的最优解集{X*}，它的Pareto最优边界定义为：

区别：Pareto最优解集，Pareto最优边界实心点A、B、C、D、E、F均处在最优边界上，它们都是最优解(Paretopoints),是非支配的(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)。表示为pq，其中“”是支配关系(dominaterelation)。定义9(目标空间中的支配关系)设和是目标空间中的两个向量，称U支配V(表示为)，当且仅当：且，使。据定义9，我们便可以得出结论：(2,6)支配(3,8)，(2,6)和(3,5)之间互相不支配。区别：决策空间支配关系，目标空间支配关系多目标进化算法为了便于理解，我们这里给出一类基于Pareto的多目标进化算法的一般流程，首先产生一个初始种群P，接着选择某个进化算法(如遗传算法)对P执行进化操作(如交叉、变异和选择)，得到新的进化群体R。然后采用某种策略构造P∪R的非支配集Nset，一般情况下在设计算法时已设置了非支配集的大小(如N)，若当前非支配集Nset的大小大于或小于N时，需要按照某种策略对Nset进行调整，调整时一方面使Nset满足大小要求，同时也必须使Nset满足分布性要求。之后判断是否满足终止条件，若满足终止条件则结束，否则将Nset中个体复制到P中并继续下一轮进化。在MOEA中，保留上一代非支配集，并使之参入新一代的多目标进化操作是非常重要的，这类似于进化算法中保留上一代的最优个体，从而使新一代的非支配集不比上一代差，这也是算法收敛的必要条件。这样，一代一代的进化下去，进化群体的非支配集不断地逼近真正的最优边界(trueparetooptimalfront)，最终得到满意的解集(不一定是最优解集)。MOEA分类按选择机制的不同(CoelloCoelloetal.2004)，可以将MOEA分为：聚集函数(aggregatingfunctions)基于群体的方法(population-basedapproaches)基于Pareto的方法(pareto-basedapproaches)按决策方式的不同，CoelloCoello等将多目标进化算法分为三大类(CoelloCoelloetal.2002)：前决策技术(prioritechnique)交互决策技术(progressivetechnique)后决策技术(posterioritechnique)进一步研究更一般的，更通用的，更接近于自然进化的MOEA模型

基于进化环境的多目标进化模型。MOEA在有限时间内的收敛性。构造多目标最优解集的最少时间复杂度。进化过程中，个体循环地进入归档集问题。MOEA在不同参数时的比较研究。MOEA进化过程中，非支配集变化规律的研究。MOEA运行的统一框架。不确定多目标优化问题。……NSGA_II1993年Deb提出NSGA（TheNon-dominatedSortingGeneticAlgorithm）NSGA主要有三个方面的不足：一是构造Pareto最优解集的时间复杂度太高；二是没有最优个体(elitist)保留机制；三是共享参数大小不容易确定。2000年，Deb等在NSGA的基础上，提出了NSGA-II。非支配集构造设群体Pop的规模大小为N，将群体Pop按某种策略进行分类排序为m个子集P1、P2、……、Pm，且满足下列性质：(1)(2)(3)P1P2…Pm，即Pk+1中的个体直接受Pk中个体的支配，(k=1,2,…,m-1)。对群体Pop进行分类排序的目的是为了将其划分成若干个满足上述三个性质的互不相交的子群体，分类排序依据个体之间的支配关系来进行。sort(Pop){foreachp∈Pop//第一部分：计算ni和si{foreachq∈Pop{if(pdominatedq)thensp=sp∪{q}elseif(qdominatedp)thennp=np+1;}endforqif(np=0)thenP1=P1∪{p}}endforpi=1;while(Pi≠φ)//第二部分：求P1、P2、P3、…Pm{H=φ;foreachp∈Pi{foreachq∈spnq=nq–1;if(nq=0)thenH=H∪{q}}endforpi=i+1;Pi=H;}endforwhile}endforsort保持种群多样性在产生新群体时，通常将优秀的同时聚集密度比较小的个体保留并参与下一代进化。聚集密度小的个体其聚集距离反而大，一个个体的聚集距离可以通过计算与其相邻的二个个体在每个子目标上的距离差之和来求取。一般情况，当有r个子目标时个体i的聚集距离为：

P[i]distance=(P[i+1].f1-P[i-1].f1)+(P[i+1].f2-P[i-1].f2)crowding-distance-assignment(P){N=|P|;//N为群体大小

foreachi,P[i]distance=0;//初始化每个个体的聚集距离

foreachobjectivem//针对每个子目标进行如下操作

{P=sort(P,m);//对子目标m的函数值进行排序

fori=2to(N-1)//针对边界点之外的解

P[i]distance=P[i]distance+(P[i+1].m-P[i-1].m)}endforobjectivemP[0]distance=P[N]distance=∞;//给边界点一个最大值以确保每次它们均能入选下一代}Deb的MOEA

Deb’smainloopofNSGA-II//初始时随机产生一个初始群体P0，Q0＝make-new-pop(P0),t=0//{Rt=Pt∪Qt//将Pt和Qt并入到Rt中

F=fast-nondominated-sort(Rt)//产生所有边界集F=(F1,F2,...)Pt+1=фandi=1//Pt+1赋空集

Until(|Pt+1|+|Fi|≤N)//选择个体到Pt+1中，直至填满

Crowding-distance-assignment(Fi)//计算第i层边界集中个体的聚集距离

Pt+1=Pt+1∪Fi//将第i层边界集并入到新群体Pt+1中

i=i+1(endofuntil)Sort(Fi,)//对第i层边界集建立偏序关系

Pt+1=Pt+1∪Fi[1:(N-|Pt+1|)]//在第i层边界集选取个体填满Pt+1

Qt+1＝make-new-pop(Pt+1)//在Pt+1上执行选择、交叉和变异操作

t=t+1}种群构造示意图SPEA1999年Zitzler提出SPEA(strengthParetoevolutionaryalgorithm)，采用聚类方法降低非支配集大小。⑴产生一个初始群体Pop，同时设置一个空的非支配集NDSet(或称归档集(archiveset))；⑵将Pop中的非支配个体复制到NDSet中；⑶删除NDSet中的支配个体；⑷如果NDSet中的个体数目超过约定值，则用聚类方法(clusteringprocedure)降低NDSet的大小；⑸计算Pop和NDSet中个体的适应度；⑹采用锦标赛选择法从群体Pop和非支配集NDSet中选择个体进入配对库，直至配对库满；⑺对群体Pop执行进化交叉和变异操作；⑻若不满足结束条件则转⑵，否则结束。

SPEA中个体的适应度SPEA中个体的适应度又称之为strength，NDSet中个体的适应度定义如下：

(10)式(10)中i∈NDSet，N为群体Pop的大小，ni为个体i在群体Pop中所支配的个体数：ni＝｜｛j∈Pop|idominatesj，i∈NDSet｝｜(11)进化群体Pop中个体适应度定义如下：

用聚类方法降低非支配集大小(1)初始化聚类集C，使，其中iNDSet。(2)若则转(5)，否则转(3)。(3），计算C1和C2之间的距离d:式中为两个个体之间的距离，这里为Euclidean距离。(4)将C中距离最小的两个子类C1和C2合并，即，转(2)。(5)在C中，从每个子类中选出一个具有代表性的个体，组成新的非支配集。SPEA2｛N为进化群体P规模，M为归档集Q(archiveset)大小，T为预定的进化代数｝(1)初始化：产生一个初始群体P0，同时使归档集Q0为空，t＝0。(2)适应度分配：计算Pt和Qt中所有个体的适应度。(3)环境选择：将Pt和Qt中所有非支配个体保存到Qt+1中。若Qt+1的大小超过M，则利用修剪过程(archivetruncationprocedure)降低其大小；若Qt+1的大小比M小，则从Pt和Qt中选取支配个体填满Qt+1。(4)结束条件：若t≥T，或其它终止条件满足，则将Qt+1中的所有非支配个体作为返回结果，保存到NDSet中。(5)配对选择：对Qt+