机械故障诊断学钟秉林第8章模拟退火与演化算法原理课件.ppt

第8章 模拟退火与演化算法的原理及应用l 模拟退火算法原理l 演化算法原理l 模拟退火和演化算法在知识获取中的应用机械故障诊断理论与方法第2篇 基于人工智能的故障诊断技术 2023/5/26 1内容安排一、概述 故障的分类和诊断本质上可以理解为一种优化过程，即在所有可能的分类或诊断结论中寻找一个最佳的结果来解释所获得的故障样本。因此，分类和诊断问题可以通过选择合适的目标函数转换为函数优化或组合优化问题。2023/5/26 2 模拟退火算法和演化算法是两种具有全局最优性能优化方法，前者模拟物理学中固体物质的高温退火过程，后者则借鉴生物界自然选择和进化机制以获取函数的最优解。本章主要介绍着两种算法的基本原理及其应用。定义：组合优化问题是一个最小化问题，或是一个最大化问题，它由下面三部分组成：(1)实例集合；(2)对每一个实例 I，有一个有穷的可行解集合 S(I)；(3)目标函数 f，它对每一个实例 I 和每一个可行解，赋以一个有理数。一、概述1.组合优化问题2023/5/26 3一个通俗的定义：p 所谓组合优化，是指在离散的、有限的数学结构上，寻找一个（或一组）满足给定约束条件并使其目标函数值达到最大或最小的解。p 一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全（难）问题，因此，精确地求解组合优化问题的全局最优解的“有效”算法一般是不存在的。一、概述2023/5/26 4典型的组合优化问题主要有如下几种：集覆盖问题（set-covering problem）装箱问题（bin-packing problem）0-1背包问题（knapsack problem）指派问题（assignment problem）旅行商问题（traveling salesman problem）TSP、货郎担问题 影片递送问题（film delivery problem）图划分问题（graph partitioning problem）作业调度问题（job-shop scheduling problem）一、概述2023/5/26 5 集覆盖问题（set-covering problem）对于一个m行n列的01矩阵A，每行代表一种任务，每列代表一个人，aij=1表示第j个人能完成第i个任务。每个人都有一个雇佣代价。问题的目标是：用最小的代价选择一些人（矩阵的列），使得每一个任务都至少有一个人能完成。设向量x的元素 xj=1 表示列 j 被选中（费用是cj0），xj=0 则表示其未被选中（j=1,2,n）。已经证明集覆盖问题是NP完全问题。一、概述2023/5/26 6 如果所有费用cj都相同，则问题称为单一费用问题（unicost set-covering problem）。如果为等式约束，则称为集划分问题（set partitioning problem）一、概述2023/5/26 7 Cost=291 0 1 0 1 0一、概述2023/5/26 82023/5/26 9 装箱问题（bin packing problem）所装物品不得超过箱子的容积一个物品只能放入一个箱子用最少的箱子将所有物品都装下一、概述2023/5/26 10 货运装箱问题 截铜棒问题 布匹套裁问题。装箱问题属于NP难问题一、概述2023/5/26 11 0/1背包问题：给出几个体积为S1，S2，Sn的物体和容量为C的背包；要求找出n个物件的一个子集使其尽可能多地填满容量为C的背包。数学形式：最大化 满足 一、概述2023/5/26 12 广义背包问题：输入由背包容积C和两个向量：物品体积S(S1，S2，Sn)和物品价值P(P1，P2，Pn)组成。设X为一整数集合（物品的标识），X1，2，3，n，T为X的子集，则问题就是找出满足约束条件，并使总价值最大的子集T。数学形式：最大化 满足 一、概述2023/5/26 13 在应用问题中，设S的元素是n项经营活动各自所需的资源消耗，C是所能提供的资源总量，P的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。背包问题属于NP-难问题一、概述2023/5/26 14 多选择背包问题：有一个容积有限的背包。要放入背包的物品被分为不重叠的若干类，每类中有若干不同的物品，从每类中选择一个物品，使得物品总体积在满足背包容积约束的前提下最大化收益。属于NP难问题一、概述2023/5/26 15 i为类下标；j为类中物品的下标；ni是第i类中物品的数量；cij是第i类中第j个物品的收益；m是类的数量；wij为第i类中第j个项目的体积，W是背包的容积。最大化所选物品的总价值所选物品的总体积不得超过背包容积每一类中只能选一个物品一、概述2023/5/26 16 旅行商问题（Traveling Salesman Problem）寻找一条最短的遍历 n个城市的路径，或者说搜索整数子集 X1，2，n（X的元素表示对n个城市的编号）的一个排列(X)=v1，v2，vn，使下式取最小值。式中的d(vi,vi+1)表示城市vi到城市vi+1的距离。对称旅行商问题是NP难问题一、概述2023/5/26 17 影片递送问题（Film Delivery Problem）一盘影片拷贝要在n个电影院放映。每个电影院放映的次数已定，记为一个非负的整数di(i1，2，n)。两个影院间的距离记为wij，若影院i和j不能直接相连，则令wij+。问题是要为影片递送员找一个巡回，从主影院1开始，将影片拷贝送到第i家影院di(i1，2，n)次，最后回到主影院1，并极小化总的路线长度。当所有的di(il，2，n)为1时，FDP变为经典的TSP。FDP是TSP的新扩展，它可以推广到一大类路径与排序问题中。一、概述2023/5/26 18 图的二划分问题：对于一无向图G，设其顶点集合为V，将顶点集合V划分为两个子集V1和V2，Vl V2，求使V1和V2两顶点子集之间联结最少的一种划分。图的划分问题在电子线路设计中非常重要。例如，在多层印刷电路板的布局设计中，使层间联线数目最少的器件布局等。由于图的划分问题的计算复杂度极高(3000个节点的二划分问题的搜索空间可达10900)，因此，在实用规模上精确求出最优解是不可能的。一、概述2023/5/26 19 广义地讲，调度问题考虑的是随着时间的变化，如何调度有限的资源在执行任务的同时满足特定约束。资源：人力、金钱、机器、工具、材料、能源、等等。任务：制造系统的加工工序；计算机系统的信息处理。任务的表征：完成时间、预期时间、相对紧急权重、处理时间和资源消耗。一、概述2023/5/26 20 经典作业车间调度问题（Job-shop Scheduling）：有m台不同的机器和n个不同的工件，每个工件包含一个由多道工序组成的工序集合，工件的工序顺序是预先给定的。每道工序用它所要求的机器和固定的加工时间来表示。此外对工件和机器有一些约束，例如：(1)一个工件不能两次访问同一机器；(2)不同工件的工序之间没有先后约束；(3)工序一旦进行不能中断；(4)每台机器一次只能加工一个工件；(5)下达时间和交货期都不是给定的。问题：确定机器上工序的顺序，以最小化完成所有工件所需的最小加工持续时间。一、概述2023/5/26 21 局部搜索算法是基于贪婪思想利用邻域函数进行搜索的，容易实现，但其搜索性能完全依赖于邻域函数和初始解的选取，领域函数设计不当或初始解选择不合适，算法的最终性能将会很差；同时贪婪思想也导致其最终解只具有局部最优性；此外，局部搜索算法的时间复杂性取决于问题的性质与邻域结构的复杂程度。鉴于局部搜索算法的上述缺点，许多学者提出了各种各样的方法来改善算法的性能。模拟退火算法和演化算法从不同的角度，利用不同的搜索机制和实现策略实现了对局部搜索算法的改进，具有了全局最优的性能，成为两种较为成功的全局优化算法。一、概述2.组合优化问题的局部搜索算法2023/5/26 22 算法的提出 模拟退火算法(Simulated Annealing,简称SA)的思想最早是由Metropolis等(1953)提出的，1983年Kirkpatrick等将其用于组合优化。SA算法是基于Monte Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。算法的目的 解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。二、模拟退火算法2023/5/26 23 模拟退火算法在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优解。模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。二、模拟退火算法2023/5/26 24局部优解全局最优解概率突跳特性l 什么是退火：退火是指将固体加热到足够高的温度（不能加热到熔解温度，得保持形状和尺寸），使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。l 退火目的：使金属的显微结构更加规则化，并消除前道工序所产生的内应力。l 简单而言，物理退火过程由以下三部分组成：1.物理退火过程和Metropolis准则二、模拟退火算法2023/5/26 25 退火过程 加温过程：其目的是增强粒子的热运动，使其偏离平衡位置。当温度足够高时，固体将熔解为液体，从而消除系统原先可能存在的非均匀态，使随后进行的冷却过程以某一平衡态为起点。熔解过程与系统的熵增过程联系，系统能量也随温度的升高而增大。等温过程：物理学的知识告诉我们，对于与周围环境交换热量而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态。冷却过程：目的是使粒子的热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。二、模拟退火算法2023/5/26 26Metropolis等在1953年提出了重要性采样法，即以概率接受新状态。具体而言：首先，在温度T，给定固体初始状态i 作为当前状态，由当前状态i随机产生新状态j，两者的能量分别为Ei和Ej。然后判断：若Ej Ei，则接受新状态j为当前“重要”状态，否则，若Ej Ei，则该状态是否“重要”要依据固体处于该状态的概率进行判断，其方法如下：二、模拟退火算法2023/5/26 27Metropolis准则 计算r=P(Ej)/P(Ei)=exp(Ei-Ej)/kT，显然r1，其中P(E)为系统处于能量E的概率、T为系统绝对温度、k为Boltzmann常数。产生一个0,1区间的随机数，若r，则新状态作为重要状态，否则舍去。若新状态为重要状态，则以新状态为当前状态（否则仍以原状态i为当前状态）。重复以上新状态产生过程。二、模拟退火算法2023/5/26 28 在大量固体状态的变换（也称迁移）后，固体趋于能量较低的平衡状态，固体状态的概率分布趋于Gibbs正则分布：P(E)exp(-E/kT)上述以一定的概率接受新状态的准则称为Metropolis准则，相应算法称为Metropolis算法。l 由r=exp(Ei-Ej)/kT可知，高温下可接受与当前状态能差较大的新状态为重要状态，而在低温下只能接受与当前状态能差较小的新状态为重要状态，这与不同温度下热运动的影响完全一致。在温度趋于0时，不能接受任一Ej Ei的新状态。二、模拟退火算法2023/5/26 29l Metropolis准则：利用重要性采样过程，p 在高温下可接受与当前状态能量差较大的新状态；p 在低温下基本只接受与当前状态能量差较小的新状态；p 当温度趋于零时，就不能接受比当前状态能量高的新状态。二、模拟退火算法2023/5/26 30 1983年Kirkpatrick等意识到组合优化与物理退火的相似性，并受到Metropolis准则的启迪，提出了模拟退火算法。l 模拟退火算法是基于Monte Carlo 迭代求解策略的一种随机寻优算法。l 其出发点是基于物理退火过程与组合优化之间的相似性，SA由某一较高初温开始，利用具有概率突跳特性的Metropolis抽样策略在解空间中进行随机搜索，伴随温度的不断下降重复抽样过程，最终得到问题的全局最优解。2.模拟退火算法的基本思想和步骤二、模拟退火算法2023/5/26 31基本思想标准模拟退火算法的一般步骤可描述如下：给定初温，随机产生初始状态，令；重复过程:Repeat 产生新状态；二、模拟退火算法2023/5/26 32算法步骤（标准）Until 抽样稳定准则满足；退温，并令；Until 算法终止准则满足；输出算法搜索结果。二、模拟退火算法2023/5/26 33 二、模拟退火算法2023/5/26 34算法步骤（组合优化问题）模拟退火算法关键参数和操作的设定 从算法流程上看，模拟退火算法包括:三函数两准则，即状态产生函数、状态接受函数、温度更新函数、内循环终止准则和外循环终止准则，这些环节的设计将决定SA算法的优化性能。此外，初温的选择对SA算法性能也有很大影响。二、模拟退火算法2023/5/26 35状态产生函数 设计状态产生函数（邻域函数）的出发点应该是尽可能保证产生的候选解遍布全部的解空间。通常，状态产生函数由两部分组成，即产生候选解的方式和候选解产生的概率分布。二、模拟退火算法2023/5/26 36状态接受函数 状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于接受概率的形式不同。设计状态接受概率，应该遵循以下原则：在固定温度下，接受使目标函数值下降的候选解的概率要大于使目标值上升的候选解的概率；二、模拟退火算法2023/5/26 37随温度的下降，接受使目标函数值上升的解的概率要逐渐减小；当温度趋于零时，只能接受目标函数值下降的解。l 状态接受函数的引入是SA算法实现全局搜索的最关键的因素，SA算法中通常采用min1,exp(-C/t)作为状态接受函数。二、模拟退火算法2023/5/26 38初温 初始温度、温度更新函数、内循环终止准则和外循环终止准则通常被称为退火历程(annealing schedule)。l 实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：二、模拟退火算法2023/5/26 39均匀抽样一组状态，以各状态目标值的方差为初温；随机产生一组状态，确定两两状态间的最大目标值差，然后依据差值，利用一定的函数确定初温。譬如，其中 为初始接受概率；利用经验公式给出。二、模拟退火算法2023/5/26 40温度更新函数l 温度更新函数，即温度的下降方式，用于在外循环中修改温度值。l 目前，最常用的温度更新函数为指数退温函数，即其大小可以不断变化。二、模拟退火算法2023/5/26 41内循环终止准则 内循环终止准则，或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。l 在非时齐SA算法理论中，由于在每个温度下只产生一个或少量候选解，所以不存在选择内循环终止准则的问题。二、模拟退火算法2023/5/26 42 而在时齐SA算法理论中，收敛条件要求在每个温度下产生候选解的数目趋于无穷大，以使相应的马氏链（Markov链）达到平稳概率分布，显然在实际应用算法时这是无法实现的。常用的抽样准则包括：检验目标函数的均值是否稳定；连续若干步的目标值变化较小；按一定的步数抽样。二、模拟退火算法2023/5/26 43外循环终止准则 外循环终止准则，即算法终止准则，用于决定算法何时结束。设置温度终值是一种简单的方法。SA算法的收敛性理论中要求温度终值趋于零，这显然不合实际。通常的做法是：二、模拟退火算法2023/5/26 44设置终止温度的阈值；设置外循环迭代次数；算法收敛到的最优值连续若干步保持不变；检验系统熵是否稳定。三、演化算法原理2023/5/26 45 演化算法是基于生物进化思想而发展起来的一种问题求解方法。采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优生劣汰的自然选择来指导学习和确定搜索的方向。与传统搜索算法相比具有以下的特点：演化算法从一个群体开始搜索，可以同时搜索解空间内的多个区域，效率高，具有本质的并行性，能够以较大的概率找到全局最优解；1.引言三、演化算法原理2023/5/26 46 演化算法解的变换使用随机转移规则，只使用解的适应性信息（即适应函数或目标函数），不受目标函数连续、可谓微条件的限制；演化算法采用适者生存、不适者淘汰的自然选择策略，利用个体的适应值推动群体的演化，算法设计过程中无需事先描述问题的全部特点及其结构特征。演化算法具有内在学习性，包括宗亲学习（phylogenetic learning）：祖先的良好特征通过遗传传递给后代；社团学习（sociogenetic learning）：独立群体内部知识或结构共享；个体学习（ontogenetic learning）：通过改变个体的基因结构来提高自己的适应度。三、演化算法原理2023/5/26 47 演化计算在机器学习、过程控制、经济预测、工程优化等领域去的巨大的成功，在故障诊断领域也得到了广泛的关注。三、演化算法原理2023/5/26 48 生物进化学说达尔文（1858年）包括以下3方面的内容：遗传（Heredity）：它是生物的普遍特征，子代按照从父代获取的遗传信息进行发育和分化，保证了子代和父代之间具有相同或相似的形状，使得物种得以稳定存在；变异（Mutation）：它是生命多样性的源泉，变异的发生使得子代的性状不同于父代性状；生存斗争和适者生存：自然选择来自繁衍过剩和生存斗争，自然选择的原则是“适者生存”，它决定了群体中只有对其生存环境具有较强适应性的那些个体才能够存活并繁殖。2.生物进化过程的一般特性三、演化算法原理2023/5/26 49 演化计算一般具有如下几大分支：遗传算法（Genetic Algorithm，GA）；演化策略（Evolution Strategy，ES）；演化规划（Evolutionary Programming，EP）；遗传程序设计（Genetic Programming，GP）：基于遗传算法发展起来的一个分支。l 这几个分支在算法实现方面具有一些细微的差别，但它们具有一个共同的特点，即都是借助生物演化的思想和原理来解决实际问题。3.演化计算的主要分支4.1 个体与种群 个体就是模拟生物个体而对问题中的对象一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集。三、演化算法原理4.遗传算法的基本概念2023/5/26 504.2 适应度与适应度函数 适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数(fitness function)就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数。三、演化算法原理2023/5/26 514.3.染色体与基因染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene）。例如：个体 染色体 9-1001（2，5，6）-010 101 110三、演化算法原理2023/5/26 524.4.遗传操作亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作:选择-复制(selection-reproduction)交叉(crossover，亦称交换、交配或杂交)变异(mutation，亦称突变)三、演化算法原理2023/5/26 53选择-复制通常做法是：对于一个规模为N的种群S,按每个染色体xiS的选择概率P(xi)所决定的选中机会,分N次从S中随机选定N个染色体,并进行复制。这里的选择概率P(xi)的计算公式为三、演化算法原理2023/5/26 54交叉 就是互换两个染色体某些位上的基因。s1=01000101,s2=10011011，可以看做是原染色体s1和s2的子代染色体。例如,设染色体 s1=01001011,s2=10010101,交换其后4位基因,即三、演化算法原理2023/5/26 55 变异 就是改变染色体某个(些)位上的基因。例如,设染色体 s=11001101，将其第三位上的0变为1,即 s=11001101 11101101=s。s也可以看做是原染色体s的子代染色体。三、演化算法原理2023/5/26 565 基本遗传算法 遗传算法基本流程框图生成初始种群计算适应度选择-复制交叉变异生成新一代种群终止?结束三、演化算法原理2023/5/26 57 1975年J.Holland在研究自然和人工系统自适应行为的过程中提出了遗传算法，他提出的遗传算法常被称为简单遗传算法（简记SGA），SGA的操作对象是一群二进制串（称 为 染 色 体、个 体），即 种 群（population），每个染色体都对应于问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，适应杂交（crossover）和变异来产生下一代种群，如此一代代演化下去，指导满足期望的终止条件。5.1 算法中的一些控制参数：种群规模 最大代数 交叉率(crossover rate)就是参加交叉运算的染色体个数占全体染色体总数的比例，记为Pc,取值范围一般为0.40.99。变异率(mutation rate)是指发生变异的基因位数所占全体染色体的基因总位数的比例，记为Pm，取值范围一般为0.00010.1。三、演化算法原理2023/5/26 585.2 基本遗传算法 步1 在 搜 索 空 间U 上 定 义 一 个 适 应 度 函 数f(x)，给定种群规模N、交叉率Pc和变异率Pm、代数T；步2 随机产生U中的N个个体s1,s2,sN，组成初始种群S=s1,s2,sN，置代数计数器t=1；步3 计算S中每个个体的适应度f()；步4 若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。三、演化算法原理2023/5/26 59 步5 按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1；步6 按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2；三、演化算法原理2023/5/26 60 步7 按变异率Pm所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3；步8 将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；6 遗传算法应用举例 例4.1 利用遗传算法求解区间0,31上的二次函数y=x2的最大值。y=x2 31 XY三、演化算法原理2023/5/26 61 分析 原问题可转化为在区间0,31中搜索能使y取最大值的点a的问题。那么，0,31 中的点x就是个体,函数值f(x)恰好就可以作为x的适应度，区间0,31就是一个(解)空间。这样,只要能给出个体x的适当染色体编码,该问题就可以用遗传算法来解决。三、演化算法原理2023/5/26 62解(1)设定种群规模，编码染色体，产生初始种群。将种群规模设定为4；用5位二进制数编码染色体；取下列个体组成初始种群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)(2)定义适应度函数,取适应度函数：f(x)=x2 三、演化算法原理2023/5/26 63(3)计算各代种群中的各个体的适应度,并对其染色体 进 行 遗 传 操 作,直 到 适 应 度 最 高 的 个 体(即31（11111）)出现为止。三、演化算法原理2023/5/26 64 首先计算种群S1中各个体 s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)的适应度f(si)。容易求得 f(s1)=f(13)=132=169 f(s2)=f(24)=242=576 f(s3)=f(8)=82=64 f(s4)=f(19)=192=361再计算种群S1中各个体的选择概率。选择概率的计算公式为 由此可求得 P(s1)=P(13)=0.14 P(s2)=P(24)=0.49 P(s3)=P(8)=0.06 P(s4)=P(19)=0.31三、演化算法原理2023/5/26 65 赌轮选择示意s40.31s20.49s10.14s30.06 赌轮选择法三、演化算法原理2023/5/26 66在算法中赌轮选择法可用下面的子过程来模拟:在0,1区间内产生一个均匀分布的随机数r。若rq1，则染色体x1被选中。若qk-1rqk(2kN),则染色体xk被选中。其中的qi称为染色体xi(i=1,2,n)的积累概率，其计算公式为 三、演化算法原理2023/5/26 67选择-复制 设从区间0,1中产生4个随机数如下:r1=0.450126,r2=0.110347 r3=0.572496,r4=0.98503 染色体 适应度选择概率 积累概率 选中次数s1=01101 169 0.14 0.14 1s2=11000 576 0.49 0.63 2s3=01000 64 0.06 0.69 0s4=10011 361 0.31 1.00 1三、演化算法原理2023/5/26 68于是，经复制得群体：s1=11000（24）,s2=01101（13）s3=11000（24）,s4=10011（19）三、演化算法原理2023/5/26 69交叉 设 交 叉 率pc=100%，即S1中 的 全 体 染 色 体 都 参 加 交 叉运算。设s1 与s2 配 对，s3 与s4 配 对。分 别 交 换 后 两 位 基 因，得新染色体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）三、演化算法原理2023/5/26 70变异 设变异率pm=0.001。这样，群体S1中共有 540.001=0.02位基因可以变异。0.02位显然不足1位，所以本轮遗传操作不做变异。三、演化算法原理2023/5/26 71 于是，得到第二代种群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）三、演化算法原理2023/5/26 72 第二代种群S2中各染色体的情况 染色体 适应度选择概率 积累概率 估计的选中次数s1=11001 625 0.36 0.36 1s2=01100 144 0.08 0.44 0s3=11011 729 0.41 0.85 2s4=10000 256 0.15 1.00 1三、演化算法原理2023/5/26 73 假设这一轮选择-复制操作中，种群S2中的4个染色体都被选中，则得到群体：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）做交叉运算，让s1与s2，s3与s4 分别交换后三位基因，得 s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）这一轮仍然不会发生变异。三、演化算法原理2023/5/26 74于是，得第三代种群S3：s1=11100（28）,s2=01001（9）s3=11000（24）,s4=10011（19）2023/5/26 75 第三代种群S3中各染色体的情况 染色体 适应度选择概率 积累概率 估计的选中次数s1=11100 784 0.44 0.44 2s2=01001 81 0.04 0.48 0s3=11000 576 0.32 0.80 1s4=10011 361 0.20 1.00 1三、演化算法原理2023/5/26 76 设这一轮的选择-复制结果为：s1=11100（28）,s2=11100（28）s3=11000（24）,s4=10011（19）做交叉运算，让s1与s4，s2与s3 分别交换后两位基因，得 s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）这一轮仍然不会发生变异。三、演化算法原理2023/5/26 77 于是，得第四代种群S4：s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）三、演化算法原理2023/5/26 78 显然，在这一代种群中已经出现了适应度最高的染色体s1=11111。于 是，遗 传 操 作 终 止，将染色体“11111”作为最终结果输出。然后，将染色体“11111”解码为表现型，即得所求的最优解：31。将31代入函数y=x2中，即得原问题的解，即函数y=x2的最大值为961。三、演化算法原理2023/5/26 79YYy=x2 8 13 19 24 X第一代种群及其适应度y=x2 12 16 25 27 XY第二代种群及其适应度y=x2 9 19 24 28 XY第三代种群及其适应度y=x2 16 24 28 31 X第四代种群及其适应度2023/5/26 80 例 4.2 用遗传算法求解TSP。分析 由于其任一可能解 一个合法的城市序列，即n个城市的一个排列，都可以事先构造出来。于是，我们就可以直接在解空间（所有合法的城市序列）中搜索最佳解。这正适合用遗传算法求解。三、演化算法原理（1）定义适应度函数 我们将一个合法的城市序列s=（c1,c2,cn,cn+1）(cn+1就是c1)作为一个个体。这个序列中相邻两城之间的距离之和的倒数就可作为相应个体s的适应度，从而适应度函数就是 三、演化算法原理2023/5/26 82（2）对个体s=（c1,c2,cn,cn+1）进行编码。但对于这样的个体如何编码却不是一件直截了当的事情。因为如果编码不当，就会在实施交叉或变异操作时出现非法城市序列即无效解。例如，对于5个城市的TSP，我们用符号A、B、C、D、E代表相应的城市，用这5个符号的序列表示可能解即染色体。三、演化算法原理2023/5/26 83然后进行遗传操作。设 s1=（A,C,B,E,D,A），s2=（A,E,D,C,B,A）实施常规的交叉或变异操作，如交换后三位，得 s1=（A,C,B,C,B,A），s2=（A,E,D,E,D,A）或者将染色体s1第二位的C变为E，得 s1=（A,E,B,E,D,A）可以看出，上面得到的s1，s2和s1都是非法的城市序列。三、演化算法原理2023/5/26 84 为此，对TSP必须设计合适的染色体和相应的遗传运算。事实上，人们针对TSP提出了许多编码方法和相应的特殊化了的交叉、变异操作，如顺序编码或整数编码、随机键编码、部分映射交叉、顺序交叉、循环交叉、位置交叉、反转变异、移位变异、互换变异等等。从而巧妙地用遗传算法解决了TSP。三、演化算法原理2023/5/26 857 遗传算法的特点与优势 7.1遗传算法的主要特点 遗传算法一般是直接在解空间搜索,而不像图搜索那样一般是在问题空间搜索,最后才找到解。遗传算法的搜索随机地始于搜索空间的一个点集,而不像图搜索那样固定地始于搜索空间的初始节点或终止节点,所以遗传算法是一种随机搜索算法。三、演化算法原理2023/5/26 86 遗传算法总是在寻找优解,而不像图搜索那样并非总是要求优解,而一般是设法尽快找到解,所以遗传算法又是一种优化搜索算法。遗传算法的搜索过程是从空间的一个点集(种群)到另一个点集(种群)的搜索，而不像图搜索那样一般是从空间的一个点到另一个点地搜索。因而它实际是一种并行搜索,适合大规模并行计算，而且这种种群到种群的搜索有能力跳出局部最优解。三、演化算法原理2023/5/26 87遗传算法的适应性强,除需知适应度函数外,几乎不需要其他的先验知识。遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束，不要求连续性,能以很大的概率从离散的、多极值的、含有噪声的高维问题中找到全局最优解。2023/5/26 88三、演化算法原理7.2 遗传算法的应用 遗传算法在人工智能的众多领域便得到了广泛应用。例如，机器学习、聚类、控制（如煤气管道控制）、规划（如生产任务规划）、设计（如通信网络设计、布局设计）、调度（如作业车间调度、机器调度、运输问题）、配置（机器配置、分配问题）、组合优化（如TSP、背包问题）、函数的最大值以及图像处理和信号处理等等。三、演化算法原理2023/5/26 89 另一方面，人们又将遗传算法与其他智能算法和技术相结合，使其问题求解能力得到进一步扩展和提高。例如，将遗传算法与模糊技术、神经网络相结合，已取得了不少成果。三、演化算法原理 对遗传算法的进一步研究将涉及到模式定理和隐性、并行性等内容。有兴趣的同学可参阅有关专著。2023/5/26 90