第9章-Memetic算法

第9章Memetic算法Contents基本思想1算法框架2静态Memetic算法3动态Memetic算法4研究展望59.1Memetic算法的基本思想Meme概念的提出—Hawkins（1976）Mosato（1989）提出了Memetic算法Memetic算法—基于群体的计算智能方法与局部搜索相结合的一类算法的总称基因（Gene）文化基因（Meme）相似点在遗传过程中通过交叉、变异等操作不断演化发展在传播过程中通过交互、融合、变异等方式传承发展不同点在生物进化过程中，变异是随机的，只有少数好的变异能够在自然选择中得到保留文化传播过程往往都以充分的专业领域知识为基础，进化速度更快9.2Memetic算法的框架Memetic算法的基本模型（9要素）),,,(002010popSizexxxP0初始种群算法的初始参数popSize种群规模offspringSize通过生成函数得到的后代的数目l编码长度F适应值函数G生成函数（如交叉、变异等算子）U更新函数（如选择算子）局部搜索策略的集合),,,(21mLLLL),,,,,,,,(00LUGFlpopSizeizeoffspringSPMA9.2Memetic算法的框架Memetic算法的流程图开始生成初始种群初始化参数k=0结束？结束返回最优解计算适应值利用更新函数得到新一代种群利用生成函数产生新群体局部搜索局部搜索k=k+1NYMemetic的各种设计方案：全局搜索策略的选择（进化算法/ACO/PSO……）局部搜索策略的选择（单一局部搜索策略/多种局部搜索策略）局部搜索策略的位置（与生成函数相结合/与更新函数相结合）局部搜索的方式（Lamarckian/Baldwinian）局部搜索的对象（整个群体/部分个体）局部搜索与全局搜索的平衡（局部搜索的强度与频率）局部搜索的参数（邻域的形状和大小/移动步长）9.2Memetic算法的框架9.3静态Memetic算法静态Memetic算法的特点一般只采用一种局部搜索策略局部搜索的执行位置和方式都预先确定，在算法执行过程中保持不变目前已提出的Memetic算法，大部分都属于静态Memetic算法9.3静态Memetic算法部分代表性的静态Memetic算法局部搜索的位置与生成函数相结合与更新函数相结合代表性算法Nguyenetal.2007Nguyenetal.2002Burkeetal.2000Shengetal.2007NomanandIba2008等等TuandLu2004局部搜索的方式LamarckianBaldwinian代表性算法KrasnogorandSmith2006Dorigoetal.2004一般而言，Lamarckian方式比Baldwinian方式性能更优9.4动态Memetic算法动态Memetic算法—动态调整局部搜索策略分类按照动态调整类型，分成三类静态型—按照静态的规则来调整适应型—利用在线反馈的信息来调整自适应型—将局部搜索设置信息也编码到算法当中一起进化（协同进化的MA）按照自适应的层次，分成三类外部型—利用外部的先验知识（一般属于静态型）局部型—采用了局部反馈信息来调整自适应型—采用了全部反馈信息来调整9.4动态Memetic算法动态Memetic算法的流程图开始生成初始种群初始化参数k=0结束？结束返回最优解计算适应值利用更新函数得到新一代种群利用生成函数产生新群体局部搜索局部搜索k=k+1NY从L中选出一种局部搜索策略设置9.4动态Memetic算法Meta-Lamarckian学习型Memetic算法每次执行局部搜索之前，从局部搜索策略池中选择一种局部搜索方案基本Meta-Lamarckian学习方案子问题分解的启发式搜索方案带偏向性轮盘赌的随机搜索方案9.4动态Memetic算法局部搜索1局部搜索2局部搜索3局部搜索4局部搜索5局部搜索6局部搜索7局部搜索8xy初始时，各种局部搜索策略具有相同的被选择概率执行了局部搜索后，根据局部搜索取得的适应值改进情况调整局部搜索的被选择概率随后，各种局部搜索策略具有不同的被选择概率（a）子问题分解的启发式搜索方案（b）带偏向性轮盘赌的随机搜索方案统计局部搜索初始点的邻域中的历史信息，采用在该邻域中具有最大平均适应值的局部搜索策略。9.4动态Memetic算法超启发式Memetic算法随机超启发式–随机地选择局部搜索策略贪心超启发式–选择能够得到最大改进幅度的局部搜索策略基于选择函数的超启发式–根据局部搜索策略的选择函数F值来选择局部搜索策略。协同进化Memetic算法局部搜索的具体设置也编码到个体的基因中，共同进化。开始生成初始种群P0和参数0根据基因的适应值，选择出新一代种群每个个体都按照它的文化基因所表示的局部搜索方式来进行局部搜索k=0满足算法结束条件？k=k+1结束返回最优解是否对基因执行交叉、变异操作，得到下一代群体对文化基因（meme）进行进化操作评价基因和文化基因的适应值子程序开始选择方式？直接选择上一代的文化基因按照文化基因的适应值选择随机选择对选择出的文化基因群体进行交叉和变异操作子程序结束方式1方式2方式3协同进化MA的流程图9.4动态Memetic算法部分代表性的动态Memetic算法类型静态适应自适应外部基本meta-Lamarckian学习，Simplerandom等局部子问题分解的启发式搜索，贪心超启发式，Randomdescent，Randompermdescent协同进化MA（或自生MA），自适应MA全局带偏向性轮盘赌的随机搜索，基于PSO的MA，基于选择函数的超启发式，快速适应MA9.5Memetic算法的研究展望理论研究进展MA的语法框架（Krasnogor和Smith）MA的收敛性分析（Ongetal.）MA的搜索行为和收敛性分析还基本处于空白状态应用研究进展已应用于众多复杂优化问题应用研究进展自适应与协同进化MA多目标MA基于智能体的MA