病毒协同进化遗传算法

病毒协同进化遗传算法

VirusCo-EvolutionaryGeneticAlgorithm(VEGA)

-----AnIntroduction-----胡仕成19/3/2004TuringForum报告内容GA简介VEGA的提出病毒个体的编码病毒个体的操作病毒个体的适应度病毒个体的参数VEGA的算法过程VEGA的性能评价VEGA的算法特点一个例子结论#GA简介解的编码GA的进化操作GA的参数GA的性能评价#解的编码－GA的基础解空间一个解的编码染色体(chromosome)编码其中的一个码和码所在的位置基因(gene)/基因位GA的进化操作－初始化(initialize)解的编号解的编码123......POP群体规模4GA的进化操作－交叉(cross)交叉位Pcrosscross父代个体子代个体交叉概率连续改变染色体多个基因位上的遗传信息1212GA的进化操作－变异(mutate)变异位Pmutatemutate父代个体子代个体变异概率随机改变染色体某些基因位上的遗传信息GA的进化操作－计算适应度解码计算适应度GA的进化操作－选择(select)select初始群体变异群体进化群体GA的参数群体规模POP交叉概率Pcross变异概率PmutateGA的性能评价－和其它算法比解的最优性(满意度)收敛速度达到最优值(满意值)的计算时间达到最优值(满意值)的计算代数模板理论得到符合要求的阶数尽可能大的模板VEGA的提出GA的进化原理：根据适应度进行选择将进化解保留到下一代通过交叉和变异逐代获得解的进化，最终产生最优解(满意解)VEGA的提出GA的进化导向单一基本上只能通过适应度来导向解的进化方向如果f1>f2，则个体1比个体2容易保留到下一代。但是，个体1并不一定比个体2“优越”VEGA的提出个体1的全部基因f1>f2从全部基因看，个体1更接近最优个体最优个体f2’>f1’从部分基因看，个体2更接近最优个体全部基因的贡献部分基因的贡献个体1的部分基因个体2的部分基因个体2的全部基因VEGA的提出GA的进化操作不一定能产生进化解，甚至还有可能产生退化解因为交叉和变异操作是随机的，和适应度无关VEGA的提出如何将部分“好”的基因保留并使之逐渐增长，当“好”的基因的长度=染色体长度时，就获得了最优解(绝对最优)VEGA的提出1996,Kubota(Japanese)提出了基于virus进化理论的遗传算法VEGAvirus的遗传特性：感染能力：virus能够将自身所携带的遗传信息传递给其它个体进化能力：virus能够从其它个体获取部分遗传信息来改变自己的遗传信息从而得以进化感染能力进化能力VEGA的提出VEGA的基本思想：“好”基因的识别－病毒的适应度“好”基因的增长－病毒的进化操作病毒个体的编码病毒个体：染色体(主个体)的部分基因*主个体(解)病毒个体的等长编码（含通配符）病毒个体的不等长编码（不含通配符）******通配符(无效基因)有效基因hostvirusvirus病毒个体的操作－感染操作病毒个体使主个体进化－病毒个体改变主个体的基因(infect)，产生进化解*病毒个体******感染前主个体感染后主个体hostvirushost病毒个体的操作－复制操作病毒个体的进化－病毒个体从主个体获取基因改变自己的基因(copy)，病毒个体增长*******主个体*****复制前病毒个体复制后病毒个体virushostvirus病毒个体的操作－复制操作病毒个体的初始化－通过“无感染能力”的病毒个体的复制操作产生新的病毒个体**************主个体*****复制前病毒个体复制后病毒个体virushostvirus*****病毒个体的操作－剪切操作病毒个体的退化－病毒个体删去部分基因(cut)，病毒个体缩短****************剪切前病毒个体剪切后病毒个体virusvirus*病毒个体的适应度病毒的感染特点：一个病毒可以感染多个个体*病毒个体******感染前主个体感染后主个体病毒个体的适应度病毒个体i的适应度=被病毒i感染的那些主个体的感染后的适应度之和-感染前的适应度之和病毒个体的参数病毒的群体规模POPvirus病毒i的感染概率Pinfect=f(病毒i的适应度)，Pinfect∈(Pinit_infect,Pmax_infect)，Pinfect是随着病毒适应度的变化而动态变化的，反映了病毒对主个体的感染能力的变化病毒i的复制概率Pcopy病毒i的剪切概率Pcut病毒i的生命力Life=f(病毒i的适应度)，反映了病毒的生存能力，当Life<0，该病毒生命结束，需要产生新的病毒VEGA的算法过程初始化主群体相关参数：POP，Pcross，Pmutate病毒群体相关参数：POPvirus，Pinit_infect，Pmax_infect，Pcopy，Pcut，等判断算法的终止条件GA的进化过程交叉操作变异操作计算主个体适应度选择操作VEGA的算法过程对每个病毒个体i执行以下VE操作计算Pinfect(对初始病毒个体Pinfect=Pinit_infect)以Pinfect对每个主个体执行infect操作计算病毒个体i的适应度根据主个体感染前后适应度的变化决定感染后的主个体是否替换感染前的主个体根据病毒个体i的适应度决定执行概率为Pcopy的copy操作或者概率为Pcut的cut操作计算病毒个体i的生命力Life，如果Life<0，则执行概率为Pcut的cut操作产生新的病毒替换该病毒VEGA的性能评价－和GA相比解的最优性(满意度)收敛速度达到最优值(满意值)的计算时间达到最优值(满意值)的计算代数模板理论

得到符合要求的阶数尽可能大的模板VEGA的算法特点编码特点：解的进化和解集的进化相结合GA：等长编码，一个主个体代表解空间中的一个解VE：变长编码，一个病毒个体代表解空间中的一个解集(一个模板)*******VEGA的算法特点操作特点：全局搜索和局部搜索相结合GA(cross,mutate,select)：全局解空间中搜索(Global)，纵向上下代群体之间传递遗传信息(Vertical)，保证全局最优VE(infect,copy,cut)：局部解空间中搜索(Local)，横向同一代群体之内传递遗传信息(Horizontal)，保证快速局部最优GA搜索轨迹VE搜索轨迹VEGA的算法特点参数特点：静态搜索和动态搜索相结合GA(POP,Pcross,Pmutate)：静态搜索(Static)VE(POPviurs,Pinfect=f(