智能计算与自然计算

李元香武汉大学软件工程国家重点实验室2008年6月从人工智能到自然计算报告提纲•梦想与困惑•人工智能及其发展•面临困境•信息时代的呼唤•智能计算—回归自然•自然计算•展望梦想•机器具有智能—计算机科学家的梦想什么是智能？能感知、能学习、能思维、能记忆、能决策、能行动，智能的核心是思维图灵测试•怎样判断机器具有智能—图灵测试1950年AlanTuring的文章“ComputingMachineryandIntelligence.”（Mind,Vol.59,No.236）提出图灵测试，检验一台机器或电脑是否具有如人一样的思维能力和智能电脑和人分别封闭在不同的房间，测试者不知道哪个房间是人，哪个房间是电脑，他向双方提出测试问题，电脑和人给出各自的答案，如果一系列的测试问题之后，测试者分不出哪些是电脑的答案，哪些是人的答案，则电脑通过测试，确实具有与人一样的智能。我是人哦！我是谁？如实回答？测试悖论•公平性问题图灵测试的出发点显然是刁难电脑，要求电脑模仿人回答问题，公平吗？反过来要求人模仿电脑回答问题，公平吗？•标准性问题在怎样的智能水平下对电脑进行测试？天才、普通人还是婴幼儿，或者说怎样认定电脑的智力水平？•全面性问题怎样全面地测试电脑的智能，喜、怒、哀、乐和表情等有关情感的测试如何进行？测试边界怎样确定？•欺骗性问题电脑如果有意欺骗测试者，测试者能判断出来吗？在一定的范围内进行测试还是可行的困惑•哲学问题（1）规则与规律：规则是制定的，规律是客观存在的，从规则能自动发现规律吗？（2）生命与非生命：智能是高等生命体独有的能力，非生命体内能产生智能吗？（3）物质与意识：唯物主义和唯心主义都承认二元论，只是在何者起决定作用上争论不休，智能能在机器内产生将导致一元论—物质生成一切？（4）智能的本质：理性与感性、思考与行动、社会性与个体性•伦理问题（1）电脑与人脑：能否互换？（2）机器人与人：机器能否融入人类社会？（3）情感与役使：机器是人制造并使用的工具，一旦机器人具有了智能和情感，人类还能当奴隶一样地役使吗？（4）机器人叛乱：机器人群体有可能叛乱而反过来役使人类吗？现实的梦•比尔·盖茨预测：智能计算发展前景乃是机器最终“能看会想，能听会讲”•无论是人工智能，还是智能人工，只要能够殊途同归，造福于人类，那么所有的努力便都是有价值的•今后十年，智能机器作为真正意义上的工作助手和生活良伴，将使我们的生活完全改观•“聪明机器”的出现，也决不会成为人类的灾难，在智慧与创造力方面，永远是人类最有发言权人工智能•人工智能（artificialintelligence，简称AI）用人工的方法和技术，模仿、延伸和扩展人的智能,实现机器智能。•人工智能的五个基本问题(1)知识与概念化是否是人工智能的核心？(2)认知能力能否与载体分开来研究？(3)认知的轨迹是否可用类自然语言来描述？(4)学习能力能否与认知分开来研究？(5)所有的认知是否有一种统一的结构？•学科交叉与生命科学、认知科学、物理学等众多学科高度交叉，共同研究智能行为的基本理论和实现技术。•三大学派符号主义（Symbolism）、连接主义(Connectionism)、行为主义（Behaviorism）——从不同侧面模拟人的智能和智能行为。符号主义•代表人物1956年，美国Dartmouth会议，几个年轻的美国学者McCarthy、Simon、Minsky、Newell等首次提出人工智能的术语•基本思想（1）认知的本质就是计算，可称为认知可计算主义—与图灵机理论一脉相承（2）思维的基本单元是符号，智能的核心是利用知识以及知识推理进行问题求解（3）智能活动的基础是物理符号运算，人脑和电脑都是物理符号系统（4）人的智能可以通过建了基于符号逻辑的智能理论体系模拟（5）理论基础是符号数学、谓词演算和归结原理符号主义-续•智能表示（1）1959年McCarthy开发了著名的LISP语言（LIStProcessingLanguage，表处理语言），基于函数的语言，通过符号（不是数值）运算进行推理，也是逻辑程序设计语言（LogicProgramming）（2）1972年PROLOG语言（PROgrammingLOGic）问世，被称为演绎推理机，接口丰富，非常适合于专家系统开发，曾有人试图发明PROLOG机器，以模拟人的智能，但未获成功•知识工程与专家系统—典型代表（1）产生式规则表示知识（2）产生式规则系统将领域专家的知识进行整理、存储构建知识库（3）专家系统运用知识库进行推理、问题求解等智能活动•推理方法知识表示与推理、归纳推理、基于事例的推理等连接主义•代表人物（1）1943年生理学家McCulloch和Pitts提出神经元的数学模型，神经元模型结合成多层结构成为神经网络（2）1959年，Rosenblatt提出感知机模型（Perceptron)，具有输入层、中间联系层和效验输出层的三层结构（3）1982年，Hopfield提出全互连的神经网络模型，成功求解TSP问题，掀起神经网络研究高潮，对符号主义也产生了巨大冲击（4）1987年，戴维.努梅尔哈特和杰弗里.欣顿提出误差反向传播（Back-Propgation）神经网络学习算法•基本思想（1）人类认知活动主要基于大脑神经元的活动，人类思维的基本单元是神经元而不是符号，智能是互连神经元竞争与协作的结果（2）模拟人的智能要依靠仿生学，特别是模拟人脑，建立脑模型（3）电脑模拟人脑应着重于结构模拟，即人的生理神经网络结构，功能、结构和行为密切相关，不同的结构表现出不同的功能行为（4）分布式信息存储和大规模并行处理，自适应和自组织特性，学习和容错能力（5）理论基础是神经生理学与脑科学神经元与神经网络连接主义-续•智能表示（1）神经元状态值、连接权值、阈值和激励函数决定输出值--隐式表示方法（2）通过学习算法修正神经元之间的连接权值，达到更精确的知识表示，学习算法包括有导师和无导师学习算法两类•模式识别—典型代表（1）建立样本库（2）特征提取与特征库（3）学习算法进行神经网络训练，模式的聚类、分类和识别•学习算法提高学习和训练速度，保证全局收敛，网络结构设计和自适应调整行为主义•代表人物1988年，Brooks等人提出无需知识、知识表示和推理的智能系统，智能来自于系统的“感知-动作”模式，基于这样的思路，他发明了六足行走机器，一个模拟昆虫行为的控制器•基本思想（1）智能是一个系统行为，智能行为可以通过与周围环境的的交互作用表现出来（2）智能的基础是“感知-动作”模式，类似于心理学的“刺激-反应”，它也决定系统的结构和参量（3）系统的智能行为决定于系统的结构和参量（4）自组织、自学习、自适应是智能系统得基本特征（5）理论基础是控制论、系统科学和心理学行为主义-续•智能表示（1）系统模型、模型结构和参量--隐式表示方法（2）学习就是一次又一次地从外界接受条件和结果，即“感知-动作”，积累知识的过程（3）自学习是指：当一个新的输入条件决定后，能根据经验的积累，给出相应结果的过程，或者当一个新的条件和结果给出后，能够调整结构和参量的过程•智能控制与智能机器人—典型代表（1）建立系统模型（2）行为（感知-动作）模拟，积累知识，形成基本控制策略（3）学习与自学习进行自适应调整与优化，形成新的控制策略•学习算法自适应、自学习、自组织、自寻优等智能化方法面临困境•源于复杂性知识的复杂性，知识表示的组合爆炸不完整知识的表达问题推理的时空爆炸性神经网络结构复杂学习、训练低效难以全局收敛能力限制复杂行为模拟不能用精确的数学模型描述的问题信息时代的呼唤•工业时代能量资源-创造动力的工具-获得能量•物理学、化学创造动力工具的理论基础•信息时代信息资源-创造智能的工具-获得智能•智能计算理论创造智能工具的理论基础智能计算-回归自然•自下而上的研究思路传统人工智能研究思路是自上而下，现代智能计算方法强调通过计算实现生物内在的智能行为，也称为计算智能•从简单到复杂的演化进程智能的获得不是一蹴而就，是渐进式的积累过程，简单中孕育复杂，平凡中蕴含智慧•在传统学科中寻找算法如生命科学（遗传算法）、物理学（模拟退火算法）和化学（DNA计算）等•从自然与社会系统中获得灵感如蚂蚁算法、禁忌搜索和粒子群优化方法，模糊计算及模糊系统、粗造集及其系统相互关系计算智能与人工智能的界限并非十分明显，1992年Bezdek给出了一个有趣的关系图，其中NN—神经网络，PR—模式识别，I—智能•A－Artificial，表示人工的（非生物的），即人造的•B－Biological，表示物理的＋化学的＋（？？）＝生物的•C－Computational，表示数学＋计算机ABC的关系图计算智能是一种智力方式的低层认知，传统人工智能是中层认知，中层系统含有知识，当一个智能计算系统以非数值方式加上知识值，则为人工智能系统自然计算•自然计算的含义学习、运用自然规律，模拟自然系统乃至社会系统的演变过程的智能计算方法，借鉴自然科学学科的原理和理论进行问题的求解方法•自然计算方法演化计算、蚁群算法、粒子群优化方法、人工免疫系统、模糊计算遗传算法•遗传算法（GeneticAlgorithm）模拟达尔文的遗传选择和自然淘汰的生物进化过程•1975年首先由Holland提出用于自然和人工系统的自适应行为研究(AdaptationinNaturalandArtificialSystems)•组成：个体与群体、适应值函数、遗传操作、终止条件•特点：隐含并行性、过程性、非确定性、群体性、内在学习、统计性、稳健性、整体优化免疫系统人体免疫系统是一个高度进化、复杂的生理机制免疫系统通过高度复杂的网络结构来识别和排除抗原性异物，维护体内环境的稳定免疫系统具有识别能力、学习和免疫记忆功能，以及自适应调节机制等特性蚁群算法概述•受蚂蚁觅食行为的的启发，90年代Dorigo提出蚁群优化算法(AntColonyOptimization，ACO)求解TSP问题•设计虚拟的“蚂蚁”，摸索不同路线，并留下会随时间挥发的虚拟“信息素”•根据“信息素较浓，则路径更短”的原则，每只蚂蚁每次随机选择要走的路径，但倾向于信息素比较浓的路径•算法利用了正反馈机制，使得较短的路径能够有较大的机会得到选择•ACO已成功用于解决其他组合优化问题图的着色(GraphColoring)问题最短超串(ShortestCommonSupersequence)问题网络路由问题蚁群觅食原理ABCD蚁穴食物蚂蚁从蚁穴出发觅食，可沿AC找到食物，也可沿ABC找到，如右图。每个蚂蚁找到食物后沿原路返回，并在路上留下外激素。AC路径短，AC上留下了两次外激素，而ABC路径长，沿CBA返回的蚂蚁，还只到了D处，故AD上只留下一次外激素。后续离穴觅食者选择外激素浓度大的AC路径，于是AC上外激素浓度将越来越大，最后，绝大多数蚂蚁沿较短的AC路径觅食。蚁群算法初始化，设置时间计数器，循环计数器，为每条边设置信息素浓度的初始值初始化tabu表tabu表满？按概率将某一个蚂蚁从第i个城市移动到第j个城市，并将j插入其tabu表封闭回路，分别计算每个蚂蚁走过的总长度，记录最短路径，计算信息素浓度改变量达到最大循环次数或不发展状态？输出结果粒子群优化概述•粒子群优化算法(ParticleSwarmOptimization，PSO)1995年由Eberhart和Kennedy提出，源于模拟鸟群捕食行为•一群鸟在随机搜索区域里的一块食物，所有的鸟都不知道食物在那里，但知道当前的位置离食物还有多远•那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前离食物最近的鸟的周围区域•PSO中，优化问题的可行解就是搜索空间中的一只鸟，称之为“粒子”，一群鸟称为粒子群，所有的粒子都有一个由优化的函数决定的适应值（fitnessvalue)•每个粒子还有一个速度决定其飞行的方向和距离，目的是追随当前的最优粒子在解空间中搜索•粒子通过跟踪两个“极值”来更新自己，第一个就是粒子自己当前找到的最优解，这个解叫做个体极值pBest，另