智能计算基础

智能计算基础第一章绪论第二章不精确推理第三章人工神经网络计算第四章演化计算第五章数据挖掘第六章粗集与模糊逻辑1第一章绪论智能的概念智能的发展历史智能学的产生智能计算的分支2智能的概念哲学（philosophy）一词来自于希腊语philosophia，是由爱好（philo）和智慧（sophia）组成。什么是智能？智能在哪里？智能什么样？智能：个体有目的的行为、合理的思维，以及有效的适应环境的综合性能力。智能在人体中，是脑的重要功能。智能的表现形式多样。其他动物是否具有智能？人类和一些动物具有的智力和行为能力。蚊子、蝙蝠、信天翁、海豚、猴子。电脑具有智能吗？3最早的智力工具从起源中理解事物，就是从本质上理解事物。4最早的智力工具最早的智力工具（大约公元前3500年）数的认识计数数制计算算盘的发明算盘的样子算盘的使用算盘的未来5思维逻辑研究公孙龙（约前320年-前250年）白马论指物论通变论坚白论名实论迹府白马非马6思维逻辑研究白马论白和马是两个不同的概念白马不同于马白马的“白”和“马”可以分开黄马和马不同马的颜色属性并不固定7思维逻辑研究坚白论石头的白色和坚硬是可以分离的属性。眼睛看不到石之坚，只能见石之白，这时坚硬性等于没有；手摸不到石之白，只能感到石之坚，这时白等于没有。有时感到坚硬，有时感到白色，感觉到的和感觉不到的，彼此分离。彼此不联在一起的，叫分离。分离就是潜在于自身之中。8思维逻辑研究名实论讨论名词（名）与其所指（实）的关系时，提出了名词的所指必须有确定的规律。故彼彼止于彼，此此止于此，可。彼此而彼且此，此彼而此且彼，不可。如果认为那个就是那个，这个就是这个，是正确的；而认为那个也是这个，这个也是那个，则不正确。9思维逻辑研究墨子（约前468年-前376年）研究了类比推理、直接推理定义了具体名词、抽象名词区分了全称判断和特称判断两个互相矛盾的判断不能同时成立，必定有一个不能成立。墨子是中国逻辑学的奠基者。10思维逻辑研究荀子（约前313年-前238年）批判地改造了先秦诸子的学术思想，反对天命、神鬼迷信，形成了比较完整的唯物主义哲学体系。对于智力，有一定的认识。他认为“智力在心里。”耳、目、口、鼻、形，能各有接而不相能也，夫是之谓天官。心居中虚，以治五官，夫是之谓天君。11脑的作用和发现脑的发现，在公元前600年—前250年希腊哲学家、医学教师希波克拉底，得出结论：大脑是人类感情的源地。亚里士多德也研究过脑，“在所有的动物中，人拥有相对于身体比例而言最大的大脑。”12哲学的发展苏格拉底：（前470—前399年），最早提出“归纳论证”方法。要求认真考察前提和结论，精确地说明和定义概念，推断必须有严格演绎，假设必须论证或驳斥。柏拉图：（约前427年－前347年），把苏格拉底的言论学说记录，与自己的思想融合到一起，创建了哲学学科，史称哲学王。亚里士多德：（前384—前322年），创造了形式逻辑学。主要著作有：形而上学、物理学、诗学、工具论、政治学、论灵魂、论产生与毁灭、伦理学。被称为“动物学之父”。与柏拉图同在，与亚里士多德同在。13逻辑学判断语句是对事物有所肯定或否定的思维形式。命题是具有真假意义的一句话。三段论如果所有阔叶植物都是落叶的，并且所有葡萄树都是阔叶植物，则所有葡萄树都是落叶的。14逻辑学证明指出了要通过推理获得知识，就必须由已有的知识出发。驳斥了“一切知识都要经过证明”的言论。公理、设定和定义都不需要证明。形而上学提出矛盾律、排中律和归纳法把矛盾律看作关于事物的规律承认有一种“直觉推理”的思维方式不受逻辑支配。15形而上学形而上学(metaphysics)是哲学术语，哲学史上指哲学中探究宇宙根本原理的部分。形而上学可以理解为：对“终极实在”的研究。广义上说，研究超越感性经验存在的学问，都可以叫做形而上学。中文译名“形而上学”取自《易经》中“形而上者谓之道，形而下者谓之器”一语。16近代智能世界笛卡尔笛卡尔（1596-1650）提出了运动量守恒定律。他的学说导致关于人类存在与思维问题的理解发生了革命性的变化。《形而上学的沉思》、《方法论》、《哲学原理》、《心灵感受》发明了笛卡尔坐标，被称为“解析几何之父”。现代哲学之父、启蒙之父17近代智能世界笛卡尔发生在脑部的任何特定的活动，会立即影响人的心灵，并产生相应的感受。如果每当小提琴声响时，你抽打一条狗五六次，那么，一旦它再听到提琴声，它就会吼叫而跑。18概率论的产生概率论源于意大利的赌博业。法国科学家Pascal和Fermat提出了概率论的概念。贝努力提出了“置信度”的概念。当有了新的证据时，主观概率可以更改。Bayes提出了Bayes公式，奠定了人工智能系统中不确定推理的现在方法论的基础。拉普拉斯：把古典概率论推进到现代概率论，形成了概率与统计。19数字计算器的发明Pascal于1642年发明了机械加减法机。Leibniz改进了Pascal的机器，于1673年造出了四则运算器，并提出了二进制的想法。Babbage于1821年发明了通用计算机，可以存储地址和程序，用于自动计算数学表，贴近了现代电子计算机。20逻辑数学化布尔于1847年提出了逻辑代数，把逻辑学引入到数学领域。布尔名著《思想规律的研究》曾提出：用符号语言与运算可以表示任何事物。提出了“类”的概念，类与集合相近，类由属于它的元素组成，它们都可以用符号表示。逻辑可以看作是类的演算，即相应的符号的代数。21逻辑数学化布尔指出：交换律X+Y=Y+XXY=YX分配率X(Y+Z)=XY+XZ结合律X+(Y+Z)=(X+Y)+ZX(YZ)=(XY)Z22生命进化论法国博物学家拉马克于1809年提出了进化学说。阐述了物种是可变的，其稳定性是相对的。拉马克被认为是科学进化论的创始人。达尔文，于1859年发表了《物种起源》。繁殖过剩，生存竞争，适者生存，自然定向选择，构成了达尔文进化论的核心。孟德尔，于1865年发表了《植物杂交试验》，为遗传学奠定了基础，也为生物进化中的遗传变异提供了理论基础。被称为现代遗传学之父。23脑的研究脑部功能区的确定大脑左半侧控制身体右侧，右脑控制身体左侧。左半部主管语言、数学解析和分析思维；右半部主管空间思维和乐感、理解普通名词、简单句子和简单算术。24脑的研究大脑的解剖脑是由什么组成的：高尔基于1872年发现了神经元，并且认为它们是直接连接在一起的。卡加尔认为神经元之间存在间隙，即突触。卡加尔被认为是神经元学说的创立者。25神经网络詹姆斯：由神经元组成的神经系统，其功能是调节生物体内各器官的活动和适应外部环境。联想是由事件A联想起事件B的过程，是大脑皮层活动区A去激活大脑皮层活动区B的过程。1943年，由生理学家麦克卡洛和数理逻辑学家皮茨成立了脑模型，称为MP模型，开创了用电子装置模仿人脑结构和功能的研究方向。26心理学心理学是研究心理过程和行为的科学，即研究认识、感情、意志等心理过程和能力、性格等心理特性。实验心理学、认知心理学取得了很重要的理论和应用。在机器的心理学研究上未取得有效的突破。27计算机模型的提出图灵，于1934年提出逻辑设计和通用机器的概念。被称作人工智能之父，计算机科学之父。于1936年发表论文《论可计算数及其在判定问题中的应用》，是阐明现代计算和计算机原理的开山之作。28计算机模型的提出图灵机，是通过一条纸带读入某种符号，一次读入一个符号。机器内部有一个动作表，决定具体的动作。这些动作组成一组计算的基本动作，由它们构成不同的数学运算。通用图灵机，就是能完成各种行为表的图灵机，相当于现代计算机。29计算机的出现冯诺依曼于1945年提出了“在计算机内部存储器中储存指令”的工作原理，以及基于这一原理的计算机系统结构。控制器、运算器、存储器、输入和输出设备的结构仍然是主流计算机的结构。30控制论和信息论的出现控制论：维纳于1948年提出。自动控制和自我调节是生物智能行为的核心。控制论的基本思想是用统一的观点讨论控制、通信与计算机，指出了计算机与神经系统工作机理的相似性。信息论：香农于1948年提出。香农的论文“通信的数学理论”，采用了信息编码和概率论方法，研究信号传输过程中的波形和干扰问题，发展了关于信息量的计算方法和统计理论，解释了通信过程的本质。31神经元学习Hebb，提出了著名的Hebb学习规则。神经元是通过不断的学习获得能力的增长的。学习能力的大小与神经元的特征及神经元的学习强度有关。某些学习是由遗传决定的。外界环境也会影响神经元的学习。32人工智能的诞生1956年在美国Dartmouth大学举行了2个月的研讨会。会上首次提出了“ArtificialIntelligence”这个概念，讨论如何使机器模拟人类智能这个中心问题。由Newell和Shannon研制的逻辑理论机LT数学定理证明程序，是第一个处理符号而不是数字的程序，是机器证明数学定理的最早尝试。Samuel编制的跳棋程序具有学习能力，后来超过了设计者本人。1969年，第一届国际人工智能联合会召开。我国从1978年开始计划人工智能的研究。33进化计算生物从低级进化到高级、从不完善到完善的过程，类似于计算机处理事务的过程。一个生命体用一组特征数据表示，用它对生存环境的的适应程度来评价它的优劣，让适应性更强的特征繁殖得更快，最终取代适应性差的。这就是生物进化的抽象过程，对它编程后就得到进化计算。代表：遗传算法34计算智能人工神经网络、模糊系统和进化计算统称为计算智能，这三者都是模仿人的智能或自然规律，给出解决实际问题的一套计算方法，称之为智能计算方法。35专家系统与知识工程Feigenbaum，1969年与同事开发出DENDRAL专家系统，该系统能从光谱仪提供的信息中推断出物质的分子结构。1976年，他们又开发出MYCIN医疗专家系统，用于抗生素药物治疗和血液感染诊断。1977年，Feigenbaum提出了专家系统和知识工程的概念。36知识工程知识工程是人工智能的一种技艺，它运用人工智能的原理和方法，对那些需要专家知识才能解决的应用难题提供求解的手段。恰当运用专家知识的获取、表达和推理过程的构成与解释，是设计基于知识的系统的重要技术问题。37人机大战下棋是很抽象的活动，是机器可以和人竞争的智能领域之一。香农和图灵都编写过下棋程序。香农提出的评估函数，至今还在广泛应用。Samuel编写的西洋跳棋程序，首次引入了自适应的概念。1997年，深蓝和卡斯帕罗夫大战。2004年，紫光计算机和诸宸大战。38智能计算的分支人工智能专家系统机器学习语音识别机器翻译人机对弈人工神经网络演化计算数据挖掘39第二章不精确推理不精确推理的概念不精确推理的方法可信度方法主观Bayes方法证据理论40推理的类型演绎推理：由一组前提必然推导出某个结论的过程。演绎推理的核心是三段论。演绎推理没有增加新的知识。演绎推理的结果是保真的。归纳推理：以某命题为前提，推论出与其有归纳关系的其他命题的过程。归纳推理增加了新的知识，但是不保真。在系统应用时，先根据一些事实进行归纳推理，得出一些结论，再根据一些事实对这些结论进行验证，去掉错误的，保留正确的。41推理的类型外展推理：已知某一结果已经发生，去寻找这个结果的原因。也即由因到果的解释论证过程。菜中放了糖会有甜味，放了醋会有酸味，放了盐会有咸味。当我们从菜中吃出了某种味道，推理出菜中放了什么。概率推理：按照事件发生概率的大小来进行推理的过程。非单调推理：推理过程中，在增加某些新的事实时，能够取消以前的一些结论。不确定推理：42不精确推理的因素知识不完备、不精确知识描述的模糊性知识的随机性原因的多样性解决方案不唯一43不精确推理的概念不精确推理就是在知识的不确定性和证据的不精确性基础上进行的具有一定程度不精确但却是合理的结论的思维过程。

44不精确推理的基本问题不精确推理的基本问题，包括关于证据的不确定性表示，规则的不确定性表示，不确定性的计算。这些问题的不同解决方法形成了各种不精确推理方法。45证据的不确定性为C（E），它表示证据E为真的程度。规则的不确定性为f（H，E），它称为规则强度，表示证据E为真的前提下，假设H为真的程度。不精确推理就是在规则强度和证据的不确定性的基础上，定义一组函数，求出结论的不确定性度量。不精确推理模型的算法46（1）根据规则前提E的不确定性C(E)和规则强度f(H，E)求出假设H的不确定性C(H)，即定义函数g1，使C(H)=g1[C(E)，f(H，E)]（2）根据分别由独立的证据E1、E2求得的假设H的不确定性C1(H)和C2(H)，求出证据E1和E2的组合所导致的假设H的不确定性C(H)，即定义函数g2，使C(H)=g2[C1(H)，C2(H)]不精确推理模型的算法47（3）根据两个证据E1和E2的不确定性C(E1)和C(E2)，求出证据E1和E2的合取的不确定性，即定义函数g3，使C(E1ANDE2)=g3[C(E1)，C(E2)]（4）根据两个证据E1和E2的不确定性C(E1)和C(E2)，求出证据E1和E2的析取的不确定性，即定义函数g4，使C(E1ORE2)=g4[C(E1)，C(E2)]不精确推理模型的算法48可信度方法：可信度方法是MYCIN系统使用的不精确推理模型，它以确定性理论为基础，方法简单实用。主观Bayes方法：主观Bayes方法是PROSPECTOR系统使用的不精确推理模型，它是对Bayes公式进行修正后形成的一种不精确推理方法。缺点是难以给出每个命题的先验概率。证据理论：证据理论通过引进信任函数，把不确定和不知道区别开来。这些函数满足比概率函数还弱的公理。主要的不精确推理模型491．知识的不确定性 IfEthenH，CF规则强度（规则可信度）：CF(H，E)=MB(H，E)-MD(H，E)其中MB为信任增长度(MeasureBelief)，MB(H，E)>0表示因证据E的出现增加了相信假设H为真的程度，即P(H|E)>P(H)。MD为不信增长度(MeasureDisbelief)，MD(H，E)>0表示因证据E的出现减少了相信假设H为真的程度，即P(H|E)<P(H)。可信度方法50

1 ifP(H)=1MB(H,E)=max[P(H,E),P(H)]-P(H)else 1-P(H) 因E而对H信任的增长 不相信H的概率

1 ifP(H)=0MD(H,E)=min[P(H,E),P(H)]-P(H)else -P(H) 因E而对H信任的减小 相信H的概率51性质：（1）互斥性 当MB(H，E)>0时MD(H，E)=0 当MD(H，E)>0时MB(H，E)=0（2）值域 0MB(H，E)1 0MD(H，E)1 -1CF(H，E)152（3）典型值若P(H|E)=1，即E为真时H为真，则CF(H，E)=1若P(H|E)=0，即E为真时H为假，则CF(H，E)=-1若P(H|E)=P(H)，即E对H无影响，则CF(H,E)=0，称为单位元。（4）CF(H，E)+CF(~H，E)=0 此点与概率不同：P(H|E)+P(~H|E)=153证明CF(H，E)+CF(~H，E)=0CF(H，E)+CF(~H，E)=MB(H，E)–MD(H，E)+MB(~H，E)–MD(~H，E)IfP(H|E)>P(H)，P(~H|E)<P(~H)则MB(H，E)–MD(~H，E)={P(H|E)–P(H)}/(1–P(H))–{P(~H|E)–P(~H)}/(-P(~H))=54(P(H|E)–P(H)+P(~H|E)–P(~H))/(1-P(H))=0IfP(H|E)<P(H)，P(~H|E)>P(~H)则-MD(H，E)+MB(~H，E)=(P(H|E)–P(H))/P(H)+(P(~H|E)–P(~H))/(1-P(~H))=055（5）互斥假设 若同一证据E有K个互不相容的假设Hi，(i=1，2，…，K)，则

只有当E逻辑蕴含某个Hi时，等式才成立。562．证据的不确定性 原始证据的不确定性（可信度）由用户在系统运行时提供。 非原始证据的不确定性（可信度）由不精确推理而来。57性质：（1）值域 当证据E以某种程度为真时0<CF(E)1 反之 -1CF(E)<0（2）典型值 当证据E肯定为真时，取CF(E)=1 当证据E肯定为假时，取CF(E)=-1 当对证据一无所知时，取CF(E)=0 单位元58

3．算法(1)动态强度----组合规则前提与规则的可信度 CF(H)=CF(H，E).max{0，CF(E)}(2)新证据法则----组合两个独立证据导出的同一假设的可信度。IfE1thenH，CF1 IfE2thenH，CF259

CF1(H)+CF2(H)-CF1(H).CF2(H) CF1(H)0且CF2(H)0CF(H)=CF1(H)+CF2(H)+CF1(H).CF2(H) CF1(H)<0且CF2(H)<0

CF1(H)+CF2(H) 其它60 组合多个独立证据导出的同一假设的可信度，分别组合MB和MD：

0 当MD(H)=1MB(H)=

MB1(H)+MB2(H)-MB1(H).MB2(H) 其他

0 当MB(H)=1MD(H)=

MD1(H)+MD2(H)-MD1(H).MD2(H) 其他CF(H)=MB(H)-MD(H)61对3个独立证据E1，E2，E3导出同一假设:MB(H)=MB1(H)+MB2(H)+MB3(H)-MB1(H).MB2(H)-MB1(H).MB3(H)-MB2(H).MB3(H)+MB1(H).MB2(H).MB3(H)MD(H)=MD1(H)+MD2(H)+MD3(H)-MD1(H).MD2(H)-MD1(H).MD3(H)-MD2(H).MD3(H)+MD1(H).MD2(H).MD3(H) CF(H)=MB(H)-MD(H)62（3）证据的逻辑合取IfE1andE2and…andEnThenH IfEthenHCF(E)=CF(E1andE2and…andEn)=min{CF(E1)，CF(E2)，…，CF(En)}（4）证据的逻辑析取IfE1orE2or…orEnThenH IfEthenHCF(E)=CF(E1orE2or…orEn)=max{CF(E1)，CF(E2)，…，CF(En)}63例：有如下推理规则：rule1:ifE1thenH，0.9rule2:ifE2thenH，0.7rule3:ifE3thenH，-0.8rule4:ifE4andE5thenE1，0.7rule5:ifE6and(E7orE8)thenE2，1已知：CF(E3)=0.3，CF(E4)=0.9，CF(E5)=0.6，CF(E6)=0.7，CF(E7)=-0.3，CF(E8)=0.864 H 0.9 0.7 -0.8 E1 E2 E3 0.7 1 0.3 E4 E5 E6 0.9 0.6 0.7 E7 E8 -0.30.865CF(E4andE5)=min{E4，E5}=E5=0.6CF(E1)=0.6*0.7=0.42CF1(H)=0.9x

0.42 CF(E7orE8)=max{E7，E8}=E8=0.8CF(E6and(E7orE8))=min{E6and(E7orE8)}=E6=0.7CF2(H)=0.7x0.7 CF3(H)=-0.8x0.366使用MB和MD组合：MB1=0.378，MB2=0.49，MB3=0MD1=0，MD2=0，MD3=0.24MB(H)=MB1+MB2+MB3-MB1xMB2-MB1xMB3-MB2xMB3+MB1xMB2xMB3=0.68278MD(H)=MD1+MD2+MD3-MD1xMD2-MD1xMD3-MD2xMD3+MD1xMD2xMD3=0.24CF(H)=MB(H)-MD(H)=0.4427867练习题已知：R1:IFA1THENB10.8R2:IFA2THENB10.5R3:IFB1∧A3THENB20.8初始证据A1、A2、A3的可信度分别假设为0.9，0.8，1，画出网络图，并求CF(B1)和CF(B2)。68主观Bayes方法 以概率论Bayes公式为基础1．知识的不确定性 IfEthenH，(LS，LN) 规则表示为 LS，LN E H PROSPECTOR的非精确推理过程，就是根据证据E的概率P(E)，利用规则的LS，LN，把结论H的先验概率P(H)更新为后验概率P(H|E)的过程，也称为概率传播。69Bayse公式为：70两式相除，得：

71记为结论的先验几率(priorodds)记结论的后验几率(posteriorodds)72上式变成：同理可得：73记得

O(H|E)=LS.O(H) (1) O(H|~E)=LN.O(H) (2)上式为修改的Bayes公式74LS，LN的性质：(1)LS当LS=1时，O(H|E)=O(H)，即E对H没有影响。当LS>1时，O(H|E)>O(H)，即E支持H。当LS<1时，O(H|E)<O(H)，即E排斥H。故LS称为充分性量度。75LS,LN的性质：(2)LN当LN=1时，O(H|~E)=O(H)，即~E对H没有影响。当LN>1时，O(H|~E)>O(H)，即~E支持H。当LN<1时，O(H|~E)<O(H)，即~E排斥H,且LN0时O(H|~E)0,即LN越接近0，E对H越是必要的。故LN称为必要性量度。76(3)LS,LN的关系，只有三种情况：LS>1且LN<1LS<1且LN>1LS=LN=1772．证据的不确定性 P(E)=1时，O(E)= P(E)=0时，O(E)=0 对E一无所知时，取E的先验概率----单位元783．算法(1)概率传播 ifEthenH，(LS，LN)在P(E)=1或P(~E)=1时，已有：如果用概率来表示，则有：79同样，对于后验几率，也有：80对于不确定证据，在0<P(E)<1时，如何根据P(E)更新P(H)。即在观察S之下，证据E有概率P(E|S)，求解P(H|S)。有：81对于上式，可以在P(E|S)的三个特殊点上求得P(H|S)的值。三个特殊值如下：P(E|S) P(H|S) 1 P(H|E) P(E) P(H) 0 P(H|~E)82 P(H|S) 1-P(H|E)-P(H)-P(H|~E)- 0 P(E) 1P(E|S)83分段线性插值，得

上式称为EH公式。84(2)独立证据导出同一假设 ifE1thenH，(LS1，LN1) …… ifEnthenH，(LSn，LNn) 设独立证据E1，E2，…，En的观察为S1，S2，…，Sn，假设为H85(3)证据的合取 ifE1andE2and…thenH P(E1andE2and…|S)=min{P(E1|S，P(E2|S)，…}(4)证据的析取 ifE1orE2or…thenH P(E1orE2or…|S)=max{P(E1|S，P(E2|S)，…}86例：设有假设H，证据E1，E2，规则R1，R2：R1:E1H，(20，1)R2:E2H，(300，1)已知先验概率P(H)=0.03，若证据E1，E2依次出现，求P(H|E1，E2)。87解法1：O(H)=P(H)/[1-P(H)]=0.03/(1-0.03)=0.0309O(H|E1)=LS1O(H)=200.0309=0.618O(H|E1,E2)=LS2O(H|E1)=3000.618=185.5

88解法2：按独立证据的组合公式：其中 O(H|E1)=LS1O(H) O(H|E2)=LS2O(H) O(H|E1，E2)=LS1LS2O(H)=185.5 与解1相同。89 最大相关：只要概率小的事件发生，则概率大的事件肯定发生。 P(AANDB)=min[P(A)，P(B)] P(AORB)=max[P(A)，P(B)]90 最小相关：两个事件同时发生的概率尽量小，如果两个事件发生的概率之和小于0，则同时发生的概率为0。P(AANDB)=max[0，P(A)+P(B)-1]P(AORB)=min[1，P(A)+P(B)]91 相互独立： P(AANDB)=P(A).P(B) P(AORB)=P(A)+P(B)–P(A).P(B)92例：推理网络如下 HYPE0.01 65，0.01 300，0.0001 0.1STIR SMIR0.032，0.000001 100，0.000001

0.2 FMGS FMGS&PT0.4用户给出： P(FMGS|S1)=0.7, P(FMGS&PT|S2)=0.6,P(SMIR|S3)=0.02求P(HYPE|S1S2S3)93求解过程（1）根据P(FMGS|S1)计算P(STIR|S1)。由于P(FMGS|S1)=0.7>0.2，因此利用EH公式的后半部分。94（2）根据P(FMGS&PT|S2)计算P(STIR|S2)。由于P(FMGS&PT|S2)=0.6>0.4，故利用EH公式的后半部分。95（3）根据独立证据FMGS和FMGS&PT计算P(STIR|S1&S2)。先计算后验几率O(STIR|S1&S2)，由于96因此得然后得到后验概率P(STIR|S1&S2)97（4）根据P(STIR|S1&S2)计算P(HYPE|S1&S2)，由于P(STIR|S1&S2)=0.4875>0.1，故利用EH公式的后半部分。98（5）根据P(SMIR|S3)计算P(HYPE|S3)，由于P(SMIR|S3)=0.02<0.03，故利用EH公式的前半部分。99（6）根据独立证据STIR和SMIR计算P(HYPE|S1&S2&S3)。先计算后验几率O(HYPE|S1&S2&S3)，由于100因此得最后得到后验概率P(HYPE|S1&S2&S3)101经过推理，假设HYPE的概率已从先验概率0.01增强到0.1245。102主观Bayes方法小结主观Bayes方法优点：修正了概率论Bayes公式，应用于不精确推理，取得了很好的效果。主观Bayes方法缺点：先验概率难以合理的给出。103证据理论Dempster/Shafer证据理论1041．基本理论设为变量x的所有可能值的穷举集合，且设中的各元素是相互排斥的，称为辨别框。为简单，以后假定为有限集合，中的元素也可以是连续变量。由于是可穷举的，对于一个提问只能有一个答案是正确的。的所有子集对应着论域中的所有可能的有效答案。105定义1：对任意一个属于的子集A（命题），命它对应一个数M(A)[0，1]，而且满足

M()=0

则称函数M为命题的基本概率分配函数bpa(basicprobabilityassignment)，称数M(A)为A的基本概率数。 若A，且A，则M(A)表示对A的精确信任程度。 若A=，则M(A)表示这个数不知如何分配。106在Bayes理论中，后验概率随证据的变化而变化是需要的；同样在D-S证据理论中，关于证据的信任也可以改变。D-S证据理论和概率论的区别是对无知的处理。概率论即便是在无知的情况下，也必须分布一个等量的概率值；而证据理论不要求必须对无知假设H赋予信任值，而是将基本概率分配给用户希望对其分配的环境子集。107定义2：若A且M(A)0，称A为M的一个焦元(Focalelement)。例：对={红，黄，白}的bpa为 M({红}，{黄}，{白}，{红，黄}，{红，白}，{黄，白},{红，黄，白}，{}) ={0.3，0，0.1，0.2，0.2，0，0.2，0}108定义3：命题的信任函数(Belieffunction)Bel:2

[0，1]为

其中2表示的所有子集。109 Bel(A)表示对A的总的信任。包含了这个集合和这个集合的所有包含A的任何一个子集。如上例： M({红}，{黄}，{白}，{红，黄}，{红，白}，{黄，白}，{红，黄，白}，{}) Bel(A)=Bel({红，白})=M({红})+M({白})+M({红，白})=0.3+0.1+0.2=0.6易见：Bel()=0 Bel()=1110 定义4：命题的似然函数(不能排斥函数，plausibilityfunction)Pl:2

[0,1]为

其中~A=–

APl(A)表示不否定A的信任程度。111信任函数与似然函数的关系： Pl(A)Bel(A)称Bel(A)和Pl(A)为命题A的下限函数和上限函数，记作A[Bel(A)，Pl(A)]。上下限的意义： A[0，1]说明对A一无所知。因为 Bel(A)=0说明A缺少信任。 Pl(A)=1–Bel(~A)=1Bel(~A)=0，说明对~A也缺少信任。112A[0，0]说明A是假 因为Bel(A)=0，Bel(~A)=1A[1，1]说明A是真 因为Bel(A)=1，Bel(~A)=0A[0.6，1]说明对A部分信任 因为Bel(A)=0.6，Bel(~A)=0A[0，0.4]说明对~A部分信任 因为Bel(A)=0，Bel(~A)=0.6A[0.3，0.9]说明同时对A和~A部分信任1132．证据的组合函数定义5：当多个Mi可组合时，它们的正交和：M=M1M2…Mn为 M()=0 A其中

若k-1=0，则Mi之间是矛盾的。K表示两个被组合证据的冲突程度。114组合证据：通过多个证据得到关于某件事物的更客观的判断。假设={airliner，bomber，fighter}，有两种类型的传感器，一种类型的传感器观察结果为m1（{B，F}）=0.7，m1（）=0.3另一种类型的传感器观察结果为m2（{B}）=0.9，m2()=0.1计算：m1m2=115Dempster采用了表格十字相乘法m2（{B}）=0.9M2()=0.1M1（{B，F}）=0.7{B}0.63{B，F}0.07M1（）=0.3{B}0.270.03116M3({B})=M1+M2({B})=0.63+0.27=0.9M3({B，F})=M1+M2({B，F})=0.07M3()=M1+M2()=0.03证据区间：支持目标飞机是轰炸机的最大可能是0.9+0.07+0.03=1，最小可能是0.9。因此证据区间是[0.9，1]。117这时，第三个传感器报告了关于飞机的一个冲突的证据：m3({a})=0.95，m3()=0.05，则应继续采用十字相乘法118M1+M2（{B}）=0.9M1+M2（{B，F}）=0.07M1+M2（）=0.03M3（{A}）=0.950.8550.0665{A}0.0285M3（）=0.05{B}0.045{B，F}0.0035（）0.0015119{A}0.0285{B}0.045{B，F}0.0035（）0.00150.9215把的情形按比例分给上面的前四种，使得=0120最终得：{A}0.0285+0.3346=0.3631{B}0.045+0.5282=0.5732{B，F}0.0035+0.0411=0.0446（）0.0015+0.0176=0.0191121第三章人工神经网络计算人工神经网络基础感知器及其训练算法BP算法Hopfield网与Boltzmann机122人工神经网络的概念人工神经网络（ArtificialNeuralNetworks，简记作ANN），是对人类大脑系统的一阶特性的一种描述。简单地讲，它是一个数学模型，可以用电子线路来实现，也可以用计算机程序来模拟，是人工智能研究的一种方法。人工神经网络是一个由大量简单的处理单元组成的高度复杂的大规模非线性自适应系统。123一、存储组织ANN力求从四个方面去模拟人脑的智能行为物理结构计算模拟存储与操作训练概述124生物神经网胞体(Soma)枝蔓（Dendrite）胞体(Soma)

轴突（Axon）突触（Synapse）125生物神经网基本特征1）神经元及其联接；2）神经元之间的联接强度决定信号传递的强弱；3）神经元之间的联接强度是可以随训练改变的；4）信号可以是起刺激作用的，也可以是起抑制作用的；5）一个神经元接受的信号的累积效果决定该神经元的状态；6)每个神经元可以有一个“阈值”。126生物神经元和人工神经元的对照关系生物神经元人工神经元作用树突输入层接收输入的信号细胞体加权和加工和处理信号轴突阈值函数（激活函数）控制输出突触输出层输出结果127神经元的结构模型神经元是一个多输入、单输出的非线形结构。树突相当于输入，轴突相当于输出，圆相当于神经元的胞体。M-P的简化模型：兴奋性输入抑制性输入

T128人工神经元的模拟人工神经元模拟生物神经元的一阶特性输入：X=（x1，x2，…，xn）联接权：W=（w1，w2，…，wn）T网络输入： net=∑xiwi向量形式： net=XW129激活函数(ActivationFunction)

激活函数：执行对该神经元所获得的网络输入的变换，也可以称为激励函数或活化函数：o=f（net）

1301、线性函数（LinerFunction）f（net）=k*net+c

netooc1312、斜面函数(RampFunction)

γ ifnet≥θf（net）=k*net if|net|<θ -γ ifnet≤-θ

γ>0为一常数，被称为饱和值，为该神经元的最大输出。

1322、斜面函数（RampFunction）γ-γθ

-θ

net

o

1333、阈值函数（ThresholdFunction）阶跃函数

β ifnet>θf（net）= -γ ifnet≤θβ、γ、θ均为非负实数，θ为阈值二值形式： 1 ifnet>θf（net）= 0 ifnet≤θ双极形式： 1 ifnet>θf（net）= -1 ifnet≤θ

1343、阈值函数（ThresholdFunction）阶跃函数β

-γθonet01354、S形函数

压缩函数（SquashingFunction）和逻辑函数（LogisticFunction）f（net）=a+b/(1+exp(-d*net))a，b，d为常数。它的饱和值为a和a+b。最简单形式为：f（net）=1/(1+exp(-d*net))函数的饱和值为0和1。S形函数有较好的增益控制

1364、S形函数

a+bo(0,c)netac=(a+b)/21375、其它函数

小波基函数如果采用小波基函数来做激活函数，则成为小波神经网络概率密度函数如果采用概率密度函数来做激活函数，则成为概率神经网络

138M-P模型

x2w2

∑fo=f（net）xnwn…net=XWx1w1McCulloch—Pitts（M—P）模型，也称为处理单元。139人工神经元拓扑图连接的拓扑表示

ANi wij ANj

140联接模式

用正号（“+”，可省略）表示传送来的信号起刺激作用，用于增加神经元的活跃度；用负号（“-”）表示传送来的信号起抑制作用，用于降低神经元的活跃度。141神经网络的典型结构

按照网络的结构区分，有正向网络和反向网络（反馈网络）；按照学习方式区分，有有监督学习网络和无监督学习网络；按照网络性能区分，有连续型网络和离散型网络，随机型网络和确定型网络；按照突触性质区分，有一阶线性关联网络和高价非线性关联网络。142联接模式

层次（又称为“级”）的划分，导致了神经元之间的三种不同的互连模式：

1、层（级）内联接层内联接又叫做区域内联接或侧联接用来加强和完成层内神经元之间的竞争2、

循环联接反馈信号

143联接模式3、层（级）间联接

层间（Inter-field）联接指不同层中的神经元之间的联接。这种联接用来实现层间的信号传递。前馈信号反馈信号

144简单单级网……x1x2…xno1o2omwnmw11w1mw2mwn1输出层输入层 145简单单级网W=（wij）输出层的第j个神经元的网络输入记为netj： netj=x1w1j+x2w2j+…+xnwnj其中,1≤j≤m。取NET=（net1，net2，…，netm）NET=XWO=F（NET）146单级横向反馈网输出层x1o1w11w1mx2o2w2m………xnomwn1输入层 V147单级横向反馈网

V=（vij）NET=XW+OVO=F（NET）时间参数——神经元的状态在主时钟的控制下同步变化。148多级网输出层隐藏层输入层o1o2om…x1x2xn………………149信号只被允许从较低层流向较高层。层号确定层的高低：层号较小者，层次较低，层号较大者，层次较高。输入层：记作第0层。该层负责接收来自网络外部的信息。第j层：第j-1层的直接后继层（j>0），它直接接受第j-1层的输出。层次划分150输出层：它是网络的最后一层，具有该网络的最大层号，负责输出网络的计算结果。隐藏层：除输入层和输出层以外的其它各层叫隐藏层。隐藏层不直接接受外界的信号，也不直接向外界发送信号。输出层隐藏层输入层o1o2om…x1x2xn………………151约定:输出层的层号为该网络的层数：n层网络，或n级网络。第j-1层到第j层的联接矩阵为第j层联接矩阵，输出层对应的矩阵叫输出层联接矩阵。一般用W（j）表示第j层矩阵。输出层隐藏层输入层o1o2om…x1x2xn………………W(1)W(2)W(3)W(h)152循环网x1o1输出层隐藏层输入层x2o2omxn…………………153循环网

如果将输出信号反馈到输入端,就可构成一个多层的循环网络。输入的原始信号被逐步地“加强”、被“修复”。大脑的短期记忆特征——看到的东西不是一下子就从脑海里消失的。稳定性：反馈信号会引起网络输出的不断变化。通常希望这种变化逐渐减小，并且最后消失。当变化最后消失时，网络就达到了平衡状态。如果这种变化不能消失，则称该网络是不稳定的。

154网络信息流向类型根据神经网络内部信息传递方向来分，有以下两种类型：前馈型网络网络信息处理方向是从输入层到中间层再到输出层逐层进行的，不存在反馈环路。多层前馈型网络可用一个有向无环图来表示。反馈型网络网络信息既可以从外界接受收入，也可以向外界输出，存在反馈环路。155神经网络的知识表示网络中的每个神经元只存储少量的信息；神经元只对输入的数据进行简单的逻辑运算或算术运算；运算操作由神经元自主进行，不由外部程序决定。156神经网络的学习

人工神经网络最具有吸引力的特点是它的学习能力。1962年，Rosenblatt给出了人工神经网络著名的学习定理：人工神经网络可以学会它可以表达的任何东西。人工神经网络的学习过程就是对它的训练过程。157学习过程是一种经过训练而使个体在行为上产生较为持久改变的过程。神经网络的学习算法很多，可以大体分为三类：有导师学习：监督学习，采用的是纠错规则。无导师学习：无监督学习，网络自行调整权值。灌输式学习：特定输入输出结果，学习是一次性的。神经网络的学习158有导师学习在学习训练过程中，需要不断给网络提供一个输入模式和一个期望网络正确输出的模式，这两个模式是一一对应的，通常称为“教师信号”。将神经网络的实际输出和期望输出相比较，当网络输出和期望的教师信号不符时，根据误差的方向和大小按一定规则调整权值，以使下一步网络的输出更接近期望结果。当网络对于各种给定的输入均能产生所期望的输出时，即认为网络已经在导师的训练下学会了训练集中包含的知识和规则，可以用来工作了。159有导师学习有导师学习的训练算法的主要步骤包括： 1）

从样本集合中取一个样本（Ai，Bi）； 2）

计算出网络的实际输出O； 3）

求D=Bi-O； 4）

根据D调整权矩阵W；5）对每个样本重复上述过程，直到对整个样本集来说，误差不超过规定范围，或者达到一定的运算次数。160无导师学习学习过程中，需要不断地给网络提供动态输入信息，网络能根据特有的内部结构和学习规则，在输入信息流中发现任何可能存在的模式和规律，同时能根据网络的功能和输入信息调整权值。这个过程称为网络的自组织，其结果是使网络能对属于同一类的模式进行自动分类。在无导师学习模式中，网络权值的调整不取决于外来教师信号的影响，认为学习评价标准来自于网络内部。161Hebb学习规则若第i与第j个神经元同时处于兴奋状态，则它们之间的连接应当加强，否则被减弱，增量与它们各自的兴奋程度si及sj成比例即Wij=asisj，0〈a〈1162竞争学习规则在学习过程中，网络各输出单元互相竞争，最好达到只有一个最强者激活。最常用的竞争规则可写为：163感知器（感知机）感知机是一种由单层神经元组成的神经网络。感知器的学习是有导师学习。感知器的训练算法的基本原理来源于著名的Hebb学习律。基本思想：逐步地将样本集里的样本输入到网络中，根据输出结果和理想输出之间的差别来调整网络中的权矩阵。164感知机算法二值网络：自变量及其函数的值、向量分量的值只取0和1函数、向量。权向量：W=(w1，w2，…，wn)输入向量：X=(x1，x2，…，xn)训练样本集：{(X，Y)|Y为输入向量X对应的输出}165感知机算法1、赋初值：各Wi一个较小的随机非零值；2、重复下列过程，直至完成：对每个样本，输入X和它的期望输出D；计算实际输出o=F（XW）；如果输出不正确，则修正权W。

当o=0时，取W=W+X， 当o=1时，取W=W-X；166多层前向网络多层前向网络，由输入层、一个或多个隐层和一个输出层组成。学习过程由信号正向传播和误差反向传播两个过程组成。信号正向传播和误差反向传播的各层权值调整过程是周而复始进行的。权值的不断调整的过程，就是学习训练的过程。该过程一直进行到误差减少到可以接受的程度，或者进行到预先设定的学习次数为止。167用输出层的误差调整输出层权矩阵，并用此误差估计输出层的直接前导层的误差，再用输出层前导层误差估计更前一层的误差。如此获得所有其它各层的误差估计，并用这些估计实现对权矩阵的修改。形成将输出端表现出的误差沿着与输入信号相反的方向逐级向输入端传递的过程。168多层前向网络算法采用了误差反向传播的方法，因此称为BP算法。（errorBackPropagation）算法使网络的学习可以收敛。优点：广泛的适应性和有效性。可以采用逐次修正法或一括修正法调整权值向量。弱点：训练速度非常慢、局部极小点的逃离问题。169网络的拓扑结构x1o1输出层隐藏层输入层x2o2omxn…………………W(1)W(2)W(3)W(L)170基本BP算法神经元的网络输入： neti=x1w1i+x2w2i+…+xnwni神经元的输出：171输出函数分析

0.5f′(net)0.25o01

1（0,0.5）

net（0,0）o应该将net的值尽量控制在收敛比较快的范围内。可以用其它的函数作为激活函数，只要该函数是处处可导的。172训练过程概述样本：(输入向量，理想输出向量)权初始化：“小随机数”与饱和状态；“不同”保证网络可以学习。1、向前传播阶段：（1）从样本集中取一个样本(Xp，Yp)，将Xp输入网络；（2）计算相应的实际输出Op： Op=Fl(…(F2(F1(XpW(1))W(2))…)W(L))173训练过程概述2、向后传播阶段——误差传播阶段：（1）计算实际输出Op与相应的理想输出Yp的差；（2）按极小化误差的方式调整权矩阵；（3）网络关于第p个样本的误差测度：（4）网络关于整个样本集的误差测度：174误差传播分析1、输出层权的调整wpq=wpq+∆wpq∆wpq=αδqop

=αfn′(netq)(yq-oq)op=αoq(1-oq)(yq-oq)op

wpqANpANq第L-1层第L层∆wpq1752、隐藏层权的调整

ANpANqANhvhp δpk-1δ1kwp1wpqδqkwpmδmk第k-2层第k层第k-1层……1762、隐藏层权的调整δpk-1的值和δ1k，δ2k，…，δmk有关。不妨认为δpk-1通过权wp1对δ1k做出贡献，通过权wp2对δ2k做出贡献，……通过权wpm对δmk做出贡献。δpk-1=fk-1′(netp)(wp1δ1k+wp2δ2k+…+wpmδmk)1772、隐藏层权的调整vhp=vhp+∆vhp

∆vhp=αδpk-1ohk-2 =αfk-1′(netp)(wp1δ1k+wp2δ2k+…+wpmδmk)ohk-2 =αopk-1(1-opk-1)(wp1δ1k+wp2δ2k+…+wpmδmk)ohk-2ANpANqANhvhp δpk-1δ1kwp1wpmδqkwpqδmk第k-2层第k层第k-1层……178算法改进收敛速度问题局部极小点问题网络瘫痪问题稳定性问题步长问题179Hopfield网络Hopfield网络的神经单元是全连接的，每两个单元都通过权值连接在一起。它的学习过程是一次完成的，工作过程则是模拟人的联想记忆，通过反复迭代完成的。Hopfield网络属于循环型网络，可分为离散型和连续型两种形式。离散型采用加权无向图表示，所有神经元都存在双向连接，每边都附有权值，每结点都附有阈值，经过符号函数作用后，形成两个状态。180网络结构

X1Xno1om………………181网络的输入输出神经元的网络输入：阈值函数：oj=1 ifnetj>θj0 ifnetj<θj

oj ifnetj=θj激活函数改为S形函数后，系统就成为一个连续系统。182Hopfield网络的工作方式Hopfield网络有两种工作方式：异步方式：在任一时刻t，只有某一个神经元状态发生变化，而其余神经元的状态保持不变。同步方式：在任一时刻t，有部分神经元或全部神经元的状态同时发生变化。当从某一时刻起神经网络不再发生变化，则称该Hopfield网络是稳定的。183Hopfield网络稳定性定理：对由N=（W，θ）描述的离散型Hopfield神经网络，若W为具有非负对角元的对称阵，则该网络具有串行稳定性；若W为非负定矩阵，则该网络具有并行稳定性。184Boltzmann机

统计Hopfield网在网络运行中，神经元状态与“人工温度”确定的概率相关网络运行模拟金属退火过程pi：ANi的状态取1的概率neti：ANi所获网络输入；θi：ANi的阈值；T：系统的人工温度。

185Boltzmann机的训练

固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温度上升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。186Boltzmann机的训练

模拟退火过程，是模拟金属退火过程，其实是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。模拟退火算法在搜索到局部最优解后，会以一定的概率向其它方向移动。也许经过几次这样的不是局部最优的移动后会到达全局最优点，于是就跳出了局部最大值。187Boltzmann机的训练

Boltzmann机是多级循环网络，是Hopfield网的一种扩展。神经元ANi实际输出状态oi=1的概率为：T趋近于0时，神经元的状态不再具有随机性，Boltzmann机退化成一般Hopfield网。188神经元ANi在运行中状态发生了变化：

Boltzmann机的能量函数(一致性函数)Boltzmann机的训练189如果ΔΕi>0，则应该选ANi输出为1，否则，应该选ANi输出为0。ΔΕi的值越大，神经元ANi应该处于状态1的概率就应该越大。反之，ΔΕi的值越小，神经元ANi应该处于状态1的概率就应该越小。从而，oi=1的概率为：

Boltzmann机的训练190处于状态a，b的概率Pa和Pb，对应于oi=1和oi=0，其它的神经元在a，b状态下不变。

Pa=γpi

Pb=γ（1-pi）

Boltzmann机的训练191网络进行足够多次迭代后，处于某状态的概率与此状态下的能量和此时系统的温度有关。由于高温时网络的各个状态出现的概率基本相同，这就给它逃离局部极小点提供了机会。当系统的温度较低时，如果Ea<Eb，则Pa>Pb：网络处于较低能量状态的概率较大。

Boltzmann机的训练192Hopfield网解决TSP问题1985年，J.J.Hopfield和D.W.Tank用循环网求解TSP。试验表明，当城市的个数不超过30时，多可以给出最优解的近似解。而当城市的个数超过30时，最终的结果就不太理想了。

n个城市间存在n!/(2n)条可能路径。设问题中含有n个城市,用n*n个神经元构成网络。

193Hopfield网解决TSP问题dxy——城市X与城市Y之间的距离；yxi——城市X的第i个神经元的状态：

1 城市X在第i个被访问 yxi= 0 城市X不在第i个被访问wxi,yj——城市X的第i个神经元到城市Y的第j个神经元的连接权。

194Hopfield网解决TSP问题例如：四个城市X、Y、Z、W城市名访问顺序标示1234X0100Y0001Z1000W0010195Hopfield网解决TSP问题

联接矩阵

wxi,yj=-Aδxy(1-δij)–Bδij(1-δxy)–C–ζdxy(δji+1+δji-1)

1 如果i=jδj= 0 如果i≠j

196网络的能量函数197网络的能量函数

仅当所有的城市最多只被访问一次时取得极小值0。A、B、C、D为惩罚因子第1项198网络的能量函数仅当每次最多只访问一个城市时取得极小值0。第2项199网络的能量函数当且仅当所有的n个城市一共被访问n次时才取得最小值0。第3项200网络的能量函数表示按照当前的访问路线的安排，所需要走的路径的总长度。

第4项201神经网络的特点大规模并行处理与容错能力信息的分布式存储与处理学习与自适应能力联想与记忆能力202神经网络的应用领域信息处理领域信号处理模式识别数据压缩自动化领域系统辨识神经控制器智能检测203神经网络的应用领域工程领域汽车工程军事工程化学工程水利工程医学领域检测数据分析生物活性研究医学专家系统经济领域信贷分析市场预测204第四章演化计算演化计算的概念遗传算法的基本术语遗传算法的理论基础模式定理遗传算法的实现技术205优化搜索问题优化问题，是针对某种问题，去寻找最好的、或者尽可能好的解。随着问题复杂度的增加，算法的效率成为选择的关键。206优化搜索问题207优化搜索问题208优化搜索问题209优化搜索问题210优化搜索问题211优化搜索问题212优化搜索问题213214215染色体216演化计算演化计算（EvolutionaryComputation）是一类模拟生物进化过程求解的人工智能计算方法。实际上是一种自适应的机器学习方法，核心思想是利用进化信息指导搜索或计算。生物进化是通过遗传、繁殖、变异、竞争和选择来实现的，如果把待解决的问题理解为对某个目标函数的全局优化，则演化计算就是建立在模拟生物进化过程基础上的随机搜索优化技术。217囚犯困境问题囚犯困境问题是一个古老的游戏问题。假设有两个囚犯共同参与了某项犯罪而被关在两个不同的牢房里。每个囚犯都被要求供出犯罪事实，依据他们的表现，审问人员将对他们进行惩罚或者给出不同程度的奖励。每个囚犯或者选择背叛同伴，或者选择与对方订立攻守同盟，即两人合作。如果只有一人选择背叛，则该人就会受到奖励，另一人会被惩罚；如果两人都选择背叛，则两人都会被惩罚；如果两人都选择合作，则两人都会受到中等程度的奖励。218囚犯困境问题对囚犯的奖励与惩罚以下表决定，则囚犯困境问题是指：对每一个囚犯而言，如何选择背叛与合作，以使自己能获得最高的奖励。219囚犯困境问题囚犯1囚犯2P1P2评注背叛背叛11相互背叛受惩罚背叛合作50背叛者受奖励合作背叛05受奖诱发背叛合作合作33相互合作受奖220遗传算法概述遗传算法(GeneticAlgorithms)是一类以Darwin自然进化论与Mendal遗传变异理论为基础的求解复杂全局优化问题的仿生型算法。由美国学者Holland等人在1975年发展起来的。GA对包含可能解的群体反复使用遗传学的基本操作，不断生成新的群体，使种群不断优化，以求解满足要求的最优解或准最优解。221遗传算法概述遗传算法的主要特点是：处理参数集合的编码，而不是参数的本身；始终保持整个种群而不是个体的进化；只需知道目标函数的信息，仅用适应度来评估个体，无需搜索空间的其它知识；使用随机转换规则而不是确定性规则指导搜索，不易陷入局部极值点，并能以较大概率找到全局最优点。算法具有很强的并行性，适合于大规模复杂问题求解。222若干术语染色体：生物遗传物质的主要载体称为染色体。DNA：染色体中的最主要遗传物质。基因：基因是控制生物性状的遗传物质的功能单位和结构单位。基因座：染色体中基因的位置称为基因座。等位基因：基因所取的值称为等位基因。单倍体：细胞核中有n个正常的不配对染色体。二倍体、多倍体：细胞核中有2n或更多倍的正常配对染色体。223若干术语一定数量的个体（individual）组成了群体（population）。一个群体是若干个个体的集合。群体中个体的数目称为群体规模（populationsize）。各个个体对环境的适应程度称为适应度（fitness）。适应度越大，说明个体对环境越适应。224若干术语位串：个体的表示形式，对应于遗传学中的染色体。基因编码：生物的基因编码决定生物的性状，一个基因编码对应着遗传算法中的某个解。繁殖：重组染色体基因，形成新的个体。交叉：有性生殖生物在繁殖下一代时，两个同源染色体在某一相同位置处被切断，其前后两个串分别交叉组合形成两个新的染色体，这个过程称为交叉。遗传算法中把交叉当作一个算子。在很多应用中，交叉是以一定概率发生的，称为交叉概率。225若干术语选择：选择是从当前群体中选择出优良的个体，使它们有机会作为父代产生后代个体。判断个体优良与否的准则就是各自的适应度的值。变异：在染色体中的某个基因发生突变。遗传算法中把变异当作一个算子，变异同样是以一定概率发生的，称为变异概率。变异的目的是为了克服陷入局部解的可能。226名词意义对照表生物遗传遗传算法群体问题搜索空间的一组有效解种群经过选择产生的新群体染色体问题解的编码串基因染色体的一个编码单元适应能力染色体的适应值交配两个染色体交换部分基因得到两个新的子代染色体变异染色体某些基因的数值发生改变进化结束算法满足终止条件时结束，找到全局最优解227遗传算法的要素参数编码初始群体的设定适应度函数的设计控制参数设定遗传参数设定228遗传算法概述遗传算法可描述如下：1、定义问题与目标函数F；2、选择候选解作为初始种群，每个解用一个二进制位串X表示；3、计算每个染色体的适应度值F（Xi）；4、指定与其适值成正比的繁殖概率pi；5、根据概率pi选择染色体，通过交叉变异等产生新一代染色体种群；6、如果找到了满意解或其他条件，则结束；否则返回3。229遗传算法的框图产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位变异运算否产生新一代群体执行n/2次230遗传算法的伪代码/*p(t)表示某一代的群体，t为当前进化代数，Best表示目前已找到