基于MPI的并行多目标粒子群算法
|
摘要
为了进一步提高速度受限的多目标粒子群算法(SMPSO)求解多目标优化问题的效率和精度,文中提出基于消息传递接口(MPI)的并行化SMPSO算法(M-SMPSO).采用主从模式的MPI并行程序设计模式,将整个种群分成几个子种群,各子种群分别执行独立进化计算,提高算法效率.此外,为了均衡考虑算法的分布性与收敛性,提出自适应的全局最优解选择策略.使用标准测试函数验证算法性能,实验表明,相比其它多目标算法,文中算法能获得更高的加速比,更快收敛到多目标优化问题的Pareto前沿.
To improve the efficiency and accuracy of speed-constrained multi-objective particle swarm optimization( SMPSO),a parallelized SMPSO algorithm based on Message Passing Interface( MPI)( M-SMPSO) is proposed. The master-slave mode of MPI is used in the proposed algorithm. The entire population is divided into several sub-populations. Then, these sub-populations are evolved independently. In addition,an adaptive global optimal solution selection strategy is proposed to balance the distribution and convergence. Several standard test functions are adopted to verify the performance of the proposed algorithm. The experimental results show that ompared with other multi-objective algorithms,M-SMPSO obtains a higher speedup ratio and it converges quickly.
To improve the efficiency and accuracy of speed-constrained multi-objective particle swarm optimization( SMPSO),a parallelized SMPSO algorithm based on Message Passing Interface( MPI)( M-SMPSO) is proposed. The master-slave mode of MPI is used in the proposed algorithm. The entire population is divided into several sub-populations. Then, these sub-populations are evolved independently. In addition,an adaptive global optimal solution selection strategy is proposed to balance the distribution and convergence. Several standard test functions are adopted to verify the performance of the proposed algorithm. The experimental results show that ompared with other multi-objective algorithms,M-SMPSO obtains a higher speedup ratio and it converges quickly.
引文
[1]WANG H,YEN G G,LUO G C.Many-Objective Particle Swarm Optimization Using Two-Stage Strategy and Parallel Cell Coordinate System.IEEE Transactions on Cybernetics,2016,47(6):1446-1459.
[2]KENNEDY J,EBERHART R.Particle Swarm Optimization//Proc of the IEEE International Conference on Neural Networks.Washington,USA:IEEE,1995:1942-1948.
[3]COELLO C A C,LECHUGA M S.MOPSO:A Proposal for Multiple Objective Particle Swarm Optimization//Proc of the Congress on Evolutionary Computation.Washington,USA:IEEE,2002:1051-1056.
[4]刘衍民,牛奔,赵庆祯.基于交叉和变异的多目标粒子群算法.计算机应用,2011,31(1):82-84,117.(LIU Y M,NIU B,ZHAO Q Z.Multi-objective Particle Swarm Optimization Based on Crossover and Mutation.Journal of Computer Applications,2011,31(1):82-84,117.)
[5]李笠,王万良,徐新黎,等.基于网格排序的多目标粒子群优化算法.计算机研究与发展,2017,54(5):1012-1023.(LI L,WANG W L,XU X L,et al.Multi-objective Particle Swarm Optimization Based on Grid Ranking.Journal of Computer Research and Development,2017,54(5):1012-1023.)
[6]LIN Q Z,LIU S B,ZHU Q L,et al.Particle Swarm Optimization with a Balanceable Fitness Estimation for Many-Objective Optimization Problems.IEEE Transactions on Evolutionary Computation,2018,22(1):32-46.
[7]TANG B W,ZHU Z X,SHIN H S,et al.A Framework for Multiobjective Optimisation Based on a New Self-adaptive Particle Swarm Optimisation Algorithm.Information Sciences,2017,420:364-385.
[8]PAN A Q,WANG L,GUO W A,et al.A Diversity Enhanced Multiobjective Particle Swarm Optimization.Information Sciences,2018,436/437:441-465.
[9]ROBERGE V,TARBOUCHI M.Comparison of Parallel Particle Swarm Optimizers for Optimizers for Graphical Processing Units and Multicore Processors.International Journal of Computational Intelligence and Applications,2013,12(1):1942-1948.
[10]DEEP K,SHARMA S,PANT M.Modified Parallel Particle Swarm Optimization for Global Optimization Using Message Passing Interface//Proc of the 5th IEEE International Conference on Bio-inspired Computing:Theories and Applications.Washington,USA:IEEE,2010:1451-1458.
[11]TU K Y,LIANG Z C.Parallel Computation Models of Particle Swarm Optimization Implemented by Multiple Threads.Expert Systems with Applications,2011,38(5):5858-5866.
[12]ZHOU Y,TAN Y.GPU-Based Parallel Multi-objective Particle Swarm Optimization.International Journal of Artificial Intelligence,2011,7(A11):125-141.
[13]LI J Z,CHEN W N,ZHANG J,et al.A Parallel Implementation of Multiobjective Particle Swarm Optimization Algorithm Based on Decomposition//Proc of the IEEE Symposium Series on Computational Intelligence.Washington,USA:IEEE,2016:1310-1317.
[14]NEBRO A J,DURILLO J J,GARCIA-NIETO J,et al.SMPSO:A New PSO-Based Metaheuristic for Multi-objective Optimization//Proc of the IEEE Symposium on Computational Intelligence in Multi-criteria Decision-Making.Washington,USA:IEEE,2009:66-73.
[15]邱飞岳,莫雷平,江波,等.基于大规模变量分解的多目标粒子群优化算法研究.计算机学报,2016,39(12):2598-2613.(QIU F Y,MO L P,JIANG B,et al.Multi-objective Particle Swarm Optimization Algorithm Using Large Scale Variable Decomposition.Chinese Journal of Computers,2016,39(12):2598-2613.)
[16]公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究.软件学报,2009,20(2):271-289.(GONG M G,JIAO L C,YANG D D,et al.Research on Evolutionary Multi-objective Optimization Algorithms.Journal of Software,2009,20(2):271-289.)
[17]MOKARRAM V,BANAN M R.A New PSO-Based Algorithm for Multi-objective Optimization with Continuous and Discrete Design Variables.Structural and Multidisciplinary Optimization,2018,57(2):509-533.
[18]ATASHPENDAR A,DORRONSORO B,DANOY G,et al.A Scalable Parallel Cooperative Coevolutionary PSO Algorithm for Multiobjective Optimization.Journal of Parallel and Distributed Computing,2018,112:111-125.
[19]ABADLIA H,SMAIRI N,GHEDIRA K.A New Proposal for a Multi-objective Technique Using SMPSO and Tabu Search//Proc of the 15th IEEE/ACIS International Conference on Computer and Information Science.Washington,USA:IEEE,2016.DOI:10.1109/ICIS.2016.7550784.
[20]CAO B,ZHAO J W,LZ H,et al.Distributed Parallel Particle Swarm Optimization for Multi-objective and Many-Objective LargeScale Optimization.IEEE Access,2017,5:8214-8221.
[21]NGUYEN L,XUAN H N,BUI L T.Performance Measurement for Interactive Multi-objective Evolutionary Algorithms//Proc of the7th International Conference on Knowledge and Systems Engineering.Washington,USA:IEEE,2015:302-305.
[2]KENNEDY J,EBERHART R.Particle Swarm Optimization//Proc of the IEEE International Conference on Neural Networks.Washington,USA:IEEE,1995:1942-1948.
[3]COELLO C A C,LECHUGA M S.MOPSO:A Proposal for Multiple Objective Particle Swarm Optimization//Proc of the Congress on Evolutionary Computation.Washington,USA:IEEE,2002:1051-1056.
[4]刘衍民,牛奔,赵庆祯.基于交叉和变异的多目标粒子群算法.计算机应用,2011,31(1):82-84,117.(LIU Y M,NIU B,ZHAO Q Z.Multi-objective Particle Swarm Optimization Based on Crossover and Mutation.Journal of Computer Applications,2011,31(1):82-84,117.)
[5]李笠,王万良,徐新黎,等.基于网格排序的多目标粒子群优化算法.计算机研究与发展,2017,54(5):1012-1023.(LI L,WANG W L,XU X L,et al.Multi-objective Particle Swarm Optimization Based on Grid Ranking.Journal of Computer Research and Development,2017,54(5):1012-1023.)
[6]LIN Q Z,LIU S B,ZHU Q L,et al.Particle Swarm Optimization with a Balanceable Fitness Estimation for Many-Objective Optimization Problems.IEEE Transactions on Evolutionary Computation,2018,22(1):32-46.
[7]TANG B W,ZHU Z X,SHIN H S,et al.A Framework for Multiobjective Optimisation Based on a New Self-adaptive Particle Swarm Optimisation Algorithm.Information Sciences,2017,420:364-385.
[8]PAN A Q,WANG L,GUO W A,et al.A Diversity Enhanced Multiobjective Particle Swarm Optimization.Information Sciences,2018,436/437:441-465.
[9]ROBERGE V,TARBOUCHI M.Comparison of Parallel Particle Swarm Optimizers for Optimizers for Graphical Processing Units and Multicore Processors.International Journal of Computational Intelligence and Applications,2013,12(1):1942-1948.
[10]DEEP K,SHARMA S,PANT M.Modified Parallel Particle Swarm Optimization for Global Optimization Using Message Passing Interface//Proc of the 5th IEEE International Conference on Bio-inspired Computing:Theories and Applications.Washington,USA:IEEE,2010:1451-1458.
[11]TU K Y,LIANG Z C.Parallel Computation Models of Particle Swarm Optimization Implemented by Multiple Threads.Expert Systems with Applications,2011,38(5):5858-5866.
[12]ZHOU Y,TAN Y.GPU-Based Parallel Multi-objective Particle Swarm Optimization.International Journal of Artificial Intelligence,2011,7(A11):125-141.
[13]LI J Z,CHEN W N,ZHANG J,et al.A Parallel Implementation of Multiobjective Particle Swarm Optimization Algorithm Based on Decomposition//Proc of the IEEE Symposium Series on Computational Intelligence.Washington,USA:IEEE,2016:1310-1317.
[14]NEBRO A J,DURILLO J J,GARCIA-NIETO J,et al.SMPSO:A New PSO-Based Metaheuristic for Multi-objective Optimization//Proc of the IEEE Symposium on Computational Intelligence in Multi-criteria Decision-Making.Washington,USA:IEEE,2009:66-73.
[15]邱飞岳,莫雷平,江波,等.基于大规模变量分解的多目标粒子群优化算法研究.计算机学报,2016,39(12):2598-2613.(QIU F Y,MO L P,JIANG B,et al.Multi-objective Particle Swarm Optimization Algorithm Using Large Scale Variable Decomposition.Chinese Journal of Computers,2016,39(12):2598-2613.)
[16]公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究.软件学报,2009,20(2):271-289.(GONG M G,JIAO L C,YANG D D,et al.Research on Evolutionary Multi-objective Optimization Algorithms.Journal of Software,2009,20(2):271-289.)
[17]MOKARRAM V,BANAN M R.A New PSO-Based Algorithm for Multi-objective Optimization with Continuous and Discrete Design Variables.Structural and Multidisciplinary Optimization,2018,57(2):509-533.
[18]ATASHPENDAR A,DORRONSORO B,DANOY G,et al.A Scalable Parallel Cooperative Coevolutionary PSO Algorithm for Multiobjective Optimization.Journal of Parallel and Distributed Computing,2018,112:111-125.
[19]ABADLIA H,SMAIRI N,GHEDIRA K.A New Proposal for a Multi-objective Technique Using SMPSO and Tabu Search//Proc of the 15th IEEE/ACIS International Conference on Computer and Information Science.Washington,USA:IEEE,2016.DOI:10.1109/ICIS.2016.7550784.
[20]CAO B,ZHAO J W,LZ H,et al.Distributed Parallel Particle Swarm Optimization for Multi-objective and Many-Objective LargeScale Optimization.IEEE Access,2017,5:8214-8221.
[21]NGUYEN L,XUAN H N,BUI L T.Performance Measurement for Interactive Multi-objective Evolutionary Algorithms//Proc of the7th International Conference on Knowledge and Systems Engineering.Washington,USA:IEEE,2015:302-305.