系统的进化.pptx

自然界生物系统进化自然界生物系统进化生命起源l化学演化化学演化小分子、化学有机小分子、氨基酸、核酸小分子、化学有机小分子、氨基酸、核酸l生命诞生生命诞生从无序到有序从无序到有序原始的原始的RNA世界：酶、模板、结构世界：酶、模板、结构生命来源于自然，又高于自然：细胞生命来源于自然，又高于自然：细胞生命起源生命起源l1981年Cech发现核酶（有酶活性的RNA)l1986年Gibert提出“RNA世界”的观念，但.l1991年提出“硫酯世界”l1992年提出“铁硫世界”l1993年提出“无机焦磷酸世界”“ATP世界”生命是一个小概率事件，在海量的分子生命是一个小概率事件，在海量的分子反应中产生了极微量的活性分子，组成反应中产生了极微量的活性分子，组成有复制能力的分子体系，并不断地进化有复制能力的分子体系，并不断地进化和分化和分化早期进化论早期进化论达尔文进化论达尔文进化论综合进化论综合进化论中性进化学说中性进化学说分子进化和中性学术分子进化和中性学术中性突变中性突变遗传漂移遗传漂移分子进化的速率分子进化的速率渐变式进化和跳跃式进化渐变式进化和跳跃式进化物种绝灭和灾变物种绝灭和灾变Special creation continuous creationEvolution达尔文进化论的要点：l遗传l自发变异l繁殖过剩l生存斗争l适者生存自然选择学说生物总祖论综合进化论（突变、遗传平衡、各种隔离）l突变突变/遗传遗传为生物进化提供材料l隔离隔离是形成性物种的前提地理隔离生理生态隔离生殖隔离l自然选择分类学和进化的研究手段分类学和进化的研究手段形态学的比较（胚胎、解剖学等）免疫学实验方法分析蛋白质的同源性特定蛋白的氨基酸序列的比较核酸序列测定、分析中性进化学说（生物进化是无规律可循、偶然突变的累加的结果）（生物进化是无规律可循、偶然突变的累加的结果）l1968年木村在“Nature”提出“中性理论”l1969年Jing和Jukes提出“非达尔文进化”生物体内的突变大多为中性的l同义突变l同功突变l非功能性突变遗传飘变导致中性突变的保留和消失中性突变的速率决定了生物进化的速率l每个密码子每年的突变频率：(0.3-9)*10-9l中性学说是达尔文进化论的微观演化水平的进一中性学说是达尔文进化论的微观演化水平的进一步发展、修正、和补充。步发展、修正、和补充。基因分析法基因分析法l不同的基因突变的频率的差异l减数分裂产生染色体之间的基因交换为什么家系很重要基因资源的争论线粒体的重要性Y染色体的重要性l基因差异的研究的重要性生命进化的规律l进化不可逆l进化方式：顺序进化跳跃式进化分支进化l非均速进化各生物的种性各生物所处的环境11人工系统进化人工系统进化GA(Genetic Algorithm)GA 简介简介l起源:USAinthe1970sl最早提出:J.Holland,K.DeJong,D.Goldbergl典型应用领域:离散系统的优化l原理基于自然选择和基因遗传学原理的搜索算法l中心问题鲁棒性传统寻优方法解析法（直接法与间接法）枚举法随机搜索遗传算法的特点遗传算法的特点l1.直接对结构对象操作，不存在求导和函数连续性的限定；l2.遗传算法不是从单个点，而是从一个点地群体开始搜索；l3.具有内在的隐并行性和较好的全局寻优能力；l4.采用概率化寻优方法，能自动获取搜索过程中的有关知识并用于指导优化，自适应地调整搜索方向，不需要确定地规则；l5.鲁棒性基本遗传算法的构成要素基本遗传算法的构成要素l1.染色体编码方法l最常用的是二进制编码，对于离散性变量直接编码，对于连续性变量先离散化后再编码l2.适应度函数l评估函数用来评估一个染色体的优劣的绝对值l适配值评估一个染色体相对整个群体的优劣的相对值的大小3.遗传算子复制算子、交叉算子、变异算子4.基本遗传算法运行参数N：群体大小，即群体中所含个体的数量T：遗传算法的终止进化代数pc：杂交概率pm：变异概率pr：复制概率具体步骤具体步骤l复制l交叉l变异复制复制l个体根据其适配值的大小进行复制l适配值大的个体，表示其性能更好，也将有更大的概率产生下一代个体。l复制的目的是使得种群中具有“优良品质”的个体逐渐增多，为提高群体的整体素质、产生更优的下一代个体提供可能。l复制的方式：轮盘赌F=x2 x(0,31)lX用5位二进制串表示，为0000011111标号串F值占整体百分数10110116914.421100057649.2301000645.541001136130.9总计1170100转动四次转动四次l得到的四个串分别为：l01101l11000l11000l10011l其中：11000被复制两次，01000被遗弃交叉交叉l交叉是将两个串从某点截成两段或几段，将其中一个串的一段或几段变换到另一个串的相应位置。l交叉的目的在于获得更多的方案，使得现有的各个方法之间取长补短，为产生更优的方案提供可能。l交叉可以有单点交叉、双点交叉、均匀交叉几种方式。单点交叉单点交叉l在串中随机产生一个位置，将两个串的尾部从这一点互换。Parents:10100011100011010010Offspring:10100100100011001110Randomly chosen position双点交叉双点交叉l随机产生两个点，将两个串在其中间的部分进行交叉Parents:10100011100011010010Offspring:01010100100011001110Randomly chosen positions均匀交叉均匀交叉l随机产生一个模板，由其决定每一位来自哪个串Mask:0110011000 (Randomly generated)Parents:10100011100011010010Offspring:0011001010 1010010110变异变异l以一个很小的概率pm改变串中的一些位，使得原来的串发生变化。l变异前:(10110110)l变异后:(10100110)l变异的目的在于提高串的多样性，避免陷入局部极值遗传算法的实现遗传算法的实现l1.问题表示l（1）根据具体问题确定寻优的参数l（2）对每个参数确定它的变化范围，并用二进制码或格雷码表示，若参数a属于amin,amax，用m位二进制数b表述，l则满足将所有参数的二进制串连接成为算法操作的一个对象算法过程l1.随机产生一个由确定长度的特征串组成的初始群体l2.对串群体迭代地执行下面的步（i）和步（ii），直到满足停止准则：l（i）计算群体中每个个体的适应值l（ii）应用复制、杂交和变异算子产生下一代群体l3.把在任一代中出现地最好地个体串指定为遗传算法的执行结果，这个结果可以表示问题的一个解（或近似解）GEN0产生初始群体是否满足停止准则指定结果结 束计算每个个体的适应值i0iN？以概率选择遗传算子GENGEN1选择一个个体 选择两个个体 选择一个个体执行复制ii1执行变异复制到新群体执行杂交插入到新群体将两个子代串插入到新群体ii1是否是否prpcpmGEN当前代数 N群体规模遗传算法中的参数选择遗传算法中的参数选择l种群大小：大的种群数量有利于找到最优解但加大运算时间l交叉概率：大的交叉概率有利于加速收敛，但可能导致收敛于非最优解l变异概率：变异概率的提高可以增大多样性、但也可能导致不稳定改进的遗传算法改进的遗传算法l1.自适应变异：根据双亲的近似程度决定变异概率l2.优秀个体保护法：使得适配值高的个体直接进入下一代，不进行交叉、变异。l3.移民法：引入新个体代替适配值低的个体。l4.分布式遗传算法：将总的群体分成若干子群，每个子群分别进行进化。例：公交车智能排序问题例：公交车智能排序问题l公交排班的目的是确定最优或近似最优的运营车辆的发车时间表，公交车队按照该时间表发车能够达到最高的运营效率和服务水平不失一般性，只考虑下行线路即要优化始发站的发车时刻表设首班车发车时刻为早上6点整，末班车发车时刻为22点整，所有运营车都在整分钟时刻发车，一天之内的总班次为m，总时间为16小时，即960分。问题的初始化问题的初始化l串的长度为960，其中该位为1代表该分钟有车发出，0代表无车发出，共有60位为1，1的位置随机产生。乘客分布乘客分布目标函数目标函数36应用应用l组合优化（离散）l函数优化（连续）l自动控制l生产调度l图像处理l机器学习l人工生命l数据挖掘37进化策略（进化策略（Evolution Strategies)l1964年在德国提出，基本步骤如下：l定义目标函数：l随机选择初始群体作为父辈双亲。l通过叠加零均方差高斯随机扰动产生子辈群体。l根据目标函数选择一定量的个体作为下一代双亲。l群体的标准偏差保持不变或完成指定迭代步数,那么处理结束。38进化编程进化编程(Evolutionary Programming)lFogel在1962年提出l产生出初始群体（处理程序）l应用变异等操作创造新的程序群体。l在后代中适应值最高的计算机程序个体被指定为进化编程的结果。39三种算法的比较三种算法的比较遗传算法进化策略进化编程思想群体繁衍、适者生存个体染色体（二进制）个体（实数）程序算子复制、交叉为主变异为主、无交叉变异算子取反高斯噪声组合变化40人工生命人工生命l人工生命是指用计算机和精密机械等生成或构造表现自然生命系统行为特点的仿真系统或模型系统。l计算机病毒l细胞机器人41生命的特点生命的特点l非线性系统：自组织能力l繁衍能力：自复制、自稳定的能力l环境适应性：自修复、进化的能力。42研究目的研究目的l构造自组织的人工系统。l分析自然的生命系统。43元胞自动机（元胞自动机（Cellular Automation）l元胞自动机元胞自动机是定义在一个由具有离散、有限状态的元胞组成的元胞空间上，并按照一定局部规则，在离散的时间维上演化的动力学系统。l四个阶段:1940s诞生：VonNeumann自我复制机.1960-70s起步：JH.Conway生命游戏.1980s理论研究：S.WolframCA分类.1980-90s应用：HPP-FHP格子气自动机、C.LangtonN.Packard人工生命44结构结构45研究内容研究内容l分布系统理论：通信、信息传递(Communication)、计算(Computation)、构造(Construction)、生长(Growth)、复制(Reproduction）、竞争(Competition)与进化(Evolution)l非线性动力学系统理论：秩序(Ordering)、紊动(Turbulence)、混沌(Chaos)、非对称(Symmetry-Breaking)、分形(Fractality)等46应用应用l社会学：人工流动l生态学：环境变化l经济学：经济危机l数学：数论和并行计算l物理学：流体力学、电磁场l化学：研究化学反应的过程4748Rules in Detail:Fish RulesIfthecurrentcellcontainsafish:lFishlivefor10generationslIf=5neighborsaresharks,fishdies(sharkfood)lIfall8neighborsarefish,fishdies(overpopulation)lIfafishdoesnotdie,incrementage49Rules in Detail:Shark RulesIfthecurrentcellcontainsashark:lSharkslivefor20generationslIf=6neighborsaresharksandfishneighbors=0,thesharkdies(starvation)lAsharkhasa1/32(.031)chanceofdyingduetorandomcauseslIfasharkdoesnotdie,incrementage50Shark Random Death:BeforeISureHopethattherandomnumberchosenis.03151Shark Random Death:AfterYESITIS!ILIVE