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

吴征天，戴金宇

（苏州科技大学 电子与信息工程学院，江苏 苏州 215009）

资源的组合分配问题在理论研究和工程实际中极为常见，如数据压缩问题、模型聚合问题、策略规划问题、区位优化问题等。这些问题的模型通常是一个优化公式，其成本面是非凸的，有许多局部极小值，因此，寻找全局最小值是一项令人望而却步的任务。由于代价曲面的非凸性，许多传统方法如梯度下降法会因初始值选取的不同而陷入较差的局部极小值。一个最直接的补救方法是选择多个初始值，并选择可实现的最低成本值作为潜在的全局最小[1]。显然，由于成本面的结构和资源组合分配的性质，这种方法在计算上是不切实际的。在这种情况下，同伦方法是有效的。

同伦方法是求解非凸优化问题的有效方法[2]。与传统优化方法相比，同伦分析法具有如下优点：（1）强收敛性，通过控制参数来保证解的收敛；（2）普遍有效性，不管求解的问题是否含有参数，高阶级数解都能求得；（3）灵活性，对初始值和辅助算子的选择不敏感，因此，可以选择迭代的方法快速得到收敛的解[3]。同时，Fox提出的“按自然法则计算”是将大量自然现象与自然规律中所表现出来的科学思想进行归纳，并提取其本质，用于解决其他新领域中的问题[4]，如神经网络、蚁群算法[5]、协同进化算法[6]等。

Rose 博士于1990 年提出确定性退火技术[7]，它是一种以温度为同伦参数的连续同伦优化技术[8]，并且它也是按自然法则计算的一个分支。参照热力学退火过程，将温度参数T 引入问题，把求解目标函数的最优值转化为求一系列随温度变化的自由能函数的极小，在模式分类、图像分割、矢量量化等领域得到了广泛应用[9-11]。

笔者对确定性退火技术进行一定的总结。首先，对它的热力学背景及基本思想作介绍，同时归纳总结了确定性退火技术的研究现状；其次，从理论分析角度证明确定性退火技术的可行性；接着，讨论了温度这一参数对该技术的影响，并将该技术与拥有相似物理背景的模拟退火技术进行分析比较；然后，介绍了确定性退火技术的应用领域；最后，指出确定性退火技术的发展挑战和前景。

1 确定性退火技术

1.1 基本思想

由统计物理学产生启发，确定性退火技术是求解全局最优解的一种连续同伦优化方法。该思想来源于热力学退火过程，将一个固体物质加热使之熔化成液体，其内部微粒的排列由稳定的结晶态转变成混乱的液态，然后使温度缓慢降低，微粒的排列从无序转变成有序，到达其结晶温度时，粒子围绕晶体格点做微小振动，此时该物质逐渐变成低能态的晶格，即达到固体的基准态[12-13]。系统在温度下降时达到这种平衡态的过程，可以用统计物理学中的吉布斯自由能极小化原理[14]来描述，即系统在与外界交换热量而温度恒定时，系统自由能下降的方向即为该系统状态变化的趋势，当自由能达到最小时，系统达到平衡态。

确定性退火技术是由基本信息理论原理（如最大熵和随机编码）在概率框架内推导出来的。以求解的随机性（香农熵）为约束条件，使特定应用成本最小化，并逐渐降低该约束条件。它可以避免许多困扰传统技术的糟糕的局部最优，而不需要随机方法通常需要的缓慢调度，由该技术得到的解与初始构型的选择完全无关，并且在“温度”为零的极限下，产生一个非随机（硬）解[1]。

对于求解极小化问题：minE=E（x），E（x）是某一系统的能量。用确定性退火技术求解该问题时，其最优解可由系统自由能函数的最小值得到。构造该系统对应的一个自由能函数[15]：F（x，T）=E（x）-TS，其中T 和S 分别是系统的温度和熵，且温度控制着系统的能量和熵的平衡[8]。在求解每一个温度T 下的最优解时，确定性退火技术利用信息论中的极大熵原理使F（x，T）最小化[16]，本质上也就是对E（x）最小化；当温度T 从充分大缓慢趋于零时，F（x，T）也相应退化成目标函数E（x）。这种优化方式可以看成以温度为同伦参数的连续同伦优化方法。同时，如果要满足上述的过程，构造的自由能函数F（x，T）必须符合下述条件：（1）当T=∞，F（x，∞）关于x 的全局极小值极易求出（需要F 是凸函数，则利用一些传统优化方法极易求解其全局极小）；（2）当T=0，F（x，0）=E（x）。确定性退火技术的基本思想如图1 所示。

图1 确定性退火技术的求解思路

1.2 研究现状

为了提高对确定性退火技术的理解，在一些比较温和的假设下，高温时的自由能函数是凸函数，因此可以假设初始值即局部极小值是唯一的，也是全局的[17]。通过适当的退火策略使温度降低，自由能函数逐渐呈非凸，确定性退火技术的目标就是跟踪该函数的全局最小值[18]。文献[19-29]讨论了确定性退火技术在聚类相关问题中的应用，将聚类问题转化为求解全局优化问题，并将聚类模型归结为求解极小化，算例表明该方法能够在开发算法的并行性上带来极大的效益。文献[30-36]将确定性退火技术应用于模式识别领域。张祥德等设计了一个点匹配算法，得到用于校准两个点集的映射参数，并由匹配校准后的点集得出点的对应关系，实验结果表明该算法的有效性[30]；孙冬梅等将点匹配算法与确定性退火算法结合，得到具有高精确性、高执行性、强鲁棒性的新方法[31]；曹治国等提出了基于确定性退火技术的分类器，与最邻近和贝叶斯分类器相比，其识别率更高[32]；Klock 等在最大熵估计的框架下提出了一种新的确定性退火技术，用于解决一个基本模式识别问题即多维尺度数据的可视化，实验结果表明该方法优于传统的梯度下降法[34]。文献[37-42]介绍了应用于图像分割背景下的确定性退火技术。吴征天等构建了一种确定性退火控制技术用于解决图分割问题，并证明了沿着特定的收敛路径可以得到图分割问题的近似解[37]；Wu 等提出一种确定性退火的神经网络算法，用于解决一般的图分割问题[38]；Xu 等考虑通过聚集节点和边来简化大型加权有向图的问题，提出了一种融合确定性退火算法特征的求解方法[42]。文献[43-47]研究了确定性退火技术与矢量量化的关系，这些研究都来源于文献[10]中提出的基于确定性退火的矢量量化理论。Rose 等设计了一种改进的熵约束矢量量化器，利用确定性退火算法的数据聚类来解决传统的熵约束矢量量化器容易陷入局部极小的陷阱[43]；文献[44]利用信息理论的最小交叉熵原理，设计了一种熵约束树结构的矢量量化器，可获得一致的显著收益；Miller 等提出了一种新的源信道组合矢量量化方法，利用确定性退火技术来避免传统下降算法所遇到的局部极小问题，所得到的矢量量化器能满足噪声信道下实现局部最优的必要条件[46]。文献[48-53]介绍了利用确定性退火算法解决一系列组合优化问题。算法由拉格朗日乘数法和Hopfield 型势垒函数的应用推导而来，通过更新拉格朗日乘数法全局收敛的迭代过程找到一种可行的下降方向，利用势垒函数强制使解向全局或近全局最优点移动；Wu 等还进一步给出了一种优化神经网络的迭代方法，并证明该方法是完全稳定并收敛于稳定的平衡状态[50]。文献[54-57]将确定性退火技术应用于解决旅行商问题。求解时将离散模型转化为连续模型，杨广文等给出了一个简单的迭代公式[54]；Dang 等提出一种全局收敛的拉格朗日—势垒迭代算法来逼近旅行商问题的解[55-56]；Baranwal 等提出一个通用的启发式框架来近似求解多旅行商问题及其许多变体的解，该框架独立于任何两对节点之间定义的边，这使得该算法特别适合于诸如“足够近距离的旅行商问题”这样的变量[57]。文献[58-59]介绍了确定性退火技术在数据挖掘中的应用，解决了神经网络算法容易陷于局部极优的问题，并实现了海量数据的聚类和降维可视化。文献[60-62]将确定性退火技术用于车辆的路径规划问题。文献[63-66]将确定性退火技术用于EM 算法，使改进的算法可以在不需要初始参数值的情况下对参数进行估计。文献[67-69]提出了一种确定性退火聚类方法来预处理输入数据，在电力系统短期负荷预测中取得巨大效益。Gehler 等证明了确定性退火技术可以应用在基于不同的支持向量机的多实例学习问题[70]；李晓花等结合确定性退火技术，提出了改进的针对概率多假设跟踪算法用于水下纯方位多目标跟踪[71]；曹怀虎等提出了基于确定性退火技术的任务调度算法，使区块链转化为并行处理过程，提高了响应速度[72]；Thomas 等提出了一种基于确定性退火的方法，以避免困扰移相器约束模拟波束形成器的局部最优问题[73]；姚剑奇等将确定性退火技术引入阵列稀疏优化问题[74]。

2 算法的理论分析

对于求解极小化问题：minE=E（x），首先构造自由能函数F（x，T），满足前面提出的两个条件，然后按照下列过程求解问题：

（1）取足够大的T0，k=0，求解优化问题：minF（x，Tk），设最优解为xmin（Tk）；

（2）Tk+1＝cTk（0＜c＜1），以xmin（Tk）为初始解，选取一种传统方法求解minF（x，Tk+1），设最优解为xmin（Tk+1）；

（3）判断是否满足收敛准则，若满足，则停，xmin（Tk+1）为最优解；否则，转（4）；

（4）k=k+1，转（2）。

从上述过程中不难看出，确定性退火技术的基本思想是试图建立一个映射φ（T），φ（T）在某一点T0的像就是函数F（x，T0）的某一个全局最小点。若F（x，T）具有某种连续性，就有理由认为在T 连续从∞下降到0的过程中，对应的全局最小点φ（T）也是连续变化的。在这种连续性的假设下，就可能以φ（T+ΔT）为初始点，利用梯度下降法等传统优化方法求得φ（T）；不断下降T 最终可求得φ（0），即目标函数的全局最小值。

文献[75]从理论上证明了映射φ（T）的连续性以及一致连续性，并强调该映射的连续性是影响确定性退火算法的关键因素，倘若不能满足，使用传统的优化方法就可能无法搜索到下一时刻温度下的全局最优点，从而使算法陷入局部极小点。文献[5]证明了当ΔT 的变化很小时，minF（x，T）与minF（x，T+ΔT）的全局最优点φ（T）和φ（T+ΔT）很接近，即可认为minF（x，T）的全局最优点位于minF（x，T+ΔT）的全局最优点所在的局部极小邻域内，所以在温度T 时，可将φ（T+ΔT）作为初始点求解minF（x，T）。文献[13]说明了只要温度下降充分缓慢，最终得到的解为目标函数的全局最优解，并证明了全局最优点x（T）在[0，+∞]是连续的，从而证明了全局最优值φ（T）在[0，+∞]是连续的。文献[30]证明了若F（x，T）为T 的连续函数，minF（x，T）的全局最优值为T 的单调非增函数，则退火速率充分缓慢时该算法的结果收敛到目标函数E（x）的全局最优解。

3 温度控制与退火过程

确定性退火技术是由信息论原理在概率框架内推导出来的，以求解的随机性（香农熵）为约束条件，使应用成本最小化[1]。Fox 证明该技术的初始点应选择在高温下，因为在较高温度下的解初始化可以减轻非线性效应。在高温时最大化熵，当温度降低时逐渐降低该约束条件，当温度为零时，直接最小化系统的能量函数，产生一个非随机（硬）解。冷却计划对该技术的性能有着至关重要的影响，快速冷却将引起淬火效应，很可能导致零温度下的非全局最小值；缓慢冷却能使系统始终保持平衡状态，因此在零温度时，系统的能量配置最小，能得到最好的解，但这计算工作量很大[5]，意味着资源的浪费。确定性退火技术允许几何冷却定律：T（t）=ρT（t-1），0＜ρ＜1，且ρ 通常取0.95 到0.99 之间。文献[76]表明，当T（t）=O（（logt）-1）时，可以实现全局最小值的概率收敛，其中T（t）为t 时刻的温度[18]，这个结论在文献[77]中被进一步强化。

虽然在文献[13]中已经证明，自由能函数的最优值及最优点连续变动到系统能量函数的全局最优值和全局最优点，但如果冷却速度较快，就不能保证在每一温度下按传统优化方法求解F（x，T）的极小值正好是全局极小点，更谈不上最终达到自由能函数的全局最优点所对应的基态，即能量函数E（x）的全局极小点。因此，如何控制温度参数的下降规律，对确定性退火技术的性能有质的影响，还需要进一步研究。

4 确定性退火与模拟退火

模拟退火技术和确定性退火技术有着相似的热力学背景，且都是按自然法则计算的一个重要分支。表1比较了随机退火和确定性退火，从优化的角度来看，有两个显著的区别[78]。第一个区别是，如果所要解决的问题是一个连续变量的优化问题，那么确定性退火技术有可能使用连续优化理论中著名的强大结论。第二个区别是，模拟退火过程用Metropolis 准则（通过蒙特卡罗法）来模拟系统的平衡态，其核心是在前期搜索时不完全拒绝比当前解差的解，且引入了概率这一随机因素[79]，而确定性退火对应于解析积分（通过平均场近似），在每一温度下的优化步骤都使用最合适的方法选择最无偏和给定条件下不可置否的解[13]，而非利用随机概率，因此算法搜索的时间复杂度远远低于随机模拟退火过程，算法的收敛也就非常快速。同时注意到，确定性退火的一个次要优点是，对于任何问题都有固定的T 的最小值和最大值，算法的这一部分不是启发式的，在原则上是可以计算的。

表1 确定性退火与随机退火的比较

5 基于确定性退火技术的应用

5.1 在聚类问题中的应用

传统的聚类模型可以归结为求解极小化问题[19]：minD=（d（xi，yi））2，对于任意的Y={y1，y2，…，yM}及J={j1，j2，…，jM}，称{Y，J}为聚类问题的一个实例，引入温度T，将聚类问题看作一个物理系统，系统取实例{Y，J}的概率为P{Y，J}。定义物理系统的能量函数和熵函数分别为

在每一温度下，利用极大熵原理，使熵H 取极大的概率分布P{Y，J}称为物理系统的平衡态，使P{Y，J}取极大的实例{Y，J}称为聚类系统的最可几实例，通过求解变分问题

可得到

其中U∝1/T，P{Y，J}为温度T 时系统的平衡态，考虑其边缘分布

使P（Y）极大的y1，y2，…，yM应使F（y1，y2，…，yM，U）取极小，使概率分布极大的y1，y2，…，yM称为聚类系统在温度T 时的最可几结构。因此，可以通过求解自由能函数F（y1，y2，…，yM，U）的极小来得到聚类问题的解。

接着，给出F（y1，y2，…，yM，U）在T=0 和T=∞下的情况，考察

该聚类算法具有较强的实用性，可适用于大规模的数据处理[19-20]。

5.2 在旅行商问题中的应用

设X＝{x1，x2，…，xN}是n 维欧式空间内一集合，表示旅行商问题中的城市集，Y＝{y1，y2，…，yN}是对应于X的一组向量参数集，表示旅行商问题的一个最优解，V 称为关联集，，定义V＝{vxj}是合法的。则旅行商问题可以描述为求Y 和V，使得D（Y，V）＝极小，其中yj为第j 类Cj的代表元，d（x，yj）为x 与yj的距离。若再加上使最小的限制，则求解旅行商问题可通过求解下述问题

若xi属于yj所对应的类，则xi称为售货员走的第j 个城市。λ 是一可变系数，用来衡量第二项的关键程度。

（1）取U0=0，minF（Y，0）的最优点为

（2）Uk+1=T（UK）（函数T 满足Uk+1＞Uk），以Ymin（Uk）作为初始点求解minF（Y，Uk+1），设求得的最优点为Ymin（Uk+1）；

（3）判断是否满足收敛准则，若满足，则Ymin（Uk+1）作为旅行商问题的一个最优解；否则，转（4）；

（4）k=k+1，转（2）。

该算法收敛于旅行商问题的全局最优解，当U＝∞，即T=0 时，F（Y，U）的第一项为0，第二项为最短路径[54-56]。

5.3 在点匹配问题中的应用

该算法对噪声、平移、旋转、丢失点和出格点都有较强的鲁棒性，具有广泛的应用[30-31]。

6 挑战和展望

自Rose 于1990 年提出确定性退火技术以来，受到了许多学者的关注。它最初仅仅作为一优化技术用于聚类分析，随着研究的不断深入，该技术在模式识别以及人工智能领域崭露头角，取得了一些实质性的、令人满意的成果。但是，它仍然面临着一些挑战和关键技术问题。例如，如何寻找一个优化问题所对应的物理系统，从而构造出它的自由能函数；对于不同的物理系统，退火过程分别如何控制，有无一般结论；如何放宽约束条件，仍能使利用该技术得到的最优解关于温度连续；能否更进一步降低算法的复杂度，以避免昂贵的计算成本。

确定性退火技术是可拓展的，该技术未来研究的重点，主要集中在以下几个方面：第一，对确定性退火技术进行更加深入的理论研究，讨论解的性质及其全局收敛能力，从理论层面给出运用该技术的更宽松的条件；第二，将该技术与某个实际问题结合，创造出一个可供学习和实践的比较成熟且具有标志性的模型；第三，总结该技术的研究成果，并基于目前的一些应用领域，试图解决更多与之相关的问题；第四，将确定性退火技术拓展到更多应用领域，解决其他一些重要问题，如NP 难问题、非凸优化问题等。由于对不同的优化问题，其自由能函数的构造也各不同，所以要试图给出自由能函数的一般构造方法是极其困难的，这也是其区别于模拟退火技术广泛应用的原因之一。可以期待，随着理论研究的不断深入与完善，随着许多难点的攻克，确定性退火技术必将拥有无比广阔的应用前景。

7 结语

目前，随着科学和工程问题的复杂程度越来越高，一些传统的优化方法已难以应对，确定性退火技术凭借自身的快速收敛性、通用性、可拓展性等特点成为解决大型复杂模型的重要方法。在此背景下，文中对确定性退火技术及其应用进行系统的总结与归纳。确定性退火技术是通过求解一个相关但较简单的问题，并在较简单的问题收敛到原始问题时跟踪其解的演化来求解组合优化问题，它可以被认为是与同伦方法相关的，且面向全局优化。同时，指出自由能函数的构造和退火温度的控制是影响该技术性能的关键，在此基础上，从理论层面分析了它的优势。最后，提出了确定性退火技术在未来发展中亟需解决的问题并给出其未来的研究重点。该文有望为确定性退火技术的理论研究与工程实践示范提供参考。