最新大连海事大学《现代优化技术》第9讲：现代启发式算法之遗传算法教学课件.ppt

《最新大连海事大学《现代优化技术》第9讲：现代启发式算法之遗传算法教学课件.ppt》由会员分享，可在线阅读，更多相关《最新大连海事大学《现代优化技术》第9讲：现代启发式算法之遗传算法教学课件.ppt（137页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、大连海事大学现代优化技大连海事大学现代优化技术第术第9 9讲：现代启发式算讲：现代启发式算法之遗传算法法之遗传算法在生物细胞中，控制并决定生物遗传特性的物质在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称是脱氧核糖核酸，简称DNA。染色体是其载体。染色体是其载体。DNA是由四种碱基按一定规则排列组成的长链。是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。四种碱基不同的排列决定了生物不同的表现性状。例如，改变例如，改变DNA长链中的特定一段（称为基因），长链中的特定一段（称为基因），即可改变人体的身高。即可改变人体的身高。细胞在分裂时，细胞在分裂时

2、，DNA通过复制而转移到新产生的通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。细胞中，新的细胞就继承了旧细胞的基因。生物学中的遗传概念现代启发式算法之遗传算法现代启发式算法之遗传算法 编码编码(code,representation)(code,representation)编码：在特定的数据结构下，编码：在特定的数据结构下，编码：在特定的数据结构下，编码：在特定的数据结构下，从可行解的状态空间到编码解的状态空间的一个映射。从可行解的状态空间到编码解的状态空间的一个映射。从可行解的状态空间到编码解的状态空间的一个映射。从可行解的状态空间到编码解的状态空间的一个映射。常规码：常规

3、码：常规码：常规码：0000，11111111：包括该项；：包括该项；：包括该项；：包括该项；0 0 0 0：不包括该项。如背包问题：不包括该项。如背包问题：不包括该项。如背包问题：不包括该项。如背包问题非常规码：非非常规码：非非常规码：非非常规码：非0000，1111向量的表示。如向量的表示。如向量的表示。如向量的表示。如TSPTSPTSPTSP问题的一个都市排列问题的一个都市排列问题的一个都市排列问题的一个都市排列针对问题针对问题针对问题针对问题设计编码设计编码设计编码设计编码编码与解码GA中中的的编编码码方方法法可可分分为为三三大大类类：二二进进制制编编码码方方法法、浮点数编码方法和符号

4、编码方法。浮点数编码方法和符号编码方法。二进制编码方案二进制编码方案是是GA中中最最常常用用的的一一种种编编码码方方法法。它它所所构构成成的个体基因型是一个二进制编码符号串。的个体基因型是一个二进制编码符号串。GA的的算算法法过过程程简简述述如如下下。首首先先在在解解空空间间中中取取一一群群点点，作作为为遗遗传传开开始始的的第第一一代代。每每个个点点（基基因因）用用一一个个二二进进制制数数字字串串表表示示，其其优优劣劣程程度度用用适适应应度度函函数（数（fitnessfunction）来衡量）来衡量。二进制编码符号串的长度与问题所要求的二进制编码符号串的长度与问题所要求的求解精度有关。设某一参

5、数的取值范围是求解精度有关。设某一参数的取值范围是B,A，B Tmin /降温过程1)for j=1k/等温过程1)对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量E=E(xnew)-E(xbest)。2)如果E 0，则xbest=xnew；3)如果E 0，则p=exp(-E/T(i);1)如果c=random0,1 p，xbest=xnew;否则 xbest=xbest。2)End for3)按照温度控制策略更新T；4)End Do5)输出当前最优点，计算结束。模拟退火算法（要素）1、状态空间与状态产生函数（邻域函数）搜索

6、空间也称为状态空间，它由经过编码的可行解的集合所组成。状态产生函数(邻域函数)应尽可能保证产生的候选解能遍布全部解空间。通常由两部分组成，即产生候选解的方式和候选解产生的概率分布。候选解一般按照某一概率分布对解空间进行随机采样来获得。概率分布可以是均匀分布、正态分布、指数分布等等。模拟退火算法（要素）2、状态转移概率（接受概率）p状态转移概率是指从一个状态xold(一个可行解)向另一个状态xnew(另一个可行解)的转移概率;通俗的理解是接受一个新解为当前解的概率;它与当前的温度参数T有关，随温度下降而减小。一般采用Metropolis准则模拟退火算法（要素）3、冷却进度表T(t)冷却进度表是指

7、从某一高温状态To向低温状态冷却时的降温管理表。假设时刻t的温度用T(t)来表示，则经典模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：这两种方式都能够使得模拟退火算法收敛于全局最小点。模拟退火算法（要素）4、初始温度T0实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：(1)均匀抽样一组状态，以各状态目标值的方差为初温。(2)随机产生一组状态，确定两两状态间的最大目标值差|max|，然后依据差值，利用一定的函数确定初温。比如，t0=max/pr，其中pr为初始接受概率。(3)利用经验公式给出。模拟退火算法

8、（要素）5、内循环终止准则或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括：(1)检验目标函数的均值是否稳定；(2)连续若干步的目标值变化较小；(3)按一定的步数抽样。模拟退火算法（要素）6、外循环终止准则即算法终止准则，常用的包括：(1)设置终止温度的阈值；(2)设置外循环迭代次数；(3)算法搜索到的最优值连续若干步保持不变；(4)检验系统熵是否稳定。模拟退火算法的改进(1)设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。(2)设计高效的退火策略。(3)避免状态的迂回搜索。(4)采用并行搜索结构。(5)为避免

9、陷入局部极小，改进对温度的控制方式(6)选择合适的初始状态。(7)设计合适的算法终止准则。模拟退火算法的改进也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：(1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。(2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将“Best So Far”的状态记忆下来。(3)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。(4)对每一当前状态

10、，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。算法实现与应用TSP问题的求解编码（城市编号顺序编码）状态产生函数（逆转算子）状态接受函数初温与初始状态，T0=max/pr 降温函数设计温度修改准则和算法终止准则运行过程运行过程运行过程运行过程 三、模拟退火算法的应用三、模拟退火算法的应用 3.1 303.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）运行过程运行过程运行过程运行

11、过程 三、模拟退火算法的应用三、模拟退火算法的应用 3.1 303.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）运行过程运行过程运行过程运行过程 三、模拟退火算法的应用三、模拟退火算法的应用 3.1 303.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）运行过程运行过程运行过程运行过程 三、模拟退火算法的应用三、模拟退火算法的应用 3.1 303.1 30城市城市城市城市TSPT

12、SP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）运行过程运行过程运行过程运行过程 三、模拟退火算法的应用三、模拟退火算法的应用 3.1 303.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）运行结果运行结果运行结果运行结果 三、模拟退火算法的应用三、模拟退火算法的应用 3.1 303.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by

13、 D B Fogel）1 随机过程的概念 随机过程随机过程被认为是概率论的“动力学”部分，即它的研究对象是随时间演变的随机现象，它是从多维随机变量向一族(无限多个)随机变量的推广。给定一随机试验 ，其样本空间 ，将样本空间 中的每一元作如下对应，便得到一系列结果：92随机过程的定义 例1：抛掷一枚硬币的试验，样本空间是 ，现定义：123494959697例5：考虑抛掷一颗骰子的试验：随机过程的分类：随机过程的分类：随机过程可根据参数集T和任一时刻的状态分为四类，参数集T可分为离散集和连续集两种情况，任一时刻的状态分别为离散型随机变量和连续型随机变量两种：1.连续参数连续型的随机过程，如例2，例

14、32.连续参数离散型的随机过程，如例1，例43.离散参数离散型的随机过程，如例54.离散参数连续型的随机过程，如下例99马尔科夫马尔科夫Markov链链Markov原名原名A.A.Markov（俄，（俄，18561922）于于1906年开始研究此类问题年开始研究此类问题.1 马马尔尔可夫可夫链链的定的定义义引例引例假定某大学有假定某大学有假定某大学有假定某大学有1 1 1 1万学生，每人每月用万学生，每人每月用万学生，每人每月用万学生，每人每月用1 1 1 1支牙膏，并且只使用支牙膏，并且只使用支牙膏，并且只使用支牙膏，并且只使用“中华中华中华中华”牙膏与牙膏与牙膏与牙膏与“黑妹黑妹黑妹黑妹”

15、牙膏两者之一。根据本月（牙膏两者之一。根据本月（牙膏两者之一。根据本月（牙膏两者之一。根据本月（12121212月）调查，有月）调查，有月）调查，有月）调查，有3000300030003000人使用黑妹牙膏，人使用黑妹牙膏，人使用黑妹牙膏，人使用黑妹牙膏，7000700070007000人使用人使用人使用人使用中华牙膏。又据调查中华牙膏。又据调查中华牙膏。又据调查中华牙膏。又据调查,使用黑妹牙膏的使用黑妹牙膏的使用黑妹牙膏的使用黑妹牙膏的3000300030003000人中，有人中，有人中，有人中，有60606060的人下月将继续使用黑的人下月将继续使用黑的人下月将继续使用黑的人下月将继续使用

16、黑妹牙膏，妹牙膏，妹牙膏，妹牙膏，40404040的人将改用中华牙膏；的人将改用中华牙膏；的人将改用中华牙膏；的人将改用中华牙膏；使用中华牙膏的使用中华牙膏的使用中华牙膏的使用中华牙膏的7000700070007000人中，人中，人中，人中，有有有有70707070的人下月将继续使用中华牙膏，的人下月将继续使用中华牙膏，的人下月将继续使用中华牙膏，的人下月将继续使用中华牙膏，30303030的人将改用黑妹牙膏。据此，可以得到的人将改用黑妹牙膏。据此，可以得到的人将改用黑妹牙膏。据此，可以得到的人将改用黑妹牙膏。据此，可以得到如表所示的统计表如表所示的统计表如表所示的统计表如表所示的统计表 拟拟

17、用用黑妹牙膏黑妹牙膏中中华华牙膏牙膏现现用用黑妹牙膏黑妹牙膏6040中中华华牙膏牙膏3070基本概念基本概念状态和状态转移状态和状态转移n n状态是指客观事物可能出现或存在的状况。状态是指客观事物可能出现或存在的状况。状态是指客观事物可能出现或存在的状况。状态是指客观事物可能出现或存在的状况。如企业的产品在市场上可能畅销，也可能滞销。如企业的产品在市场上可能畅销，也可能滞销。如企业的产品在市场上可能畅销，也可能滞销。如企业的产品在市场上可能畅销，也可能滞销。n n状态转移是指客观事物由一种状态到另一种状态的变化。状态转移是指客观事物由一种状态到另一种状态的变化。状态转移是指客观事物由一种状态到

18、另一种状态的变化。状态转移是指客观事物由一种状态到另一种状态的变化。客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往往条件变化，状态也会发生变化。如某种产品在市场上本来是滞销的，但是由于销售往条件变化，状态也会发生变化。如某种产品在市场上本来是滞销的，但是由于销售往条件变化，状态也会发生变化。如某种产品在市场上本来是滞销的，但是由于销售往条件变化，状态也会发

19、生变化。如某种产品在市场上本来是滞销的，但是由于销售渠道变化了，或者消费心理发生了变化等，它便可能变为畅销产品。渠道变化了，或者消费心理发生了变化等，它便可能变为畅销产品。渠道变化了，或者消费心理发生了变化等，它便可能变为畅销产品。渠道变化了，或者消费心理发生了变化等，它便可能变为畅销产品。转移概率与转移概率矩阵转移概率与转移概率矩阵假定某大学有假定某大学有假定某大学有假定某大学有1 1 1 1万学生，每人每月用万学生，每人每月用万学生，每人每月用万学生，每人每月用1 1 1 1支牙膏，并且只使用支牙膏，并且只使用支牙膏，并且只使用支牙膏，并且只使用“中华中华中华中华”牙膏与牙膏与牙膏与牙膏与

20、“黑妹黑妹黑妹黑妹”牙膏两者之一。根据本月（牙膏两者之一。根据本月（牙膏两者之一。根据本月（牙膏两者之一。根据本月（12121212月）调查，有月）调查，有月）调查，有月）调查，有3000300030003000人使用黑妹牙膏，人使用黑妹牙膏，人使用黑妹牙膏，人使用黑妹牙膏，7000700070007000人使用人使用人使用人使用中华牙膏。又据调查中华牙膏。又据调查中华牙膏。又据调查中华牙膏。又据调查,使用黑妹牙膏的使用黑妹牙膏的使用黑妹牙膏的使用黑妹牙膏的3000300030003000人中，有人中，有人中，有人中，有60606060的人下月将继续使用黑的人下月将继续使用黑的人下月将继续使用

21、黑的人下月将继续使用黑妹牙膏，妹牙膏，妹牙膏，妹牙膏，40404040的人将改用中华牙膏；的人将改用中华牙膏；的人将改用中华牙膏；的人将改用中华牙膏；使用中华牙膏的使用中华牙膏的使用中华牙膏的使用中华牙膏的7000700070007000人中，人中，人中，人中，有有有有70707070的人下月将继续使用中华牙膏，的人下月将继续使用中华牙膏，的人下月将继续使用中华牙膏，的人下月将继续使用中华牙膏，30303030的人将改用黑妹牙膏。据此，可以得到的人将改用黑妹牙膏。据此，可以得到的人将改用黑妹牙膏。据此，可以得到的人将改用黑妹牙膏。据此，可以得到如表所示的统计表如表所示的统计表如表所示的统计表如

22、表所示的统计表 拟拟用用黑妹牙膏黑妹牙膏中中华华牙膏牙膏现现用用黑妹牙膏黑妹牙膏6040中中华华牙膏牙膏3070上表中的上表中的上表中的上表中的4 4 4 4个概率就称为个概率就称为个概率就称为个概率就称为状态的转移概率状态的转移概率状态的转移概率状态的转移概率，而这四个，而这四个，而这四个，而这四个转移概率组成的矩阵转移概率组成的矩阵转移概率组成的矩阵转移概率组成的矩阵B B B B 称为称为称为称为转移概率矩阵。转移概率矩阵。转移概率矩阵。转移概率矩阵。可以看出，可以看出，可以看出，可以看出，转移概率矩阵转移概率矩阵转移概率矩阵转移概率矩阵的一个特点是其各行元素之和为的一个特点是其各行元素

23、之和为的一个特点是其各行元素之和为的一个特点是其各行元素之和为 2 转转移概率矩移概率矩阵阵及柯及柯尔尔莫哥洛夫定理莫哥洛夫定理 （1 1 1 1）转移概率矩阵中的元素是根据近期市场）转移概率矩阵中的元素是根据近期市场）转移概率矩阵中的元素是根据近期市场）转移概率矩阵中的元素是根据近期市场 或顾客的保留与得失流向资料确定的。或顾客的保留与得失流向资料确定的。或顾客的保留与得失流向资料确定的。或顾客的保留与得失流向资料确定的。（2 2 2 2）下一期的概率只与上一期的预测结果有）下一期的概率只与上一期的预测结果有）下一期的概率只与上一期的预测结果有）下一期的概率只与上一期的预测结果有 关，不取决

24、于更早期的概率。关，不取决于更早期的概率。关，不取决于更早期的概率。关，不取决于更早期的概率。（3 3 3 3）利用转移概率矩阵进行决策，其最后结）利用转移概率矩阵进行决策，其最后结）利用转移概率矩阵进行决策，其最后结）利用转移概率矩阵进行决策，其最后结 果取决于转移矩阵的组成，不取决于原果取决于转移矩阵的组成，不取决于原果取决于转移矩阵的组成，不取决于原果取决于转移矩阵的组成，不取决于原 始条件，即最初占有率。始条件，即最初占有率。始条件，即最初占有率。始条件，即最初占有率。用马尔科夫链方法进行决策的特点：用马尔科夫链方法进行决策的特点：用马尔科夫链方法进行决策的特点：用马尔科夫链方法进行决

25、策的特点：主要用于企业产品的市场占有率预测主要用于企业产品的市场占有率预测主要用于企业产品的市场占有率预测主要用于企业产品的市场占有率预测转移概率矩阵决策的应用步骤转移概率矩阵决策的应用步骤转移概率矩阵决策的应用步骤转移概率矩阵决策的应用步骤 1 1 1 1）建立转移概率矩阵。）建立转移概率矩阵。）建立转移概率矩阵。）建立转移概率矩阵。2 2 2 2）利用转移概率矩阵进行模拟预测。）利用转移概率矩阵进行模拟预测。）利用转移概率矩阵进行模拟预测。）利用转移概率矩阵进行模拟预测。3 3 3 3）求出转移概率矩阵的平衡状态，即稳定状态。）求出转移概率矩阵的平衡状态，即稳定状态。）求出转移概率矩阵的平

26、衡状态，即稳定状态。）求出转移概率矩阵的平衡状态，即稳定状态。4 4 4 4）应用转移概率矩阵进行决策。）应用转移概率矩阵进行决策。）应用转移概率矩阵进行决策。）应用转移概率矩阵进行决策。例例1某计算机机房的一台计算机经常出故障，研究者每隔某计算机机房的一台计算机经常出故障，研究者每隔15min观察一次计观察一次计算机的运行状态，收集了算机的运行状态，收集了24h的数据（共作的数据（共作97次观察）。用次观察）。用1表示正常状态，表示正常状态，用用0表示不正常状态，所得的数据序列如下：表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111

27、1100011011011110110110101111011101111011111100110111111001111 1）建立转移概率矩阵）建立转移概率矩阵）建立转移概率矩阵）建立转移概率矩阵MatlabMatlab程序见程序见程序见程序见ex2.mex2.m黑妹黑妹中华中华30007000本月市场占有情况转移概率矩阵下月市场占有情况2 2）利用转移概率矩阵进行模拟预测）利用转移概率矩阵进行模拟预测）利用转移概率矩阵进行模拟预测）利用转移概率矩阵进行模拟预测3 3）求出转移概率矩阵的平衡状态，即稳定状态。）求出转移概率矩阵的平衡状态，即稳定状态。）求出转移概率矩阵的平衡状态，即稳定状态。

28、）求出转移概率矩阵的平衡状态，即稳定状态。3 转转移概率的移概率的渐渐近性近性质质极限概率分布极限概率分布解空间的搜索解空间的搜索解解离散随机状态离散随机状态随机状态的跳随机状态的跳转转满意解满意解最终状态最终状态SA接受准则接受准则/GA算子算子状态转移概率状态转移概率矩阵矩阵目标函数的导向性目标函数的导向性稳态概率最大似然稳态概率最大似然值对应状态值对应状态成绩构成三次大作业三次大作业50%，期末考试（闭卷），期末考试（闭卷）50%作业要求：尽量避免手写，应包含三部分内容作业要求：尽量避免手写，应包含三部分内容（1）程序简要说明）程序简要说明（2）程序代码）程序代码（3）算例实验）算例实验

29、考试内容l重重“意意”不重不重“形形”考试内容重在对算法原理以及技术考试内容重在对算法原理以及技术细节的理解，没有直接的数值计算。细节的理解，没有直接的数值计算。l不考传统精确解技术，以现代优化方法为主。不考传统精确解技术，以现代优化方法为主。l四大内容：传统优化技术与现代优化技术的区别与联系、时四大内容：传统优化技术与现代优化技术的区别与联系、时间复杂度理论、传统启发式方法、现代智能算法（间复杂度理论、传统启发式方法、现代智能算法（GA和和SA）考试题型选择（选择（20）、判断（）、判断（20）、简答（）、简答（60）简答内容：简答内容：（1）对于概念，技术细节的描述，原理的阐述）对于概念，

30、技术细节的描述，原理的阐述（2）编码设计）编码设计（3）编写算法伪代码）编写算法伪代码（4）算法的时间复杂度计算算法的时间复杂度计算（5）收敛性简要分析收敛性简要分析下次课（1）数学模型，算法设计以及程序设计的关系（难点：约束条件的算法）数学模型，算法设计以及程序设计的关系（难点：约束条件的算法处理，模式定理与积木块假设，算法迭代中不可行解的处理办法）处理，模式定理与积木块假设，算法迭代中不可行解的处理办法）（2）算法程序实现的实例详解（适应度函数编写的难点：复杂模型的程）算法程序实现的实例详解（适应度函数编写的难点：复杂模型的程序推进核心：时间残值矩阵）序推进核心：时间残值矩阵）Q&AQ&A结束语结束语谢谢大家聆听！谢谢大家聆听！137