现代优化方法之模拟退火课件

1、第三部分 现代优化方法选讲 现代优化方法包括禁忌搜索、模拟退火、智能计算等。其中模拟退火、神经网络和遗传算法并称为现代优化算法中的三大杰出代表。一、模拟退火算法 在管理科学、计算机科学、分子物理学、生物学、超大规模集成电路设计、代码设计、图象处理和电子工程等领域中，存在着大量的组合优化问题。例如，货郎担问题、最大截问题、01背包问题、图着色问题、设备布局问题以及布线问题等，这些问题至今仍未找到多项式时间算法。这些问题已被证明是NP完全问题。根据NP完全性理论，除非P=NP，否则所有的NP难问题都不存在多项式时间算法。但是，这并不意味着问题的终结。相反，由于这类问题广泛应用性，反而刺激人们以更大

2、的热情对NP完全问题进行研究。 为解决这类问题，人们提出了许多近似算法，但这些算法或过于注意个别问题的特征而缺乏通用性，或因所得解强烈地依赖初始解的选择而缺乏实用性。模拟退火算法是近年提出的一种适合解大规模组合优化问题，特别是解NP完全问题的通用有效的近似算法，与以往近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制的优点，而且特别适合并行计算，因此具有很大的使用价值。同时由于其讨论涉及随机分析、马氏链理论、渐进收敛性等学科，所以其研究还具有重要的理论意义。 在高温状态下，液体的分子彼此之间可以自由移动。如果液体徐徐冷却，它的分子就会丧失由于温度而引起的流动性。这时

3、原子就会自己排列起来而形成一种纯晶体，它们依次地朝各个方向几十亿倍于单个原子大小的距离，这个纯晶状态就是该系统的最小能量状态，有趣的是：对于一个徐徐冷却的系统，当这些原子在逐渐失去活力的同时，它们自己就同时地排列 而形成一个纯晶体，使这个系统的能量达到其最小值。这里我们特别强调在这个物理系统的冷却过程中，这些原子就同时的把它们自己排列成一个纯晶体的。如果一种金属熔液是被快速的冷却，则它不能达到纯晶体状态，而是变成一种多晶体或非晶体状态，系统处在这种状态时具有较高的能量。 1982年Kipatrick等人首次把固体退火与组合极小化联系在一起，他们分别用目标函数和组合极小化问题的解替代物理系统的能

4、量和状态，从而物理系统内粒子的摄动等价于组合极小化问题中解的试探。极小化过程就是：首先在一个高温（温度现在就成为一个参数控制）状态下有效的“溶化”解空间，然后慢慢地降低温度直到系统“晶体”到一个稳定解。 通过以下示例，我们可以将组合优化问题与固体退火进行类比： 组合优化问题 固体退火 解 状态 最优解 能量最低状态 费用函数 能量2. 模拟退火算法的基本思想与算法 用传统优化算法优化多峰值函数时，往往由于过分追求“下降”而极易陷于局部最优解。为了克服这个缺陷，在搜索最优解的过程中，模拟退火方法除了接受优化解外，还根据一个随机接受准则有限地接受恶化解，并使接受恶化解的概率逐渐趋于零。这既可使得算

5、法以较大概率跳出局部最优解，又保证了算法的收敛性。绝新解； (4) 重复第(2),(3)步若干次，使解接近当前温度下的最优解，这相当于用足够慢的速度降温，以保证在每个温度时系统都能处于当前温度下的能量最低状态；(5) 按一定的方式降低温度，例如 ，其中 ；(6) 若满足收敛条件，退火过程结束，否则 ，转(2)。 通常 ，收敛条件为 。 理论已证明：只要初始温度足够高，退火过程足够慢，模拟退火算法以概率1收敛到全局最优解。 3. 模拟退火算法的应用 模拟退火算法具有广泛的应用性，可用于求解许多组合优化问题。根据模拟退火算法的过程（产生新解计算目标函数差判别是否接受新解接受或舍弃新解），在算法的实

6、际应用中必须解决好三个问题：第一，问题的数学描述；第二，新解的产生和接受机制；第三，冷却进度表的选取。冷却进度表包括：初始温度、降温策略、马氏链长度以及停止准则四个方面。 此外，还包括随机数发生器。 问题的描述主要包括解空间和目标函数两部分。解空间为所有可行解的集合，它限定了初始解选取和新解产生的范围。对于无约束优化问题，任一可能解即为可行解；对于有约束优化问题，解集中还可以包含一些不可行解，同时在目标函数中加上惩函数，以惩罚出现的不可行解。 新解的产生和接受可分为四个步骤：第一，给出新解的变换方法，得到一个产生装置，以从当前解产生一个新解；第二，计算新解和当前解的目标函数差，由于目标函数差仅

7、由变换部分产生，因此，通常按增量计算目标函数差；第三，判断新解是否被接受，判断的依据是Metropolis准则，对于有约束优化问题往往还伴随有新解可行性的判断；第四，接受或舍弃新 解，若接受，用新解代替当前解，同时修正目标函数值，否则当前解与目标函数值保持不变。 下面仅对几个典型的组合优化问题给出算法描述，以揭示其建立数学模型和新解产生装置的基本方法。 (1) 旅行商问题（tsp） 设有n个城市和距离矩阵 ，其中 表示城市i 到城市j的距离，i,j=1,，n，则问题是寻找遍访每个城市恰好一次的一条回路，且其路径长度为最短。 求解的模拟退火算法描述如下： 解空间 解空间S可表为1,2，n的所有循

8、环排列的集合，即其中每一循环排列表示遍访n个城市的一条回路， 表示在第i个次序访问城市j，并约定 。初始解可选为（1,2，n）。 目标函数 此时的目标函数为访问所有城市的路径长度之和，即其中 。int d1111=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,

9、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;非数值并行算法模拟退火算法康立山科学出版社理后其适应度变得更差，在后面的进化过程中被淘汰的概率就极大。也就是说，在距离 L之内将只存在一个优良的个体，从而既维护了群体的多样性，又使得各个个体之间保持一定的距离。 上述小生境遗传算法具体实现过程如下：随机生成M 个初始

10、个体组成初始群体，并计算适应度 ；根据各个个体的适应度对其进行降序排序，记忆前N个个体（NM）；进行比例选择、单点交叉、基本位变异运算；小生境淘汰运算：将第步得到的 M个个体和第步所记忆的 N 个个体合并在一起，得到一个含有M+N个个体的新群体。对这M+N个个体，求出每两个个体 和 之间的Hamming距离 。 当 时，比较个体 和 的适应度大小，并对其中适应度较低的个体处以罚函数；根据这M+N个个体的新适应度对各个个体进行降序排序，记忆前N个个体；终止条件判断：若不满足终止条件，则将第步排序中的前M个个体作为新的下一代群体，然 后转到第步；若满足终止条件，则输出计算结果，算法结束。 本文对上

11、述算法做了两处改进。第一，原算法用Hamming距离来衡量两个个体的远近程度。我们认为这是不妥的，因为即使海明距离很小的两个个休，其实际距离也可能很大。本文采用欧氏距离来衡量个体的远近程度。第二，原算法在进行小生境运算时采用的是通常的（1+1）淘汰。Goldberg指出，在小生境的竞争选择机制中，(+)选择机制具有较强的选择压，可有效地提高种群的多样性。(+)选择允许个父代个体和个子代个体共同竞争，确定性地选择高适应值个体进入新的种群。仿真实验表明，用(+)竞争选择能大大提高种群的多样性，产生较快的收敛速度。综合考虑计算速度和计算量，本文采用（2+2）竞争选择机制。 为了定量描述改进后算法维持

12、种群多样性的能力以及收敛速度的提高程度，我们采用下列函数表示种群的多样性程度 其中n为种群规模， 为个体的二进制编码长度， 为种群中第i个个体的第j个二进制的值。显然，越小（大），种群的多样性就越高（低）。 测试函数为1、五峰函数 函数分别在 处有极大点，其中 为全局极大点。2、六峰值驼背函数函数有六个极大点其中为 全局极大点，极大值为 。 测试参数为种群规模100，个体编码长度20，交叉概率0.9，变异概率0.01，小生境半径0.5，Penalty=1E-30。 下面给出相关测试数据。 从表中可以看出，随着进化代数的增加，原算法种群的多样性快速下降，而改进算法种群的多样性能稳定在一个理想的水

13、平，这表明改进算法有更多机会搜寻到更多的峰。 由于新算法采用（2+2）竞争选择机制，较原算法增加了计算量，因此对于相同进化代数，改进算法的运行时间比原算法略长。但在相同的进化代数下，两者的搜索效率是不同的。仿真实验表明，采用同样的参数，原算法和改进算法对五峰函数搜索到全部峰的百分比分别约为92%和99%，对六峰值驼背函数分别约为67%和86%，鉴于此我们认为改进算法的相对收敛速度高于原算法。 下面给出用基于罚函数改进的小生境遗传算法优化函数的例子。 例1、初始群体（群体大小M=100） 第1代群体 第5代群体 求最小值时的第100代群体 例2、Shubert函数此函数共有760个局部极小点，其

14、中18个为全局最小点，最小值为-186.7309。 以下给出某一次计算出的全部18个为全局最小点的具体数值，其中第1、2列为横、纵坐标，第3列为目标函数值，第4列为适应度。这个结果的精确度超过了所有公开报道的计算结果。 4.8578 -7.0835 -186.7307 10.3365 4.8578 -0.8003 -186.7307 10.3365 4.8578 5.4829 -186.7307 10.3365 5.4828 -1.4251 -186.7309 10.3365 5.4828 -7.7083 -186.7309 10.3365 5.4828 4.8581 -186.7309 10

15、.3365 -1.4252 -7.0835 -186.7309 10.3365 -1.4252 -0.8003 -186.7309 10.3365 -1.4252 5.4829 -186.7309 10.3365 -7.7083 -7.0835 -186.7309 10.3365 -7.7083 -0.8003 -186.7309 10.3365 -0.8003 -1.4251 -186.7309 10.3365 -0.8003 -7.7083 -186.7309 10.3365 -7.0835 -1.4251 -186.7309 10.3365 -7.0835 -7.7083 -186.73

16、09 10.3365 -0.8003 4.8581 -186.7309 10.3365 -7.0835 4.8581 -186.7309 10.3365 -7.7083 5.4829 -186.7309 10.33652、基于改进K均值聚类分析的排挤小生境遗传算法 适应值共享算法是遗传算法解决多峰优化问题的重要手段之一。标准适应值共享算法要求事先知道小生境半径，并假设解空间中小生境具有相同的小生境半径。本文 1 中讨论的排挤小生境算法同样也要预先设定适当的峰半径，否则算法不能保证求出所有最优解。然而，在实际多峰优化问题中峰半径往往无法事先估计。 聚类分析作为一种有效的数据分析手段，已经在模式识

17、别、知识获取、数据挖掘等多个领域获得了比较广泛的应用。将聚类分析与排挤小生境遗传算法相结合，可以在一定程度上解决峰半径的设定问题，大大提高算法的实用性。 在聚类分析方法中最常用的是K均值聚类方法，其基本流程如下： 随机产生q个中心；将每一个点按照某种距离量度分配到最近的一个中心；对于每一个中心，计算所有属于此中心的点的重心，作为新的中心坐标；如果某个中心发生变化，转到；计算结束，返回q个中心位置。 上述K均值算法只能产生预定的q个聚类中心，在预先难以确定小生境数目时，往往只能取一个估计的保守值。这样，如果第步中中心的位置不理想，会导致最后计算出来的中心不能真实反映群体的小生境数。为了弥补这个缺

18、陷，我们将通常的K均值聚类方法做了改进，引进了一个最小聚类距离 。在第步后，如果有两个中心之间的距离小于最小聚类距离 ，则将这两个中心合并。使用改进后的算法产生出来的聚类数目可能小于预定值，能在很大程度上反映出群体中实际的小生境数。 本文通过对小生境遗传算法的分析，提出了一种新的基于聚类分析的排挤小生境算法，这种算法将聚类分析、排挤技术有机地结合起来，可以有效地搜索多模函数空间的多个极值点，同时可以通过调节最小聚类距离控制收敛到的小生境的数目，避免找到无效的极值点，这种算法无需事先确定生境的具体数目和生境半径的大小，能够适应各种问题的优化。 算法的具体步骤如下：随机生成M个初始个体组成初始群体

19、，并计算适应度；根据各个个体的适应度对其进行降序排序，记忆前N个个体(NM)；使用改进的K-均值算法对群体进行聚类分析，将群体划分为q个聚类；计算每个聚类中个体的数目，计算个体的竞争适应度；按照个体适应度进行选择、交叉、变异运算； 将第步得到的M个子代个体和第步所记忆的N个个体合并在一起，得到一个含有M+N个个体的新群体。确定新群体中的个代属于哪个聚类，在每一个聚类中计算每两个个体和的适应度大小，并对其中适应度较低的个体处以罚函数；根据这M+N个个体的新适应度对各个个体进行降序排序，记忆前N个个体； 终止条件判断：若不满足终止条件，则将第步排序中的前M个个体作为新的下一代群体，然后转到第步；若

20、满足终止条件，则输出计算结果，算法结束。 3、数值实验 为了测试基于改进K均值聚类分析的排挤小生境遗传算法的性能，我们选择了下列几个难度较大的标准测试函数。例3、不均匀分布等高峰函数该函数有5个不均匀分布的峰，分别为，峰高均为1.000。例4、不均匀分布不等高峰函数 该函数有5个不均匀分布的峰，分别为峰高分别为 。例6、二元不均匀分布等高峰函数该函数有4个不均匀分布的峰，分别在峰高均为2500。 由图形可以看出，该函数的峰比较平坦，性能不佳的算法很难精确搜索到全部四个峰。 下面给出用基于改进K均值聚类分析的排挤小生境遗传算法连续三次的计算结果。x = 3.0000 -3.7687 -2.803

21、7 3.5845y = 2.2509 -3.2798 3.1230 -1.8486z = 2498.8 2500.0 2500.0 2500.0 x =-3.7500 3.5625 3.0030 -2.8076y =-3.2549 -1.8427 1.9980 3.1318z = 2499.9 2500.0 2500.0 2500.0 x =-2.8125 3.0034 -3.7778 3.5845y =3.1289 1.9981 -3.2827 -1.8457z = 2500.0 2500.0 2500.0 2500.0例6、复杂欺骗性问题其中， ， 定义为： 显然， 是一个简单欺骗性问题，它有两个