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

针对具有大型解空间的多目标决策问题,为进一步提高多目标决策的效率,快速且有效的非支配解集构造方法值得探究.给出非支配关系性质、初始非支配解集(简称初集)及非支配解集构造的有关定义与定理.在此基础上,依据有序集理论与运算规则,提出基于初集排序方法的Pareto非支配解集构造算法.该算法应用集合排序的方法,对有序的可行解集与有序的非支配解集进行比较,获得多目标决策问题的最优解.构建不包含初始非支配解的有序可行解集,设计非支配解排序规则、查找规则与插入规则.分析提出的算法及常见的非支配排序方法的时间复杂度.通过ZDT1～ZDT3、DTLZ1与DTLZ3测试函数的非支配解集构造实验,与王芳等(2016)提出的NTCM等方法相比,证明提出的非支配解集构造算法是有效的,时间复杂度更低,非支配解集构造时间具有显著的优势.

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

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.