一种快速的双目标非支配排序算法

提出一种快速的双目标非支配排序算法(BNSA)。设计了前向比较操作，以便快速识别非支配个体。提出了按需排序策略，避免生成多余的非支配前沿。论证BNSA算法的正确性，分析其时间复杂度为O(NlogN)。在9个标准的双目标优化测试问题上进行了比较实验。实验结果表明与其它3种非支配排序算法相比，BNSA算法在大多数测试问题上具有更快速的性能。当进化代数超过400代时，BNSA在所有的测试问题上都具有最好的加速效果。此外，BNSA算法简明、易于编程实现，可集成到任何基于非支配排序的多目标进化算法中，能较大程度地提高双目标优化的运行速度。

A FastBi-ObjectiveNon-DominatedSortingAlgorithm

A fast bi-objective non-dominated sorting algorithm (BNSA) is proposed. An operator of forward comparison is designed to identify non-dominated individuals quickly. A sorting strategy according to need is proposed to avoid generating unnecessary non-dominated fronts. Then, the correctness of BNSA is proved and its time complexity is analyzed to be O(NlogN). Next, some comparable experiments are carried out on nine benchmark test problems for bi-objective optimization. Results of the experiments indicate that the proposed BNSA, for the most test problems, is faster than the other three non-dominated sorting algorithms. Furthermore, the BNSA, on all the test problems, has the best of accelerative effect, particularly when the number of evolutionary generations exceeds 400. In addition, the BNSA is concise and easy to be implemented. It can be incorporated into any multi-objective evolutionary algorithms based on non-dominated sorting to improve the running speed of bi-objective optimization.