关于作者
一个毕业于北京大学数学力学系，在中国科学院计算所、计算中心和网络中心工作过，在澳大利亚科工组织dms、香港浸会学院数学系和中国21世纪议程管理中心等处工作过，多次获国家和中科院科技奖并享受政府特殊津贴的退休老头。现在在【中国科普博览】网“科学新语林”栏目里开设一个《数学与计算机》的个人专栏，愿和爱好数学与计算机的各界网友和青少年朋友，谈谈对数学与计算机的看法、想法。
《常用算法之智能计算(七) 》：物理智能计算
张建中
2019年01月04日
物理智能计算(physical？intelligence computing)，是指一些受自然界物理现象启发而设计出来的具有分布式智能行为特征的一类智能算法，出发点是基于物理中物质与通常组合优化问题之间的相似性，又是基于蒙特卡罗迭代求解策略的一种随机寻优算法。智能计算作为一种新兴的计算机计算技术，已成为越来越多研究者关注的焦点，并有着广泛的应用。物理智能计算在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的提供了基础。
物理智能计算含模拟退火算法、烟花算法等，下面对它们进行一些简单介绍。
模拟退火算法（simulated annealing algorithm）来源于固体退火原理，是一种基于蒙特卡罗思想设计的近似求解最优化问题的算法。
在热力学上，退火现象是指物体逐渐降温的物理现象，温度愈低，物体的能量状态会愈低；够低后，物体开始冷凝并结晶，在结晶状态时，系统的能量最低、状态最稳。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温时，会导致不是最低能态的非晶形。
物理上的退火如下图所示。首先，物体处于非晶体状态（如图1所示）。我们将固体加温至充分高，固体内能增大，内部粒子随温度升高变为无序状态（如图2所示），再让其徐徐冷却，也就退火。降温时，徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小，此时物体呈现晶体形态（如图3所示），系统最稳定。
模拟退火算法成功地将退火思想引入到组合优化领域，从某一较高初温出发，伴随温度参数的不断下降,结合突跳特性在中随机寻找的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上该算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，可以较高的效率求解最大化问题、0-1背包问题、图着色问题等，再如在超大规模集成电路vlsi设计、生产调度、控制工程、机器学习、神经网络、信号处理等领域都取得了成功应用。模拟退火算法是通过赋予搜索过程一种时变且最终趋于1的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。
模拟退火算法来源于固体退火原理，根据metropolis准则，在温度t时趋于平衡的为e-/(kt)，其中e为温度t时的内能， e为其改变量，k为boltzmann常数。用固体退火模拟组合优化问题，将内能e模拟为值f，温度t演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解和控制参数初值t开始，对当前解重复“产生新解 计算目标函数差 接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似，这是基于迭代求解法的一种启发式过程。退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子 t、每个t值时的迭代次数l和停止条件s。
模拟退火算法的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度的选取有一定的影响。
第二步是计算与新解所对应的差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是metropolis准则: 若 t<0则接受s′作为新的当前解s，否则以概率exp(- t/t)接受s′作为新的当前解s。
第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现一次迭代，可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
模拟退火算法与初始值无关，算法求得的解与初始解状态s(算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局的全局优化算法，模拟退火算法还具有并行性。
模拟退火算法的应用如下：
1、模拟退火算法在超大规模集成电路vlsi设计中的应用
利用模拟退火算法进行vlsi的最优设计，是目前模拟退火算法最成功的应用实例之一。用模拟退火算法几乎可以很好地完成所有优化的vlsi设计工作。如全局布线、布板、布局和逻辑最小化等等。
2、模拟退火算法在神经网计算机中的应用
模拟退火算法具有跳出局部最优陷阱的能力。在boltzmann机中，即使系统落入了局部最优的陷阱，经过一段时间后，它还能再跳出来，再系统最终将往全局最优值的方向收敛。
3、模拟退火算法在图像处理中的应用
模拟退火算法可用来进行图像恢复等工作，即把一幅被污染的图像重新恢复成清晰的原图，滤掉其中被畸变的部分。因此它在图像处理方面的应用前景是广阔的。
4、模拟退火算法的其他应用
除了上述应用外，模拟退火算法还用于其它各种组合优化问题，如和knapsack问题等。大量的模拟实验表明，模拟退火算法在求解这些问题时能产生令人满意的近似最优解，而且所用的时间也不很长。
模拟退火算法的应用很广泛，但存在问题也不少，其主要问题有以下三点：
模拟退火算法的优缺点及其改进：
优点：计算过程简单，通用，稳健性强，适用于并行处理，可用于求解复杂的非线性优化问题。
缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等。
模拟退火算法的改进：
1) 设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。
2) 设计高效的退火策略，避免状态的迂回搜索。
3) 采用并行搜索结构，避免陷入局部极小，改进对温度的控制方式。
4) 选择合适的初始状态和算法终止准则。
也可通过增加某些环节而实现对模拟退火算法的改进，改进方式包括：
(1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。
(2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。
(3)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。
(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准单次比较方式。
(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。
(6)上述各种方法的综合应用。
烟花算法 (fire works algorithm)是受到夜空中烟花爆炸的启发而提出的一种算法。
烟花算法自2010年首次提出之后？，对烟花算法的研究逐步深入并展开。通过对原始烟花算法的细致、深入的分析，针对原始烟花算法的不足，提出了大量的改进方法，并据此发展了各种改进算法以及与其他方法的混合方法，大大提高的原始烟花算法的性能，同时研究了烟花算法在求解不同类型优化问题的能力，还进行了烟花算法的应用研究，给出了一些典型的成功应用案例。
烟花算法的实现步骤：
1）在特定的解空间中随机产生一些烟花，每一个烟花代表解空间的一个解。
2）根据适应度函数计算每一个烟花的适应度值，并根据适应度值产生火花。火花的个数是基于免疫学中的免疫浓度的思想来计算的，即适应度值越好的烟花产生火花的数目越多。
3）根据现实中的烟花属性并结合搜索问题的实际情况，在烟花的辐射空间内产生火花。某个烟花的爆炸幅度的大小由该烟花在函数上的适应度值决定，适应度值越大，爆炸幅度越大，反之亦然。每一个火花代表解空间中的一个解。为了保证种群的多样性，需要对烟花进行适当变异，如高斯变异。
4）计算种群的最优解，判定是否满足要求，如果满足则停止搜索，没有满足则继续迭代。迭代的初始值为此次循环得到的最好的解和选择的其他的解。
烟花算法的特点
基本烟花算法具有如下特点？？：随机性、局部性、爆发性、隐并行性、简单性、多样性和瞬时性、可扩充性及适应性等。
烟花算法的未来发展
迄今为止，烟花算法的研究还是很初步的。在有些方面，还是空白，在许多方面还比较肤浅，急需对其进行进一步研究。烟花算法的未来发展方向归纳起来，有以下几个方面：
1、 算法的理论基础和分析，如稳定性、收敛及其特性和参数灵敏度分析等问题的研究；
2、 各种改进方法的深入研究，如各种因素对烟花算法性能的影响，如何有效控制和调整，重点是子烟花间的协同机制建立和研究等；
3、混合算法研究和问题的求解；
4、动态优化问题的求解和更广泛的应用研究。
物理智能计算含模拟退火算法、烟花算法等，下面对它们进行一些简单介绍。
模拟退火算法（simulated annealing algorithm）来源于固体退火原理，是一种基于蒙特卡罗思想设计的近似求解最优化问题的算法。
在热力学上，退火现象是指物体逐渐降温的物理现象，温度愈低，物体的能量状态会愈低；够低后，物体开始冷凝并结晶，在结晶状态时，系统的能量最低、状态最稳。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温时，会导致不是最低能态的非晶形。
物理上的退火如下图所示。首先，物体处于非晶体状态（如图1所示）。我们将固体加温至充分高，固体内能增大，内部粒子随温度升高变为无序状态（如图2所示），再让其徐徐冷却，也就退火。降温时，徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小，此时物体呈现晶体形态（如图3所示），系统最稳定。
模拟退火算法成功地将退火思想引入到组合优化领域，从某一较高初温出发，伴随温度参数的不断下降,结合突跳特性在中随机寻找的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法，理论上该算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，可以较高的效率求解最大化问题、0-1背包问题、图着色问题等，再如在超大规模集成电路vlsi设计、生产调度、控制工程、机器学习、神经网络、信号处理等领域都取得了成功应用。模拟退火算法是通过赋予搜索过程一种时变且最终趋于1的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。
模拟退火算法来源于固体退火原理，根据metropolis准则，在温度t时趋于平衡的为e-/(kt)，其中e为温度t时的内能， e为其改变量，k为boltzmann常数。用固体退火模拟组合优化问题，将内能e模拟为值f，温度t演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解和控制参数初值t开始，对当前解重复“产生新解 计算目标函数差 接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似，这是基于迭代求解法的一种启发式过程。退火过程由冷却进度表控制，包括控制参数的初值t及其衰减因子 t、每个t值时的迭代次数l和停止条件s。
模拟退火算法的产生和接受可分为如下四个步骤：
第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度的选取有一定的影响。
第二步是计算与新解所对应的差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。
第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是metropolis准则: 若 t<0则接受s′作为新的当前解s，否则以概率exp(- t/t)接受s′作为新的当前解s。
第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现一次迭代，可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。
模拟退火算法与初始值无关，算法求得的解与初始解状态s(算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局的全局优化算法，模拟退火算法还具有并行性。
模拟退火算法的应用如下：
1、模拟退火算法在超大规模集成电路vlsi设计中的应用
利用模拟退火算法进行vlsi的最优设计，是目前模拟退火算法最成功的应用实例之一。用模拟退火算法几乎可以很好地完成所有优化的vlsi设计工作。如全局布线、布板、布局和逻辑最小化等等。
2、模拟退火算法在神经网计算机中的应用
模拟退火算法具有跳出局部最优陷阱的能力。在boltzmann机中，即使系统落入了局部最优的陷阱，经过一段时间后，它还能再跳出来，再系统最终将往全局最优值的方向收敛。
3、模拟退火算法在图像处理中的应用
模拟退火算法可用来进行图像恢复等工作，即把一幅被污染的图像重新恢复成清晰的原图，滤掉其中被畸变的部分。因此它在图像处理方面的应用前景是广阔的。
4、模拟退火算法的其他应用
除了上述应用外，模拟退火算法还用于其它各种组合优化问题，如和knapsack问题等。大量的模拟实验表明，模拟退火算法在求解这些问题时能产生令人满意的近似最优解，而且所用的时间也不很长。
模拟退火算法的应用很广泛，但存在问题也不少，其主要问题有以下三点：
- 温度t的初始值设置问题。
- 退火速度问题。
- 温度管理问题。
模拟退火算法的优缺点及其改进：
优点：计算过程简单，通用，稳健性强，适用于并行处理，可用于求解复杂的非线性优化问题。
缺点：收敛速度慢，执行时间长，算法性能与初始值有关及参数敏感等。
模拟退火算法的改进：
1) 设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。
2) 设计高效的退火策略，避免状态的迂回搜索。
3) 采用并行搜索结构，避免陷入局部极小，改进对温度的控制方式。
4) 选择合适的初始状态和算法终止准则。
也可通过增加某些环节而实现对模拟退火算法的改进，改进方式包括：
(1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。
(2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。
(3)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。
(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准单次比较方式。
(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。
(6)上述各种方法的综合应用。
烟花算法 (fire works algorithm)是受到夜空中烟花爆炸的启发而提出的一种算法。
烟花算法自2010年首次提出之后？，对烟花算法的研究逐步深入并展开。通过对原始烟花算法的细致、深入的分析，针对原始烟花算法的不足，提出了大量的改进方法，并据此发展了各种改进算法以及与其他方法的混合方法，大大提高的原始烟花算法的性能，同时研究了烟花算法在求解不同类型优化问题的能力，还进行了烟花算法的应用研究，给出了一些典型的成功应用案例。
烟花之火花图（摘自互联网）
烟花算法开始迭代，依次利用爆炸算子、变异算子、映射规则和选择策略，直到达到终止条件，即满足问题的精度要求或者达到最大函数评估次数。烟花算法的实现步骤：
1）在特定的解空间中随机产生一些烟花，每一个烟花代表解空间的一个解。
2）根据适应度函数计算每一个烟花的适应度值，并根据适应度值产生火花。火花的个数是基于免疫学中的免疫浓度的思想来计算的，即适应度值越好的烟花产生火花的数目越多。
3）根据现实中的烟花属性并结合搜索问题的实际情况，在烟花的辐射空间内产生火花。某个烟花的爆炸幅度的大小由该烟花在函数上的适应度值决定，适应度值越大，爆炸幅度越大，反之亦然。每一个火花代表解空间中的一个解。为了保证种群的多样性，需要对烟花进行适当变异，如高斯变异。
4）计算种群的最优解，判定是否满足要求，如果满足则停止搜索，没有满足则继续迭代。迭代的初始值为此次循环得到的最好的解和选择的其他的解。
烟花算法的特点
基本烟花算法具有如下特点？？：随机性、局部性、爆发性、隐并行性、简单性、多样性和瞬时性、可扩充性及适应性等。
烟花算法的未来发展
迄今为止，烟花算法的研究还是很初步的。在有些方面，还是空白，在许多方面还比较肤浅，急需对其进行进一步研究。烟花算法的未来发展方向归纳起来，有以下几个方面：
1、 算法的理论基础和分析，如稳定性、收敛及其特性和参数灵敏度分析等问题的研究；
2、 各种改进方法的深入研究，如各种因素对烟花算法性能的影响，如何有效控制和调整，重点是子烟花间的协同机制建立和研究等；
3、混合算法研究和问题的求解；
4、动态优化问题的求解和更广泛的应用研究。