现代优化方法之模拟退火

第三部分现代优化方法选讲

现代优化方法包括禁忌搜索、模拟退火、智能计算等。其中模拟退火、神经网络和遗传算法并称为现代优化算法中的三大杰出代表。一、模拟退火算法

在管理科学、计算机科学、分子物理学、生物学、超大规模集成电路设计、代码设计、图象处理和电子工程等领域中，存在着大量的组合优化问题。例如，货郎担问题、最大截问题、0—1背包问题、图着色问题、设备布局问题以及布线问题等，这些问题至今仍未找到多项式时间算法。这些问题已被证明是NP完全问题。根据NP完全性理论，除非P=NP，否则所有的NP难问题都不存在多项式时间算法。但是，这并不意味着问题的终结。相反，由于这类问题广泛应用性，反而刺激人们以更大的热情对NP完全问题进行研究。为解决这类问题，人们提出了许多近似算法，但这些算法或过于注意个别问题的特征而缺乏通用性，或因所得解强烈地依赖初始解的选择而缺乏实用性。模拟退火算法是近年提出的一种适合解大规模组合优化问题，特别是解NP完全问题的通用有效的近似算法，与以往近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制的优点，而且特别适合并行计算，因此具有很大的使用价值。同时由于其讨论涉及随机分析、马氏链理论、渐进收敛性等学科，所以其研究还具有重要的理论意义。1.模拟退火算法的物理背景固体退火过程的物理图象和统计性质是模拟退火算法的物理背景。在热力学与统计物理学的研究领域中，固体退火是其重要的研究对象。固体退火是指先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程。在高温状态下，液体的分子彼此之间可以自由移动。如果液体徐徐冷却，它的分子就会丧失由于温度而引起的流动性。这时原子就会自己排列起来而形成一种纯晶体，它们依次地朝各个方向几十亿倍于单个原子大小的距离，这个纯晶状态就是该系统的最小能量状态，有趣的是：对于一个徐徐冷却的系统，当这些原子在逐渐失去活力的同时，它们自己就同时地排列而形成一个纯晶体，使这个系统的能量达到其最小值。这里我们特别强调在这个物理系统的冷却过程中，这些原子就同时的把它们自己排列成一个纯晶体的。如果一种金属熔液是被快速的冷却，则它不能达到纯晶体状态，而是变成一种多晶体或非晶体状态，系统处在这种状态时具有较高的能量。模拟退火算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术，可用马氏链的遍历理论给它以数学上的描述。在搜索最优解的过程中，模拟退火除了可以接受优化解外，还用一个随机准则(Metropolis准则)有限地接受恶化解，并使接受恶化解的概率逐渐趋于零，这使得算法有可能从局部最优解中跳出，尽可能找到全局最优解，并保证了算法的收敛性。1982年Kipatrick等人首次把固体退火与组合极小化联系在一起，他们分别用目标函数和组合极小化问题的解替代物理系统的能量和状态，从而物理系统内粒子的摄动等价于组合极小化问题中解的试探。极小化过程就是：首先在一个高温（温度现在就成为一个参数控制）状态下有效的“溶化”解空间，然后慢慢地降低温度直到系统“晶体”到一个稳定解。通过以下示例，我们可以将组合优化问题与固体退火进行类比：组合优化问题固体退火解状态最优解能量最低状态费用函数能量2.模拟退火算法的基本思想与算法用传统优化算法优化多峰值函数时，往往由于过分追求“下降”而极易陷于局部最优解。为了克服这个缺陷，在搜索最优解的过程中，模拟退火方法除了接受优化解外，还根据一个随机接受准则有限地接受恶化解，并使接受恶化解的概率逐渐趋于零。这既可使得算法以较大概率跳出局部最优解，又保证了算法的收敛性。模拟退火算法的求解过程如下：(1)随机产生初始解X0，给定初始温度T0，令k=0；(2)随机产生新解，并计算函数增量

(3)若，则接受新解，，转(2)，否则以概率决定是否接受新解。具体方法是：产生0和1之间的一个随机数r，若，接受新解，否则拒绝新解；(4)重复第(2),(3)步若干次，使解接近当前温度下的最优解，这相当于用足够慢的速度降温，以保证在每个温度时系统都能处于当前温度下的能量最低状态；(5)按一定的方式降低温度，例如，其中；(6)若满足收敛条件，退火过程结束，否则，转(2)。通常，收敛条件为。理论已证明：只要初始温度足够高，退火过程足够慢，模拟退火算法以概率1收敛到全局最优解。模拟退火算法在许多领域有非常广泛的应用，尤其适用于求解组合优化问题。如旅行商问题(TSP)、0-1背包问题(ZKP)、最大截问题(MCP)、独立集问题(ISP)、调度问题(SCP)、图着色问题(GCP)等。例用模拟退火算法求的极小值。3.模拟退火算法的应用模拟退火算法具有广泛的应用性，可用于求解许多组合优化问题。根据模拟退火算法的过程（产生新解——计算目标函数差——判别是否接受新解——接受或舍弃新解），在算法的实际应用中必须解决好三个问题：第一，问题的数学描述；第二，新解的产生和接受机制；第三，冷却进度表的选取。冷却进度表包括：初始温度、降温策略、马氏链长度以及停止准则四个方面。此外，还包括随机数发生器。问题的描述主要包括解空间和目标函数两部分。解空间为所有可行解的集合，它限定了初始解选取和新解产生的范围。对于无约束优化问题，任一可能解即为可行解；对于有约束优化问题，解集中还可以包含一些不可行解，同时在目标函数中加上惩函数，以惩罚出现的不可行解。新解的产生和接受可分为四个步骤：第一，给出新解的变换方法，得到一个产生装置，以从当前解产生一个新解；第二，计算新解和当前解的目标函数差，由于目标函数差仅由变换部分产生，因此，通常按增量计算目标函数差；第三，判断新解是否被接受，判断的依据是Metropolis准则，对于有约束优化问题往往还伴随有新解可行性的判断；第四，接受或舍弃新解，若接受，用新解代替当前解，同时修正目标函数值，否则当前解与目标函数值保持不变。下面仅对几个典型的组合优化问题给出算法描述，以揭示其建立数学模型和新解产生装置的基本方法。(1)旅行商问题（tsp）设有n个城市和距离矩阵，其中表示城市i到城市j的距离，i,j=1,…，n，则问题是寻找遍访每个城市恰好一次的一条回路，且其路径长度为最短。求解的模拟退火算法描述如下：①解空间解空间S可表为{1,2，…，n}的所有循环排列的集合，即其中每一循环排列表示遍访n个城市的一条回路，表示在第i个次序访问城市j，并约定。初始解可选为（1,2，…，n）。②目标函数此时的目标函数为访问所有城市的路径长度之和，即其中。③新解的产生（2变换法）任选访问的序号u和v，逆转u和v及其之间的访问顺序，此时新路径为（设u<v）④代价函数差新解的目标函数差可由公式计算。特别地，当问题为对称的，即距离矩阵为对称矩阵时，上式可简化为intd[11][11]={{0,3,93,66,13,100,25,33,9,57,19}, {24,0,33,77,42,21,16,45,34,21,109}, {45,107,0,81,36,16,4,28,25,37,62}, {139,90,80,0,56,7,44,56,20,91,75}, {18,64,188,33,0,11,25,96,5,57,43}, {3,88,18,46,92,0,55,33,20,91,7}, {44,26,33,27,84,39,0,101,9,72,36}, {11,39,24,98,103,76,54,0,50,63,99}, {77,82,67,19,30,42,56,9,0,88,28}, {12,133,32,69,21,52,87,66,43,0,55}, {92,32,81,73,44,24,64,15,77,9,0}};非数值并行算法——模拟退火算法康立山《科学出版社》排挤小生境遗传算法改进研究

1、排挤小生境遗传算法及其改进

日本学者提出了一种基于罚函数的排挤小生境遗传算法，其基本思想是：首先比较群体中每两个个体之间的距离，若这个距离小于预先指定的距离L，再比较两者的适应度，并对其中适应度较小的个体施加一个较强的罚函数，极大地降低其适应度。这样，对于在距离L之内的两个个体，其中较差的个体经处理后其适应度变得更差，在后面的进化过程中被淘汰的概率就极大。也就是说，在距离L之内将只存在一个优良的个体，从而既维护了群体的多样性，又使得各个个体之间保持一定的距离。上述小生境遗传算法具体实现过程如下：①随机生成M个初始个体组成初始群体，并计算适应度；②根据各个个体的适应度对其进行降序排序，记忆前N个个体（N<M）；③进行比例选择、单点交叉、基本位变异运算；④小生境淘汰运算：将第③步得到的M个个体和第②步所记忆的N个个体合并在一起，得到一个含有M+N个个体的新群体。对这M+N个个体，求出每两个个体和之间的Hamming距离。当时，比较个体和的适应度大小，并对其中适应度较低的个体处以罚函数；⑤根据这M+N个个体的新适应度对各个个体进行降序排序，记忆前N个个体；⑥终止条件判断：若不满足终止条件，则将第⑤步排序中的前M个个体作为新的下一代群体，然后转到第③步；若满足终止条件，则输出计算结果，算法结束。本文对上述算法做了两处改进。第一，原算法用Hamming距离来衡量两个个体的远近程度。我们认为这是不妥的，因为即使海明距离很小的两个个休，其实际距离也可能很大。本文采用欧氏距离来衡量个体的远近程度。第二，原算法在进行小生境运算时采用的是通常的（1+1）淘汰。Goldberg指出，在小生境的竞争选择机制中，(μ+λ)选择机制具有较强的选择压，可有效地提高种群的多样性。(μ+λ)选择允许μ个父代个体和λ个子代个体共同竞争，确定性地选择高适应值个体进入新的种群。仿真实验表明，用(μ+λ)竞争选择能大大提高种群的多样性，产生较快的收敛速度。综合考虑计算速度和计算量，本文采用（2+2）竞争选择机制。为了定量描述改进后算法维持种群多样性的能力以及收敛速度的提高程度，我们采用下列函数表示种群的多样性程度

其中n为种群规模，为个体的二进制编码长度，为种群中第i个个体的第j个二进制的值。显然，越小（大），种群的多样性就越高（低）。测试函数为1、五峰函数

函数分别在处有极大点，其中为全局极大点。2、六峰值驼背函数函数有六个极大点其中为全局极大点，极大值为。

测试参数为种群规模100，个体编码长度20，交叉概率0.9，变异概率0.01，小生境半径0.5，Penalty=1E-30。下面给出相关测试数据。从表中可以看出，随着进化代数的增加，原算法种群的多样性快速下降，而改进算法种群的多样性能稳定在一个理想的水平，这表明改进算法有更多机会搜寻到更多的峰。由于新算法采用（2+2）竞争选择机制，较原算法增加了计算量，因此对于相同进化代数，改进算法的运行时间比原算法略长。但在相同的进化代数下，两者的搜索效率是不同的。仿真实验表明，采用同样的参数，原算法和改进算法对五峰函数搜索到全部峰的百分比分别约为92%和99%，对六峰值驼背函数分别约为67%和86%，鉴于此我们认为改进算法的相对收敛速度高于原算法。下面给出用基于罚函数改进的小生境遗传算法优化函数的例子。例1、初始群体（群体大小M=100）第1代群体第5代群体求最小值时的第100代群体例2、Shubert函数此函数共有760个局部极小点，其中18个为全局最小点，最小值为-186.7309。以下给出某一次计算出的全部18个为全局最小点的具体数值，其中第1、2列为横、纵坐标，第3列为目标函数值，第4列为适应度。这个结果的精确度超过了所有公开报道的计算结果。

4.8578-7.0835-186.730710.33654.8578-0.8003-186.730710.33654.85785.4829-186.730710.33655.4828-1.4251-186.730910.33655.4828-7.7083-186.730910.33655.48284.8581-186.730910.3365-1.4252-7.0835-186.730910.3365-1.4252-0.8003-186.730910.3365-1.42525.4829-186.730910.3365-7.7083-7.0835-186.730910.3365-7.7083-0.8003-186.730910.3365-0.8003-1.4251-186.730910.3365-0.8003-7.7083-186.730910.3365-7.0835-1.4251-186.730910.3365-7.0835-7.7083-186.730910.3365-0.80034.8581-186.730910.3365-7.08354.8581-186.730910.3365-7.70835.4829-186.730910.33652、基于改进K—均值聚类分析的排挤小生境遗传算法适应值共享算法是遗传算法解决多峰优化问题的重要手段之一。标准适应值共享算法要求事先知道小生境半径，并假设解空间中小生境具有相同的小生境半径。本文1中讨论的排挤小生境算法同样也要预先设定适当的峰半径，否则算法不能保证求出所有最优解。然而，在实际多峰优化问题中峰半径往往无法事先估计。聚类分析作为一种有效的数据分析手段，已经在模式识别、知识获取、数据挖掘等多个领域获得了比较广泛的应用。将聚类分析与排挤小生境遗传算法相结合，可以在一定程度上解决峰半径的设定问题，大大提高算法的实用性。在聚类分析方法中最常用的是K—均值聚类方法，其基本流程如下：①随机产生q个中心；②将每一个点按照某种距离量度分配到最近的一个中心；③对于每一个中心，计算所有属于此中心的点的重心，作为新的中心坐标；④如果某个中心发生变化，转到②；⑤计算结束，返回q个中心位置。上述K—均值算法只能产生预定的q个聚类中心，在预先难以确定小生境数目时，往往只能取一个估计的保守值。这样，如果第①步中中心的位置不理想，会导致最后计算出来的中心不能真实反映群体的小生境数。为了弥补这个缺陷，我们将通常的K—均值聚类方法做了改进，引进了一个最小聚类距离。在第③步后，如果有两个中心之间的距离小于最小聚类距离，则将这两个中心合并。使用改进后的算法产生出来的聚类数目可能小于预定值，能在很大程度上反映出群体中实际的小生境数。本文通过对小生境遗传算法的分析，提出了一种新的基于聚类分析的排