遗传算法and多目标遗传算法ppt课件.pptx

多目标遗传算法,BY：*,大连海事大学交通运输管理学院,CONTENTS,CONTENTS,基本概念,遗传算法,NSGA-,单目标和多目标,单目标优化问题 唯一最优目标值多目标优化问题 1 (), 2 () 若两个解 , 1 1 ， 2 2 ,Which is better？,以最小化问题为例，对于两个任意决策变量 x A , x B X f （可行解集合）：(l)当且仅当i= 1,2,k : f i ( x A ) f i ( x B )时，称A占优于B( x A x B )(2)当且仅当i= 1,2,k : f i ( x A ) f i ( x B )且i= 1,2,k : f i ( x A ) f i ( x B )时，称A弱占优于B( x A x B )(3)当且仅当A不占优于B，且B不占优于A时，称A与B非支配 。此处是在有多个目标函数的情况下对两个解进行比较的，即如果Pareto占优，则该决策向量的所有目标函数值均应小于另一决策向量对应的各目标函数值。,Pareto占优,Pareto最优解,对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解.,Pareto最优前沿,Pareto最优解的集合称为Pareto最优前沿,遗传算法,问题:,1、产生初始种群,2、计算适应度,选择：具有随机性和进化性。 进化性：选择适应度高的个体进入下一代。 随机性：按照概率选择适应度高的进入下一代。,交叉,单点交叉,双点交叉,变异,交叉变异产生新解，防止陷入局部最优,迭代优化,选择,交叉,变异,最优解,NSGA-,全称：Non-dominated Sorting Genetic Algorithm- 非支配排序遗传算法，目前最流行的多目标进化算法之一。,NSGA-II 算法的改进：1）提出了快速非支配排序算法，使算法的复杂度由原来m N 3 的降到 m N 2 2）采用拥挤度和拥挤度比较算子，克服了 NSGA 中需要人为指定共享参数的缺陷，使得准 Pareto 域中的个体能均匀地扩展到整个 Pareto 域，保证了种群的多样性。 3）引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，提高了优化结果的精度。并通过对种群中所有个体的分层存放，使得最佳个体不会丢失。,快速非支配排序法分级,对于每个个体i都设有以下两个参数 n i 和 s i , n i 为在种群中支配个体 i 的解个体的数量， s i 为被个体 i 所支配的解个体的集合。 找到种群中所有 n i =0的个体，将它们存入当前集合 Z 1 ； 对于当前集合 Z 1 中的每个个体 j ，考察它所支配的个体集 S j ，将集合 S j 中的每个个体k 的 n k 减去 1，即支配个体 k 的解个体数减 1(因为支配个体 k 的个体 j 已经存入当前集 Z 1 )，如果 n k - 1=0,则将个体 k 存入另一个集 H ； 将 Z 1 作为第一级非支配个体集合， Z 1 中的个体是最优的，它只支配个体而不被其他任何个体支配，赋予该集合内个体一个相同的非支配序 i rank ，然后继续对 H作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。,拥挤度比较算子 -拥挤度的确定,NSGA-II 中提出了拥挤度的概念：拥挤度表示在种群中给定点的周围个体的密度，用 i d 表示。, 每个点的拥挤度 i d 置为 0； 针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷，即 o d = I d =； 对其他个体进行拥挤度的计算： i d = j=1 m f j i+1 f j i1 其中， i d 表示 i 点的拥挤度， f j i+1 表示 i+1点的第 j 个目标函数值， f j i1 表示 i -1点的第 j个目标函数值。,拥挤度比较算子-拥挤度比较算子,经过前面的快速非支配排序和拥挤度计算之后，种群中的每个个体i都拥有两个属性：非支配排序决定的非支配序 i rank 和拥挤度 i d 。依据这两个属性，可以定义拥挤度比较算子：个体i与另一个个体 j 进行比较，只要下面任意一个条件成立，则个体i获胜。 如果个体i所处非支配层优于个体 j 所处的非支配层，即 第一个条件确保被选择的个体属于较优的非劣等级。第二个条件根据它们的拥挤距离选择由于在同一非劣等级而不分胜负的两个个体中位于较不拥挤区域的个体(有较大的拥挤度 i d )。胜出的个体进入下一个操作。,精英策略,感谢聆听,