《人工智能及其應(yīng)用》課件第11章 人機(jī)結(jié)合求解中國(guó)旅行商問(wèn)題

第11章

人機(jī)結(jié)合求解中國(guó)旅行商問(wèn)題人們將讓機(jī)器為自己做出更多決策，這單純是因?yàn)闄C(jī)器做出的決策能帶來(lái)比人類(lèi)決策更好的結(jié)果。這最終會(huì)發(fā)現(xiàn)到某個(gè)特定階段，在這一階段中，保持系統(tǒng)運(yùn)作所需要的決策將變得極為復(fù)雜，導(dǎo)致人類(lèi)再也無(wú)法有效做出決策。——泰德·卡欽斯基,199511.1人機(jī)結(jié)合的研究現(xiàn)狀與進(jìn)展

人機(jī)結(jié)合是人工智能中新興的一個(gè)涉及內(nèi)容廣泛的重要研究方向和分支，其核心就是將人的心智（形象思維、靈感）與計(jì)算機(jī)智能（計(jì)算和邏輯推理）統(tǒng)一在一個(gè)相互作用、相互影響的環(huán)境中，通過(guò)人機(jī)協(xié)作實(shí)現(xiàn)智能互補(bǔ)，以充分發(fā)揮系統(tǒng)的整體優(yōu)勢(shì)和綜合優(yōu)勢(shì)。

人機(jī)結(jié)合主要分為人機(jī)交互（Human-ComputerInteraction,HCI）和腦機(jī)接口（Brain-ComputerInterface,BCI）兩大技術(shù)分支。本書(shū)主要關(guān)注國(guó)內(nèi)外在“創(chuàng)造腦”方面的研究進(jìn)展，重點(diǎn)綜述在開(kāi)發(fā)仿腦計(jì)算機(jī)的人機(jī)結(jié)合技術(shù)上的創(chuàng)新研究。11.1.1人機(jī)交互（HCI）

人機(jī)結(jié)合的第一個(gè)研究方向?yàn)槿藱C(jī)仿真研究（HumanEmulationApproach），即賦予計(jì)算機(jī)類(lèi)似人類(lèi)的能力，通過(guò)仿真人－人協(xié)作的模型，尤其是語(yǔ)言協(xié)作模型，來(lái)實(shí)現(xiàn)計(jì)算機(jī)的擬人化和智能化。該研究方向以人機(jī)交互（HCI）為典型代表。11.1.1人機(jī)交互（HCI）1.HCI的提出與發(fā)展

隨著計(jì)算機(jī)使用的普及，研究人員開(kāi)始聚焦于人類(lèi)和機(jī)器間的交互，并試圖從生理、心理和理論等方面進(jìn)行分析，促使了HCI領(lǐng)域的出現(xiàn)，其目的就是為了理解和改善人與計(jì)算機(jī)之間的交流。

HCI的重點(diǎn)在于交互設(shè)計(jì)（InteractionDesign,ID）。

HCI包含三個(gè)子領(lǐng)域：計(jì)算機(jī)支持的協(xié)同工作（computersupportedcollaborativeworking,CSCW）、計(jì)算機(jī)支持的協(xié)同學(xué)習(xí)（ComputerSupportedCollaborativeLearning,CSCL）和計(jì)算機(jī)支持的協(xié)同研究（ComputerSupportedCollaborativeResearch,CSCR），而且后者是前者的子集。11.1.1人機(jī)交互（HCI）2.HCI系統(tǒng)分類(lèi)HCI按交互模式可分為單通道交互系統(tǒng)（Uni-modalInteractionSystem）和多通道交互系統(tǒng)（Multi-modalInteractionSystem）兩種。

單通道交互系統(tǒng)又分為基于視覺(jué)的HCI（Visual-BasedHCI）、基于音頻的HCI（Audio-BasedHCI）和基于傳感器人機(jī)交互的HCI（Sensor-BasedHCI）三個(gè)子類(lèi)。

基于視覺(jué)人機(jī)交互又包括面部識(shí)別、手勢(shì)識(shí)別、軀體運(yùn)動(dòng)追蹤和視覺(jué)追蹤；基于音頻的人機(jī)交互包括音頻識(shí)別、語(yǔ)音情感識(shí)別和噪聲探測(cè)。

語(yǔ)音識(shí)別指計(jì)算機(jī)識(shí)別語(yǔ)音內(nèi)容，并將音頻資料轉(zhuǎn)化為相應(yīng)的機(jī)器語(yǔ)言的能力。音頻情感分析和噪聲探測(cè)則多基于人類(lèi)的情緒化聲音（如笑聲、哭聲和嘆息聲等）進(jìn)行甄別分析。11.1.1人機(jī)交互（HCI）3.HCI研究進(jìn)展Gupta等總結(jié)了20世紀(jì)HCI的主要進(jìn)展，包括普適計(jì)算（UbiquitousComputing）以及HCI的智能化與自適應(yīng)化。

普適計(jì)算又稱(chēng)環(huán)境智能（AmbientIntelligence）感知或者普及計(jì)算（PervasiveComputing），這一概念強(qiáng)調(diào)和環(huán)境融為一體的計(jì)算，而計(jì)算機(jī)本身則從人們的視線(xiàn)里消失。

普適計(jì)算的促進(jìn)者希望嵌入到環(huán)境或日常工具中去的計(jì)算能夠使人更自然地和計(jì)算機(jī)交互，其顯著目標(biāo)之一是使得計(jì)算機(jī)設(shè)備可以感知周?chē)沫h(huán)境變化，從而根據(jù)環(huán)境的變化做出自動(dòng)的基于用戶(hù)需要或者設(shè)定的行為。11.1.2腦機(jī)接口（BCI）

人機(jī)結(jié)合的第二個(gè)研究方向?yàn)槿藱C(jī)互補(bǔ)研究，即利用計(jì)算機(jī)獨(dú)特的能力，通過(guò)人體協(xié)作的途徑來(lái)彌補(bǔ)人類(lèi)某些能力的不足或缺撼。

研究的重點(diǎn)是如何合理分配每個(gè)智能體（人、計(jì)算機(jī)）的任務(wù)，使不同任務(wù)既具區(qū)別性又能巧妙利用各個(gè)智能體的長(zhǎng)處，然后通過(guò)人機(jī)協(xié)作的途徑促進(jìn)人與計(jì)算機(jī)間的有效交流。該研究方向以腦機(jī)接口為典型代表。11.1.2腦機(jī)接口（BCI）1.BCI的提出BCI技術(shù)開(kāi)辟了一種全新的模式，給人類(lèi)提供了一種可根據(jù)不同情境的腦電活動(dòng)來(lái)操控電腦或者通信設(shè)備進(jìn)行活動(dòng)的可能，為用意念或思維控制外部設(shè)備提供了可行手段。

該技術(shù)使人在無(wú)外周神經(jīng)系統(tǒng)和肌肉組織參與的條件下，通過(guò)計(jì)算機(jī)等電子設(shè)備輸出控制信號(hào)，進(jìn)而與外界環(huán)境進(jìn)行交流。

腦成像技術(shù)如腦電圖（ElectroencEphaloGraph,EEG）、功能磁共振成像（FunctionalMagneticResonanceimaging,FMRI）、腦磁圖描記術(shù)（MagnetoencEphaloGraphy,MEG）和功能性近紅外光譜（FunctionalNearinfra-RedSpectroscopy,FNIRS）等則為觀(guān)察神經(jīng)生理活動(dòng)提供了可能途徑。11.1.2腦機(jī)接口（BCI）2.BCI分類(lèi)

依據(jù)采集腦電信號(hào)的位置可將BCI分為植入式和非植入式。

非植入式BCI因其無(wú)創(chuàng)性和便于記錄，因而成為當(dāng)前研究的重點(diǎn)。

按照采集的腦電信號(hào)的類(lèi)型可分為基于誘發(fā)EEG的BCI和基于自發(fā)EEG的BCI兩種。

誘發(fā)EEG指人接受外界刺激時(shí)所產(chǎn)生的特定腦電活動(dòng)，目前以P300和穩(wěn)態(tài)視覺(jué)誘發(fā)電位（Steady-StateVisualEvokedPotential,SSVEP）的研究為主。

自發(fā)EEG則是在人體自然狀態(tài)下就可以記錄到的腦細(xì)胞的自發(fā)性腦電活動(dòng)，目前研究的重點(diǎn)包括皮層慢電位法（SlowCorticalPotential,SCP）、眼動(dòng)產(chǎn)生的α波、基于運(yùn)動(dòng)想象的μ節(jié)律和β節(jié)律等。11.1.2腦機(jī)接口（BCI）3.BCI系統(tǒng)組成BCI系統(tǒng)的組成，一般包括信號(hào)采集、信號(hào)處理和控制器三個(gè)功能模塊。（1）信號(hào)采集：

采用盤(pán)裝或者支架型電極，獲取腦電信號(hào)，通過(guò)導(dǎo)聯(lián)線(xiàn)傳送給前置放大器，經(jīng)過(guò)預(yù)處理（去除部分極化電壓）、多級(jí)放大（10000倍左右）、高低通濾波、隔離后送入AD轉(zhuǎn)換成數(shù)字信號(hào)，存儲(chǔ)于計(jì)算機(jī)中。（2）信號(hào)處理：

包括特征提取和信號(hào)分類(lèi)兩部分，是腦機(jī)接口系統(tǒng)的核心。利用獨(dú)立向量分析、傅立葉變換、小波分析和遺傳算法等方法，從經(jīng)過(guò)預(yù)處理的腦電信號(hào)中提取與受試者意圖相關(guān)的特定特征量（如頻率變化和幅度變化等）。（3）控制器：將已分類(lèi)的信號(hào)轉(zhuǎn)換為實(shí)際的動(dòng)作以控制外部電子設(shè)備，如顯示器上光標(biāo)的移動(dòng)、機(jī)械手的運(yùn)動(dòng)、輪椅的前進(jìn)與后退和字母的輸入等。11.1.3人機(jī)結(jié)合領(lǐng)域的研究成果2011年IBM研發(fā)人員研制出能模擬大腦認(rèn)知活動(dòng)的第一代神經(jīng)突觸計(jì)算機(jī)芯片，未來(lái)，IBM將結(jié)合混合信號(hào)、類(lèi)比數(shù)位和特制容錯(cuò)算法（如異步、平行、分布式和可重組等）來(lái)進(jìn)一步開(kāi)發(fā)神經(jīng)突觸芯片。

NeuroSky研制出能檢測(cè)腦電波和其它生物信號(hào)的生物傳感芯片。2013年4月，日本京都國(guó)際電氣通信基礎(chǔ)技術(shù)研究所借助核磁共振成像設(shè)備來(lái)解讀夢(mèng)境，該研究或在未來(lái)為窺測(cè)他人意圖想法提供可能。

2013年6月，美國(guó)明尼蘇達(dá)州的科學(xué)家首次實(shí)現(xiàn)了通過(guò)意念遠(yuǎn)程遙控直升機(jī)的飛行。

2013年8月，美國(guó)華盛頓大學(xué)科學(xué)家首次進(jìn)行了人類(lèi)之間非侵入式腦－腦接口試驗(yàn)，一個(gè)研究人員能通過(guò)互聯(lián)網(wǎng)發(fā)送腦信號(hào)，成功控制遠(yuǎn)在校園另一側(cè)的同伴的手部運(yùn)動(dòng)，該研究計(jì)劃在下一步進(jìn)行兩個(gè)大腦之間直接進(jìn)行更加對(duì)等的雙向交流。11.2人機(jī)結(jié)合的集大成智慧

在研制智能系統(tǒng)時(shí)，應(yīng)強(qiáng)調(diào)的是人類(lèi)的“心智”與機(jī)器的“智能”相結(jié)合。

從體系上講，在系統(tǒng)的設(shè)計(jì)過(guò)程中，把人作為成員綜合到整個(gè)系統(tǒng)中去，充分利用并發(fā)揮人類(lèi)和計(jì)算機(jī)各自的長(zhǎng)處形成新的體系是今后深入研究的問(wèn)題。

在知識(shí)系統(tǒng)的“第二個(gè)紀(jì)元”中“系統(tǒng)”將使智能計(jì)算機(jī)與智能人之間形成一種同事關(guān)系，人和計(jì)算機(jī)各自完成自己最擅長(zhǎng)的任務(wù)，系統(tǒng)的智能是這種合作的產(chǎn)物。11.2人機(jī)結(jié)合的集大成智慧

人與計(jì)算機(jī)的這種合作可能達(dá)到天衣無(wú)縫并極其自然，以至于技能、知識(shí)及想法是在人腦中還是在計(jì)算機(jī)的知識(shí)結(jié)構(gòu)中都是沒(méi)有什么關(guān)系的，斷定智能在程序之中是不準(zhǔn)確的，從這樣的人機(jī)系統(tǒng)中將出現(xiàn)超人的智能和能力。這段話(huà)充分表明了人機(jī)結(jié)合的前景。

另外“人作為智能系統(tǒng)成員”的論點(diǎn)，也包括兩個(gè)層次，即界面與體系兩方面的含義。

人機(jī)界面是實(shí)現(xiàn)上述論點(diǎn)的必要條件。這里所說(shuō)的人機(jī)界面，其含義不同于那種基于圖形學(xué)的人機(jī)界面，而是包含了模式識(shí)別這類(lèi)涉及感知方面問(wèn)題的更廣義的人機(jī)界面。11.2人機(jī)結(jié)合的集大成智慧

目前這方面的工作是十分活躍的，有代表性的研究有兩類(lèi)：（1）多媒體技術(shù)；（2）“臨境”或“虛擬現(xiàn)實(shí)”技術(shù)（VirtualReality）。

根據(jù)美國(guó)麻省理工學(xué)院（M.I.T.）媒體實(shí)驗(yàn)室的規(guī)劃，多媒體包括以下三個(gè)部分：（1）學(xué)習(xí)與常識(shí)；（2）感知計(jì)算；（3）信息與娛樂(lè)。

關(guān)于“臨境”技術(shù)或“虛擬現(xiàn)實(shí)”技術(shù)，目前還不夠成熟，其思想是力求人在求解問(wèn)題的過(guò)程中使其有身臨其境之感。

“臨境”技術(shù)使人的感覺(jué)大大拓寬，小至分子原子大至宇宙都可如同親臨其境，將使人的感覺(jué)及認(rèn)知來(lái)一次大的飛躍。11.3TSP問(wèn)題分類(lèi)1.經(jīng)典TSPCTSP是在一個(gè)帶權(quán)無(wú)向完全圖中找一個(gè)權(quán)值最小的Hamilton回路。在各類(lèi)TSP中，該類(lèi)問(wèn)題的研究成果最多。

近幾年來(lái)，研究者或者基于數(shù)學(xué)理論構(gòu)造近似算法，或者使用各種仿自然的算法框架結(jié)合不同的局部搜索方法構(gòu)造混合算法。

神經(jīng)網(wǎng)絡(luò)方法和自組織圖方法在該問(wèn)題上的應(yīng)用研究也引起了研究者的關(guān)注。2.不對(duì)稱(chēng)TSP

若在CTSP模型中，兩個(gè)頂點(diǎn)i和j間的距離d不一定相等，則稱(chēng)為ATSP。ATSP由于兩點(diǎn)間距離的不對(duì)稱(chēng)性，所以求解更困難，但由于現(xiàn)實(shí)生活中多數(shù)實(shí)際場(chǎng)景都為不對(duì)稱(chēng)的TSP，所以對(duì)于基于實(shí)際交通網(wǎng)絡(luò)的物流配送來(lái)說(shuō)，其比CTSP更具有實(shí)際應(yīng)用價(jià)值。11.3TSP問(wèn)題分類(lèi)3.配送收集TSPTSPPD是由CTSP適應(yīng)物流配送領(lǐng)域的實(shí)際需求而產(chǎn)生的。這個(gè)問(wèn)題涉及到兩類(lèi)顧客需要：

一類(lèi)是配送需求，要求將貨物從配送中心送到需求點(diǎn)；

另一類(lèi)是收集需求，要求將貨物從需求點(diǎn)運(yùn)往配送中心。

當(dāng)所有的配送和收集需求都由一輛從配送中心出發(fā)、限定容量的車(chē)輛來(lái)完成時(shí)，問(wèn)題轉(zhuǎn)化為怎樣安排行駛路線(xiàn)才能構(gòu)成一條行程最短的Hamilton回路。11.3TSP問(wèn)題分類(lèi)4.多人旅行商問(wèn)題

即多個(gè)旅行商遍歷多個(gè)城市，在滿(mǎn)足每個(gè)城市被一個(gè)旅行商經(jīng)過(guò)一次的前提下，求遍歷全部城市的最短路徑。

解決

MTSP對(duì)解決“車(chē)輛調(diào)度路徑安排”問(wèn)題具有重要意義。過(guò)去的研究大多將MTSP轉(zhuǎn)化成多個(gè)TSP，再使用求解TSP的算法進(jìn)行求解。

HongQu等人結(jié)合勝者全取（Winner-take-all）的競(jìng)爭(zhēng)機(jī)制設(shè)計(jì)了一個(gè)柱形競(jìng)爭(zhēng)的神經(jīng)網(wǎng)絡(luò)模型來(lái)求解MTSP，并對(duì)網(wǎng)絡(luò)收斂于可行解進(jìn)行了分析和論證。11.3TSP問(wèn)題分類(lèi)5.多目標(biāo)旅行商問(wèn)題CRISP的路徑上只有一個(gè)權(quán)值（即距離），而MTSP研究的是路徑上有多個(gè)權(quán)值的TSP，要求找一條通過(guò)所有頂點(diǎn)并最終回到起點(diǎn)的回路，使回路上的各個(gè)權(quán)值都盡可能小。

由于在多目標(biāo)情況下，嚴(yán)格最優(yōu)解并不存在，研究MTSP的目的是找到Pareto最優(yōu)解，這是一個(gè)解集，而不是一個(gè)單一解。

現(xiàn)階段算法為構(gòu)造一個(gè)求解單目標(biāo)的遺傳局部搜索算法，然后基于此求解多目標(biāo)組合優(yōu)化問(wèn)題算法。11.3TSP問(wèn)題分類(lèi)5.多目標(biāo)旅行商問(wèn)題CRISP的路徑上只有一個(gè)權(quán)值（即距離），而MTSP研究的是路徑上有多個(gè)權(quán)值的TSP，要求找一條通過(guò)所有頂點(diǎn)并最終回到起點(diǎn)的回路，使回路上的各個(gè)權(quán)值都盡可能小。

由于在多目標(biāo)情況下，嚴(yán)格最優(yōu)解并不存在，研究MTSP的目的是找到Pareto最優(yōu)解，這是一個(gè)解集，而不是一個(gè)單一解。

現(xiàn)階段算法為構(gòu)造一個(gè)求解單目標(biāo)的遺傳局部搜索算法，然后基于此求解多目標(biāo)組合優(yōu)化問(wèn)題算法。11.3TSP問(wèn)題分類(lèi)5.多目標(biāo)旅行商問(wèn)題CRISP的路徑上只有一個(gè)權(quán)值（即距離），而MTSP研究的是路徑上有多個(gè)權(quán)值的TSP，要求找一條通過(guò)所有頂點(diǎn)并最終回到起點(diǎn)的回路，使回路上的各個(gè)權(quán)值都盡可能小。

由于在多目標(biāo)情況下，嚴(yán)格最優(yōu)解并不存在，研究MTSP的目的是找到Pareto最優(yōu)解，這是一個(gè)解集，而不是一個(gè)單一解。

現(xiàn)階段算法為構(gòu)造一個(gè)求解單目標(biāo)的遺傳局部搜索算法，然后基于此求解多目標(biāo)組合優(yōu)化問(wèn)題算法。11.4TSP問(wèn)題求解

11.4TSP問(wèn)題求解

11.4TSP問(wèn)題求解3.分支限界法

采用FIFO分支限界法，分支限界法是在生成當(dāng)前E-結(jié)點(diǎn)全部?jī)鹤又笤偕善渌罱Y(jié)點(diǎn)的兒子，且用限界函數(shù)幫助避免生成不包含答案結(jié)點(diǎn)子樹(shù)的狀態(tài)空間的檢索方法。

分支限界法在兩個(gè)方面加速了算法的搜索速度，一是選擇要擴(kuò)展的節(jié)點(diǎn)時(shí)，總是選擇一個(gè)最小成本的結(jié)點(diǎn)，盡可能早的進(jìn)入最有可能成為最優(yōu)解的分支；二是擴(kuò)展節(jié)點(diǎn)的過(guò)程中，舍棄導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的子結(jié)點(diǎn)。11.4TSP問(wèn)題求解4.貪心法

貪心法是一種改進(jìn)了的分級(jí)處理方法。它首先根據(jù)旅行商問(wèn)題描述，選取一種度量標(biāo)準(zhǔn)。然后按這種度量標(biāo)準(zhǔn)對(duì)n個(gè)輸入城市排序，并按序一次輸入一個(gè)城市。

如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把這個(gè)城市加入到這部分解中。

這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理方法成為貪心方法。獲得最優(yōu)路徑的貪心法應(yīng)一條邊一條邊地構(gòu)造這棵樹(shù)。根據(jù)某種量度來(lái)選擇將要計(jì)入的下一條邊。最簡(jiǎn)單的量度標(biāo)準(zhǔn)是選擇使得迄今為止計(jì)入的那些邊的成本的和有最小增量的那條邊。11.5Hopfield神經(jīng)網(wǎng)絡(luò)求解旅行商問(wèn)題

11.5Hopfield神經(jīng)網(wǎng)絡(luò)求解旅行商問(wèn)題

11.5Hopfield神經(jīng)網(wǎng)絡(luò)求解旅行商問(wèn)題

11.5Hopfield神經(jīng)網(wǎng)絡(luò)求解旅行商問(wèn)題

11.6人機(jī)結(jié)合求解中國(guó)旅行商問(wèn)題

中國(guó)旅行商問(wèn)題是中國(guó)