电子学报

• 科研通信 • 上一篇    下一篇

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

许鹏飞1, 苗启广1, 李伟生2, 张军英1   

  1. 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-fei1, MIAO Qi-guang1, LI Wei-sheng2, ZHANG Jun-ying1   

  1. 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: 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

中图分类号: