NSGA-II多目标优化算法小白详细介绍ppt

非支配排序，拥挤度计算，pareto前沿，A Fast and Elitist Multi-objective Genetic Algorithm:NSGA-II NSGA算法 NSGA算法缺陷 NSGA-II算法 总结 1. 快速非支配排序法将时间复杂度改进为O(MN2)； 2.使用拥塞距离代替代替共享函数算法保持种群多样性； 引入精英保留策略。 非支配排序的复杂度较高: O(MN3) （M是目标函数的个数，N是种群大小)； 缺少精英保留策略； 需要人为指定共享参数σshare（共享小生境步骤）。 NSGA： nondominated sorting genetic algorithms-非支配排序遗传算法 nondominated：非支配 例：回家，两目标（费用，时间），均越小越好 动车A（270 , 7），普快B（120 , 10），飞机C（240，2） C（240，2）支配A（270 ， 7）; A（270 , 7）被C（240，2）支配; B（120 , 10）和C（240，2）不可比，即非支配。 目的：得到一组非支配的解--Pareto最优解集。 非支配排序遗传算法（NSGA）是一种用于多目标优化问题的进化算法，它通过模拟自然选择和遗传机制来寻找帕累托最优解集。帕累托最优是指在多个相互冲突的目标中，没有其他解决方案可以在所有目标上同时优于或等于当前方案的情况。在多目标优化中，目标通常不能同时达到最小化，因此寻求的是一个平衡点，即帕累托最优解。 NSGA算法主要由以下几个步骤组成： 1. **非支配排序**：这是NSGA的核心，用于确定个体之间的相对优势。如果一个个体在所有目标上都不劣于另一个个体，那么前一个个体就支配后者。通过非支配排序，可以将种群分为不同的层级，第一层是最优的，依次递增。然而，这种排序的计算复杂度很高，为O(MN^3)，其中M是目标函数的数量，N是种群大小。 2. **适应度值分配**：在非支配排序的基础上，为每个层级的个体分配虚拟适应度值。层级越低，适应度值越高，这样可以保证在选择操作中，较优的个体有更大的概率被选入下一代。 3. **适应度共享小生境**：为了保持种群多样性，NSGA算法引入了适应度共享机制。这需要人为设定共享参数σshare，以确保不同解在种群中有一定的分布，防止过早收敛到局部最优。 然而，NSGA算法存在几个显著的缺陷： - **计算复杂度高**：非支配排序的复杂度使得处理大型问题时效率低下。 - **缺乏精英保留策略**：NSGA在进化过程中可能会丢失优秀的解，因为没有强制保留前一代的最优个体。 - **依赖人工参数设置**：共享参数σshare的设定需要经验，可能影响算法的性能。 针对这些问题，NSGA-II算法进行了改进： 1. **快速非支配排序**：NSGA-II提出了一种更快的排序方法，将时间复杂度降低到O(MN^2)，提高了效率。 2. **拥挤度计算**：用拥挤度代替共享函数，更有效地衡量个体间的距离，有助于保持种群多样性。 3. **精英保留策略**：NSGA-II引入了精英保留机制，确保最佳解能够传递到下一代，提高了算法的稳定性。 NSGA-II算法的主要流程包括：初始化种群、进行非支配排序、计算拥挤度、执行选择、交叉和变异操作，然后重复这个过程，直至满足停止条件。通过这些改进，NSGA-II能够在保持多样性的同时，更快地收敛到帕累托最优解集。