GPU上的维度并行随机吸引策略萤火虫算法

计算机工程与科学

GPU上的维度并行随机吸引策略萤火虫算法

刘金1，2，吴志健1，2，吴双可2，王晖3，邓长寿4

（1.武汉大学软件工程国家重点实验室，湖北武汉 430072；2.武汉大学计算机学院，湖北武汉 430072；

3.南昌工程学院信息工程学院，江西南昌 330099；4.九江学院信息科学与技术学院，江西九江 332005）

收稿日期:2015-05-28 修回日期:2015-10-20 出版日期:2016-10-25 发布日期:2016-10-25
基金资助:
国家自然科学基金（61305150,61364025,61070008）；江西省自然科学基金（20142BAB217020）；南通市科技局应用研究项目（BK2014057）

A dimensionally parallel firefly algorithm

with random attraction on GPU

LIU Jin1，2，WU Zhijian1，2，WU Shuangke1，2，WANG Hui3，DENG Changshou4

（1.State Key Laboratory of Software Engineering,Wuhan University,Wuhan 430072;

2.School of Computer,Wuhan University,Wuhan 430072;

3.School of Information Engineering,Nanchang Institute of Technology,Nanchang 330099;

4.School of Information Science and Technology,Jiujiang University,Jiujiang 332005,China）

Received:2015-05-28 Revised:2015-10-20 Online:2016-10-25 Published:2016-10-25

摘要/Abstract

摘要：

随机吸引策略萤火虫算法是一种元启发式优化算法。它优化了标准萤火虫算法，不仅降低了其时间复杂度，而且提高了其优化能力。高维全局优化问题的求解是一个非常耗时的过程，为了减少优化高维问题所需时间，进一步简化了随机吸引策略萤火虫算法，降低了时间复杂度，同时设计了一种维度并行策略，提出了GPU上的维度并行随机吸引策略萤火虫算法。实验结果表明，本算法保持了随机吸引策略萤火虫算法的优化能力，且加速效果明显。

关键词: 萤火虫算法, CUDA, 并行化

Abstract:

The firefly algorithm (FA) with random attraction is a metaheuristic optimization algorithm. It optimizes the standard FA, reduces the computation time complexity and improves the optimization ability of the standard FA. Solving highdimensional global optimization problem is time consuming. So to reduce the time for solving highdimensional global optimization problems, we simplify the firefly algorithm with random attraction further, and propose a dimensionparallel firefly algorithm with random attraction on GPU. Experimental results show that the proposed algorithm can reduce the computation time effectively while remaining the same optimization ability as the firefly algorithm with random attraction.

Key words: firefly algorithm, CUDA, parallelization

刘金1，2，吴志健1，2，吴双可2，王晖3，邓长寿4. GPU上的维度并行随机吸引策略萤火虫算法[J]. 计算机工程与科学.

LIU Jin1，2，WU Zhijian1，2，WU Shuangke1，2，WANG Hui3，DENG Changshou4.

A dimensionally parallel firefly algorithm

with random attraction on GPU

[J]. Computer Engineering & Science.

参考文献

［1］Zang H,Zhang S,Hapeshi K.A review of natureinspired algorithms［J］.Journal of Bionic Engineering,2010,7（3）:S232S237.

［2］Zhang Changsheng, Sun Jigui, Ouyang Dantong, et al. A selfadaptive hybrid particle swarm optimization algorithm for flow shop scheduling problem［J］.Chinese Journal of Computers,2009,32（11）:21372146.（in Chinese）

［3］Ji Junzhong,Huang Zhen,Liu Chunnian,et al.An ant colony algorithm based on multiplegrain representation for the traveling salesman problems［J］.Journal of Computer Research and Development，2010,47（3）:434444.（in Chinese）

［4］Kennedy J, Eberhart R. Particle swarm optimization［C］∥Proc of IEEE International Conference on Neural Networks,1995:19421948.

［5］Dorigo M.The ant system:Optimization by a colony of cooperating agents［J］.IEEE Transactions on Cybernetics,1996,26（1）:2941.

［6］Karaboga D,Basturk B.A powerful and efficient algorithm for numerical function optimization:Artificial bee colony （ABC） algorithm［J］.Journal of Global Optimization,2007,39（3）:459471.

［7］Yang X S,Deb S.Cuckoo search via Lévy flights［C］∥Proc of
IEEE World Congress on Nature & Biologically Inspired Computing,2009:210214.

［8］Yang X S.Firefly algorithm,stochastic test functions and design optimisation［J］.International Journal of BioInspired Computation,2010,2（2）:7884.

［9］Wang H, Wu Z J, Sun H, et al. Firefly algorithm with random attraction［J］.International Journal of BioInspired Computation,2013,1（1/2/3）:4351.

［10］Wang H, Wu Z J, Rahnamayan S. Enhanced oppositionbased differential evolution for solving highdimensional continuous optimization problems.［J］.Soft Computing,2011,15（11）:21272140.

［11］Yang Z,Tang K,Yao X.Scalability of generalized adaptive differential evolution for largescale continuous optimization［J］.Soft Computing,2011,15（11）:21412155.

［12］Zhao S Z,Suganthan P N,Das S.Selfadaptive differential evolution with multitrajectory search for largescale optimization［J］.Soft Computing,2011,15（11）:21752185.

［13］Yang Jun,Cao Jing,Zhang Zhengxiao,et al.A parallelized multiscale retinex video enhancement algorithm based on CUDA［J］.Computer Engineering & Science,2012,34（4）:3742.（in Chinese）

［14］Du P,Zhao J Y,Pan W B,et al.GPU accelerated realtime collision handling in virtual disassembly［J］.Journal of Computer Sciences & Technology,2015,30(3):511518.

［15］Qin Jin,Gong Chunye,Hu Qingfeng,et al.Optimization of sparse diagonal matrixvector multiplication based on the CUDA program model［J］.Computer Engineering & Science,2012,34（7）:7883.（in Chinese）

［16］Zhao Ruibin,Zhao Shenghui,Hu Xinli.A CPUGPU collaboration based computing parallel algorithm for MTF degradation of remote sensing simulation images［J］.Computer Engineering & Science,2015,37（7）:12581264.（in Chinese）

［17］Gandomi A H,Yang X S,Talatahari S,et al.Firefly algorithm with chaos［J］.Communications in Nonlinear Science & Numerical Simulation,2013,18（1）:8998.

附中文参考文献：

［2］张长胜,孙吉贵,欧阳丹彤，等.求解车间调度问题的自适应混合粒子群算法［J］.计算机学报,2009,32（11）:21372146.

［3］冀俊忠,黄振,刘椿年，等.基于多粒度的旅行商问题描述及其蚁群优化算法［J］.计算机研究与发展,2010,47（3）:434444.

［13］杨军,曹静,张正孝，等.基于CUDA的并行多尺度Retinex视频增强算法［J］.计算机工程与科学,2012,34（4）:3742.

［15］秦晋,龚春叶,胡庆丰，等.基于CUDA编程模型的稀疏对角矩阵向量乘优化［J］.计算机工程与科学,2012,34（7）:7883.

［16］赵瑞斌,赵生慧,胡新礼.CPUGPU协同计算的遥感仿真图像MTF退化并行算法［J］.计算机工程与科学,2015,37（7）:12581264.

[1]	苏丽，孙彦猛，张博为，杨先博，朱颖. 一种基于Hadoop+CUDA实现相关器的方法[J]. J4, 20160101, 38(01): 46-51.
[2]	陈强, 谭林, 王云丽, 肖靖. 工业区块链中基于CUDA的数据并行处理方法[J]. 计算机工程与科学, 2022, 44(12): 2102-2110.
[3]	仲臣, 余学祥, 邰晓曼, 韩雨辰, 肖星星, 刘清华, . 萤火虫算法优化支持向量机室内定位研究[J]. 计算机工程与科学, 2022, 44(11): 1968-1975.
[4]	曹良林, 贲可荣, 张献. 基于代理辅助多目标萤火虫算法的软件缺陷预测方法研究[J]. 计算机工程与科学, 2022, 44(02): 257-265.
[5]	左宪禹1,2，张哲1,5，黄祥志4,5，葛强1,2，张理涛3，臧文乾4,5. 一种适用于GPU图像处理算法的合并存储结构[J]. 计算机工程与科学, 2020, 42(02): 197-202.
[6]	杨青1,2,3，张亚文1,2，张琴1，袁佩玲1. 基于Hadoop的多维关联规则挖掘算法研究及应用[J]. 计算机工程与科学, 2019, 41(12): 2127-2133.
[7]	何登平1，2，3，何宗浩1,2，李培强1,2. 基于Spark的并行化高效用项集挖掘算法[J]. 计算机工程与科学, 2019, 41(10): 1723-1730.
[8]	段兴锋1,2,任鸿翔1,神和龙1. 基于CUDA的弱可压SPH流体建模与仿真[J]. 计算机工程与科学, 2018, 40(08): 1375-1382.
[9]	陶晓玲1,2,亢蕊楠3，刘丽燕3. 基于选择性集成的并行多分类器融合方法[J]. 计算机工程与科学, 2018, 40(05): 787-792.
[10]	东桥，郭敏. 基于萤火虫算法的温度场重建[J]. 计算机工程与科学, 2018, 40(01): 159-164.
[11]	张敏华,张剑贤,裘雪红,周端. 基于OpenCL 的JPEG压缩算法并行化设计与实现[J]. 计算机工程与科学, 2017, 39(05): 860-.
[12]	谭延丹，易会战，张鹏. 面向多核体系结构的并行迭代编译技术研究[J]. 计算机工程与科学, 2017, 39(03): 436-442.
[13]	侯泳旭1,段磊1,2,秦江龙3,秦攀1,唐常杰1. 基于Isolation Forest的并行化异常探测设计[J]. 计算机工程与科学, 2017, 39(02): 236-244.
[14]	李帅1，吴斌2，杜修明3，陈玉峰3. 基于Spark的BIRCH算法并行化的设计与实现[J]. 计算机工程与科学, 2017, 39(01): 35-41.
[15]	陆克中1,2，孙俊3. 全局信息共享的自适应FA算法[J]. J4, 2016, 38(06): 1164-1170.