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

吴征天，戴金宇

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

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

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

Rose 博士于1990 年提出确定性退火技术[7]，它是一种以温度为同伦参数的连续同伦优化技术[8]，并且它也是按自然法则计算的一个分支。……