3多目标进化算法ppt课件.ppt

郑金华 多目标进化算法简介 jhzheng 多目标进化算法历史 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 同时达到最小 值空间分布图 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 3602 0004 0000 0002 1004 4100 010 2 2004 8400 0402 3005 2900 0902 4005 7600 1602 5006 2500 2502 6006 7600 3602 7007 2900 4902 8007 8400 6402 9008 4100 810 Pareto最优解基本定义 多目标优化的最优解称为Pareto最优解 1896年VilfredoPareto 定义1 给定一个多目标优化问题 它的最优解x 定义为 3 其中 4 这里 为满足式 1 和式 2 的可行解集 即 我们称 为决策变量空间 简称决策空间 向量函数将映射到集合 是目标函数空间 称目标空间 决策空间和目标空间 定义2 给定一个多目标优化问题 称是最优解 即Paretooptimalsolution 若 满足下列条件 或者 5 或至少存在一个 I 1 2 r 使 6 其中 满足式 1 和式 2 的可行解集 即 定义3 给定一个多目标优化问题 若 且不存在其它的使得 成立 且其中至少一个是严格不等式 则称X 是的Pareto最优解 Pareto最优解 Xf1f20040 10 013 610 20 043 240 30 092 890 40 162 560 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 给定一个多目标优化问题 它的最优解集定义为 多目标进化算法的优化过程是 针对每一代进化群体 寻找出其当前最优个体 即当前最优解 称一个进化群体的当前最优解为非支配解 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 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进行分类排序的目的是为了将其划分成若干个满足上述三个性质的互不相交的子群体 分类排序依据个体之间的支配关系来进行 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 1Qt 1 make new pop Pt 1 在Pt 1上执行选择 交叉和变异操作t t 1 种群构造示意图 SPEA 1999年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的