吳 雷 劉 箴 錢平安 劉婷婷， 王 瑾 柴艷杰

（1.寧波大學(xué)信息科學(xué)與工程學(xué)院 寧波 315211）（2.寧波市第九醫(yī)院 寧波 315211）（3.寧波大學(xué)科學(xué)技術(shù)學(xué)院 寧波 315211）

1 引言

智能體的路徑規(guī)劃問題是指在若干障礙物的環(huán)境下［1］，為智能體規(guī)劃出一條從起始位置到目標(biāo)位置的最優(yōu)或者次優(yōu)的安全無碰撞路徑。路徑規(guī)劃問題通常存在環(huán)境信息量大、障礙物多等約束，其已被證實為NP-Hard問題［2］。一些學(xué)者從智能體對環(huán)境感知的角度，將智能體路徑規(guī)劃方法分為3種類型［3］：基于環(huán)境模型的規(guī)劃方法、基于事例學(xué)習(xí)的規(guī)劃方法和基于智能體行為的路徑規(guī)劃方法；根據(jù)智能體對環(huán)境信息的掌握程度，又可分為全局路徑規(guī)劃和局部路徑規(guī)劃；根據(jù)規(guī)劃環(huán)境中障礙物位置信息是靜態(tài)或者動態(tài)的角度，還可分為靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃［4］。

本文通過對智能體進行仿真建模，為智能體提供感知模型和記憶模型，并且將感知模型和記憶模型的數(shù)值作為神經(jīng)網(wǎng)絡(luò)的輸入來指導(dǎo)智能體在仿真環(huán)境中的行為。并通過適應(yīng)性函數(shù)來對智能體在仿真環(huán)境中執(zhí)行路徑規(guī)劃任務(wù)的表現(xiàn)進行評價。然后通過NEAT算法對指導(dǎo)智能體行為的神經(jīng)網(wǎng)絡(luò)進行拓?fù)浣Y(jié)構(gòu)和連接權(quán)重的進化，并生成和優(yōu)化出一個最佳神經(jīng)網(wǎng)絡(luò)，指導(dǎo)智能體在設(shè)定的進化周期內(nèi)尋找到一條最優(yōu)的路徑。

2 相關(guān)工作

人工智能路徑規(guī)劃技術(shù)是通過現(xiàn)代人工智能技術(shù)進行智能體的路徑規(guī)劃研究［4］，常見的人工智能路徑規(guī)劃技術(shù)有遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、進化算法、模糊邏輯與信息融合［5～8］。

由于模糊邏輯與信息融合技術(shù)在不確定信息處理方面表現(xiàn)良好，且智能體傳感器采集的環(huán)境信息存在不確定性，使得模糊邏輯與信息融合技術(shù)在智能體路徑規(guī)劃中有較好的應(yīng)用［4］。如郝冬等［12］針對未知環(huán)境提出了一種基于模糊邏輯行為融合的路徑規(guī)劃方法，李擎等［13］提出基于動態(tài)環(huán)境下模糊邏輯路徑規(guī)劃方法，Zun等［14］提出基于信息融合技術(shù)的智能體路徑規(guī)劃與避碰方法。然而由于模糊邏輯對信息的精度要求較高，且模糊邏輯無法精確地定義控制目標(biāo)，這些因素的存在限制了模糊邏輯在路徑規(guī)劃上的廣泛應(yīng)用。

遺傳算法及其派生算法在智能體路徑規(guī)劃研究領(lǐng)域已得到了廣泛的應(yīng)用［9～11］。Pang等［18］利用遺傳算法實現(xiàn)了智能體的自主避障。然而遺傳算法本身結(jié)構(gòu)簡單且運行效率不高，只能解決路徑規(guī)劃的部分問題。遺傳算法通過與其他算法相結(jié)合，充分發(fā)揮自身迭代進化的優(yōu)勢，能夠得到較好的路徑規(guī)劃效果。近年來一些研究人員將進化算法用于基于行為的智能體仿真［15～18］，并且已經(jīng)做了相當(dāng)多的概念證明和實例研究。進化算法（EAs）一直是用于設(shè)計和訓(xùn)練神經(jīng)網(wǎng)絡(luò)的有力工具。José等［15］利用進化算法和離散時間遞歸神經(jīng)網(wǎng)絡(luò)進化出智能體的避障行為，然而該方法存在規(guī)劃知識的學(xué)習(xí)過程，存在學(xué)習(xí)樣本難以獲取和學(xué)習(xí)滯后等問題，從而影響神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃的實時性。

德克薩斯州大學(xué)的Stanley K.O.和Miikkulain?en R.創(chuàng)造性的提出了一種稱之為NEAT（Neu?ro-Evolution Through Augmenting Topology）的新型進化算法［19］，這是一種逐步增加網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)并不斷演化網(wǎng)絡(luò)權(quán)重的方法。NEAT算法已經(jīng)被應(yīng)用到了一些有趣的領(lǐng)域，并產(chǎn)生了許多令人印象深刻的效果。Stanley等將NEAT方法應(yīng)用于一個FPS視頻游戲中，使得虛擬智能體自主進化出射擊目標(biāo)、躲避敵人、尋找掩體等復(fù)雜行為［20］。趙金等利用NEAT方法進化智能體的行為，實現(xiàn)了多智能體對目標(biāo)的圍捕效果，從而證明了算法對于復(fù)雜環(huán)境適應(yīng)的有效性［21］。

NEAT算法是遺傳算法和神經(jīng)網(wǎng)絡(luò)相結(jié)合的無監(jiān)督強化學(xué)習(xí)方法。該算法對于優(yōu)化復(fù)雜環(huán)境中的控制類問題具有良好效果。本文將NEAT算法引入到路徑規(guī)劃這一領(lǐng)域，通過設(shè)計合理有效的智能體模型和適應(yīng)性函數(shù)，來研究NEAT算法對于解決復(fù)雜環(huán)境下智能體路徑規(guī)劃問題的有效性。

3 智能體建模

3.1 智能體動力模型

智能體的動力模型包括以下屬性：

1）智能體為兩輪差速驅(qū)動模型。即，智能體的移動是通過左右兩個仿真輪子的速度來控制，vL，vR分別代表智能體左右輪子的速度大小。設(shè)定智能體的移動速度大小為：vspeed=vL+vR。

2）只有速度大小不能驅(qū)動智能體正確地移動。為了明確智能體在下一個時刻的運動方向，還需要給智能體設(shè)置一個視覺向量。若當(dāng)前時刻智能體的運動角度為 θ ，設(shè)定=(sin(θ)，cos(θ))。

3）通過以上兩步，可以獲得智能體在當(dāng)前時刻所具備的速度v?=vspeed，智能體在運動的過程中，需要保留智能體當(dāng)前的位置坐標(biāo)。設(shè)定下一時刻智能體的位置坐標(biāo)為：。

3.2 智能體感知模型

在路徑規(guī)劃中，智能體應(yīng)該首先具備探測環(huán)境的能力。智能體對環(huán)境中的障礙物，具備認(rèn)知和反饋的能力。這就需要為智能體設(shè)置相應(yīng)的傳感器或者更形象的稱之為觸覺器。智能體在運行的過程中，通過傳感器與障礙物之間的交互來熟悉環(huán)境。在本文中，我們?yōu)橹悄荏w設(shè)置五個傳感器S={ }s1，s2，s3，s4，s5，如圖1所示。

圖1 智能體感知模型

傳感器的作用是在智能體探測環(huán)境的過程中，如果傳感器探測到障礙物，則返回當(dāng)前傳感器與障礙物的碰撞點到智能體中心的距離di，式（1）描述了距離d的求解過程，設(shè)傳感器的距離向量為D={d1，d2，d3，d4，d5} 。如果傳感器返回的碰撞距離di小于了規(guī)定的閾值，設(shè)置智能體的檢測碰撞狀態(tài)位C為真，否則為假。

判斷是否發(fā)生碰撞的條件公式為式（2）。其中di是檢驗仿真機器人是否和障礙物發(fā)生碰撞并停止運行的閾值。碰撞檢測位C也是作為神經(jīng)網(wǎng)絡(luò)的輸入，參與到網(wǎng)絡(luò)的學(xué)習(xí)中。

3.3 智能體記憶模型

在二維地圖中隨機分布著若干任意形狀的障礙物 oi(i=1，2，3，…，n)，智能體的感知模型在和障礙物oi的交互過程中，會逐漸產(chǎn)生對障礙物的認(rèn)知，從而避開障礙物。但是，仍然會存在一個問題，那就是智能體雖然成功的避開了障礙物，卻可能在沒有障礙物的可通行區(qū)域，重復(fù)訪問已經(jīng)走過的路段。因此，除了探測環(huán)境的能力外，我們還賦予智能體另外一種能力：記錄環(huán)境的能力。通過對訪問環(huán)境的記錄，避免智能體在探索環(huán)境的過程中，出現(xiàn)對已經(jīng)探索過的環(huán)境的重復(fù)探索。為了實現(xiàn)上述功能，我們將二維平面地圖進行柵格化處理。設(shè)定地圖的長度為l，寬度為w，單元格的長度為u?？梢酝茖?dǎo)出二維地圖橫向和縱向的柵格數(shù)分別為：Nc=l/u，Nl=w/u。經(jīng)過柵格化處理的二維地圖，如圖2所示，定義柵格坐標(biāo)系為。在智能體對未知環(huán)境的探索過程中，每一個時刻智能體所訪問的單元格都會被系統(tǒng)標(biāo)記。在實驗平臺中，對于重復(fù)訪問的區(qū)域，我們做加深渲染處理。以此來區(qū)分在此迭代過程中，智能體對區(qū)域的探測效果。而傳感器負(fù)責(zé)記錄某一時刻傳感器末端所占據(jù)的單元格被訪問的次數(shù)ti。設(shè)定某一時刻傳感器的訪問集為T={t1， t2， t3， t4， t5} 。

傳 感 器 所 返 回 的 距 離 向 量 D={d1，d2，d3，d4，d5} 、傳感器的訪問集 T={t1，t2，t3，t4，t5} ，以及智能體的狀態(tài)位C，共同構(gòu)成了支配智能體行為的神經(jīng)網(wǎng)絡(luò)的輸入集I={D，T，C}。

圖2 智能體記憶模型

4 基于NEAT的智能體路徑規(guī)劃

4.1 行為學(xué)習(xí)

設(shè)定有N個智能體同時在N個相同的二維環(huán)境下運動。智能體具有相同的起點S和相同的終點E。智能體i在一個仿真周期中的路徑為Pi，如果路徑Pi可以到達(dá)終點，則設(shè)定Pi為Pi*。則基于NEAT的智能體路徑規(guī)劃模型可表述為：尋找N個智能體的可行路徑集合}(m≤n)，并最終獲得一條路徑，使得 f()=min{P*}。

智能體的運動規(guī)則取決于為其分配的神經(jīng)網(wǎng)絡(luò)。每一時刻，智能體都會根據(jù)其感知器和記憶器，來獲取當(dāng)前時刻神經(jīng)網(wǎng)絡(luò)的輸入集I，并通過神經(jīng)網(wǎng)絡(luò)獲得輸出vL，vR。智能體根據(jù)輸出決策出下一時刻的運動位置。在一個運行周期中，智能體不斷地進行上述步驟，直至結(jié)束當(dāng)前周期。當(dāng)前周期結(jié)束時，評估每個智能體的表現(xiàn)。我們的目標(biāo)是優(yōu)化出一條路徑，因此必須構(gòu)建出可以指導(dǎo)NEAT算法按照此目標(biāo)方向正確進化的適應(yīng)性函數(shù)F。上文中，為智能體設(shè)置記憶器的目的，是防止智能體在不和障礙物發(fā)生碰撞的過程中，避免智能體發(fā)生“徘徊”的現(xiàn)象，從而盡可能多地訪問智能體沒有訪問過的區(qū)域。但是又會帶來一個問題，那就是智能體在通向目的地的過程中，會行駛太多的路程。我們希望隨著迭代次數(shù)的增加，可以消除這一現(xiàn)象，讓智能體做到既不重復(fù)訪問已經(jīng)行駛過的區(qū)域，又可以花費盡可能少的路程到達(dá)指定位置。設(shè)定智能體運動的總路程為L(P)=N·u，其中N為一次迭代周期中，智能體在沒有到達(dá)終點時，所訪問的單元格的個數(shù)，則設(shè)定適應(yīng)性函數(shù)為

其中，dx和dy分別表示在一個周期結(jié)束時，智能體的最終位置相對起點S的橫縱坐標(biāo)差值，α為設(shè)定的權(quán)重。

4.2 NEAT算法的基本思想

4.2.1 基因編碼

為了進化神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)，需要一個動態(tài)并且可擴展的基因編碼方法。在NEAT算法中，為了完整的描述一個神經(jīng)網(wǎng)絡(luò)的全部信息，每個基因組都要包含一個連接信息和節(jié)點基因信息。每個連接信息都指明一個輸入節(jié)點和輸出節(jié)點，以及連接權(quán)重。節(jié)點基因描述了節(jié)點在神經(jīng)網(wǎng)絡(luò)內(nèi)的功能，指示該節(jié)點在神經(jīng)網(wǎng)絡(luò)中的屬性。每個節(jié)點基因都包含一個唯一的ID?；蚓幋a示意圖如圖3所示。

圖3 基因編碼示意圖

4.2.2 突變操作

在NEAT算法中，突變可以同時改變連接權(quán)重和網(wǎng)絡(luò)結(jié)構(gòu)。連接權(quán)重的突變和一般的神經(jīng)進化系統(tǒng)相同，每個權(quán)重以固定概率加上一個符合正態(tài)分布的浮點數(shù)即可。

結(jié)構(gòu)突變則分為兩種，如圖4所示，DIS表示基因不表達(dá)。在增加連接突變中，一個新的連接被加入，將之前未被連接的兩個節(jié)點相連。在增加節(jié)點的突變中，一個現(xiàn)存的連接被斷開，一個新的節(jié)點被添加在連接斷開的位置。舊的連接被斷開，并且兩個新的連接被添加到基因組中。在新形成的兩個連接中，新節(jié)點和前一個節(jié)點之間的連接權(quán)重被設(shè)置為1，而新節(jié)點和后一個節(jié)點的連接權(quán)重則繼承了舊的連接值。

圖4 突變操作示意圖

4.2.3 雜交操作

如圖5所示，在雜交操作中，Parent1和Parent2稱為兩個雙親網(wǎng)絡(luò)，為雙親中的每個基因指定一個創(chuàng)新號，DISAB表示基因不表達(dá)。Parent1和Par?ent2中都擁有從創(chuàng)新號1～5的結(jié)構(gòu)，而創(chuàng)新號為6、7、8、9、10的結(jié)構(gòu)分別只存在于單一雙親中，在基因組內(nèi)部的單獨基因稱為脫落基因（disjoint gene），而在基因組末端的無匹配基因稱為過量基因（ex?cess gene）。創(chuàng)新號允許NEAT對不同的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進行雜交，當(dāng)網(wǎng)絡(luò)的大小和結(jié)構(gòu)隨著進化變得越來越復(fù)雜時，網(wǎng)絡(luò)之間仍然保持兼容。

圖5 雜交操作示意圖

4.3 人工神經(jīng)網(wǎng)絡(luò)的設(shè)定

本文為每個智能體分配一個神經(jīng)網(wǎng)絡(luò)。我們在實驗中，采用可以同時進化人工神經(jīng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和連接權(quán)重的NEAT算法來訓(xùn)練神經(jīng)網(wǎng)絡(luò)。NEAT算法的優(yōu)勢在于，神經(jīng)網(wǎng)絡(luò)的連接權(quán)重和拓?fù)溲莼稍撍惴ㄘ?fù)責(zé)，因此我們并不需要人工建立神經(jīng)網(wǎng)絡(luò)，只需要根據(jù)實驗需求設(shè)置輸入和輸出神經(jīng)元的個數(shù)，并根據(jù)交互環(huán)境獲得輸入數(shù)據(jù)I，以及引導(dǎo)網(wǎng)絡(luò)進化的適應(yīng)性函數(shù)即可，當(dāng)一個仿真運行周期結(jié)束后，每個智能體都會依據(jù)其表現(xiàn)得到相應(yīng)的適應(yīng)性分?jǐn)?shù)，這些適應(yīng)性分?jǐn)?shù)匯總后，將傳遞給NEAT算法用于生成下一代的智能體的“大腦”（人工神經(jīng)網(wǎng)絡(luò)）。

相比較于傳統(tǒng)的拓?fù)錂?quán)重演化神經(jīng)網(wǎng)絡(luò)，NEAT算法在以下三個方面做了細(xì)致的優(yōu)化：

1）使用歷史標(biāo)記來判斷基因之間的同源性。

2）使用物種（Speciation）形成來保護創(chuàng)新。

3）當(dāng)網(wǎng)絡(luò)初始化時，采用無隱含節(jié)點的最小網(wǎng)絡(luò)，并且只在必要情況下增加網(wǎng)絡(luò)拓?fù)?，以此來達(dá)到網(wǎng)絡(luò)維度的最小化。

NEAT算法訓(xùn)練智能體進行路徑規(guī)劃的步驟如下：

Step1智能體根據(jù)設(shè)定的時間步長，在仿真環(huán)境中隨機尋路。根據(jù)設(shè)置的適應(yīng)性函數(shù)，取得上一代所有智能體（表現(xiàn)型）的適應(yīng)性分?jǐn)?shù)。

Step2只保留適應(yīng)性分?jǐn)?shù)最高的智能體所對應(yīng)的神經(jīng)網(wǎng)絡(luò)，清空父代中剩余的智能體。

Step3適應(yīng)性分?jǐn)?shù)最高的智能體的神經(jīng)網(wǎng)絡(luò)作為該物種的代表，計算該神經(jīng)網(wǎng)絡(luò)和其他物種的兼容性。

Step4若存在15代內(nèi)適應(yīng)性分?jǐn)?shù)沒有提高的物種，刪除該物種。

Step5重新計算顯示適應(yīng)性共享分?jǐn)?shù)，并根據(jù)顯示適應(yīng)性共享分?jǐn)?shù)調(diào)整種群。

Step6計算在新的一代中，每個物種中子代的孵化數(shù)。

Step7通過突變和雜交，生成相應(yīng)個數(shù)的子代，并將子代的基因型轉(zhuǎn)化成神經(jīng)網(wǎng)絡(luò)表現(xiàn)型。

Step8計算所有物種及其個體的適應(yīng)性分?jǐn)?shù)。如果適應(yīng)性分?jǐn)?shù)小于閾值，則將該個體劃分至原來所屬物種中。反之，如果適應(yīng)性分?jǐn)?shù)大于閾值，則創(chuàng)建新的物種，并將該個體加入其中。

Step9將種群中所有物種所含有的個體的基因型轉(zhuǎn)換為神經(jīng)網(wǎng)絡(luò)表現(xiàn)型，并將每個表現(xiàn)型網(wǎng)絡(luò)加載到智能體，指導(dǎo)智能體的行為。

Step10重復(fù)Step1～Step9，隨著進化代數(shù)的增加，智能體在路徑規(guī)劃方面的性能會不斷提高。

5 實驗分析

仿真實驗平臺：智能體運動區(qū)間為400×400像素的窗口，其邊界存在屏障，所有智能體只能在屏障內(nèi)部運動?；顒訁^(qū)域內(nèi)，存在靜態(tài)障礙物。仿真環(huán)境的運行速度為60幀/s，每代的運行周期為2000步長。智能體的半徑為5個像素，傳感器的半徑為25像素。仿真實驗運行500代。神經(jīng)網(wǎng)絡(luò)的兩個輸出值vL，vR經(jīng)過logistic sigmoid函數(shù)做平滑處理，分別用于驅(qū)動智能體左右輪子的轉(zhuǎn)動。每代運行完畢之后，采用NEAT方法，根據(jù)個體的適應(yīng)性分?jǐn)?shù)，進化智能體的神經(jīng)網(wǎng)絡(luò)。網(wǎng)絡(luò)的初始狀態(tài)無隱含層。NEAT方法的主要演化參數(shù)如表1所示。

表1 NEAT神經(jīng)網(wǎng)絡(luò)主要的演化參數(shù)

將本文實驗所采用的NEAT算法和基于權(quán)重進化神經(jīng)網(wǎng)絡(luò)（Weight Evolving Neural Networks，WENN）算法［22］的仿真結(jié)果進行比較。設(shè)定進化代數(shù)為500代，分別通過智能體的適應(yīng)性值和智能體在趨于終點的過程中，訪問單元格的數(shù)量，以及優(yōu)化路徑的多樣性，這三個方面來評價兩種算法的特點。

圖6所呈現(xiàn)出的是眾多組仿真實驗中的一組實驗數(shù)據(jù)圖表。在本組實驗中，如圖6（b）所示，藍(lán)色曲線表示的是WENN算法，所訪問的單元格個數(shù)。在設(shè)定的運行代數(shù)內(nèi)，每一代所訪問的單元格個數(shù)均為2000，和實驗設(shè)置的步長一致。這表明在設(shè)定的進化代數(shù)內(nèi)，WENN算法并沒有成功的優(yōu)化出一條路徑。這說明此方法對初始化敏感，當(dāng)對固定結(jié)構(gòu)神經(jīng)網(wǎng)絡(luò)的權(quán)重進行隨機初始化時，不同的初始化將對進化算法的進化效果產(chǎn)生根本性的影響。以這組實驗而言，WENN算法在優(yōu)化的過程中，陷入了局部最優(yōu)解，雖然在進化到320代的時候，適應(yīng)性值出現(xiàn)了波動，但是并沒有對實驗的最終結(jié)果有所改善。NEAT算法并不存在初始化敏感的問題。雖然NEAT算法的網(wǎng)絡(luò)初始化也是隨機的，但是網(wǎng)絡(luò)會根據(jù)智能體在與環(huán)境的交互過程中所反饋的信息，以及NEAT算法本身的進化規(guī)則，使得網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)不斷進化，從而不斷地添加網(wǎng)絡(luò)節(jié)點和鏈接，而新的鏈接會被賦予新的權(quán)重。因此，NEAT算法對于初始化不敏感。

圖6 NEAT算法和固定結(jié)構(gòu)網(wǎng)絡(luò)的初始化敏感性比較

為了避免在進化的過程中陷入局部最優(yōu)解，NEAT算法設(shè)計了一個特有的機制：物種的形成機制。NEAT算法中，把為網(wǎng)絡(luò)添加新的鏈接和新的節(jié)點的行為，稱之為創(chuàng)新。一般情況下，擁有創(chuàng)新的個體適應(yīng)性并不是很強，這就意味著，新個體在尚未有機會去演繹任何潛在的有意義的行為時，就有很高的概率會被淘汰。這種情況的弊端在于，有潛力的創(chuàng)新不能被繼承。因此接下來的進化，只能局限在歷史相對較好的個體中，這種情況也會使得整體的優(yōu)化陷入到局部最優(yōu)解。而創(chuàng)新有可能在接下來的進化過程中，進化出相對于當(dāng)前個體更好的表現(xiàn)型。

基于上述問題，NEAT算法模擬了物種形成機制，為整個種群產(chǎn)生新的拓?fù)鋭?chuàng)新提供進化場所。這種機制的特點是，具有相似結(jié)構(gòu)的個體只在物種的內(nèi)部競爭，而不參與其他物種間的競爭。這種機制盡可能的避免了新產(chǎn)生的創(chuàng)新被淘汰的情況發(fā)生。

僅僅使用物種的形成機制還不足以保護種群中新的創(chuàng)新。為了更好的保護種群中的創(chuàng)新，必須幫助年幼的個體調(diào)整其適應(yīng)性的值，使得在合理長的一段時間內(nèi)，能有更多的不同的個體保持為活躍狀態(tài)。NEAT算法采用顯示適應(yīng)性共享的方法來實現(xiàn)這一想法。在NEAT中，適應(yīng)性分?jǐn)?shù)由物種的成員所共享，這實際上就是，每個個體的適應(yīng)性值都除以其相應(yīng)物種的大小。這樣，規(guī)模較大的物種的擴張性就會受到限制，而新生的物種在進化競爭中得以生存。此外，年輕的物種在適應(yīng)性共享計算中，被賦予了更易加速增長的適應(yīng)性分?jǐn)?shù)。

接下來這組實驗，在排除初始化敏感因素的前提下，對比兩種方法的實驗效果。從實驗結(jié)果分析來看，物種機制對于路徑規(guī)劃的多樣性，以及跳出當(dāng)前局部最優(yōu)解，尋找到更優(yōu)解均起到的良好的效果。圖7（a）、（b）、（c）表示在進化的過程中，使用NEAT算法分別在100代、300代和500代所尋找到的路徑，重復(fù)訪問的單元格做顏色加深渲染。這些被智能體尋找到的路徑，在軌跡上有本質(zhì)的區(qū)別。

圖7 NEAT算法實驗效果

而WENN算法，因為其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)是預(yù)先設(shè)定的。在算法運行過程中，僅僅對網(wǎng)絡(luò)的權(quán)重進行優(yōu)化。所以該方法只是在尋找到一條可行路徑之后，基于此路徑進行優(yōu)化，如圖8（a）、（b）、（c）所示，而這種優(yōu)化方式，往往會陷入局部最優(yōu)解。

圖8 WENN算法實驗效果

本組實驗中，基于NEAT算法和WENN算法的適應(yīng)性值比對如圖9（a）所示?；贜EAT算法和WENN算法的路徑單元格訪問數(shù)量比對如圖9（b）所示。

圖9 兩種算法對比圖

6 結(jié)語

本文采用NEAT算法進化神經(jīng)網(wǎng)絡(luò)，解決在未知環(huán)境下，智能體的路徑規(guī)劃問題。為了使智能體具備探測未知環(huán)境中障礙物的能力，設(shè)計了智能體的感知模型，同時為了解決智能體重復(fù)探測區(qū)域環(huán)境的問題，為智能體設(shè)計了記憶器模型。為了有效的指導(dǎo)NEAT算法的優(yōu)化方向，設(shè)計了合理的適應(yīng)性函數(shù)。實驗結(jié)果表明，在智能體感知模型和記憶器模型的作用下，NEAT算法在設(shè)定的進化周期內(nèi)，能夠通過適應(yīng)性函數(shù)的指導(dǎo)，快速優(yōu)化出一條路程最短且平滑的路徑。同時NEAT算法與傳統(tǒng)的將神經(jīng)網(wǎng)絡(luò)權(quán)重作為優(yōu)化對象的神經(jīng)進化算法相比，具有更快的收斂性。NEAT算法的物種機制對于路徑規(guī)劃的多樣性，以及跳出當(dāng)前局部最優(yōu)解，尋找到更優(yōu)解均起到了良好的效果。該方法有望為新一代家庭掃地機的研發(fā)提供了新的思路。