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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第三部分 现代优化方法选讲,第三部分 现代优化方法选讲,现代优化方法包括禁忌搜索、模拟退火、智能计算等。,其中模拟退火、神经网络和遗传算法并称为现代优化算法中的三大杰出代表。,现代优化方法包括禁忌搜索、模拟退火、智能计算,一、模拟退火算法,在管理科学、计算机科学、分子物理学、生物学、超大规模集成电路设计、代码设计、图象处理和电子工程等领域中，存在着大量的组合优化问题。例如，货郎担问题、最大截问题、,01,背包问题、图着色问题、设备布局问题以及布线问题等，这些问题至今仍未找到多项式时间算法。这些问题已被证明是,NP,完全问题。,一、模拟退火算法,根据,NP,完全性理论，除非,P=NP,，否则所有的,NP,难问题都不存在多项式时间算法。但是，这并不意味着问题的终结。相反，由于这类问题广泛应用性，反而刺激人们以,更大的热情对,NP,完全问题进行研究。,为解决这类问题，人们提出了许多近似算法，但这些算法或过于注意个别问题的特征而缺乏通用性，或因所得解强烈地依赖初始解的选择而缺乏实用性。模拟退,根据NP完全性理论，除非P=NP，否则所有的NP难问题都不存,火算法是近年提出的一种适合解大规模组合优化问题，特别是解,NP,完全问题的通用有效的近似算法，与以往近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制的优点，而且特别适合并行计算，因此具有很大的使用价值。同时由于其讨论涉及随机分析、马氏链理论、渐进收敛性等学科，所,以其研究还具有重要的理论意义。,火算法是近年提出的一种适合解大规模组合优化问题，特别是解NP,1.,模拟退火算法的物理背景,固体退火过程的物理图象和统计性质是模拟退火算法的物理背景。在热力学与统计物理学的研究领域中，固体退火是其重要的研究对象。固体退火是指先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程。,1. 模拟退火算法的物理背景,在高温状态下，液体的分子彼此之间可以自由移动。如果液体徐徐冷却，它的分子就会丧失由于温度而引起的流动性。这时原子就会自己排列起来而形成一种纯晶体，它们依次地朝各个方向几十亿倍于单个原子大小的距离，这个纯晶状态就是该系统的最小能量状态，有趣的是：对于一个徐徐冷却的系统，当这些原子在逐渐失去活力的同时，它们自己就同时地排列,在高温状态下，液体的分子彼此之间可以自由移动,而形成一个纯晶体，使这个系统的能量达到其最小值。这里我们特别强调在这个物理系统的冷却过程中，这些原子就同时的把它们自己排列成一个纯晶体的。如果一种金属熔液是被快速的冷却，则它不能达到纯晶体状态，而是变成一种多晶体或非晶体状态，系统处在这种状态时具有较高的能量。,而形成一个纯晶体，使这个系统的能量达到其最小值。这里我们特别,模拟退火算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术，可用马氏链的遍历理论给它以数学上的描述。在搜索最优解的过程中，模拟退火除了可以接受优化解外，还用一个随机准则,(Metropolis,准则,),有限地接受恶化解，并使接受恶化解的概率逐渐趋于零，这使得算法有可能从局部最优解中跳出，尽可能找到全局最优解，并保证了算法的收敛性。,模拟退火算法就是模仿上述物理系统徐徐退火过程,1982,年,Kipatrick,等人首次把固体退火与组合极小化联系在一起，他们分别用目标函数和组合极小化问题的解替代物理系统的能量和状态，从而物理系统内粒子的摄动等价于组合极小化问题中解的试探。极小化过程就是：首先在一个高温（温度现在就成为一个参数控制）状态下有效的“溶化”解空间，然后慢慢地降低温度直到系统“晶体”到一个稳定解。,1982年Kipatrick等人首次把固体退,通过以下示例，我们可以将组合优化问题与固体退火进行类比：,组合优化问题 固体退火,解 状态,最优解 能量最低状态,费用函数 能量,通过以下示例，我们可以将组合优化问题与固体退,2.,模拟退火算法的基本思想与算法,用传统优化算法优化多峰值函数时，往往由于过分追求“下降”而极易陷于局部最优解。为了克服这个缺陷，在搜索最优解的过程中，模拟退火方法除了接受优化解外，还根据一个随机接受准则有限地接受恶化解，并使接受恶化解的概率逐渐趋于零。这既可使得算法以较大概率跳出局部最优解，又保证了算法的收敛性。,2. 模拟退火算法的基本思想与算法,模拟退火算法的求解过程如下：,(1),随机产生初始解,X,0,，给定初始温度,T,0,，令,k=0,；,(2),随机产生新解 ，并计算函数增量,(3),若 ，则接受新解， ，转,(2),，否则以概率 决定是否接受新解。具体方法是：产生,0,和,1,之间的一个随机数,r,，若 ，接受新解，否则拒,模拟退火算法的求解过程如下：,绝新解；,(4),重复第,(2),(3),步若干次，使解接近当前温度下的最优解，这相当于用足够慢的速度降温，以保证在每个温度时系统都能处于当前温度下的能量最低状态；,(5),按一定的方式降低温度，例如 ，其中 ；,(6),若满足收敛条件，退火过程结束，否则,，转,(2),。,绝新解；,通常 ，收敛条件为 。,理论已证明：只要初始温度足够高，退火过程足够慢，模拟退火算法以概率,1,收敛到全局最优解。,通常,模拟退火算法在许多领域有非常广泛的应用，尤其适用于求解组合优化问题。如旅行商问题,(TSP),、,0-1,背包问题,(ZKP),、最大截问题,(MCP),、独立集问题,(ISP),、调度问题,(SCP),、图着色问题,(GCP),等。,例,用模拟退火算法求,的极小值。,模拟退火算法在许多领域有非常广泛的应用，尤其,3.,模拟退火算法的应用,模拟退火算法具有广泛的应用性，可用于求解许多组合优化问题。根据模拟退火算法的过程（产生新解,计算目标函数差,判别是否接受新解,接受或舍弃新解），在算法的实际应用中必须解决好三个问题：第一，问题的数学描述；第二，新解的产生和接受机制；第三，冷却进度表的选取。冷却进度表包括：初始温,3. 模拟退火算法的应用,度、降温策略、马氏链长度以及停止准则四个方面。 此外，还包括随机数发生器。,问题的描述主要包括解空间和目标函数两部分。解空间为所有可行解的集合，它限定了初始解选取和新解产生的范围。对于无约束优化问题，任一可能解即为可行解；对于有约束优化问题，解集中还可以包含一些不可行解，同时在目标函数中加上惩函数，以惩罚出现的不可行解。,度、降温策略、马氏链长度以及停止准则四个方面。 此外，还包括,新解的产生和接受可分为四个步骤：第一，给出新解的变换方法，得到一个产生装置，以从当前解产生一个新解；第二，计算新解和当前解的目标函数差，由于目标函数差仅由变换部分产生，因此，通常按增量计算目标函数差；第三，判断新解是否被接受，判断的依据是,Metropolis,准则，对于有约束优化问题往往还伴随有新解可行性的判断；第四，接受或舍弃新,新解的产生和接受可分为四个步骤：第一，给出新,解，若接受，用新解代替当前解，同时修正目标函数值，否则当前解与目标函数值保持不变。,下面仅对几个典型的组合优化问题给出算法描述，以揭示其建立数学模型和新解产生装置的基本方法。,解，若接受，用新解代替当前解，同时修正目标函数值，否则当前解,(1),旅行商问题（,tsp,）,设有,n,个城市和距离矩阵 ，其中 表示城市,i,到城市,j,的距离，,i,j=1,，,n,，则问题是寻找遍访每个城市恰好一次的一条回路，且其路径长度为最短。,求解的模拟退火算法描述如下：, 解空间,解空间,S,可表为,1,2,，,，,n,的所有循环排列的集合，即,(1) 旅行商问题（tsp）,其中每一循环排列表示遍访,n,个城市的一条回路，,表示在第,i,个次序访问城市,j,，并约定 。初始解可选为（,1,2,，,，,n,）。, 目标函数,此时的目标函数为访问所有城市的路径长度之和，即,其中 。,其中每一循环排列表示遍访n个城市的一条回路，,新解的产生（,2,变换法）,任选访问的序号,u,和,v,，逆转,u,和,v,及其之间的访问顺序，此时新路径为（设,uv,）, 代价函数差,新解的目标函数差可由公式,计算。特别地，当问题为对称的，即距离矩阵,为对称矩阵时，上式可简化为, 新解的产生（2变换法）,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,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,个个体（,NM,）；,进行比例选择、单点交叉、基本位变异运算；,理后其适应度变得更差，在后面的进化过程中被淘汰的概率就极大。,小生境淘汰运算：将第步得到的,M,个个体和第步所记忆的,N,个个体合并在一起，得到一个含有,M+N,个个体的新群体。对这,M+N,个个体，求出每两个个体 和 之间的,Hamming,距离 。,当 时，比较个体 和 的适应度大小，并对其中适应度较低的个体处以罚函数；,根据这,M+N,个个体的新适应度对各个个体进行降序排序，记忆前,N,个个体；,终止条件判断：若不满足终止条件，则将第步排序中的前,M,个个体作为新的下一代群体，然,小生境淘汰运算：将第步得到的 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,）竞争选择机制，较原算法增加了计算量，因此对于相同进化代数，,测试参数为种群规模100，个体编码长度20，,改进算法的运行时间比原算法略长。但在相同的进化代数下，两者的搜索效率是不同的。仿真实验表明，采用同样的参数，原算法和改进算法对五峰函数搜索到全部峰的百分比分别约为,92%,和,99%,，对六峰值驼背函数分别约为,67%,和,86%,，鉴于此我们认为改进算法的相对收敛速度高于原算法。,下面给出用基于罚函数改进的小生境遗传算法优化函数的例子。,改进算法的运行时间比原算法略长。但在相同的进化代数下，两者的,例,1,、,初始群体（群体大小,M=100,）,例1、,第,1,代群体,第1代群体,第,5,代群体,第5代群体,求最小值时的第,100,代群体,求最小值时的第100代群体,例,2,、,Shubert,函数,此函数共有,760,个局部极小点，其中,18,个为全局最小点，最小值为,-186.7309,。,以下给出某一次计算出的全部,18,个为全局最小点的具体数值，其中第,1,、,2,列为横、纵坐标，第,3,列为目标函数值，第,4,列为适应度。这个结果的精确度超过了所有公开报道的计算结果。,例2、Shubert函数,现代优化方法之模拟退火课件,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.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.7309 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.3365,4.8578 -7.0835 -186.73,现代优化方法之模拟退火课件,2,、基于改进,K,均值聚类分析的排挤小生境遗传算法,适应值共享算法是遗传算法解决多峰优化问题的重要手段之一。标准适应值共享算法要求事先知道小生境半径，并假设解空间中小生境具有相同的小生境半径。本文,1,中讨论的排挤小生境算法同样也要预先设定适当的峰半径，否则算法不能保证求出所有最优解。然而，在实际多峰优化问题中峰半径往往无法事先估计。,2、基于改进K均值聚类分析的排挤小生境遗传算法,聚类分析作为一种有效的数据分析手段，已经在模式识别、知识获取、数据挖掘等多个领域获得了比较广泛的应用。将聚类分析与排挤小生境遗传算法相结合，可以在一定程度上解决峰半径的设定问题，大大提高算法的实用性。,在聚类分析方法中最常用的是,K,均值聚类方法，其基本流程如下：,聚类分析作为一种有效的数据分析手段，已经在模,随机产生,q,个中心；,将每一个点按照某种距离量度分配到最近的一个中心；,对于每一个中心，计算所有属于此中心的点的重心，作为新的中心坐标；,如果某个中心发生变化，转到；,计算结束，返回,q,个中心位置。,上述,K,均值算法只能产生预定的,q,个聚类中心，在预先难以确定小生境数目时，往往只能取一个估计的保守值。这样，如果第步中中心的,随机产生q个中心；,位置不理想，会导致最后计算出来的中心不能真实反映群体的小生境数。为了弥补这个缺陷，我们将通常的,K,均值聚类方法做了改进，引进了一个最小聚类距离 。在第步后，如果有两个中心之间的距离小于最小聚类距离 ，则将这两个中心合并。使用改进后的算法产生出来的聚类数目可能小于预定值，能在很大程度上反映出群体中实际的小生境数。,位置不理想，会导致最后计算出来的中心不能真实反映群体的小生境,本文通过对小生境遗传算法的分析，提出了一种新的基于聚类分析的排挤小生境算法，这种算法将聚类分析、排挤技术有机地结合起来，可以有效地搜索多模函数空间的多个极值点，同时可以通过调节最小聚类距离控制收敛到的小生境的数目，避免找到无效的极值点，这种算法无需事先确定生境的具体数目和生境半径的大小，能够适应各种问题的优化。,本文通过对小生境遗传算法的分析，提出了一种新,算法的具体步骤如下：,随机生成,M,个初始个体组成初始群体，并计算适应度；,根据各个个体的适应度对其进行降序排序，记忆前,N,个个体,(NM),；,使用改进的,K,-,均值算法对群体进行聚类分析，将群体划分为,q,个聚类；,计算每个聚类中个体的数目，计算个体的竞争适应度；,按照个体适应度进行选择、交叉、变异运算；,算法的具体步骤如下：,将第步得到的,M,个子代个体和第步所记忆的,N,个个体合并在一起，得到一个含有,M+N,个个体的新群体。确定新群体中的个代属于哪个聚类，在每一个聚类中计算每两个个体和的适应度大小，并对其中适应度较低的个体处以罚函数；,根据这,M+N,个个体的新适应度对各个个体进行降序排序，记忆前,N,个个体；,终止条件判断：若不满足终止条件，则将第步排序中的前,M,个个体作为新的下一代群体，然后转到第步；若满足终止条件，则输出计算结,将第步得到的M个子代个体和第步所记忆的N个个体合并在,果，算法结束。,3,、数值实验,为了测试基于改进,K,均值聚类分析的排挤小生境遗传算法的性能，我们选择了下列几个难度较大的标准测试函数。,例,3,、,不均匀分布等高峰函数,该函数有,5,个不均匀分布的峰，分别为，,峰高均为,1.000,。,果，算法结束。,现代优化方法之模拟退火课件,例,4,、,不均匀分布不等高峰函数,该函数有,5,个不均匀分布的峰，分别为,峰高分别为 。,例4、不均匀分布不等高峰函数,例,6,、,二元不均匀分布等高峰函数,该函数有,4,个不均匀分布的峰，分别在,峰高均为,2500,。,由图形可以看出，该函数的峰比较平坦，性能不佳的算法很难精确搜索到全部四个峰。,例6、二元不均匀分布等高峰函数,现代优化方法之模拟退火课件,下面给出用基于改进,K,均值聚类分析的排挤小生境遗传算法连续三次的计算结果。,x = 3.0000 -3.7687 -2.8037 3.5845,y = 2.2509 -3.2798 3.1230 -1.8486,z = 2498.8 2500.0 2500.0 2500.0,x =-3.7500 3.5625 3.0030 -2.8076,y =-3.2549 -1.8427 1.9980 3.1318,z = 2499.9 2500.0 2500.0 2500.0,x =-2.8125 3.0034 -3.7778 3.5845,y =3.1289 1.9981 -3.2827 -1.8457,z = 2500.0 2500.0 2500.0 2500.0,下面给出用基于改进K均值聚类分析的排挤小生,现代优化方法之模拟退火课件,现代优化方法之模拟退火课件,现代优化方法之模拟退火课件,例,6,、,复杂欺骗性问题,其中， ， 定义为：,显然， 是一个简单欺骗性问题，它有两个高度为,1,的峰和一个高度为,0.640576,的峰。复杂欺骗性问题由,5,个这样的简单欺骗性问题相加而成，,例6、复杂欺骗性问题,它的峰的数量约为 ，其中全局峰仅有,32,个，分别在,，,，,。之所以称之为复杂欺骗性问题，不仅因为其巨大的局部峰数量，而且因为众多的局部峰包围着全局峰，这就使得即使较好的算法也极难寻找到所有全局峰。,大量计算显示，本文提出的算法在优化复杂欺骗性问题时效果欠佳，多数情况下只能找到,8,个全局最优解，只有偶尔能找到,16,个全局最优解。,它的峰的数量约为 ，其中全局峰仅,现代优化方法之模拟退火课件,例,7,、,复杂多峰函数,其中,该函数有,8,个不均匀分布的峰，峰的高度相差比较悬殊，很难同时搜索到所有,8,个峰。,例7、复杂多峰函数,现代优化方法之模拟退火课件,现代优化方法之模拟退火课件,现代优化方法之模拟退火课件,现代优化方法之模拟退火课件,现代优化方法之模拟退火课件,现代优化方法之模拟退火课件,现代优化方法之模拟退火课件,一、概念,1,、梯度,2,、海色（,Hessain,）矩阵,3,、凸函数,4,、共轭方向,二、问题,1,、最优化中下降算法的基本思想和算法结构,2,、,0.618,法的基本思想与步骤,3,、最速下降法的缺陷,4,、拟牛顿法对牛顿法的改进之处,一、概念,三、,证明：在最速下降法中，相邻两次搜索方向正交。,四、,模拟退火算法与遗传算法与传统优化方法相比各有什么优缺点？,五、你能否搜集一些资料，说明本门课中所介绍的一些优化算法，特别是现代优化算法可以用于解决你所学专业中的某些问题。,三、证明：在最速下降法中，相邻两次搜索方向正交。,两条巷道间的最短距离,这是一个来自新集煤矿的实际问题。,某矿井中有两条巷道，巷道可近似为半圆柱面，现要求一条巷道的工作面到另一条巷道的最短距离。,根据建立的坐标系和现场数据，可以得出其中一条巷道工作面所在的平面方程为,巷道工作面为下列四个点所围成的矩形部分,两条巷道间的最短距离,另一条巷道的方程为,根据上述数据计算工作面到巷道的最短距离。,现代优化方法之模拟退火课件,考核方式及所占比例：,平时出勤（,20%,）,+,实际问题建模计算（,30%,）,+,书面考试（闭卷）（,50%,）,下周一书面考试，下周五交实际问题计算答卷。,考核方式及所占比例：,知识回顾,Knowledge Review,祝您成功！,知识回顾Knowledge Review祝您成功！,