复杂性科学与智能计算.ppt

复杂性科学与智能计算 2 报告人 陈贤富中国科学技术大学电子科学与技术系E mail xfchen Tel 3602173 o 3661273 H 33869872004年5月19日 攻城不怕坚攻书莫畏难科学有险阻苦战能过关 叶剑英元帅 1977年安徽高考作文题 从科学有险阻苦战能过关谈起 往哪儿谈 演化性 非线性 复杂性 创造性模式定理 混沌现象 涌现机制 突生演化 创新系统模型 报告内容 1 复杂性 的根源2 3 积木块假设与混沌现象4 复杂系统与复杂性 简介 5 突生演化 创新过程6 创新 丰富联想 随机碰撞 个人观点 1 Holland的生物进化模拟与复杂自适应系统 1 科学技术发展的源泉 路甬祥院长1 生产 生活2 模拟自然1960年前后 Holland企图运用计算机模拟生物的遗传演化过程没料到 遗传模拟 优化算法1975年 Holland出版名著 自然与人工系统的自适应 遗传算法的基本思想 达尔文进化论 门德尔遗传学说遗传算法的基本构架 选择 交叉 变异遗传算法的基本理论 Holland模式定理 1 Holland的生物进化模拟与复杂自适应系统 2 再次出乎所料 精心模拟达尔文进化论的遗传算法实际上反映的是非达尔文主义进化思想 由选择 交叉 变异三个基本GA算子构成的遗传算法却呈现出独特的阶跃性 探险式搜索方式和学习能力 这种阶跃性 探险式搜索方式反映了突生演化的主要特征 80年代中后期 Holland转入非线性 复杂性科学领域智能诞生在混沌边缘智能 复杂自适应系统 2 关于Holland模式定理的理论研究 生物进化动力 主流观点 自然选择基因突变区域隔离与基因流动随机漂变标准遗传算法基本算子 Holland 选择 selection 交叉 crossover 变异 mutation Holland模式定理推导思路 交叉操作破坏模式 Schema 变异操作破坏模式 Schema 2 关于Holland模式定理的理论研究 2 Holland的模式定理在选择 交叉和变异操作的作用下 低模阶 短模长 高适应度的优模式在连续后代中呈指数级增长 Holland模式定理的缺陷1 模式增长的下限估计过低2 不能解释遗传算法的收敛过程 2 关于Holland模式定理的理论研究 3 Holland忽略的模式增长因素1 隐含模式H的个体之间进行交叉对模式H的保护作用 2 模式H与非H模式相交叉时 模式H的生存机会 a 交叉位点在模式H之外 b 个体间模式相似度极高 3 非模式H的个体在交叉和变异过程中 创造模式H 2 关于Holland模式定理的理论研究 3 同模式 具有共同特征 个体之间的交叉对模式H的保护作用 1 优模式在遗传演化过程中呈指数级增长 2 人以群聚 物一类分 同类交配是自然遗传的主要方式 2 关于Holland模式定理的理论研究 4 修正的模式定理 经标准GA遗传操作后 种群中模式H数目的数学期望值可用下式进行估计 修正的模式定理的下界始终是大于Holland模式定理的下界的 Holland模式定理并未涉及模式数量这一因素 但修正的模式定理明确的表明 模式的增长不仅仅跟模式的平均适应度有关 而且还与模式的相对数量有关 2 关于Holland模式定理的理论研究 5 结论 1 提高了模式估计的下限 2 揭示了低阶模式主要靠适应度占优不断发展 高阶模式主要靠数量占优维持生存的GA模式演变特性 3 积木块假设与混沌现象 积木块假设 在选择 交叉和变异操作的作用下 低模阶 短模长 高适应度的优模式 积木块 在连续后代中呈指数级增长 混沌 误差随时间呈指数级增长 问题 可否用遗传算法模拟混沌现象 指数级增长 纯随机 不可预测 复杂涌现 4 复杂系统与复杂性 简介 l当代科学的发展特点 从2到3 科技前沿 极大 极小 极复杂研究手段 理论 实验 模拟研究对象 物质 能量 信息研究方法 分析 还原 集成体现了哲学观念的重大变革 4 复杂系统与复杂性 简介 1877年 哲学家GeorgeHenryLewes在批评Hume的 因果关系理论 时指出 有必要区分两种类型的效果 effects 因果型效果和突生型效果 有些效果是不能依据组成部件或构成要素的有关知识来进行预测的 也不能分解为子功能或部件的组合 4 复杂系统与复杂性 简介 2 l什么是 复杂性 远离平衡的巨大耗散系统中由于组成单元之间局部的非线性作用而自发涌现出的系统整体特性 l复杂性体现了以下特点 1 复杂性是从属于某个系统的内禀性质和特征 研究复杂性离不开系统 但并非任何系统都具有复杂性 2 这个性质 主要指系统的 整体的 全局的性质 是突生的 具有不可归约 不可预测等特征 3 突生结果源自系统内部的自组织过程 4 复杂系统与复杂性 简介 3 l涌现机制是复杂性研究的中心课题l涌现机制 Emergence 的基本特征 新颖性 创新性 不可预测性 Holland认为 对一个处于某种环境内的协同进化系统来说 没有任何事情是固定不变的 复杂自适应系统的本质就在于进化过程中突生的永恒的新奇性 4 复杂系统与复杂性 简介 4 lGA本质上的并行性及其独特的阶跃性探险式搜索方式和学习能力 具有某些突生演化特征 为 复杂性研究 和 复杂系统模拟 提供了重要的研究思路和研究手段 5 突生演化 创新过程 1922年 哲学家C LloydMorgan在传播Lewes的突生理论演讲中 首次使用了 突生进化 术语 他认为高级复杂组织是较低级组织的突生进化结果 1930年Mead在美国哲学学会会议上发表著名演讲二十世纪二十年代前后 当突生学说主要作为一种生物进化理论时 不少 创造性理论 的开拓者就把 创造性活动 比喻成 突生进化过程 形成了当时的创造性研究热潮 5 突生演化 创新过程 2 1960年 Cambell提出了类似自然进化过程的创造性活动三阶段 盲目求异 blandvariation 阶段 自然选择 selection 阶段和维持 retention 阶段 1988年 Csikszentmihalyi依据Cambell思想指出创造性系统应包括三个组成部分 富有创造力的个体发生器 产生新颖性 由个体组成的社会系统 依据建立的标准评估新生个体并进行自然选择 外部机制 依据较为稳定的物理特性提供维持能力和评估标准 1913年 数学家HenriPoincare这样来描述他的创见的突生 一天晚上 我品着黑咖啡 久久不能入眠 思绪在脑中翻滚 我感觉它们在冲突和碰撞 欲以一种稳定的组合形态说点什么 第二天早晨醒来 我确认了一类Fuchian函数的存在 5 突生演化 创新过程 3 1988年 认知学家Simonton在他提出的认知模型中继承了这一思想 指出一个个体要进行创新 必须具有涉及所创新领域的精神元素 例如事实 理论及信息等 并把这些精神元素存储在脑子里 通过潜意识的创新过程 各种精神元素进行随机的结合和构造 虽然大部分新颖的构造物是不稳定的 不能被人们所意识到 但可能有若干新颖的构造物稳定得足以让人主观感觉到一种创见的突生 在突生现象的模拟和仿真方面 Holland先生开创了先河 6 创新 丰富联想 随机碰撞 个人观点 联想能力是人类智能 智慧 的主要标志之一灵感来自随机碰撞 GA的交叉操作 创新是一个突生进化过程基于领域知识的丰富联想 精神元素的随机碰撞 具有创新性的火花 火花 通过在系统中传播和蔓延 遗传演化 稳定下来 创新成果基于突生演化机理的联想式创新系统模型研究 国家自然基金课题 近期若干研究思想 多层次演化计算 1 单基因层次 物理 化学 生理 生化层次2 基因型层次 有序结构 遗传演化 3 主体层次 主体对环境的适应 经验学习 条件反射式的适应 4 系统层次 竞争 自组织 协同发展 近期若干研究思想 2 弹性TSP问题研究 1 突触连接 橡皮筋 有弹性2 神经网络 图3 脑思维 图论问题求解4 求解过程 外部刺激 灵感 下的丰富联想5 求解结果 边界条件下多角度 多层次丰富联想的共鸣 主观与客观的一致 近期若干研究思想 3 沙漠绿洲的蔓延 生态演化 1 生命的源泉