多目标进化算法.ppt

《多目标进化算法.ppt》由会员分享，可在线阅读，更多相关《多目标进化算法.ppt（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、郑金华多目标进化算法简介 多目标进化算法历史1967年Rosenberg就建议采用基于进化的搜索来处理多目标优化问题。1984年，David Schaffer首次在机器学习中实现了向量评估遗传算法。1989年David Goldberg在其著作Genetic algorithms for search,optimization,and machine learning中，提出了用进化算法实现多目标的优化技术。从2001年以来，每二年召开一次有关多目标进化的国际会议(EMO：evolutionary multi-criterion optimization)国际刊物“IEEE Transacti

2、ons on Evolutionary Computation”(1997年创刊)Evolutionary Computation(1993年创刊)Genetic Programming and Evolvable Machines(1999年)基本概念进化算法(evolutionary algorithm,EA)得到了非常广泛应用。现实中，一般对多个目标同时优化，往往优化的多个目标之间是相互冲突。如：企业生产中，产品质量与生产成本的关系。为达到总目标的最优化，对各子目标进行折衷，出现了多目标进化算法(multi-objective EA,MOEA)。一般描述给定决策向量，它满足下列约束：设有

3、r个优化目标，且这r个优化目标是相互冲突的，优化目标可表示为：寻求 ，使 在满足约束(1)和(2)的同时达到最优。例子决策变量x,满足约束条件：-3x 3设有2个优化目标：f(x)=(f1(x),f2(x),其中 f1=x2 f2=(x-2)2求解x*,使得f(x*)同时达到最小。值空间分布图X f1f2-3.000 9.000 25.000-2.900 8.41024.010-2.800 7.84023.040-2.700 7.29022.090-2.600 6.76021.160-2.500 6.25020.250-2.400 5.76019.3602.000 4.0000.0002.10

4、0 4.4100.0102.200 4.8400.0402.300 5.2900.0902.400 5.7600.1602.500 6.2500.2502.600 6.7600.3602.700 7.2900.4902.800 7.8400.6402.900 8.4100.810.Pareto最优解基本定义多目标优化的最优解称为Pareto最优解。(1896年 Vilfredo Pareto）定义1：给定一个多目标优化问题 ，它的最优解x*定义为：(3)其中：(4)这里为满足式(1)和式(2)的可行解集，即：我们称为决策变量空间(简称决策空间)，向量函数 将 映射到集合 ，是目标函数空间(称目

5、标空间)。决策空间和目标空间X决策空间-3-2.92.93f1目标空间98.418.419f2目标空间2524.010.811定义2：给定一个多目标优化问题 ，称 是最优解(即Pareto optimal solution)，若 ，满足下列条件：或者 (5)或至少存在一个 ，I=1，2，r,使：(6)其中满足式(1)和式(2)的可行解集，即：定义3：给定一个多目标优化问题 ，若 ，且不存在其它的 使得：成立，且其中至少一个是严格不等式，则称X*是 的Pareto最优解。Pareto最优解X f1f20040.10.013.610.20.043.240.30.092.890.40.162.560

6、.50.252.250.60.361.960.70.491.690.80.641.440.90.811.211111.11.210.811.21.440.641.31.690.491.41.960.361.52.250.251.62.560.161.72.890.091.83.240.041.93.610.01240定义4：给定一个多目标优化问题 ，设如果 ，则称 比 优越；如果 ，则称 比 更优越；定义 ：若X*比更优越的 不存在，则称X*为弱Pareto最优解。若X*比任何 都优越，则称X*为完全Pareto最优解。若比X*优越的 不存在，则称X*为强Pareto最优解。定义5：给定一个多

7、目标优化问题 ，它的最优解集定义为：多目标进化算法的优化过程是，针对每一代进化群体，寻找出其当前最优个体(即当前最优解)，称一个进化群体的当前最优解为非支配解(non-dominated solution)，或称为非劣解(non-inferior solution)；所有非支配解的集合称之为当前进化群体的非支配集(NDS：non-dominated solutions)，并使非支配集NDS不断逼近真正的最优解集，最终达到最优，即使NDSet*X*，NDSet*为算法运行结束时所求得的非支配集。Pareto最优边界定义6：给定一个多目标优化问题 和它的最优解集X*，它的Pareto最优边界定义为

8、：区别：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，而在第二个目

9、标上又有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

10、relation)。定义定义9(目标空间中的支配关系目标空间中的支配关系)设 和 是目标空间中的两个向量，称U支配V(表示为 )，当且仅当：且 ，使 。据定义9，我们便可以得出结论：(2,6)支配(3,8)，(2,6)和(3,5)之间互相不支配。区别：决策空间支配关系，目标空间支配关系多目标进化算法为了便于理解，我们这里给出一类基于Pareto的多目标进化算法的一般流程，首先产生一个初始种群P，接着选择某个进化算法(如遗传算法)对P执行进化操作(如交叉、变异和选择)，得到新的进化群体R。然后采用某种策略构造PR的非支配集Nset，一般情况下在设计算法时已设置了非支配集的大小(如N)，若当前非支

11、配集Nset的大小大于或小于N时，需要按照某种策略对Nset进行调整，调整时一方面使Nset满足大小要求，同时也必须使Nset满足分布性要求。之后判断是否满足终止条件，若满足终止条件则结束，否则将Nset中个体复制到P中并继续下一轮进化。在MOEA中，保留上一代非支配集，并使之参入新一代的多目标进化操作是非常重要的，这类似于进化算法中保留上一代的最优个体，从而使新一代的非支配集不比上一代差，这也是算法收敛的必要条件。这样，一代一代的进化下去，进化群体的非支配集不断地逼近真正的最优边界(true pareto optimal front)，最终得到满意的解集(不一定是最优解集)。MOEA分类按选

12、择机制的不同(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)进一步研究更一般的，更通用的，

13、更接近于自然进化的更一般的，更通用的，更接近于自然进化的MOEA模型模型 基于进化环境的多目标进化模型基于进化环境的多目标进化模型。MOEA在有限时间内的收敛性在有限时间内的收敛性。构造多目标最优解集的最少时间复杂度构造多目标最优解集的最少时间复杂度。进化过程中，个体循环地进入归档集问题进化过程中，个体循环地进入归档集问题。MOEA在不同参数时的比较研究在不同参数时的比较研究。MOEA进化过程中，非支配集变化规律的研究进化过程中，非支配集变化规律的研究。MOEA运行的统一框架。运行的统一框架。不确定多目标优化问题不确定多目标优化问题。NSGA_II1993年 Deb提出NSGA（The Non

14、-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进行分类排序的目的是为了将其划分成若干个满足上述三个性质的互不相交的子群体，分类排序

15、依据个体之间的支配关系来进行。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 qspnq=nq 1;if(nq=0)then H=H q end for p i=i+1;Pi=H;end for while end fo

16、r 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=so

17、rt(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/初始时随机产生一个初始群体P0，Q0make-new-pop(P0),t=0/Rt=PtQt /将Pt和Qt并入到Rt中 F=fast-nondominated-sort(Rt)/产生所有边界集F=(F1,F2,.)Pt

18、+1=and i=1 /Pt+1赋空集Until(|Pt+1|+|Fi|N)/选择个体到Pt+1中，直至填满Crowding-distance-assignment(Fi)/计算第i层边界集中个体的聚集距离Pt+1=Pt+1Fi /将第i层边界集并入到新群体Pt+1中i=i+1 (end of until)Sort(Fi,)/对第i层边界集建立偏序关系 Pt+1=Pt+1Fi1:(N-|Pt+1|)/在第i层边界集选取个体填满Pt+1 Qt+1make-new-pop(Pt+1)/在Pt+1上执行选择、交叉和变异操作 t=t+1 种群构造示意图SPEA1999年 Zitzler提出SPEA(s

19、trength Pareto evolutionary algorithm)，采用聚类方法降低非支配集大小。产生一个初始群体Pop，同时设置一个空的非支配集NDSet(或称归档集(archive set)；将Pop中的非支配个体复制到NDSet中；删除NDSet中的支配个体；如果NDSet中的个体数目超过约定值，则用聚类方法(clustering procedure)降低NDSet的大小；计算Pop和NDSet中个体的适应度；采用锦标赛选择法从群体Pop和非支配集NDSet中选择个体进入配对库，直至配对库满；对群体Pop执行进化交叉和变异操作；若不满足结束条件则转，否则结束。SPEA中个体的适

20、应度SPEA中个体的适应度又称之为strength，NDSet中个体的适应度定义如下：(10)式(10)中iNDSet，N为群体Pop的大小，ni为个体i在群体Pop中所支配的个体数：nijPop|i dominates j，iNDSet (11)进化群体Pop中个体适应度定义如下：用聚类方法降低非支配集大小(1)初始化聚类集C，使 ，其中i NDSet。(2)若 则转(5)，否则转(3)。(3），计算C1和C2之间的距离d:式中 为两个个体之间的距离，这里为Euclidean距离。(4)将C中距离最小的两个子类C1和C2合并，即，转(2)。(5)在C中，从每个子类中选出一个具有代表性的个体，

21、组成新的非支配集。SPEA2N为进化群体P规模，M为归档集Q(archive set)大小，T为预定的进化代数(1)初始化：产生一个初始群体P0，同时使归档集Q0为空，t0。(2)适应度分配：计算Pt和Qt中所有个体的适应度。(3)环境选择：将Pt和Qt中所有非支配个体保存到Qt+1中。若Qt+1的大小超过M，则利用修剪过程(archive truncation procedure)降低其大小；若Qt+1的大小比M小，则从Pt和Qt中选取支配个体填满Qt+1。(4)结束条件：若tT，或其它终止条件满足，则将Qt+1中的所有非支配个体作为返回结果，保存到NDSet中。(5)配对选择：对Qt+1执

22、行锦标赛选择(binary tournament selection)。(6)进化操作：对Qt+1执行交叉、变异操作，并将结果保存到Qt+1中，t=t+1，转(2)。适应度计算在SPEA2中，计算个体适应度的方法在SPEA的基础上做了很大的改进，SPEA2计算个体适应度的方法为：(13)式(13)中：为个体i到其第k个邻近个体之间的距离。为此，需要计算个体i到进化群体P和归档集Q中其它所有个体之间的距离，并按增序排列。环境选择环境选择时，首先选择适应度值小于1的个体进入归档集Q中，即：(14)此时若Qt+1中个体数少于约定值M，即|Qt+1|M，则按下列方法依次选择个体i从Qt+1中删除：(15)直至|Qt+1|=M。在此 表示个体i与归档集Qt+1中第k个个体之距离。也就是说，依次选择距离最近的个体删除之。当有多个个体在与其前l(0lk，0k|Qt+1|)个邻近个体具有相同的最小距离时，而与其第k个邻近个体具有不同的距离时，则选取一个具有最小距离的个体删除。如图所示，为二个目标求最大值的归档集修剪示例，并设归档集的规模M为5，图中删除了三个个体，并标明了删除次序分别为1、2和3。