下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、郑金华,多目标进化算法简介,多目标进化算法历史,1967年Rosenberg就建议采用基于进化的搜索来处理多目标优化问题。 1984年,David Schaffer首次在机器学习中实现了向量评估遗传算法。 1989年David Goldberg在其著作Genetic algorithms for search, optimization, and machine learning中,提出了用进化算法实现多目标的优化技术。 从2001年以来,每二年召开一次有关多目标进化的国际会议(EMO:evolutionary multi-criterion optimization) 国际刊物“IEEE T
2、ransactions 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.9008.41024.010 -2.8007.84023.040 -2.7007.29022.090 -2.6006.76021.160 -2.5006.25020.250 -2.4005.
4、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)的可行解集,即: 我们称为决
5、策变量空间(简称决策空间),向量函数 将 映射到集合 ,是目标函数空间(称目标空间)。,决策空间和目标空间,定义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.
6、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*优越的
7、 不存在,则称X*为强Pareto最优解。,定义5:给定一个多目标优化问题 ,它的最优解集定义为: 多目标进化算法的优化过程是,针对每一代进化群体,寻找出其当前最优个体(即当前最优解),称一个进化群体的当前最优解为非支配解(non-dominated solution),或称为非劣解(non-inferior solution);所有非支配解的集合称之为当前进化群体的非支配集(NDS:non-dominated solutions),并使非支配集NDS不断逼近真正的最优解集,最终达到最优,即使NDSet*X*,NDSet*为算法运行结束时所求得的非支配集 。,Pareto最优边界,定义6:给定
8、一个多目标优化问题 和它的最优解集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。在多目标情况下,由于每个个体有多个属性,比较两个个体之间的关系不能使用简单的大小关系。
9、如两个目标的个体(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为被支
10、配的(dominated)。表示为p q,其中“ ”是支配关系(dominate relation)。,定义9(目标空间中的支配关系) 设 和 是目标空间中的两个向量,称U支配V(表示为 ),当且仅当: 且 ,使 。 据定义9,我们便可以得出结论:(2, 6)支配(3, 8),(2, 6)和(3, 5)之间互相不支配。 区别:决策空间支配关系,目标空间支配关系,多目标进化算法,为了便于理解,我们这里给出一类基于Pareto的多目标进化算法的一般流程,首先产生一个初始种群P,接着选择某个进化算法(如遗传算法)对P执行进化操作(如交叉、变异和选择),得到新的进化群体R。然后采用某种策略构造PR的非
11、支配集Nset,一般情况下在设计算法时已设置了非支配集的大小(如N),若当前非支配集Nset的大小大于或小于N时,需要按照某种策略对Nset进行调整,调整时一方面使Nset满足大小要求,同时也必须使Nset满足分布性要求。之后判断是否满足终止条件,若满足终止条件则结束,否则将Nset中个体复制到P中并继续下一轮进化 。,在MOEA中,保留上一代非支配集,并使之参入新一代的多目标进化操作是非常重要的,这类似于进化算法中保留上一代的最优个体,从而使新一代的非支配集不比上一代差,这也是算法收敛的必要条件。这样,一代一代的进化下去,进化群体的非支配集不断地逼近真正的最优边界(true pareto o
12、ptimal 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
13、technique) 后决策技术(posteriori technique),进一步研究,更一般的,更通用的,更接近于自然进化的MOEA模型 基于进化环境的多目标进化模型。 MOEA在有限时间内的收敛性。 构造多目标最优解集的最少时间复杂度。 进化过程中,个体循环地进入归档集问题。 MOEA在不同参数时的比较研究。 MOEA进化过程中,非支配集变化规律的研究。 MOEA运行的统一框架。 不确定多目标优化问题。 ,NSGA_II,1993年 Deb提出NSGA(The Non-dominated Sorting Genetic Algorithm ) NSGA主要有三个方面的不足:一是构造Par
14、eto最优解集的时间复杂度太高;二是没有最优个体(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和
15、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,保持种群多样性,在产生新群体时,通常将优
16、秀的同时聚集密度比较小的个体保留并参与下一代进化。聚集密度小的个体其聚集距离反而大,一个个体的聚集距离可以通过计算与其相邻的二个个体在每个子目标上的距离差之和来求取。 一般情况,当有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)
17、; /对子目标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=(F
18、1,F2,.) Pt+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 ,种群构造示意图
19、,SPEA,1999年 Zitzler提出SPEA(strength Pareto evolutionary algorithm) ,采用聚类方法降低非支配集大小。 产生一个初始群体Pop,同时设置一个空的非支配集NDSet(或称归档集(archive set); 将Pop中的非支配个体复制到NDSet中; 删除NDSet中的支配个体; 如果NDSet中的个体数目超过约定值,则用聚类方法(clustering procedure)降低NDSet的大小; 计算Pop和NDSet中个体的适应度; 采用锦标赛选择法从群体Pop和非支配集NDSet中选择个体进入配对库,直至配对库满; 对群体Pop执行
20、进化交叉和变异操作; 若不满足结束条件则转,否则结束。,SPEA中个体的适应度,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中,从每个子类中选出一个具有代表性的个体,组成新的非支配集。,SPEA2,N为进化群体P规模,M为归档集Q(archive set)大小,T为预定的进化代数 (1)初始化:产生一个初始群体P0,同时使归档集Q0为空,t0。 (2)适应度分配:计算Pt和Qt中所有个体的适应度。 (3)环境选择:将Pt和Qt
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学三年级科学教学设计:指南针制作与磁性探究
- 高三化学教学设计:金属材料微点深耕与情境化解题决策构建
- 八年级数学三角形内角和定理创新教学设计
- 七年级生物学《人体内废物的排出》教学设计
- 高中政治必修三《基层群众自治制度》教学设计
- 八年级语文下册《壶口瀑布》深度教学设计与课堂实践研究
- 2026年细毛绵羊皮行业洞察报告及未来五至十年发展趋势报告
- 2026年汽车网络营销行业洞察报告及未来五至十年发展趋势报告
- 2026年无人驾驶汽车创新技术分析报告
- 2026年医疗健康行业在线课程与社群运营策略报告
- 2025年gsp药品批发企业质量风险管理试题及答案
- 描写河西走廊的古诗
- 文心雕龙课件
- 松下-GF2-相机说明书
- 专题18 传送带模型(学生版)新高一物理多维度导学与分层专练
- 布比卡因脂质体注射液-临床用药解读
- 统计学基础与应用课件
- 传感器的应用与调试高职全套教学课件
- 【影片中的非线性叙事结构的实例研究(论文)】
- 为孩子培养良好的习惯【一年级家长会】讲座用课件
- 2023学年完整公开课版孔子论孝
评论
0/150
提交评论