引用网站代码,如何创建微信公众号平台,如何免费制作网站?,社交网站模版当我们面临多个目标函数时#xff0c;单目标的遗传算法可能无法满足需求。这时#xff0c;我们可以引入多目标遗传算法。在这种情况下#xff0c;目标函数可能存在冲突#xff0c;例如#xff0c;一个目标函数需要最小化#xff0c;而另一个目标函数需要最大化。某个目标…当我们面临多个目标函数时单目标的遗传算法可能无法满足需求。这时我们可以引入多目标遗传算法。在这种情况下目标函数可能存在冲突例如一个目标函数需要最小化而另一个目标函数需要最大化。某个目标函数的提高可能需要以另一个函数的降低为代价。这就引出了帕累托解Pareto解的概念。即每个目标都想达到最优。解决pareto解有以下几种常用方法
权重系数转换法
对于每个目标函数f(xi)(i1,2,3,4…)赋予权重wi(i1,2,3…)wi为目标函数重要程度有
权重系数函数利用权重将多目标转化为单目标函数将W作为评价函数。缺点需要自己确定特征数据的权重主观影响较大。
排序选择法
基于pareto最优个体的概念对群体中的个体进行排序。然后根据这个次序进行种群选择。这样的话能够让pareto最优个体有更多的机会遗传到下一代。缺点仅仅度量了各个个体之间的优越次序而并未度量各个个体的分散程度所以容易生成相似的解而不是分布较广的多个最优解。
带精英策略的非支配排序遗传算法–NSGAII
1采用快速非支配型排序降低了算法复杂度。其复杂度为O(MN**2)。2提出了拥挤度和拥挤度比较算子代替需要制定共享半径的适应度共享策略。并在快速排序后的同级比较中作为胜出标准。使pareto解中的个体扩展到整个pareto域中并均匀分布保持了种群的多样性。3引入精英策略扩大采样空间。将父代种群和子代种群合并保证优良个体能够留存下来。
算法步骤如下 首先随机产生数量为n的初始种群
2然后对其进行非支配排序可以将种群中的个体按照pareto支配关系分成不同的层级。3然后计算每个个体的拥挤度拥挤度主要是用于衡量每个个体在目标空间中与其他个体的相似程度拥挤度距离越大说明个体越具有多样性。4接下来就是常规的选择交叉变异操作产生第一代子代种群。
从第二代开始将父代和子代合并
然后对其进行快速非支配型排序同时计算每个非支配层的个体进行拥挤度的计算。然后根据非支配关系和拥挤度来选择合适的个体组成新的父代种群。最后再通过选择、交叉变异产生子代。重复。还有几个主要的关键技术需要解释一下1快速非支配型排序假设种群为P则该算法需要计算P中的每个个体p的两个参数np和Sp其中np为种群中支配个体p的个体数Sp为种群中支配个体p的个体集合。遍历整个种群这里那个两个参数的时间复杂度O(mN2)。2拥挤度在种群中给定点的周围个体密度用id表示。它指出了在个体i周围包含个体i本身但不包含其他个体的最小的长方形。3拥挤比较算子经过快速非支配排序和拥挤度计算种群中的每一个个体都得到了两个属性非支配序rankn和拥挤度。利用这两个属性我们可以区分种群中间任意两个个体间的支配和非支配关系。定义拥挤度比较算子当且仅当irankjrank或irankjrank且idjd有个体i优于个体j。4精英选择策略精英策略是指在每一代的进化过程中保留一部分优秀的个体使得下一代的种群从父代和子代的合并种群中选择从而提高算法的收敛性和解的质量。精英选择策略可以防止优秀的解被破坏或丢失也可以加快非支配解集的收敛速度。NSGAII中的精英选择策略具体如下
在每一代首先对父代种群进行交叉和变异操作产生子代种群。然后将父代种群和子代种群合并为一个大小为2N的种群其中N是种群大小。对合并种群进行快速非支配排序根据Pareto支配关系将个体分成不同的层级并给每个个体赋予一个等级值。从最高层级开始依次将每个层级的个体加入到下一代种群中直到下一代种群达到N个个体或者超过N个个体。如果最后一个加入的层级导致下一代种群超过N个个体则对该层级的个体进行拥挤度计算和比较根据拥挤度大小选择部分个体加入到下一代种群中使得下一代种群恰好有N个个体。重复上述步骤直到达到预设的进化代数。
总结来说相比于单目标函数求解多目标函数求解明显难度提升了好几个数量级其核心问题在于出现Pareto解。我们需要权衡各个目标函数之间的利弊选择合适算法来求解。下面是NSGA3算法流程图
NSGA-III算法相比于NSGA和NSGA-II算法
NSGA-III算法引入了一组均匀分布的参考点用于指导种群的选择保持种群的多样性和收敛性。参考点的数量和位置可以根据目标个数和种群大小自适应地确定而不需要人为地设定。NSGA-III算法采用了一种新的归一化方法即用理想点和截距点将目标空间映射到单位超立方体中然后计算每个个体与最近的参考点的距离根据距离和参考点的拥挤度进行选择这样可以避免目标之间的尺度差异和非均匀分布的影响。NSGA-III算法在选择过程中不仅考虑了个体的非支配等级还考虑了个体的参考点关联度即个体与参考点的距离和参考点的拥挤度这样可以更好地平衡种群的多样性和收敛性同时也可以避免过度选择或忽略某些目标。
结论
多目标遗传算法的核心思想是没有最好的解只有最合适的解。所以不要太担心你的选择是否正确只要你能找到一个让你满意的解就可以啦。
