遗传算法and多目标遗传算法.ppt

《遗传算法and多目标遗传算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、多目标遗传算法BY：*****大连海事大学交通运输管理学院CONTENTSCONTENTS1基本概念23遗传算法NSGA-Ⅱ单目标和多目标单目标优化问题唯一最优目标值多目标优化问题若两个解,Whichisbetter？以最小化问题为例，对于两个任意决策变量（可行解集合）：(l)当且仅当时，称A占优于B(2)当且仅当且时，称A弱占优于B()(3)当且仅当A不占优于B，且B不占优于A时，称A与B非支配。此处是在有多个目标函数的情况下对两个解进行比较的，即如果Pareto占优，则该决策向量的所有目标函

2、数值均应小于另一决策向量对应的各目标函数值。FPareto占优Pareto最优解对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解.Pareto最优前沿Pareto最优解的集合称为Pareto最优前沿遗传算法2问题:1、产生初始种群2、计算适应度选择：具有随机性和进化性。进化性：选择适应度高的个体进入下一代。随机性：按照概率选择适应度高的进入下一代。交叉单点交

3、叉双点交叉变异交叉变异产生新解，防止陷入局部最优迭代优化选择交叉变异最优解3NSGA-Ⅱ全称：Non-dominatedSortingGeneticAlgorithm-Ⅱ非支配排序遗传算法，目前最流行的多目标进化算法之一。NSGA-II算法的改进：1）提出了快速非支配排序算法，使算法的复杂度由原来的降到2）采用拥挤度和拥挤度比较算子，克服了NSGA中需要人为指定共享参数的缺陷，使得准Pareto域中的个体能均匀地扩展到整个Pareto域，保证了种群的多样性。3）引入精英策略，扩大采样空间。将父代

4、种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，提高了优化结果的精度。并通过对种群中所有个体的分层存放，使得最佳个体不会丢失。快速非支配排序法—分级对于每个个体i都设有以下两个参数和,为在种群中支配个体i的解个体的数量，为被个体i所支配的解个体的集合。①找到种群中所有=0的个体，将它们存入当前集合；②对于当前集合中的每个个体j，考察它所支配的个体集，将集合中的每个个体k的减去1，即支配个体k的解个体数减1(因为支配个体k的个体j已经存入当前集)，如果-1

5、=0,则将个体k存入另一个集H；③将作为第一级非支配个体集合，中的个体是最优的，它只支配个体而不被其他任何个体支配，赋予该集合内个体一个相同的非支配序，然后继续对H作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。拥挤度比较算子--拥挤度的确定NSGA-II中提出了拥挤度的概念：拥挤度表示在种群中给定点的周围个体的密度，用表示。①每个点的拥挤度置为0；②针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷，即；③对其他个体进行拥挤度的计算：其中，表示i点的拥挤度，表示i+1

6、点的第j个目标函数值，表示i-1点的第j个目标函数值。拥挤度比较算子--拥挤度比较算子经过前面的快速非支配排序和拥挤度计算之后，种群中的每个个体i都拥有两个属性：非支配排序决定的非支配序和拥挤度依据这两个属性，可以定义拥挤度比较算子：个体i与另一个个体j进行比较，只要下面任意一个条件成立，则个体i获胜。①如果个体i所处非支配层优于个体j所处的非支配层，即②如果他们有相同的等级，且个体i比个体j有一个更大的拥挤距离，即且第一个条件确保被选择的个体属于较优的非劣等级。第二个条件根据它们的拥挤距离选择

7、由于在同一非劣等级而不分胜负的两个个体中位于较不拥挤区域的个体(有较大的拥挤度)。胜出的个体进入下一个操作。精英策略开始输出进化代数Gen=1,初始化种群非支配排序形成非支配集ZGen=最大代数Gen=Gen+1交叉,变异新的子代种群个数等于N子代与父代种群合并形成2N大小种群进行拥挤度排序,拥挤度大的选入i=i+1YNYNi=1将放入新父代种群(精英策略)YN感谢聆听