(特价书)智能系统原理、算法与应用
|
信息提示 关闭
如果您急需团购,可点击“团购急调”按钮将此书加入购物车,由我们的客服人员为您协调调货!
- 团购订单标准如下:
- 单品满30册可选择团购服务。
- 提交团购订单后,服务人员会主动和您联系,并根据您的会员等级、购买数量、金额、时间、配送要求等情况和您协商,以促成最终的成交。
- 有关团体购书的任何问题请随时联系:(010)63970506
基本信息

编辑推荐
本书是国内首部系统、全面地介绍智能系统基本原理、主要算法及其应用的导论性著作,可作为高等院校计算机、自动控制、管理、电子信息等专业研究生和高年级本科生的“智能系统”等课程的教材或教学参考书,也可供从事智能系统和人工智能(包括智慧城市和智能家居在内)研究与应用的科技人员及管理人员学习参考。
本书具有下列特色:
导论性 内容系统全面,既包含智能系统的基础知识和理论,又囊括各种智能系统及其算法,还介绍了多种智能系统的应用及其展望,使读者能够对智能系统有全面和系统的了解,扩大知识面。
新颖性 本书为我国第一部知识覆盖较广的智能系统著作,较全面地反映了国内外智能系统研究与应用的最新进展,内容新颖,具有新意。
实用性 本书比较注重理论联系实际,书中除以很大篇幅介绍各种智能系统的算法外,还举例分析了几种典型的智能系统的应用,指导读者进行应用实践。
可读性 本书虽为导读性教材,但仍有难度,作者力图将问题表述与物理内涵结合起来,更易于读者对基本概念的理解。
前:
蔡自兴
1962年毕业于西安交通大学电机工程系,现为中南大学信息科学与工程学院教授、博士生导师。1983~1985年为美国普渡大学和内华达大学访问学者,1988~1990年任中国科学院自动化研究所和北京大学信息科学中心客座研究员,1992~1993年任美国伦塞勒工业大学客座教授。2004年4~7月为俄罗斯科学院圣彼得堡信息学与自动化研究所客座研究员。2007年5~8月任丹麦技术大学客座教授。联合国专家(UNIDO)、国际导航与运动控制科学院院士、纽约科学院院士,全国高等学校首届国家级教学名师奖、宝钢教育基金优秀教师特等奖和徐特立教育奖获得者。
曾任第八届湖南省政协副主席,全国政协第九、十届委员会委员。曾兼任中国人工智能学会副理事长及智能机器人专业委员会主任、中国自动化学会理事及智能自动化专业委员会委员、中国计算机学会人工智能与模式识别专业委员会委员等职。
主要从事人工智能、智能系统、智能控制、智能机器人等研究,在智能科学基础的多个学科的科学研究和课程教学与改革中成绩卓著,是我国智能系统、人工智能、智能控制、机器人学诸学科的学术带头人之一。已在国内外出版专著、教材40多部,发表学术论文近千篇。主持并完成包括国家自然科学基金重点项目在内的科研20多项,主持国家级和省级教学改革项目10多项,获国际奖励3项,国家级奖励2项,省部级以上奖励10多项。
后:
王 勇
2003年本科毕业于武汉工程大学自动化专业,2006年获中南大学模式识别与智能系统专业硕士学位,2011年获中南大学控制科学与工程专业博士学位。自2006年10月起历任中南大学助教和讲师,2012年9月晋升为副教授。2011年5月至今担任硕士生导师,2013年9月至今担任博士生导师。
主要研究方向为进化计算、单目标优化、约束优化、多目标优化、智能优化算法及其在实际工程中的应用等。现为IEEE计算智能学会Task Force on Nature-Inspired Constrained Optimization和Task Force on Differential Evolution委员,41个国际期刊审稿人,24次担任国际会议程序委员会委员。主持2项国家自然科学基金项目,发表国际期刊论文18篇,其中IEEE Transactions长文8篇,3篇论文进入ESI高引用论文前1%,所设计的算法被国内外学者应用于20多个领域。连续三次获“湖南省自然科学优秀学术论文”一等奖,其博士毕业论文被评选为“湖南省优秀博士学位论文”(2013年)及“IEEE计算智能学会优秀博士论文”(2015年)。2011年入选中南大学“升华育英计划”,2012年入选“香江学者计划”,2013年入选“教育部新世纪优秀人才计划”和“湖南省青年骨干教师”。
内容简介
计算机书籍
《智能系统原理、算法与应用》介绍智能系统的基本原理、主要算法及其应用。全书共三篇、18章:第一篇为智能系统基础,包括第1~3章,第1章介绍人工智能和智能系统的概况,涉及人工智能和智能系统的定义、发展过程、主要学派的认知观和智能系统的分类等,第2章和第3章分别讨论知识表示与推理及非经典推理;第二篇为智能系统原理与算法,包括第4~11章,探讨各种智能系统的基础理论与算法,涉及专家系统、模糊逻辑系统、神经网络系统、机器学习系统、仿生进化系统、群智能系统、多真体系统和人工免疫系统;第三篇为智能系统应用与展望,包括第12~18章,其中第12~17章探讨智能系统的各种应用,包括智能机器人系统、智能控制系统、智能规划系统、智能决策系统、自然语言理解系统和智能交通系统,第18章展望智能系统的发展。
《智能系统原理、算法与应用》可作为高等院校计算机、自动控制、管理、电子信息等专业研究生和高年级本科生学习“智能系统”等课程的教材或教学参考书,也可供从事智能系统和人工智能研究与应用的科技人员及管理人员学习参考。
作译者
1962年毕业于西安交通大学电机工程系,现为中南大学信息科学与工程学院教授、博士生导师。1983~1985年为美国普渡大学和内华达大学访问学者,1988~1990年任中国科学院自动化研究所和北京大学信息科学中心客座研究员,1992~1993年任美国伦塞勒工业大学客座教授。2004年4~7月为俄罗斯科学院圣彼得堡信息学与自动化研究所客座研究员。2007年5~8月任丹麦技术大学客座教授。联合国专家(UNIDO)、国际导航与运动控制科学院院士、纽约科学院院士,全国高等学校首届国家级教学名师奖、宝钢教育基金优秀教师特等奖和徐特立教育奖获得者。
曾任第八届湖南省政协副主席,全国政协第九、十届委员会委员。曾兼任中国人工智能学会副理事长及智能机器人专业委员会主任、中国自动化学会理事及智能自动化专业委员会委员、中国计算机学会人工智能与模式识别专业委员会委员等职。
主要从事人工智能、智能系统、智能控制、智能机器人等研究,在智能科学基础的多个学科的科学研究和课程教学与改革中成绩卓著,是我国智能系统、人工智能、智能控制、机器人学诸学科的学术带头人之一。已在国内外出版专著、教材40多部,发表学术论文近千篇。主持并完成包括国家自然科学基金重点项目在内的科研20多项,主持国家级和省级教学改革项目10多项,获国际奖励3项,国家级奖励2项,省部级以上奖励10多项。
王勇
2003年本科毕业于武汉工程大学自动化专业,
2006年获中南大学模式识别与智能系统专业硕士学位,2011年获中南大学控制科学与工程专业博士学位。自2006年10月起历任中南大学助教和讲师,2012年9月晋升为副教授。2011年5月至今担任硕士生导师,2013年9月至今担任博士生导师。
主要研究方向为进化计算、单目标优化、约束优化、多目标优化、智能优化算法及其在实际工程中的应用等。现为IEEE计算智能学会Task Forceon Nature-Inspired Constrained Optimization和Task Force On DifferentialEvolution委员,41个国际期刊审稿人,24次担任国际会议程序委员会委员。主持2项国家自然科学基金项目,发表国际期刊论文18篇,其中,EEETransactlons长文8篇,3篇论文进入ESI高引用论文前1%,所设计的算法被国内外学者应用于20多个领域。连续三次获“湖南省自然科学优秀学术论文”一等奖,其博士毕业论文被评选为“湖南省优秀博士学位论文”(2013年)及“IEEE计算智能学会优秀博士论文”(2015年)。201 7年入选中南大学“升华育英计划”,2012年入选“香江学者计划”,2013年入选“教育部新世纪优秀人才计划”和”湖南省青年骨干教师”。
目录
前言
第一篇智能系统基础
第1章概述2
1.1人工智能与智能系统的定义2
1.2人工智能和智能系统的起源与发展4
1.3人工智能的各种认知观10
1.3.1人工智能各学派的认知观10
1.3.2人工智能的争论11
1.4智能系统的分类12
1.5人工智能的研究目标和内容17
1.5.1人工智能的研究目标17
1.5.2人工智能研究的基本内容17
1.6人工智能与智能系统的计算方法19
1.7本书内容编排20
习题1 21
第2章知识表示与推理22
2.1智能系统知识的分类与表示问题22
2.1.1智能系统知识的分类22
2.1.2知识表示的要求23
2.2.1问题状态描述24
2.2.2无信息搜索25
2.2.3启发式搜索26
2.3谓词演算与消解原理30
2.3.1谓词演算30
2.3.2置换与合一33
2.3.3消解原理35
2.4产生式系统38
2.4.1产生式系统的组成与表示38
2.4.2产生式系统的推理40
2.5语义网络法42
2.5.1二元语义网络的表示43
2.5.2多元语义网络的表示44
2.5.3基于语义网络的知识推理45
2.6框架表示与推理47
2.6.1框架的构成47
2.6.2框架的推理50
2.7知识表示与搜索的综合问题51
2.7.1问题的复合知识表示51
2.7.2启发式算法的可纳性与单调性51
2.8本章小结52
习题2 53
*第3章非经典推理55
3.1经典推理和非经典推理55
3.2不确定性推理56
3.2.1不确定性的表示与量度56
3.2.2不确定性的算法57
3.3概率推理58
3.3.1概率的基本性质和计算公式59
3.3.2概率推理方法60
3.4贝叶斯推理62
3.4.1知识不确定性的表示62
3.4.2证据不确定性的表示63
3.5可信度方法65
3.5.1基于可信度的不确定性表示66
3.5.2可信度方法的推理算法67
3.6搜索与计算复杂度70
3.7本章小结71
习题3 72
第二篇智能系统原理与算法
第4章专家系统74
4.1专家系统概述74
4.1.1专家系统的特点74
4.1.2专家系统的结构和建造步骤75
4.2基于规则的专家系统77
4.2.1基于规则的专家系统的工作模型和结构77
4.2.2基于规则的专家系统的特点78
4.3基于框架的专家系统80
4.3.1基于框架的专家系统的定义与结构80
4.3.2基于框架的专家系统的设计方法81
4.4基于模型的专家系统82
4.4.1基于模型的专家系统的提出82
4.4.2基于神经网络的专家系统82
*4.4.3基于概率的专家系统84
4.5基于Web的专家系统87
4.5.1基于Web的专家系统的结构87
4.5.2基于Web的专家系统的实例分析89
4.6新型专家系统92
4.7专家系统设计93
4.7.1专家知识的描述93
4.7.2知识的使用和决策解释96
4.8专家系统开发工具98
4.8.1骨架型开发工具98
4.8.2语言型开发工具99
4.8.3构造辅助工具100
4.8.4支撑环境100
4.9本章小结101
习题4 102
第5章模糊逻辑系统103
5.1模糊数学基础103
5.1.1模糊集合及其运算103
5.1.2模糊关系与模糊变换106
5.2模糊逻辑语言与推理109
5.2.1模糊逻辑语言109
5.2.2模糊逻辑推理111
5.3模糊系统的原理与结构115
5.3.1模糊系统的原理115
5.3.2模糊系统的结构116
5.4模糊系统的设计方法118
5.4.1模糊系统设计的查表法118
5.4.2模糊系统设计的递推最小二乘法119
5.4.3模糊系统设计的聚类法121
*5.5模糊系统的可达性与鲁棒性122
5.5.1模糊控制系统的可达性122
5.5.2模糊控制系统的鲁棒性123
5.6MATLAB模糊控制工具箱124
5.7本章小结127
习题5 127
第6章神经网络系统129
6.1人工神经网络概述129
6.1.1神经元及其特性130
6.1.2人工神经网络的基本类型和学习算法131
6.1.3人工神经网络的典型模型134
6.2基于神经网络的知识表示与推理138
6.2.1基于神经网络的知识表示138
6.2.2基于神经网络的知识推理140
6.3神经网络在约束优化中的应用问题142
6.4MATLAB神经网络工具箱及其仿真144
6.4.1MATLAB神经网络工具箱图形用户界面144
6.4.2基于Simulink的神经网络模块工具145
6.5本章小结147
习题6147
第7章机器学习系统149
7.1机器学习的定义和发展149
7.1.1机器学习的定义149
7.1.2机器学习的发展150
7.2机器学习的主要策略与基本结构151
7.2.1机器学习的主要策略151
7.2.2机器学习系统的基本结构152
7.3归纳学习153
7.3.1归纳学习的模式和规则154
7.3.2归纳学习方法155
7.4类比学习157
7.4.1类比推理和类比学习形式157
7.4.2类比学习过程与研究类型158
7.5解释学习159
7.5.1解释学习过程和算法159
7.5.2解释学习举例160
7.6神经网络学习161
7.6.1基于反向传播网络的学习161
7.6.2基于Hopfield网络的学习165
7.7知识发现167
7.7.1知识发现的发展和定义167
7.7.2知识发现的处理过程168
7.7.3知识发现的方法170
7.8增强学习172
7.8.1增强学习概述172
7.8.2Q-学习174
7.9本章小结175
习题7176
第8章仿生进化系统177
8.1进化算法177
8.1.1进化算法的主要原理178
8.1.2进化算法的整体框架179
8.2遗传算法180
8.2.1个体编码和解码180
8.2.2遗传算子181
8.2.3遗传算法的执行过程184
8.2.4遗传算法的执行实例185
8.2.5实数编码遗传算法187
8.3进化策略188
8.3.1变异算子188
8.3.2交叉算子与替换算子190
8.3.3进化策略的执行过程191
8.4进化规划191
8.4.1变异算子与替换算子192
8.4.2进化规划的执行过程192
8.4.3高斯变异与柯西变异193
8.5遗传算法、进化策略与进化规划的异同点194
8.6本章小结195
习题8 195
第9章群智能系统197
9.1粒子群优化算法197
9.1.1粒子群优化算法的基本原理197
9.1.2粒子群优化算法的执行过程199
9.1.3粒子速度和位置的修复199
9.1.4粒子群优化算法的两个变种200
9.1.5粒子群优化算法的改进201
9.2蚁群算法205
9.2.1蚁群算法的起源与发展205
9.2.2蚁群算法的原理与执行206
9.3本章小结211
习题9 212
第10章多真体系统213
10.1分布式人工智能213
10.2Agent及其要素214
10.2.1Agent的定义和译法215
10.2.2真体的要素和特性216
10.3真体的结构218
10.3.1真体的抽象结构和结构特点218
10.3.2真体结构的分类219
*10.4真体通信221
10.4.1通信的过程221
10.4.2真体通信的类型和方式225
10.4.3真体的通信语言227
10.5移动真体和多真体系统228
10.5.1移动真体的定义和系统构成229
10.5.2多真体系统的特征和关键技术230
10.5.3多真体系统的模型和结构231
10.5.4多真体的协作、协商和协调232
*10.5.5多真体的学习与规划235
10.5.6多真体系统的研究和应用领域236
10.6本章小结237
习题10 238
第11章人工免疫系统239
11.1自然免疫系统的概念、组成与功能239
11.2免疫算法及其设计方法241
11.2.1免疫算法的定义241
11.2.2免疫算法的步骤和框图242
11.2.3免疫算法的设计方法和参数选择244
*11.3人工免疫系统的结构246
11.4人工免疫系统应用示例247
11.4.1免疫控制系统的一般结构247
11.4.2免疫控制的计算体系和系统框图247
11.4.3免疫控制系统示例248
11.5本章小结250
习题11 250
第三篇智能系统应用与展望
第12章智能机器人系统252
12.1机器人学的起源与发展252
12.2机器人的定义和特点254
12.3机器人系统的构成与分类255
12.4智能机器人的研究领域257
12.5智能机器人应用示例259
12.5.1汽车自主驾驶系统的组成259
12.5.2汽车自主驾驶系统的结构260
12.5.3汽车自主驾驶系统的软件结构与控制算法262
12.5.4汽车自主驾驶系统的实验结果262
12.6本章小结263
习题12 263
第13章智能控制系统264
13.1智能控制的产生与发展264
13.1.1自动控制的机遇与挑战264
13.1.2智能控制的发展和作用266
13.2智能控制的定义、特点、一般结构与分类268
13.2.1智能控制的定义与特点268
13.2.2智能控制器的一般结构与分类269
13.3智能控制的学科结构理论体系272
13.3.1二元交集结构理论272
13.3.2三元交集结构理论273
13.3.3四元交集结构理论273
13.4智能控制系统应用示例276
13.5本章小结279
习题13279
第14章智能规划系统280
14.1智能规划概述280
14.1.1规划的概念和作用280
14.1.2规划的分类282
14.2任务规划283
14.2.1系统结构和规划机理283
14.2.2ROPES机器人规划系统285
14.3路径规划的主要方法和发展趋势287
14.4基于蚁群算法的移动机器人路径规划289
14.4.1蚁群优化算法简介289
14.4.2基于蚁群算法的路径规划290
14.5轨迹规划简介293
14.6本章小结294
习题14295
第15章智能决策系统296
15.1智能决策系统的定义与组成296
15.1.1智能决策系统的定义296
15.1.2智能决策系统的组成297
15.2智能决策系统的概念模型与典型特性298
15.2.1SHORE C2概念模型299
15.2.2指挥决策过程的典型特性301
15.3智能指挥决策的过程模型302
15.3.1智能数据融合303
15.3.2智能态势估计304
15.3.3资源的智能规划与分配305
15.4多属性决策305
15.4.1多属性决策的基本概念305
15.4.2多属性决策方法306
15.5本章小结309
习题15309
第16章自然语言理解系统310
16.1自然语言理解概述310
16.1.1语言与语言理解310
16.1.2自然语言理解的研究历史和发展现状312
16.1.3自然语言处理的定义和研究意义315
16.2自然语言理解的研究领域和研究方法317
16.2.1自然语言处理的研究领域317
16.2.2自然语言理解的研究方法318
16.2.3自然语言理解过程的层次319
16.3自然语言理解系统的主要模型320
16.4自然语言理解系统应用示例322
16.4.1自然语言自动理解系统322
16.4.2自然语言问答系统323
16.5本章小结325
习题16 325
第17章智能交通系统326
17.1智能交通系统概述326
17.2智能交通系统的发展327
17.3智能交通系统的体系结构329
17.4智能交通系统的信息平台331
17.5智能交通系统应用示例334
17.6本章小结338
习题17338
第18章智能系统展望339
18.1智能系统的学科定位问题339
18.2智能系统对人类的影响340
18.2.1对经济的影响340
18.2.2对社会的影响340
18.2.3对文化的影响342
18.3智能系统的未来343
18.3.1更新的理论框架343
18.3.2更好的技术集成345
18.3.3更成熟的应用方法345
18.4本章小结346
习题18347
参考文献348
前言
两年前,由我主持和主讲的国家级视频精品公开课“人工智能PK人类智能”在网上公开播出后,引发广大高校师生和公众的热烈反响与好评。这不仅是他们对我国视频公开课首播的热烈欢迎与充分肯定,而且体现了他们对人工智能及智能系统研究和进展的高度兴趣与由衷向往,还是对我们的极大鼓励与支持。我已经编著了30多部人工智能、智能控制、机器人学、专家系统和智能决策系统等方面的著作,以为再没有什么好写的内容了,最多只能继续撰写这些著作的新版本。上述视频公开课的鼓励与启发,使我萌生了编著一部新的智能科学著作的念头,即这本《智能系统原理、算法与应用》。
我们编著的上述各类智能科学著作提供了智能系统的基本内容和编写经验,而且已在中南大学为博士研究生开设了整整20届的“智能系统原理与应用”课程。教材编著和课程教学的经验,为我们编著这部新著作保驾护航,增加了我们写好本著作的信心。
本书分三篇介绍智能系统的基本原理、主要算法及其应用,可作为高等院校计算机、自动控制、管理、电子信息等专业研究生和高年级学生学习“智能系统”等课程的教材或教学参考书,也可供从事智能系统和人工智能研究与应用,以及智慧城市和智能住宅设计与开发的科技人员及管理人员学习参考。本书中带有星号(*)的章节为难点章节,除研究生需要参考外,其他读者可以不读。
在编写本书过程中,除了参阅本人独著著作外,还参阅了本人的合著著作和国内外部分相关文献,引用了其中的部分材料,使本书能够更好地反映智能系统的最新进展。例如,徐光祐、姚莉、龚涛、John Durkin、Robert Schalkoff,Y C Shin,Adriam Hopgood,Michael Negnevisky和LA Zadeh等,在此向相关著作的作者们表示特别感谢。
我们要衷心感谢中南大学研究生院和信息科学与工程学院的大力支持与合作,还特别感谢机械工业出版社策划编辑姚蕾和责任编辑李燕的敬业奉献精神,她们的支持,使本书能够迅速、高质量地与读者见面。
本书第1~7章以及第10~18章由蔡自兴编写,第8章和第9章由王勇编写,蔡自兴还负责全书内容的系统设计和统稿工作。由于水平所限和编写时间比较紧迫,因而书中可能存在不足之处,诚恳地欢迎各位专家、高校师生和其他读者批评指正。
蔡自兴
2014年5月
于广州迎风阁
媒体评论
本书具有下列特色:
导论性 内容系统全面,既包含智能系统的基础知识和理论,又囊括各种智能系统及其算法,还介绍了多种智能系统的应用及其展望,使读者能够对智能系统有全面和系统的了解,扩大知识面。
新颖性 本书为我国第一部知识覆盖较广的智能系统著作,较全面地反映了国内外智能系统研究与应用的最新进展,内容新颖,具有新意。
实用性 本书比较注重理论联系实际,书中除以很大篇幅介绍各种智能系统的算法外,还专列一篇、6章举例分析各种典型的智能系统的应用,能够指导读者进行应用实践。
可读性 本书虽为导读性教材,但仍有难度。作者努力将问题表述与物理内涵结合起来,更易于读者对基本概念的理解。
书摘
第1章概述
第2章知识表示与推理
第3章非经典推理
第一篇智能系统基础
CHAPTER1
第1章概述
半个多世纪以来,人工智能和智能系统迅速发展,引起了众多学科和不同专业背景学者们的广泛重视,并逐渐发展成为一门广泛的交叉和前沿科学。智能科学的研究成果将能够创造出更多、更高级的智能“制品”,并使之在越来越多的领域超越人类智能,人工智能和智能系统已经并将继续为发展国民经济和改善人类生活做出更大贡献。
在人工智能和智能系统的发展过程中始终面临一些争论、困难和挑战,然而这些争论是十分有益的,这些困难终将被解决,这些挑战始终与机遇并存,并将推动人工智能和智能系统继续发展。本书着重对智能系统进行全面、系统和尽可能深入的探讨。
本章讨论智能系统和人工智能的定义、发展历史和研究内容,并给出本书的内容编排。
1.1人工智能与智能系统的定义
无论是人工智能还是智能系统,科技学术界至今都没有统一和公认的定义。下面将结合我们的理解给出相关定义,并尽可能提供各种不同的观点。
1.知识的定义
人类的智力活动过程主要是一个获得并运用知识(knowledge)的过程,知识是智能的基础。那么什么是知识呢?具有不同研究与应用背景的学者对知识有不同的理解,进而形成不同的定义。其中,比较有代表性的有:
定义1.1知识是经过归约、塑造、解释和转换的信息。简单地说,知识是经过加工的信息。(费根鲍姆,Feigenbaum)
定义1.2知识是由特定领域的描述、关系和过程组成的。(伯恩斯坦,Bernstein)
定义1.3知识包括事实、信念和启发式规则等。(海斯-罗思,Hayes-Roth)
定义1.4知识是人们通过体验、学习或联想而知晓的对客观世界规律性的认识,这些认识包括事实、条件、过程、规则、关系和规律等。(蔡自兴)
此外,还有其他关于知识的认识。
从知识库观点看,知识是某个论域中涉及的各有关方面、状态的一种符号表示。
2.信息的定义
定义1.5信息(information)是知识的交流或对知识的感受,是对知识内涵的一种量测。描述事件的信息量越大,该事件的不确定性就越小。
3.智能的定义
定义1.6智能(intelligence)是人类理解和学习事物的能力,或者说,智能是思考和理解问题的能力,而不是本能或自动处理问题的能力。
定义1.7智能是一种应用知识处理环境的能力或由目标准则衡量的抽象思考能力。
定义1.8智能是系统在不确定环境中成功实现目标行为的能力。
定义1.9智能是在一定环境下针对特定目标而有效地获取信息、处理信息和利用信息从而成功地达到目标的能力。
图灵(A.Turing)于20世纪30~40年代创造了一个通用的非数字计算机模型,并直接证明了计算机可能以某种被理解为智能的方法工作,即机器(计算机)能够具有智能。许多哲学家和计算机科学家接受了这一思想,而另一些哲学家则反对这个思想,认为诸如创造发现、道德选择和爱情这样高度复杂的行为,将是机器永远无法实现的。
下面就我们所知给出智能机器和人工智能的定义。
4.智能机器的定义
定义1.10智能机器(intelligent machine)是一种能够呈现出人类智能行为的机器,而这种智能行为呈现出人类用大脑考虑问题或创造思想的智力功能。
定义1.11智能机器是一类能够在定型或不定型、熟悉或不熟悉、已知或未知的环境中自主或交互地执行各种拟人任务(anthropomorphic task)的机器。
5.人工智能的定义
定义1.12长期以来,人工智能(artificial intelligence)研究者认为:人工智能(学科)是计算机科学中涉及研究、设计和应用智能机器的一个分支。它的近期主要目标在于研究用机器来模仿和执行人脑的某些智力功能,并开发相关理论和技术。
近年来,许多人工智能和智能系统研究者认为:人工智能(学科)是智能科学(intelligence science)中涉及研究、设计、应用智能机器和智能系统的一个分支。而智能科学是一门与计算机科学并行的学科。
确定人工智能到底属于计算机科学还是智能科学,可能仍需要一段时间的探讨与实践,而实践是检验真理的标准,实践将做出权威的回答。目前,两者的研究并不冲突,而是相辅相成的。或许有一天,它们终会走到一起。
定义1.13人工智能(能力)是智能机器所执行的通常与人类智能有关的智能行为,这些智能行为涉及学习、感知、思考、理解、识别、判断、推理、证明、通信、设计、规划、决策和问题求解等活动。
1950年,图灵设计和进行的著名实验(后来被称为图灵实验,Turing test)提出并部分回答了“机器能否思维”的问题,这也是对人工智能的一个很好注释。
6.智能系统的定义
智能系统(intelligent system)与人工智能有着十分密切的关系。智能系统可由显示知识库建立,而知识库又是由综合和正规的推理机制操作的。这意味着,研究从符号表示的知识获取信息的途径,即知识表示与推理,对研究智能系统是至关重要的。
对知识系统的定义涉及两个问题:①专注于作为任何反映智能系统主题的知识表示与推理;②假设系统只包含表示知识和应用推理技术的机理,建立基于计算系统的模型。
定义1.14智能系统是一门通过计算实现智能行为的学科领域。简而言之,智能系统是具有智能的系统(systems with intelligence)。
任何计算都需要某个实体(如概念或数量)和操作过程(运算步骤)。计算、操作和学习是智能系统的要素。而要进行操作,就需要适当的表示。与此相关的问题有:
1)知识或智能是如何表示的?
2)知识或智能是如何操作(运算)的?
3)知识或智能是如何学习(获取)的?
这些都是需要深入研究的问题。
定义1.15从工程观点出发,将智能系统定义为一门关于生成表示、推理过程和学习策略以自动(自主)解决人类此前解决过的问题的学科。于是,智能系统是认知科学的工程对应物,而认知科学是一门哲学、语言学和心理学相结合的科学。
定义1.16能够驱动智能机器感知环境以实现其目标的系统叫智能系统。
有一种观点是在专家系统的基础上来定义智能系统的:
定义1.17智能系统是随着数据仓库、数据挖掘、知识发现、智能真体技术和分布式系统及算法的出现,由专家系统逐渐发展演变而成的具有专家解决问题能力的智能计算机程序系统。
1.2人工智能和智能系统的起源与发展
下面按时期来说明人工智能和智能系统的发展过程,这种时期划分方法有时难以严谨,因为许多事件可能跨接不同时期,另外一些事件虽然时间相隔甚远但又可能密切相关。
1.孕育时期(1956年前)
人类对智能机器和人工智能的梦想和追求可以追溯到三千多年前。早在我国西周时代(公元前1046~公元前771年)就流传有关巧匠偃师献给周穆王一个歌舞艺伎的故事。作为第一批自动化动物之一的能够飞翔的木鸟是在公元前400年至公元前350年间制成的。在公元前2世纪出现的书籍中,描写过一个具有类似机器人角色的机械化剧院,这些人造角色能够在宫廷仪式上进行舞蹈和列队表演。我国东汉时期(公元25~220年),张衡发明的指南车是世界上最早的机器人雏形。
这里不打算列举三千多年来人类在追梦智能机器和人工智能道路上的万千遐想、实践和成果,而是跨越三千年转到20世纪。时代思潮直接帮助科学家去研究某些现象。对于人工智能的发展来说,20世纪30年代和40年代的智能界,发现了两件最重要的事:数理逻辑(它从19世纪末起就获得迅速发展)和关于计算的新思想。弗雷治(Frege)、怀特赫德(Whitehead)、罗素(Russell)和塔斯基(Tarski)以及另外一些人的研究表明,推理的某些方面可以用比较简单的结构加以形式化。1913年,年仅19岁的维纳(Wiener)在他的论文中将数理关系理论简化为类理论,为发展数理逻辑做出了贡献,并向机器逻辑迈进一步,与后来图灵提出的逻辑机不谋而合。1948年,维纳创立的控制论(Cybernetics)对人工智能的早期思潮产生了重要影响,后来成为人工智能行为主义学派。数理逻辑仍然是人工智能研究的一个活跃领域,其部分原因是一些逻辑演绎系统已经在计算机上实现过。不过,在计算机出现之前,逻辑推理的数学公式就为人们建立了计算与智能关系的概念。
丘奇(Church)、图灵和其他一些人关于计算本质的思想,提供了形式推理概念与即将发明的计算机之间的联系。在这方面的重要工作是关于计算和符号处理的理论概念。1936年,年仅26岁的图灵创立了自动机理论(后来被人们称为图灵机),提出一个理论计算机模型,为电子计算机设计奠定了基础,促进了人工智能特别是思维机器的研究。第一批数字计算机(实际上为数字计算器)看来不包含任何真实智能。早在这些机器设计之前,丘奇和图灵就已发现,数字并不是计算的主要方面,它们仅仅是一种解释机器内部状态的方法。1950年10月,图灵又发表了一篇题为《机器会思维吗?》(Can A Machine Think?)的论文,成为划时代之作。也正是这篇文章,使图灵被誉为“人工智能之父”。被称为人工智能之父的图灵,不仅创造了一个简单、通用的非数字计算模型,而且直接证明了计算机可能以某种被理解为智能的方法工作。
20多年后,道格拉斯·霍夫施塔特(Douglas Hofstadter)在《GeB——永恒的金带》一书中对这些逻辑和计算的思想,以及它们与人工智能的关系给予了透彻而又引人入胜的解释。
麦卡洛克(McCulloch)和皮茨(Pitts)于1943年提出的“拟脑机器”(mindlike machine)是世界上第一个神经网络模型(称为MP模型),开创了从结构上研究人类大脑的新途径。神经网络连接机制后来发展成为人工智能连接主义学派的代表。
值得一提的是控制论思想对人工智能早期研究的影响。正如艾伦·纽厄尔(Allen Newell)和赫伯特·西蒙(Herbert Simon)在他们的优秀著作《人类问题求解》(Human Problem Solving)的“历史补篇”中指出的那样,20世纪中叶人工智能的奠基者们在人工智能研究中出现了几股强有力的思潮。维纳、麦卡洛克和其他一些人提出的控制论和自组织系统的概念集中讨论了“局部简单”系统的宏观特性。尤其重要的是,1948年维纳发表的控制论(或动物与机器中的控制与通信)论文,不但开创了近代控制论,而且为人工智能的控制论学派(即行为主义学派)树立了新的里程碑。控制论影响了许多领域,因为控制论的概念跨接了许多领域,从而将神经系统的工作原理与信息理论、控制理论、逻辑以及计算联系起来。控制论的这些思想是时代思潮的一部分,而且在许多情况下影响了许多早期和近期人工智能工作者,成为他们的指导思想。
从上述情况可以看出,人工智能开拓者们在数理逻辑、计算本质、控制论、信息论、自动机理论、神经网络模型和电子计算机等方面做出的创造性贡献,奠定了人工智能发展的理论基础,孕育了人工智能的“胎儿”。人们将很快听到人工智能婴儿呱呱坠地的哭声,看到这个宝贝降临人间的可爱身影!
2.形成时期(1956~1970年)
到了20世纪50年代,人工智能已躁动于人类科技社会的母胎,即将分娩。1956年夏季,由年轻的美国数学家和计算机专家麦卡锡(McCarthy)、数学家和神经学家明斯基(Minsky)、IBM公司信息中心主任朗彻斯特(Lochester)以及贝尔实验室信息部数学家和信息学家香农(Shannon)共同发起,邀请IBM公司的莫尔(More)和塞缪尔(Samuel)、MIT的塞尔夫里奇(Selfridge)和索罗蒙夫(Solomonff),以及兰德公司和CMU(卡内基梅隆大学)的纽厄尔(Newell)和西蒙(Simon),共10人,在美国的达特茅斯(Dartmouth)大学举办了一次长达两个月的研讨会,认真热烈地讨论用机器模拟人类智能的问题。会上,由麦卡锡提议正式使用“人工智能”这一术语。这是人类历史上第一次人工智能研讨会,标志着人工智能学科的诞生,具有十分重要的历史意义。这些从事数学、心理学、信息论、计算机科学和神经学研究的杰出年轻学者,后来绝大多数都成为著名的人工智能专家,为人工智能的发展做出了重要贡献。
最终将这些不同思想连接起来的是由巴贝奇(Babbage)、图灵、冯·诺依曼(Von Neumman)和其他一些人所研制的计算机本身。在机器的应用成为可行之后不久,人们就开始试图编写程序以解决智力测验难题、数学定理和其他命题的自动证明、下棋,以及将文本从一种语言翻译成另一种语言,这是第一批人工智能程序。对于计算机来说,促使人工智能发展的是什么呢?是出现在早期设计中的许多与人工智能有关的计算概念,包括存储器和处理器的概念、系统和控制的概念,以及语言的程序级别的概念。不过,引起新学科出现的新机器的唯一特征是这些机器的复杂性,它促进了对描述复杂过程方法的新的、更直接的研究(采用复杂的数据结构和具有数以百计的不同步骤的过程来描述这些方法)。
1965年,被誉为“专家系统和知识工程之父”的费根鲍姆(Feigenbaum)所领导的研究小组开始研究专家系统,并于1968年研究成功第一个专家系统DENDRAL,用于质谱仪分析有机化合物的分子结构。后来又开发出其他一些专家系统,为人工智能的应用研究做出了开创性的贡献。
1969年召开了第一届国际人工智能联合会议(International Joint Conference on AI,IJCAI),这标志着人工智能作为一门独立学科登上了国际学术的舞台。此后,IJCAI每两年召开一次。1970年《人工智能国际杂志》(International Journal of AI)创刊。这些事件对开展人工智能国际学术活动和交流、促进人工智能的研究和发展起到了积极的作用。
上述事件表明,人工智能经历了从诞生到成人的热烈(形成)期,已成为一门独立学科。这一时期为人工智能建立了良好的环境,为进一步发展人工智能打下了重要基础。虽然人工智能在前进的道路上仍将面临不少困难和挑战,但是有了这个基础,就能够迎接挑战,抓住机遇,不断发展。
3.暗淡时期(1966~1974年)
在形成期和后面的知识应用期之间,交叠地存在一个人工智能的暗淡(低潮)期。在取得“热烈”发展的同时,人工智能也遇到一些困难和问题。
一方面,一些人工智能研究者被“胜利冲昏了头脑”,盲目乐观,对人工智能的未来发展和成果做出了过高的预言,而这些预言的失败,给人工智能的声誉造成重大伤害。同时,许多人工智能理论和方法未能得到通用化和推广应用,专家系统也尚未获得广泛开发。因此,看不出人工智能的重要价值。究其原因,当时的人工智能主要存在如下三个局限性。
(1)知识局限性
早期开发的人工智能程序包含太少的主题知识,甚至没有知识,而且只采用简单的句法处理。
(2)解法局限性
人工智能试图解决的许多问题因其求解方法和步骤的局限性,往往使得设计的程序实际上无法求得问题的解答,或者只能得到简单问题的解答,而这种简单问题并不需要人工智能的参与。
(3)结构局限性
用于产生智能行为的人工智能系统或程序存在一些基本结构上的严重局限,如没有考虑不良结构,无法处理组合爆炸问题,因而只能用于解决比较简单的问题,影响到推广应用。
另一方面,科学技术的发展对人工智能提出了新的要求甚至挑战。例如,当时认知生理学研究发现,人类大脑含有1011个以上神经元,而人工智能系统或智能机器在现有技术条件下无法从结构上模拟大脑的功能。此外,哲学、心理学、认知生理学和计算机科学各学术界对人工智能的本质、理论和应用各方面一直抱有怀疑和批评,也使得人工智能四面楚歌。例如,1971年英国剑桥大学数学家詹姆士(James)按照英国政府的旨意,发表了一份关于人工智能的综合报告,声称“人工智能不是骗局,也是庸人自扰”。在这个报告的影响下,英国政府削减了人工智能研究经费,解散了人工智能研究机构。在人工智能的发源地美国,连在人工智能研究方面颇有影响的IBM,也被迫取消了该公司的所有人工智能研究工作。人工智能研究在世界范围内陷入困境,处于低潮,由此可见一斑。
任何事物的发展都不可能一帆风顺,冬天过后,春天就会到来。通过总结经验教训,开展更为广泛、深入和有针对性的研究,人工智能必将走出低谷,迎来新的发展时期。
4.知识应用时期(1970~1988年)
费根鲍姆研究小组自1965年开始研究专家系统,并于1968年研究成功第一个专家系统DENDRAL。1972~1976年,他们又开发成功MYCIN医疗专家系统,用于抗生素药物治疗。此后,许多著名的专家系统,如斯坦福国际人工智能研究中心的杜达(Duda)开发的PROSPECTOR地质勘探专家系统,拉特格尔大学的CASNET青光眼诊断治疗专家系统,MIT的MACSYMA符号积分和数学专家系统,以及R1计算机结构设计专家系统、ELAS钻井数据分析专家系统和ACE电话电缆维护专家系统等被相继开发,为工矿数据分析处理、医疗诊断、计算机设计、符号运算等提供了强有力的工具。在1977年举行的第五届国际人工智能联合会议上,费根鲍姆正式提出了知识工程(knowledge engineering)的概念,并预言20世纪80年代将是专家系统蓬勃发展的时代。
事实果真如此,整个80年代,专家系统和知识工程在全世界得到迅速发展。专家系统为企业等用户赢得了巨大的经济效益。到1988年,DEC公司的人工智能团队开发了40个专家系统。更有甚者,杜珀公司已使用100个专家系统,正在开发500个专家系统。几乎每个美国大公司都拥有自己的人工智能小组,并应用或投资专家系统。20世纪80年代,日本和西欧也争先恐后地投入对专家系统的智能计算机系统的开发,并应用于工业部门。其中,日本1981年发布的“第五代智能计算机计划”就是一例。在开发专家系统过程中,许多研究者获得共识,即人工智能系统是一个知识处理系统,而知识表示、知识利用和知识获取则成为人工智能系统的三个基本问题。
5.集成发展时期(1986年至今)
到20世纪80年代后期,各个争相进行的智能计算机研究计划先后遇到严峻挑战和困难,无法实现其预期目标。这促使人工智能和智能系统研究者们对已有的人工智能和专家系统思想和方法进行反思。已有的专家系统存在缺乏常识知识、应用领域狭窄、知识获取困难、推理机制单一、未能分布处理等问题。他们发现,这些挑战和困难反映出人工智能和智能系统的一些根本问题,如交互问题、扩展问题和体系问题等。对存在问题的探讨和对基本观点的争论,有助于人工智能摆脱困境,迎来新的发展机遇。
人工智能和智能系统应用技术应当以知识处理为核心实现软件的智能化。知识处理需要对应用领域和问题求解任务有深入的理解,扎根于主流计算环境。只有这样,才能促使人工智能研究和应用走上持续发展的道路。
20世纪80年代后期以来,机器学习、计算智能、人工神经网络和行为主义等研究深入开展,不时形成高潮。有别于符号主义的连接主义和行为主义的人工智能学派也乘势而上,获得新的发展。不同人工智能学派间的争论推动了人工智能研究和应用的进一步发展。以数理逻辑为基础的符号主义,从命题逻辑到谓词逻辑再到多值逻辑,包括模糊逻辑和粗糙集理论,已为人工智能的形成和发展做出了历史性贡献,并已超出传统符号运算的范畴,表明符号主义在发展中不断寻找新的理论、方法和实现途径。传统人工智能(我们称为AI)的数学计算体系仍不够严格和完整。除了模糊计算外,近年来,许多模仿人脑思维、自然特征和生物行为的计算方法(如神经计算、进化计算、自然计算、免疫计算和群计算等)已被引入人工智能学科。我们将这些有别于传统人工智能的智能计算理论和方法称为计算智能(Computational Intelligence,CI)。计算智能弥补了传统AI缺乏数学理论和计算的不足,更新并丰富了人工智能的理论框架,使人工智能进入一个新的发展时期。人工智能不同观点、方法和技术的集成,是人工智能发展所必需,也是人工智能发展的必然。
在这个时期,特别值得一提的是神经网络的复兴和智能真体(intelligent agent)的突起。
麦卡洛克和皮茨于1943年提出的“似脑机器”构造了一个表示大脑基本组成的神经元模型。当时神经网络的局限性,特别是硬件集成技术的局限性,使人工神经网络研究在20世纪70年代进入低潮。直到1982年霍普菲尔德(Hopfield)提出离散神经网络模型,1984年又提出连续神经网络模型,才促进了人工神经网络研究的复兴。布赖森(Bryson)和何(He)提出的反向传播(BP)算法及鲁梅尔哈特(Rumelhart)和麦克莱伦德(McClelland)于1986年提出的并行分布处理(PDP)理论是人工神经网络研究复兴的真正推动力,人工神经网络再次出现研究热潮。1987年在美国召开了第一届神经网络国际会议,并发起成立了国际神经网络学会。这表明神经网络已置身于国际信息科技之林,成为人工智能的一个重要子学科。现在对神经网络的研究虽然没有当时那么热烈,但仍然保持比较平稳的发展势头。如果人工神经网络硬件能够在大规模集成上取得突破,那么其作用不可估量。
智能真体(以前称为智能主体)是20世纪90年代随着网络技术,特别是计算机网络通信技术的发展而兴起的,并发展为人工智能又一个新的研究热点。人工智能的目标就是要建造能够表现出一定智能行为的真体,因此,真体(Agent)应是人工智能的一个核心问题。人们在人工智能研究过程中逐步认识到,人类智能的本质是一种具有社会性的智能,社会问题特别是复杂问题的解决需要各方面人员共同完成。人工智能特别是比较复杂的人工智能问题的求解也必须要由各个相关个体协商、协作和协调来完成。人类社会中的基本个体“人”对应于人工智能系统中的基本组元“真体”,而社会系统所对应的人工智能“多真体系统”也就成为人工智能新的研究对象。
人工智能已获得越来越广泛的应用,深入渗透到其他学科和科学技术领域,为这些学科和领域的发展做出功不可没的贡献,并为人工智能理论和应用研究提供新的思路与借鉴。例如,对生物信息学、生物机器人学和基因组的研究就是如此。
上述这些新出现的人工智能理论、方法和技术,其中包括人工智能三大学派,即符号主义、连接主义和行为主义,已不再是单枪匹马打天下,而往往是携手合作,走综合集成、优势互补、共同发展的康庄大道。人工智能学界那种势不两立的激烈争论局面,可能一去不复返了。我们有理由相信,人工智能工作者一定能够抓住机遇,不负众望,创造更多、更大的新成果,开创人工智能发展的新时期。
值得特别指出的是对人类大脑的最新研究计划。欧盟于2013年1月28日宣布将在未来10年内为“人类大脑计划”(Human Brain Project)提供10亿欧元的研发经费,由来自23个国家(其中16个是欧盟国家)的大学、研究机构和工业界的87个组织通力合作,用计算机模拟的方法研究人类大脑是如何工作的。该研究有望促进人工智能、机器人学和神经形态计算系统的发展,奠定医学进步的科学和技术基础,有助于神经系统及相关疾病的诊疗及药物测试。
差不多与此同时,美国总统奥巴马于2013年4月2日宣布一项旨在揭开人类大脑未解之谜的重大研究计划“BRAIN”,将从2014财年的政府预算中拿出1亿美元,用于进行一项希望找出治疗阿尔茨海默氏症等与大脑有关疾病的方法。此计划将利用新技术解析脑细胞及神经的运作,了解大脑奥秘,帮助研究人员找到治疗、治愈和预防老年痴呆、癫痫和创伤性脑损伤等脑部疾病的新方法。在这个重大研究计划框架下,美国国家卫生研究院于2013年9月16日公布了包括统计大脑细胞类型,建立大脑结构图,开发大规模神经网络记录技术,开发操作神经回路的工具,了解神经细胞与个体行为之间的联系,将神经科学实验与理论、模型、统计学等整合,描述人类大脑成像技术的机制,为科学研究建立收集人类数据的机制,以及知识传播与培训等9个资助领域。
欧盟和美国的上述最新研究计划,必将激发一场世界范围内的大脑研究热潮,推动智能系统和人工智能研究,促进智能系统和人工智能学科的进一步发展。
我国的人工智能和智能系统研究起步较晚。纳入国家计划的研究(“智能模拟”)始于1978年;1984年召开了智能计算机及其系统的全国学术讨论会;1986年起将智能计算机系统、智能机器人和智能信息处理(含模式识别)等重大项目列入国家高技术研究计划;1993年起,又将智能控制和智能自动化等项目列入国家科技攀登计划。进入21世纪后,已有更多的人工智能与智能系统研究获得各种基金计划支持,并与国家国民经济和科技发展的重大需求相结合,力求做出更大贡献。1981年起,相继成立了中国人工智能学会(CAAI)及智能机器人专业委员会和智能控制专业委员会、全国高校人工智能研究会、中国计算机学会人工智能与模式识别专业委员会、中国自动化学会模式识别与机器智能专业委员会、中国软件行业协会人工智能协会以及智能自动化专业委员会等学术团体。1989年首次召开了中国人工智能控制联合会议(CJCAI)。已有约50部国内编著的具有知识产权的人工智能专著和教材出版。《模式识别与人工智能》杂志和《智能系统学报》已分别于1987年和2006年创刊。2006年8月,中国人工智能学会联合兄弟学会和有关部门,在北京举办了包括人工智能国际会议和中国象棋人机大战等在内的“庆祝人工智能学科诞生50周年”大型庆祝活动,产生了很好的影响。中国的人工智能工作者已在人工智能领域取得许多具有国际先进水平的创造性成果。其中,尤以吴文俊院士关于几何定理证明的“吴氏方法”最为突出,已在国际上产生了重大影响,并荣获2001年国家科学技术最高奖。现在,我国已有数以万计的科技人员和高校师生从事不同层次的人工智能研究与学习,人工智能研究已在我国深入开展,它必将为促进其他学科的发展和我国的现代化建设做出新的重大贡献。
1.3人工智能的各种认知观
目前人工智能的主要学派有以下3个:
1)符号主义(Symbolicism),又称为逻辑主义(Logicism)、心理学派(Psychlogism)或计算机学派(Computerism),其原理主要为物理符号系统假设和有限合理性原理。
2)连接主义(Connectionism),又称为仿生学派(Bionicsism)或生理学派(Physiologism),其原理主要为神经网络及神经网络间的连接机制与学习算法。
3)行为主义(Actionism),又称进化主义(Evolutionism)或控制论学派(Cyberneticsism),其原理为控制论及感知—动作型控制系统。
1.3.1人工智能各学派的认知观
人工智能各学派对人工智能发展历史具有不同的看法。
1.符号主义
认为人工智能源于数理逻辑。数理逻辑从19世纪末起就迅速发展;到20世纪30年代开始用于描述智能行为。计算机出现后,又在计算机上实现了逻辑演绎系统。其有代表性的成果为启发式程序LT(逻辑理论家),证明了38条数学定理,表明了可以应用计算机研究人的思维过程,模拟人类智能活动。正是这些符号主义者,早在1956年首先采用“人工智能”这个术语。后来又发展了启发式算法→专家系统→知识工程理论与技术,并在20世纪80年代取得很大发展。符号主义曾长期一枝独秀,为人工智能的发展做出重要贡献,尤其是专家系统的成功开发与应用,为人工智能走向工程应用和实现理论联系实际具有特别重要的意义。在人工智能的其他学派出现之后,符号主义仍然是人工智能的主流学派。这个学派的代表人物有纽厄尔、肖、西蒙和尼尔逊(Nilsson)等。
2.连接主义
认为人工智能源于仿生学,特别是人脑模型的研究。它的代表性成果是1943年由生理学家麦卡洛克(McCulloch)和数理逻辑学家皮茨(Pitts)创立的脑模型,即MP模型,开创了用电子装置模仿人脑结构和功能的新途径。它从神经元开始进而研究神经网络模型和脑模型,开辟了人工智能的又一发展道路。20世纪60~70年代,连接主义,尤其是对以感知器(perceptron)为代表的脑模型的研究曾出现过热潮,由于当时理论模型、生物原型和技术条件的限制,脑模型研究在20世纪70年代后期至80年代初期落入低潮。直到前述Hopfield教授在1982年和1984年发表两篇重要论文,提出使用硬件模拟神经网络后,连接主义又重新抬头。1986年鲁梅尔哈特(Rumelhart)等人提出多层网络中的反向传播(BP)算法。此后,连接主义势头大振,从模型到算法,从理论分析到工程实现,为神经网络计算机走向市场打下基础。现在,对ANN的研究热情仍然较高,但研究成果未能如预想的那样好。
3.行为主义
认为人工智能源于控制论。控制论思想早在20世纪40~50年代就成为时代思潮的重要部分,影响了早期的人工智能工作者。维纳和麦克洛等人提出的控制论和自组织系统,以及钱学森等人提出的工程控制论和生物控制论,影响了许多领域。控制论将神经系统的工作原理与信息理论、控制理论、逻辑以及计算机联系起来。早期研究工作的重点是模拟人在控制过程中的智能行为和作用,如对自寻优、自适应、自校正、自镇定、自组织和自学习等控制论系统的研究,并进行“控制论动物”的研制。到20世纪60~70年代,上述这些控制论系统的研究取得一定进展,播下智能控制和智能机器人的种子,并在80年代诞生了智能控制和智能机器人系统。行为主义是20世纪末才以人工智能新学派的面孔出现的,引起许多人的兴趣。这一学派的代表作首推布鲁克斯(Brooks)的六足行走机器人,它被看作新一代的“控制论动物”,是一个基于“感知-动作”模式的模拟昆虫行为的控制系统。
以上三个人工智能学派将长期共存与合作,取长补短,并走向融合和集成,为人工智能的发展做出贡献。
1.3.2人工智能的争论
1.对人工智能理论的争论
人工智能各学派对于AI的基本理论问题,诸如定义、基础、核心、要素、认知过程、学科体系以及人工智能与人类智能的关系等,均有不同观点。
(1)符号主义
认为人的认知基元是符号,而且认知过程即符号操作过程。它认为人是一个物理符号系统,计算机也是一个物理符号系统,因此,我们就能够用计算机来模拟人的智能行为,即用计算机的符号操作来模拟人的认知过程,也就是说,人的思维是可操作的。它还认为,知识是信息的一种形式,是构成智能的基础。人工智能的核心问题是知识表示、知识推理和知识运用。知识可用符号表示,也可用符号进行推理,因而有可能建立起基于知识的人类智能和机器智能的统一理论体系。
(2)连接主义
认为人的思维基元是神经元,而不是符号处理过程。它对物理符号系统假设持反对意见,认为人脑不同于计算机,并提出连接主义的大脑工作模式,用于取代符号操作的计算机工作模式。
(3)行为主义
认为智能取决于感知和行动(所以被称为行为主义),提出智能行为的“感知—动作”模式。行为主义者认为智能不需要知识、不需要表示、不需要推理;人工智能可以像人类智能一样逐步进化(所以称为进化主义);智能行为只能在现实世界中与周围环境交互作用而表现出来。行为主义还认为:符号主义(还包括连接主义)对真实世界客观事物的描述及其智能行为工作模式是过于简化的抽象,因而是不能真实地反映客观存在的。
2.对人工智能方法的争论
不同人工智能学派对人工智能的研究方法问题也有不同的看法。这些问题涉及:人工智能是否一定采用模拟人的智能的方法?若要模拟又该如何模拟?对结构模拟和行为模拟、感知思维和行为、对认知与学习以及逻辑思维和形象思维等问题是否应分离研究?是否有必要建立人工智能的统一理论系统?若有,又应以什么方法为基础?
(1)符号主义
认为人工智能的研究方法应为功能模拟方法。通过分析人类认知系统所具备的功能和机能,然后用计算机模拟这些功能,实现人工智能。符号主义力图用数学逻辑方法来建立人工智能的统一理论体系,但遇到不少暂时无法解决的困难,并受到其他学派的否定。
(2)连接主义
主张人工智能应着重于结构模拟,即模拟人的生理神经网络结构,并认为功能、结构和智能行为是密切相关的。不同的结构表现出不同的功能和行为。已经提出多种人工神经网络结构和众多的学习算法。
(3)行为主义
认为人工智能的研究方法应采用行为模拟方法,也认为功能、结构和智能行为是不可分的。不同行为表现出不同功能和不同控制结构。行为主义的研究方法也受到其他学派的怀疑与批判,认为行为主义最多只能创造出智能昆虫行为,而无法创造出人的智能行为。
1.4智能系统的分类
分类学与科学学这两门学科主要研究科学技术学科的分类问题,本是十分严谨的学问,但对于一些新学科却很难确切地对其进行分类或归类。例如,至今多数学者都将人工智能看作计算机科学的一个分支;但从科学长远发展的角度看,人工智能可能要归类于智能科学的一个分支。智能系统也尚无统一的分类方法,下面按其作用原理可分为下列几种系统。
1.专家系统
专家系统(Expert System,ES)是人工智能和智能系统应用研究最活跃和最广泛的领域之一。自从1965年第一个专家系统DENDRAL在美国斯坦福大学问世以来,经过20年的研究开发,到20世纪80年代中期,各种专家系统已遍布各个专业领域,取得很大的成功。现在,专家系统得到了更为广泛的应用,并在应用开发中得到进一步发展。
专家系统存在一些不同的定义。
定义1.18专家系统是一个智能计算机程序系统。其内部含有大量的某个领域专家水平的知识与经验,能够利用人类专家的知识和解决问题的方法来处理该领域问题。也就是说,专家系统是一个具有大量的专门知识与经验的程序系统。它应用人工智能技术和计算机技术,根据某领域一个或多个专家提供的知识和经验。进行推理和判断,模拟人类专家的决策过程,以便解决那些需要人类专家处理的复杂问题。简而言之,专家系统是一种模拟人类专家解决领域问题的计算机程序系统。
此外,还有其他一些关于专家系统的定义。这里首先给出专家系统技术先行者和开拓者、美国斯坦福大学教授费根鲍姆1982年对人工智能的定义。为便于读者准确理解该定义的原意,下面用英文原文给出:
定义1.19Expert system is“an intelligent computer program that uses knowledge and inference procedures to solve problems that are difficult enough to require significant human expertise for their solutions.”That is, an expert system is a computer system that emulates the decision-making ability of a human expert.The term emulate means that the expert system is intended to act in all respects like a human expert.
下面是韦斯(Weiss)和库利柯夫斯基(Kulikowski)对专家系统的界定。
定义1.20专家系统使用人类专家推理的计算机模型来处理现实世界中需要专家做出解释的复杂问题,并得出与专家相同的结论。
专家系统是将专家系统技术和方法,尤其是工程控制论的反馈机制有机结合而建立的。专家系统已广泛应用于故障诊断、工业设计和过程控制。专家系统一般由知识库、推理机、控制规则集和算法等组成。专家系统所研究的问题一般具有不确定性,是以模仿人类智能为基础的。
2.模糊逻辑系统
扎德(L.Zadeh)于1965年提出的模糊集合理论成为处理现实世界各类物体的方法,意味着模糊逻辑技术的诞生。此后,对模糊集合和模糊控制的理论研究和实际应用进行广泛开展。1965~1975年间,扎德对许多重要概念进行研究,包括模糊多级决策、模糊近似关系、模糊约束和语言学界限等。此后10年许多数学结构借助模糊集合实现模糊化。这些数学结构涉及逻辑、关系、函数、图形、分类、语法、语言、算法和程序等。
模糊系统是一类应用模糊集合理论的智能系统。模糊系统的价值可从两个方面来考虑。一方面,模糊系统提出一种新的机制用于实现基于知识(规则)甚至语义描述的表示、推理和操作规律。另一方面,模糊系统为非线性系统提出一个比较容易的设计方法,尤其是当系统含有不确定性而且很难用常规非线性理论处理时,更是有效。
模糊集合和模糊逻辑推理是模糊系统的基础。模糊数学的基础包括模糊集合及其运算法则、模糊关系、模糊变换和模糊逻辑推理等。
模糊系统提供一种实现基于知识(规则)的,甚至语言描述的新机理。另一方面,模糊系统提供了一种改进非线性系统的替代方法。模糊系统已经得到十分广泛的应用。
3.神经网络系统
人工神经网络(Artificial Neural Network,ANN)研究的先锋麦卡洛克(McCulloch)和皮茨(Pitts)曾于1943年提出一种叫做“似脑机器”(mindlike machine)的思想,这种机器可由基于生物神经元特性的互连模型来制造,这就是神经学网络的概念。他们构造了一个表示大脑基本组分的神经元模型,对逻辑操作系统表现出通用性。随着大脑和计算机研究的进展,研究目标已从“似脑机器”变为“学习机器”,为此一直关心神经系统适应律的赫布(Hebb)提出了学习模型。罗森布拉特(Rosenblatt)命名感知器,并设计一个引人注目的结构。到20世纪60年代初期,关于学习系统的专用设计方法有威德罗(Widrow)等提出的Adaline(Adaptive Linear Element,自适应线性元)以及斯坦巴克(Steinbuch)等提出的学习矩阵。由于感知器的概念简单,因而在开始介绍时人们对它寄托很大希望。然而,不久之后明斯基和帕伯特(Papert)从数学上证明了感知器不能实现复杂逻辑功能。
到了20世纪70年代,格罗斯伯格(Grossberg)和科霍恩(Kohonen)对神经网络研究做出重要贡献。以生物学和心理学证据为基础,格罗斯伯格提出几种具有新颖特性的非线性动态系统结构。该系统的网络动力学由一阶微分方程建模,而网络结构为模式聚集算法的自组织神经实现。基于神经元组织自调整各种模式的思想,科霍恩发展了他在自组织映射方面的研究工作。沃博斯(Werbos)在70年代开发一种反向传播算法。霍普菲尔德在神经元交互作用的基础上引入一种递归型神经网络,这种网络就是有名的霍普菲尔德网络。在80年代中叶,作为一种前馈神经网络的学习算法,帕克(Parker)和鲁姆尔哈特(Rumelhart)等重新发现了反向传播算法。近十多年来,神经网络已在从家用电器到工业对象的广泛领域找到它的用武之地,主要应用涉及模式识别、图像处理、自动控制、机器人、信号处理、管理、商业、医疗和军事等领域。
神经网络由于其学习和适应、自组织、函数逼近和大规模并行处理等能力,因而具有用于智能系统的巨大潜力。神经网络在模式识别、信号处理、自动控制、系统辨识和优化等方面均有应用。将神经网络用于非线性和不确定性,以及逼近系统的辨识函数等,是十分有效的。
4.机器学习系统
学习(learning)是一个非常普遍的术语,人和计算机都通过学习获取和增加知识、改善技术和技巧。具有不同背景的人们对“学习”具有不同的看法和定义。
学习是人类的主要智能之一,在人类进化过程中,学习起到了很大作用。下面给出关于学习和学习控制的不同定义。
维纳(Wiener)于1965年对学习给出一个比较普遍的定义:
定义1.21一个具有生存能力的动物在它的一生中能够被其经受的环境所改造。一个能够繁殖后代的动物至少能够生产出与自身相似的动物(后代),即使这种相似可能随着时间变化。如果这种变化是可自我遗传的,那么,就存在一种能受自然选择影响的物质。如果该变化是以行为形式出现,并假定这种行为是无害的,那么这种变化就会世代相传下去。这种从一代至其下一代的变化形式称为种族学习(racial learning)或系统发育学习(system growth learning),而发生在特定个体上的这种行为变化或行为学习,则称为个体发育学习(individual growth learning)。
香农(C.Shannon)在1953年对学习给予较多限制的定义:
定义1.22假设①一个有机体或一部机器处在某类环境中,或者同该环境有联系;②对该环境存在一种“成功的”度量或“自适应”度量;③这种度量在时间上是比较局部的,也就是说,人们能够用一个比有机体生命期短的时间来测试这种成功的度量。对于所考虑的环境,如果这种全局的成功度量能够随时间而改善,那么我们就说对于所选择的成功度量,该有机体或机器正为适应这类环境而学习。
茨普金(Tsypkin)为学习和自学习下了较为一般的定义:
定义1.23学习是一种过程,通过对系统重复输入各种信号,并从外部校正该系统,从而系统对特定的输入作用具有特定的响应。自学习就是不具外来校正的学习,即不具奖罚的学习,它不给出系统响应正确与否的任何附加信息。
西蒙(Simon)对学习给予更准确的定义:
定义1.24学习表示系统中的自适应变化,该变化能使系统比上一次更有效地完成同一群体所执行的同样任务。
下面,综述学习系统的定义。
定义1.25学习系统(learning system)是一个能够学习有关过程的未知信息,并用所学信息作为进一步决策或控制的经验,从而逐步改善系统的性能。
定义1.26如果一个系统能够学习某一过程或环境的未知特征固有信息,并用所得经验进行估计、分类、决策或控制,使系统的品质得到改善,那么称该系统为学习系统。
定义1.27学习系统是一个能在其运行过程中逐步获得过程及环境的非预知信息,积累经验,并在一定的评价标准下进行估值、分类、决策和不断改善系统品质的智能系统。
进入21世纪以来,机器学习的研究取得了新的进展,尤其是一些新的学习方法为学习系统注入的新鲜血液,必将推动学习系统研究的进一步开展。
5.仿生进化系统
科学家和工程师们应用数学和科学来模仿自然,包括人类和生物的自然智能。人类智能已激励出高级计算、学习方法和技术。仿生智能系统就是模仿与模拟人类和生物行为的智能系统。试图通过人工方法模仿人类智能已有很长的历史了。
生物通过个体间的选择、交叉、变异来适应大自然环境。生物种群的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则。种群中的个体根据对环境的适应能力而被大自然选择或淘汰。进化过程的结果反映在个体结构上,其染色体包含若干基因,相应的表现型和基因型的联系体现了个体的外部特性与内部机理间的逻辑关系。生物通过个体间的选择、交叉、变异来适应大自然环境。生物染色体用数学方式或计算机方式来体现就是一串数码,仍叫染色体,有时也叫个体;适应能力用对应一个染色体的数值来衡量;染色体的选择或淘汰问题按求最大还是最小问题来进行。把进化计算(evolutionary computation),特别是遗传算法(Generic Algorithm,GA)机制用于人工系统和过程,则可实现一种新的智能系统,即仿生智能系统(bionic intelligent system)。
6.群智能系统
群智能系统是另一类仿生系统。假定某个团队正在执行寻宝的任务,团队内每个人都有一个金属探测器并能将自己的通讯信号和当前位置传给几个最邻近的伙伴。因此,每人都知道是否有个邻近伙伴比他更接近宝藏。如果是这种情况,你就可以向该邻近伙伴移动。这样做的结果就使得你可能更快地发现宝藏,而且,找到该宝藏也可能要比你单人寻找快得多。
这是一个对群行为(swarm behavior)的极其简单的实例,其中,群中各个体交互作用,使用比单一个体更有效的方法来寻找全局目标。
可将群(swarm)定义为某种交互作用的组织或真体(agent)的结构集合。在群智能计算研究中,群的个体组织包括蚂蚁、白蚁、蜜蜂、黄蜂、鱼群和鸟群等。在这些群体中,个体在结构上是很简单的,而它们的集体行为却可能变得相当复杂。社会组织的全局群行为是由群内个体行为以非线性方式实现的。于是,在个体行为和全局群行为间存在某个紧密的联系。这些个体的集体行为构成和支配了群行为。另一方面,群行为又决定了个体执行其作用的条件。这些作用可能改变环境,因而也可能改变这些个体自身的行为和它的地位。由群行为决定的条件包括空间和时间两种模式。
群社会网络结构形成该群存在的一个集合,它提供了个体间交换经验知识的通信通道。群社会网络结构的一个惊人的结果是它们在建立最佳蚁巢结构、分配劳力和收集食物等方面的组织能力。群计算建模已获得许多成功的应用,从不同的群研究得到不同的应用。其中,最引人注目的是对蚁群和鸟群的研究工作。其中,群优化方法是由模拟鸟群的社会行为发展起来的,而蚁群优化主要是由建立蚂蚁的轨迹跟踪行为模型而形成的。
7.多真体系统
计算机技术、人工智能、网络技术的出现与发展,突破了集中式系统的局限性,并行计算和分布式处理等技术(包括分布式人工智能)和多真体系统(Multiple Agent System,MAS)应运而生。可将真体(Agent)看作能够通过传感器感知其环境,并借助执行器作用于该环境的任何事物。当采用多真体系统进行操作时,其操作原理随着真体结构的不同而有所差异,难以给出一个通用的或统一的多真体系统结构。
定义1.28多个真体组成一个松散耦合又协作共事的系统,就是一个多真体系统。
多真体系统具有分布式系统的许多特性,如交互性、社会性、协作性、适应性和分布性等。此外,多真体系统还具有如下特点:
1)数据分布或分散;
2)计算过程异步、并发或并行;
3)每个真体具有不完全的信息和问题求解能力;
4)不存在全局控制。
多真体系统技术除了移动(migration)外,还包括分布式系统、分布式智能、计算机网络、通信、移动模型和计算、编程语言、安全性、容错和管理等关键技术。
多真体系统已获得十分广泛的应用,涉及机器人协调、过程控制、远程通信、柔性制造、网络通信、网络管理、交通控制、电子商务、数据库、远程教育和远程医疗等。
8.混合智能系统
前面介绍的几种智能系统,各自具有固有优点和缺点。例如,模糊逻辑擅长于处理不确定性,神经网络主要用于学习,进化计算是优化的高手。在真实世界中,不仅需要不同的知识,而且需要不同的智能技术。这种需求导致了混合智能系统的出现。单一智能机制往往无法满足一些复杂、未知或动态系统的系统要求,就需要开发某些混合的(或称为集成的、综合的、复合的)智能技术和方法,以满足现实问题提出的要求。
以智能控制为例,只有在出现和应用智能控制之后才有可能实现混合智能控制。所谓混合智能控制主要是指不同智能控制手段的集成,而不包括智能控制手段与非智能控制手段的集成。由此可见,混合智能控制包含十分广泛的领域,用“丰富多彩”来形容一点也不过分。混合智能系统在相当长的一段时间成为智能系统研究与发展的一种趋势,各种混合智能方案如雨后春笋般破土而出,纷纷面世。其中也的确不乏有好方案和好示例。混合能否成功,不仅取决于结合前各方的固有特性和结合后“取长补短”或“优势互补”的效果,而且也需要经受实际应用的检验。
此外,还可以按照应用领域来对智能系统进行分类,如智能机器人系统、智能决策系统、智能加工系统、智能控制系统、智能规划系统、智能交通系统、智能管理系统、智能家电系统等。
1.5人工智能的研究目标和内容
本节探讨人工智能的研究目标和主要研究内容。
1.5.1人工智能的研究目标
在前面定义人工智能学科和能力时,我们曾指出:人工智能的近期研究目标在于“研究用机器来模仿和执行人脑的某些智力功能,并开发相关理论和技术”。而且这些智力功能“涉及学习、感知、思考、理解、识别、判断、推理、证明、通信、设计、规划、行动和问题求解等活动。”下面进一步探讨人工智能的研究目标问题。
人工智能的一般研究目标为:
1)更好地理解人类智能,通过编写程序来模仿和检验人类智能的相关理论。
2)创造有用的灵巧程序,该程序能够执行一般需要人类专家才能实现的任务。
一般地,人工智能的研究目标又可分为近期研究目标和远期研究目标两种。
人工智能的近期研究目标是建造智能计算机以代替人类的某些智力活动。通俗地说,就是使现有的计算机更聪明和更有用,使它不仅能够进行一般的数值计算和非数值信息的数据处理,而且能够使用知识和计算智能,模拟人类的部分智力功能,解决传统方法无法处理的问题。为了实现这个近期目标,就需要研究开发能够模仿人类的这些智力活动的相关理论、技术和方法,建立相应的人工智能系统。
人工智能的远期研究目标是用自动机模仿人类的思维活动和智力功能。也就是说,是要建造能够实现人类思维活动和智力功能的智能系统。实现这一宏伟目标还任重道远,这不仅是由于当前的人工智能技术远未达到应有的高度,而且还由于人类对自身的思维活动过程和各种智力行为的机理还知之甚少,我们还不知道要模仿问题的本质和机制。
人工智能研究的近期目标和远期目标具有不可分割的关系。一方面,近期目标的实现为远期目标研究做好理论和技术准备,打下必要的基础,并增强人们实现远期目标的信心;另一方面,远期目标则为近期目标指明了方向,强化了近期研究目标的战略地位。
1.5.2人工智能研究的基本内容
人工智能学科有着十分广泛和极其丰富的研究内容。不同的人工智能研究者从不同的角度对人工智能的研究内容进行分类。例如,基于脑功能模拟、基于不同认知观、基于应用领域和应用系统、基于系统结构和支撑环境等。因此,要对人工智能研究内容进行全面和系统的介绍也是比较困难的,而且可能也是没有必要的。下面综合介绍一些得到诸多学者认同并具有普遍意义的人工智能研究的基本内容。
1.认知建模
浩斯顿(Houston)等将认知归纳为如下五种类型:①信息处理过程;②心理上的符号运算;③问题求解;④思维;⑤诸如知觉、记忆、思考、判断、推理、学习、想象、问题求解、概念形成和语言使用等关联活动。
人类的认知过程是非常复杂的。作为研究人类感知和思维信息处理过程的一门学科,认知科学(或称思维科学)就是要说明人类在认知过程中是如何进行信息加工的。认知科学是人工智能的重要理论基础,涉及非常广泛的研究课题。除了浩斯顿提出的知觉、记忆、思考、学习、语言、想象、创造、注意和问题求解等关联活动外,还会受到环境、社会和文化背景等方面的影响。人工智能不仅要研究逻辑思维,而且还要深入研究形象思维和灵感思维,使人工智能具有更坚实的理论基础,为智能系统的开发提供新思想和新途径。
2.知识表示
知识表示、知识推理和知识应用是传统人工智能的三大核心研究内容。其中,知识表示是基础,知识推理实现问题求解,而知识应用是目的。
知识表示是将人类知识概念化、形式化或模型化。一般地,就是运用符号知识、算法和状态图等来描述待解决的问题。已提出的知识表示方法主要包括符号表示法和神经网络表示法两种。我们将在第2章中集中讨论知识表示问题,涉及状态空间法、谓词演算法、语义网络法、框架表示法、本体表示法和神经网络表示法等。
3.知识推理
推理是人脑的基本功能。几乎所有的人工智能领域都离不开推理。要让机器实现人工智能,就必须赋予机器推理能力,进行机器推理。
所谓推理就是从一些已知判断或前提推导出一个新的判断或结论的思维过程。形式逻辑中的推理分为演绎推理、归纳推理和类比推理等。我们将在第3章和第4章中探讨逻辑演绎推理的各种方法和技术,并在专家系统和机器学习等后续篇章中研究归纳推理和类比推理等方法。知识推理,包括不确定性推理和非经典推理等,似乎已是人工智能的一个永恒研究课题,仍有很多尚未发现和解决的问题值得研究。
4.知识应用
人工智能能否获得广泛应用是衡量其生命力和检验其生存力的重要标志。20世纪70年代,正是专家系统的广泛应用使人工智能走出低谷,获得快速发展。后来的机器学习和近年来的自然语言理解应用研究取得重大进展,又促进人工智能的进一步发展。当然,应用领域的发展是离不开知识表示和知识推理等基础理论和基本技术的进步的。
我们将在第12~17章中逐一介绍智能系统的一些重要应用领域,包括智能机器人、智能控制、智能规划、智能决策、自然语言理解系统和智能交通等。
5.机器感知
机器感知就是使机器具有类似于人的感觉,包括视觉、听觉、力觉、触觉、嗅觉、痛觉、接近感和速度感等。其中,最重要和应用最广的要算机器视觉(计算机视觉)和机器听觉。机器视觉要能够识别与理解文字、图像、场景以至人的身份等;机器听觉要能够识别与理解声音和语言等。机器感知是机器获取外部信息的基本途径。要使机器具有感知能力,就要为其安上各种传感器。
6.机器思维
机器思维是对传感信息和机器内部的工作信息进行有目的地处理。要使机器实现思维,需要综合应用知识表示、知识推理、认知建模和机器感知等方面的研究成果,开展如下各方面研究工作:
1)知识表示,特别是各种不确定性知识和不完全知识的表示。
2)知识组织、积累和管理技术。
3)知识推理,特别是各种不确定性推理、归纳推理、非经典推理等。
4)各种启发式搜索和控制策略。
5)人脑结构和神经网络的工作机制。
7.机器学习
机器学习是继专家系统之后人工智能应用的又一重要研究领域,也是人工智能和神经计算的核心研究课题之一。现有的计算机系统和人工智能系统大多数没有学习能力,至多也只有非常有限的学习能力,因而不能满足科技和生产发展提出的新要求。
学习是人类具有的一种重要智能行为。机器学习就是使机器(计算机)具有学习新知识和新技术,并在实践中不断改进和完善的能力。机器学习能够使机器自动获取知识,向书本等文献资料以及与人交谈或观察环境进行学习。
8.机器行为
机器行为指智能系统(计算机、机器人)具有的表达能力和行动能力,如对话、描写、刻画,以及移动、行走、操作和抓取物体等。研究机器的拟人行为是人工智能的高难度任务。机器行为与机器思维密切相关,机器思维是机器行为的基础。
9.智能系统构建
上述智能研究内容的实现,离不开智能计算机系统或智能系统,离不开对新理论、新技术和新方法以及系统的硬件和软件支持。需要开展对模型、系统构造与分析技术、系统开发环境和构造工具以及人工智能程序设计语言的研究。一些能够简化演绎、机器人操作和认知模型的专用程序设计,以及计算机的分布式系统、并行处理系统、多机协作系统和各种计算机网络等的发展,将直接有益于人工智能的开发。
1.6人工智能与智能系统的计算方法
人工智能各个学派,不仅其理论基础不同,计算方法也不尽相同。因此,人工智能和智能系统的计算方法也不尽相同。
基于符号逻辑的人工智能学派强调基于知识的表示与推理,而不强调计算,但并非没有任何计算。图搜索、谓词演算和规则运算都属于广义上的计算。显然,这些计算是与传统的采用数理方程、状态方程、差分方程、传递函数、脉冲传递函数和矩阵方程等数值分析计算有根本区别的。随着人工智能的发展,出现了各种新的智能计算技术,如模糊计算、神经计算、进化计算、免疫计算和粒子群计算等,它们是以算法为基础的,也与数值分析计算方法有所不同。
归纳起来,人工智能和智能系统中采用的主要计算方法如下。
(1)概率计算
在专家系统中,除了进行知识推理外,还经常采用概率推理、贝叶斯推理、基于可信度推理、基于证据理论推理等不确定性推理方法。在递阶智能机器和递阶智能系统中,用信息熵计算各层级的作用。实质上,这些都是采用概率计算,属于传统的数学计算方法。
(2)符号规则逻辑运算
一阶谓词逻辑的消解(归结)原理、规则演绎系统和产生式系统,都是建立在谓词符号演算基础上的IF→THEN(如果→那么)规则运算。这种运算方法在基于规则的专家系统和专家控制系统中得到普遍应用。这种基于规则的符号运算特别适于描述过程的因果关系和非解析的映射关系等。
(3)模糊计算
利用模糊集合及其隶属度函数等理论,对不确定性信息进行模糊化、模糊决策和模糊判决(解模糊)等,实现模糊推理与问题求解。根据智能系统求解过程的一些定性知识,采用模糊数学和模糊逻辑中的概念与方法,建立系统的输入和输出模糊集以及它们之间的模糊关系。从实际应用的观点来看,模糊理论的应用大部分集中在模糊系统上,也有一些模糊专家系统将模糊计算应用于医疗诊断和决策支持。模糊控制系统主要应用模糊计算技术。
(4)神经计算
认知心理学家通过计算机模拟提出的一种知识表征理论,认为知识在人脑中以神经网络形式储存,神经网络由可在不同水平上被激活的节点组成,节点间有连接作用,并通过学习对神经网络进行训练,形成了人工神经网络学习模型。
(5)进化计算与免疫计算
可将进化计算和免疫计算用于智能系统。这两种新的智能计算方法都是以模拟计算模型为基础的,具有分布并行计算特征,强调自组织、自学习与自适应。
此外,还有群优化计算、蚁群算法等。
1.7本书内容编排
本书讨论人工智能和智能系统的基本原理、主要算法和典型应用,具体如下。
第一篇智能系统基础
包括第1~3章内容。简单介绍了人工智能和智能系统的定义、起源与发展、人工智能的各种认知观、智能系统的分类、人工智能的研究目标和内容、人工智能与智能系统的计算方法等。讨论知识表示与推理理论和算法,包括状态空间图搜索、谓词演算与消解原理、产生式系统、语义网络、框架和本体等表示、搜索推理或建模问题,还叙述了非单调推理。作为难点,提出和探讨了知识表示与搜索的两个问题,即问题的复合知识表示,启发式算法的可纳性、单调性、信息性问题。研究非经典推理理论,含有不确定性推理、概率推理、贝叶斯推理和可信度方法等,还探讨了有趣的搜索与计算复杂度问题。这些内容表现了人工智能和智能系统深厚的根基及多学科的有机交叉与结合。
第二篇智能系统原理与算法
涉及第4~11章内容。逐章研讨了专家系统、模糊逻辑系统、神经网络系统、机器学习系统、仿生进化系统、群智能系统、多真体系统和人工免疫系统的原理和算法,展示出智能系统的丰富内涵和诱人魅力。
第三篇智能系统应用与展望
包含第12~18章内容。第12~17章介绍智能系统的典型应用领域,如智能机器人系统、智能控制系统、智能规划系统、智能决策系统、自然语言理解系统和智能交通系统等,展现了智能系统的生命力和广泛的应用前景。
第18章展望了智能系统的发展前景与问题,供研究者和读者参考。
本书适用于不同层次的读者。对于高年级本科生,可作为导论性教材;对于硕士研究生和博士研究生,可作为学位课程教材或教学参考书。在本书的第一篇和第二篇中,很多章节内含有一节难点问题,可供研究生深入研究参考,而本科生可以不学习这些内容。
习题1
1-1什么是人工智能?试从学科和能力两方面加以说明。
1-2什么是智能系统?试从不同角度加以说明。
1-3在人工智能的发展过程中,有哪些思想和思潮起了重要作用?
1-4通过学习人工智能的发展历史,你有何感想?
1-5人工智能有哪些学派?它们的认知观是什么?现在这些学派的关系如何?
1-6进入21世纪以来,人工智能和智能系统发生了怎样的变化?
1-7按照作用原理,可将智能系统分为哪几类?
1-8人工智能和智能系统采用哪些计算方法?
1-9人工智能的基本研究方法有哪几类?
1-10人工智能的主要研究和应用领域是什么?其中,哪些是新的研究热点?
第 2章知识表示与推理CHAPTER2
本章研究的知识表示方法与推理技术是问题求解所必需的。表示问题是为了进一步解决问题。从问题表示到问题的解决,有一个求解的过程,即搜索过程。在这一过程中,采用适当的搜索技术,包括各种规则、过程和算法等推理技术,力求找到问题的答案。本章首先讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理,然后研究一些比较新的、能够求解复杂问题的推理技术。
2.1智能系统知识的分类与表示问题
2.1.1智能系统知识的分类
一个智能系统及其程序的高水平运行需要相关知识。在人工智能和智能系统中,知识可以分为事实知识、规则知识、控制知识和元知识四种。
(1)事实知识
事实知识是有关问题环境事物的知识,常以“……是……”的形式出现。例如事物的分类、属性、事物间关系、科学事实、客观事实等。事实是静态的、为人们共享的、可公开获得的、公认的知识,在知识库中属低层的知识。如雪是白色的、鸟有翅膀等。
(2)规则知识
规则知识是有关问题中与事物的行动、动作相联系的因果关系知识,是动态的,常以“如果……那么……”的形式出现。特别是启发式规则,它是专家提供的专门经验知识,这种知识虽无严格解释,但很有实际应用价值。
(3)控制知识
控制知识是有关问题的求解技巧性的知识,可指导如何做一件事。它也包括当有多个动作同时被激活时应选哪一个动作来执行的知识。例如,一个问题求解的算法可以看做是一种控制知识。
(4)元知识
元知识是有关知识的知识,是知识库中的高层知识。包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。元知识与控制知识是有重叠的,对一个大的程序来说,以元知识或者元规则的形式来体现控制知识更为方便,因为元知识存储于知识库中,而控制知识常与程序结合在一起出现,从而不易修改。
从知识的静态和动态特性看,知识表示可以分为陈述式知识表示与过程式知识表示。
(1)陈述式知识表示
语义网络、框架和剧本等知识表示方法,均是对知识和事实的一种静止的表达方法,称这类知识表达方式为陈述式知识表示,它强调的是事物涉及的对象是什么,是对事物有关知识的静态描述,是知识的一种显式表达形式。而对于如何使用这些知识,则通过控制策略来决定。
(2)过程式知识表示
与知识的陈述式表示相对应的是知识的过程式表示。所谓过程式知识表示就是将有关某一问题领域的知识,连同如何使用这些知识的方法一起隐式地表达为一个求解问题的过程。它所给出的是事物的一些客观规律,表达的是如何求解问题。知识的描述形式就是程序,所有信息均隐含在程序中,因而难于添加新知识和扩充功能,适用范围也较窄。
2.1.2知识表示的要求
自然语言是人类进行思维活动的主要信息载体,可以理解为人类的知识表示。将自然语言所承载的知识输入到计算机前一般先经过对实际问题进行建模,然后基于此模型实现面向机器的符号表示——一种数据结构,图2-1基于知识问题求解的一般处理过程这种数据结构就是知识表示问题。计算机对这种符号流进行处理后,形成原问题的解,再经过模型还原,最后得到基于自然语言(包括图形、图像等)表示的问题解决方案。这种处理过程可以用图2-1简要表示。
对知识表示的基本要求是所表示的知识必须能够为计算机接受和识别(可行性)。在这个前提下,知识表示还应注意以下问题:
1)合适性:所采用的知识表示方法应适合于问题的处理和求解,表示方法不能过于简单而导致不能胜任问题的求解;也不宜过于复杂而导致处理过程做了大量无用功。
2)高效性:求解算法对所用的知识表示方法、对知识的检索都应该是高效的。
3)可理解性:在既定的知识表示方法下,知识易于为用户所理解或转化为自然语言。
4)无歧义性:知识所表示的结果应该是唯一的,对用户来说是无歧义性的。
下面逐一讨论各种知识表示和知识推理的理论、算法和技术。
2.2状态空间图搜索
从本节起,将要研究如何通过网络寻找路径,进而求解问题。首先研究图搜索的一般策略,它给出图搜索过程的一般步骤,并可从中看出无信息搜索和启发式搜索的区别。
在分析了人工智能研究中运用的问题求解方法之后,就会发现许多问题求解方法是采用试探搜索方法。也就是说,这些方法是在某个可能的解空间内寻找一个解以求解问题。这种基于解答空间的问题表示和求解方法就是状态空间法,它是以状态(state)与算符(operator)为基础来表示和求解问题的。
2.2.1问题状态描述
定义2.1状态(state)是描述某类不同事物间的差别而引入的一组最少变量q0、q1、…、qn的有序集合,其矢量形式如下:Q=[q0,q1,…,qn]T(2-1)式中,每个元素qi(i=0,1,…,n)为集合的分量,称为状态变量。
定义2.2算符(operator)是使问题从一种状态变化为另一种状态的手段,也可称为操作符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。
定义2.3问题的状态空间(state space)是一个表示该问题全部可能状态及其关系的图,它包含三种说明的集合,即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G。可将状态空间记为三元状态(S、F、G)。
从上述可见,状态空间法的三个要点为:
1)状态:表示问题解法中每一步问题状况的数据结构。
2)算符:将问题从一种状态变换为另一种状态的手段。
3)状态空间:即解答空间,它是以状态与算符为基础来表示和求解问题的。
可将图搜索策略看成一种在图中寻找路径的方法。初始节点和目标节点分别代表初始数据库和满足终止条件的目标数据库。求得将一个数据库变换为另一个数据库的规则序列问题就等价于求得图中的一条路径问题。
图搜索(GRAPHSEARCH)的算法过程如下:
1)建立只含有起始节点S的搜索图G,将S放到OPEN表的未扩展节点中。
2)建立一个叫做CLOSED的已扩展节点表,其初始为空表。
3)LOOP:若OPEN表是空表,则失败退出。
4)选择OPEN表上的第一个节点n,将其从OPEN表移出并放进CLOSED表中。
5)若n为一目标节点,则有解并成功退出,此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7)步中设置)。
6)扩展节点n,同时生成不是n的祖先的那些后继节点的集合M。将M的这些成员作为n的后继节点添入图G中。
7)对那些未曾在G中出现过的(即未曾在OPEN表上或CLOSED表上出现过的)M成员设置一个通向n的指针。将M的这些成员加进OPEN表。对已经在OPEN表或CLOSED表上的每一个M成员,确定是否需要更改通向n的指针方向。对已在CLOSED表上的每个M成员,确定是否需要更改图G中通向它的每个后裔节点的指针方向。
8)按某一任意方式或按某个启发值重排OPEN表。
9)GO LOOP。
以上算法的搜索过程可用图2-2的程序框图来表示。
该过程一般包括各种具体的图搜索算法。此过程生成一个明确的图G(称为搜索图)和G的一个子集T(称为搜索树),树T上的每个节点也在图G中。搜索树是由第7)步中设置的指针来确定的。G中的每个节点(除S外)都有一个只指向G中一个父辈节点的指针,该父辈节点就定为图2-2图搜索算法过程框图树中那个节点的唯一父辈节点。搜索图形成局部的排序,因为图中没有一个后继节点是自己的祖先节点(见第6)步)。到达由算法发现的某个节点上,每条可能的路径被明确地保存在图中。对任何节点的单独一条路径是用T来定义的:粗略地说,在OPEN表上的节点都是搜索图的端节点,而在CLOSED表上的节点则不是。较确切地说,在过程的第3)步,OPEN表上的节点都是搜索树上未被扩展的那些节点;在CLOSED表上的节点,或者是几个已被扩展但是在搜索树中没有生成后继节点的端节点,或者是搜索树的非端节点。
过程的第8)步对OPEN表上的节点进行排序,以便能够从中选出一个“最好”的节点作为第4)步扩展使用。这种排序可以是任意的(即盲目的,属于盲目搜索),也可以用以后要讨论的各种启发思想或其他准则为依据(属于启发式搜索)。每当被选作扩展的节点为目标节点时,这一过程就宣告成功结束。这时,能够重现从起始节点到目标节点的这条成功路径,其办法是从目标节点按指针向S返回追溯。当搜索树不再剩有未被扩展的端节点时,过程就以失败告终(某些节点最终可能没有后继节点,所以OPEN表可能最后变成空表)。在失败终止的情况下,从起始节点出发,一定达不到目标节点。
GRAPHSEARCH算法同时生成一个节点的所有后继节点。为了说明图搜索过程的某些通用性质,将继续使用同时生成所有后继节点的算法,而不采用修正算法。在修正算法中,一次只生成一个后继节点。
从图搜索过程可以看出,是否重新安排OPEN表,即是否按照某个启发信息或准则的试探值重新对未扩展节点进行排序,将决定该图搜索过程是无信息搜索还是启发式搜索。
2.2.2无信息搜索
不需要重新安排OPEN表的搜索叫做无信息搜索或盲目搜索,它包括宽度优先搜索、深度优先搜索和等代价搜索等。盲目搜索只适用于求解比较简单的问题。
1.宽度优先搜索
如果搜索是以接近起始节点的程度依次扩展节点的,那么这种搜索就叫做宽度优先搜索(breadth-first search)。这种搜索是逐层进行的,在对下一层的任一节点进行搜索之前,必须搜索完本层的所有节点。
宽度优先搜索算法过程如下:
1)将起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答)。
2)如果OPEN是个空表,则没有解,失败退出;否则继续。
3)将第一个节点(节点n)从OPEN表移出,并将它放入CLOSED扩展节点表中。
4)扩展节点n。如果没有后继节点,则转向上述第2)步。
5)将n的所有后继节点放到OPEN表的末端,并提供从这些后继节点回到n的指针。
6)如果n的任一后继节点是个目标节点,则找到一个解答,成功退出;否则转向第2)步。
这一算法假定起始节点本身不是目标节点。要检验起始节点是目标节点的可能性,只要在第1)步的最后,加上一句“如果起始节点为一目标节点,则求得一个解答”即可做到,正如第1)步括号内所写的。这个搜索过程产生的节点和指针构成一棵隐式定义的状态空间树的子树,称为搜索树。
显而易见,宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径;这棵搜索树提供了所有存在的路径(如果没有路径存在,那么对有限图来说,表示该算法失败退出;对于无限图来说,则永远不会终止)。
此外,还有深度优先搜索、有界深度优先搜索和有界宽度优先盲目搜索算法。
2.等代价搜索
有些问题并不要求具有应用算符序列为最少的解,而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路径,与许多这样的广义准则相符合。宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题,这种推广了的宽度优先搜索算法叫做等代价搜索算法。如果所有的连接弧线具有相等的代价,那么等代价算法就简化为宽度优先搜索算法。在等代价搜索算法中,不是描述沿着等长度路径断层进行的扩展,而是描述沿着等代价路径断层进行的扩展。
在等代价搜索算法中,将从节点i到它的后继节点j的连接弧线代价记为c(i,j),将从起始节点S到任一节点i的路径代价记为g(i)。在搜索树上,假设g(i)也是从起始节点S到节点i的最小代价路径上的代价,因为它是唯一的路径。等代价搜索方法以g(i)的递增顺序扩展其节点,其算法过程如下:
1)将起始节点S放到未扩展节点表OPEN中。如果此起始节点为一目标节点,则求得一个解;否则令g(S)=0。
2)如果OPEN是个空表,则没有解而失败退出。
3)从OPEN表中选择一个节点i,使其g(i)为最小。如果有几个节点都合格,那么就要选择一个目标节点作为节点i(要是有目标节点的话);否则,就从中选一个作为节点i。将节点i从OPEN表移至扩展节点表CLOSED中。
4)如果节点i为目标节点,则求得一个解。
5)扩展节点i。如果没有后继节点,则转向第2)步。
6)对于节点i的每个后继节点j,计算g(j)=g(i)+c(i,j),并将所有后继节点j放进OPEN表。提供回到节点i的指针。
7)转向第2)步。
2.2.3启发式搜索
盲目搜索的效率低,耗费过多的计算空间与时间。如果能够找到一种方法用于排列待扩展节点的顺序,即选择最有希望的节点加以扩展,那么,搜索效率将会大为提高。在许多情况下,能够通过检测来确定合理的顺序。本节所介绍的搜索方法就是优先考虑这类检测。称这类搜索为启发式搜索(heuristic search)或有信息搜索(informed search)。
1.启发式搜索策略和估价函数
要在盲目搜索中找到一个解,所需要扩展的节点数目可能是很大的,因为这些节点的扩展次序完全是随意的,而且没有利用已解决问题的任何特性。因此,除了那些最简单的问题之外,一般都要占用很多时间或空间(或者两者均有)。这种结果是组合爆炸的一种表现形式。
有关具体问题领域的信息常常可以用来简化搜索。假设初始状态、算符和目标状态的定义都是完全确定的,然后决定一个搜索空间。因此,问题就在于如何有效地搜索这个给定空间。进行这种搜索的技术一般需要某些有关具体问题领域的特性的信息,此种信息称为启发信息,并把利用启发信息的搜索方法叫做启发式搜索方法。
利用启发信息来决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望”的节点作为下一个被扩展的节点。这种搜索叫做有序搜索(ordered search)。
一个比较灵活(但代价也较大)的利用启发信息的方法是应用某些准则来重新排列每一步OPEN表中所有节点的顺序,然后,搜索就可能沿着某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程,需要估算某些节点“希望”的量度,这种量度叫做估价函数(evolution function)。
应使路径代价与求得此路径所需要的搜索代价的某些综合指标为最小。通常,特别感兴趣的一些搜索方法是对于所有可能遇到的问题,使其平均综合指标为最小。
实际上,确定一种搜索方法是否比另一种搜索方法具有更强的启发能力的问题,往往就变成在实际应用这些方法的经验中获取有关信息的直观知识问题。
估价函数能够提供一个评定候选扩展节点的方法,以确定哪个节点最有可能在通向目标的最佳路径上。启发信息可用在GRAPHSEARCH第8)步中来排列OPEN表上的节点,使得搜索沿着那些被认为最有希望的区段扩展。一个估量某个节点“希望”程度的重要方法是对各个节点使用估价函数的实值函数。现已根据许多概念建立了估价函数:试图确定一个处在最佳路径上的节点的概率;提出任意节点与目标集之间的距离量度或差别量度;在棋盘式的博弈和难题中根据棋局的某些特点来决定棋局的得分数。这些特点被认为与向目标节点前进一步的希望程度有关。
用符号f来标记估价函数,用f(n)表示节点n的估价函数值。暂时令f为任意函数,以后将会提出f是从起始节点约束地通过节点n而到达目标节点的最小代价路径上的一个估算代价。
用函数f来排列GRAPHSEARCH第8)步中OPEN表上的节点。根据习惯,OPEN表上的节点按照f函数值的递增顺序排列。根据推测,某个具有低的估价值的节点较有可能处在最佳路径上。应用某个算法(例如等代价算法)选择OPEN表上具有最小f值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索,而其算法就叫做有序搜索算法或最佳优先算法。
2.有序搜索
有序搜索(ordered search)又称为最好优先搜索(best-first search),它总是选择最有希望的节点作为下一个要扩展的节点。
尼尔逊(Nilsson)曾提出一个有序搜索的基本算法。估价函数f是这样确定的:一个节点的希望程度越大,其f值就越小。被选为扩展的节点,是估价函数最小的节点。
有序状态空间搜索算法过程如下:
1)将起始节点S放到OPEN表中,计算f(S)并将其值与节点S联系起来。
2)如果OPEN是个空表,则失败退出,无解。
3)从OPEN表中选择一个f值最小的节点i。如果有几个节点合格,当其中有一个为目标节点时,则选择此目标节点,否则就选择其中任一个节点作为节点i。
4)将节点i从OPEN表中移出,并将它放入CLOSED扩展节点表中。
5)如果i是目标节点,则成功退出,求得一个解。
6)扩展节点i,生成其全部后继节点。对于i的每一个后继节点j:
a)计算f(j)。
b)如果j既不在OPEN表中,又不在CLOSED表中,则用估价函数f将其添入OPEN表。从j加一个指向其父辈节点i的指针,以便一旦找到目标节点时记住一个解答路径。
c)如果j已在OPEN表或CLOSED表中,则比较刚刚对j计算过的f值和前面计算过的该节点在表中的f值。如果新的f值较小,则
ⅰ)以此新值取代旧值。
ⅱ)从j指向i,而不是指向它的父辈节点。
ⅲ)如果节点j在CLOSED表中,则将其移回OPEN表。
7)转向第2)步。
步骤6)中的第c)步操作是一般搜索图所需要的,该图中可能有一个以上的父辈节点。具有最小估价函数值f(j)的节点被选为父辈节点。但是,对于搜索树,它最多只有一个父辈节点,所以步骤6)中的第c)步可以略去。值得指出的是,即使搜索空间是一般的搜索图,其显式子搜索图总是一棵树,因为节点j从来没有同时记录过一个以上的父辈节点。
宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索,选择f(i)作为节点i的深度。对于等代价搜索,f(i)是从起始节点至节点i这段路径的代价。
当然,与盲目搜索方法比较,有序搜索的目的在于减少被扩展的节点数。有序搜索的有效性直接取决于f的选择,这将敏锐地辨别出有希望的节点和没有希望的节点。不过,如果这种辨别不准确,那么有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的、准确的希望量度,那么f的选择将涉及两方面的内容:一方面是一个时间和空间之间的折中方案;另一方面是保证有一个最优的解或任意解。
正确地选择估价函数对确定搜索结果具有决定性的作用。使用不能识别某些节点真实希望的估价函数会形成非最小代价路径;而使用一个过多地估计了全部节点希望的估价函数(就像宽度优先搜索方法得到的估价函数一样)又会扩展过多的节点。
3.A*算法
令估价函数f在任意节点上其函数值f(n)能估算出从节点S到节点n的最小代价路径的代价与从节点n到某一目标节点的最小代价路径的代价之总和,也就是说f(n)是约束通过节点n的一条最小代价路径的代价的一个估计。因此,OPEN表上具有最小f值的那个节点就是所估计的加有最少严格约束条件的节点,而且下一步要扩展这个节点是合适的。
在正式讨论A*算法之前,先介绍几个有用的记号。令k(ni,nj)表示任意两个节点ni和nj之间最小代价路径的实际代价(对于两节点间没有通路的节点,函数k没有定义)。于是,从节点n到某个具体的目标节点ti,某一条最小代价路径的代价可由k(n,ti)给出。令h*(n)表示整个目标节点集合{ti}上所有k(n,ti)中最小的一个,因此,h*(n)就是从n到目标节点最小代价路径的代价,而且从n到目标节点能够获得h*(n)的任一路径就是一条从n到某个目标节点的最佳路径(对于任何不能到达目标节点的节点n,函数h*没有定义)。
通常感兴趣的是想知道从已知起始节点S到任意节点n的一条最佳路径的代价k(S,n)。为此,引进一个新函数g*,这将使记号得到某些简化。对所有从S开始可到达n的路径来说,函数g*定义为g*(n)=k(S,n)(2-2)其次,定义函数f*,使得在任一节点n上其函数值f*(n)就是从节点S到节点n的一条最佳路径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和,即f(n)=g(n)+h(n)(2-3)因而f(n)值就是从S开始约束通过节点n的一条最佳路径的代价,而f(S)=h(S)是一条从S到某个目标节点中间无约束的一条最佳路径的代价。
希望估价函数f是f的一个估计,此估计可由下式给出:f(n)=g(n)+h(n)(2-4)其中,g是g的估计;h是h的估计。对于g(n)来说,一个明显的选择就是搜索树中从S到n这段路径的代价,这一代价可以由从n到S寻找指针时,将所遇到的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从S到n的最小代价路径)。这个定义包含了g(n)≥g(n)。h(n)的估计h(n)依赖于有关问题领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。h()叫做启发函数。
A算法是一种有序搜索算法,其特点在于对估价函数的定义上。对于一般的有序搜索,总是选择f值最小的节点作为扩展节点。因此,f是根据需要找到一条最小代价路径的观点来估算节点的。可考虑每个节点n的估价函数值为两个分量:从起始节点到节点n的代价以及从节点n到达目标节点的代价。
在讨论A算法前,先做出下列定义:
定义2.4在GRAPHSEARCH过程中,如果第8)步的重排OPEN表是依据f(x)=g(x)+h(x)进行的,则称该过程为A算法。
定义2.5在A算法中,如果对所有的x存在h(x)≤h(x),则称h(x)为h(x)的下界,它表示某种偏于保守的估计。
定义2.6采用h(x)的下界h(x)为启发函数的A算法,称为A算法。当h=0时,A算法就变为有序搜索算法。
A算法的过程如下:
1)将S放入OPEN表,记f=h,令CLOSED为空表。
2)重复下列过程,直至找到目标节点为止。若OPEN为空表,则宣告失败。
3)选取OPEN表中未设置过的具有最小f值的节点为最佳节点BESTNODE,并将它放入CLOSED表。
4)若BESTNODE为目标节点,则成功求得一解。
5)若BESTNODE不是目标节点,则扩展之,产生后继节点SUCCESSOR。
6)对每个SUCCESSOR进行下列过程:
①建立从SUCCESSOR返回BESTNODE的指针。
②计算g(SUC)=g(BES)+g(BES,SUC)。
③如果SUCCESSOR∈OPEN,则称此节点为OLD,并将它添至BESTNODE的后继节点表中。
④比较新旧路径代价。如果g(SUC)<g(OLD),则重新确定OLD的父辈节点为BESTNODE,记下较小代价g(OLD),并修正f(OLD)值。
⑤若至OLD节点的代价较低或一样,则停止扩展节点。
⑥若SUCCESSOR不在OPEN表中,则查看其是否在CLOSED表中。
⑦若SUCCESSOR在CLOSED表中,则转向③。
⑧若SUCCESSOR既不在OPEN表中,又不在CLOSED表中,则将它放入OPEN表中,并添入BESTNODE后裔表,然后转向第7)步。
7)计算f值。
8)GO LOOP。
2.3谓词演算与消解原理
2.3.1谓词演算
1.谓词公式
用P(x1,x2,…,xn)表示一个n元谓词公式(Predicate Formula),其中P为n元谓词,x1,x2,…,xn为客体变量或变元。通常将P(x1,x2,…,xn)叫做谓词演算(Predicate Calculus)的原子公式,或原子谓词公式。可以用连词将原子谓词公式组成复合谓词公式,并将它叫做分子谓词公式。为此,用归纳法给出谓词公式的定义。在谓词演算中合式公式的递归定义如下:
1)原子谓词公式是合式公式。
2)若A为合式公式,则~A也是一个合式公式。
3)若A和B都是合式公式,则(A∧B)、(A∨B)、(A=>B)和(A← →B)也都是合式公式。
4)若A是合式公式,x为A中的自由变元,则(x)A和(x)A都是合式公式。
5)只有按上述规则1)至4)求得的那些公式,才是合式公式。
例2.1试将下列命题表示为谓词公式:任何整数或者为正或者为负。
解将上述命题意译如下:
对于所有的x,如果x是整数,则x或为正或为负。
用I(x)表示“x是整数”,P(x)表示“x是正数”,N(x)表示“x是负数”。于是,可将给定命题用下列谓词公式来表示:(x)(I(x)=>(P(x)∨N(x)))2.语法和语义
基本符号:谓词符号、变量符号、函数符号、常量符号、括号和逗号。
原子公式(atomic formula)是由若干谓词符号和项组成的谓词公式。原子公式是谓词演算的基本积木块。例如,要表示“机器人(ROBOT)在1号房间(r1)内”,如图2-3所示,可应用原子公式
图2-3谓词例子
当机器人ROBOT移到房间r2时,原子公式可以表示为INROOM(ROBOT,r2)这两个原子公式的通用形式即
又如,“李的母亲和他的父亲结婚”这句话的原子公式表示如下
3.连词和量词
(1)连词
1)与·合取(conjunction)。
合取就是用连词“∧”把几个公式连接起来而构成的公式。合取项是合取式的每个组成部分。
例如,LIKE(I,MUSIC)∧LIKE(I,PAINTING)
(我喜爱音乐和绘画)
2)或·析取(disjunction)。
析取就是用连词“∨”将几个公式连接起来而构成的公式。析取项是析取式的每个组成部分。
又如,PLAYS(LILI,BASKETBALL)∨PLAYS(LILI,FOOTBALL)
(李力打篮球或踢足球)
3)蕴涵(implication)。
蕴涵“=>”表示“如果……那么……”的语句。用连词“=>”连接两个公式所构成的公式叫做蕴涵。
IF=>THEN
前项后项
(左式)(右式)
例如,RUNS(LIUHUA,FASTEST)=>WINS(LIUHUA,CHAMPION)
(如果刘华跑得最快,那么他取得冠军)
4)非(not)。
非表示否定,~、┑也均可表示否定。
例如,~INROOM(ROBOT,r2)
(机器人不在2号房间内)
(2)量词
1)全称量词(universal quantifier)。
若一个原子公式P(x)对于所有可能变量x都具有T值,则用(x)P(x)表示。
例如,(x)[ROBOT(x)=>COLOR(x,GRAY)]
(所有的机器人都是灰色的)
(x)[Student(x)=>Uniform(x,Color)]
(所有学生都穿彩色制服)
2)存在量词(existential quantifier)。
若一个原子公式P(x)至少有一个变元x可使P(x)为T值,则用(x)P(x)表示。
例如,(x)INROOM(x,r1)
(1号房间内有一个物体)
量词变元(quantified variable)就是被量化了的变元x约束的变量。
4.谓词演算
如果P和Q是两个合式公式,则由这两个合式公式所组成的复合表达式可由表2-1所示的真值表给出。
表2-1真值表PQP∨QP∧QP=>Q~PTTTTTFFTTFTTTFTFFFFFFFTT
如果两个合式公式无论如何解释其真值表都是相同的,那么就称此两合式公式是等价的。应用上述真值表,能够确立下列等价关系:
(1)否定之否定
~(~P)等价于P
(2)P∨Q等价于~P=>Q
(3)狄·摩根定律
~(P∨Q)等价于~P∧~Q
~(P∧Q)等价于~P∨~Q
(4)分配律
P∧(Q∨R)等价于(P∧Q)∨(P∧R)
P∨(Q∧R)等价于(P∨Q)∧(P∨R)
(5)交换律
P∧Q等价于Q∧P
P∨Q等价于Q∨P
(6)结合律
(P∧Q)∧R等价于P∧(Q∧R)
(P∨Q)∨R等价于P∨(Q∨R)
(7)逆否律
P=>Q等价于~Q=>~P
此外,还可建立下列等价关系:
(8)~(x)P(x)等价于(x)[~P(x)]
~(x)P(x)等价于(x)[~P(x)]
(9)(x)[P(x)∧Q(x)]等价于(x)P(x)∧(x)Q(x)
(x)[P(x)∨Q(x)]等价于(x)P(x)∧(x)Q(x)
(10)(x)P(x)等价于(y)P(y)
(x)P(x)等价于(y)P(y)
上述最后两个等价关系说明,在一个量词的表达式中的约束变量是一种虚元,它可以用任何一个不在表达式中出现过的其他变量符号来代替。
下面列举一个用谓词演算来表示的英文句子的实例:
For every set x,there is a set y,such that the cardinality of y is greater than the cardinality of x.
这个英文句子可用谓词演算表示为(x){SET(x)=>(y)(u)(v)[SET(y)∧CARD(x,u)∧CARD(y,v)∧G(v,u)]}2.3.2置换与合一
1.置换
在谓词逻辑中,有些推理规则可应用于一定的合式公式和合式公式集,以产生新的合式公式。一个重要的推理规则是假元推理,这就是由合式公式W1和W1=>W2产生合式公式W2的运算。另一个推理规则叫做全称化推理,它是由合式公式(x)W(x)产生合式公式W(A),其中A为任意常量符号。同时应用假元推理和全称化推理,例如,可由合式公式(x)[W1(x)=>W2(x)]和W1(A)生成合式公式W2(A)。这就是寻找A对x的置换(substitution),使W1(A)与W1(x)一致。
一个表达式的项可为变量符号、常量符号或函数表达式。函数表达式由函数符号和项组成。一个表达式的置换就是在该表达式中用置换项置换变量。
置换是可结合的。用s1s2表示两个置换s1和s2的合成。L表示一表达式,则有(Ls1)s2=L(s1s2)以及(s1s2)s3=s1(s2s3)
即用s1和s2相继作用于表达式L与s1s2作用于L是一样的。
一般说来,置换是不可交换的,即s1s2≠s2s12.合一
寻找项对变量的置换,以使两表达式一致,叫做合一(unification)。合一是人工智能中很重要的过程,它是一些推理的基础。
如果一个置换s作用于表达式集{Ei}的每个元素,则用{Ei}s来表示置换例的集。称表达式集{Ei}是可合一的。如果存在一个置换s使得E1s=E2s=E3s=…那么称此s为{Ei}的合一者,因为s的作用是使集合{Ei}成为单一形式。
消解是一种可用于一定子句公式的重要推理规则。子句定义为由文字的析取组成的公式(一个原子公式和原子公式的否定都叫做文字)。当消解可使用时,消解过程被应用于母体子句对,以产生一个导出子句。例如,如果存在某个公理E1∨E2和另一公理~E2∨E3,那么E1∨E3在逻辑上成立。这就是消解,而称E1∨E3为E1∨E2和~E2∨E3的消解式(resolvent)。
3.子句集的求取
在说明消解过程之前,首先说明任一谓词演算公式可以化成一个子句集。变换过程由下列步骤组成。
(1)消去蕴涵符号
只应用∨和~符号,以~A∨B替换A=>B。
(2)减少否定符号的辖域
每个否定符号~最多只用到一个谓词符号上,并反复应用狄·摩根定律。例如:
以~A∨~B代替~(A∧B)
以~A∧~B代替~(A∨B)
以A代替~(~A)
以(x){~A}代替~(x)A
以(x){~A}代替~(x)A
(3)对变量标准化
在任一量词辖域内,受该量词约束的变量为一哑元(虚构变量),它可以在该辖域内处处统一地被另一个没有出现过的任意变量所代替,而不改变公式的真值。合式公式中变量的标准化意味着对哑元改名以保证每个量词有其唯一的哑元。例如,将(x){P(x)(x)Q(x)}标准化而得到(x){P(x)(y)Q(y)}(4)消去存在量词
在公式(y)〔(x)P(x,y)〕中,存在量词是在全称量词的辖域内,人们允许所存在的x可能依赖于y值。这种依赖关系明显地由函数g(y)定义,它将每个y值映射到存在的x,这种函数叫做Skolem函数。如果用Skolem函数代替存在的x,就可以消去全部存在量词,并写成(y)P[g(y),y]从一个公式消去一个存在量词的一般规则是以一个Skolem函数代替每个出现的存在量词的量化变量,而这个Skolem函数的变量就是由那些全称量词所约束的全称量词量化变量,这些全称量词的辖域包括要被消去的存在量词的辖域在内。Skolem函数所使用的函数符号必须是新的,即不允许是公式中已经出现过的函数符号。例如,(y)(x)P(x,y)被〔(y)P(g(y),y)〕代替,其中g(y)为一个Skolem函数。
如果要消去的存在量词不在任何一个全称量词的辖域内,那么就用不含变量的Skolem函数,即常量。例如,(x)P(x)化为P(A),其中常量符号A用来表示人们知道的存在实体。A必须是个新的常量符号,它未曾在公式中其他地方使用过。
(5)化为前束形
到这一步,已不留下任何存在量词,而且每个全称量词都有自己的变量。将所有全称量词移到公式的左边,并使每个量词的辖域包括这个量词后面公式的整个部分,所得公式称为前束形。前束形公式由前缀和母式组成,前缀由全称量词串组成,母式由没有量词的公式组成,即前束形=(前缀)全称量词串(母式)无量词公式(6)将母式化为合取范式
任何母式都可写成由一些谓词公式和(或)谓词公式的否定的析取的有限集组成的合取。这种母式叫做合取范式。可以反复应用分配律将任一母式化成合取范式。
例如,将A∨{B∧C}化为
{A∨B}∧{A∨C}
(7)消去全称量词
到了这一步,所有余下的量词均被全称量词量化了。同时,全称量词的次序也不重要了。因此,可以消去前缀,即消去明显出现的全称量词。
(8)消去连词符号∧
用{A,B}代替(A∧B)以消去明显的符号∧。反复代替,最后得到一个有限集,其中每个公式是文字的析取。任一个只由文字的析取构成的合式公式叫做一个子句。
(9)更换变量名称
可以更换变量符号的名称,使一个变量符号不出现在一个以上的子句中。
2.3.3消解原理
1.消解推理规则
令L1为任一原子公式,L2为另一原子公式;L1和L2具有相同的谓词符号,但一般具有不同的变量。已知两子句L1∨α和~L2∨β,如果L1和L2具有最一般合一者σ,那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β)σ。这个新子句叫做消解式,它是取这两个子句的析取后消去互补对得到的。
下面举出几个从父辈子句求消解式的例子。
(1)假言推理
(2)合并
(3)重言式
(4)空子句(矛盾)
(5)链式(三段论)
由以上各例可见,消解可以合并几个运算为一个简单的推理规则。
2.含有变量的消解式
上述简单的对基子句的消解推理规则可推广到含有变量的子句。为了对含有变量的子句使用消解规则,必须找到一个置换,作用于父辈子句使其含有互补文字。
下面举几个对含有变量的子句使用消解的例子。
例2.2
例2.3
例2.4
本节中对基子句和对含有变量的子句进行消解的例子,其父辈子句和消解式列表示见表2-2。这些例子表示出了消解推理的某些常用规则。
表2-2子句和消解式父辈子句消解式P和~P∨Q(即P=>Q)QP∨Q和~P∨QQP∨Q和~P∨~QQ∨~Q和P∨~P~P和PNIL~P∨Q(即P=>Q)和~Q∨R(即Q=>R)~P∨R(即P=>R)B(x)和~B(x)∨C(x)C(x)P(x)∨Q(x)和~Q(f(y))P(f(y)),σ={f(y)/x}P(x,f(y))∨Q(x)∨R(f(a),y)Q(f(f(a)))∨R(f(a),y)∨R(f(y),w)和~P(f(f(a)),z)∨R(z,w)σ={f(f(a))/x,f(y)/z}[BG]F
3.消解反演求解过程
可以将要解决的问题作为一个要证明的命题,消解通过反演产生证明。也就是说,要证明某个命题,其目标公式被否定并化成子句形,然后添加到命题公式集中,将消解反演系统应用于联合集,并推导出一个空子句(NIL),产生一个矛盾,从而使定理得到证明。这种消解反演的证明思想与数学中反证法的思想十分相似。
(1)消解反演
给出一个公式集S和目标公式L,通过反证或反演来求证目标公式L,其证明步骤如下:
1)否定L,得~L;
2)将~L添加到S中去;
3)将新产生的集合{~L,S}化成子句集;
4)应用消解原理,力图推导出一个表示矛盾的空子句。
可以简单讨论一下用反演证明过程的正确性。设公式L在逻辑上遵循公式集S,那么按照定义满足S的每个解释也满足L。绝不会有满足S的解释能够满足~L的,所以不存在能够满足并集S∪{~L}的解释。如果一个公式集不能被任一解释满足,那么这个公式是不可满足的。因此,如果L在逻辑上遵循S,那么S∪{~L}是不可满足的。可以证明,如果消解反演反复应用到不可满足的子句集,那么最终将要产生空子句(NIL)。因此,如果L在逻辑上遵循S,那么由并集S∪{~L}消解得到的子句,最后将产生空子句;反之可以证明,如果从S∪{~L}的子句消解得到空子句,那么L在逻辑上遵循S。
(2)反演求解过程
从反演树求取对某个问题的答案,其过程如下:
1)将由目标公式的否定产生的每个子句添加到目标公式否定之否定的子句中。
2)按照反演树,执行和以前相同的消解,直至在根部得到某个子句为止。
3)用根部的子句作为一个回答语句。
答案求取涉及将一棵根部有空子句(NIL)的反演树变换为在根部带有可用作答案的某个语句的一棵证明树。由于变换关系涉及将由目标公式的否定产生的每个子句变换为一个重言式,所以被变换的证明树就是一棵消解的证明树,其在根部的语句在逻辑上遵循公理加上重言式,因而也单独地遵循公理。因此被变换的证明树本身就证明了求取办法是正确的。
2.4产生式系统
1943年,美国逻辑学家波斯特(Post)首先提出产生式系统(production system),其中使用产生式规则来表示知识。这种表示方法刻画了各种知识块之间的因果关系,揭示了人类求解问题的行为特征,并通过“认识→行动”的循环过程求解问题。其优点是形式简单、意义明了,各产生式规则彼此独立,符合人类的认知过程,成为常用的知识表示方法之一。他们用这种规则对符号串进行置换运算。后来,纽厄尔和西蒙在1965年利用该原理建立了一个人类的认知模型。同时,斯坦福大学用产生式系统结构设计出第一个专家系统DENDRAL。
2.4.1产生式系统的组成与表示
产生式系统用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。在产生式系统中,论域的知识分为两部分:用事实表示静态知识,如事物、事件和它们之间的关系;用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则,因此又将此类系统称为基于规则的系统(rule-based system)。
产生式系统表达自然直观,便于推理,可进行模块化处理,格式清晰,设计和检测方便,表示灵活,因而曾得到广泛应用。不过,产生式系统因求解效率低和无法表示结构性知识,使其不适用于求解复杂系统。
产生式规则是表示一种因果关系或推理关系,通常用下列形式表示:IFPTHENQ(如果P则Q)(2-5)或者P→Q(2-6)其中,P称为条件、前项或产生式的左边,Q称为操作、结果或产生式的右边。其含义是“如果P被满足,则可推出结论Q,或应该执行操作Q”。
需要指出的是,在谓词逻辑法中有“P=>Q”形式的蕴涵式,但这种蕴涵式与这里讲的产生规则有很大的区别。在谓词逻辑法中,蕴涵式“P=>Q”是一种谓词公式,符合逻辑公式的所有要求,P和Q也都要求是谓词公式;但这里的产生式规则“P→Q”比蕴涵式“P=>Q”更为广泛,它可以是谓词逻辑法中的蕴涵式,也可以不是。例如,P和Q可以是谓词公式以外的其他符号,这时“P→Q”也不再是谓词公式,它没有真值。
实际上,P通常是在实践中观察得到的现象、事实的符号表示,Q则是相应的操作或结果,它们不限于逻辑上的公式,因而超越了逻辑上的束缚,使得我们可以轻易地表示任何两个概念之间的因果关系(即使我们目前无法验证这种关系的逻辑内涵)。例如,如果我们多次观察到:现象1出现后随之发生现象2,则可以建立如下的规则“现象1→现象2”,而不必去研究现象1和现象2之间的逻辑关系。这样,就为知识获取提供了基于观察的解决方案(即使这种方案不是完全正确的),这对工程实践十分重要。
产生式系统由三个部分组成,即总数据库(或全局数据库)、产生式规则和控制策略。各部分间的关系如图2-4所示。总数据库又称为综合数据库、上下文、黑板等,用于存放求解过程中各种当前信息的数据结构,如问题的初图2-4产生式系统的主要组成始状态、事实或证据、中间推理结论和最后结果等。当产生式规则中某条规则的前提与总数据库中的某些事实相匹配时,该规则就被激活,并将其结论作为新的事实存入总数据库。产生式规则是一个规则库,用于存放与求解问题有关的某个领域知识的规则集合及其交换规则。规则库知识的完整性、一致性、准确性、灵活性和知识组织的合理性,将对产生式系统的运行效率和工作性能产生重要影响。
控制策略为一推理机构,由一组程序组成,用来控制产生式系统的运行,决定问题求解过程的推理线路,实现对问题的求解。其主要任务如下:
1)按一定策略从规则库中选择与总数据库中的已知事实相匹配的规则。即将所选规则的前提与总数据库中的已知事实进行比较,若事实与所选规则前提一致,则匹配成功,该规则可被使用;否则,匹配失败,该规则不可用于当前推理。
2)当存在多条匹配成功的规则时,控制策略能够按照某种策略从中选出一条适合的规则去执行。
3)如果要执行规则的右部不是问题的目标,且为一个或多个结论时,则将这些结论加入到总数据库中;当其为一个或多个操作时,执行这些操作。
4)如果要执行规则的右部满足问题的结束条件时,则停止推理。
5)记住问题求解过程应用过的规则序列,以便求解结束时能够给出问题的解答路径。
产生式系统的控制策略随搜索方式的不同分为可撤回策略、回溯策略、图搜索策略等。
产生式规则是一个以“如果满足这个条件,就应当采取某些操作”形式表示的语句,其基本形式为
IF前提THEN结论
例如,规则
如果某种动物是哺乳动物,并且吃肉
那么这种动物被称为食肉动物
在产生式系统的执行过程中,如果某条规则的条件满足了,那么,就可以应用这条规则。也就是说,系统的控制部分可以执行规则的操作部分。产生式的两边可用谓词逻辑、符号和语言的形式,或用很复杂的过程语句来表示。这取决于所采用数据结构的类型。附带说明一下,这里所说的产生式规则和谓词逻辑中所讨论的产生式规则,从形式上看都采用了“IF THEN”的形式,但这里所讨论的产生式更为通用。在谓词运算中,“IF THEN”实质上是表示蕴涵关系。也就是说要满足相应真值表。这里所讨论的条件和操作部分除了可以用谓词逻辑表示外,还可以有其他多种表示形式,并不受相应真值表的限制。
总数据库有时也称为上下文、当前数据库或暂时存储器。总数据库是产生式规则的注意中心。产生式规则的左边表示在启用这一规则之前总数据库内必须准备好的条件。例如在上述例子中,在得出该动物是食肉动物的结论之前,必须在总数据库中存有“该动物是哺乳动物”和“该动物吃肉”这两个事实。执行产生式规则的操作会引起总数据库的变化,这就使其他产生式规则的条件可能被满足。
控制策略的作用是说明下一步应该选用什么规则,也就是如何应用规则。通常从选择规则到执行操作分为三步:匹配、冲突解决和操作。
1.匹配
在这一步,将当前数据库与规则的条件部分相匹配。如果两者完全匹配,则将这条规则称为触发规则。当按规则的操作部分去执行时,称这条规则为启用规则。被触发的规则不一定总是启用规则,因为可能同时有几条规则的条件部分被满足,这就要在“冲突解决”步骤中来解决这个问题。在复杂的情况下,在数据库和规则的条件部分之间可能要进行近似匹配。
2.冲突解决
当有一条以上规则的条件部分和当前数据库相匹配时,就需要决定首先使用哪一条规则,这称为冲突解决。例如,设有以下两条规则。R1IFfourth dawn
short yardage
THENpunt
R2IFfouth dawn
short yardage
within 30 yards(from the goal line)
THENfield goal这是两条关于美式足球的规则。R1规则规定进攻一方如果在前三次进攻中前进的距离少于10码(short yardage),那么在第四次进攻(fourth dawn)时,可以踢悬空球(punt)。R2规则规定,如果进攻这一方在前三次进攻中前进的距离少于10码,而进攻的位置又在离对方球门线30码距离之内,那么就可以射门(field goal)。
如果当前数据库包含事实fourth dawn和short yardage,以及within 30 yards时,则上述两条规则都被触发,这就需要用冲突解决来决定首先使用哪一条规则。有很多种冲突解决策略,其中一种策略是先使用规则R2,因为R2的条件部分包含了更多的限制,因此规定了一个更为特殊的情况。这是一种按专一性来编排顺序的策略,称为专一性排序。还有不少其他的冲突解决策略,如规则排序、数据排序、规模排序和就近排序等。
3.操作
操作就是执行规则的操作部分,经过操作以后,当前数据库将被修改。然后,其他的规则有可能被使用。
2.4.2产生式系统的推理
产生式系统的问题求解过程即为对解空间的搜索过程,也就是推理过程。按照搜索方向可将产生式系统分为正向推理、逆向推理和双向推理。正向推理又称为事实(或数据)驱动推理、前向链接推理;逆向推理又称为目标驱动推理、逆向链接推理。
1.正向推理
正向推理从一组表示事实的谓词或命题出发,使用一组产生式规则,用以证明该谓词公式或命题是否成立。设有下列规则集合R1至R3:
R1:P1→P2
R2:P2→P3
R3:P3→P4
其中,P1、P2、P3和P4为谓词公式或命题。设总数据库中已存在事实P1,则应用规则R1、R2、R3进行正向推理,其过程如图2-5所示。
实现正向推理的一般策略是:先提供一批事实(数据)到总数据库中。系统利用这些事实与规则的前提相匹配,触发匹配成功的规则,将其结论作为新的事实添加到总数据库中。继续上述过程,用更新过的总数据库的所有事实再与规则库中另一条规则匹配,用其结论再次修改总数据库的内容,直到没有可匹配的新规则,不再有新的事实加到总数据库中为止。当产生式系统的左部和右部是用谓词表示时,全局规则的前提与总数据库中的事实相匹配意味着对左部谓词中出现的变量进行统一的置换,使置换后的左部谓词成为总数据库中某个谓词的实例,使左部谓词实例与总数据库中的某个事实相同。执行右部是指当左部匹配成功时,用左部匹配时使用的相同变量,并按相同方式对右部谓词进行置换,将置换结果(即右部谓词实例)加入总数据库。
2.逆向推理
逆向推理从表示目标的谓词或命题出发,使用一组产生式规则证明事实谓词或命题成立,即首先提出一批假设目标,然后逐一验证这些假设。如果使用前述三条规则R1至R3,则逆向推理过程如图2-6所示。
图2-5正向推理过程图2-6逆向推理过程首先假设目标P4成立,由规则3(P3→P4)必须先验证P3成立才能证明P4成立。不过,总数据库中不存在事实P3,所以只能假设子目标P3成立。由规则2(P2→P3),应验证P2;同样因总数据库中不存在事实P2,假设子目标P2成立。再由规则1(P1→P2),要验证P2成立必须先验证P1。因总数据库中没有事实P1,所以假设子目标P1成立,并最后得出P4成立的结论。
要实现逆向推理,其策略如下:首先假设一个可能的目标,然后由产生式系统试图证明此假设目标是否在总数据库中。若在总数据库中,则该假设目标成立;否则,若该假设为终叶(证据)节点,则询问用户。若不是,则再假定另一个目标,即寻找结论部分包含该假设的那些规则,将它们的前提作为新的假设,并力图证明其成立。这样反复进行推理,直到所有目标均获证明或者所有路径都得到测试为止。
从上面的讨论可知,正向推理和逆向推理各有其特点和适用场合。正向推理由事实(数据)驱动,从一组事实出发推导结论。其优点是算法简单、容易实现,允许用户一开始就将有关的事实数据存入数据库,在执行过程中系统能够很快获得这些数据,而不必等到系统需要数据时才向用户询问。其主要特点是盲目搜索,可能会求解许多与总目标无关的子目标,每当总数据库内容更新后都要遍历整个规则库,推理效率较低。因此,正向推理策略主要用于已知初始数据。而无法提供推理目标,或解空间很大的一类问题,如监控、预测、规划、设计等问题的求解。
逆向推理由目标驱动,从一组假设出发验证结论。其优点是搜索目的性强、推理效率高。缺点是目标的选择具有盲目性,可能会求解许多假的目标;当可能的结论数目很多,即目标空间很大时,推理效率不高;当规则的右部是执行某种动作(如打开阀门)而不是结论时,逆向推理不便使用。因此逆向推理主要用于结论单一或者已知目标结论,而要求验证的系统,如选择、分类、故障诊断等问题的求解。正、逆向推理策略比较见表2-3。
表2-3正、逆向推理的比较比较内容正向推理逆向推理驱动方式数据驱动目标驱动推理方法从一组数据出发向前推导结论从可能的解答出发,向后推理验证解答启动方法从一个事件启动由询问关于目标状态的一个问题而启动透明程度不能解释其推理过程可解释其推理过程推理方向由底向上推理由顶向下推理典型系统CLIPS、OPSPROLOG
3.双向推理
双向推理又称为正反向混合推理,它综合了正向推理和逆向推理的长处,克服了两者的短处。双向推理的推理策略是同时从目标向事实推理和从事实向目标推理,并在推理过程中的某个步骤实现事实与目标的匹配。具体的推理策略有多种。例如,通过数据驱动帮助选择某个目标,即从初始证据(事实)出发进行正向推理,同时以目标驱动求解该目标,通过交替使用正逆向混合推理对问题进行求解。双向推理的控制策略比前两种方法都要复杂。美国斯坦福研究所人工智能中心研制的基于规则的专家系统工具KAS,就是采用正逆向混合推理的产生式系统的一个典型例子。
双向混合推理过程的示意图如图2-7所示。
图2-7双向混合推理过程
2.5语义网络法
语义网络是知识的一种结构化图解表示,它由节点和弧线或链线组成。节点用于表示实体、概念和情况等,弧线用于表示节点间的关系。
1)语义网络表示由下列4个相关部分组成:
①词法部分:决定表示词汇表中允许有哪些符号,它涉及各个节点和弧线。
②结构部分:叙述符号排列的约束条件,指定各弧线连接的节点对。
③过程部分:说明访问过程,这些过程能用来建立和修正描述,以及回答相关问题。
④语义部分:确定与描述相关的(联想)意义的方法,即确定有关节点的排列及其占有物和对应弧线。
2)语义网络具有下列特点:
①能将实体的结构、属性与实体间的因果关系显式和简明地表达出来,与实体相关的事实、特征和关系可以通过相应的节点弧线推导出来,以联想方式实现对系统的解释。
②由于在一个节点中组织与概念相关的属性和联系,因而易于访问和学习概念。
③表现问题更加直观,更易于理解,适于知识工程师与领域专家沟通。语义网络中的继承方式也符合人类的思维习惯。
④语义网络结构的语义解释依赖于该结构的推理过程而没有结构的约定,因而得到的推理不能保证和谓词逻辑法一样有效。
⑤节点间的联系可能是线状、树状或网状的,甚至是递归状的结构,使相应的知识存储和检索可能需要比较复杂的过程。
系列图书推荐
多Agent系统编程实践
- ¥79.00
- ¥55.30
- 多Agent系统编程实践
知识图谱实战:构建方法与行业应用
- ¥99.00
- ¥49.50
- 知识图谱实战:构建方法与..
基于NLP的内容理解
- ¥99.00
- ¥49.50
- 基于NLP的内容理解
机器视觉入门与实战:人脸识别与人体识别
- ¥89.00
- ¥62.30
- 机器视觉入门与实战:人脸..
Python深度学习:基于PyTorch 第2版
- ¥109.00
- ¥54.50
- Python深度学习:基于PyTo..
作者其它作品
人工智能及其应用(第4版)
- ¥39.00
- ¥33.15
- 人工智能及其应用(第4版)..
机器人学-第二版
- ¥42.00
- ¥35.70
- 机器人学-第二版
机器人学基础
- ¥23.00
- ¥19.55
- 机器人学基础
智能控制原理与应用
- ¥35.00
- ¥31.50
- 智能控制原理与应用
智能控制(第二版)
- ¥29.00
- ¥26.10
- 智能控制(第二版)
同类热销商品
大教堂与集市[图书]
- ¥59.00
- ¥59.00
- 大教堂与集市[图书]
深入理解C++11:C++11新特性解析与应用[按需印刷]
- ¥69.00
- ¥69.00
- 深入理解C++11:C++11新特..
深入浅出DPDK[图书]
- ¥69.00
- ¥69.00
- 深入浅出DPDK[图书]
深入理解BootLoader[按需印刷]
- ¥59.00
- ¥59.00
- 深入理解BootLoader[按需..
Linux高性能服务器编程[图书]
- ¥89.00
- ¥89.00
- Linux高性能服务器编程[图..