人工智能及其应用chapter7-071106课件.ppt

1、 7.1 分层设计原理n分层设计的基本思想分层设计的基本思想:v将初始问题分解为等效的几个子问题；将初始问题分解为等效的几个子问题；v对每个子问题进行分析；如果必要继续分解子问题，对每个子问题进行分析；如果必要继续分解子问题，直到子问题直到子问题能够用程序设计语言将其轻而易举地表能够用程序设计语言将其轻而易举地表达清楚达清楚为止。为止。v可用树状结构表示分层设计的结果可用树状结构表示分层设计的结果。人工智能及其应用1 7.1 分层设计原理n例：例：求一组数的平均值求一组数的平均值F 初始化：提示信息，输入一组数字。初始化：提示信息，输入一组数字。F 计算：计算这组数的累加和，计算平均值。计算：

2、计算这组数的累加和，计算平均值。F 输出：输出解释信息、程序运行结果。输出：输出解释信息、程序运行结果。人工智能及其应用2 求平均值的分层设计过程 下图为分层设计结果下图为分层设计结果 求平均值求平均值第一层第一层初始化初始化计计 算算输输 出出显示显示有关有关程序程序信息信息读读入入N N读读入入N N个个数数计计算算平平均均值值计算计算N N 个个数的数的总和总和显显示示平平均均值值输输出出提提示示信信息息第二层第二层第三层第三层人工智能及其应用3 求平均值的分层设计过程此设计结果描述此设计结果描述为为Prolog程序：程序：ch7ex01.pro/*Program ch7ex01.pro

3、*/DOMAINSn=integers,ave=realslist=integer*PREDICATESinit(n,slist)calc(n,slist,ave)averagesum(slist,s)input(n,slist)output(ave)人工智能及其应用4CLAUSESaverage:-init(N,List),calc(N,List,Ave),output(Ave).init(N,List):-write(“Calculate the average of a list of numbers.n),nl,write(How many numbers?),readint(N),n

4、l,write(Now type in ),write(N),write(Numbers),nl,nl,input(N,List).calc(N,List,Ave):-sum(List,Sum),Ave=Sum/N.output(Ave):-nl,nl,write(The average of your numbers is=),write(Ave),nl,nl.input(0,):-!.input(N,H|T):-readint(H),M=N-1,input(M,T).sum(,0):-!.sum(H|T,S):-sum(T,S1),S=H+S1.GOALaverage.人工智能及其应用5

5、7.2 智能识别系统 问题描述 系统结构与设计 智能识别系统的使用人工智能及其应用6 问题描述KennelKennel俱乐部关于种狗的分类俱乐部关于种狗的分类：种种 狗狗Pedigree Dogs猎猎 狗狗Hounds玩玩具具狗狗Toys犭犭 更更Terriers捡捡物物狗狗Gun Dogs工工具具狗狗Working Dogs商商品品狗狗UtilitiesBegeleCreyhoundIrishWolfhoundEnglishSetterColdenRetrieverPointerCairnTerrierIrishTerrierStaffordshireBull TerrierChihuahu

6、aPugYorkshireTerrierHuskyRottweilerSt BernardBulldogChow ChowDalmatian人工智能及其应用7 系统结构与设计识别用户的狗。识别用户的狗。把识别结果输出给用户。把识别结果输出给用户。显示提示信息。显示提示信息。清除识别过程中的中间结果及信息。清除识别过程中的中间结果及信息。d do og gs s显显示示提提示示信信息息识识 别别 狗狗输输 出出 结结 论论/解解 释释 结结 论论忘忘记记对对话话中中掌掌握握的的信信息息向向用用户户提提问问记记住住用用户户对对问问题题的的回回答答人工智能及其应用8 系统结构与设计即即“dogs”系

7、统的最高层目标可以用系统的最高层目标可以用Prolog的规则表示如下：的规则表示如下：dogs:-init,identify(Dog),outmessage(Dog),forget.此最高层目标说明了整个程序由以下四个子目标组成：此最高层目标说明了整个程序由以下四个子目标组成：FInit显示提示信息，告诉用户程序的目的和操作方法。显示提示信息，告诉用户程序的目的和操作方法。Fidentify识别用户的狗。识别用户的狗。Fout_message把识别结果输出给用户，输出信息中包把识别结果输出给用户，输出信息中包括狗的种类名；或者告诉用户无法识别狗品种的原因。括狗的种类名；或者告诉用户无法识别狗品

8、种的原因。Fforget从系统中清除掉刚才识别过的狗的信息，以避从系统中清除掉刚才识别过的狗的信息，以避免在识别另一只狗时发生混淆。免在识别另一只狗时发生混淆。人工智能及其应用9 智能识别系统的使用例：例：“dogs”智能识别系统识别纯种狗智能识别系统识别纯种狗greyhound (1)运行该系统时，在用户终端上会显示出下述信息：运行该系统时，在用户终端上会显示出下述信息：This is a program to identify predigree dogs,according to the groupings of the Kennel Club of Great Britain.The

9、program will ask you a series of questions to which you must answer yes or no.The program will then attempt to identify your dog.Press the return key to continue.在按下回车键之后，系统将向用户提出一系列问题，用户要用在按下回车键之后，系统将向用户提出一系列问题，用户要用“yes”或或“no”来回答。下面就是这些问答信息和系统推出的识别结果。来回答。下面就是这些问答信息和系统推出的识别结果。人工智能及其应用10 智能识别系统的使用Is

10、it a hunting dog that tracks by sight or scent?yes.Is it a muscular dog?yes.Is it a compact dog?no.Does it have a short coat?yes.Is it used for racing?yes.*Your dog is a(n)greyhoundProgram finished.Do you wish to run the program again?no.人工智能及其应用11 智能识别系统的使用(2)而下面的对话告诉我们，当该系统无法识别用户的狗品种时，它是而下面的对话告诉我们

11、，当该系统无法识别用户的狗品种时，它是如何回答的：如何回答的：Is it a hunting dog that tracks by sight or scent?yes.Is it a muscular dog?no.*Failure!I cannot identify your dog.Program finished.当系统识别不出这只狗时，系统会再次询问用户是否希望重新运行当系统识别不出这只狗时，系统会再次询问用户是否希望重新运行这一程序。如果回答这一程序。如果回答“no”，系统就会终止。，系统就会终止。Do you wish to run the Program again?no.人工

12、智能及其应用127.3 智能诊断系统 问题描述及系统开发方法 系统结构与设计 智能诊断系统的使用人工智能及其应用13 问题描述及系统开发方法n可信度一般形式可信度一般形式 :如果如果:条件条件(X1)(X1)的可信度为的可信度为(Y1)(Y1)且且 条件条件(X2)(X2)的可信度为的可信度为(Y2)(Y2)且且 条件条件(X3)(X3)的可信度为的可信度为(Y3)(Y3)且且 则有：结论则有：结论(X)(X)的可信度为的可信度为(Y)(Y)。人工智能及其应用14 问题描述及系统开发方法开发智能诊断系统的过程可分为下列五个步骤：开发智能诊断系统的过程可分为下列五个步骤：(1)(1)确定问题范围

13、确定问题范围:即确定对象问题的范围，以及问题即确定对象问题的范围，以及问题范围内所涉及的领域、对象和关系。本例将介绍的范围内所涉及的领域、对象和关系。本例将介绍的营养分析系统其知识范围包括了营养分析系统其知识范围包括了1313种营养缺乏症，种营养缺乏症，涉及的对象是涉及的对象是4545种症状，对象的全体构成了深度优种症状，对象的全体构成了深度优先逆向推理系统。先逆向推理系统。(2)(2)收集事实收集事实:即收集支持每个营养缺乏症所需要的事即收集支持每个营养缺乏症所需要的事实。有关营养分析的事实表列出了开发一个营养分实。有关营养分析的事实表列出了开发一个营养分析系统所需的事实，它们是按照各种缺乏

14、症及其相析系统所需的事实，它们是按照各种缺乏症及其相关症状分别排列的。关症状分别排列的。人工智能及其应用15序号序号缺缺 乏乏 症症症症 状状1维生素维生素A缺乏症缺乏症Bitot氏斑氏斑(眼球上的白色斑点眼球上的白色斑点)；夜盲症；夜盲症(暗处眼睛无调节能力暗处眼睛无调节能力)；麦；麦粒肿，结膜炎；牙龈脆弱、出血；皮肤粗糙、干燥、发红；粉粒肿，结膜炎；牙龈脆弱、出血；皮肤粗糙、干燥、发红；粉刺、痤疮；刺、痤疮；2维生素维生素B1缺乏症缺乏症弱视弱视(视力模糊视力模糊)；神经过敏；智力减退；健忘；迟钝，浮肿；厌食；神经过敏；智力减退；健忘；迟钝，浮肿；厌食；精神混乱；精神不易集中；眩晕；皮肤溃

15、疡精神混乱；精神不易集中；眩晕；皮肤溃疡3维生素维生素B2缺乏症缺乏症眼球发红，对光敏感；角膜溃疡；紫舌；嘴裂；眩晕；皮肤溃疡；眼球发红，对光敏感；角膜溃疡；紫舌；嘴裂；眩晕；皮肤溃疡；油性皮肤；迟钝、浮肿油性皮肤；迟钝、浮肿4维生素维生素B3缺乏症缺乏症舌、嘴、牙龈、口腔溃疡；红舌；精神过敏、抑郁；忧虑、易疲舌、嘴、牙龈、口腔溃疡；红舌；精神过敏、抑郁；忧虑、易疲劳、失眠；精神抑郁；皮肤干燥、发暗、有鳞屑；消化不良劳、失眠；精神抑郁；皮肤干燥、发暗、有鳞屑；消化不良5维生素维生素B5缺乏症缺乏症关节炎；巨舌；嘴裂；胀肚；精神、抑郁；眩晕；角膜溃疡关节炎；巨舌；嘴裂；胀肚；精神、抑郁；眩晕；角

16、膜溃疡6维生素维生素B6缺乏症缺乏症角膜溃疡；舌、嘴、齿龈溃疡；嘴裂；角膜溃疡；舌、嘴、齿龈溃疡；嘴裂；(妇女妇女)体内积水体内积水7维生素维生素B12缺乏症缺乏症光舌或亮舌；条件反射慢；口吃；精神不易集中、抑郁光舌或亮舌；条件反射慢；口吃；精神不易集中、抑郁8维生素维生素C缺乏症缺乏症伤口愈合慢；对传染病的抵抗力低；角膜溃疡；牙龈脆弱、出血；伤口愈合慢；对传染病的抵抗力低；角膜溃疡；牙龈脆弱、出血；口腔溃疡；关节炎；粉刺，痤疮；皮肤干裂；口腔溃疡；关节炎；粉刺，痤疮；皮肤干裂；营养缺乏症及其症状表现事实表营养缺乏症及其症状表现事实表 人工智能及其应用16 问题描述及系统开发方法(3)(3)列

17、事实表列事实表:用上表描述中的事实可得到下页事实表用上表描述中的事实可得到下页事实表(全表见书中表全表见书中表7-2)7-2)。其中，用列表示结论（即缺乏。其中，用列表示结论（即缺乏症），用行表示证据（即症状）。相关的结论与证据症），用行表示证据（即症状）。相关的结论与证据用行、列交叉点处加用行、列交叉点处加“”标记表示。标记表示。(4)(4)事实分组：对事实表中的症状进行分组，尽量把相事实分组：对事实表中的症状进行分组，尽量把相似的症状放在一起。本例仅采用一级分组，分组结果似的症状放在一起。本例仅采用一级分组，分组结果见事实分组表。见事实分组表。(5)(5)编写程序编写程序人工智能及其应用1

18、7缺乏症症状缺乏症症状A AB1B1B2B2B3B3B5B5B6B6B12B12C CE E钙钙叶叶酸酸铁铁蛋蛋白白质质BitotBitot氏斑氏斑(眼眼)夜盲症夜盲症麦粒肿，结膜炎麦粒肿，结膜炎事实表事实表人工智能及其应用18缺乏症缺乏症症状症状A AB1B1B2B2B3B3B5B5B6B6B12B12C CE E钙钙叶酸叶酸铁铁蛋白质蛋白质眼眼睛睛BitotBitot氏斑氏斑(眼眼)夜盲症夜盲症麦粒肿，麦粒肿，结膜炎结膜炎弱视弱视眼球发红，眼球发红，对光敏感对光敏感角膜溃疡角膜溃疡事实分组表事实分组表人工智能及其应用19系统结构与设计分层设计分层设计:v输入症状输入症状v智能诊断智能诊断

19、v清空数据库清空数据库 v退出退出营营养养分分析析诊诊断断系系统统输输入入症症状状退退 出出清清空空数数据据库库智智能能诊诊断断按按症症状状做做分分组组选选择择存存事事实实库库症症状状匹匹配配累累计计可可信信度度输输出出结结果果人工智能及其应用20 系统结构与设计n顶层菜单式规则：顶层菜单式规则：go_once_read_choice(1):-go_choice(1),go_once,!.go_once_read_choice(4):-!.go_once_read_choice(_):-write(“choice error”),nl,write(“Please make option aga

20、in(“1-4):”),nl,readint(Choice),go_once_read_choice(Choice).F第一个第一个go_once_read_choice(1)规则表示进入第一个功能分支规则表示进入第一个功能分支输输入症状。进入入症状。进入“智能诊断智能诊断”或或“清空数据库清空数据库”与此同理。与此同理。F第二个第二个go_once_read_choice(4)规则表示退出系统。规则表示退出系统。F第三个第三个go_once_read_choice(_)规则表示用户没有输入规则表示用户没有输入1-41-4的选项的选项时，要求重新输入，直到输入合法的选项为止。时，要求重新输入，

21、直到输入合法的选项为止。人工智能及其应用21n第二级菜单式规则：第二级菜单式规则：(1)(1)输入症状：输入症状：go_choice(1)go_choice(1)为用户提供了为用户提供了“眼睛、嘴、骨骼眼睛、嘴、骨骼”共共7 7大大类输入症状选项以及退出功能。类输入症状选项以及退出功能。branch_mainbranch_main是某一大类中的症状分是某一大类中的症状分类子菜单，规则设计方法与类子菜单，规则设计方法与go_choicego_choice类似。类似。go_choice(1):-write(“*”),nl,write(“The Enter Symptom_1 Menu”),nl,w

22、rite(“*”),nl,write(“please select category of symptom:”),nl,write(“=1:Eyesn”,“=2:Mouthn”),nl,readint(Choice),branch_main(Choice),Choice0,Choice=0.19,setflag1,nl,write(“Theres evidence of a”,Deficiency),write(“deficiency”,N),nl.writeout(_,_).人工智能及其应用23n第二级菜单式规则：第二级菜单式规则：(3)(3)清空数据库清空数据库 ：go_choice(3)

23、go_choice(3)进入清空数据库这一功能分支，系统采用进入清空数据库这一功能分支，系统采用clear_factsclear_facts谓词分别来清除事实数据库中的症状、营养缺乏症、谓词分别来清除事实数据库中的症状、营养缺乏症、姓名、性别、年龄等信息，为下一次运行做好准备。姓名、性别、年龄等信息，为下一次运行做好准备。例如清除症状数据库为：例如清除症状数据库为：clear_facts:-retract(xpositive(_,_),fail.人工智能及其应用24 智能诊断系统的使用 第一步：第一步：清空事实数据库清空事实数据库;第二步：第二步：输入症状输入症状;第三步：第三步：执行诊断执行

24、诊断;第四步：第四步：显示最后诊断结果。显示最后诊断结果。人工智能及其应用25 7.4 智能规划系统 规划问题 系统结构与设计 智能规划系统的使用人工智能及其应用26规划问题n智能系统在智能系统在AI应用系统中的级别：应用系统中的级别：过过程程式式系系统统诊诊断断系系统统规规划划系系统统决决策策系系统统n 例：例：以在给定房间中安置特定家具为实例，介绍以在给定房间中安置特定家具为实例，介绍智能规划系统的设计思想。如下页图所示，该智能智能规划系统的设计思想。如下页图所示，该智能规划系统首先应该接受给定的房间基本信息和欲安规划系统首先应该接受给定的房间基本信息和欲安置家具基本信息，然后依次扫描合适

25、的安置条件，置家具基本信息，然后依次扫描合适的安置条件，直至达到最终规划目标。直至达到最终规划目标。人工智能及其应用27 规划问题房间内家具安置的正向推理路径：房间内家具安置的正向推理路径：房房间间尺尺寸寸安安置置书书桌桌椅椅子子尺尺寸寸书书柜柜尺尺寸寸写写字字椅椅尺尺寸寸书书桌桌尺尺寸寸安安置置书书柜柜安安置置写写字字椅椅安安置置椅椅子子人工智能及其应用28 系统结构与设计 系统分层设计：系统分层设计：v数据库初始化。数据库初始化。v输入原始数据。输入原始数据。v扫描条件子句，扫描条件子句，寻找成功的匹配。寻找成功的匹配。v扫描动作子句。扫描动作子句。v程序不断地进行程序不断地进行扫描。扫描

26、。规规划划系系统统安置结果输出安置结果输出家具安置规划家具安置规划初初始始化化扫描扫描对应对应的目的目标并标并产生产生安置安置动作动作扫描扫描匹配匹配的条的条件组件组输入输入各种各种原始原始数据数据人工智能及其应用29 系统结构与设计系统中的知识可用如下一系列规则表达：系统中的知识可用如下一系列规则表达：规则规则1:IF 条件条件1 THEN 目标目标1规则规则2:IF 条件条件2 THEN 动作动作1规则规则3:IF 目标目标1 AND 条件条件3 THEN 动作动作2参照上页图，可通过下述规则实现正向推理策略：参照上页图，可通过下述规则实现正向推理策略：run:-initialize,in

27、put_data,/*Get the input data*/scan_conditions(A,B,C),/*Scan for a matching condition set*/try_action(A,B,C),/*Scan for the corresponding goal&action*/fail.run:-print_summary./*Print the planning result*/人工智能及其应用30 智能规划系统的使用 (1)(1)initialize：将将相关的房间初始信息送入事实数据库；相关的房间初始信息送入事实数据库；(2)(2)input_data：通过与用户

28、会话获得各个欲安置家具的名通过与用户会话获得各个欲安置家具的名称、尺寸，房间内门窗的方位及尺寸信息，以及电源插座称、尺寸，房间内门窗的方位及尺寸信息，以及电源插座的位置信息。的位置信息。(3)(3)scan_conditions：寻求匹配的可安置条件，并寻找对应寻求匹配的可安置条件，并寻找对应的的try_action动作子句，尝试完成各项家具的安置规划。动作子句，尝试完成各项家具的安置规划。(4)(4)print_summary：系统输出已安置的规划结果及未安置系统输出已安置的规划结果及未安置的家具，并根据现有房间条件和安置结果输出建议用户购的家具，并根据现有房间条件和安置结果输出建议用户购买

29、的物品清单。买的物品清单。人工智能及其应用31 7.5 基于框架表示的智能系统 基于框架的智能系统设计框架系统的使用 人工智能及其应用32基于框架的智能系统设计v天气预报系统分层设计结构天气预报系统分层设计结构 v天气知识框架槽天气知识框架槽 v会话框架会话框架 人工智能及其应用33 基于框架的智能系统设计天气预报系统的分层设计：天气预报系统的分层设计：天气预报系统天气预报系统初初始始化化与用与用户对户对话并话并接收接收测量测量数据数据查找查找匹配匹配的天的天气预气预报结报结果值果值输出输出预报预报结果结果人工智能及其应用34 基于框架的智能系统设计气压表压力气压表压力 (高，低，正常，等等高

30、，低，正常，等等)气压表压力变化气压表压力变化 (稳定，缓慢下降稳定，缓慢下降)风向风向 (东，东南，东，东南，)季节季节 (春，夏，秋，东春，夏，秋，东)天气结果天气结果 （晴，多云，雨，（晴，多云，雨，）v框架中包含了现行的框架中包含了现行的天气条件组。天气条件组。v所有的槽所有的槽(除最后一个除最后一个)均可以通过与用户对均可以通过与用户对话得到填充话得到填充。v最后一个槽要通过其最后一个槽要通过其它槽计算或演绎得到。它槽计算或演绎得到。天气框架槽天气框架槽人工智能及其应用35 基于框架的智能系统设计n 建立框架目的：建立框架目的：用于存放会话的问题。用于存放会话的问题。n 框架的框架的

31、PrologProlog表示：表示：query(Slotname,Question)n 会话框架：会话框架：槽槽 名名问问 题题 人工智能及其应用36 基于框架的智能系统设计该系统的顶层目标：该系统的顶层目标：go:-init,/*Clear the Facts Database&load the initial knowledge*/user_enter_value,/*Dialog with the user and get the input data*/use_rules,/*Use the observed values to forecast the weather*/write_

32、weather./*Output the weather forecast*/go:-write(“Sorry,I can not determine the weather.”).init:-clear_rule,load_kd.clear_rule:-retract(_),fail.clear_rule.load_kd:-consult(“WeatherFrame_KD.dba”).人工智能及其应用37 框架系统的使用 天气预报框架系统运行时，会依次询问并要求用户输入其天气预报框架系统运行时，会依次询问并要求用户输入其观测值：观测值：气压值：气压值：非常低、低、正常、高、非常高；相应输入选

33、项分别是非常低、低、正常、高、非常高；相应输入选项分别是数字数字1-5。气压变化情况：气压变化情况：剧烈下降、缓慢下降、急剧上升和缓慢上升剧烈下降、缓慢下降、急剧上升和缓慢上升；相相应输入选项分别是数字应输入选项分别是数字1-4。风向：风向：北、东北、东、东南、南、西南、西、西北；相应输入选北、东北、东、东南、南、西南、西、西北；相应输入选项分别是数字项分别是数字1-8。季节：季节：春、夏、秋、冬；相应输入选项分别是数字春、夏、秋、冬；相应输入选项分别是数字1-4。人工智能及其应用38 框架系统的使用一个该系统运行结果示例如下：一个该系统运行结果示例如下：What is the baromet

34、ric pressure?4How is the barometric pressure changing?1What direction is the wind from?4What is the season?1The Possible Result(s)is(are)as follows:(1)Windy,rain within 12 hours.Press any key to return人工智能及其应用39 7.6 神经网络的应用 BP神经网络的应用用Hopfield网络求解TSP问题 人工智能及其应用40 BP神经网络的应用n“熟人熟人”的学习问题：的学习问题：下页图所示网络的目

35、标：确定输入的两个人是否相识，下页图所示网络的目标：确定输入的两个人是否相识，其任务为学习图中上半部分一组其任务为学习图中上半部分一组3 3人中的任何一人是人中的任何一人是下半部分一组下半部分一组3 3人中任何一人的熟人，用节点人中任何一人的熟人，用节点A A 代表。代表。如果网络的输出大于如果网络的输出大于0.90.9，那么就判定这两个人，那么就判定这两个人“相相识识”；如果输出小于；如果输出小于0.10.1，就判定为，就判定为“不相识不相识”；其；其它它 结果被认为是模糊不定的。结果被认为是模糊不定的。人工智能及其应用41 BP神经网络的应用假设输入仅为二值，即假设输入仅为二值，即0 0或

36、或1 1，H1H1和和H2H2为隐节点，为隐节点，具有具有“与门与门”的作用。的作用。在该问题中假设在该问题中假设Robert、Raquel和和Romeo是同胞，是同胞，而而Joan、James和和Juliet也是同胞，因此不能把也是同胞，因此不能把他们相互视为熟人。他们相互视为熟人。RobertRaquelRomeoJoanJamesJulietAH1H2人工智能及其应用42下表给出这样的认识描述：下表给出这样的认识描述：对于对于1515种可能的输入组合，种可能的输入组合，其对应其对应“熟人熟人”的输出有的输出有9 9种，而对应种，而对应“同胞同胞”的输出为的输出为6 6种。种。Robert

37、 Raquel RomeoJoanJamesJuliet熟人熟人 同胞同胞110000011010000101100101100100101000101010000110010100100100101001000110001100100010101000100110000110010001010100001101人工智能及其应用43 BP神经网络的应用“熟人熟人”问题的学习结果问题的学习结果：00.10.20.30.40.5100200300400500权值变化周期均方误差人工智能及其应用44 BP神经网络的应用学习行为与比率参数的关系：学习行为与比率参数的关系：00.10.20.30.40.

38、50.60.7100200 300 400 500 600 700 800 900权值变化周期均方误差8.04.00.250.51.02.0人工智能及其应用45 用Hopfield网络求解TSP问题n适用于：适用于：模糊推理模型、非线性辨识和自适应控制模型中模糊推理模型、非线性辨识和自适应控制模型中的问题学习求解。的问题学习求解。n旅行商最优旅行商最优路径问题路径问题(TSP)：设有设有n n个城市，两两城市间均有直线路径个城市，两两城市间均有直线路径 ，要，要求寻找一条闭合的路径，该路径必须历经每个城市，求寻找一条闭合的路径，该路径必须历经每个城市，且仅经过一次，当返回起始城市时总的路径长度

39、最短。且仅经过一次，当返回起始城市时总的路径长度最短。ijd人工智能及其应用46 用Hopfield网络求解TSP问题 为建立表述为建立表述TSPTSP问题状态与结果的人工神经网络模型，以问题状态与结果的人工神经网络模型，以n=5n=5为例设置如下表所示的为例设置如下表所示的置换矩阵置换矩阵。城市名称城市名称路径访问顺序路径访问顺序12345A01000B00010C10000D00001E00100人工智能及其应用47 用Hopfield网络求解TSP问题 置换矩阵中的每列最多有一个置换矩阵中的每列最多有一个“1”1”，表示每次仅经，表示每次仅经过一个城市；每行最多有一个过一个城市；每行最多

40、有一个“”“”1 1，表示每个城市仅，表示每个城市仅被经历过一次；置换矩阵中被经历过一次；置换矩阵中“1”1”的个数为（城市个的个数为（城市个数）。数）。n能量函数的构造：能量函数的构造：各城市间的距离用各城市间的距离用 表示，作为约束信息以确定表示，作为约束信息以确定各神经元间的联接强度；神经元输出电压表示为各神经元间的联接强度；神经元输出电压表示为 ，其中其中x表示城市名，表示城市名，i 表示该城市在路径中的顺序，表示该城市在路径中的顺序，表示城市表示城市x 在路径中被访问的次序为在路径中被访问的次序为i。yxd,ixV,1,ixV人工智能及其应用48 用Hopfield网络求解TSP问题

41、(1)置换矩阵：置换矩阵：上式满足最小时对应如下情况：上式满足最小时对应如下情况：第一项对应置换矩阵中每一行最多一个第一项对应置换矩阵中每一行最多一个“1”1”；第二项对应置换矩阵中每一列最多一个第二项对应置换矩阵中每一列最多一个“1”1”；第三项对应置换矩阵中只有个第三项对应置换矩阵中只有个“1”1”。此外，因为路径是循环的，所以此外，因为路径是循环的，所以 ，满足取模，满足取模“n”n”的规律。的规律。2,222nVCVVBVVAxiixixxyiyixxiijjxixjyjnyVV,人工智能及其应用49 用Hopfield网络求解TSP问题(2)路径最短：路径最短：上式表示若路径中包括距

42、离上式表示若路径中包括距离 ，则城市，则城市x的访问次序为的访问次序为i时，城市时，城市y的访问次序应为的访问次序应为i-1或或i+1。能量函数描述为：能量函数描述为：)(21,iyyxxxyiixyxVVVdDyxd,xxyiiyiyixyxxiixixxyiyixxiijjxixVVVdDnVCVVBVVAE)(2 2221,1,2,人工智能及其应用50 用Hopfield网络求解TSP问题例：例：下图是下图是Hopfield网络应用于含网络应用于含8 8个城市的个城市的TSP问题求解问题求解过程，过程，(a)图表示图表示8 8个城市的初始位置；个城市的初始位置；(b)图为网络结构图为网络

43、结构（共共88个神经元个神经元）及网络最终运行结果，其中各圆圈及网络最终运行结果，其中各圆圈的大小表示相应神经元输出值的大小；的大小表示相应神经元输出值的大小；(c)图是根据图是根据(b)图图结果得出的最终路径。结果得出的最终路径。人工智能及其应用51 7.7 遗传算法的应用 遗传算法优化神经网络 基于遗传算法的混合Flow-shop调度方法 人工智能及其应用52 遗传算法优化神经网络 n用遗传算法实现网络优化的步骤：用遗传算法实现网络优化的步骤：(1)(1)初始化过程：确定初始化过程：确定BPBP网络结构、遗传算法进化参数。网络结构、遗传算法进化参数。(2)(2)根据网络结构产生网络权值，作

44、为遗传算法中个体根据网络结构产生网络权值，作为遗传算法中个体的表现型；排列网络权值，组成个体基因型；按照的表现型；排列网络权值，组成个体基因型；按照群体规模生成初始群体。群体规模生成初始群体。(3)(3)由神经网络的误差函数确定个体的适应度函数。由神经网络的误差函数确定个体的适应度函数。(4)(4)根据适应度函数计算群体中个体的适应度值。根据适应度函数计算群体中个体的适应度值。人工智能及其应用53 遗传算法优化神经网络(5)(5)判断是否满足进化结束条件。若满足则结束进化过判断是否满足进化结束条件。若满足则结束进化过程，输出最优解对应的个体表现型，即优化的网络权程，输出最优解对应的个体表现型，

45、即优化的网络权值；否则，执行值；否则，执行(6)(6)，继续进化过程。，继续进化过程。(6)(6)对当前群体进行选择、交叉、变异等遗传操作，产对当前群体进行选择、交叉、变异等遗传操作，产生下一代群体，转生下一代群体，转(4)(4)。人工智能及其应用54 遗传算法优化神经网络n算法的实现：算法的实现：(1)编码编码 (2)群体设定群体设定 (3)适应度函数的确定适应度函数的确定 (4)遗传操作遗传操作人工智能及其应用55 混合Flow-shop调度方法v混合混合Flow-shop调度问题调度问题（Hybrid Flow-shop Scheduling Problem，HFSP）是一般是一般FSP

46、问题的推广，与问题的推广，与FSP不同不同之处在于某些工序上存在并行工作的机器，被称为柔性之处在于某些工序上存在并行工作的机器，被称为柔性流水线。流水线。vHFSP问题可描述为：需要加工多个工件，所有工件的问题可描述为：需要加工多个工件，所有工件的加工路线相同，都需要依次通过各道工序，在所有工序加工路线相同，都需要依次通过各道工序，在所有工序中至少有一个工序存在着多台机器并行。需要解决的问中至少有一个工序存在着多台机器并行。需要解决的问题是确定并行机器的分配以及同一台机器上工件的加工题是确定并行机器的分配以及同一台机器上工件的加工次序，目标是使最大加工时间最小化。次序，目标是使最大加工时间最小

47、化。人工智能及其应用56 混合Flow-shop调度方法nHFSP问题遗传算法求解的编码方法：问题遗传算法求解的编码方法：假设要加工假设要加工N N个工件，每个工件都要依次经过个工件，每个工件都要依次经过S S个个加工工序，每个工序的并行机器为加工工序，每个工序的并行机器为 ,所有工序中至少有一个工序存在并行机器，即至少存所有工序中至少有一个工序存在并行机器，即至少存在一个在一个 大于大于1 1的情况。构造如下的情况。构造如下 的维的维HFSPHFSP编码编码矩阵：矩阵：Si,2,1iMiMNS SNSSNNaaaaaaaaaA212222111211人工智能及其应用57 混合Flow-sho

48、p调度方法 根据上述编码矩阵可确定染色体。染色体由根据上述编码矩阵可确定染色体。染色体由S个小段个小段组成，每个小段包括组成，每个小段包括N个基因。染色体可表示为：个基因。染色体可表示为：n例：例：对于对于3个工件、个工件、3道工序，各工序的并行机器数分别道工序，各工序的并行机器数分别为为3、2、2的混合的混合Flow-shop调度问题，各机器编号如下调度问题，各机器编号如下图所示。图所示。,0,0,0,212222111211SNSSNNkaaaaaaaaaInd机器1机器2机器3机器4机器5机器6机器7工序1工序2工序3人工智能及其应用58 混合Flow-shop调度方法 假设产生编码矩阵

49、：假设产生编码矩阵：对矩阵的各元素分别取整，并根据各工序上的并行机对矩阵的各元素分别取整，并根据各工序上的并行机器编号原则，可得到各工件与机器的对应关系：器编号原则，可得到各工件与机器的对应关系：根据编码矩阵可得染色体如下：根据编码矩阵可得染色体如下：2.14.21.13.21.26.19.14.21.2A121221122)(AIntA2.1,4.2,1.1,0,3.2,1.2,6.1,0,9.1,4.2 ,1.2Ind人工智能及其应用59 混合Flow-shop调度方法n基于遗传算法的基于遗传算法的HFSPHFSP问题求解：问题求解：v产生初始群体产生初始群体v选择适应度函数选择适应度函数

50、v选择算子选择算子 v交叉算子交叉算子 v变异操作变异操作人工智能及其应用60 混合Flow-shop调度方法nHFSP实例：实例：某汽车发动机厂金加工车间要加工某汽车发动机厂金加工车间要加工1212个工件，每个工件，每个工件需经过车、刨、磨个工件需经过车、刨、磨3 3个工序，现有个工序，现有3 3台车床，台车床，2 2台台刨床，刨床，4 4台磨床，每台机床的加工能力不同（加工时间台磨床，每台机床的加工能力不同（加工时间不同），具体加工时间如下页表所示：不同），具体加工时间如下页表所示：人工智能及其应用61工件工序1工序2工序3机器1机器2机器3机器4机器5机器6机器7机器8机器9122345