Parallel Many-objective Evolutionary Optimization Using Objectives Decomposition
-
摘要: 高维多目标优化问题普遍存在且难以解决, 到目前为止, 尚缺乏有效解决该问题的进化优化方法. 本文提出一种基于目标分解的高维多目标并行进化优化方法, 首先, 将高维多目标优化问题分解为若干子优化问题, 每一子优化问题除了包含原优化问题的少数目标函数之外, 还具有由其他目标函数聚合成的一个目标函数, 以降低问题求解的难度; 其次, 采用多种群并行进化算法, 求解分解后的每一子优化问题, 并在求解过程中, 充分利用其他子种群的信息, 以提高Pareto非被占优解的选择压力; 最后, 基于各子种群的非被占优解形成外部保存集, 从而得到高维多目标优化问题的Pareto 最优解集. 性能分析表明, 本文提出的方法具有较小的计算复杂度. 将所提方法应用于多个基准优化问题, 并与NSGA-II、PPD-MOEA、ε-MOEA、HypE和MSOPS等方法比较, 实验结果表明, 所提方法能够产生收敛性、分布性, 以及延展性优越的Pareto最优解集.Abstract: Many-objective optimization problem is common in real-world applications, however, so far few evolutionary algorithms are suitable for them due to the difficulties of the problem. A parallel many-objective evolutionary optimization algorithm based on objectives decomposition is proposed. First, the many-objective optimization problem is decomposed into several sub-problems, which contain only some objectives of the original optimization problem together with a constructed objective by aggregating all the other objectives. Then, a multi-population parallel evolutionary algorithm is adopted to solve these sub-problems. The pressure on selecting non-dominated solutions for a sub-problem is improved by taking full advantage of the information obtained from other sub-populations. The final Pareto set of the optimized many-objective is achieved by archiving those sets of non-dominated solutions coming from the sub-populations. The performance of the proposed algorithm on reducing computation complexity is qualitatively analyzed. Furthermore, the algorithm is applied to several benchmark problems and compared with NSGA-II, PPD-MOEA, ε-MOEA, HypE, and MSOPS. The results experimentally demonstrate that the algorithm is strengthened in obtaining solutions with better convergence, distribution and approximation.
-
Key words:
- Evolutionary algorithm /
- many-objective optimization /
- decomposition /
- parallel /
- Pareto domination
-
[1] Zhang Xiao-Dong, Yao Xiao-Lan, Wu Qing-He, Li Dao-Ping. Design and application of a class of multiplexed receding horizon controllers for looper control system. Acta Automatica Sinica, 2011, 37(3): 380-384(张晓东, 姚小兰, 伍清河, 李道平. 一类基于滚动时域优化原理的多路控制器设计及其在活套控制中的应用. 自动化学报, 2011, 37(3): 380-384) [2] Kong Wei-Jian, Chai Tian-You, Ding Jin-Liang, Wu Zhi-Wei. A real-time multiobjective electric energy allocation optimization approach for the smelting process of magnesia. Acta Automatica Sinica, 2014, 40(1): 51-61(孔维健, 柴天佑, 丁进良, 吴志伟. 镁砂熔炼过程全厂电能分配实时多目标优化方法研究. 自动化学报, 2014, 40(1): 51-61) [3] Zuo Xing-Quan, Wang Chun-Lu, Zhao Xin-Chao. Combining multi-objective immune algorithm and linear programming for double row layout problem. Acta Automatica Sinica, 2015, 41(3): 528-540(左兴权, 王春露, 赵新超. 一种结合多目标免疫算法和线性规划的双行设备布局方法. 自动化学报, 2015, 41(3): 528-540) [4] Deb K, Pratap A, Agarwal A, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197 [5] Zitzler E, Laumanns M, Thiele L. SPEA2: improving the strength Pareto evolutionary algorithm for multiobjective optimization. In: Proceedings of the 5th Conference on Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. Athens, Greece: CIMNE, 2001. 95-100 [6] Deb K, Saxena D K. Searching for Pareto-optimal solutions through dimensionality reduction for certain large-dimensional multi-objective optimization problems. In: Proceedings of the 2006 IEEE Congress on Evolutionary Computation. Vancouver, Canada: IEEE, 2006. 3353-3360 [7] Jaimes A L, Coello C A C, Chakraborty D. Objective reduction using a feature selection technique. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM, 2008. 673-680 [8] Adra S F, Fleming P J. Diversity management in evolutionary many-objective optimization. IEEE Transactions on Evolutionary Computation, 2011, 15(2): 183-195 [9] Li M Q, Yang S X, Liu X H. Shift-based density estimation for Pareto-based algorithms in many-objective optimization. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 348-365 [10] Sato H, Aguirre H E, Tanaka K. Pareto partial dominance MOEA and hybrid archiving strategy included CDAS in many-objective optimization. In: Proceedings of the 2010 IEEE Congress on Evolutionary Computation. Barcelona, Spain: IEEE, 2010. 1-8 [11] Jaimes A L, Coello C A C, Aguirre H, Tanaka K. Objective space partitioning using conflict information for solving many-objective problems. Information Sciences, 2014, 268: 305-327 [12] Deb K, Mohan M, Mishra S. Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions. Evolutionary Computation, 2005, 13(4): 501-525 [13] Kukkonen S, Lampinen J. Ranking-dominance and many-objective optimization. In: Proceedings of the 2007 IEEE Congress on Evolutionary Computation. Singapore: IEEE, 2007. 3983-3990 [14] Zitzler E, Künzli S. Indicator-based selection in multiobjective search. In: Proceedings of the 8th International Conference on Parallel Problem Solving from Nature. Berlin: Springer-Verlag, 2004. 832-842 [15] Bader J, Zitzler E. HypE: an algorithm for fast hyper- volume-based many-objective optimization. Evolutionary Computation, 2011, 19(1): 45-76 [16] Hughes E J. Multiple single objective Pareto sampling. In: Proceedings of the 2003 IEEE Congress on Evolutionary Computation. Canberra, Australia: IEEE, 2003. 2678-2684 [17] Zhang Q F, Li H. MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-730 [18] Zitzler E, Thiele L, Bader J. On set-based multiobjective optimization. IEEE Transactions on Evolutionary Computation, 2010, 14(1): 58-79 [19] Gong Dun-Wei, Ji Xin-Fang, Sun Xiao-Yan. Solving many-objective optimization problems using set-based evolutionary algorithms. Acta Electronica Sinica, 2014, 42(1): 77-83(巩敦卫, 季新芳, 孙晓燕. 基于集合的高维多目标优化问题的进化算法. 电子学报, 2014, 42(1): 77-83) [20] Toro F, Ortega J, Fernandez J, Diaz A. PSFGA: a parallel genetic algorithm for multiobjective optimization. In: Proceedings of the 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing. Canary Islands: IEEE Computer Society, 2002. 384-391 [21] Qi R B, Ma T Y, Sun F, Qian F. Evolutionary algorithm based on the evolution of Pareto archive and individual migration. In: Proceedings of the 2011 International Symposium on Advanced Control of Industrial Processes. Hangzhou, China: IEEE, 2011. 90-95 [22] Wang Xing. Non-Parametric Statistics. Beijing: Tsinghua University Press, 2009. 180-184(王星. 非参数统计. 北京: 清华大学出版社, 2009. 180-184) [23] Murata T, Taki A. Examination of the performance of objective reduction using correlation-based weighted-sum for many objective knapsack problems. In: Proceedings of the 10th International Conference on Hybrid Intelligent Systems. Atlanta, GA: IEEE, 2010. 175-180 [24] Deb K, Thiele L, Laumanns M, Zitzler E. Scalable test problems for evolutionary multiobjective optimization. In: Proceedings of the 2005 Evolutionary Multiobjective Optimization. London: Springer-Verlag, 2005. 105-145 [25] Corne D W, Knowles J D. Techniques for highly multiobjective optimisation: some nondominated points are better than others. In: Proceedings of the 9th Annual Conference Genetic Evolutionary Computation. London, England: ACM, 2007. 773-780 [26] van Veldhuizen D A, Lamont G B. On measuring multiobjective evolutionary algorithm performance. In: Proceedings of the 2000 IEEE Congress on Evolutionary Computation. San Diego, CA, US: IEEE, 2000. 204-211 [27] Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: empirical results. Evolutionary Computation, 2000, 8(2): 173-195 [28] Zhang Q F, Zhou A M, Zhao S Z, Suganthan P N, Liu W D, Tiwari S. Multiobjective Optimization Test Instances for the CEC 2009 Special Session and Competition, Technical Report CES-487, University of Essex, Colchester, UK, and Nanyang Technological University, Singapore, 2008. [29] Ishibuchi H, Akedo N, Nojima Y. Behavior of multi-objective evolutionary algorithms on many-objective knapsack problems. IEEE Transactions on Evolutionary Computation, 2015, 19(2): 264-283
点击查看大图
计量
- 文章访问数: 2021
- HTML全文浏览量: 145
- PDF下载量: 1734
- 被引次数: 0