人工智能与计算智能概述

1人工神经网络（ArtificialNeuralNetworks,ANN）裴振奎peizhk@126.com计算机与通信工程学院计算机科学系人工智能与计算智能概述第1页教材及参考书（1）人工神经网络导论，蒋宗礼编著，高等教育出版社（2）人工神经网络原理及仿真实例(第2版)，高隽编著，

机械工业出版社（3）人工神经网络与模拟进化计算(第2版),阎平凡、张长水编著

清华大学出版社（4）神经网络模型及MATLAB仿真程序设计,周开利编著,

清华大学出版社（5）神经网络(英文影印版),SatishKumar著,清华大学出版社

教材及参考书人工智能与计算智能概述第2页

人工神经网络计算智能人工智能人工智能这个词看起来似乎一目了然，人制造智能，不过要给人工智能这个科学名词下一个准确定义却很困难。智能是个体有目标行为、合理思维以及有效适应环境综合性能力。通俗地讲，智能是个体认识客观事物和利用知识处理问题能力。尤其指出智能是相正确、发展，假如离开特定时间说智能是困难、没有意义。人工智能介绍人工智能与计算智能概述第3页人工智能是相对于人自然智能而言，即经过人工方法和技术，研制智能机器或智能系统来模仿、延伸和扩展人智能，实现智能行为和“机器思维”活动，处理需要人类教授才能处理问题。本质上讲，人工智能是研究怎样让计算机模仿人脑从事推理、规划、设计、思索和学习等思维活动，处理需要人类智能才能处理复杂问题。简单地讲，人工智能就是由计算机来表示和执行人类智能活动。人工智能与计算智能概述第4页远期目标是建立信息处理智能理论，制造智能机器。智能机器是指能够在各类环境中自主地或交互执行各种拟人任务，与人智力相当或相近机器。详细地讲，这就要求使计算机能够了解人类语言，并能够进行学习和推理。近期目标是处理制造智能机器或智能系统相关原理和技术问题，以实现部分智能。

人工智能研究目标人工智能与计算智能概述第5页1.2人工智能发展简史第一阶段——孕育期（1956年以前）第二阶段——人工智能基础技术研究和形成（1956年—1970年）第三阶段——发展和实用化阶段（1971年—1980年）第四阶段——知识工程与教授系统（1980年至今）人工智能与计算智能概述第6页第一阶段——孕育期公元前，古希腊哲学家亚里士多德（Aristotle）创建了古典形式逻辑。17世纪，英国哲学家和自然科学家培根（F.Bacon）系统地提出了古典归纳推理。17世纪，德国数学家莱布尼茨（G.W.Leibniz）提出了数理逻辑基本思想。1642年，法国物理学家和数学家帕斯卡（B.Pascal）创造了世界上第一台会演算机械加法机。1673年，Leibniz在这台加法机基础上发展并制成了可进行四则运算计算器。1832年，英国数学家巴比奇（C.Babbage）制成可用来计算简单数学表差分机，并提出分析机（能自动完成各种类型数字计算）设计思想。19世纪中叶，英国数学家布尔（G.Boole）出了布尔代数，初步实现了Leibniz数理逻辑思想。人工智能与计算智能概述第7页1879年，德国逻辑学家费雷治（G.Frege）提出用机械推理符号表示系统，创造了谓词逻辑。1930年，奥地利数学家歌德尔（K.Godel）证实了一阶谓词完备性定理。1936年，英国数学家Turing提出了一个理想计算机数学模型（即图灵机）；在1950年，他还提出了著名“图灵测验”，给智能标准提供了明确定义。1943年，美国神经生理学家麦卡洛（W.McCulloch）和数理逻辑学家匹茨（W.Pitts）提出了第一个神经元数学模型（M-P模型），开创了神经科学研究新时代。1945年，美籍匈牙利数学家冯·诺依曼（J.V.Neumann）提出了以二进制和程序存放控制为关键通用电子数字计算机体系结构原理，奠定了当代电子计算机体系结构基础。1946年，美国数学家莫克利（J.W.Mauchly）和埃克特（J.P.Eckert）研制成功了世界上第一台通用电子数字计算机ENIAC（ElectronicNumericalIntegratorAndCalculator）。1949年，加拿大心理学家赫布（D.O.Hebb）提出了关于神经元连接强度Hebb规则。Hebb学习规则为神经网络学习算法研究奠定了基础。人工智能与计算智能概述第8页第二阶段——人工智能基础技术研究和形成

1956年夏，美国达特茅斯（Dartmouth）大学麦卡锡（J.McCarthy）、哈佛大学明斯基（M.Minsky）、IBM企业罗彻斯特（N.Lochester）和贝尔试验室香农（E.Shannon）四人共同发起，邀请IBM企业摩尔（T.More）和塞缪尔（A.Samuel）、麻省理工学院塞弗里奇（O.Selfridge）和门罗索夫（R.Solomonff）、卡内基-梅隆大学西蒙（H.Simon）和纽厄尔（A.Newell）等人参加学术讨论班，在一起共同学习和探讨用机器模拟智能各种问题。Minsky构建第一个神经元网络模拟器SNARC（StochasticNeural-AnalogReinforcementComputer）、McCarthyα-β搜索法、以及Simon和Newell逻辑理论家程序（LogicTheorist）成为这次研讨会三个亮点。经McCarthy提议，决定使用“人工智能”一词来概括这个研究方向。这次含有历史意义会议标志着人工智能这个学科正式诞生，McCarthy也由此被称为“人工智能之父”。人工智能与计算智能概述第9页1956年，Newell和Simon等人编写程序LogicTheorist证实了《数学原理》中第二章三十八条定理，又于1963年证实了该章中全部五十二条定理。他们结果使人工智能研究走上以计算机程序来模拟人类思维道路，第一次把求解方法和问题领域知识分离开。在相同研究路径下，Selfridge编制了字符识别程序、Samuel研制了跳棋程序。Samuel跳棋程序含有学习功效，在1959和1962年分别打败了Samuel本人和美国一个州跳棋冠军。1957年，Simon、Newell和肖（J.C.Shaw）合作开发了表处理语言IPL（InformationProcessingLanguage。1957年，罗森勃拉特（F.Rosenblatt）提出著名感知机（Perceptron）模型，该模型是第一个完整人工神经网络。1958年，美籍逻辑学家王浩在自动定理证实中取得主要进展。他程序在IBM-704计算机上用不到5分钟时间证实了《数学原理》中“命题演算”全部220条定理。1959年，王浩改进程序用8.4分钟证实了上述220条定理及谓词演算绝大部分定理。人工智能与计算智能概述第10页1959年，Minsky和McCarthy在麻省理工学院创建世界上第一个人工智能试验室。1959年，McCarthy开发出了著名表处理语言LISP（ListProcessor）。IBM企业格伦特尔（H.Gelernter）研制出平面几何证实程序。1960年，Simon、Newell和Shaw又一次合作开发了通用问题求解系统GPS（GeneralProblemSolver）。1962年，美国工程师威德罗（B.Windrow）和霍夫（E.Hoff）提出了自适应线性单元Adaline（Adaptivelinearelement）。人工神经网络研究第一次高潮。1965年，罗伯特（L.G.Roberts）编制了能够分辨积木结构程序，开创了计算机视觉新领域。同年，美国数理逻辑学家鲁宾逊（J.A.Robinson）提出了与传统演绎法完全不一样消解法（也称归结原理），掀起了研究计算机定理证实又一高潮。人工智能与计算智能概述第11页1968年，美国斯坦福大学教授费根鲍姆（E.Feigenbaum）主持开发出世界上第一个化学分析教授系统DENDRAL，开创以知识为基础教授咨询系统研究领域。1968年，奎廉（J.R.Quillian）提出了语义网络知识表示方法，试图处理记忆心理学模型，以后Simon等人将语义网络应用于自然语言了解方面取得了很大成效。1969年，Minsky出版了《感知机》一书，该书对感知机进行了深入分析，而且从数学上证实了感知机功效不足，即只能处理一阶谓词逻辑问题，不能处理高阶谓词问题。同时，还发觉有许多模式不能用单层人工神经网络训练，而多层人工神经网络是否可行还很值得怀疑。所以，人工神经网络研究由此进入低潮时期，而教授系统研究进入高潮。人工智能与计算智能概述第12页第三阶段——发展和实用化阶段

以Feigenbaum为首一批年轻科学家改变了人工智能研究战略思想，开展了以知识为基础教授咨询系统研究与应用。在20世纪70年代有不少教授系统被研制开发，如麻省理工学院研制符号数学教授系统MACSYMA和自然语言了解系统SHRDLU，诊疗和治疗青光眼病教授系统CASNET，诊疗内科疾病教授系统INTERNIST，肾脏病教授咨询系统PIP，DEC企业开发诊疗系统VAX，卡内基-梅隆大学开发计算机配置教授系统XCON（RI）和XSEL。1972年，肖特利夫（E.H.Shortliffe）等人开发了医学诊疗教授系统MYCIN，1972年，吴兹（W.Woods）研制成功了自然语言了解系统LUNAR。1973年，法国马赛大学教授考尔麦劳厄（A.Colmerauer）研究小组实现逻辑式程序设计语言PROLOG（ProgramminginLogic）。人工智能与计算智能概述第13页1974年，沃博斯（P.J.Werbos）在其博士论文中提出在感知机基础上加入隐含层学习算法，有效处理了多层网络中隐含节点学习问题。1975年，Minsky创建了框架理论（FrameTheory）1975，美国密执根大学教授霍兰德（J.H.Holland）提出了遗传算法。1976年7月，美国阿佩尔（K.Appel）等用三台大型计算机，用1200小时时间，证实了四色定理。1977年，Feigenbaum在第五届国际智能联合会议上提出“知识工程”概念，人工智能研究从以基于推理为主模型转向以基于知识为主模型。1977年，休维特（C.Hewitt）在研究ConcurrentActorModel时就首次提出了含有自组织性、反应机制和同时执行能力软件模型，这就是最初软件Agent思想。1977年，我国吴文俊院士给出了一类平面几何问题机械化证实理论，在计算机上证实了一大批平面几何定理。1979年，由鲍勃罗夫（D.G.Boborow）采取基于框架设计，实现了KRL语言（KnowledgeRepresentationLanguage）。人工智能与计算智能概述第14页第四阶段——知识工程与教授系统

20世纪80年代，人工智能发展到达了阶段性顶峰。1982年日本开始了“第五代计算机研制计划”。美国物理学家霍普菲尔德（J.J.Hopfield）提出了一个新人工神经网络模型——Hopfield网络模型。1984年，希尔顿（G.Hinton）等人将模拟退火算法引入到人工神经网络中，提出了波尔兹曼（Boltzmann）机网络模型。1986年，鲁姆尔哈特（D.E.Rumelhart）和麦克莱伦（J.LMcclelland）重新提出了多层网络误差反向传输算法BP（Back-Propagation）。1987年6月，第一届国际人工神经网络会议在美国召开，宣告了这一新学科诞生。1987年，美国神经计算机教授尼尔森（R.H.Nielsen）提出了对向传输神经网络（CPN，CounterPropagationNetwork）人工智能与计算智能概述第15页进入90年代，计算机发展趋势为小型化、并行化、网络化、智能化。人工智能技术逐步与数据库、多媒体等主流技术相结合，并融合在主流技术之中，意在使计算机更聪明、更有效、与人更靠近。1992年，日本政府在第五代计算机研制计划宣告失败，但随即开启RWC计划（RealWorldComputingProject）。1993年，美国斯坦福教授肖汉姆（Y.Shoham）提出面向Agent程序设计（AOP，Agent-OrientedProgramming）。1995年，瓦普尼克（V.Vapnik）提出支持向量机（SVM，SupportVectorMachine）理论。1997年，麦克昆（W.McCune）提出了定理证实系统，成功地证实了1930年提出未被证实数学难题Robbins问题。1998年，在IBM“深蓝”计算机与著名大师国际象棋比赛中，“深蓝”战胜了卡斯帕罗夫大师。人工智能与计算智能概述第16页伴随计算机和网络技术发展与普及，当今人工智能主攻方向表达于：并行与分布式处理技术；知识获取、表示、更新和推理新机制；多功效感知技术；关于Agent研究；数据挖掘。人工智能是计算机研究中一个非常主要领域，在20世纪40位图灵奖取得者中有6位人工智能学者。其中，Minsky在1969年获奖，McCarthy在1971年获奖，Simon和Newell在1975年获奖，Feigenbaum和雷迪（R.Reddy）在1994年获奖。人工智能与计算智能概述第17页因为人们对人工智能本质不一样了解和认识，形成了人工智能研究各种不一样路径。在不一样研究路径下，其研究方法、学术观点和研究重点有所不一样，进而形成不一样学派。这里主要介绍认知学派、逻辑学派、行为主义学派和连接主义学派。人工智能研究路径和方法

人工智能与计算智能概述第18页

1.认知学派以Minsky、Simon和Newell等为代表从人思维活动出发，利用计算机进行宏观功效模拟。该学派认为认知基元是符号，智能行为经过符号操作来实现，它以美国Robinson提出消解法（即归结原理）为基础，以LISP和Prolog语言为代表，着重于问题求解中启发式搜索和推理过程。该学派在逻辑思维模拟方面取得成功，如自动定理证实和教授系统。人工智能与计算智能概述第19页

2.逻辑学派以McCarthy和尼尔逊（N.J.Nillson）等为代表主张用逻辑来研究人工智能，即用形式化方法描述客观世界。该学派主要观点以下：首先，智能机器必须相关于本身环境知识；其次，通用智能机器要能陈说性地表示关于本身环境大部分知识；再次，通用智能机器表示陈说性知识语言最少要有一阶逻辑表示能力。人工智能与计算智能概述第20页

3.行为主义学派以布鲁克斯（R.A.Brooks）为代表认为智能行为只能在现实世界中，由系统与周围环境交互过程中表现出来。主要观点：首先，智能系统与环境进行交互，即从运行环境中获取信息（感知），并经过自己动作对环境施加影响；其次，指出智能取决于感知和行为，提出了智能行为“感知-行为”模型，认为智能系统能够不需要知识、不需要表示、不需要推理，像人类智能一样能够逐步进化；再次，强调直觉和反馈主要性，智能行为表达在系统与环境交互之中，功效、结构和智能行为是不可分割。人工智能与计算智能概述第21页

4.连接主义学派以Rumelhart、Mcclelland和Hopfield等为代表，从人大脑神经系统结构出发，研究非程序、适应性、类似大脑格调信息处理本质和能力，人们也称它为神经计算。这种方法普通经过人工神经网络“自学习”取得知识，再利用知识处理问题。另外，还有知识工程学派和分布式学派。知识工程学派是以Feigenbaum为代表研究知识在人类智能中作用和地位。分布式学派是以Hewitt为代表研究智能系统中知识分布行为。人工智能与计算智能概述第22页人工智能研究与应用领域从应用角度看，人工智能研究主要集中在以下几个方面。1.教授系统8.模式识别2.自然语言了解9.博弈

3.机器学习10.计算机视觉4.自动定理证实11.计算智能

5.自动程序设计12.智能控制6.分布式人工智能13.智能规划7.机器人学人工智能与计算智能概述第23页教授系统是一个含有大量专门知识与经验程序系统，它应用人工智能技术，依据某个领域一个或多个人类教授提供知识和经验进行推理和判断，模拟人类教授决议过程，以处理那些需要教授决定复杂问题。教授系统与传统计算机程序本质区分在于，教授系统所要处理问题普通没有算法解，而且经常要在不完全、不准确或不确定信息基础上做出结论。从体系结构上可分为集中式教授系统、分布式教授系统、协同式教授系统、神经网络教授系统等；从方法上可分为基于规则方法教授系统、基于模型教授系统、基于框架教授系统等。1.教授系统人工智能与计算智能概述第24页2.自然语言了解自然语言了解是研究实现人类与计算机系统之间用自然语言进行有效通信各种理论和方法。实现人机间自然语言通信意味着计算机系统既能了解自然语言文本意义，也能生成自然语言文原来表示给定意图和思想等。而语言了解和生成是一个极为复杂解码和编码问题。一个能够了解自然语言计算机系统看起来就像一个人一样，它需要有上下文知识和信息，并能用信息发生器进行推理。了解口头和书写语言计算机系统基础就是表示上下文知识结构一些人工智能思想以及依据这些知识进行推理一些技术。人工智能与计算智能概述第25页3.机器学习机器学习研究主要目标是让机器本身含有获取知识能力，使机器能够总结经验、修正错误、发觉规律、改进性能，对环境含有更强适应能力。通常要处理以下几方面问题：（1）选择训练经验。包含怎样选择训练经验类型，怎样控制训练样本序列，以及怎样使训练样本分布与未来测试样本分布相同等子问题（2）选择目标函数。全部机器学习问题几乎都可简化为学习某个特定目标函数问题；（3）选择目标函数表示。在确定了理想目标函数后，接下来任务是必须从很多（甚至是无数）种表示方法中选择一个最优或近似最优表示方法。人工智能与计算智能概述第26页它是数学和计算机科学相结合研究课题。数学定理证实是人类思维中演绎推理能力主要表达。数理逻辑建立使自动定理证实构想有了更明确数学形式。1965年，Robinson提出了一阶谓词演算中归结原理，这是自动定理证实重大突破。1976年，美国Appel等三人利用高速计算机证实了124年未能处理“四色问题”。我国数学家吴文俊在1976年底开始研究可判定问题。他在微型机上成功地设计了初等几何与初等微分几何中一大类问题判定算法及对应程序。我国数学家张景中等人深入推出了“可读性证实”机器证实方法。4.自动定理证实人工智能与计算智能概述第27页5.自动程序设计自动程序设计是指依据给定问题原始描述，自动生成满足要求程序。自动程序设计主要包含程序综合和程序验证两方面内容。前者实现自动编程，即用户只需通知机器“做什么”，无须告诉“怎么做”，这后一步工作由机器自动完成；后者是程序自动验证，自动完成正确性检验。当前途序综合基本路径主要是程序变换，即经过对给定输入、输出条件进行逐步变换，已组成所要求程序。程序验证是利用一个已验证过程序系统来自动证实某一给定程序P正确性。人工智能与计算智能概述第28页6.分布式人工智能主要研究在逻辑上或物理上分散智能动作者怎样协调其智能行为，求解单目标和多目标问题。主要研究内容有分布式问题求解（DistributionProblemSolving，DPS）和Multi-Agent系统（MAS）。DPS方法是，先把问题分解成任务，再为之设计对应任务执行系统。

MAS主要研究多个Agent为了联合采取行动或求解问题，怎样协调各自知识、目标、策略和规划。在表示实际系统时，MAS经过各Agent间通讯、合作、互解、协调、调度、管理及控制来表示系统结构、功效及行为特征。人工智能与计算智能概述第29页机器人学是机械结构学、传感技术和人工智能结合产物。机器人发展经历了以下几个阶段：第一代为程序控制机器人；第二代为自适应机器人；第三代为分布式协同机器人。从功能上来考虑，机器人学研究主要涉及两个方面：一方面是模式识别，即给机器人配备视觉和触觉，使其能够识别空间景物实体和阴影，甚至可以辨别出两幅图像微小差别，从而完成模式识别功能；其次是运动协调推理。机器人运动协调推理是指机器人在接收外界刺激后，驱动机器人行动过程。7.机器人学人工智能与计算智能概述第30页

8.模式识别

模式识别研究是计算机模式识别系统，即用计算机代替人类或帮助人类感知模式。模式通常含有实体形式，如声音、图片、图像、语言、文字、符号、物体和景象等等，能够用物理、化学及生物传感器进行详细地采集和测量。但模式所指不是事物本身，而是从事物取得信息，所以，模式往往表现为含有时间和空间分布信息。人们在观察、认识事物和现象时，经常寻找它与其它事物和现象相同与不一样之处，依据使用目标进行分类、聚类和判断，人脑这种思维能力就组成了模式识别能力。人工智能与计算智能概述第31页

9.博弈

计算机博弈主要是研究下棋程序。在20世纪60年代就出现了很有名西洋跳棋和国际象棋程序，并到达了大师水平。进入20世纪90年代，IBM企业以其雄厚硬件基础，支持开发以后被称之为“深蓝”国际象棋系统人工智能与计算智能概述第32页10.计算机视觉计算机视觉研究任务是了解一个图像，这里图像是利用像素所描绘景物。该领域可分为以下三类：第一是信号处理，即研究把一个图像转换为含有所需特征另一个图像方法；第二是分类，即研究怎样把图像划分为预定类别。分类是从图像中抽取一组预先确定特征值，然后依据用于多为特征空间统计决议方法决定一个图像是否符合某一类；第三是了解，即在给定某一图像情况下，一个图像了解程序不但描述这个图像本身，而且也描述该图像所描绘景物。

人工智能与计算智能概述第33页通常把人工神经网络、含糊计算和进化计算作为计算智能三个主要内容。一般来说，计算智能多应用于缺乏足够先验知识，只有一大堆相关数据和记录问题。人工神经网络是一种应用类似于大脑神经突触连接结构进行信息处理数学模型。在这一模型中，大量节点之间相互连接组成网络，即“神经网络”，以抵达处理信息目标。含糊计算处理是含糊集合和逻辑连接符，以描述现实世界中类似人类处理推理问题。含糊集合包含论域中全部元素，不过具有[0,1]区间可变隶度属值。进化计算是经过模拟自然界中生物进化机制进行搜索一种算法，以遗传算法进化策略等为代表。遗传算法是一种随机算法，它是模拟生物进化中“优胜劣汰”自然法则进化过程而设计算法。11.计算智能人工智能与计算智能概述第34页智能控制是把人工智能技术引入控制领域，建立智能控制系统。智能控制含有两个显著特点：首先，智能控制同时含有知识表示非数学广义世界模型和传统数学模型混合表示控制过程，并以知识进行推理，以启发来引导求解过程。其次，智能控制关键在高层控制，即组织级控制。其任务在于对实际环境或过程进行组织，即决议和规划，以实现广义问题求解。12.智能控制人工智能与计算智能概述第35页13.智能规划

智能规划主要思想：对周围环境进行认识与分析，依据自己要实现目标，对若干可供选择动作及所提供资源限制施行推理，综合制订出实现目标规划。最早规划系统——通用问题求解系统GPS。1969年，格林（G.Green）——QA3系统。1971年，菲克斯（R.E.Fikes）和Nilsson——STRIPS系统。1971~1977年间，先后出现了HACKER、WARPLAN、INTERPLAN、ABSTRIPS、NOAH、NONLIN等规划系统。上述系统也被称做经典规划系统。进入八十年代中期后，规划技术研究热点转向开拓非经典实际规划问题。人工智能与计算智能概述第36页美国人工智能协会

人工智能教育知识库/~manaris/ai-education-repository/index.html教授系统expertise2go网

人工智能语言VisualProlog

人工智能研究者俱乐部/bitfarmer/default.asp智能科学与人工智能网站/index.html

人工智能相关网站介绍人工智能与计算智能概述第37页IEEE计算智能协会，国际神经网络协会，国际人工智能联合会，欧洲人工智能联合会，斯里兰卡国际人工智能中心，美国伯克利大学人工智能网站，/ai.html美国加里福尼大学机器学习研究/research/ml/中国人工智能网北京大学人工智能试验室http://

人工智能与计算智能概述第38页我们要对计算智能这一当今热点研究领域做深入讨论！人工智能与计算智能概述第39页Contents最优化问题1计算复杂性及NP理论2计算智能算法3计算智能分类与理论计算智能研究与发展计算智能特征与应用人工智能与计算智能概述第40页1.1最优化问题最优化问题求解模型以下公式所表示Minf(X),X

D其中D是问题解空间，X是D中一个正当解。普通可将X表示为X=(x1,x2,…,xn)，表示一组决议变量最优化问题就是在解空间中寻找一个正当解X（一组最正确决议变量），使得X对应函数映射值f(X)最小（最大）最优化问题分类分类标志变量个数变量性质约束条件极值个数目标个数函数关系问题性质时间改变类型单变量连续无约束单峰单目标线性确定性静态离散随机性多变量混合有约束多峰多目标非线性含糊性动态人工智能与计算智能概述第41页1.1最优化问题依据决议变量xi取值类型，我们能够将最优化问题分为函数优化问题和组合优化问题两大类函数优化问题决议变量均为连续变量最优化问题最优化问题组合优化问题决议变量均为离散取值最优化问题人工智能与计算智能概述第42页1.1.1函数优化问题比如：

其中，n=30表示问题空间维数，xi∈[-100,100]是定义域，这个函数最小值为0这是一个最简单函数优化问题人工智能与计算智能概述第43页1.1.1函数优化问题很多科学试验参数配置和工农业生产实践都需要面临这种类型最优化问题比如设计神经网络过程中，需要确定神经元节点间网络连接权重，从而使得网络性能到达最优在这种问题中，需要优化变量取值是某个连续区间上值，是一个实数。各个决议变量之间可能是独立，也可能是相互关联、相互制约，它们取值组合组成了问题一个解因为决议变量是连续值，所以对每个变量进行枚举是不可能。在这种情况下，必须借助最优化方法对问题进行求解人工智能与计算智能概述第44页1.1.2组合优化问题组合优化问题决议变量是离散取值比如整数规划问题，0-1规划问题等等很多离散组合优化问题都是从运筹学（OperationsResearch，OR）中演化出来组合优化其所研究问题包括到信息技术、经济管理、工业工程、交通运输、通信网络等众多领域，在科学研究和生产实践中都起着主要作用人工智能与计算智能概述第45页1.1.2组合优化问题经典组合优化问题：旅行商问题（TravelingSalesmanProblem，TSP）0-1背包问题（Zero/oneKnapsackProblem，ZKP/0-1KP/KP）……当问题规模n比较大时，用枚举方法所需时间太大，我们借助智能优化计算方法，能够在合理时间内求解得到令人满意解，从而满足实践需要人工智能与计算智能概述第46页1.2.1计算复杂性计算复杂性（ComputationalComplexity）

描述求解问题难易程度或者算法执行效率对于算法计算复杂性，我们普通很轻易进行判断，比如使用蛮力法去枚举旅行商问题或者0-1背包问题算法，就是含有指数计算复杂性算法对于某问题计算复杂性进行判断却不是一件简单事情人工智能与计算智能概述第47页1.2.1计算复杂性问题计算复杂性是问题规模函数，故需要首先定义问题规模比如对于矩阵运算，矩阵阶数可被定义为问题规模假如求解一个问题需要运算次数或步骤数是问题规模n指数函数，则称该问题有指数时间复杂性假如所需运算次数是n多项式函数，则称它有多项式时间复杂性对于某个详细问题，其复杂性上界是已知求解该问题最快算法复杂性，而复杂性下界只能经过理论证实来建立证实一个问题复杂性下界就需要证实不存在任何复杂性低于下界算法。显然，建立下界要比确定上界困难得多人工智能与计算智能概述第48页1.2.2NP理论P类问题（PolynomialProblem）

P类问题是指一类能够用确定性算法在多项式时间内求解判定问题。其实，在非正式定义中，我们能够把那些在多项式时间内求解问题看成P类问题。人工智能与计算智能概述第49页1.2.2NP理论NP类问题（Non-deterministicPolynomialProblem）

NP类问题是指一类能够用不确定性多项式算法求解判定问题。比如旅行商问题判定版本就是一个NP类问题。我们即使还不能找到一个多项式确实定性算法求解最小周游路线，不过能够在一个多项式时间内对任意生成一条“路线”判定是否是正当（经过每个城市一次且仅仅一次）。比较P类问题和NP类问题定义，我们很轻易得到一个结论：P

NP。人工智能与计算智能概述第50页1.2.2NP理论

NP完全问题（NPCompleteProblem）我们称一个判定问题D是NP完全问题，条件是：（1）D属于NP类；（2）NP中任何问题都能够在多项式时间内转化为D。人工智能与计算智能概述第51页1.2.2NP理论

NP完全问题（NPCompleteProblem）另外，一个满足条件（2）但不满足条件（1）问题被称为NP难问题。也就是说，NP难问题不一定是NP类问题，比如图灵停机问题。正式地说，一个NP难问题最少跟NP完全问题一样难，可能更难！比如在一些任意大棋盘游戏走出必胜下法，就是一个NP难问题，这个问题甚至比那些NP完全问题还难。人工智能与计算智能概述第52页1.3计算智能方法计算智能算法是人工智能一个分支，是联结主义经典代表，又称为仿生学派或生理学派。逻辑主义又称为符号主义(Symbolicism)、心理学派(Psychlogism)或计算机学派(Computerism)，其原理主要为物理符号系统假设和有限理性原理。人工智能行为主义又称为控制论学派(Cyberneticsism)，其原理为控制论及感知-动作型控制系统。他们对人工智能发展历史含有不一样看法，这一学派认为人工智能源于控制论。联结主义又称为仿生学派(Bionicsism)或生理学派(Physiologism)，其原理主要为神经网络及神经网络间连接机制与学习算法，包含进化计算等计算智能算法。计算智能人工智能与计算智能概述第53页1.3计算智能方法伴随技术进步、工程实践问题变得越来越复杂，传统计算方法面临着计算复杂度高、计算时间长等问题计算智能方法采取启发式随机搜索策略，在问题全局空间中进行搜索寻优，能在可接收时间内找到全局最优解或者可接收解计算智能算法在处理优化问题时候，对求解问题不需要严格数学推导，而且有很好全局搜索能力，含有普遍适应性和求解鲁棒性计算智能人工智能与计算智能概述第54页1.3计算智能方法计算智能计算智能是人工智能主要领域，也是近几十年来研究热点问题。计算智能兴起和快速发展，为人工智能提供了新出路计算智能技术在国内得到了广泛重视。因为这个领域研究包括到硬件要求不高，国内研究已经到达国际认可水平计算智能技术深入发展和完善，以及应用深入拓展，都将对计算机技术和各个相关应用领域带来深刻变革人工智能与计算智能概述第55页1.3.1计算智能分类与理论人工智能与计算智能概述第56页1.3.1计算智能分类与理论研究领域主要特点人工神经网络模仿人脑生理结构和信息处理过程，模拟人类智慧含糊逻辑（含糊系统）模仿人类语言和思维中含糊性概念，模拟人类智慧进化计算模仿生物进化过程和群体智能过程，模拟大自然智慧计算智能主要研究方向及其特点人工智能与计算智能概述第57页1.3.1计算智能分类与理论数学基础马尔可夫过程统计学习过程随机过程模式定理稳定性收敛性……群体智能个体认识群体智慧个体竞争群体协作……生物学基础优胜劣汰适者生存自然选择生物进化遗传规律人脑模拟生物觅食……计算智能相关理论基础人工智能与计算智能概述第58页1.3.2计算智能研究与发展遗传算法(GA)GeneticAlgorithm神经网络(NN)（感知器）1950sRosenblatt等人1950s美国学者Holland20世纪50-60年代起步阶段进化策略(ES)EvolutionStrategy进化规划(EP)EvolutionaryProgramming1960s德国人RechenbergSchwefel1960s美国学者Fogel含糊逻辑理论(FL)FuzzyLogic1960s美国学者Zadeh人工智能与计算智能概述第59页1.3.2计算智能研究与发展20世纪70-80年代发展阶段遗传算法、进化策略、进化规划理论基础不停完善（模式定理）算法之间区分越来越不显著禁忌搜索算法（1986