基于函数复杂度的自适应模拟退火和禁忌搜索新算法

doi:10.3969/j.issn.0372-2112.2012.06.025

电子学报

基于函数复杂度的自适应模拟退火和禁忌搜索新算法

许鹏飞¹, 苗启广¹, 李伟生², 张军英¹

1. 西安电子科技大学计算机学院,陕西西安 710071;
2. 重庆邮电大学计算机学院,重庆 400065

收稿日期:2011-07-03 修回日期:2011-11-23 出版日期:2012-06-25
- 作者简介:
- 许鹏飞 男,1987年出生于安徽省巢湖市,2009获西安电子科技大学管理学学士学位,2009年秋进入西安电子科技大学计算机学院攻读硕士研究生,2010年秋进入西安电子科技大学计算机学院攻读博士学位.现主要研究方向是模式识别,数字图像处理. E-mail:xpf1987071500@126.com
- 基金资助:
- 国家自然科学基金项目 (No.61072109,No.61142011); 中央高校基本科研业务费专项资金 (2012年度); 西安市科技局计划项目 (No.CXY1133 (1),No.CXY1119 (6))

Adaptive Simulated Annealing Algorithm and Tabu Search Algorithm Based on the Function Complexity

XU Peng-fei¹, MIAO Qi-guang¹, LI Wei-sheng², ZHANG Jun-ying¹

1. School of Computer,Xidian University,Xi’an,Shaanxi 710071,China;
2. College of Computer Science and Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China

Received:2011-07-03 Revised:2011-11-23 Online:2012-06-25 Published:2012-06-25
- Supported by:
- National Natural Science Foundation of China (No.61072109, No.61142011); Fundamental Research Funds for the Central Universities -2012; Xi 'an Science and Technology Bureau Project (No.CXY1133 (1), No.CXY11196))

摘要/Abstract

摘要： 在求解多峰复杂函数的过程中,传统的模拟退火算法和禁忌搜索算法经常出现算法快速收敛于局部最优解、后期收敛速度变慢和搜索能力变差等问题.为解决这些问题,本文给出函数复杂度的定义,并提出基于函数复杂度的自适应模拟退火和禁忌搜索算法.该算法首先根据函数复杂度自适应调整步长控制参数,然后根据调整后步长求得函数的粗糙解,在此基础上再使用初始步长求得全局最优解.实验表明,该算法不仅可以跳出局部最优解的限制,并且减少了迭代次数,有效地提高了全局和局部搜索能力.

关键词: 函数复杂度, 模拟退火算法, 禁忌搜索算法, 函数优化

Abstract: In the process of applying traditional simulated annealing algorithm and tabu search algorithm to solving multi-peak complex functions,the following problems often occur:particles converge to the local optimal solution too fast,the late converge slows down and search ability turns poor.In order to solve these problems,the definition of function complexity is proposed,and adaptive simulated annealing algorithm and tabu search algorithm are presented based on the function complexity.In these algorithms,the step length control parameters are adaptively adjusted according to the function complexity;then rough solution of the function is obtained in terms of regulated step length;finally,and the original step length is used to acquire the global optimal solution.Experiments show that the proposed method cannot only transcend the limits of the local optimal solution,but also reduce iteration of the above algorithms,and efficiently improve local and global search ability.

Key words: function complexity, simulated annealing algorithm, tabu search algorithm, function optimization

中图分类号:

TP301.6

许鹏飞, 苗启广, 李伟生, 等. 基于函数复杂度的自适应模拟退火和禁忌搜索新算法[J]. 电子学报, DOI: 10.3969/j.issn.0372-2112.2012.06.025.

XU Peng-fei, MIAO Qi-guang, LI Wei-sheng, et al. Adaptive Simulated Annealing Algorithm and Tabu Search Algorithm Based on the Function Complexity[J]. Acta Electronica Sinica, DOI: 10.3969/j.issn.0372-2112.2012.06.025.

参考文献

[1] 周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版,2005.125-127.

[2] 张火明,陆慧娟,等.混合离散变量模拟退火方法及其应用[J].中国计量学院学报,2006,17(1):44-49. ZHANG Huoming,LU Huijuan,et al.Improvement and application of annealing simulation method for hybrid discrete variables[J].Journal of China Jiliang University,2006,17(1):44-49.(in Chinese)

[3] 谢云.模拟退火算法综述[J].计算机应用研究,1998(5):7-9.

[4] 康立山,谢云.非数值并行计算——模拟退火算法[M].北京:科学出版社,1998.22-55

[5] GLOVER F.Tabu search:PartⅡ[J].ORSA Journal on Computing,1990,2(1):4-32.

[6] GLOVER F.Tabu search:Part I[J].ORSA Journal on Computing,1990,1(3):190-206.

[7] BATTITI R,TECCHIOLLI G.The reactive tabu search[J].ORSA Journal on Computing,1994,6(2):126-140.

[8] 宋炜,刘强.基于模拟退火算法的过程挖掘研究[J].电子学报,2008,36(4A):35-139. SONG Wei,LIU Qiang.Business process mining based on simulated annealing[J].Acta Electronica Sinica,2008,36(4A):35-139.(in Chinese)

[9] 李铁,王航字,等.目标表面BRDF统计建模中的遗传模拟退火算法[J].量子电子学报,2008,25(4):489-492. LI Tie,WANG Hangyu,et al.Application of genetic simulated annealing algorithm in BRDF statistical modeling[J].Chinese Journal of Quantum Electronics,2008,25(4):489-492.(in Chinese)

[10] 雍正正,罗萍,等.一种进化模拟退火矢量量化图像编码新算法[J].电子学报,2001,29(5):1-4. YONG Zhengzheng,LUO Ping,et al.A new vector quantization image coding algorithm based on evolutionary simulated annealing[J].Acta Electronica Sinica,2001,29(5):1-4.(in Chinese)

[11] 张昊,陶然,等.基于KNN算法及禁忌搜索算法的特征选择方法在入侵检测中的应用研究[J].电子学报,2009,37(7):1628-1632. ZHANG Hao,TAO Ran,et al.A research and application of feature selection based on KNN and tabu search algorithm in the intrusion detection[J]. Acta Electronica Sinica,2009,37(7):1628-1632.(in Chinese)

[12] 蓝海,王雄,等.复杂函数全局最优化的改进遗传退火算法[J].清华大学学报(自然科学版),2002,42(9):1237-1240. LAN Hai,WANG Xiong,et al.Improved genetic-annealing algorithm for global optimization of complex functions[J].J Tsinghua Univ (Sic &.Tech),2002,42(9):1237-1240.(in Chinese)

[13] 王登刚,刘迎曦,等.最优化问题全局寻优的混合遗传算法[J].力学学报,2002,34(3):0471-0473.

[14] 陈龙,朱宏.改进的模拟退火遗传算法在函数优化中的应用[J].计算机与数学工程,2010,38(7):13-16. CHEN Long,ZHU Hong.Application of improved simulated annealing genetic algorithm in function optimization[J].Computer & Digital Engineering,2010,38(7):13-16.(in Chinese)

[15] 石运序,范红梅.改进的遗传模拟退火算法在多峰值函数优化中的应用[J].烟台大学学报(自然科学与工程版),2008,21(3):209-212.

[16] Young-Jae Jeon,Jae-Chul Kin.Application of simulated annealing and tabu search for loss minimization in distribution systems[J].Electrical Power and Energy Systems,2004,26(1):9-18.

[17] 张晓菲,张火明.基于连续函数优化的禁忌搜索算法[J].中国计量学院学报,2010,21(3):251-256. ZHANG Xiaofei,ZHANG Huoming.Improved tabu search algorithm for continuous problems[J].Journal of China University of Metrology,2010,21(3):251-256.(in Chinese)

基于函数复杂度的自适应模拟退火和禁忌搜索新算法

Adaptive Simulated Annealing Algorithm and Tabu Search Algorithm Based on the Function Complexity

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	褚鼎立, 陈红, 王旭光. 基于自适应权重和模拟退火的鲸鱼优化算法[J]. 电子学报, 2019, 47(5): 992-999.
[2]	戴忠华, 周穗华, 单珊. 基于模拟退火算法的舰船磁场高精度建模方法[J]. 电子学报, 2018, 46(6): 1524-1529.
[3]	杜振鑫, 刘广钟, 韩德志, 余学山, 贾建鑫. 基于全局无偏搜索策略的精英人工蜂群算法[J]. 电子学报, 2018, 46(2): 308-314.
[4]	田波, 蔡述庭. 面向GEO卫星网络的多速率多播拥塞控制机制[J]. 电子学报, 2016, 44(7): 1599-1604.
[5]	王福才, 周鲁苹. 混合精英策略的元胞多目标遗传算法及其应用[J]. 电子学报, 2016, 44(3): 709-717.
[6]	张屹, 万兴余, 郑小东, 孙莉莉. 基于正交设计的元胞多目标遗传算法[J]. 电子学报, 2016, 44(1): 87-94.
[7]	钱洁, 郑建国. 引入逆学习的量子自适应禁忌搜索算法[J]. 电子学报, 2013, 41(6): 1069-1075.
[8]	王鹏, 黄焱, 任超, 郭又铭. 多尺度量子谐振子高维函数全局优化算法[J]. 电子学报, 2013, 41(12): 2468-2473.
[9]	陈晓峰, 姜慧研. 量子禁忌搜索算法的研究[J]. 电子学报, 2013, 41(11): 2161-2166.
[10]	游晓明;刘升;王裕明. 基于量子计算模型的混合进化算法及其性能分析[J]. 电子学报, 2012, 40(4): 856-860.
[11]	李军华;黎明. 噪声环境下多模态函数优化的遗传算法[J]. 电子学报, 2012, 40(2): 327-330.
[12]	李文锋, 梁晓磊, 张煜. 具有异构分簇的粒子群优化算法研究[J]. 电子学报, 2012, 40(11): 2194-2199.
[13]	易军;石为人;唐云建;许磊. 无线传感器/执行器网络任务动态调度策略[J]. 电子学报, 2010, 38(6): 1239-1244.
[14]	宋炜, 刘强. 基于模拟退火算法的过程挖掘研究[J]. 电子学报, 2009, 37(S1): 135-139.
[15]	马卫;朱庆保. 求解函数优化问题的快速连续蚁群算法[J]. 电子学报, 2008, 36(11): 2120-2124.