基于OpenMP求解无容量设施选址问题的并行PSO算法  

OpenMP-based Multi-population PSO Algorithm to Solve the Uncapacitated Facility Location Problem

作　　者：王大志[1] 闫杨[1] 汪定伟[1] 王洪峰[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110004

出　　处：《东北大学学报（自然科学版）》2008年第12期1681-1684,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金重点项目(70431003);国家创新研究群体科学基金资助项目(60521003);国家科技支撑计划项目(2006BAH02A09)

摘　　要：讨论无容量设施选址(UFL)问题,提出了一个基于OpenMP技术的并行多粒子群优化(PSO)算法.将整个种群分为若干子种群,同时利用局部信息来更新粒子速度,使得并行算法异步进行.算法运行一定代数后,每个子种群都会与其相邻种群交换最优粒子.通过将并行多粒子群算法对OR-library中的标准测试问题进行测试,并将计算结果与串行多粒子群算法的计算结果进行比较.相比之下,并行多粒子群算法执行时间短,特别对于大规模的计算问题,所得结果有更好的鲁棒性.The OpenMP-based parallel multi-population particle swarm optimization （PSO） algorithm to solve the uncapacitated facility location （UFL） problem. The parallel algorithm is operating asynchronously by dividing the whole particle swarm into several sub-swarm and the particle velocity is updated with a variety of local optima. Every sub-swarm exchange its optimal particle with its neighboring swarm after the algorithm operated for a certain number of generations. The parallel multi-population PSO （PMPSO） algorithm is applied to several benchmark suits collected from OR-library, and the results are compared to that of the serial multi-population PSO. It is found that the parallel multi-population PSO is time saving in execution, especially in the large scale computation it will provide higher robustness.

关 键 词：粒子群算法 无容量设施选址问题 并行计算 OPENMP 多种群 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]