Parallel particle swarm optimization algorithm in multicore computing environment

doi:10.11772/j.issn.1001-9081.2015.09.2482

Journal of Computer Applications ›› 2015, Vol. 35 ›› Issue (9): 2482-2485.DOI: 10.11772/j.issn.1001-9081.2015.09.2482

Previous Articles Next Articles

Parallel particle swarm optimization algorithm in multicore computing environment

HE Li¹, LIU Xiaodong¹, LI Songyang¹, ZHANG Qian²

1. School of Computer, Henan Institute of Engineering, Zhengzhou Henan 451191, China;
2. School of Materials and Chemical Engineering, Henan Institute of Engineering, Zhengzhou Henan 451191, China

Received:2015-04-15 Revised:2015-06-11 Online:2015-09-10 Published:2015-09-17

多核环境下并行粒子群算法

何莉¹, 刘晓东¹, 李松阳¹, 张倩²

1. 河南工程学院计算机学院, 郑州 451191;
2. 河南工程学院材料与化学工程学院, 郑州 451191

通讯作者: 何莉(1982-),男,江西萍乡人,讲师,博士,CCF会员,主要研究方向:智能计算、物联网,engineerheli@126.com
作者简介:刘晓东(1981-),男,河南林州人,讲师,博士,主要研究方向:云计算、并行计算;李松阳(1985-),男,河南南阳人,讲师,博士,主要研究方向:群体智能、虚拟植物;张倩(1982-),女,河南驻马店人,讲师,博士,主要研究方向:晶体合成、物联网。
基金资助:
国家自然科学基金青年项目(61301232);河南省教育厅科学技术研究重点项目(13A520148);河南工程学院博士基金资助项目(D2012016)。

Abstract

Abstract: Aiming at the problem that serial Particle Swarm Optimization (PSO) algorithms are time-consuming to deal with big tasks, a novel shared parallel PSO (Shared-PSO) algorithm was proposed. The multi-core processing power was used to reduce time to get resolution. In order to facilitate communication of particles, a shared area was set up and a random strategy was applied to switch particles. Several serial PSO algorithms could be permitted to update particle information because of the universality of its algorithm flow. Shared-PSO was applied on the standard optimization test set CEC (Congress on Evolutionary Computation) 2014. The experiment results show that the execution time of Shared-PSO is a quarter of the serial PSO's. The proposed algorithm can effectively improve the execution efficiency of serial PSO, and expand applied range of PSO.

Key words: parallel Particle Swarm Optimization (PSO), multicore computing, parallel algorithm, optimization, swarm intelligence

摘要： 针对串行粒子群算法在解决大任务耗时过长的问题,提出一种共享并行粒子群(Shared-PSO)算法。充分利用多核处理能力缩短问题处理运行时间,设置共享区和采取粒子随机替换策略有效促进粒子信息的交流,其算法流程具有较好的通用性,允许利用多种串行粒子群算法完成粒子信息更新工作。在标准优化测试集CEC 2014上的实验结果显示新算法的执行时间是串行算法的1/4。新算法能够有效地改善串行粒子群的执行效率,扩展粒子群算法的应用范围。

关键词: 并行粒子群算法, 多核计算, 并行算法, 最优化, 群智能

CLC Number:

TP301.6

HE Li, LIU Xiaodong, LI Songyang, ZHANG Qian. Parallel particle swarm optimization algorithm in multicore computing environment[J]. Journal of Computer Applications, 2015, 35(9): 2482-2485.

何莉, 刘晓东, 李松阳, 张倩. 多核环境下并行粒子群算法[J]. 计算机应用, 2015, 35(9): 2482-2485.

References

[1] KENNEDY J, EBERHART R. Particle swarm optimization [C]//Proceedings of the International Conference on Neural Networks. Piscataway: IEEE, 1995:1942-1948.
[2] DORIGO M, BIRATTARI M, STUTZLE T. Ant colony optimization [J]. IEEE Computational Intelligence Magazine, 2006,1(4):28-39.
[3] KARABOGA D, GORKEMLI B, OZTURK C, et al. A comprehensive survey: Artificial Bee Colony (ABC) algorithm and applications [J]. Artificial Intelligence Review, 2014,42(1):21-57.
[4] KENNEDY J, EBERHART R C. A discrete binary version of the particle swarm algorithm [C]//Proceedings of the IEEE International Conference on Computational Cybernetics and Simulation. Piscataway: IEEE, 1997:4104-4108.
[5] NEZAMABADI-POUR H, ROSTAMI-SHARBABAKI M, MAGHFOORI-FARSANGI M. Binary particle swarm optimization: challenges and new solutions [J]. Journal of Computer Society of Iran (CSI) on Computer Science and Engineering (JCSE), 2008,6(1-A):21-32.
[6] del VALLE Y, VENAYAGAMOORTHY G K, MOHAGHEGHI S, et al. Particle swarm optimization: basic concepts, variants and applications in power systems [J]. IEEE Transactions on Evolutionary Computation, 2008,12(2):171-195.
[7] XI M, SHENG X, SUN J. Quantum-behaved particle swarm optimization algorithm with crossover operator to multi-dimension problems [J]. Journal of Computer Applications, 2015,35(3):680-684.(奚茂龙,盛歆漪,孙俊.基于多维问题的交叉算子量子粒子群优化算法[J].计算机应用,2015,35(3):680-684.)
[8] CHEN S. Improved particle swarm optimization algorithm based on centroid and self-adaptive exponential inertia weight [J]. Journal of Computer Applications, 2015,35(3):675-679.(陈寿文.基于质心和自适应指数惯性权重改进的粒子群算法[J].计算机应用,2015,35(3):675-679.)
[9] XU J, LU H, SHI G. Application of restricted velocity particle swarm optimization and self-adaptive velocity particle swarm optimization to unconstrained optimization problem [J]. Journal of Computer Applications, 2015,35(3):668-674.(许君,鲁海燕,石桂娟.限制速度粒子群优化和自适应速度粒子群优化在无约束优化问题中的应用[J].计算机应用,2015,35(3):668-674.)
[10] LALWANI S, SINGHAL S, KUMAR R, et al. A comprehensive survey: Applications of Multi-Objective Particle Swarm Optimization (MOPSO) algorithm[J]. Transactions on Combinatorics, 2013,2(1):39-101.
[11] TU K, LIANG Z. Parallel computation models of particle swarm optimization implemented by multiple threads [J]. Expert Systems with Applications, 2011,38(5):5858-5866.
[12] MUSSI L, DAOLIO F, CAGNONI S. Evaluation of parallel particle swarm optimization algorithms within the CUDA architecture [J]. Information Sciences, 2011,181(20):4642-4657.
[13] WAINTRAUB M, SCHIRRU R, PEREIRA C M N A. Multiprocessor modeling of parallel particle swarm optimization applied to nuclear engineering problems [J]. Progress in Nuclear Energy, 2009,51(6/7):680-688.
[14] ALBA E, TOMASSINI M. Parallelism and evolutionary algorithms [J]. IEEE Transactions on Evolutionary Computation, 2002,6(5):443-462.
[15] CLERC M. Standard particle swarm optimisation from 2006 to 2011 [EB/OL]. [2015-01-08]. https://hal.archives-ouvertes.fr/hal-00764996.
[16] AB AZIZ N A, MUBIN M, MOHAMAD M S, et al. A synchronous-asynchronous particle swarm optimisation algorithm [J]. The Scientific World Journal, 2014,2014:1-17.
[17] LIANG J J, QU B Y, SUGANTHAN P N. Problem definitions and evaluation criteria for the CEC 2014 special session and competition on single objective real-parameter numerical optimization [EB/OL]. [2015-01-06]. http://web.mysites.ntu.edu.sg/epnsugan/PublicSite/Shared%20Documents/CEC-2014/Definitions%20of%20%20CEC2014%20benchmark%20suite%20Part%20A.pdf.
[18] ZAMBRANO-BIGIARINI M, CLERC M, ROJAS R. Standard particle swarm optimisation 2011 at CEC-2013: a baseline for future PSO improvements [C]//Proceedings of the IEEE Congress on Evolutionary Computation. Piscataway: IEEE, 2013:2337-2344.

Parallel particle swarm optimization algorithm in multicore computing environment

多核环境下并行粒子群算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	CHEN Jun, HE Qing. Improved butterfly optimization algorithm based on cosine similarity [J]. Journal of Computer Applications, 2021, 41(9): 2668-2677.
[2]	NIU Ruihua, YANG Jun, XING Lanxin, WU Renbiao. Micro-expression recognition algorithm based on convolutional block attention module and dual path networks [J]. Journal of Computer Applications, 2021, 41(9): 2552-2559.
[3]	LI Kairong, LIU Shuang, HU Qianqian, TANG Yiyuan. Improved ant colony optimization algorithm for path planning based on turning angle constraint [J]. Journal of Computer Applications, 2021, 41(9): 2560-2568.
[4]	LI Mengmeng, QIN Wei, LIU Yi, DIAO Xingchun. Hybrid ant colony optimization algorithm with brain storm optimization [J]. Journal of Computer Applications, 2021, 41(8): 2412-2417.
[5]	LUO Mingyu, LUO Xiaomeng, ZHU Wenmin, ZHANG Lei, FAN Xiumin. Modeling technology for maintenance posture of virtual human in narrow space of ship [J]. Journal of Computer Applications, 2021, 41(8): 2466-2472.
[6]	ZHANG Wenqiang, XING Zheng, YANG Weidong. Hybrid particle swarm optimization with multi-region sampling strategy to solve multi-objective flexible job-shop scheduling problem [J]. Journal of Computer Applications, 2021, 41(8): 2249-2257.
[7]	TANG Andi, HAN Tong, XU Dengwu, XIE lei. Chaotic elite Harris hawks optimization algorithm [J]. Journal of Computer Applications, 2021, 41(8): 2265-2272.
[8]	ZHANG Meng, GUO Jianquan. Channel structure choice of closed-loop supply chain under uncertain demand and recovery [J]. Journal of Computer Applications, 2021, 41(7): 2100-2107.
[9]	TANG Andi, HAN Tong, XU Dengwu, XIE Lei. Path planning method of unmanned aerial vehicle based on chaos sparrow search algorithm [J]. Journal of Computer Applications, 2021, 41(7): 2128-2136.
[10]	ZHAO Qiuyun, WEI Le, SHU Hongping. Construction method of cloud manufacturing virtual workshop for manufacturing tasks [J]. Journal of Computer Applications, 2021, 41(7): 2003-2011.
[11]	YANG Zhen, MA Jianxiao, WANG Baojie. Signal timing optimization model of dual-ring phase under condition of setting waiting area [J]. Journal of Computer Applications, 2021, 41(7): 2108-2112.
[12]	ZHANG Xiangfei, LU Yuming, ZHANG Pingsheng. Constrained multi-objective optimization algorithm based on coevolution [J]. Journal of Computer Applications, 2021, 41(7): 2012-2018.
[13]	WANG Yu, LIU Yanli, CHEN Shaowu. Maximum common induced subgraph algorithm based on vertex conflict learning [J]. Journal of Computer Applications, 2021, 41(6): 1756-1760.
[14]	CHENG Meiying, QIAN Qian, NI Zhiwei, ZHU Xuhui. Self-organized migrating algorithm for multi-task optimization with information filtering [J]. Journal of Computer Applications, 2021, 41(6): 1748-1755.
[15]	CAI Ruiguang, ZHANG Desheng, XIAO Yanting. Parameter independent weighted local mean-based pseudo nearest neighbor classification algorithm [J]. Journal of Computer Applications, 2021, 41(6): 1694-1700.