系统的进化.ppt

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