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

第11章

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

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

人机结合主要分为人机交互（Human-ComputerInteraction,HCI）和脑机接口（Brain-ComputerInterface,BCI）两大技术分支。本书主要关注国内外在“创造脑”方面的研究进展，重点综述在开发仿脑计算机的人机结合技术上的创新研究。11.1.1人机交互（HCI）

人机结合的第一个研究方向为人机仿真研究（HumanEmulationApproach），即赋予计算机类似人类的能力，通过仿真人－人协作的模型，尤其是语言协作模型，来实现计算机的拟人化和智能化。该研究方向以人机交互（HCI）为典型代表。11.1.1人机交互（HCI）1.HCI的提出与发展

随着计算机使用的普及，研究人员开始聚焦于人类和机器间的交互，并试图从生理、心理和理论等方面进行分析，促使了HCI领域的出现，其目的就是为了理解和改善人与计算机之间的交流。

HCI的重点在于交互设计（InteractionDesign,ID）。

HCI包含三个子领域：计算机支持的协同工作（computersupportedcollaborativeworking,CSCW）、计算机支持的协同学习（ComputerSupportedCollaborativeLearning,CSCL）和计算机支持的协同研究（ComputerSupportedCollaborativeResearch,CSCR），而且后者是前者的子集。11.1.1人机交互（HCI）2.HCI系统分类HCI按交互模式可分为单通道交互系统（Uni-modalInteractionSystem）和多通道交互系统（Multi-modalInteractionSystem）两种。

单通道交互系统又分为基于视觉的HCI（Visual-BasedHCI）、基于音频的HCI（Audio-BasedHCI）和基于传感器人机交互的HCI（Sensor-BasedHCI）三个子类。

基于视觉人机交互又包括面部识别、手势识别、躯体运动追踪和视觉追踪；基于音频的人机交互包括音频识别、语音情感识别和噪声探测。

语音识别指计算机识别语音内容，并将音频资料转化为相应的机器语言的能力。音频情感分析和噪声探测则多基于人类的情绪化声音（如笑声、哭声和叹息声等）进行甄别分析。11.1.1人机交互（HCI）3.HCI研究进展Gupta等总结了20世纪HCI的主要进展，包括普适计算（UbiquitousComputing）以及HCI的智能化与自适应化。

普适计算又称环境智能（AmbientIntelligence）感知或者普及计算（PervasiveComputing），这一概念强调和环境融为一体的计算，而计算机本身则从人们的视线里消失。

普适计算的促进者希望嵌入到环境或日常工具中去的计算能够使人更自然地和计算机交互，其显著目标之一是使得计算机设备可以感知周围的环境变化，从而根据环境的变化做出自动的基于用户需要或者设定的行为。11.1.2脑机接口（BCI）

人机结合的第二个研究方向为人机互补研究，即利用计算机独特的能力，通过人体协作的途径来弥补人类某些能力的不足或缺撼。

研究的重点是如何合理分配每个智能体（人、计算机）的任务，使不同任务既具区别性又能巧妙利用各个智能体的长处，然后通过人机协作的途径促进人与计算机间的有效交流。该研究方向以脑机接口为典型代表。11.1.2脑机接口（BCI）1.BCI的提出BCI技术开辟了一种全新的模式，给人类提供了一种可根据不同情境的脑电活动来操控电脑或者通信设备进行活动的可能，为用意念或思维控制外部设备提供了可行手段。

该技术使人在无外周神经系统和肌肉组织参与的条件下，通过计算机等电子设备输出控制信号，进而与外界环境进行交流。

脑成像技术如脑电图（ElectroencEphaloGraph,EEG）、功能磁共振成像（FunctionalMagneticResonanceimaging,FMRI）、脑磁图描记术（MagnetoencEphaloGraphy,MEG）和功能性近红外光谱（FunctionalNearinfra-RedSpectroscopy,FNIRS）等则为观察神经生理活动提供了可能途径。11.1.2脑机接口（BCI）2.BCI分类

依据采集脑电信号的位置可将BCI分为植入式和非植入式。

非植入式BCI因其无创性和便于记录，因而成为当前研究的重点。

按照采集的脑电信号的类型可分为基于诱发EEG的BCI和基于自发EEG的BCI两种。

诱发EEG指人接受外界刺激时所产生的特定脑电活动，目前以P300和稳态视觉诱发电位（Steady-StateVisualEvokedPotential,SSVEP）的研究为主。

自发EEG则是在人体自然状态下就可以记录到的脑细胞的自发性脑电活动，目前研究的重点包括皮层慢电位法（SlowCorticalPotential,SCP）、眼动产生的α波、基于运动想象的μ节律和β节律等。11.1.2脑机接口（BCI）3.BCI系统组成BCI系统的组成，一般包括信号采集、信号处理和控制器三个功能模块。（1）信号采集：

采用盘装或者支架型电极，获取脑电信号，通过导联线传送给前置放大器，经过预处理（去除部分极化电压）、多级放大（10000倍左右）、高低通滤波、隔离后送入AD转换成数字信号，存储于计算机中。（2）信号处理：

包括特征提取和信号分类两部分，是脑机接口系统的核心。利用独立向量分析、傅立叶变换、小波分析和遗传算法等方法，从经过预处理的脑电信号中提取与受试者意图相关的特定特征量（如频率变化和幅度变化等）。（3）控制器：将已分类的信号转换为实际的动作以控制外部电子设备，如显示器上光标的移动、机械手的运动、轮椅的前进与后退和字母的输入等。11.1.3人机结合领域的研究成果2011年IBM研发人员研制出能模拟大脑认知活动的第一代神经突触计算机芯片，未来，IBM将结合混合信号、类比数位和特制容错算法（如异步、平行、分布式和可重组等）来进一步开发神经突触芯片。

NeuroSky研制出能检测脑电波和其它生物信号的生物传感芯片。2013年4月，日本京都国际电气通信基础技术研究所借助核磁共振成像设备来解读梦境，该研究或在未来为窥测他人意图想法提供可能。

2013年6月，美国明尼苏达州的科学家首次实现了通过意念远程遥控直升机的飞行。

2013年8月，美国华盛顿大学科学家首次进行了人类之间非侵入式脑－脑接口试验，一个研究人员能通过互联网发送脑信号，成功控制远在校园另一侧的同伴的手部运动，该研究计划在下一步进行两个大脑之间直接进行更加对等的双向交流。11.2人机结合的集大成智慧

在研制智能系统时，应强调的是人类的“心智”与机器的“智能”相结合。

从体系上讲，在系统的设计过程中，把人作为成员综合到整个系统中去，充分利用并发挥人类和计算机各自的长处形成新的体系是今后深入研究的问题。

在知识系统的“第二个纪元”中“系统”将使智能计算机与智能人之间形成一种同事关系，人和计算机各自完成自己最擅长的任务，系统的智能是这种合作的产物。11.2人机结合的集大成智慧

人与计算机的这种合作可能达到天衣无缝并极其自然，以至于技能、知识及想法是在人脑中还是在计算机的知识结构中都是没有什么关系的，断定智能在程序之中是不准确的，从这样的人机系统中将出现超人的智能和能力。这段话充分表明了人机结合的前景。

另外“人作为智能系统成员”的论点，也包括两个层次，即界面与体系两方面的含义。

人机界面是实现上述论点的必要条件。这里所说的人机界面，其含义不同于那种基于图形学的人机界面，而是包含了模式识别这类涉及感知方面问题的更广义的人机界面。11.2人机结合的集大成智慧

目前这方面的工作是十分活跃的，有代表性的研究有两类：（1）多媒体技术；（2）“临境”或“虚拟现实”技术（VirtualReality）。

根据美国麻省理工学院（M.I.T.）媒体实验室的规划，多媒体包括以下三个部分：（1）学习与常识；（2）感知计算；（3）信息与娱乐。

关于“临境”技术或“虚拟现实”技术，目前还不够成熟，其思想是力求人在求解问题的过程中使其有身临其境之感。

“临境”技术使人的感觉大大拓宽，小至分子原子大至宇宙都可如同亲临其境，将使人的感觉及认知来一次大的飞跃。11.3TSP问题分类1.经典TSPCTSP是在一个带权无向完全图中找一个权值最小的Hamilton回路。在各类TSP中，该类问题的研究成果最多。

近几年来，研究者或者基于数学理论构造近似算法，或者使用各种仿自然的算法框架结合不同的局部搜索方法构造混合算法。

神经网络方法和自组织图方法在该问题上的应用研究也引起了研究者的关注。2.不对称TSP

若在CTSP模型中，两个顶点i和j间的距离d不一定相等，则称为ATSP。ATSP由于两点间距离的不对称性，所以求解更困难，但由于现实生活中多数实际场景都为不对称的TSP，所以对于基于实际交通网络的物流配送来说，其比CTSP更具有实际应用价值。11.3TSP问题分类3.配送收集TSPTSPPD是由CTSP适应物流配送领域的实际需求而产生的。这个问题涉及到两类顾客需要：

一类是配送需求，要求将货物从配送中心送到需求点；

另一类是收集需求，要求将货物从需求点运往配送中心。

当所有的配送和收集需求都由一辆从配送中心出发、限定容量的车辆来完成时，问题转化为怎样安排行驶路线才能构成一条行程最短的Hamilton回路。11.3TSP问题分类4.多人旅行商问题

即多个旅行商遍历多个城市，在满足每个城市被一个旅行商经过一次的前提下，求遍历全部城市的最短路径。

解决

MTSP对解决“车辆调度路径安排”问题具有重要意义。过去的研究大多将MTSP转化成多个TSP，再使用求解TSP的算法进行求解。

HongQu等人结合胜者全取（Winner-take-all）的竞争机制设计了一个柱形竞争的神经网络模型来求解MTSP，并对网络收敛于可行解进行了分析和论证。11.3TSP问题分类5.多目标旅行商问题CRISP的路径上只有一个权值（即距离），而MTSP研究的是路径上有多个权值的TSP，要求找一条通过所有顶点并最终回到起点的回路，使回路上的各个权值都尽可能小。

由于在多目标情况下，严格最优解并不存在，研究MTSP的目的是找到Pareto最优解，这是一个解集，而不是一个单一解。

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

由于在多目标情况下，严格最优解并不存在，研究MTSP的目的是找到Pareto最优解，这是一个解集，而不是一个单一解。

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

由于在多目标情况下，严格最优解并不存在，研究MTSP的目的是找到Pareto最优解，这是一个解集，而不是一个单一解。

现阶段算法为构造一个求解单目标的遗传局部搜索算法，然后基于此求解多目标组合优化问题算法。11.4TSP问题求解

11.4TSP问题求解

11.4TSP问题求解3.分支限界法

采用FIFO分支限界法，分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。

分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。11.4TSP问题求解4.贪心法

贪心法是一种改进了的分级处理方法。它首先根据旅行商问题描述，选取一种度量标准。然后按这种度量标准对n个输入城市排序，并按序一次输入一个城市。

如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中。

这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。获得最优路径的贪心法应一条边一条边地构造这棵树。根据某种量度来选择将要计入的下一条边。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增量的那条边。11.5Hopfield神经网络求解旅行商问题

11.5Hopfield神经网络求解旅行商问题

11.5Hopfield神经网络求解旅行商问题

11.5Hopfield神经网络求解旅行商问题

11.6人机结合求解中国旅行商问题

中国旅行商问题是中国