大连海事大学《现代优化技术》第9讲：现代启发式算法之遗传算法

现代优化技术,第9讲：现代启发式算法之遗传算法,在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称DNA。染色体是其载体。DNA是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如，改变DNA长链中的特定一段（称为基因），即可改变人体的身高。细胞在分裂时，DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因。,生物学中的遗传概念,有性生殖生物在繁殖下一代时，两个同元染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉形成两个新的染色体。在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生新的染色体。这些新的染色体将决定新的个体（后代）的新的性状。,生物学中的遗传概念,在一个群体中，并不是所有的个体都能得到相同的繁殖机会，对生存环境适应度高的个体将获得更多的繁殖机会；对生存环境适应度较低的个体，其繁殖机会相对较少，即所谓自然选择。而生存下来的个体组成的群体，其品质不断得以改良，称为进化。,遗传算法的基本思想和基本概念,基本思想遗传算法GA把问题的解表示成“染色体”，在算法中即是以一定方式编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。,现代启发式算法之遗传算法,GeneticAlgorithm(遗传算法),模仿生物遗传进化过程同时产生复数的可行解（即，解集团population）新的解集团的生成来自于两种基本操作：交叉(crossover)变异(mutation),现代启发式算法之遗传算法,遗传算法与生物遗传的对应关系,现代启发式算法之遗传算法,GeneticAlgorithm（粗略）,选择(X)=在集団X中，通过自然淘汰，仅将优秀的子孙集団作为下一代生成(X)=在集団X中，通过交叉或変異，生成新的集団,P(0):=初始解集团fort=0toTdoP(t+1):=选择(Y)Y:=生成(P(t)end,现代启发式算法之遗传算法,编码(code,representation),编码：在特定的数据结构下，从可行解的状态空间到编码解的状态空间的一个映射。,常规码：0，11：包括该项；0：不包括该项。如背包问题,非常规码：非0，1向量的表示。如TSP问题的一个都市排列,针对问题设计编码,编码与解码,GA中的编码方法可分为三大类：二进制编码方法、浮点数编码方法和符号编码方法。二进制编码方案是GA中最常用的一种编码方法。它所构成的个体基因型是一个二进制编码符号串。GA的算法过程简述如下。首先在解空间中取一群点，作为遗传开始的第一代。每个点（基因）用一个二进制数字串表示，其优劣程度用适应度函数（fitnessfunction）来衡量。,二进制编码符号串的长度与问题所要求的求解精度有关。设某一参数的取值范围是B,A，BTmin/降温过程forj=1k/等温过程对当前最优解xbest按照某一邻域函数，产生一新的解xnew。计算新的目标函数值E(xnew)，并计算目标函数值的增量E=E(xnew)-E(xbest)。如果E0，则xbest=xnew；如果E0，则p=exp(-E/T(i);如果c=random0,1p，xbest=xnew;否则xbest=xbest。Endfor按照温度控制策略更新T；EndDo输出当前最优点，计算结束。,模拟退火算法（要素）,1、状态空间与状态产生函数（邻域函数）搜索空间也称为状态空间，它由经过编码的可行解的集合所组成。状态产生函数(邻域函数)应尽可能保证产生的候选解能遍布全部解空间。通常由两部分组成，即产生候选解的方式和候选解产生的概率分布。候选解一般按照某一概率分布对解空间进行随机采样来获得。概率分布可以是均匀分布、正态分布、指数分布等等。,模拟退火算法（要素）,2、状态转移概率（接受概率）p状态转移概率是指从一个状态xold(一个可行解)向另一个状态xnew(另一个可行解)的转移概率;通俗的理解是接受一个新解为当前解的概率;它与当前的温度参数T有关，随温度下降而减小。一般采用Metropolis准则,模拟退火算法（要素）,3、冷却进度表T(t)冷却进度表是指从某一高温状态To向低温状态冷却时的降温管理表。假设时刻t的温度用T(t)来表示，则经典模拟退火算法的降温方式为：而快速模拟退火算法的降温方式为：这两种方式都能够使得模拟退火算法收敛于全局最小点。,模拟退火算法（要素）,4、初始温度T0实验表明，初温越大，获得高质量解的几率越大，但花费的计算时间将增加。因此，初温的确定应折衷考虑优化质量和优化效率，常用方法包括：(1)均匀抽样一组状态，以各状态目标值的方差为初温。(2)随机产生一组状态，确定两两状态间的最大目标值差|max|，然后依据差值，利用一定的函数确定初温。比如，t0=max/pr，其中pr为初始接受概率。(3)利用经验公式给出。,模拟退火算法（要素）,5、内循环终止准则或称Metropolis抽样稳定准则，用于决定在各温度下产生候选解的数目。常用的抽样稳定准则包括：(1)检验目标函数的均值是否稳定；(2)连续若干步的目标值变化较小；(3)按一定的步数抽样。,模拟退火算法（要素）,6、外循环终止准则即算法终止准则，常用的包括：(1)设置终止温度的阈值；(2)设置外循环迭代次数；(3)算法搜索到的最优值连续若干步保持不变；(4)检验系统熵是否稳定。,模拟退火算法的改进,(1)设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。(2)设计高效的退火策略。(3)避免状态的迂回搜索。(4)采用并行搜索结构。(5)为避免陷入局部极小，改进对温度的控制方式(6)选择合适的初始状态。(7)设计合适的算法终止准则。,模拟退火算法的改进,也可通过增加某些环节而实现对模拟退火算法的改进。主要的改进方式包括：(1)增加升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。(2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将“BestSoFar”的状态记忆下来。(3)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传算法、混沌搜索等。(6)上述各方法的综合应用。,算法实现与应用,TSP问题的求解编码（城市编号顺序编码）状态产生函数（逆转算子）状态接受函数初温与初始状态，T0=max/pr降温函数设计温度修改准则和算法终止准则,运行过程,三、模拟退火算法的应用,3.130城市TSP问题（d*=423.741byDBFogel）,运行过程,三、模拟退火算法的应用,3.130城市TSP问题（d*=423.741byDBFogel）,运行过程,三、模拟退火算法的应用,3.130城市TSP问题（d*=423.741byDBFogel）,运行过程,三、模拟退火算法的应用,3.130城市TSP问题（d*=423.741byDBFogel）,运行过程,三、模拟退火算法的应用,3.130城市TSP问题（d*=423.741byDBFogel）,运行结果,三、模拟退火算法的应用,3.130城市TSP问题（d*=423.741byDBFogel）,92,1随机过程的概念,随机过程被认为是概率论的“动力学”部分，即它的研究对象是随时间演变的随机现象，它是从多维随机变量向一族(无限多个)随机变量的推广。给定一随机试验，其样本空间，将样本空间中的每一元作如下对应，便得到一系列结果：,随机过程的定义,94,例1：抛掷一枚硬币的试验，样本空间是，现定义：,95,96,97,例5：考虑抛掷一颗骰子的试验：,99,随机过程的分类：随机过程可根据参数集T和任一时刻的状态分为四类，参数集T可分为离散集和连续集两种情况，任一时刻的状态分别为离散型随机变量和连续型随机变量两种：连续参数连续型的随机过程，如例2，例3连续参数离散型的随机过程，如例1，例4离散参数离散型的随机过程，如例5离散参数连续型的随机过程，如下例,马尔科夫Markov链,Markov原名A.A.Markov（俄，18561922）于1906年开始研究此类问题.,1马尔可夫链的定义,引例假定某大学有1万学生，每人每月用1支牙膏，并且只使用“中华”牙膏与“黑妹”牙膏两者之一。根据本月（12月）调查，有3000人使用黑妹牙膏，7000人使用中华牙膏。又据调查,使用黑妹牙膏的3000人中，有60的人下月将继续使用黑妹牙膏，40的人将改用中华牙膏；使用中华牙膏的7000人中，有70的人下月将继续使用中华牙膏，30的人将改用黑妹牙膏。据此，可以得到如表所示的统计表,基本概念,状态和状态转移状态是指客观事物可能出现或存在的状况。如企业的产品在市场上可能畅销，也可能滞销。状态转移是指客观事物由一种状态到另一种状态的变化。客观事物的状态不是固定不变的，它可能处于这种状态，也可能处于那种状态，往往条件变化，状态也会发生变化。如某种产品在市场上本来是滞销的，但是由于销售渠道变化了，或者消费心理发生了变化等，它便可能变为畅销产品。,转移概率与转移概率矩阵假定某大学有1万学生，每人每月用1支牙膏，并且只使用“中华”牙膏与“黑妹”牙膏两者之一。根据本月（12月）调查，有3000人使用黑妹牙膏，7000人使用中华牙膏。又据调查,使用黑妹牙膏的3000人中，有60的人下月将继续使用黑妹牙膏，40的人将改用中华牙膏；使用中华牙膏的7000人中，有70的人下月将继续使用中华牙膏，30的人将改用黑妹牙膏。据此，可以得到如表所示的统计表,上表中的4个概率就称为状态的转移概率，而这四个转移概率组成的矩阵B称为转移概率矩阵。可以看出，转移概率矩阵的一个特点是其各行元素之和为,2转移概率矩阵及柯尔莫哥洛夫定理,（1）转移概率矩阵中的元素是根据近期市场或顾客的保留与得失流向资料确定的。（2）下一期的概率只与上一期的预测结果有关，不取决于更早期的概率。（3）利用转移概率矩阵进行决策，其最后结果取决于转移矩阵的组成，不取决于原始条件，即最初占有率。,用马尔科夫链方法进行决策的特点：主要用于企业产品的市场占有率预测,转移概率矩阵决策的应用步骤,1）建立转移概率矩阵。2）利用转移概率矩阵进行模拟预测。3）求出转移概率矩阵的平衡状态，即稳定状态。,4）应用转移概率矩阵进行决策。,例1某计算机机房的一台计算机经常出故障，研究者每隔15min观察一次计算机的运行状态，收集了24h的数据（共作97次观察）。用1表示正常状态，用0表示不正常状态，所得的数据序列如下：1110010011111110011110111111001111111110001101101111011011010111101110111101111110011011111100111,1）建立转移概率矩阵,Matlab程序见ex2.m,本月市场占有情况,转移概率矩阵,下月市场占有情况,2）利用转移概率矩阵进行模拟预测,3）求出转移概率矩阵的平衡状态，即稳定状态。,3转移概率的渐近性质极限概率分布,解空间的搜索,解,离散随机状态,随机状态的跳转,满意解,最终状态,SA接受准则/GA算子,状态转移概率矩阵,目标函数的导向性,稳态概率最大似然值对应状态,成绩构成,三次大作业50%，期末考试（闭卷）50%作业要求：尽量避免手写，应包含三部分内容（1）程序简要说明（2）程序代码（3）算例实验,考试内容,重“意”不重“形”考试内容重在对算法原理以及技术细节的理解，没有直接的数值计算。不考传统精确解技术，以现代优化方法为