基于熵约束的确定性退火算法综述  

A review on deterministic annealing algorithms based on entropy constraints

作　　者：吴征天 戴金宇 WU Zhengtian;DAI Jinyu(School of Electronic&Information Engineering,SUST,Suzhou 215009,China)

机构地区：[1]苏州科技大学电子与信息工程学院,江苏苏州215009

出　　处：《苏州科技大学学报（自然科学版）》2021年第2期1-10,共10页Journal of Suzhou University of Science and Technology（Natural Science Edition）

基　　金：国家自然科学基金资助项目(61672371,61803279);江苏省“青蓝工程”资助项目。

摘　　要：在智能技术应用的众多领域内都会涉及到NP-hard问题,这个问题传统优化技术无法解决。确定性退火技术,作为一种启发式算法,能够避开局部极小值,找到非凸连续函数的全局最优点。首先介绍确定性退火技术的物理背景及其基本思想,并对国内外在该领域的理论探索和应用实践进行分析总结;其次给出一系列的数学证明,作为确定性退火技术的理论支撑;再次阐述温度的控制对该技术的影响;接着将随机模拟退火技术与该技术进行比较,突出确定性退火技术具有收敛速度快的优势;然后说明确定性退火技术在聚类分析、旅行商问题、点匹配问题等领域中的应用;最后指出确定性退火技术在人工智能等领域必将起着重要的作用,并提出一些亟待解决的问题以及未来的研究方向。NP-hard problems are widely involved in many areas of intelligent technology application,which cannot be solved by traditional optimization technology.As a heuristic algorithm,deterministic annealing can avoid local minima and find the global optimum of non-convex continuous function.Firstly,the paper presented the physical background and basic ideas of deterministic annealing while we analyzed the theoretical exploration as well as application practice in this field at home and abroad.Secondly,a series of mathematical proofs were given to provide a theoretical support for deterministic annealing.Thirdly,it explained the influence of temperature control on the technology.Then the stochastic simulated annealing was compared with this technology to give prominence to the superiorities of deterministic annealing with fast convergence speed.The applications of deterministic annealing in cluster analysis,traveling salesman problems,point matching problems and other fields were illustrated.Finally,the paper indicates that deterministic annealing plays an important role in artificial intelligence and other fields.In addition,it puts forward some urgent problems to be solved and proposes its future research directions.

关 键 词：确定性退火 自由能函数 全局优化 同伦方法 

分 类 号：O224[理学—运筹学与控制论]