《人工智能及其应用》课件第11章 人机结合求解中国旅行商问题.pptx

1、第第1111章章 人人机结合求解中国旅行商问题机结合求解中国旅行商问题 人们人们将让机器为自己做出更多决策，这单纯是因为机器做出将让机器为自己做出更多决策，这单纯是因为机器做出的决策能带来比人类决策更好的结果。这最终会发现到某个特定的决策能带来比人类决策更好的结果。这最终会发现到某个特定阶段，在这一阶段中，保持系统运作所需要的决策将变得极为复阶段，在这一阶段中，保持系统运作所需要的决策将变得极为复杂，导致人类再也无法有效做出决策。杂，导致人类再也无法有效做出决策。泰德卡钦斯基,199511.111.1人人机结合的研究现状与进展机结合的研究现状与进展 人人机结合是人工智能中新兴的一个涉及内容广泛

2、的重要研究机结合是人工智能中新兴的一个涉及内容广泛的重要研究方向和分支，其核心就是将人的心智（形象思维、灵感）与计算方向和分支，其核心就是将人的心智（形象思维、灵感）与计算机智能（计算和逻辑推理）统一在一个相互作用、相互影响的环机智能（计算和逻辑推理）统一在一个相互作用、相互影响的环境中，通过人机协作实现智能互补，以充分发挥系统的整体优势境中，通过人机协作实现智能互补，以充分发挥系统的整体优势和综合优势和综合优势。人人机结合主要分为人机交互（机结合主要分为人机交互（Human-Computer Interaction,Human-Computer Interaction,HCIHCI）和脑机接

3、口（）和脑机接口（Brain-Computer Interface,BCIBrain-Computer Interface,BCI）两大技术）两大技术分支。本书主要关注国内外在分支。本书主要关注国内外在“创造脑创造脑”方面的研究进展，重点方面的研究进展，重点综述在开发仿脑计算机的人机结合技术上的创新研究。综述在开发仿脑计算机的人机结合技术上的创新研究。11.1.1 11.1.1 人机交互（人机交互（HCIHCI）人人机结合的第一个研究方向为人机仿真研究机结合的第一个研究方向为人机仿真研究（Human Emulation ApproachHuman Emulation Approach），即赋予

4、计算机类），即赋予计算机类似人类的能力，通过仿真人人协作的模型，尤其似人类的能力，通过仿真人人协作的模型，尤其是语言协作模型，来实现计算机的拟人化和智能化。是语言协作模型，来实现计算机的拟人化和智能化。该研究方向以人机交互（该研究方向以人机交互（HCIHCI）为典型代表。）为典型代表。11.1.1 11.1.1 人机交互（人机交互（HCIHCI）1.HCI1.HCI的提出与发展的提出与发展 随着计算机使用的普及，研究人员开始聚焦于人类和机器间的交互，并随着计算机使用的普及，研究人员开始聚焦于人类和机器间的交互，并试图从生理、心理和理论等方面进行分析，促使了试图从生理、心理和理论等方面进行分析，

5、促使了HCIHCI领域的出现，其目的就领域的出现，其目的就是为了理解和改善人与计算机之间的交流是为了理解和改善人与计算机之间的交流。HCI HCI的重点在于交互设计（的重点在于交互设计（Interaction Design,IDInteraction Design,ID）。HCI HCI包含三个子领域：计算机支持的协同工作（包含三个子领域：计算机支持的协同工作（computer supported computer supported collaborative working,CSCWcollaborative working,CSCW）、计算机支持的协同学习（）、计算机支持的协同学习（Co

6、mputer Computer Supported Collaborative Learning,CSCLSupported Collaborative Learning,CSCL）和计算机支持的协同研究）和计算机支持的协同研究（Computer Supported Collaborative Research,CSCRComputer Supported Collaborative Research,CSCR），而且后者是前者），而且后者是前者的子集。的子集。11.1.1 11.1.1 人机交互（人机交互（HCIHCI）2.HCI2.HCI系统分类系统分类 HCI HCI按交互模式可分为单通

7、道交互系统（按交互模式可分为单通道交互系统（UniUni-modal Interaction System-modal Interaction System）和多通道交互系统（和多通道交互系统（Multi-modal Interaction SystemMulti-modal Interaction System）两种）两种。单单通道交互系统又分为基于视觉的通道交互系统又分为基于视觉的HCIHCI（Visual-Based HCIVisual-Based HCI）、基于音频）、基于音频的的HCIHCI（Audio-Based HCIAudio-Based HCI）和基于传感器人机交互的）和基于

8、传感器人机交互的HCIHCI（Sensor-Based HCISensor-Based HCI）三个子类三个子类。基于基于视觉人机交互又包括面部识别、手势识别、躯体运动追踪和视觉追视觉人机交互又包括面部识别、手势识别、躯体运动追踪和视觉追踪；基于音频的人机交互包括音频识别、语音情感识别和噪声探测踪；基于音频的人机交互包括音频识别、语音情感识别和噪声探测。语音识别语音识别指计算机识别语音内容，并将音频资料转化为相应的机器语言指计算机识别语音内容，并将音频资料转化为相应的机器语言的能力。音频情感分析和噪声探测则多基于人类的情绪化声音（如笑声、哭的能力。音频情感分析和噪声探测则多基于人类的情绪化声音

9、（如笑声、哭声和叹息声等）进行甄别分析。声和叹息声等）进行甄别分析。11.1.1 11.1.1 人机交互（人机交互（HCIHCI）3.HCI3.HCI研究进展研究进展 Gupta Gupta等总结了等总结了2020世纪世纪HCIHCI的主要进展，包括普适计算（的主要进展，包括普适计算（Ubiquitous Ubiquitous ComputingComputing）以及）以及HCIHCI的智能化与自适应化的智能化与自适应化。普普适计算又称环境智能（适计算又称环境智能（Ambient IntelligenceAmbient Intelligence）感知或者普及计算）感知或者普及计算（Perva

10、sive ComputingPervasive Computing），这一概念强调和环境融为一体的计算，而计算机），这一概念强调和环境融为一体的计算，而计算机本身则从人们的视线里消失本身则从人们的视线里消失。普普适计算的促进者希望嵌入到环境或日常工具中去的计算能够使人更自适计算的促进者希望嵌入到环境或日常工具中去的计算能够使人更自然地和计算机交互，其显著目标之一是使得计算机设备可以感知周围的环境然地和计算机交互，其显著目标之一是使得计算机设备可以感知周围的环境变化，从而根据环境的变化做出自动的基于用户需要或者设定的行为变化，从而根据环境的变化做出自动的基于用户需要或者设定的行为。11.1.2

11、11.1.2 脑机接口（脑机接口（BCIBCI）人人机结合的第二个研究方向为人机互补研究，即利用计算机独特的能力，机结合的第二个研究方向为人机互补研究，即利用计算机独特的能力，通过人体协作的途径来弥补人类某些能力的不足或缺撼通过人体协作的途径来弥补人类某些能力的不足或缺撼。研究研究的重点是如何合理分配每个智能体（人、计算机）的任务，使不同的重点是如何合理分配每个智能体（人、计算机）的任务，使不同任务既具区别性又能巧妙利用各个智能体的长处，然后通过人机协作的途径任务既具区别性又能巧妙利用各个智能体的长处，然后通过人机协作的途径促进人与计算机间的有效交流。该研究方向以脑机接口为典型代表。促进人与计

12、算机间的有效交流。该研究方向以脑机接口为典型代表。11.1.2 11.1.2 脑机接口（脑机接口（BCIBCI）1.BCI1.BCI的提出的提出 BCI BCI技术开辟了一种全新的模式，给人类提供了一种可根据不同情境的技术开辟了一种全新的模式，给人类提供了一种可根据不同情境的脑电活动来操控电脑或者通信设备进行活动的可能，为用意念或思维控制外脑电活动来操控电脑或者通信设备进行活动的可能，为用意念或思维控制外部设备提供了可行手段。部设备提供了可行手段。该该技术使人在无外周神经系统和肌肉组织参与的条件下，通过计算机等技术使人在无外周神经系统和肌肉组织参与的条件下，通过计算机等电子设备输出控制信号，进

13、而与外界环境进行交流电子设备输出控制信号，进而与外界环境进行交流。脑脑成像技术如脑电图（成像技术如脑电图（ElectroencElectroenc EphaloEphalo Graph,EEG Graph,EEG）、功能磁共振）、功能磁共振成像（成像（Functional Magnetic Resonance imaging,FMRIFunctional Magnetic Resonance imaging,FMRI）、脑磁图描记术）、脑磁图描记术（MagnetoencMagnetoenc EphaloEphalo GraphyGraphy,MEG,MEG）和功能性近红外光谱（）和功能性近红外

14、光谱（Functional Functional NearinfraNearinfra-Red Spectroscopy,FNIRS-Red Spectroscopy,FNIRS）等则为观察神经生理活动提供了可能）等则为观察神经生理活动提供了可能途径。途径。11.1.2 11.1.2 脑机接口（脑机接口（BCIBCI）2.BCI2.BCI分类分类 依据采集脑电信号的位置可将依据采集脑电信号的位置可将BCIBCI分为植入式和非植入式分为植入式和非植入式。非非植入式植入式BCIBCI因其无创性和便于记录，因而成为当前研究的重点因其无创性和便于记录，因而成为当前研究的重点。按照按照采集的脑电信号的类

15、型可分为基于诱发采集的脑电信号的类型可分为基于诱发EEGEEG的的BCIBCI和基于自发和基于自发EEGEEG的的BCIBCI两种两种。诱发诱发EEGEEG指人接受外界刺激时所产生的特定脑电活动，目前以指人接受外界刺激时所产生的特定脑电活动，目前以P300P300和稳态和稳态视觉诱发电位（视觉诱发电位（Steady-State Visual Evoked Potential,SSVEPSteady-State Visual Evoked Potential,SSVEP）的研究为）的研究为主主。自发自发EEGEEG则是在人体自然状态下就可以记录到的脑细胞的自发性脑电活动，则是在人体自然状态下就可

16、以记录到的脑细胞的自发性脑电活动，目前研究的重点包括皮层慢电位法（目前研究的重点包括皮层慢电位法（Slow Cortical Potential,SCPSlow Cortical Potential,SCP）、眼）、眼动产生的动产生的波、基于运动想象的波、基于运动想象的节律和节律和节律等。节律等。11.1.2 11.1.2 脑机接口（脑机接口（BCIBCI）3.BCI3.BCI系统组成系统组成 BCI BCI系统的组成，一般包括信号采集、信号处理和控制器三个功能模块。系统的组成，一般包括信号采集、信号处理和控制器三个功能模块。（1 1）信号采集）信号采集：采用采用盘装或者支架型电极，获取脑电信

17、号，通过导联线传送给前置放大盘装或者支架型电极，获取脑电信号，通过导联线传送给前置放大器，经过预处理（去除部分极化电压）、多级放大（器，经过预处理（去除部分极化电压）、多级放大（1000010000倍左右）、高低通倍左右）、高低通滤波、隔离后送入滤波、隔离后送入ADAD转换成数字信号，存储于计算机中。转换成数字信号，存储于计算机中。（2 2）信号处理）信号处理：包括包括特征提取和信号分类两部分，是脑机接口系统的核心。利用独立向特征提取和信号分类两部分，是脑机接口系统的核心。利用独立向量分析、傅立叶变换、小波分析和遗传算法等方法，从经过预处理的脑电信量分析、傅立叶变换、小波分析和遗传算法等方法，

18、从经过预处理的脑电信号中提取与受试者意图相关的特定特征量（如频率变化和幅度变化等）号中提取与受试者意图相关的特定特征量（如频率变化和幅度变化等）。（3 3）控制器：将已分类的信号转换为实际的动作以控制外部电子设备，如显）控制器：将已分类的信号转换为实际的动作以控制外部电子设备，如显示器上光标的移动、机械手的运动、轮椅的前进与后退和字母的输入等。示器上光标的移动、机械手的运动、轮椅的前进与后退和字母的输入等。11.1.3 11.1.3 人机结合领域的研究成果人机结合领域的研究成果 2011 2011年年IBMIBM研发人员研制出能模拟大脑认知活动的第一代神经突触计算机研发人员研制出能模拟大脑认知

19、活动的第一代神经突触计算机芯片，未来，芯片，未来，IBMIBM将结合混合信号、类比数位和特制容错算法（如异步、平行、将结合混合信号、类比数位和特制容错算法（如异步、平行、分布式和可重组等）来进一步开发神经突触芯片分布式和可重组等）来进一步开发神经突触芯片。Neuro Neuro Sky Sky 研制出能检测脑电波和其它生物信号的生物传感芯片研制出能检测脑电波和其它生物信号的生物传感芯片。2013 2013年年4 4月，日本京都国际电气通信基础技术研究所借助核磁共振成像设月，日本京都国际电气通信基础技术研究所借助核磁共振成像设备来解读梦境，该研究或在未来为窥测他人意图想法提供可能备来解读梦境，该

20、研究或在未来为窥测他人意图想法提供可能。2013 2013年年6 6月，美国明尼苏达州的科学家首次实现了通过意念远程遥控直升月，美国明尼苏达州的科学家首次实现了通过意念远程遥控直升机的飞行机的飞行。2013 2013年年8 8月，美国华盛顿大学科学家首次进行了人类之间非侵入式脑脑月，美国华盛顿大学科学家首次进行了人类之间非侵入式脑脑接口试验，一个研究人员能通过互联网发送脑信号，成功控制远在校园另一接口试验，一个研究人员能通过互联网发送脑信号，成功控制远在校园另一侧的同伴的手部运动，该研究计划在下一步进行两个大脑之间直接进行更加侧的同伴的手部运动，该研究计划在下一步进行两个大脑之间直接进行更加对

21、等的双向交流。对等的双向交流。11.211.2人人机结合的集大成智慧机结合的集大成智慧 在在研制智能系统时，应强调的是人类的研制智能系统时，应强调的是人类的“心智心智”与机器的与机器的“智能智能”相结相结合合。从从体系上讲，在系统的设计过程中，把人作为成员综合到整个系统中去，体系上讲，在系统的设计过程中，把人作为成员综合到整个系统中去，充分利用并发挥人类和计算机各自的长处形成新的体系是今后深入研究的问充分利用并发挥人类和计算机各自的长处形成新的体系是今后深入研究的问题题。在在知识系统的知识系统的“第二个纪元第二个纪元”中中“系统系统”将使智能计算机与智能人之间将使智能计算机与智能人之间形成一种

22、同事关系，人和计算机各自完成自己最擅长的任务，系统的智能是形成一种同事关系，人和计算机各自完成自己最擅长的任务，系统的智能是这种合作的产物。这种合作的产物。11.211.2人人机结合的集大成智慧机结合的集大成智慧 人人与计算机的这种合作可能达到天衣无缝并极其自然，以至于技能、知与计算机的这种合作可能达到天衣无缝并极其自然，以至于技能、知识及想法是在人脑中还是在计算机的知识结构中都是没有什么关系的，断定识及想法是在人脑中还是在计算机的知识结构中都是没有什么关系的，断定智能在程序之中是不准确的，从这样的人机系统中将出现超人的智能和能力。智能在程序之中是不准确的，从这样的人机系统中将出现超人的智能和

23、能力。这段话充分表明了人机结合的前景这段话充分表明了人机结合的前景。另外另外“人作为智能系统成员人作为智能系统成员”的论点，也包括两个层次，即界面与体系的论点，也包括两个层次，即界面与体系两方面的含义两方面的含义。人机界面人机界面是实现上述论点的必要条件。这里所说的人机界面，其含义不是实现上述论点的必要条件。这里所说的人机界面，其含义不同于那种基于图形学的人机界面，而是包含了模式识别这类涉及感知方面问同于那种基于图形学的人机界面，而是包含了模式识别这类涉及感知方面问题的更广义的人机界面。题的更广义的人机界面。11.211.2人人机结合的集大成智慧机结合的集大成智慧 目前这方面的工作是十分活跃的

24、，有代表性的研究有两类：目前这方面的工作是十分活跃的，有代表性的研究有两类：（1 1）多媒体技术；）多媒体技术；（2 2）“临境临境”或或“虚拟现实虚拟现实”技术（技术（Virtual RealityVirtual Reality）。）。根据美国麻省理工学院（根据美国麻省理工学院（M.I.T.M.I.T.）媒体实验室的规划，多媒体包括以下）媒体实验室的规划，多媒体包括以下三个部分：三个部分：（1 1）学习与常识；）学习与常识；（2 2）感知计算；）感知计算；（3 3）信息与娱乐。）信息与娱乐。关于关于“临境临境”技术或技术或“虚拟现实虚拟现实”技术，目前还不够成熟，其思想是力技术，目前还不够成

25、熟，其思想是力求人在求解问题的过程中使其有身临其境之感求人在求解问题的过程中使其有身临其境之感。“临境临境”技术使人的感觉大大拓宽，小至分子原子大至宇宙都可如同亲临技术使人的感觉大大拓宽，小至分子原子大至宇宙都可如同亲临其境，将使人的感觉及认知来一次大的飞跃。其境，将使人的感觉及认知来一次大的飞跃。11.3 11.3 TSPTSP问题分类问题分类1.1.经典经典TSPTSP CTSP CTSP是在一个带权无向完全图中找一个权值最小的是在一个带权无向完全图中找一个权值最小的HamiltonHamilton回路。在各回路。在各类类TSPTSP中，该类问题的研究成果最多中，该类问题的研究成果最多。近

26、几年来近几年来，研究者或者基于数学理论构造近似算法，或者使用各种仿自，研究者或者基于数学理论构造近似算法，或者使用各种仿自然的算法框架结合不同的局部搜索方法构造混合算法然的算法框架结合不同的局部搜索方法构造混合算法。神经网络神经网络方法和自组织图方法在该问题上的应用研究也引起了研究者的方法和自组织图方法在该问题上的应用研究也引起了研究者的关注。关注。2.2.不对称不对称TSPTSP 若在若在CTSPCTSP模型中，两个顶点模型中，两个顶点i i和和j j间的距离间的距离d d不一定相等，则称为不一定相等，则称为ATSPATSP。ATSPATSP由于两点间距离的不对称性，所以求解更困难，但由于现

27、实生活中多数由于两点间距离的不对称性，所以求解更困难，但由于现实生活中多数实际场景都为不对称的实际场景都为不对称的TSPTSP，所以对于基于实际交通网络的物流配送来说，其，所以对于基于实际交通网络的物流配送来说，其比比CTSPCTSP更具有实际应用价值。更具有实际应用价值。11.3 11.3 TSPTSP问题分类问题分类3.3.配送收集配送收集TSPTSP TSPPD TSPPD是由是由CTSPCTSP适应物流配送领域的实际需求而产生的。这个问题涉及到适应物流配送领域的实际需求而产生的。这个问题涉及到两类顾客需要两类顾客需要：一类一类是配送需求，要求将货物从配送中心送到需求点是配送需求，要求将

28、货物从配送中心送到需求点；另另一类是收集需求，要求将货物从需求点运往配送中心一类是收集需求，要求将货物从需求点运往配送中心。当当所有的配送和收集需求都由一辆从配送中心出发、限定容量的车辆来所有的配送和收集需求都由一辆从配送中心出发、限定容量的车辆来完成时，问题转化为怎样安排行驶路线才能构成一条行程最短的完成时，问题转化为怎样安排行驶路线才能构成一条行程最短的HamiltonHamilton回回路路。11.3 11.3 TSPTSP问题分类问题分类4 4.多人旅行商问题多人旅行商问题 即多个旅行商遍历多个城市，在满足每个城市被一个旅行商经过一次的即多个旅行商遍历多个城市，在满足每个城市被一个旅行

29、商经过一次的前提下，求遍历全部城市的最短路径前提下，求遍历全部城市的最短路径。解决解决 MTSPMTSP对解决对解决“车辆调度路径安排车辆调度路径安排”问题具有重要意义。过去的研究问题具有重要意义。过去的研究大多将大多将 MTSP MTSP转化成多个转化成多个TSPTSP，再使用求解，再使用求解 TSP TSP的算法进行求解的算法进行求解。Hong Hong QuQu等人结合胜者全取（等人结合胜者全取（Winner-take-allWinner-take-all）的竞争机制设计了一个）的竞争机制设计了一个柱形竞争的神经网络模型来求解柱形竞争的神经网络模型来求解MTSPMTSP，并对网络收敛于可

30、行解进行了分析和，并对网络收敛于可行解进行了分析和论证。论证。11.3 11.3 TSPTSP问题分类问题分类5.5.多目标旅行商问题多目标旅行商问题 CRISP CRISP的路径上只有一个权值（即距离），而的路径上只有一个权值（即距离），而 MTSP MTSP研究的是路径上有多研究的是路径上有多个权值的个权值的TSPTSP，要求找一条通过所有顶点并最终回到起点的回路，使回路上的，要求找一条通过所有顶点并最终回到起点的回路，使回路上的各个权值都尽可能小各个权值都尽可能小。由于由于在多目标情况下，严格最优解并不存在，研究在多目标情况下，严格最优解并不存在，研究MTSPMTSP的目的是找到的目的是

31、找到ParetoPareto最优解，这是一个解集，而不是一个单一解最优解，这是一个解集，而不是一个单一解。现阶段现阶段算法为构造一个求解单目标的遗传局部搜索算法，然后基于此求算法为构造一个求解单目标的遗传局部搜索算法，然后基于此求解多目标组合优化问题算法。解多目标组合优化问题算法。11.3 11.3 TSPTSP问题分类问题分类5.5.多目标旅行商问题多目标旅行商问题 CRISP CRISP的路径上只有一个权值（即距离），而的路径上只有一个权值（即距离），而 MTSP MTSP研究的是路径上有多研究的是路径上有多个权值的个权值的TSPTSP，要求找一条通过所有顶点并最终回到起点的回路，使回路上

32、的，要求找一条通过所有顶点并最终回到起点的回路，使回路上的各个权值都尽可能小各个权值都尽可能小。由于由于在多目标情况下，严格最优解并不存在，研究在多目标情况下，严格最优解并不存在，研究MTSPMTSP的目的是找到的目的是找到ParetoPareto最优解，这是一个解集，而不是一个单一解最优解，这是一个解集，而不是一个单一解。现阶段现阶段算法为构造一个求解单目标的遗传局部搜索算法，然后基于此求算法为构造一个求解单目标的遗传局部搜索算法，然后基于此求解多目标组合优化问题算法。解多目标组合优化问题算法。11.3 11.3 TSPTSP问题分类问题分类5.5.多目标旅行商问题多目标旅行商问题 CRIS

33、P CRISP的路径上只有一个权值（即距离），而的路径上只有一个权值（即距离），而 MTSP MTSP研究的是路径上有多研究的是路径上有多个权值的个权值的TSPTSP，要求找一条通过所有顶点并最终回到起点的回路，使回路上的，要求找一条通过所有顶点并最终回到起点的回路，使回路上的各个权值都尽可能小各个权值都尽可能小。由于由于在多目标情况下，严格最优解并不存在，研究在多目标情况下，严格最优解并不存在，研究MTSPMTSP的目的是找到的目的是找到ParetoPareto最优解，这是一个解集，而不是一个单一解最优解，这是一个解集，而不是一个单一解。现阶段现阶段算法为构造一个求解单目标的遗传局部搜索算法

34、，然后基于此求算法为构造一个求解单目标的遗传局部搜索算法，然后基于此求解多目标组合优化问题算法。解多目标组合优化问题算法。11.4 11.4 TSPTSP问题求解问题求解11.4 11.4 TSPTSP问题求解问题求解11.4 11.4 TSPTSP问题求解问题求解3.3.分支限界法分支限界法 采用采用FIFOFIFO分支限界法，分支限界法是在生成当前分支限界法，分支限界法是在生成当前E-E-结点全部儿子之后再结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法状态空间的检索方法

35、。分支分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的时，总是选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。11.4 11.4 TSPTSP问题求解问题求解4.4.贪心法贪心法 贪心法是一种改进了的分级处理方法。它首先根据旅行商问题描述，选取一种贪心法是一种改进了的分级处理方法。它首先根据旅行商问题描述，选取一种

36、度量标准。然后按这种度量标准对度量标准。然后按这种度量标准对n n个输入城市排序，并按序一次输入一个城市个输入城市排序，并按序一次输入一个城市。如果如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中一个可行解，则不把这个城市加入到这部分解中。这种这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。获得最能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。获得最优路径的贪心法应一条边一条边地构造这棵树。根据某种量度来选择将要计入的下优路径的贪心法应一条边一条

37、边地构造这棵树。根据某种量度来选择将要计入的下一条边。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增一条边。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增量的那条边。量的那条边。11.5 11.5 HopfieldHopfield神经网络求解旅行商问题神经网络求解旅行商问题11.5 11.5 HopfieldHopfield神经网络求解旅行商问题神经网络求解旅行商问题11.5 11.5 HopfieldHopfield神经网络求解旅行商问题神经网络求解旅行商问题11.5 11.5 HopfieldHopfield神经网络求解旅行商问题神经网络求解旅行商问题1

38、1.611.6人机结合求解中国旅行商问题人机结合求解中国旅行商问题 中国中国旅行商问题是中国旅行商问题是中国3131个直辖市、省会和自治区首府的旅行商问题，个直辖市、省会和自治区首府的旅行商问题，到目前为止，用一种新的几何算法可以得到中国旅行商问题的最优解是到目前为止，用一种新的几何算法可以得到中国旅行商问题的最优解是1549215492公里公里。对于对于中国旅行商问题，中国旅行商问题，3131个城市之间的相对位置是一条重要信息，以往个城市之间的相对位置是一条重要信息，以往的各种求解方法几乎没有利用这条信息，下面以人机结合寻优方法求解中国的各种求解方法几乎没有利用这条信息，下面以人机结合寻优方

39、法求解中国旅行商问题，人机结合寻优方法使用旅行商问题，人机结合寻优方法使用“临境临境”或或“虚拟现实虚拟现实”技术（技术（Virtual Virtual RealityReality）模拟人面对中国地图求解中国旅行商问题时的思维过程，尽量充分）模拟人面对中国地图求解中国旅行商问题时的思维过程，尽量充分利用各个城市之间相对位置这条信息，从而使计算工作量大大减少。利用各个城市之间相对位置这条信息，从而使计算工作量大大减少。11.611.6人机结合求解中国旅行商问题人机结合求解中国旅行商问题 如何在计算机中实现如何在计算机中实现“最先最先”，“其次其次”，“再次再次”，“再其次再其次”呢？呢？模糊数

40、学给我们提供了解决方法。在旅行商问题中，每到达一个城市后，其模糊数学给我们提供了解决方法。在旅行商问题中，每到达一个城市后，其余所有未被访问过的城市构成一个集合，而下一步应该访问的城市构成一个余所有未被访问过的城市构成一个集合，而下一步应该访问的城市构成一个模糊子集合模糊子集合。人人可以把可以把“最先最先”考虑城市的隶属度定义为考虑城市的隶属度定义为0.90.9，“其次其次”考虑定义为考虑定义为0.70.7，“再次再次”考虑定义为考虑定义为0.50.5，“再其次再其次”考虑定义为考虑定义为0.30.3，其他城市定义为，其他城市定义为0.10.1。11.611.6人机结合求解中国旅行商问题人机结

41、合求解中国旅行商问题11.611.6人机结合求解中国旅行商问题人机结合求解中国旅行商问题11.611.6人机结合求解中国旅行商问题人机结合求解中国旅行商问题11.611.6人机结合求解中国旅行商问题人机结合求解中国旅行商问题11.7 11.7 小结小结11.7 11.7 小结小结 人人机结合是人工智能中新兴的一个涉及内容广泛的重要研究方向和分支，机结合是人工智能中新兴的一个涉及内容广泛的重要研究方向和分支，其核心就是将人的心智（形象思维、灵感）与计算机智能（计算和逻辑推理）其核心就是将人的心智（形象思维、灵感）与计算机智能（计算和逻辑推理）统一在一个相互作用、相互影响的环境中，通过人机协作实现智能互补，以统一在一个相互作用、相互影响的环境中，通过人机协作实现智能互补，以充分发挥系统的整体优势和综合优势。人机结合主要分为人机交互和脑机接充分发挥系统的整体优势和综合优势。人机结合主要分为人机交互和脑机接口两大技术分支。口两大技术分支。