多目标优化之非支配排序遗传算法（NSGA-II）

        遗传算法GA ( Genetic Algorithms)是受生物学进化学说和遗传学理论的启发而发展起来的，是一类模拟自然生物进化过程与机制求解问题的自组织与自适应的人工智能技术，是一种借鉴生物界自然选择和自然遗传机制的随机的搜索算法，由Holland教授于1975年提出。

         经过十几年的努力，遗传算法不论是在应用研究上，算法设计上，还是在基础理论上，均取得了长足的发展，己经成为信息科学、计算机科学、运筹学和应用科学等诸多学科所共同关注的热点研究领域。

        遗传算法虽然在过去的20年中得到了广泛的应用，但研究人员己经意识到，遗传算法采用简单的、固定不变的进化策略对复杂应用场合的效果并不理想，传统的遗传算法逐渐暴露出一些缺点。所以，为了提高遗传算法的性能，使其更好地应用于实际问题的解决中，研究者们开始对基本遗传算法进行改进，通过不同的遗传基因表达方式，不同的交叉和变异算子的选择，特殊算子的引用，以及不同的再生和选择方法，产生了以基本遗传算法为核心的各种算法。遗传算法的这些扩展和改进给一般问题特别是工业工程中的难以求解的优化问题带来了新的希望和方向。

        由于多目标优化问题在科学和工程实践中普遍存在，但又缺少确实有效的解决方法，研究人员把目光投向了具有多方向和全局搜索特点的遗传算法。遗传算法的这一基本特点可以确保带有潜在解的种群能够一代一代地维持下来，这种从种群到种群的方法对于搜索Pareto解非常有益，因此，利用遗传算法解决多目标优化问题极具研究意义。于是，遗传算法应用于单目标问题之后的20多年以后，多目标遗传算法逐渐成为研究热点。

           非支配排序遗传算法NSGA (Non-dominated Sorting Genetic Algorithms)是由Srinivas和Deb于1995年提出的。这是一种基于Pareto最优概念的遗传算法，它是众多的多目标优化遗传算法中体现Goldberg思想最直接的方法。该算法就是在基本遗传算法的基础上，对选择再生方法进行改进:将每个个体按照它们的支配与非支配关系进行分层，再做选择操作，从而使得该算法在多目标优化方面得到非常满意的结果。

        2000年，他们又提出NSGA的改进算法—带精英策略的非支配排序遗传算法(NSGA-II)。 NSGA-II改进了原来算法的不足之处，提高了算法的运算速度和鲁棒性，并保证了非劣最优解的均匀分布。因而，NSGA-II比NSGA更具优越性。

        NSGA-II的三大优点分别是引入了非支配排序、提出拥挤度和拥挤度比较算子以及引入精英策略等。非支配排序利用Pareto最优解的概念将种群中的个体进行分级，非支配状态越高的个体层级越靠前，从而能够挑选出个体中较为优异的，使其有较大机会进入下一迭代。拥挤度只适用于同一支配层级的个体之间的比较，通过对每个个体的每个目标函数进行计算拥挤度，进而得出每个个体的拥挤度，通过拥挤度比较个体的优异程度。精英策略是把当前种群和通过选择、交叉和变异产生的子种群合并，共同竞争产生下一种群，保证具有较好特性的个体能够保留在种群中，提高了种群的多样性和计算效率。

        以下是NSGA-II算法的Matlab代码，需要的可以尝试下载。