Fruit fly optimization algorithm based on simulated annealing

doi:10.11772/j.issn.1001-9081.2016.11.3118

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (11): 3118-3122.DOI: 10.11772/j.issn.1001-9081.2016.11.3118

Previous Articles Next Articles

Fruit fly optimization algorithm based on simulated annealing

ZHANG Bin, ZHANG Damin, A Minghan

College of Big Data and Information Engineering, Guizhou University, Guiyang Guizhou 550025, China

Received:2016-05-20 Revised:2016-06-14 Online:2016-11-10 Published:2016-11-12
Supported by:
This work is partially supported by the Cooperation Project of Guizhou Province (QKHJSH[2012]7002, QKHJSH[2014]7002), the Graduate Innovation Fund Project of Guizhou University (Research Institute of Technology2016069).

基于模拟退火的果蝇优化算法

张斌, 张达敏, 阿明翰

贵州大学大数据与信息工程学院, 贵阳 550025

通讯作者: 张达敏
作者简介:张斌(1990-),男,河南南阳人,硕士研究生,主要研究方向:优化计算、数据挖掘;张达敏(1967-),男,贵州贵阳人,教授,博士,主要研究方向:优化计算、网络拥塞控制;阿明翰(1992-),男,吉林白山人,硕士研究生,主要研究方向:数据挖掘、推荐系统。
基金资助:
贵州省合作计划项目（黔科合计省合[2012]7002号，黔科合计省合[2014]7002号）；贵州大学研究生创新基金资助项目（研理工2016069）。

Abstract

Abstract: Concerning the defects of low optimization precision and easy to fall into local optimum in Fruit Fly Optimization Algorithm (FOA), a Fruit Fly Optimization Algorithm based on Simulated Annealing (SA-FOA) was proposed. The receiving mechanism of solution and the optimal step size were improved in SA-FOA. The receiving probability was based on the generalized Gibbs distribution and the receiving of solution met Metropolis criterion. The step length decreased with the increasing iteration according to non-uniform variation idea. The simulation result using several typical test functions show that the improved algorithm has high capability of global searching. Meanwhile, the optimization accuracy and convergence rate are also improved greatly. Therefore, it can be used to optimize the parameters of neural network and service scheduling models.

Key words: Fruit Fly Optimization Algorithm (FOA), annealing algorithm, optimal step size, receiving probability, convergence rate

摘要： 针对果蝇算法（FOA）寻优精度不高且易陷入局部最优的缺陷，提出了一种基于模拟退火思想的果蝇优化算法（SA-FOA）。所提算法对解的接收机制和寻优步长进行了改进：以广义的Gibbs分布产生的概率为接收概率，解的接收满足Metropolis准则；参考非均匀变异的思想，使步长随迭代次数的增加逐渐减小。通过对几种典型测试函数的仿真表明，改进算法具有较强的全局搜索能力，同时寻优精度和收敛速度比果蝇算法也有较大的提高。因此，可以用改进算法对神经网络和服务调度问题的参数进行优化。

关键词: 果蝇算法, 模拟退火, 寻优步长, 接收概率, 收敛速度

CLC Number:

TP301

ZHANG Bin, ZHANG Damin, A Minghan. Fruit fly optimization algorithm based on simulated annealing[J]. Journal of Computer Applications, 2016, 36(11): 3118-3122.

张斌, 张达敏, 阿明翰. 基于模拟退火的果蝇优化算法[J]. 计算机应用, 2016, 36(11): 3118-3122.

References

[1] PAN W T. A new fruit fly optimization algorithm:taking the financial distress model as an example[J]. Knowledge Based System,2012, 26(2):69-74.
[2] PAN W T. Using modified fruit fly optimization algorithm to perform the function test and case studies[J].Connection Science, 2013, 25(2/3):151-160.
[3] CHEN P W, LIN W Y, HUANG T H, et al. Using fruit fly optimization algorithm optimized grey model neural network to perform satisfaction analysis for E-business service[J]. Applied Mathematics & Information Sciences, 2013, 7(2L):459-465.
[4] ISCAN H, GUNDUZ M. Parameter analysis on fruit fly optimization algorithm[J]. Journal of Computer & Communications,2016,2(4):137-141.
[5] PAN Q K, SANG H Y, DUAN J H, et al. An improved fruit fly optimization algorithm for continuous function optimization problems[J]. Knowledge Based System, 2014,62(5):69-83.
[6] 吴小文,李擎.果蝇算法和5种群智能算法的寻优性能研究[J].火力与指挥控制,2013,38(4):17-20.(WU X W, LI Q. Research of optimizing performance of fruit fly optimization algorithm and five kinds of intelligent algorithm[J]. Fire Control & Command Control,2013, 38(4):17-20.)
[7] 杨书佺,舒勤,何川.改进的果蝇算法及其在PPI网络中的应用[J].计算机应用与软件,2014,31(12):291-294.(YANG S Q,SHU Q, HE C. A modified fruit fly algorithm and its application in PPI network[J].Computer Applications and Software, 2014,31(12):291-294.)
[8] 宁剑平,王冰,李洪儒,等.递减步长果蝇优化算法及应用[J].深圳大学学报(理工版),2014,31(4):367-373.(NING J P, WANG B, LI H R, et al. Research on and application of diminishing step fruit fly optimization algorithm[J].Journal of Shenzhen University (Science and Engineering), 2014,31(4):367-373.)
[9] 韩俊英,刘成忠.自适应调整参数的果蝇优化算法[J].计算机工程与应用,2014,50(7):50-55.(HAN J Y, LIU C Z. Fruit fly optimization algorithm with adaptive parameter[J]. Computer Engineering and Applications, 2014, 50(7):50-55.)
[10] 曹磊,叶春明,包晓晓.改进果蝇算法求解带有学习效应的PFSP[J].数学理论与应用,2015,35(1):103-114.(CAO L,YE C M, BAO X X. An improved fruit optimization fly algorithm for solving the permutation flow-shop scheduling problem with learning effects[J]. Mathematical Theory and Applications, 2015,35(1):103-114.)
[11] 蒋龙聪,刘江平.模拟退火算法及其改进[J].工程地球物理学报,2007,4(2):135-139.(JIANG L C, LIU J P. Revised simulated annealing algorithm[J]. Chinese Journal of Engineering Geophysics, 2007,4(2):135-139.)
[12] DOWSLAND K A, THOMPSON J M. Simulated annealing[J].Handbook of Natural Computing, 2012,43(1):1623-1655.
[13] 博文渊,凌朝东.布朗运动模拟退火算法[J].计算机学报,2014,37(6):1031-1037.(BO W Y, LING C D. Brownian motion based simulated annealing algorithm[J].Chinese Journal of Computers, 2014, 37(6):1031-1037.)
[14] 韩俊英,刘成忠.自适应混沌果蝇优化算法[J].计算机应用,2013,33(5):1313-1316.(HAN J Y, LIU C D. Adaptive chaos fruit fly optimization algorithm[J].Journal of Computer Applications, 2013,33(5):1313-1316.)
[15] 林川,冯全源.一种新的自适应粒子群优化算法[J].计算机工程,2008,34(7):181-183.(LIN C, FENG Q Y. New adaptive particle swarm optimization algorithm[J].Computer Engineering,2008,34(7):181-183.)
[16] 王联国,洪毅,施秋红.全局版人工鱼群算法[J].系统仿学报,2009,21(23):7483-7486.(WANG L G, HONG Y, SHI Q H. Global edition artificial fish swarm algorithm[J].Journal of System Simulation, 2009,21(23):7483-7486.)

Fruit fly optimization algorithm based on simulated annealing

基于模拟退火的果蝇优化算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	YANG Wei, LI Ran, ZHANG Kun. Task allocation optimization for automated guided vehicles based on variable neighborhood simulated annealing algorithm [J]. Journal of Computer Applications, 2021, 41(10): 3056-3062.
[2]	LIN Li, MENG Xuelei, SONG Zhongzhong. Optimization of intercity train operation plan considering regional coordination [J]. Journal of Computer Applications, 2019, 39(2): 598-603.
[3]	WU Bin, WANG Chao, DONG Min. Hybrid fruit fly optimization algorithm for field service scheduling problem [J]. Journal of Computer Applications, 2018, 38(9): 2706-2711.
[4]	YOU Xinxin, GE Meng. Community detection algorithm based on belief propagation in complex networks [J]. Journal of Computer Applications, 2017, 37(11): 3115-3118.
[5]	LI Meng, QIN Pingle, LI Chuanpeng. Deep belief network algorithm based on multi-innovation theory [J]. Journal of Computer Applications, 2016, 36(9): 2521-2525.
[6]	WANG Xingfu, CHEN Jing, WANG Lin. Mutation fruit fly optimization algorithm based on adaptive dynamic step size [J]. Journal of Computer Applications, 2016, 36(7): 1870-1874.
[7]	XIAO Zhenjiu, SUN Jian, WANG Yongbin, JIANG Zhengtao. Wavelet domain digital watermarking method based on fruit fly optimization algorithm [J]. Journal of Computer Applications, 2015, 35(9): 2527-2530.
[8]	ZHANG Qiantu, FANG Liqing, ZHAO Yulong. Double subgroups fruit fly optimization algorithm with characteristics of Levy flight [J]. Journal of Computer Applications, 2015, 35(5): 1348-1352.
[9]	WANG Zhen-chaoZhenchao GAO Yang XUE Wenling YANG Jianpo. Echo cancellation technique solutions based on parallel filter [J]. Journal of Computer Applications, 2013, 33(07): 1839-1841.
[10]	ZHENG Hui-jie LIU Hong ZHENG Xiang-wei. Group path planning method based on improved group search optimization algorithm [J]. Journal of Computer Applications, 2012, 32(08): 2223-2226.
[11]	. Clustering scheme based on simulated annealing algorithm in wireless sensor network [J]. Journal of Computer Applications, 2010, 30(2): 299-302.
[12]	. New modified particle swarm optimization on basis of two latest generations [J]. Journal of Computer Applications, 2010, 30(2): 472-475.
[13]	. Optimization of coordinated procurement strategy in steel group [J]. Journal of Computer Applications, 2010, 30(07): 1913-1915.
[14]	. Failure model of software reliability based on LSSVRM and simulated annealing algorithm [J]. Journal of Computer Applications, 2010, 30(06): 1648-1650.
[15]	. Process mining based on parallel recombination simulated annealing algorithm [J]. Journal of Computer Applications, 2009, 29(05): 1389-1392.