有效构造非支配解集可加快Pareto前沿的求解速度,提升多目标决策的质量和效率.在非支配解定义和性质分析基础上,推导出支配关系传递性引理,非支配解集构造定理及引理,并据此提出一种基于性质定理的非支配解集构造方法.基于所提方法,分析其循环次数和比较次数,推导出在最坏情况下能算出确定值的复杂度计算公式.最后证明该方法的正确性与完备性,分析最坏情形下其构造集的结构特征,并通过ZDT1~ZDT3测试函数进行检验.结果表明:所提方法比排除法和选举法的计算复杂度更低,构造速度更快.
Abstract
Formulating non-dominated solution set effectively can speed up the solving process of the Pareto front, and can improve the quality and efficiency of multi-objective decision-making. Therefore, based on the definition and feature of the non-dominated solutions, the lemma of dominations relation transitivity, the theorems and lemma of non-dominated solution set construction are deduced. Depending upon the proposed theorems and lemmas, a novel non-dominated solution set construction method is first proposed. Then the frequency of the comparison and the number of iteration in the new method are counted, and a novel formula is put forward to calculate the deterministic value of computational complexity in the worst case. Finally, the correctness and completeness of the new method are proved in theory, and the structural features of the construction set at the maximum degree of complexity are given, what's more, the performance test of the new method is carried out through the ZDT1~ZDT3 test functions. The results show that the new method is lower in computational complexity and faster in construction speed than the exclusions method and electoral law method.
关键词
多目标决策 /
Pareto非支配解 /
构造方法 /
复杂度
{{custom_keyword}} /
Key words
multi-objective decision-making /
Pareto non-dominated solution /
construction method /
computational complexity
{{custom_keyword}} /
中图分类号:
N945.25
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] Pareto V. Course economic politique[M]. Lausanne, Switzerland:F.Rouge, 1896.
[2] Vira C K, Haimes Y Y. Multiobjective decision making:Theory and methodology[M]. New York:North Holland, 1983.
[3] Ehrgott M. Multi-criteria optimization[M]. Berlin:Springer, 2000.
[4] 方国华, 黄显峰. 多目标决策理论、方法及其应用[M]. 北京:科学出版社, 2011. Fang G H, Huang X F. Multi-objective decision-making theory, method and application[M]. Beijing:Science Press, 2011.
[5] Srinivas N, Deb K. Muilti-objective optimization using non-dominated sorting in genetic algorithms[J]. Evolutionary Computation, 1994, 3(2):221-248.
[6] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm:NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2):182-197.
[7] Sierra R M, Coello C A C. Multi-objective particle swarm optimizers:A survey of the state-of-the-art[J]. International Journal Computation Intelligence Research, 2006, 2(3):287-308.
[8] Chan T M, Man K F, Tang K S, et al. A jumping genes paradigm for evolutionary multiobjective optimization[J].IEEE Transactions on Evolution Computation, 2008, 12(2):143-159.
[9] Yang Y, Wu J f, Sun X M, et al. A niched Pareto tabu search for multi-objective optimal design of groundwater remediation systems[J]. Journal of Hydrology, 2013, 5(490):56-73.
[10] 李双琳, 马祖军, 郑斌,等. 震后初期应急物资配送的模糊多目标选址-多式联运问题[J]. 中国管理科学, 2013, 21(2):144-151.Li S L, Ma Z J, Zheng B, et al. Fuzzy multi-objective location-multimodal transportation problem for relief delivery during the initial post-earthquake period[J]. Chinese Journal of Management Science, 2013, 21(2):144-151.
[11] 李洪波, 徐哲, 于静. 基于DSM的研发项目流程多目标仿真优化[J]. 系统工程理论与实践, 2015, 35(1):142-149.Li H B, Xu Z, Yu J. Multi-objective simulation optimization for the process of R&D projects based on DSM[J]. Systems Engineering-Theory & Practice, 2015, 35(1):142-149.
[12] Deb K. Multi-objective optimization using evolutionary algorithms[M]. Chichester:Wiley, 2001.
[13] Coello C A C, Van-Veldhuizen D A, Lamont G B. Evolutionary algorithms for solving multi-objective problems[M]. Boston:Kluwer Academic Publishers, 2002.
[14] Coello C A C, Aguirre A H, Zitzler E. Evolutionary multi-criterion optimization:Third international conference[C]//Guanajuato, Mexico, March 9-11, 2005, New York:Springer, 2005:912.
[15] 郑金华. 多目标进化算法及其应用[M]. 北京:科学出版社, 2007.Zheng J H. Multi-objective evolutionary algorithm and application[M]. Beijing:Science Press, 2007.
[16] 雷德明, 严新平. 多目标智能优化算法及其应用[M]. 北京:科学出版社, 2009.Lei D M, Yan X P. Multi-objective intelligent optimization algorithm and application[M]. Beijing:Science Press, 2009.
[17] 焦李成, 尚荣华, 马文萍,等.多目标优化免疫算法、理论和应用[M]. 北京:科学出版社, 2010.Jiao L C, Shang R H, Ma W P, et al. Multi-objective optimization immune algorithm, the theory and application[M]. Beijing:Science Press, 2010.
[18] Shukla P K, Deb K. On finding multiple Pareto-optimal solutions using classical and evolutionary generating methods[J].European Journal of Operational Research, 2007(181):1630-1652.
[19] Lu L, Cook A C M, Robinson T J. A case study to demonstrate Pareto frontiers for selecting a best response surface design with simultaneously optimizing multiple criteria[J]. Applied Stochastic Models in Business and Industry, 2012, 3(28):85-96.
[20] Wagner T, Trautmann H. Integration of preferences in hypervolume-based multiobjective evolutionary algorithms by means of desirability functions[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(5):688-701.
[21] Lu L, Cook A C M, Lin D K J.Optimal designed experiments using a Pareto front search for focused preference of multiple objectives[J]. Computational Statistics and Data Analysis, 2014(71):1178-1192.
[22] Deb K. Multi-objects evolutionary optimization:Past, present and future[C]//Proceedings of the Fourth International Conference on Adaptive Computing in Design and Manufacture. London:Springer, 2000:225-236.
[23] Jensen M T. Reducing the run-time complexity of multiobjective EAs:The NSGA-II and other algorithms[J].IEEE Transactions on Evolutionary Computation, 2003, 7(5):503-515.
[24] 李丽荣, 郑金华. 基于Pareto Front的多目标遗传算法[J]. 湘潭大学自然科学学报, 2004, 26(3):39-41.Li L R, Zheng J H. Multi-objective genetic algorithm based on the Pareto front[J]. Natural Science Journal of Xiangtan University, 2004, 26(3):39-41.
[25] 郑金华, 蒋浩, 邝达,等. 用擂台赛法则构造多目标Pareto最优解集的方法[J]. 软件学报, 2007, 18(6):1287-1297.Zheng J H, Jiang H, Kuang D, et al. An approach of constructing multi-objective Pareto optimal solutions using Arena's principle[J]. Journal of Software, 2007, 18(6):1287-1297.
[26] 杨平, 郑金华, 李密青,等. 一种快速构造多目标Pareto非支配集的方法:选举法则[J]. 计算机应用研究, 2009, 26(2):488-491.Yang P, Zheng J H, Li M Q, et al. Fast method of constructing multi-objective Pareto non-dominated set:Election principle[J]. Application Research of Computers, 2009, 26(2):488-491.
[27] Zitzler E, Deb K, Thiele L. Comparison of multi-objective evolutionary algorithms:Empirical results[J]. Evolutionary Computation, 2000, 8(2):173-195.
[28] Shaffer C A. 数据结构与算法分析(C++版)[M]. 3版. 张铭, 刘晓丹,译. 北京:电子工业出版社, 2013.Shaffer C A. Data structures and algorithm analysis in C++[M]. 3rd ed. Beijing:Electronic Industry Press, 2013.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
湖北省教育厅青年项目(Q20151104);国家自然科学基金面上项目(51275366);国家重点基础研究发展计划项目(973计划)(2014CB046705);国家自然科学基金青年项目(51305311)
{{custom_fund}}