《机械故障诊断学钟秉林第8章模拟退火与演化算法原理课件》由会员分享，可在线阅读，更多相关《机械故障诊断学钟秉林第8章模拟退火与演化算法原理课件（90页珍藏版）》请在金锄头文库上搜索。
1、第8章 模拟退火与演化算法的原理及应用l 模拟退火算法原理l 演化算法原理l 模拟退火和演化算法在知识获取中的应用机械故障诊断理论与方法第2篇 基于人工智能的故障诊断技术 2022/5/131内容安排一、概述 故障故障的分类和诊断本质上可以理解为一种优化过程，即在所有可能的分类或诊断结论中寻找寻找一个最佳的结果来解释所获得的故障样本。因此，分类和诊断问题可以通过选择合适的目标函数转换为函数优化或组合优化问题。2022/5/132 模拟退火算法和演化算法是两种具有全局最优性能优化方法，前者前者模拟物理学中固体物质的高温退火过程，后者后者则借鉴生物界自然选择和进化机制以获取函数的最优解。本章主要介
2、绍着两种算法的基本原理及其应用。 定义：组合优化问题是一个最小化问题，或是一个最大化问题，它由下面三部分组成：(1) 实例集合；(2) 对每一个实例 I，有一个有穷的可行解集合 S(I)；(3) 目标函数 f，它对每一个实例 I 和每一个可行解 ，赋以一个有理数 。 一、概述1.组合优化问题2022/5/133一个通俗的定义：一个通俗的定义：p所谓组合优化，是指在离散的、有限的数学结构上，寻找一个（或一组）满足给定约束条件并使其目标函数值达到最大或最小最大或最小的解。p一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全（难）问题
3、，因此，精确地求解组合优化问题的全局最优解的“有效”算法一般是不存在的。一、概述2022/5/134典型的组合优化问题典型的组合优化问题主要有如下几种：集覆盖问题（set-covering problem）装箱问题（bin-packing problem）0-1背包问题（knapsack problem）指派问题（assignment problem）旅行商问题（traveling salesman problem）TSP、货郎担问题影片递送问题（film delivery problem）图划分问题（graph partitioning problem）作业调度问题（job-shop sch
4、eduling problem）一、概述2022/5/135集覆盖问题集覆盖问题（set-covering problem）对于一个m行n列的01矩阵A，每行代表一种任务，每列代表一个人，aij=1表示第j个人能完成第i个任务。每个人都有一个雇佣代价。问题的目标是：用最小的代价选择一些人（矩阵的列），使得每一个任务都至少有一个人能完成。设向量x的元素 xj=1 表示列 j 被选中（费用是cj0）， xj=0 则表示其未被选中（j=1,2,n）。已经证明集覆盖问题是NP完全问题。一、概述2022/5/136如果所有费用费用cj都相同，则问题称为单一费用问题（unicost set-coverin
5、g problem）。如果为等式约束，则称为集划分问题（set partitioning problem）一、概述2022/5/137Cost = 291 0 1 0 1 0一、概述2022/5/1382022/5/139装箱问题装箱问题（bin packing problem）所装物品不得超过不得超过箱子的容积一个物品只能只能放入一个箱子用最少最少的箱子将所有所有物品都装下一、概述2022/5/1310货运装箱问题截铜棒问题布匹套裁问题。装箱问题属于NP难问题一、概述2022/5/13110/1背包问题：背包问题：给出几个体积为S1，S2，Sn的物体和容量为C的背包；要求找出n个物件的一个子
6、集使其尽可能多尽可能多地填满容量为C的背包。数学形式： 最大化 满足 一、概述2022/5/1312广义背包问题：广义背包问题：输入由背包容积C和两个向量：物品体积S(S1，S2，Sn)和物品价值P(P1，P2，Pn)组成。设X为一整数集合（物品的标识），X1，2，3，n，T为X的子集，则问题就是找出满足约束条件，并使总价值最大的子集T。 数学形式： 最大化 满足 一、概述2022/5/1313在应用问题中，设S的元素是n项经营活动各自所需的资源消耗，C是所能提供的资源总量，P的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。背
7、包问题属于NP-难问题一、概述2022/5/1314多选择背包问题：多选择背包问题：有一个容积有限的背包。要放入背包的物品被分为不重叠的若干类，每类中有若干不同的物品，从每类中选择选择一个物品，使得物品总体积在满足背包容积约束的前提下最大化收益。属于NP难问题一、概述2022/5/1315i为类下标；j为类中物品的下标；ni是第i类中物品的数量；cij是第i类中第j个物品的收益；m是类的数量；wij为第i类中第j个项目的体积，W是背包的容积。最大化最大化所选物品的总价值所选物品的总体积不不得超过得超过背包容积每一类中只能只能选一个物品一、概述2022/5/1316旅行商问题旅行商问题（Trav
8、eling Salesman Problem）寻找一条最最短短的遍历n个城市的路径，或或者者说搜索整数子集X1，2，n（X的元素表示对n个城市的编号）的一个排列(X) = v1，v2，vn，使下式取最小值。式中的d(vi, vi+1)表示城市vi到城市vi+1的距离。对称旅行商问题是NP难问题一、概述2022/5/1317影片递送问题影片递送问题（Film Delivery Problem）一盘影片拷贝要在n个电影院放映。每个电影院放映的次数已定，记为一个非负的整数di(i1，2，n)。两个影院间的距离记为wij，若影院i和j不能直接相连，则令wij+。问题是要为影片递送员找一个巡回，从主影院
9、1开始，将影片拷贝送到第i家影院di(i1，2，n)次，最后最后回到主影院1，并极小化极小化总的路线长度。当所有的di(il，2，n)为1时，FDP变为经典的TSP。FDP是TSP的新新扩展，它可以推广到一大类路径与排序问题中。一、概述2022/5/1318图的二划分问题图的二划分问题：对于一无向图G，设其顶点集合为V，将顶点集合V划分为两个子集V1和V2，Vl V2 ，求使V1和V2两顶点子集之间联结最少的一种划分。图的划分问题在电子线路设计中非常重要。例如，在多层印刷电路板的布局设计中，使层间联线数目最少的器件布局等。由于图的划分问题的计算复杂度极高(3000个节点的二划分问题的搜索空间可
10、达10900)，因此，在实用规模上精确求出最优解是不可能的。一、概述2022/5/1319广义地讲，调度问题考虑的是随着时间的变化，如何调度有限的资源在执行任务的同时满足特定约束。资源：人力、金钱、机器、工具、材料、能源、等等。任务：制造系统的加工工序；计算机系统的信息处理。任务的表征：完成时间、预期时间、相对紧急权重、处理时间和资源消耗。一、概述2022/5/1320经典作业车间调度问题经典作业车间调度问题（Job-shop Scheduling）：有m台不同的机器和n个不同的工件，每个工件包含包含一个由多道工序组成的工序集合，工件的工序顺序是预先给定的。每道工序用它所要求的机器和固定的加工
11、时间来表示。此外对工件和机器有一些约束，例如：(1) 一个工件不能两次访问同一机器；(2) 不同工件的工序之间没有先后约束；(3) 工序一旦进行不能中断； (4) 每台机器一次只能加工一个工件；(5) 下达时间和交货期都不是给定的。问题：问题：确定机器上工序的顺序，以最小化完成所有工件所需的最小加工持续时间。一、概述2022/5/1321局部搜索算法是基于贪婪思想利用邻域函数进行搜索的，容易容易实现实现，但但其搜索性能完全依赖于邻域函数和初始解的选取，领域函数设计不当或初始解选择不合适，算法的最终性能将会很差很差；同时贪婪思想也导致导致其最终解只具有局部最优性；此外，局部搜索算法的时间复杂性取
12、决于取决于问题的性质与邻域结构的复杂程度。鉴于局部搜索算法的上述缺点缺点，许多学者提出了各种各样的方法来改善算法的性能。模拟退火算法和演化算法从不同的角度，利用不同的搜索机制和实现策略实现了实现了对局部搜索算法的改进，具有了全局最优的性能，成为两种较为成功较为成功的全局优化算法。一、概述2.组合优化问题的局部搜索算法2022/5/1322算法的提出算法的提出 模拟退火算法(Simulated Annealing,简称SA)的思想最早是由Metropolis等(1953)提出提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Monte Carlo迭代求解策略的一种随机寻优
13、算法，其出发点出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。算法的目的算法的目的 解决NP复杂性问题； 克服优化过程陷入局部极小； 克服初值依赖性。二、模拟退火算法2022/5/1323 模拟退火算法模拟退火算法在某一初温下，伴随伴随温度参数的不断下降，结合结合概率突跳特性在解空间中随机寻找寻找目标函数的全局最优解，即即在局部优解能概率性地跳出跳出并最终最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。 二、模拟退火算法2022/5/1324局部优解全局最优解概率突跳特性l什么什么是退火：是退火： 退火是指将固体加热到足够高的温度（不能加
14、热到熔解温度，得保持形状和尺寸），使分子呈随机排列状态，然后然后逐步降温使之冷却，最后最后分子以低能状态排列，固体达到某种稳定状态。l退火退火目的目的： 使金属的显微结构更加规则化，并消除前道工序所产生的内应力。l简单而言简单而言，物理退火过程由以下三部分组成：1. 物理退火过程和Metropolis准则二、模拟退火算法2022/5/1325 退火过程退火过程 加温过程：加温过程： 其目目的的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔解为液体，从而消消除除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起起点点。熔解过程与系统的熵增过程联系，系统能能量量也随温
15、度的升高而增大。 等温过程等温过程： 物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封封闭闭系系统统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小最小时，系统达到平衡态。 冷却过程：冷却过程： 目的目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降下降，从而得到低能的晶体结构。 二、模拟退火算法2022/5/1326Metropolis等在1953年提出了重要性采样法，即即以概率接受新状态。具体而言：首先首先，在温度T，给定固体初始状态i 作为当前状态，由当前状态i随机产生新状态j，两者的能量分别为Ei和Ej。然后判断判断： 若Ej Ei，则接受接受新状态j为当前
16、“重要”状态，否则， 若Ej Ei，则该状态是否是否“重要”要依据固体处于该状态的概率进行判断，其方法如下： 二、模拟退火算法2022/5/1327Metropolis准则准则 计算r=P(Ej)/P(Ei)=exp(Ei-Ej)/kT，显然r1，其中P(E)为系统处于能量E的概率、T为系统绝对温度、k为Boltzmann常数。 产生一个0,1区间的随机数，若r ，则新状态作为重要状态，否则舍去。 若新状态为重要状态，则则以新状态为当前状态（否则仍以原状态i为当前状态）。 重复以上新状态产生过程。二、模拟退火算法2022/5/1328 在大量固体状态的变换（也称迁移）后，固体趋于能量较低的平衡状态，固体状态的概率分布趋于Gibbs正则分布： P(E) exp(-E/kT) 上述以一定的概率接受新状态的准则称为Metropolis准则，相应算法称为Metropolis算法。l由r=exp(Ei-Ej)/kT可知，高温下可接受与当前状态能差较大较大的新状态为重要状态，而在低温下只能只能接受与当前状态能差较小较小的新状态为重要状态，这与不同温度下热运动的影响完全一致。在温度趋于0时，不能接受
