第9章-Memetic算法

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,Company,Logo,*,Click to edit Master title style,*,Click to edit Master title style,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,第,9,章,Memetic,算法,Contents,基本思想,1,算法框架,2,静态,Memetic,算法,3,动态,Memetic,算法,4,研究展望,5,9,.,1 Memetic,算法的基本思想,Meme,概念的提出,Hawkins,（,1976,）,Mosato,（,1989,）提出了,Memetic,算法,Memetic,算法,基于群体的计算智能方法与局部搜索相结合的一类算法的总称,基因（,Gene,）,文化基因（,Meme,）,相似点,在遗传过程中通过交叉、变异等操作不断演化发展,在传播过程中通过交互、融合、变异等方式传承发展,不同点,在生物进化过程中，变异是随机的，只有少数好的变异能够在自然选择中得到保留,文化传播过程往往都以充分的,专业领域知识,为基础，进化速度更快,9,.,2 Memetic,算法的框架,Memetic,算法的基本模型（,9,要素）,初始种群,算法的初始参数,popSize,种群规模,offspringSize,通过生成函数得到的后代的数目,l,编码长度,F,适应值函数,G,生成函数（如交叉、变异等算子）,U,更新函数（如选择算子）,局部搜索策略的集合,9,.,2 Memetic,算法的框架,Memetic,算法的流程图,开始,生成初始种群,初始化参数,k,=0,结束？,结束,返回最优解,计算适应值,利用更新函数得到新一代种群,利用生成函数产生新群体,局部搜索,局部搜索,k,=,k,+1,N,Y,Memetic,的各种设计方案：,全局搜索策略的选择,（进化算法,/,ACO,/,PSO,）,局部搜索策略的选择,（单一局部搜索策略,/,多种局部搜索策略）,局部搜索策略的位置,（与生成函数相结合,/,与更新函数相结合）,局部搜索的方式,（,Lamarckian/,Baldwinian,）,局部搜索的对象,（整个群体,/,部分个体）,局部搜索与全局搜索的平衡,（局部搜索的强度与频率）,局部搜索的参数,（邻域的形状和大小,/,移动步长）,9,.,2 Memetic,算法的框架,9,.,3,静态,Memetic,算法,静态,Memetic,算法的特点,一般只采用一种局部搜索策略,局部搜索的执行位置和方式都预先确定，在算法执行过程中保持不变,目前已提出的,Memetic,算法，大部分都属于静态,Memetic,算法,9,.,3,静态,Memetic,算法,部分代表性的静态,Memetic,算法,局部搜索的位置,与生成函数相结合,与更新函数相结合,代表性算法,Nguyen et al.2007,Nguyen et al.2002 Burke et al.2000,Sheng,et al.2007,Noman,and,Iba,2008,等等,Tu,and Lu,2004,局部搜索的方式,Lamarckian,Baldwinian,代表性算法,Krasnogor,and Smith,2006,Dorigo,et al.2004,一般而言，,Lamarckian,方式比,Baldwinian,方式性能更优,9,.,4,动态,Memetic,算法,动态,Memetic,算法,动态调整局部搜索策略,分类,按照动态调整类型，分成三类,静态型,按照静态的规则来调整,适应型,利用在线反馈的信息来调整,自适应型,将局部搜索设置信息也编码到算法当中一起进化（协同进化的,MA,）,按照自适应的层次，分成三类,外部型,利用外部的先验知识（一般属于静态型）,局部型,采用了局部反馈信息来调整,自适应型,采用了全部反馈信息来调整,9,.,4,动态,Memetic,算法,动态,Memetic,算法的流程图,开始,生成初始种群,初始化参数,k,=0,结束？,结束,返回最优解,计算适应值,利用更新函数得到新一代种群,利用生成函数产生新群体,局部搜索,局部搜索,k,=,k,+1,N,Y,从,L,中选出一种局部搜索策略设置,9,.,4,动态,Memetic,算法,Meta-,Lamarckian,学习型,Memetic,算法,每次执行局部搜索之前，从局部搜索策略池中选择一种局部搜索方案,基本,Meta-Lamarckian,学习,方案,子问题分解的启发式搜索方案,带偏向性轮盘赌的随机搜索方案,9,.,4,动态,Memetic,算法,9,.,4,动态,Memetic,算法,超启发式,Memetic,算法,随机超启发式,随机地选择局部搜索策略,贪心超启发式,选择能够得到最大改进幅度的局部搜索策略,基于选择函数的超启发式,根据局部搜索策略的选择函数,F,值来选择局部搜索策略。,协同进化,Memetic,算法,局部搜索的具体设置也编码到个体的基因中，共同进化。,协同进化,MA,的流程图,9,.,4,动,态,Memetic,算法,部分代表性的,动,态,Memetic,算法,类型,静态,适应,自适应,外部,基本,meta-Lamarckian,学习，,Simplerandom,等,局部,子问题分解的启发式搜索，贪心超启发式，,Randomdescent,，,Randompermdescent,协同进化,MA,（或自生,MA,），自适应,MA,全局,带偏向性轮盘赌的随机搜索，基于,PSO,的,MA,，基于选择函数的超启发式，快速适应,MA,9,.,5 Memetic,算法的研究展望,理论研究进展,MA,的语法框架（,Krasnogor,和,Smith,）,MA,的收敛性分析（,Ong,et al.,）,MA,的搜索行为和收敛性分析还基本处于空白状态,应用研究进展,已应用于众多复杂优化问题,应用研究进展,自适应与协同进化,MA,多目标,MA,基于智能体的,MA,Thank You!,