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

复杂性科学与智能计算,（2） 报告人：陈贤富 中国科学技术大学电子科学与技术系 e_mail: tel: 3602173(o) 3661273(h) 3386987 2004年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年,哲学家george henry lewes 在批评hume的“因果关系理论“时指出,有必要区分两种类型的效果(effects):因果型效果和突生型效果.有些效果是不能依据组成部件或构成要素的有关知识来进行预测的,也不能分解为子功能或部件的组合.,4. 复杂系统与复杂性（简介）（2）,l 什么是“复杂性“? 远离平衡的巨大耗散系统中由于组成单元之间局部的非线性作用而自发涌现出的系统整体特性。 l 复杂性体现了以下特点: 1.复杂性是从属于某个系统的内禀性质和特征.研究复杂性离不开系统,但并非任何系统都具有复杂性. 2.这个性质(主要指系统的、整体的、全局的性质)是突生的, 具有不可归约、不可预测等特征. 3.突生结果源自系统内部的自组织过程.,4. 复杂系统与复杂性（简介）（3）,l 涌现机制是复杂性研究的中心课题 l 涌现机制(emergence)的基本特征: 新颖性(创新性) 不可预测性. holland认为,对一个处于某种环境内的协同进化系统来说,没有任何事情是固定不变的,复杂自适应系统的本质就在于进化过程中突生的永恒的新奇性.,4. 复杂系统与复杂性（简介）（4）,l ga本质上的并行性及其独特的阶跃性探险式搜索方式和学习能力(具有某些突生演化特征),为“复杂性研究”和“复杂系统模拟”提供了重要的研究思路和研究手段.,5. 突生演化=创新过程,1922年,哲学家c.lloyd morgan在传播lewes的突生理论演讲中,首次使用了“突生进化“术语,他认为高级复杂组织是较低级组织的突生进化结果. 1930年mead 在美国哲学学会会议上发表著名演讲 二十世纪二十年代前后,当突生学说主要作为一种生物进化理论时,不少“创造性理论“的开拓者就把“创造性活动“比喻成“突生进化过程“,形成了当时的创造性研究热潮.,5. 突生演化=创新过程(2),1960年,cambell提出了类似自然进化过程的创造性活动三阶段:盲目求异(bland variation)阶段,自然选择(selection)阶段和维持(retention)阶段. 1988年,csikszentmihalyi依据cambell思想指出创造性系统应包括三个组成部分:富有创造力的个体发生器-产生新颖性,由个体组成的社会系统-依据建立的标准评估新生个体并进行自然选择,外部机制-依据较为稳定的物理特性提供维持能力和评估标准. 1913年,数学家henri poincare这样来描述他的创见的突生:“一天晚上,我品着黑咖啡,久久不能入眠.思绪在脑中翻滚,我感觉它们在冲突和碰撞,欲以一种稳定的组合形态说点什么.第二天早晨醒来,我确认了一类fuchian函数的存在.“,5. 突生演化=创新过程(3),1988年,认知学家simonton在他提出的认知模型中继承了这一思想,指出一个个体要进行创新,必须具有涉及所创新领域的精神元素-例如事实,理论及信息等,并把这些精神元素存储在脑子里,通过潜意识的创新过程,各种精神元素进行随机的结合和构造,虽然大部分新颖的构造物是不稳定的,不能被人们所意识到,但可能有若干新颖的构造物稳定得足以让人主观感觉到一种创见的突生. 在突生现象的模拟和仿真方面,holland先生开创了先河,6. 创新: 丰富联想 + 随机碰撞 （个人观点）,联想能力是人类智能(智慧)的主要标志之一 灵感来自随机碰撞（ga的交叉操作） 创新是一个突生进化过程 基于领域知识的丰富联想+精神元素的随机碰撞= “ 具有创新性的火花 ” “火花” 通过在系统中传播和蔓延（遗传演化）稳定下来=创新成果 基于突生演化机理的联想式创新系统模型研究 国家自然基金课题,近期若干研究思想：,多层次演化计算： 1）单基因层次：物理、化学、生理、生化层次 2）基因型层次：有序结构（遗传演化） 3）主体层次：主体对环境的适应（经验学习，条件反射式的适应） 4）系统层次：竞争、自组织、协同发展。,近期若干研究思想：,2. 弹性tsp问题研究： 1）突触连接=橡皮筋：有弹性 2）神经网络=图 3）脑思维=图论问题求解 4）求解过程=外部刺激（灵感）下的丰富联想 5）求解结果：边界条件下多角度、多层次丰富联想的共鸣！（主观与客观的一致）,近期若干研究思想：,3. 沙漠绿洲的蔓延（生态演化） 1）生命的源泉：水 “