人工智能导论全套课件

人工智能导论,2,第1章绪论,人工智能导论,3,第1章绪论,1956年正式提出人工智能（artificialintelligence,AI）这个术语并把它作为一门新兴科学的名称。,4,第1章绪论,1.1人工智能的基本概念1.2人工智能的发展简史1.3人工智能研究的基本内容1.4人工智能的主要研究领域,5,第1章绪论,1.1人工智能的基本概念1.2人工智能的发展简史1.3人工智能研究的基本内容1.4人工智能的主要研究领域,6,1.1.1智能的概念,自然界四大奥秘：物质的本质、宇宙的起源、生命的本质、智能的发生。对智能还没有确切的定义，主要流派有：（1）思维理论：智能的核心是思维（2）知识阈值理论：智能取决于知识的数量及一般化程度（3）进化理论：用控制取代知识的表示智能是知识与智力的总和,知识是一切智能行为的基础,获取知识并应用知识求解问题的能力,7,感知能力：通过视觉、听觉、触觉、嗅觉等感觉器官感知外部世界的能力。80%以上信息通过视觉得到，10%信息通过听觉得到。,1.1.2智能的特征,存储由感知器官感知到的外部信息以及由思维所产生的知识,对记忆的信息进行处理,2.记忆与思维能力,8,（1）逻辑思维（抽象思维）依靠逻辑进行思维。思维过程是串行的。容易形式化。思维过程具有严密性、可靠性。,1.1.2智能的特征,（2）形象思维（直感思维）依据直觉。思维过程是并行协同式的。形式化困难。在信息变形或缺少的情况下仍有可能得到比较满意的结果。,9,4.行为能力（表达能力）,1.1.2智能的特征,（3）顿悟思维（灵感思维）不定期的突发性。非线性的独创性及模糊性。穿插于形象思维与逻辑思维之中。,人们的感知能力：用于信息的输入。行为能力：信息的输出。,10,人工智能：用人工的方法在机器（计算机）上实现的智能；或者说是人们使机器具有类似于人的智能。,1.1.3人工智能,人工智能学科：一门研究如何构造智能机器（智能计算机）或智能系统，使它能模拟、延伸、扩展人类智能的学科。图灵测试：1950年图灵发表的计算机与智能中设计了一个测试，用以说明人工智能的概念。,11,第1章绪论,1.1人工智能的基本概念1.2人工智能的发展简史1.3人工智能研究的基本内容1.4人工智能的主要研究领域,12,1.2人工智能的发展简史,1.2.1孕育（1956年之前）公元前，亚里斯多德（Aristotle）：三段论培根（F.Bacon）：归纳法莱布尼茨（G.W.Leibnitz）：万能符号、推理计算布尔（G.Boole）：用符号语言描述思维活动的基本推理法则1936年，图灵：图灵机1943年，麦克洛奇（W.McCulloch）、匹兹(W.Pitts)：MP模型,13,1.2人工智能的发展简史,1.2.1孕育（1956年之前）美国爱荷华州立大学的阿塔纳索夫教授和他的研究生贝瑞在1937年至1941年间开发的世界上第一台电子计算机“阿塔纳索夫贝瑞计算机（Atanasoff-BerryComputer，ABC）”为人工智能的研究奠定了物质基础。,14,1.2.2形成（1956年1969年）,1956年夏，当时美国达特茅斯大学数学助教、现任斯坦福大学教授麦卡锡和哈佛大学数学和神经学家、现任MIT教授明斯基、IBM公司信息研究中心负责人洛切斯特、贝尔实验室信息部数学研究员香农共同发起，邀请普林斯顿大学莫尔和IBM公司塞缪尔、MIT的塞尔夫里奇和索罗莫夫以及兰德公司和卡内基梅隆大学的纽厄尔、西蒙等10名年轻学者在达特莫斯大学召开了两个月的学术研讨会，讨论机器智能问题。会上经麦卡锡提议正式采用“人工智能”这一术语，标志着人工智能学科正式诞生。麦卡锡因而被称为人工智能之父。此后，美国形成了多个人工智能研究组织，如纽厄尔和西蒙的CarnegieRAND协作组，明斯基和麦卡锡的MIT研究组，塞缪尔的IBM工程研究组等。,15,1.2.2形成（1956年1969年）,1956年以后，人工智能的研究在机器学习、定理证明、模式识别、问题求解、专家系统及人工智能语言等方面都取得了许多引人瞩目的成就。1969年，成立了国际人工智能联合会议（InternationalJointConferencesonArtificialIntelligence，IJCAI）。1970年，创刊了国际性的人工智能杂志（ArtificialIntelligence）。,16,1.2.3发展（1970年）,20世纪60年代末，人工智能研究遇到困难，如机器翻译。1966年美国顾问委员会的报告裁定：还不存在通用的科学文本机器翻译，也没有很近的实现前景。英国、美国中断了大部分机器翻译项目的资助。1977年，费根鲍姆在第五届国际人工智能联合会议上提出了“知识工程”概念，推动了知识为中心的研究。1981年，日本宣布第五代计算机发展计划，并在1991年展出了研制的PSI3智能工作站和由PSI3构成的模型机系统。我国自1978年开始把“智能模拟”作为国家科学技术发展规划的主要研究课题。1981年成立了中国人工智能学会。现在，人工智能已经成为计算机、航空航天、军事装备、工业等众多领域的关键技术。,17,第1章绪论,1.1人工智能的基本概念1.2人工智能的发展简史1.3人工智能研究的基本内容1.4人工智能的主要研究领域,18,1.3人工智能研究的基本内容,知识表示知识表示：将人类知识形式化或者模型化。知识表示方法：符号表示法、连接机制表示法。,符号表示法：用各种包含具体含义的符号，以各种不同的方式和顺序组合起来表示知识的一类方法。例如，一阶谓词逻辑、产生式等。连接机制表示法：把各种物理对象以不同的方式及顺序连接起来，并在其间互相传递及加工各种包含具体意义的信息，以此来表示相关的概念及知识。例如，神经网络等。,19,2.机器感知,2.机器感知机器感知：使机器（计算机）具有类似于人的感知能力。以机器视觉(machinevision)与机器听觉为主。,1.3人工智能研究的基本内容,3.机器思维机器思维：对通过感知得来的外部信息及机器内部的各种工作信息进行有目的的处理。,20,2.机器感知,4.机器学习机器学习（machinelearning）：研究如何使计算机具有类似于人的学习能力，使它能通过学习自动地获取知识。1957年，Rosenblatt研制成功了感知机。,1.3人工智能研究的基本内容,5.机器行为机器行为：计算机的表达能力，即“说”、“写”、“画”等能力。,21,第1章绪论,1.1人工智能的基本概念1.2人工智能的发展简史1.3人工智能研究的基本内容1.4人工智能的主要研究领域,22,1.4人工智能的主要研究领域,1.自动定理证明,定理证明的实质是证明由前提P得到结论Q的永真性。1958年，王浩证明了有关命题演算的全部定理（220条）、谓词演算中150条定理的85%。1965年鲁宾逊（Robinson）提出了归结原理，使机器定理证明成为现实。我国著名数学家、中国科学院吴文俊院士把几何代数化，建立了一套机器证明方法，被称为“吴方法”。,23,1.4人工智能的主要研究领域,2.博弈下棋、打牌、战争等一类竞争性的智能活动。1956年，塞缪尔研制出跳棋程序。1991年8月，IBM公司研制的DeepThought2计算机系统与澳大利亚象棋冠军约翰森（D.Johansen）举行了一场人机对抗赛，以1：1平局告终。1996年2月10日至17日，IBM公司的“深蓝”计算机系统与卡斯帕罗夫进行了六局比赛，以3.5比2.5的总比分赢得这场世人瞩目的“人机大战”的胜利。,24,1.4人工智能的主要研究领域,2.博弈2004年6月8日，中国首届国际象棋人机对弈开战。国际象棋特级大师诸宸与“紫光之星”笔记本电脑对阵。诸宸在最后关头被电脑抓住破绽，先负一局。4天后诸宸灵活变阵，但再负一局。,25,2007年台北国际发明暨技术交易展览上，第三代智能机器人DOC现场表演下棋。,1.4人工智能的主要研究领域,26,1.4人工智能的主要研究领域,模式识别（patternrecognition）：研究对象描述和分类方法的学科。分析和识别的模式可以是信号、图象或者普通数据。文字识别：邮政编码、车牌识别、汉字识别。人脸识别：反恐、商业。物体识别：导弹、机器人。,3.模式识别,27,1.4人工智能的主要研究领域,4.机器视觉,机器视觉(machinevision)或计算机视觉(computervision)是用机器代替人眼睛进行测量和判断。机器视觉系统是指通过图像摄取装置将被摄取的目标转换成图像信号，传送给专用的图像处理系统，根据像素分布和宽度、颜色等信息，转换成数字信号，抽取目标的特征，根据判别结果控制现场的设备动作。机器视觉应用在半导体及电子、汽车、冶金、制药、食品饮料、印刷、包装、零配件装配及制造质量检测等。,28,1.4人工智能的主要研究领域,5.自然语言理解研究如何让计算机理解人类自然语言，包括回答问题、生成摘要、翻译等。1957年，在苏联人造卫星成功发射的刺激下,美国国家研究会大力支持对俄科技论文的计算机翻译。人们最初以为机器翻译只要将双向词典及一些词法知识放进计算机就行了。后来发现有时会出现十分荒谬的错误。,“Thespiritiswillingbutthefleshisweak”心有余而力不足。俄语“Thewineisgoodbutthemeatisspoiled”酒是好的但肉变质了。,29,1.4人工智能的主要研究领域,6.智能信息检索,智能信息检索系统的功能：(1)能理解自然语言。(2)具有推理能力。(3)系统拥有一定的常识性知识。,7.数据挖掘与知识发现,数据挖掘的目的是从数据库中找出有意义的模式(一组规则、聚类、决策树、依赖网络或其他方式表示的知识)。数据挖掘过程：数据预处理、建模、模型评估及模型应用。,30,1.4人工智能的主要研究领域,8.专家系统,专家系统模拟人类专家求解问题的思维过程求解领域内的各种问题，其水平可以达到甚至超过人类专家的水平。1965年费根鲍姆研究小组开始研制第一个专家系统分析化合物分子结构的DENDRAL，1968年完成并投入使用。1971年MIT开发成功求解一些数学问题的MYCSYMA专家系统。拉特格尔大学开发的清光眼诊断与治疗的专家系统CASNET。1972年斯坦福大学肖特里菲等人开始研制用于诊断和治疗感染性疾病的专家系统MYCIN。1976年斯坦福研究所开始开发探矿专家系统PROSPECTOR，1980年首次实地分析华盛顿某山区地质资料，发现了一个钼矿。1981年斯坦福大学研制成功专家系统AM，能模拟人类进行概括、抽象和归纳推理，发现某些数论的概念和定理。,31,1.4人工智能的主要研究领域,9.自动程序设计,程序综合：用户只需要告诉计算机要“做什么”，无须说明“怎么做”，计算机就可自动实现程序的设计。程序正确性的验证：研究出一套理论和方法，通过运用这套理论和方法就可以证明程序的正确性。,32,1.4人工智能的主要研究领域,10.机器人,20世纪60年代初，研制出尤尼梅特和沃莎特兰两种机器人。机器人发展：程序控制机器人（第一代）、自适应机器人（第二代）、智能机器人（现代）。,33,1.4人工智能的主要研究领域,美国军用机器人携带火箭,34,美军排爆机器人,1.4人工智能的主要研究领域,35,美军投入伊拉克战场的可携带侦察机器人,1.4人工智能的主要研究领域,36,1.4人工智能的主要研究领域,11.组合优化问题,组合优化问题：旅行商问题、生产计划与调度、物流中的车辆调度、智能交通、通信中的路由调度、计算机网络信息调度等NP完全问题：用目前知道的最好的方法求解，问题求解需要花费的时间是随问题规模增大以指数关系增长。,12.人工神经网络,人工神经网络：一个用大量简单处理单元经广泛连接而组成的人工网络，用来模拟大脑神经系统的结构和功能。,37,1.4人工智能的主要研究领域,分布式人工智能系统以鲁棒性作为控制系统质量的标准，并具有互操作性，即不同的异构系统在快速变化的环境中，具有交换信息和协同工作的能力。分布式问题求解：把一个具体的求解问题划分为多个相互合作和知识共享的模块或者结点。多智能体系统：研究各智能体之间行为的协调。,13.分布式人工智能与多智能体,38,1.4人工智能的主要研究领域,国际知名美籍华裔科学家傅京孙（KS.Fu）在1965年首先把人工智能的启发式推理规则用于学习控制系统。智能控制的两个显著特点：第一，智能控制是同时具有知识表示的非数学广义世界模型和传统数学模型混合表示的控制过程。第二，智能控制的核心在高层控制，其任务在于实际环境或过程进行组织，即决策与规划，以实现广义问题求解。智能控制的基本类型：（1）专家智能控制（2）模糊控制（3）神经网络控制,14.智能控制,39,1.4人工智能的主要研究领域,智能仿真是将AI引入仿真领域，建立智能仿真系统。仿真是对动态模型的实验，即行为产生器在规定的实验条件下驱动模型，从而产生模型行为。仿真是在描述性知识、目的性知识及处理知识的基础上产生结论性知识。利用AI对整个仿真过程（建模、实验运行及结果分析）进行指导，在仿真模型中引进知识表示，改善仿真模型的描述能力，为研究面向目标的建模语言打下基础，提高仿真工具面向用户、面向问题的能力，使仿真更有效地用于决策，更好地用于分析、设计及评价知识库系统。,15.智能仿真,40,1.4人工智能的主要研究领域,智能CAD（简称ICAD）就是把人工智能技术引入计算机辅助设计领域，建立智能CAD系统。AI几乎可以应用到CAD技术的各个方面。从目前发展的趋势来看，至少有下述四个方面：（1）设计自动化。（2）智能交互。（3）智能图形学。（4）自动数据采集。,16.智能CAD,41,1.4人工智能的主要研究领域,智能CAI就是把AI引入计算机辅助教学领域。ICAI系统一般分成专门知识、教导策略和学生模型和自然语言的智能接口。ICAI应具备下列智能特征：（1）自动生成各种问题与练习。（2）根据学生的学习情况自动选择与调整教学内容与进度。（3）在理解教学内容的基础上自动解决问题生成解答。（4）具有自然语言生成和理解能力。（5）对教学内容有理解咨询能力。（6）能诊断学生错误，分析原因并采取纠正措施。（7）能评价学生的学习行为。（8）能不断地在教学中改善教学策略。,17.智能CAI,42,1.4人工智能的主要研究领域,智能管理就是把人工智能技术引入管理领域，建立智能管理系统，研究如何提高计算机管理系统的智能水平，以及智能管理系统的设计理论、方法与实现技术。智能决策就是把人工智能技术引入决策过程，建立智能决策支持系统。智能决策支持系统是由传统决策支持系统再加上相应的智能部件就构成了智能决策支持系统。智能部件可以是专家系统模式、知识库模式等。,18.智能管理与智能决策,43,1.4人工智能的主要研究领域,多媒体计算机系统就是能综合处理文字、图形、图像和声音等多种媒体信息的计算机系统。智能多媒体就是将人工智能技术引入多媒体系统，使其功能和性能得到进一步发展和提高。多媒体技术与人工智能所研究的机器感知、机器理解等技术不谋而合。人工智能的计算机视听觉、语音识别与理解、语音对译、信息智能压缩等技术运用于多媒体系统，将会使现在的多媒体系统产生质的飞跃。,19.智能多媒体系统,44,1.4人工智能的主要研究领域,智能操作系统的基本模型：以智能机为基础，能支撑外层的AI应用程序，实现多用户的知识处理和并行推理。智能操作系统三大特点：并行性：支持多用户、多进程，同时进行逻辑推理等;分布性：把计算机硬件和软件资源分散而又有联系地组织起来，能支持局域网和远程网处理;智能性：一是操作系统处理的是知识对象，具有并行推理功能，支持智能应用程序运行;二是操作系统的绝大部分程序使用AI程序编制，充分利用硬件并行推理功能;三是具有较高智能程序的自动管理维护功能，如故障的监控分析等，帮助维护人员决策。,20.智能操作系统,45,1.4人工智能的主要研究领域,智能计算机系统就是人们正在研制的新一代计算机系统。智能计算机系统从基本元件到体系结构，从处理对象到编程语言，从使用方法到应用范围，同当前的诺依曼型计算机相比，都有质的飞跃和提高，它将全面支持智能应用开发，且自身就具有智能。,21.智能计算机系统,46,1.4人工智能的主要研究领域,智能通信就是把人工智能技术引入通信领域，建立智能通信系统。智能通信就是在通信系统的各个层次和环节上实现智能化。例如在通信网的构建、网管与网控、转接、信息传输与转换等环节，都可实现智能化。这样，网络就可运行在最佳状态，具有自适应、自组织、自学习、自修复等功能。,22.智能通信,47,1.4人工智能的主要研究领域,智能网络系统就是将人工智能技术引入计算机网络系统。如在网络构建、网络管理与控制、信息检索与转换、人机接口等环节，运用AI的技术与成果。AI的专家系统、模糊技术和神经网络技术可用于网络的连接接纳控制、业务量管制、业务量预测、资源动态分配、业务流量控制、动态路由选择、动态缓冲资源调度等许多方面。,23.智能网络系统,48,1.4人工智能的主要研究领域,人工生命是以计算机为研究工具，模拟自然界的生命现象，生成表现自然生命系统行为特点的仿真系统。主要研究进化的模式和方式、人工仿生学、进化博弈、分子进化、免疫系统进化、学习等；具有自治性、智能性、反应性、预动性和社会性的智能主体的形式化模型、通信方式、协作策略；研究生物感悟的机器人、自治和自适应机器人、进化机器人、人工脑。,24.人工生命,第2章知识表示,50,第2章知识表示,人类的智能活动主要是获得并运用知识。知识是智能的基础。为了使计算机具有智能，能模拟人类的智能行为，就必须使它具有知识。但知识需要用适当的模式表示出来才能存储到计算机中去，因此，知识的表示成为人工智能中一个十分重要的研究课题。本章将首先介绍知识与知识表示的概念，然后介绍一阶谓词逻辑、产生式、框架、语义网络等当前人工智能中应用比较广泛的知识表示方法，为后面介绍推理方法、专家系统等奠定基础。,51,第2章知识表示,2.1知识与知识表示的概念2.2一阶谓词逻辑表示法2.3产生式表示法2.4框架表示法,52,第2章知识表示,2.1知识与知识表示的概念2.2一阶谓词逻辑表示法2.3产生式表示法2.4框架表示法,53,2.1.1知识的概念,知识：在长期的生活及社会实践中、在科学研究及实验中积累起来的对客观世界的认识与经验。知识：把有关信息关联在一起所形成的信息结构。知识反映了客观世界中事物之间的关系，不同事物或者相同事物间的不同关系形成了不同的知识。,信息关联形式：“如果，则”如果大雁向南飞，则冬天就要来临了。,规则,事实,例如：“雪是白色的”。“如果头痛且流涕，则有可能患了感冒”。,54,2.1.2知识的特性,1.相对正确性任何知识都是在一定的条件及环境下产生的，在这种条件及环境下才是正确的。,1+1=2（十进制）1+1=10(二进制）,55,2.1.2知识的特性,不确定性,随机性引起的不确定性模糊性引起的不确定性经验引起的不确定性不完全性引起的不确定性,知识状态：“真”“假”“真”与“假”之间的中间状态,“如果头痛且流涕，则有可能患了感冒”,小李很高,56,2.1.2知识的特性,可表示性与可利用性知识的可表示性:知识可以用适当形式表示出来，如用语言、文字、图形、神经网络等。知识的可利用性:知识可以被利用。,57,2.1.3知识的表示,知识表示（knowledgerepresentation）：将人类知识形式化或者模型化。知识表示是对知识的一种描述，或者说是一组约定，一种计算机可以接受的用于描述知识的数据结构。选择知识表示方法的原则：,（1）充分表示领域知识。（2）有利于对知识的利用。（3）便于对知识的组织、维护与管理。（4）便于理解与实现。,58,第2章知识表示,2.1知识与知识表示的概念2.2一阶谓词逻辑表示法2.3产生式表示法2.4框架表示法,59,2.2一阶谓词逻辑表示法,60,2.2一阶谓词逻辑表示法,2.2.1命题2.2.2谓词2.2.3谓词公式2.2.4谓词公式的性质2.2.5一阶谓词逻辑知识表示方法2.2.6一阶谓词逻辑表示法的特点,61,命题逻辑：研究命题及命题之间关系的符号逻辑系统。命题逻辑表示法：无法把它所描述的事物的结构及逻辑特征反映出来，也不能把不同事物间的共同特征表述出来。,2.2.1命题,命题（proposition）：一个非真即假的陈述句。若命题的意义为真，称它的真值为真，记为T。若命题的意义为假，称它的真值为假，记为F。一个命题可在一种条件下为真，在另一种条件下为假。,例如：33”：二元谓词Greater(5,3)“Smith作为一个工程师为IBM工作”：三元谓词Works(Smith,IBM,engineer),（1）个体是常量：一个或者一组指定的个体。,63,2.2.2谓词,（2）个体是变元（变量）：没有指定的一个或者一组个体。,“小李的父亲是教师”：Teacher(father(Li),（3）个体是函数：一个个体到另一个个体的映射。,“x0，证据的出现越是支持H为真，就使CF（H，E)的值越大。反之，CF（H，E）0，证据的出现越是支持H为假，CF（H，E）的值就越小。若证据的出现与否与H无关，则CF（H，E）=0。,1.知识不确定性的表示,4.2可信度方法,191,证据E的可信度取值范围：-1，1。对于初始证据，若所有观察S能肯定它为真，则CF(E)=1。若肯定它为假，则CF(E)=1。若以某种程度为真，则0CF(E)1。若以某种程度为假，则1CF(E)动作电位的阈值神经冲动抑制状态：细胞膜电位0,wij=wji,则；当且仅当,524,8.4.3随机神经网络,Hopfield神经网络中，神经元状态为1是根据其输入是否大于阈值确定的，是确定性的。随机神经网络中，神经元状态为1是随机的，服从一定的概率分布。例如，服从玻尔兹曼(Boltzmann)、高斯(Gaussian)、柯西(Cauchy)分布等，从而构成玻尔兹曼机、高斯机、柯西机等随机机。,525,8.4.3随机神经网络,1.Boltzmann机1985年，加拿大多伦多大学教授欣顿(Hinton)等人借助统计物理学的概念和方法，提出了Boltzmann机神经网络模型。Boltzmann机是离散Hopfield神经网络的一种变型，通过对离散Hopfield神经网络加以扰动，使其以概率的形式表达，而网络的模型方程不变，只是输出值类似于Boltzmann分布以概率分布取值。Boltzmann机是按Boltzmann概率分布动作的神经网络。,526,8.4.3随机神经网络,1.Boltzmann机（续）离散Hopfield神经网络的输出：Boltzman机的内部状态：神经元输出值为0和1时的概率：,527,8.4.3随机神经网络,1.Boltzmann机（续）Boltzmann的能量函数：,神经元状态转换时网络能量的变化：,神经元改变为状态“1”的概率：,),exp(,1,1,T,E,p,i,i,D,-,+,=,528,2.高斯机,8.4.3随机神经网络,:均值为0的高斯随机变量（白噪声），其方差为,3.柯西机,:柯西随机变量（有色噪声）,529,8.5Hopfield神经网络的应用,8.5.1Hopfield神经网络在联想记忆中的应用8.5.2Hopfield神经网络优化方法,530,8.5.1Hopfield神经网络在联想记忆中的应用,531,例8.2,传感器输出：外形，质地，重量T,8.5.1Hopfield神经网络在联想记忆中的应用,532,例8.2,样本:,具体怎样实现联想记忆？,8.5.1Hopfield神经网络在联想记忆中的应用,533,样本:,（1）设计DHNN结构,3神经元的DHNN结构图,注：,8.5.1Hopfield神经网络在联想记忆中的应用,534,样本:，,连接权：,（2）设计连接权矩阵,8.5.1Hopfield神经网络在联想记忆中的应用,535,样本:，,连接权：,T,0,1,0,),2,(,=,x,（2）设计连接权矩阵,8.5.1Hopfield神经网络在联想记忆中的应用,536,（2）设计连接权矩阵,8.5.1Hopfield神经网络在联想记忆中的应用,537,输入：1，1，1T,输出?,（3）测试,8.5.1Hopfield神经网络在联想记忆中的应用,538,（3）测试,调整次序：,初始状态：,测试用例：,样本：,8.5.1Hopfield神经网络在联想记忆中的应用,539,调整次序：213,k=0,8.5.1Hopfield神经网络在联想记忆中的应用,540,k=1,调整次序：213,8.5.1Hopfield神经网络在联想记忆中的应用,541,k=2,调整次序：213,8.5.1Hopfield神经网络在联想记忆中的应用,542,k=2,k=3,k=0,k=1,样本：,调整次序：,213,213,213,213,8.5.1Hopfield神经网络在联想记忆中的应用,543,例8.2,输入：1，1，1T,输出：1，0，1T,8.5.1Hopfield神经网络在联想记忆中的应用,544,连续Hopfiled神经网络求解约束优化问题的基本思路：,8.5.2Hopfield神经网络优化方法,1985年，霍普菲尔德和塔克（D.W.Tank）应用连续Hopfield神经网络求解旅行商问题（travelingsalesmanproblem，TSP）获得成功。,545,8.5.2Hopfield神经网络优化方法,用神经网络方法求解优化问题的一般步骤：（1）将优化问题的每一个可行解用换位矩阵表示。（2）将换位矩阵与由n个神经元构成的神经网络相对应：每一个可行解的换位矩阵的各元素与相应的神经元稳态输出相对应。（3）构造能量函数，使其最小值对应于优化问题的最优解，并满足约束条件。（4）用罚函数法构造目标函数，与Hopfield神经网络的计算能量函数表达式相等，确定各连接权和偏置参数。（5）给定网络初始状态和网络参数等，使网络按动态方程运行，直到稳定状态，并将它解释为优化问题的解。,546,应用举例：Hopfield神经网络优化方法求解TSP。,1985年，霍普菲尔德和塔克（D.W.Tank）应用连续Hopfield神经网络求解旅行商问题获得成功。,旅行商问题（travelingsalesmanproblem，TSP）：有n个城市，城市间的距离或旅行成本已知，求合理的路线使每个城市都访问一次，且总路径（或者总成本）为最短。,8.5.2Hopfield神经网络优化方法,547,5个城市的TSP：,神经元数目：25,8.5.2Hopfield神经网络优化方法,548,TSP的描述：,用罚函数法，写出优化问题的目标函数：,8.5.2Hopfield神经网络优化方法,549,Hopfield神经网络能量函数：,8.5.2Hopfield神经网络优化方法,令E1与目标函数J相等，确定神经网络的连接权值和偏置电流：,550,神经网络的动态方程：,8.5.2Hopfield神经网络优化方法,551,选择合适的A、B、C、D和网络的初始状态，按网络动态方程演化直到收敛。,8.5.2Hopfield神经网络优化方法,552,神经网络优化计算目前存在的问题：（1）解的不稳定性。（2）参数难以确定。（3）能量函数存在大量局部极小值，难以保证最优解。,8.5.2Hopfield神经网络优化方法,第9章智能体与多智能体系统,554,第9章智能体与多智能体系统,随着计算机网络和信息技术的发展，智能体技术得到广泛应用。多智能不仅具备自身的问题求解能力和行为目标，而且能够相互协作，来达到共同的整体目标。因此，能够解决现实中广泛存在的复杂的大规模问题。本章在介绍智能体与多智能体系统概念的基础上，简要介绍多智能体系统中的通信、协作、协调等基本技术。,555,第9章智能体与多智能体系统,9.1智能体的概念与结构9.2多智能体系统的概念与结构9.3多智能体系统的通信9.4多智能体系统的协调9.5多智能体系统的协作9.6多智能体系统的协商,556,9.1智能体的概念与结构9.2多智能体系统的概念与结构9.3多智能体系统的通信9.4多智能体系统的协调9.5多智能体系统的协作9.6多智能体系统的协商,第9章智能体与多智能体系统,557,9.1智能体的概念与结构,9.1.1智能体的概念,Agent可以看做是一个程序或者一个实体，它嵌入在环境中，通过传感器(sensors)感知环境，通过效应器（effectors）自治地作用于环境并满足设计要求。,Agent与环境的交互作用,558,9.1.2智能体的特性,（1）自主性：Agent具有独立的局部于自身的知识和知识处理方法，能够根据其内部状态和感知到的环境信息自主决定和控制自身的状态和行为。（2）反应性：Agent能够感知、影响环境。Agent的行为是为了实现自身内在的目标，在某些情况下，Agent能够采取主动的行为，改变周围的环境，以实现自身的目标。（3）社会性：很多Agent同时存在，形成多智能体系统，模拟社会性的群体。Agent具有和外部环境中其它Agent相互协作的能力，在遇到冲突时能够通过协商来解决问题。（4）进化性：Agent应该能够在交互过程中逐步适应环境，自主学习，自主进化。,9.1智能体的概念与结构,559,9.1.3智能体的结构,Agent结构接受传感器的输入，然后运行Agent程序，并把执行的结果传送到效应器进行动作。Agent系统的结构直接影响到系统的性能。Agent、体系结构和程序之间的关系：Agent=体系结构+程序,9.1智能体的概念与结构,560,9.1.3智能体的结构,Agent结构需要解决以下问题：（1）Agent由哪些模块组成；（2）这些模块之间如何交互信息；（3）Agent感知的信息如何影响它的行为和内部状态；（4）如何将这些模块用软件或硬件的方式组合起来形成一个有机的整体。单个Agent的结构按属性可以分为：反应式体系结构、慎思式体系结构和混合式体系结构。,9.1智能体的概念与结构,561,9.1.4反应式Agent反应式Agent是一种具备对当时处境的实时反应能力的Agent。,9.1智能体的概念与结构,562,9.1.5慎思式Agent慎思式Agent是一种基于知识的系统，包括环境描述和丰富的智能行为的逻辑推理能力。,9.1智能体的概念与结构,563,9.1.6复合式Agent复合式Agent是在一个Agent内组合多种相对独立和并行执行的智能形态，其结构包括感知、动作、反应、建模、规划、通信和决策等模块。,9.1智能体的概念与结构,564,9.1.7Agent的应用,（1）电信。利用Agent的特性解决复杂系统和网络管理方面的任务，包括负载均衡、故障预测、问题分析和信息综合等。（2）兴趣匹配。Agent更多应用于商业网站向用户提供建议。（3）用户助理。用Agent协助用户更好地完成特定的任务。（4）组织结构。由多个Agent构造一个类似于人类组织的系统，不同的Agent代表着系统内的不同角色，通过这些Agent之间的通信和协作来完成具体的任务。目前主要应用于电子商务。（5）智能信息检索。Agent可以通过利用相关知识检索一些特定信息。,9.1智能体的概念与结构,565,9.1.7Agent的应用,（6）决策支持系统。Agent能够监控系统的一些关键信息，在系统可能出现问题的时候，警告相应的操作员，并在数据挖掘技术和决策支持模型的协助下，为复杂的决策提供有效的支持。（7）移动计算。Agent能为移动应用提供自然有效且稳定的离线计算模式，在移动用户再次连上网络之后再把结果反馈给用户。（8）远程教育。Agent作为虚拟教师、虚拟学习伙伴、虚拟实验设备、虚拟图书管理员等，实现虚拟的教学、练习和实验环节等。（9）数字娱乐。如在个性化的节目中插入点播服务；在游戏、动画中进行更加人性化的角色设计。,9.1智能体的概念与结构,566,9.1智能体的概念与结构9.2多智能体系统的概念与结构9.3多智能体系统的通信9.4多智能体系统的协调9.5多智能体系统的协作9.6多智能体系统的协商,第9章智能体与多智能体系统,567,9.2多智能体系统的概念与结构,9.2.1多智能体系统的特点,MAS中每个智能体具有独立性和自主性。MAS支持分布式应用，具有良好的模块性。MAS按面向对象的方法构造多层次、多元化的智能体。MAS是一个协调式的系统，也是一个集成系统。在MAS中，智能体之间相互通讯，彼此协调，并行地求解问题，提高了问题求解效率。同一个MAS中各个智能体可以是异构的。在MAS中，不同领域的专家系统、同一领域不同的专家系统可以协作求解单一专家系统难以解决的问题。,568,9.2多智能体系统的概念与结构,9.2.2多智能体系统的基本类型,BDI模型：是一个概念和逻辑上的理论模型，是研究Agent理性和推理机制的基础。协商模型：Agent的协作行为一般通过协商而产生。合同网协议就是协商模型的典型代表，主要解决任务分配、资源冲突和知识冲突等问题。协作规划模型：用于制订其协调一致的问题规划。自协调模型：随环境变化自适应地调整行为。,569,9.2多智能体系统的概念与结构,9.2.3多智能体系统的体系结构,网络结构：Agent之间都是直接通信的，通信和状态知识都是固定的。联盟结构：若干相距较近的Agent通过一个叫做协助者的Agent来进行交互，而远程Agent之间的交互和消息发送是由局部Agent群体的协助者Agent协作完成的。黑板结构：黑板结构中的局部Agent把信息存放在可存取的黑板上，实现局部数据共享。,570,9.1智能体的概念与结构9.2多智能体系统的概念与结构9.3多智能体系统的通信9.4多智能体系统的协调9.5多智能体系统的协作9.6多智能体系统的协商,第9章智能体与多智能体系统,571,9.3多智能体系统的通信,两个Agent之间的通信过程如下：,发送方将自己的思想翻译成通信所用语言的格式；发送方将语言格式加载到通信传播媒体，如声音、文字和图像；传播载体到达接收方；接收方读取载体中的语言代码；接收方在思维空间中将语言代码按其格式翻译为思想，从而熟悉发送方的意识状态。,572,9.3.1智能体通信的类型,使用Tell和Ask通信：Agent分享共同内部表示语言，并通过界面Tell和Ask直接访问相互的知识库。,573,9.3.1智能体通信的类型,使用形式语言通信：大多数Agent的通信是通过语言而不是通过直接访问知识库而实现的。,574,9.3.2Agent通信的方式,1.黑板系统,黑板系统的模型有三个主要组成部分：知识源，即Agent，是作为求解问题的独立单元，具有不同的专门知识，独立完成特定的任务。黑板，即公共工作区，为知识源提供信息和数据，同时，供知识源进行修改。监控机制。根据黑板当前的问题求解状态，以及各知识源的不同求解能力，对其进行监控，使之能适时相应黑板变化，及时进行问题求解。,575,9.3.2Agent通信的方式,2.消息/对话系统,有如下两种方式来实现Agent间的消息传递：直接通信方式：每个Agent必须知道消息在什么时候发送到什么地方，系统中有哪些Agent可以合作，这些Agent各具备什么样的能力等。这要求系统中的每个Agent都拥有其他Agent的信息。中介的通信：在基于中介的消息传送中，若干相距较近的Agent通过通信服务器来进行交互和消息发送，而远程Agent之间的交互是由局部群体中的通信服务器协作完成的。,576,9.3.3智能体通信语言,1.知识交换格式语言KIF主要是基于谓词逻辑，可以作为描述专家系统、数据库、多智能体的知识表示工具。KIF负责将一种语言翻译成另一种语言，或者为两种异构智能体的知识表达提供语义共享。可共享重用知识则是一个词汇表，它可以使可共享知识库的内容更容易被理解，同时也为特定的领域提供开发工具和方法。外部接口主要设计软件智能体运行时能够共享知识和信息的通信高层语言KQML，即知识查询操纵语言。KQML是自主的异步智能体之间共享知识和实现协作问题求解的通信语言。KQML既是一种消息格式，也是支持实时智能体之间知识共享的消息处理协议，实现基于知识的异构系统之间互操作和集成。,577,9.3.3智能体通信语言,在实际应用中，软件实体之间的互操作和知识共享是应用程序作为软件智能体的重要基础，甚至是必不可少的先决条件。互操作软件智能体的抽象模型。,578,9.3.3智能体通信语言,2.知识查询操纵语言KQMLKQML为多智能体通信定义了一套消息表达机制和消息传递格式，构建了一种标准通用框架。KQML分为3层：内容层、消息层和通信层。内容层使用应用程序本身的表达语言来传送消息的实际内容。通信层主要负责对消息的某些特性进行编码，这些特性描述了底层通信参数，例如发送者和接收者的标识符。消息层是整个KQML语言的核心。将一条消息从一个应用程序传送到另一个应用程序时，消息层完成对所传送信息的封装。消息层的一个最基本功能是识别传输消息发送时所使用的协议，并且给消息发送者提供一个附加在内容上的述行语或原语。KQML语言在内容不可知的情况下实现对消息的分析、路由和正确的传送。,579,9.3.3智能体通信语言,KQML语言中有多种在进程之间进行信息交换的协议。,580,9.1智能体的概念与结构9.2多智能体系统的概念与结构9.3多智能体系统的通信9.4多智能体系统的协调9.5多智能体系统的协作9.6多智能体系统的协商,第9章智能体与多智能体系统,581,9.4多智能体系统的协调,协调和协作是MAS研究的核心问题之一，是一个系统智能水平的重要体现。协调是一组Agent完成集体活动时相互作用的性质。协作是非对抗的Agent之间保持行为协调的特例。MAS中的协调是指多个Agent为了一致和谐的方式工作而进行交互的过程，避免Agent之间的死锁或活锁。死锁指多个Agent无法进行各自的下一步动作；活锁指多个Agent不断工作却无任何进展。,582,9.4多智能体系统的协调,当前主要有以下四种协调方法。(1)基于集中规划的协调：将具备其他Agent的知识、能力和环境资源知识的Agent可作为主控Agent，对该MAS的目标进行分解，对任务进行规划，并指示或建议其他Agent执行相关任务。特别适用于环境和任务相对固定、动态行为集可预计和需要集中监控的情况。(2)基于协商的协调：通过协商来实现任务的分配。协商是Agent间减缓信息、讨论和达成共识的方式。,583,9.4多智能体系统的协调,当前主要有以下四种协调方法。(3)基于对策论的协调：有通信协调和无通信协调两类。无通信协调是在没有通信的情况下，Agent根据对方及自身效益模型，按照对策论选择适当行为，Agent至多也只能达到协调的平衡解。在有通信协调中则可得到协作解。(4)基于社会规划的协调：以每个Agent必须遵循的社会规则、过滤策略、标准和惯例为基础的协调方法。这些规则对于Agent的行为加以限制，过滤某些有冲突的意图和行为，保证其他Agent必须的行为方式。,584,9.1智能体的概念与结构9.2多智能体系统的概念与结构9.3多智能体系统的通信9.4多智能体系统的协调9.5多智能体系统的协作9.6多智能体系统的协商,第9章智能体与多智能体系统,585,9.5多智能体系统的协作,9.5.1多智能体的协作类型,（1）完全协作型：系统中的智能体围绕一个共同的全局目标全力以赴地协作，各个智能体没有自己的局部目标。（2）协作型：系统中的智能体具有一个共同的全局目标，同时各个智能体还有与全局目标一致的局部目标。（3）自私型：系统中不存在共同的全局目标，各智能体都为自己的局部目标工作，而且目标之间可能存在冲突。（4）完全自私型：系统中不存在共同的目标，各智能体都为自己的局部目标工作，并且不考虑任何协作行为。（5）协作与自私共存型：系统中既存在共同的全局目标，某些智能体也可能还具有与全局目标无直接联系的局部目标。,586,9.5多智能体系统的协作,多智能体系统的协作过程一般分为六个阶段：,（1）产生协作需求，即确定协作目标；（2）协作规划，求解合理的协作结构；（3）寻求协作伙伴；（4）选择协作方案，即根据协作竞争者反推最佳的协作方案；（5）按协作或交互协议进行协作以实现所确定的目标；（6）结果评估，即判断协作的效果并为以后的协作提供可供参考的经验和教训。,587,9.5多智能体系统的协作,9.5.2合同网协作方法,在所有的协作方法中，合同网是最著名并且应用最广泛的一种协作方法。是由Smith于1980年提出的。基本思想:人们在商务过程中用于管理商品和服务的合同机制。在合同网方法中，所有智能体分为两种角色：管理者和工作者。在合同网协作方法中，智能体的角色在协作过程中的角色可以变化：任何智能体通过发布任务通知书而成为管理者；相反，任何智能体通过应答任务通知书而成为工作者。,588,9.5多智能体系统的协作,9.5.3黑板模型协作方法,黑板模型由三个基本模块构成：知识源：应用领域根据求解问题专门知识的不同划分成若干相互独立的专家，这些专家称为知识源（即智能体）。每一知识源独立完成一个特定领域的任务。黑板：共享的问题求解工作空间。主要存放知识源所需要的信息和求解过程中的解状态数据，如初始数据、部分解、替换解、最终解等。在问题求解过程中，知识源不断地修改黑板。知识源之间的通信和交互智能通过黑板进行。监控机制：根据黑板上的问题求解状态和各知识源的求解技能，依据某种控制策略，动态地选择和激活合适的知识源，使知识源能实时地响应黑板的变化。,589,9.5多智能体系统的协作,9.5.4市场机制协作方法,市场机制的基本思想是针对分布式资源分配的待定问题，建立相应的计算经济，使智能体之间通过最少的直接通信来协调多个智能体之间的活动。系统中只存在两种类型的智能体：生产者和消费者。智能体以各种价格对商品进行投标，但所有的商品交换都以当前市场价格进行，每一智能体通过投标以便获得最大利益和效用。在开放的市场环境中，智能体应该可以自由地选择自己的贸易策略，其行为不一定合乎常规。市场机制假定智能体所给予的偏好是与智能体获得行动结果的知识相一致，因此智能体推理行为就是最大化它自身的偏好。,590,9.1智能体的概念与结构9.2多智能体系统的概念与结构9.3多智能体系统的通信9.4多智能体系统的协调9.5多智能体系统的协作9.6多智能体系统的协商,第9章智能体与多智能体系统,591,9.6多智能体系统的协商,1.协商协议,Multi-Agent协商概括为协商协议、协商策略和协商处理。协商协议用于处理协商过程中协商之间的交互和作用，是交易双方交互的规则。主要研究的内容是Agent通信语言的定义、表示、处理和语义解释。协商协议的形式化表示通常有三种方法：巴科斯范式表示、有限自动机表示和语义表示。巴科斯范式表示具有简洁、明了的特点，是最常用的方法。常用的协商协议：根据协商对象的数量分为一对一、一对多、多对多的协议；根据协商的顺序分为轮流出价、同时出价协商协议；根据协商议题的数量分为