3多目标进化算法

郑金华多目标进化算法简介[e-mail]多目标进化算法历史•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)的同时达到最优。()01,2,,(1)igXik()01,2,,(2)ihXil12()((),(),,())(3)rfXfXfXfX****12(,,,)nXxxx*()fX例子•决策变量x,满足约束条件：-3≤x≤3•设有2个优化目标：f(x)=(f1(x),f2(x)),其中•f1=x2•f2=(x-2)2•求解x*,使得f(x*)同时达到最小。值空间分布图•Xf1f2•-3.0009.00025.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年VilfredoPareto）•定义1：给定一个多目标优化问题，它的最优解x*定义为：•(3)•其中：(4)•这里Ω为满足式(1)和式(2)的可行解集，即：•我们称Ω为决策变量空间(简称决策空间)，向量函数将映射到集合，∏是目标函数空间(称目标空间)。()fX*()()XfXfXopt:rf{|()0,()0;(1,2,,;1,2,,)}nijXgXhXikjl()fXnr决策空间和目标空间X决策空间-3-2.9…2.93f1目标空间98.41…8.419f2目标空间2524.01…0.811•定义2：给定一个多目标优化问题，称是最优解(即Paretooptimalsolution)，若，满足下列条件：•或者(5)•或至少存在一个，I={1，2，…r},使：•(6)•其中Ω满足式(1)和式(2)的可行解集，即：()MinfX*XX*(()())iiiIfXfXjI*()()jjfXfX{|()0,()0;(1,2,,;1,2,,)}nijXgXhXikjl•定义3：给定一个多目标优化问题，•若，且不存在其它的使得：•成立，且其中至少一个是严格不等式，•则称X*是的Pareto最优解。()MinfX*X*X**()()(1,2,,)jjfXfXjr，()MinfXPareto最优解•Xf1f2•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最优解。()MinfX12,XX12()()fXfX1X2X12()()fXfX1X2X*XXXX•定义5：给定一个多目标优化问题，它的最优解集定义为：•多目标进化算法的优化过程是，针对每一代进化群体，寻找出其当前最优个体(即当前最优解)，称一个进化群体的当前最优解为非支配解(non-dominatedsolution)，或称为非劣解(non-inferiorsolution)；所有非支配解的集合称之为当前进化群体的非支配集(NDS：non-dominatedsolutions)，并使非支配集NDS不断逼近真正的最优解集，最终达到最优，即使NDSet*⊆{X*}，NDSet*为算法运行结束时所求得的非支配集。()MinfX**''{}{|,()(),(1,2,,)}jjPXXXfXfXjrPareto最优边界•定义6：给定一个多目标优化问题和它的最优解集{X*}，它的Pareto最优边界定义为：••区别：Pareto最优解集，Pareto最优边界()MinfX**12{()((),(),,())|{}}rPFfXfXfXfXXX•实心点A、B、C、D、E、F均处在最优边界上，它们都是最优解(Paretopoints),是非支配的(non-dominated)；空心点G、H、I、J、K、L落在搜索区域内，但不在最优边界上，不是最优解，是被支配的(dominated)，它们直接或间接受最优边界上的最优解支配。f1f2ABCDEFGHIJKL个体之间的支配关系•对两个变量(个体)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)。()(),(1,2,,)kkfpfqkr{1,2,,}lr()()llfpfq•定义9(目标空间中的支配关系)•设和是目标空间中的两个向量，称U支配V(表示为)，当且仅当：且，使。•据定义9，我们便可以得出结论：(2,6)支配(3,8)，(2,6)和(3,5)之间互相不支配。•区别：决策空间支配关系，目标空间支配关系12(,,,)rUuuu12(,,,)rVvvvUV,(1,2,,)kkuvkr{1,2,,}lrlluv多目标进化算法•为了便于理解，我们这里给出一类基于Pareto的多目标进化算法的一般流程，首先产生一个初始种群P，接着选择某个进化算法(如遗传算法)对P执行进化操作(如交叉、变异和选择)，得到新的进化群体R。然后采用某种策略构造P∪R的非支配集Nset，一般情况下在设计算法时已设置了非支配集的大小(如N)，若当前非支配集Nset的大小大于或小于N时，需要按照某种策略对Nset进行调整，调整时一方面使Nset满足大小要求，同时也必须使Nset满足分布性要求。之后判断是否满足终止条件，若满足终止条件则结束，否则将Nset中个体复制到P中并继续下一轮进化。产生初始种群P用EA进化P得新群体R构造P∪R的非支配集Nset调整Nset的规模并使之满足分布性要求满足终止条件P=Nset开始是否输出结果，结束•在MOEA中，保留上一代非支配集，并使之参入新一代的多目标进化操作是非常重要的，这类似于进化算法中保留上一代的最优个体，从而使新一代的非支配集不比上一代差，这也是算法收敛的必要条件。这样，一代一代的进化下去，进化群体的非支配集不断地逼近真正的最优边界(trueparetooptimalfront)，最终得到满意的解集(不一定是最优解集)。MOEA分类•按选择机制的不同(CoelloCoelloetal.2004)，可以将MOEA分为：•聚集函数(aggregatingfunctions)•基于群体的方法(population-basedapproaches)•基于Pareto的方法(pareto-basedapproaches)•按决策方式的不同，CoelloCoello等将多目标进化算法分为三大类(CoelloCoelloetal.2002)：•前决策技术(prioritechnique)•交互决策技术(progressivetechnique)•后决策技术(posterioritechnique)进一步研究•更一般的，更通用的，更接近于自然进化的MOEA模型•基于进化环境的多目标进化模型。•MOEA在有限时间内的收敛性。•构造多目标最优解集的最少时间复杂度。•进化过程中，个体循环地进入归档集问题。•MOEA在不同参数时的比较研究。•MOEA进化过程中，非支配集变化规律的研究。•MOEA运行的统一框架。•不确定多目标优化问题。•……NSGA_II•1993年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进行分类排序的目的是为了将其划分成若干个满足上述三个性质的互不相交的子群体，分类排序依据个体之间的支配关系来进行。12{,,,}mpPPPPPop,{1,2,,}ijijmijPP且•sort(Pop)•{foreachp∈Pop//第一部分：计算ni和si•{foreachq∈Pop•{if(pdominatedq)then•sp=sp∪{q}•elseif(qdominatedp)then•np=np+1;•}endforq•if(np=0)then•P1=P1∪{p}•}endforp•i=1;•while(Pi≠φ