微信服务号

微信订阅号

2025年5月14日 5:18 星期三
首页 > 过刊浏览>2014年第25卷第5期 >1025-1050. DOI:10.13328/j.cnki.jos.004496
PDF HTML阅读 XML下载 导出引用 引用提醒
基于Pareto熵的多目标粒子群优化算法
作者:
基金项目:

中央高校基本科研业务费专项资金（2672013ZYGX2013J078）


Multiobjective Particle Swarm Optimization Based on Pareto Entropy
Author:
  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [48]
    • |
  • 相似文献 [20]
    • |
  • 引证文献
    • | |
  • 文章评论
    摘要:

    粒子群优化算法因形式简洁、收敛快速和参数调节机制灵活等优点，同时一次运行可得到多个解，且能逼近非凸或不连续的Pareto最优前端，因而被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法从单目标问题扩展到多目标问题时，Pareto最优解集的存储与维护、全局和个体最优解的选择以及开发与开采的平衡等问题亦随之出现.通过目标空间变换方法，采用Pareto前端在被称为平行格坐标系统的新目标空间中的分布熵及差熵评估种群的多样性及进化状态，并以此为反馈信息来设计进化策略，使得算法能够兼顾近似Pareto前端的收敛性和多样性.同时，引入格占优和格距离密度的概念来评估Pareto最优解的个体环境适应度，以此建立外部档案更新方法和全局最优解选择机制，最终形成了基于Pareto熵的多目标粒子群优化算法.实验结果表明：在IGD性能指标上，与另外8种对等算法相比，该算法在由ZDT和DTLZ系列组成的12个多目标测试问题集中表现出了显著的性能优势.

    Abstract:

    Due to its concise formation, fast convergence, and flexible parameters, particle swarm optimization (PSO) with the ability to gain multiple solutions at a run and to approximate the Pareto front of those non-convex or discontinuous multiobjective optimization problems (MOPs) is considered to be one of the most promising techniques for MOPs. However, several challenges, such as maintaining the archive, selecting the global and personal best solutions, and balancing the exploration and exploitation, occur when extending PSO from single-objective optimization problems to MOPs. In this paper, the distribution entropy and its difference of an approximate Pareto front in a new objective space, named parallel cell coordinate system (PCCS), are proposed to assess the diversity and evolutionary status of the population. The feedback information from evolutionary environment is served in the evolutionary strategies to balance the convergence and diversity of an approximate Pareto front. Meanwhile, the new concepts, such as cell dominance and individual density based on cell distance in the PCCS, are introduced to evaluate the individual environmental fitness which is the metric using in updating the archive and selecting the global best solutions. The experimental results illustrate that the proposed algorithm in this paper significantly outperforms the other eight peer competitors in terms of IGD on 12 test instances chosen from the ZDT and DTLZ test suites.

    参考文献
    [1] Kennedy J, Eberhart R. Particle swarm optimization. In: Proc. of the IEEE Int'l Conf. on Neural Networks. Piscataway: IEEE Service Center, 1995. 1942-1948. [doi: 10.1109/ICNN.1995.488968]
    [2] Coello Coello CA, Lechuga MS. MOPSO: A proposal for multiple objective particle swarm optimization. In: Fogel DB, ed. Proc. of the IEEE Congress on Evolutionary Computation (CEC 2002). Piscataway: IEEE Service Center, 2002. 1051-1056. [doi: 10. 1109/CEC.2002.1004388]
    [3] Coello Coello CA, Pulido GT, Lechuga MS. Handling multiple objectives with particle swarm optimization. IEEE Trans. on Evolutionary Computation, 2004,8(3):256-279. [doi: 10.1109/TEVC.2004.826067]
    [4] Reyes-Sierra M, Coello Coello CA. Multi-Objective particle swarm optimizers: A survey of the state-of-the-art. Int'l Journal of Computational Intelligence Research, 2006,2(3):287-308.
    [5] Padhye N, Branke J, Mostaghim S. Empirical comparison of MOPSO methods—Guide selection and diversity preservation. In: Tyrrell A, ed. Proc. of the IEEE Congress on Evolutionary Computation (CEC 2009). Piscataway: IEEE Service Center, 2009. 2516-2523. [doi: 10.1109/CEC.2009.4983257]
    [6] Padhye N. Comparison of archiving methods in multi-objective particle swarm optimization (MOPSO): Empirical study. In: Rothlauf F, ed. Proc. of the Genetic and Evolutionary Computation Conf. (GECCO 2009). New York: ACM Press, 2009. 1755-1756. [doi: 10.1145/1569901.1570143]
    [7] Gong MG, Jiao LC, Yang DD, Ma WP. Evolutionary multi-objective optimization algorithms. Ruan Jian Xue Bao/Journal of Software, 2009,20(2):271-289 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3483.htm [doi: 10.3724/SP.J. 1001.2009.03483]
    [8] Zhou AM, Qu BY, Li H, Zhao SZ, Suganthan PN, Zhang QF. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation, 2011,1(1):32-49. [doi: 10.1016/j.swevo.2011.03.001]
    [9] Reyes-Sierra M, Coello Coello CA. Improving PSO-based multiobjective optimization using crowding, mutation and ε- Dominance. In: Coello Coello CA, Aguirre AH, Zitzler E, eds. Proc. of the 3rd Int'l Conf. on Evolutionary Multi-Criterion Optimization (EMO 2005). Berlin: Springer-Verlag, 2005. 505-519. [doi: 10.1007/978-3-540-31880-4_35]
    [10] Li XD. Better spread and convergence: particle swarm multiobjective optimization using the maximin fitness. In: Deb K, Poli R, et al., eds. Proc. of the Genetic and Evolutionary Computation Conf. (GECCO 2004). New York: ACM Press, 2004. 117-128. [doi: 10.1007/978-3-540-24854-5_11]
    [11] Lei DM, Wu ZM. Pareto archive multi-objective particle swarm optimization. Pattern Recongnition and Artificial Intelligence, 2006,19(4):475-480 (in Chinese with English abstract). [doi: 10.3969/j.issn.1003-6059.2006.04.008]
    [12] Huang VL, Suganthan PN, Liang JJ. Comprehensive learning particle swarm optimizer for solving multiobjective optimization problems. Int'l Journal of Intelligence System, 2006,21(2):209-226.
    [13] Branke J, Mostaghim S. About selecting the personal best in multiobjective particle swarm optimization. In: Runarsson TP, Beyer HG, Burke E, Merelo-Guervos JJ, Whitley LD, Yao X, eds. Proc. of the Parallel Problem Solving from Nature (PPSN IX). LNCS, Berlin: Springer-Verlag, 2006. 523-532. [doi: 10.1007/11844297_53]
    [14] Abido A. Multiobjective particle swarm optimization with nondominated local and global sets. Nautral Computation, 2010,9(1): 747-766. [doi: 10.1007/s11047-009-9171-7]
    [15] Leong WF, Yen GG. PSO-Based multiobjective optimization with dynamic population size and adaptive local archives. IEEE Trans. on System, Man, Cybernetics, Part B, 2008,38(5):1270-1293. [doi: 10.1109/TSMCB.2008.925757]
    [16] Yen GG, Leong WF. Dynamic multiple swarms in multiobjective particle swarm optimization. IEEE Trans. on System, Man, Cybernetics, Part A, 2009,39(4):890-911. [doi: 10.1109/TSMCA.2009.2013915]
    [17] Liang JJ, Qu BY, Suganthan PN, Niu B. Dynamic multi-swarm particle swarm optimization for multi-objective optimization problems. In: Soule T, Moore JH, eds. Proc. of the Genetic and Evolutionary Computation Conf. (GECCO 2012). New York: ACM Press, 2012. 1-8. [doi: 10.1109/CEC.2012.6256416]
    [18] Daneshyari M, Yen GG. Constrained multiple-swarm particle swarm optimization within a cultural framework. IEEE Trans. on System, Man, Cybernetics, Part A, 2012,42(2):475-490. [doi: 10.1109/TSMCA.2011.2162498]
    [19] Daneshyari M, Yen GG. Cultural-Based multiobjective particle swarm optimization. IEEE Trans. on System, Man, Cybernetics, Part B, 2011,41(2):553-567. [doi: 10.1109/TSMCB.2010.2068046]
    [20] Kadkol AA, Yen GG. A cultural-based particle swarm optimization framework for dynamic, constrained multi-objective optimization. Int'l Journal of Swarm Intelligence Research, 2012,3(1):1-29. [doi: 10.4018/jsir.2012010101]
    [21] Cooren Y, Clerc M, Siarry P. MO-TRIBES, an adaptive multiobjective particle swarm optimization algorithm. Computational Optimization and Applications, 2011,49(2):379-400. [doi: 10.1007/s10589-009-9284-z]
    [22] Tang LX, Wang XP. A hybrid multiobjective evolutionary algorithm for multiobjective optimization problems. IEEE Trans. on Evolutionary Computation, 2013,17(1):20-45. [doi: 10.1109/TEVC.2012.2185702]
    [23] Liu DS, Tan KC, Goh CK, Ho WK. A multiobjective memetic algorithm based on particle swarm optimization. IEEE Trans. on System, Man, Cybernetics, Part B, 2007,37(1):42-50. [doi: 10.1109/TSMCB.2006.883270]
    [24] Zhan ZH, Zhang J, Li Y, Chung SH. Adaptive particle swarm optimization. IEEE Trans. on System, Man, Cybernetics, Part B, 2009,39(6):1362-1381. [doi: 10.1109/TSMCB.2009.2015956]
    [25] Inselberg A. The plane with parallel coordinates. Visual Computer, 1985,1(2):69-91. [doi: 10.1007/BF01898350]
    [26] Knowles JD, Corne DW. Approximating the nondominated front using the Pareto archived evolution strategy. Evolutionary Computation, 2000,8(1):149-172. [doi: 10.1162/106365600568167]
    [27] Deb K, Mohan M, Mishra S. A fast multi-objective evolutionary algorithm for finding well-spread pareto-optimal solutions. KanGAL Report, 2003002, Kanpur: Indian Institute of Technology (Kanpur), Kanpur Genetic Algorithms Laboratory (KanGAL), 2003.
    [28] Yang SX, Li MQ, Liu XH, Zheng JH. A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans, on Evolutionary Computation, 2013, 17(5):721-736. [doi: 10.1109/TEVC.2012.2227145]
    [29] Purshouse RC, Fleming JF. On the evolutionary optimization of many conflicting objectives. IEEE Trans. on Evolutionary Computation, 2007,11(6):770-784. [doi: 10.1109/TEVC.2007.910138]
    [30] Adra SF, Fleming PJ. Diversity management in evolutionary many-objective optimization. IEEE Trans. on Evolutionary Computation, 2011,15(2):770-784. [doi: 10.1109/TEVC.2010.2058117]
    [31] Lopez A, Coello Coello CA, Oyama A, Fujii K. An alternative preference relation to deal with many-objective optimization problems. In: Purshouse RC, Fleming PJ, Fonseca CM, Greco S, Shaw J, eds. Proc. of the 3rd Int'l Conf. on Evolutionary Multi- Criterion Optimization (EMO 2013). Berlin: Springer-Verlag, 2013. 291-306. [doi: 10.1007/978-3-642-37140-0_24]
    [32] Batista LS, Campelo F, Guimaraes FG, Ramirez JA. A comparison of dominance criteria in many-objective optimization problems. In: Proc. of the IEEE Congress on Evolutionary Computation (CEC 2011). Piscataway: IEEE Service Center, 2011. 2359-2366. [doi: 10.1109/CEC.2011.5949909]
    [33] Van den Bergh F. An analysis of particle swarm optimizers [Ph. D. Thesis]. Pretoria: University of Pretoria, 2002.
    [34] Ratnaweera A, Halgamuge S, Watson H. Self-Organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Trans. on Evolutionary Computation, 2004,8(3):240-255. [doi: 10.1109/TEVC.2004.826071]
    [35] Hu W, Li ZS. A simpler and more effective particle swarm optimization algorithms. Ruan Jian Xue Bao/Journal of Software, 2007, 18(4):861-868 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/18/861.htm [doi: 10.1360/jos180861]
    [36] Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: empirical results. Evolutionary Computation, 2000,8(2):173-195. [doi: 10.1162/106365600568202]
    [37] Deb K, Thiele L, Laumanns M, Zitzler E. Scalable multiobjective optimization test problems. In: Fogel DB, ed. Proc. of the IEEE Congress on Evolutionary Computation (CEC 2002). Piscataway: IEEE Service Center, 2002. 825-830. [doi: 10.1109/CEC.2002. 1007032]
    [38] Mostaghim S, Teich J. Strategies for finding good local guides in multi-objective particle swarm optimization (MOPSO). In: Proc. of the IEEE Swarm Intelligence Symp. (SIS 2003). Los Alamitos: IEEE Computer Society Press, 2003. 26-33. [doi: 10.1109/SIS. 2003.1202243]
    [39] Raquel CR, Nava PC. An effective use of crowding distance in multiobjective particle swarm optimization. In: Beyer HG, O'Reilly UM, eds. Proc. of the Genetic and Evolutionary Computation Conf. (GECCO 2005). New York: ACM Press, 2005. 257-264.
    [40] Pulido GT, Coello Coello CA. Using clustering techniques to improve the performance of a particle swarm optimizer. In: Deb K, Poli R, et al., eds. Proc. of the Genetic and Evolutionary Computation Conf. (GECCO 2004). New York: ACM Press, 2004. 225-237. [doi: 10.1007/978-3-540-24854-5_20]
    [41] Alvarez-Benitez JE, Everson RM, Fieldsend JE. A MOPSO algorithm based exclusively on Pareto dominance concepts. In: Coello Coello CA, Aguirre AH, Zitzler E, eds. Proc. of the 3rd Int'l Conf. on Evolutionary Multi-Criterion Optimization (EMO 2005). Berlin: Springer-Verlag, 2005. 459-473. [doi: 10.1007/978-3-540-31880-4_32]
    [42] Deb K, Pratap A, Agarwal S, Meyarivan T. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation, 2002,6(2):182-197. [doi: 10.1109/4235.996017]
    [43] Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm. Technical Report, TIK-Report 103, Zurich: Swiss Federal Institute of Technology (ETH), 2001.
    [44] Zhang QF, Li H. MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Trans. on Evolutionary Computation, 2007,11(6):712-731. [doi: 10.1109/TEVC.2007.892759]
    [45] Wolpert DH, Macready WG. No free lunch theorems for optimization. IEEE Trans. on Evolutionary Computation, 1997,1(1): 67-82. [doi: 10.1109/4235.585893]
    [46] Chow CK, Yuen SY. A multiobjective evolutionary algorithm that diversifies population by its density. IEEE Trans. on Evolutionary Computation, 2012,16(2):149-172. [doi: 10.1109/TEVC.2010.2098411]
    [47] Deb K, Jain S. Running performance metrics for evolutionary multi-objective optimization. Technical Report, 2002004, Kanpur: Indian Institute of Technology Kanpur, 2002.
    [48] Schott JR. Fault tolerant design using single and multicriteria genetic algorithm optimization [MS. Thesis]. Cambridge: Massachusetts Institute of Technology, 1995.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

胡旺,Gary G. YEN,张鑫.基于Pareto熵的多目标粒子群优化算法.软件学报,2014,25(5):1025-1050

复制
分享
文章指标
  • 点击次数:4336
  • 下载次数: 9459
  • HTML阅读次数: 1622
  • 引用次数: 0
历史
  • 收稿日期:2013-04-19
  • 最后修改日期:2013-09-09
  • 在线发布日期: 2014-05-04
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19937774位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号