基于初集排序的Pareto非支配解集构造算法  

A construction algorithm of Pareto non-dominated solution set based on initial set sorting

作　　者：汪勇[1,2] 程姣 高娜 王静 WANG Yong;CHENG Jiao;GAO Na;WANG Jing(School of Management, Wuhan University of Science and Technology, Wuhan 430081, China;School of Economics and Management, Tsinghua University, Beijing 100084, China)

机构地区：[1]武汉科技大学恒大管理学院,武汉430081 [2]清华大学经济管理学院,北京100084

出　　处：《系统工程理论与实践》2018年第4期960-970,共11页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金重点项目(71232007);国家自然科学基金面上项目(51275366)~~

摘　　要：针对具有大型解空间的多目标决策问题，为进一步提高多目标决策的效率，快速且有效的非支配解集构造方法值得探究．给出非支配关系性质、初始非支配解集（简称初集）及非支配解集构造的有关定义与定理．在此基础上，依据有序集理论与运算规则，提出基于初集排序方法的Pareto非支配解集构造算法．该算法应用集合排序的方法，对有序的可行解集与有序的非支配解集进行比较，获得多目标决策问题的最优解．构建不包含初始非支配解的有序可行解集，设计非支配解排序规则、查找规则与插入规则．分析提出的算法及常见的非支配排序方法的时间复杂度．通过ZDT1-ZDT3、DTLZ1与DTLZ3测试函数的非支配解集构造实验，与王芳等（2016）提出的NTCM等方法相比，证明提出的非支配解集构造算法是有效的，时间复杂度更低，非支配解集构造时间具有显著的优势．In order to further enhance the efficiency of the multi-objective decision-making problem with an enormous solution space, an effective and fast construction approach of the non-dominated solution set is worth to explore. At first, the properties of non-dominated relationship, the initial set of non-dominated solution, the definitions and theorems related to the set of non-dominated solution construction are given. In this paper, then, in terms of ordered set theory and operation rules, a new kind of construction approach of Pareto non-dominated solution set is proposed based on the initial non-dominated solution set sorting approach. This algorithm applies set sorting approach to attain the optimal solutions of MOP through comparing the ordered feasible solution set with the ordered non-dominated solution set. On the one hand, the ordered feasible solution set which not include the initial non-dominated solutions is built. On the other hand, some rules of algorithm are designed, which include the sorting criterion of initial non-dominated solutions, the insertion criterion and the find criterion of non-dominated solution. The time complexity in different situations of the presented algorithm and the common non-dominated sorting approaches are analyzed. At last, the experiments to construct the set of non-dominated solutions have been done through the test functions of ZDT1-ZDT3, DTLZ1 and DTLZ3, compared with the approach of NTCM proposed by Wang and the other three kinds of approaches, the algorithm mentioned above has a higher effectivity to find the non-dominated solution correctly, it has the more lower time complexity and the more shorter computation time to construct the set of non-dominated solutions.

关 键 词：多目标决策 PARETO最优解 初始非支配解集 有序集 

分 类 号：C934[经济管理—管理学] TP301[自动化与计算机技术—计算机系统结构]