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

多目标遗传算法BY：*****大连海事大学交通运输管理学院CONTENTSCONTENTS1基本概念23遗传算法NSGA-Ⅱ单目标和多目标单目标优化问题𝑀𝑖𝑛𝑓𝑥唯一最优目标值多目标优化问题𝑀𝑖𝑛𝑓1(𝑥),𝑓2(𝑥)若两个解𝑋𝐴,𝑋𝐵𝑓1𝑋𝐴𝑓1𝑋𝐵，𝑓2𝑋𝐴𝑓2𝑋𝐵以最小化问题为例，对于两个任意决策变量xA,xB∈Xf（可行解集合）：(l)当且仅当∀i=1,2,…,k:fi(xA)fi(xB)时，称A占优于B(xA≻xB)(2)当且仅当∀i=1,2,…,k:fi(xA)≤fi(xB)且∃i=1,2,…,k:fi(xA)fi(xB)时，称A弱占优于B(xA≽xB)(3)当且仅当A不占优于B，且B不占优于A时，称A与B非支配。此处是在有多个目标函数的情况下对两个解进行比较的，即如果Pareto占优，则该决策向量的所有目标函数值均应小于另一决策向量对应的各目标函数值。FPareto占优Pareto最优解对于多目标优化问题，通常存在一个解集，这些解之间就全体目标函数而言是无法比较优劣的，其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解或Pareto最优解.Pareto最优前沿Pareto最优解的集合称为Pareto最优前沿遗传算法2问题:2min()[0,63]gxxx1、产生初始种群2、计算适应度2()()[0,63]fxgxxxx()fx选择：具有随机性和进化性。进化性：选择适应度高的个体进入下一代。随机性：按照概率选择适应度高的进入下一代。交叉单点交叉crandpcrandp双点交叉crandpcrandp变异crandpcrandp迭代优化选择交叉变异最优解3NSGA-Ⅱ全称：Non-dominatedSortingGeneticAlgorithm-Ⅱ非支配排序遗传算法，目前最流行的多目标进化算法之一。NSGA-II算法的改进：1）提出了快速非支配排序算法，使算法的复杂度由原来mN3的降到mN22）采用拥挤度和拥挤度比较算子，克服了NSGA中需要人为指定共享参数的缺陷，使得准Pareto域中的个体能均匀地扩展到整个Pareto域，保证了种群的多样性。3）引入精英策略，扩大采样空间。将父代种群与其产生的子代种群组合，共同竞争产生下一代种群，有利于保持父代中的优良个体进入下一代，提高了优化结果的精度。并通过对种群中所有个体的分层存放，使得最佳个体不会丢失。快速非支配排序法—分级对于每个个体i都设有以下两个参数ni和si,ni为在种群中支配个体i的解个体的数量，si为被个体i所支配的解个体的集合。①找到种群中所有ni=0的个体，将它们存入当前集合Z1；②对于当前集合Z1中的每个个体j，考察它所支配的个体集Sj，将集合Sj中的每个个体k的nk减去1，即支配个体k的解个体数减1(因为支配个体k的个体j已经存入当前集Z1)，如果nk-1=0,则将个体k存入另一个集H；③将Z1作为第一级非支配个体集合，Z1中的个体是最优的，它只支配个体而不被其他任何个体支配，赋予该集合内个体一个相同的非支配序irank，然后继续对H作上述分级操作并赋予相应的非支配序，直到所有的个体都被分级。拥挤度比较算子--拥挤度的确定NSGA-II中提出了拥挤度的概念：拥挤度表示在种群中给定点的周围个体的密度，用id表示。①每个点的拥挤度id置为0；②针对每个目标，对种群进行非支配排序，令边界的两个个体拥挤度为无穷，即od=Id=∞；③对其他个体进行拥挤度的计算：id=fji+1−fji−1mj=1其中，id表示i点的拥挤度，fji+1表示i+1点的第j个目标函数值，fji−1表示i-1点的第j个目标函数值。拥挤度比较算子--拥挤度比较算子经过前面的快速非支配排序和拥挤度计算之后，种群中的每个个体i都拥有两个属性：非支配排序决定的非支配序irank和拥挤度id。依据这两个属性，可以定义拥挤度比较算子：个体i与另一个个体j进行比较，只要下面任意一个条件成立，则个体i获胜。①如果个体i所处非支配层优于个体j所处的非支配层，即𝒊𝒓𝒂𝒏𝒌𝒋𝒓𝒂𝒏𝒌②如果他们有相同的等级，且个体i比个体j有一个更大的拥挤距离，即𝒊𝒓𝒂𝒏𝒌=𝒋𝒓𝒂𝒏𝒌且𝒊𝒅𝒋𝒅第一个条件确保被选择的个体属于较优的非劣等级。第二个条件根据它们的拥挤距离选择由于在同一非劣等级而不分胜负的两个个体中位于较不拥挤区域的个体(有较大的拥挤度id)。胜出的个体进入下一个操作。精英策略开始输出进化代数Gen=1,初始化种群𝑹𝒕非支配排序形成非支配集ZGen=最大代数Gen=Gen+1交叉,变异新的子代种群𝑸𝒕+𝟏𝑷𝒕+𝟏个数等于N子代与父代种群合并形成2N大小种群𝑹𝒕𝒁𝒊…𝒁i+j进行拥挤度排序,拥挤度大的选入i=i+1YNYNi=1将𝒁𝒊放入新父代种群𝑷𝒕+𝟏(精英策略)𝒁𝒊=𝒁i+1=⋯=𝒁i+jYN感谢聆听