4.1功率負(fù)載線

4.2負(fù)載控制器

4.3電場風(fēng)資源與風(fēng)力發(fā)電機組的匹配

4.4風(fēng)電輸出與電網(wǎng)的匹配4.1功率負(fù)載線4.1.1最佳功率負(fù)載線在不同風(fēng)速下,風(fēng)輪機的輸出功率與風(fēng)輪機轉(zhuǎn)速的關(guān)系如圖41所示。從圖中曲線可以看出,在不同風(fēng)速下,風(fēng)輪機的輸出功率與轉(zhuǎn)速的關(guān)系特性曲線中皆有一個最大輸出功率值,如a、b、c…g點,將這些點連成曲線,就得到風(fēng)輪機的最佳功率輸出線,即最佳功率負(fù)載線,如圖41中虛線所示。前已闡明,風(fēng)輪機的輸出功率

而功率系數(shù)CP是風(fēng)輪機的高速性系數(shù)(或葉尖速比)λ的函數(shù),即

變化時,CP值是變化的,在某一個λ值時,CP值達到最大值,對應(yīng)于此最大CP值(CPmax)的λ值,稱為最佳葉尖速比。因此所謂最佳功率負(fù)載線即意味著在這條線上的各點皆是運行于最佳葉尖速比情況下。這就是說,當(dāng)風(fēng)速增大時,風(fēng)輪機轉(zhuǎn)速也應(yīng)隨之增高(即v增加,n增加),從而維持葉尖速比為最佳的葉尖速比,即λ=ωR/v不變(最佳),以達到維持風(fēng)能利用系數(shù)CP=CPmax不變,風(fēng)輪機的輸出功率也將達最大值。從最大限度地利用風(fēng)能的角度看,應(yīng)使風(fēng)輪機運行在最佳功率負(fù)載上,但從圖41可以看出,若風(fēng)輪機運行在最佳功率負(fù)載線上,則風(fēng)輪機的轉(zhuǎn)速應(yīng)隨風(fēng)速的變化而在很大的范圍內(nèi)變化。在獨立運行的風(fēng)力發(fā)電系統(tǒng)中,一般多采用同步發(fā)電機,而同步發(fā)電機輸出電能的頻率與其轉(zhuǎn)速有固定的比例關(guān)系(即頻率f∝n),這將導(dǎo)致供電質(zhì)量達不到要求。因此實際上風(fēng)力發(fā)電機在運行過程中應(yīng)按照用戶用電設(shè)備對電能質(zhì)量(如頻率、電壓)的要求,使風(fēng)輪機在盡可能接近最佳功率負(fù)載線的情況下運行,而不是在實際最佳功率負(fù)載線上運行。4.1.2實際功率負(fù)載線的確定及負(fù)載調(diào)節(jié)為了保證輸出電能的質(zhì)量(頻率、電壓等),風(fēng)輪機不可能完全按照最佳功率負(fù)載線運行,但應(yīng)盡量接近最佳功率負(fù)載線,特別是額定風(fēng)速及接近額定風(fēng)速時,風(fēng)輪機應(yīng)運行在最佳功率負(fù)載線上或靠近最佳功率負(fù)載線,如圖42所示。例如額定風(fēng)速為8m/s,則實際功率負(fù)載線應(yīng)選擇如圖42中實線所示,可以看出,當(dāng)如此選擇時,在6~8m/s風(fēng)速內(nèi)運行時,風(fēng)輪機的實際功率負(fù)載線與最佳功率負(fù)載線是靠近的。由圖42中還可以看出,按照所選擇的實際功率負(fù)載運行時,風(fēng)輪機轉(zhuǎn)速的變化,遠較按照最佳功率負(fù)載線運行時要小,這樣,輸出電能的質(zhì)量可以得到保證。圖42中,ns為額定風(fēng)速下風(fēng)輪機的轉(zhuǎn)速。而當(dāng)風(fēng)輪機在4~12m/s的風(fēng)速下運行時,風(fēng)輪機的轉(zhuǎn)速

為ns±Δn,相

應(yīng)

的

同

步

發(fā)

電

機

的

頻

率

將

為f(50Hz)±Δf。由圖42可以看出,當(dāng)風(fēng)速變化時,為了使風(fēng)輪機能沿著實際功率負(fù)載線運行,必須相應(yīng)地增加或減少負(fù)載,以使風(fēng)輪機的輸出功率與負(fù)載上所吸收(或消耗)的功率平衡,這就是負(fù)載調(diào)節(jié)。負(fù)載調(diào)節(jié)可以按照風(fēng)輪機在風(fēng)速(或負(fù)載)變化時轉(zhuǎn)速的變化來相應(yīng)地增加(投入)或減少(切除)負(fù)載,也可以按照發(fā)電機輸出電能頻率的變化來調(diào)節(jié)負(fù)載,從而使風(fēng)輪機轉(zhuǎn)速達到穩(wěn)定。所以,也可以認(rèn)為負(fù)載調(diào)節(jié)即是利用改變負(fù)載來穩(wěn)定風(fēng)輪機的轉(zhuǎn)速。由圖中可以看出,當(dāng)實際負(fù)載功率線選定的轉(zhuǎn)速變化范圍如果很小時,顯然可以提高發(fā)電機的供電質(zhì)量,但相對于比較小的轉(zhuǎn)速變化所需增加或減少的負(fù)載就顯得較大,對機組有沖擊作用,對機組運行的穩(wěn)定性會有影響。4.2負(fù)

載

控

制

器4.2.1分級負(fù)載控制器獨立運行的風(fēng)力發(fā)電系統(tǒng)最大的特點是不需要蓄能設(shè)備,直接向用戶的用電設(shè)備提供交流電能。采用負(fù)載調(diào)節(jié),理想的情況是根據(jù)來自發(fā)電機的頻率信號的變化連續(xù)地改變用戶負(fù)載,以使風(fēng)輪機的輸出功率與用戶負(fù)載達到平衡。實際上是采用分級投入或切除負(fù)載的方式來平衡風(fēng)輪機輸出功率的變化,只要每級負(fù)載的變化不是太大,風(fēng)輪機就能靠近最佳功率負(fù)載線運行。在采用負(fù)載調(diào)節(jié)的風(fēng)力發(fā)電系統(tǒng)中,經(jīng)常變動(投入或切除)的負(fù)載宜采用電阻式設(shè)備(如電熱器、電爐等)。這種性質(zhì)的負(fù)載屬于線性變化元件,對于提高整個系統(tǒng)運行的穩(wěn)定性有利,當(dāng)然變動負(fù)載的最大功率值應(yīng)按照風(fēng)輪機及發(fā)電機的最大允許功率值來確定,這樣,當(dāng)系統(tǒng)內(nèi)屬于經(jīng)常固定的負(fù)載因不需要而減少時,則可由系統(tǒng)內(nèi)的變動負(fù)載來補足。分級負(fù)載控制器的原理如圖43所示。將負(fù)載分成幾級,每一級負(fù)載的投入或切除動作點頻率皆不同,可以事先調(diào)整確定。當(dāng)發(fā)電機的輸出頻率大于該級負(fù)載投入動作點頻率,該級負(fù)載便投入;當(dāng)頻率變得小于該級負(fù)載切除動作點頻率,該級負(fù)載便切除。由于負(fù)載的投入和切除是分級進行的,當(dāng)投入或切除負(fù)載時會引起發(fā)電機輸出頻率相應(yīng)的變化。因此如果選擇某一級負(fù)載的投入與切除動作點的頻率相同,則可能引起該級負(fù)載在動作點反復(fù)投入和切除,為了避免這種現(xiàn)象,在同一級負(fù)載的投入動作點與切除動作點之間設(shè)置了回滯區(qū),使投入點頻率略高于標(biāo)稱動作點值,而切除點頻率略低于標(biāo)稱動作點頻率值。如圖44所

示,若

標(biāo)

稱

動

作

點

的

頻

率

選

定

為50Hz,回

滯

區(qū)

選

定

為-0.25Hz~0.25Hz,則該級負(fù)載投入點頻率為50.25Hz,切除點頻率為49.75Hz。這種負(fù)載投入點頻率與切除點頻率之間的回滯差,保證了整個系統(tǒng)的穩(wěn)定。利用負(fù)載調(diào)節(jié)系統(tǒng)中的分級負(fù)載控制器,可以自動依次投入或切除負(fù)載,使獨立的風(fēng)電系統(tǒng)達到穩(wěn)定運行,發(fā)電機的頻率可控制在49~51Hz或48~52Hz之間。為了防止獨立運行的風(fēng)力發(fā)電機組超負(fù)載運行,風(fēng)輪機應(yīng)具有槳距調(diào)節(jié)裝置或失速葉片,當(dāng)大風(fēng)或超速運行時能自動降低風(fēng)輪機輸出功率,保證系統(tǒng)的安全。4.2.2負(fù)載控制器與變速恒頻風(fēng)力發(fā)電當(dāng)風(fēng)輪機轉(zhuǎn)速波動(或停轉(zhuǎn)),發(fā)電機電壓低于蓄電池電壓時,發(fā)電機不但不能對蓄電池充電,相反,蓄電池卻要向發(fā)電機送出電流。為了防止這種情況出現(xiàn),在發(fā)電機電樞回路與蓄電池組之間加入截流器,其作用是當(dāng)發(fā)電機電壓低于蓄電池電壓時,截流器動作斷開兩者之間的連接。風(fēng)輪機帶動主發(fā)電機轉(zhuǎn)子旋轉(zhuǎn)后,由于發(fā)電機有剩磁,在發(fā)電機的附加繞組中產(chǎn)生感應(yīng)電勢。感應(yīng)電勢經(jīng)二極管全波整流后,供給勵磁機勵磁繞組。風(fēng)輪機與勵磁機的三相交流繞組同軸旋轉(zhuǎn),在三相交流繞組中感應(yīng)出交流電勢,經(jīng)三相半波旋轉(zhuǎn)二極管整流后供給主發(fā)電機勵磁繞組。主發(fā)電機勵磁繞組通電后,則在主發(fā)電機繞組中產(chǎn)生感應(yīng)電勢,同時又在附加繞組中感應(yīng)電勢,增大了勵磁機的勵磁繞組中的電流,從而又增大了主發(fā)電機勵磁繞組中的電流,如此反復(fù),在主發(fā)電機勵磁繞組內(nèi)的電流越來越大,而主發(fā)電機三相繞組內(nèi)感應(yīng)的電勢也越來越大,最后趨于穩(wěn)定,并建立起電壓。風(fēng)能是一種隨機性很強的能源,風(fēng)的方向不斷變化,風(fēng)力的大小時強時弱。風(fēng)速的變化會引起風(fēng)輪機轉(zhuǎn)速的變化,如果沒有必要的機械或電氣控制,則由風(fēng)輪機驅(qū)動的交流發(fā)電機的轉(zhuǎn)速也將隨之變化,因而發(fā)電機的輸出電壓及頻率都不是恒定的。無論是單獨由風(fēng)電站供電或是與其他類型發(fā)電機組(例如柴油發(fā)電機組)并聯(lián)運行,或是與電網(wǎng)并聯(lián),這都是不允許的。另一方面,眾所周知,風(fēng)能與風(fēng)速的立方成比例,當(dāng)風(fēng)速在一定范圍內(nèi)變化時,如果允許風(fēng)輪機變速運行,使風(fēng)輪機始終維持或接近在最佳葉尖速比下運行,也就是維持葉尖速比為最佳值并保持不變,從而使風(fēng)輪機的功率系數(shù)值不變,則能達到更好地利用風(fēng)能的目的。因此,變速恒頻發(fā)電方式具有重要的現(xiàn)實意義。實現(xiàn)變速恒頻發(fā)電可以有多種不同方案,例如交流

直流

交流轉(zhuǎn)換系統(tǒng);交流整流子發(fā)電機方式;磁場調(diào)制發(fā)電機及降頻轉(zhuǎn)換系統(tǒng)等。各種系統(tǒng)各有不同的特點,并且都在進一步的研究和發(fā)展中。交流

直流

交流轉(zhuǎn)換系統(tǒng)是將變速運轉(zhuǎn)的風(fēng)輪機轉(zhuǎn)子和交流發(fā)電機連接,發(fā)電機發(fā)出的變頻交流電,經(jīng)整流器變成直流,再經(jīng)逆變器轉(zhuǎn)變?yōu)楣ゎl交流電。這種方法在技術(shù)上是成熟的,但由于采用整流及逆變裝置,電子設(shè)備成本較高,會導(dǎo)致發(fā)電設(shè)備的投資費用提高。當(dāng)風(fēng)輪機的轉(zhuǎn)速由于風(fēng)速的變化而改變時,電磁滑差連接裝置的主動軸轉(zhuǎn)速將隨之改變,但與交流同步發(fā)電機硬性連接的電磁滑差連接裝置的從動軸轉(zhuǎn)速則可以通過自動調(diào)節(jié)電磁滑差連接裝置的磁場(通過調(diào)節(jié)勵磁電流)而維持不變,也就是使電磁滑差連接裝置的主動軸與從動軸之間的轉(zhuǎn)速差(滑差)作相應(yīng)的變化。磁場的調(diào)節(jié)是通過測速機構(gòu)及電子調(diào)節(jié)裝置而實現(xiàn)的。所以電磁滑差連接裝置變速恒頻發(fā)電系統(tǒng)是在風(fēng)輪機及發(fā)電機之間借助電磁聯(lián)系實現(xiàn)滑差連接,并通過調(diào)節(jié)電磁滑差連接裝置的磁場。改變滑差,就能在風(fēng)輪機風(fēng)速變化的情況下,保證在發(fā)電機端得到穩(wěn)定頻率的電源。電磁滑差連接裝置實質(zhì)上是一個特殊電機,起著離合器的作用。它由兩個旋轉(zhuǎn)的部分組成,區(qū)別于一般電磁離合器的地方,是在這兩個旋轉(zhuǎn)部分之間沒有機械上的硬性連接,而是以電磁場的方式實現(xiàn)從原動機到被驅(qū)動機械之間的彈性連接來傳遞力矩。從結(jié)構(gòu)原理上看,電磁連接裝置與工業(yè)上日趨廣泛使用的滑差電機相似。在工業(yè)上當(dāng)交流電動機由恒定頻率的電網(wǎng)供電時,滑差電機可作為均勻調(diào)速的裝置,實現(xiàn)由恒頻電能到變速機械能的能量轉(zhuǎn)換。而電磁滑差連接裝置與交流發(fā)電機一起則可以實現(xiàn)由變速的機械能到恒頻電能的轉(zhuǎn)換。電磁滑差連接裝置的結(jié)構(gòu)形式可以是多種多樣的?？紤]到運行可靠簡單,可以采用不帶滑環(huán)的無刷勵磁方式,其不足之處是滑差功率不能利用,特別是在滑差值比較大時整個系統(tǒng)的效率會受到影響。為提高整個系統(tǒng)的效率,同時獲得可以利用的直流電能,則可考慮采用轉(zhuǎn)動部分帶有滑環(huán)的結(jié)構(gòu)形式,通過滑環(huán)將滑差功率引出,當(dāng)然隨著滑差的變化,在滑環(huán)上引出的滑差功率的頻率及電壓也是變化的,但這種結(jié)構(gòu)形式對于充分利用風(fēng)能是有效的。由滑環(huán)引出的滑差功率經(jīng)過整流設(shè)備整流以后可以對蓄電池充電,并將這部分電功率輸送到需要直流電的網(wǎng)路上去。由滑環(huán)引出的滑差功率也可以經(jīng)過整流器及逆變器,先轉(zhuǎn)變成直流,再轉(zhuǎn)變成工頻交流電饋給電網(wǎng)。這也是一種交流

直流

交流轉(zhuǎn)換系統(tǒng)。4.3電場風(fēng)資源與風(fēng)力發(fā)電機組的匹配風(fēng)力發(fā)電的匹配問題包括兩個方面,一是風(fēng)力發(fā)電機組與風(fēng)電場風(fēng)資源的匹況,二是風(fēng)電場與電網(wǎng)的匹配?；鹆Πl(fā)電廠裝機容量越大,發(fā)電量也就越多,但風(fēng)力發(fā)電則不同,風(fēng)力發(fā)電機組必須和風(fēng)場資源相匹配,才能提高發(fā)電量。另外,在具有風(fēng)力發(fā)電的電網(wǎng)中,風(fēng)電場容量也不是越大越好,只有保持一定的比例,才能保證電力系統(tǒng)可靠、穩(wěn)定、經(jīng)濟運行,這就是風(fēng)電場與電網(wǎng)的匹配問題。對于一個特定的風(fēng)電場,風(fēng)力發(fā)電機組的輸出功率取決于多種因素。這些因素包括風(fēng)電場址的平均風(fēng)速,風(fēng)力發(fā)電機組輸出特性,特別是輪轂高度、切入風(fēng)速vc、額定風(fēng)速vr和切出風(fēng)速vf,如圖45所示?，F(xiàn)在,市場上銷售的風(fēng)力發(fā)電機組種類很多,容量從11kW到1.5MW不等。對于某一個風(fēng)電場,應(yīng)選擇最好而又適合的風(fēng)力發(fā)電機組,而不能局限于風(fēng)力發(fā)電機組容量。平均容量系數(shù)反映風(fēng)力發(fā)電機組與風(fēng)電場風(fēng)資源匹配信況,下面介紹怎樣計算風(fēng)力發(fā)電機組的平均容量系數(shù)。4.4風(fēng)電輸出與電網(wǎng)的匹配風(fēng)力發(fā)電機組并網(wǎng)運行,對電網(wǎng)有一定的影響。由于風(fēng)力發(fā)電機組單機容量比較小,一般不超過2MW,對于一個大電網(wǎng),影響很小,可以忽略。但對一個風(fēng)電場來說,由幾十臺、上百臺機組組成,總裝機容量超過幾十萬千瓦,對于一個容量不大的電網(wǎng),就會造成很大的影響,影響程度與風(fēng)電容量所占電網(wǎng)容量的比例有關(guān)。風(fēng)電場對電網(wǎng)有多大影響,為了保證電網(wǎng)安全可靠運行,風(fēng)電場容量應(yīng)占多大比例比較合適,這就是本節(jié)要研究的風(fēng)電場與電網(wǎng)的匹配問題。據(jù)丹麥專家分析,風(fēng)電比例低于10%對電網(wǎng)不會構(gòu)成危險。德國也曾提出過,風(fēng)電場并入人口稀少地區(qū)的電網(wǎng)可能受到容量的潛在限制。我國原電力部頒布的《風(fēng)力發(fā)電場并網(wǎng)運行管理規(guī)定》中有一條:風(fēng)電場容量與電網(wǎng)統(tǒng)一調(diào)度的原則是由穩(wěn)態(tài)運行下的電能質(zhì)量、最小線路損失和暫態(tài)穩(wěn)定性等因素決定。當(dāng)風(fēng)電場容量占電網(wǎng)統(tǒng)一調(diào)度容量的5%以下時,一般無需裝控制設(shè)備,當(dāng)超過5%時,應(yīng)與電網(wǎng)調(diào)度機構(gòu)協(xié)商解決。對于某電網(wǎng),目前風(fēng)電裝機容量已約占3.3%,有必要對風(fēng)電場與電網(wǎng)的匹配問題進行深入的研究,從而既充分利用風(fēng)能資源,又保證電網(wǎng)的安全、可靠、經(jīng)濟運行。風(fēng)電場對電網(wǎng)穩(wěn)態(tài)頻率的影響是指電網(wǎng)受到擾動后,從一個穩(wěn)態(tài)頻率到另一個穩(wěn)態(tài)頻率的情況,而不考慮期間的頻率變化過程。風(fēng)力發(fā)電的不穩(wěn)定性表現(xiàn)在間歇性和難以預(yù)計性。陣風(fēng)、從有風(fēng)到無風(fēng)等,都會對電網(wǎng)曲率產(chǎn)生影響。眾所周知,電力系統(tǒng)的作用是維持發(fā)電輸出功率和用電負(fù)荷的動態(tài)平衡。當(dāng)風(fēng)電場輸出功率突然增加時,對電網(wǎng)產(chǎn)生影響,電網(wǎng)頻率有增加的趨勢,電網(wǎng)對這種變化適應(yīng)能力比較強。當(dāng)風(fēng)電場電輸出功率下降時,或者用電負(fù)荷增加時,這樣就破壞了原有電力平衡,旋轉(zhuǎn)備用容量經(jīng)一次調(diào)頻和二次調(diào)頻后,若仍不能達到新的電力平衡,即仍有功率缺額ΔP,則電網(wǎng)球頻率必然下降,同時用電負(fù)荷的功率隨之下降,其下降額度等于功率缺額ΔP時,重新達到電力平衡,電網(wǎng)頻率也就穩(wěn)定下來。負(fù)荷的這種對頻率的補償作用稱為負(fù)荷的頻率靜特性。該特性在50Hz附近可以近似為一條直線,其數(shù)學(xué)表達式為式中:k為負(fù)荷頻率調(diào)節(jié)效應(yīng)系數(shù),P0為初始用電負(fù)荷,f0為初始電網(wǎng)頻率,ΔP為功率缺額,Δf為允許頻率偏差。假設(shè)一個風(fēng)電場的裝機容量為P風(fēng),風(fēng)電負(fù)載率為mi,則電風(fēng)場輸出功率為miP風(fēng)

。常規(guī)電源裝機總?cè)萘繛镻0,常規(guī)電源開機容量P風(fēng),旋轉(zhuǎn)備用容量的比率mc,則常規(guī)電源輸出(1-mc)P開

。電網(wǎng)總的容量為從以上公式可以看出,風(fēng)電比例與電網(wǎng)正常運行頻率、允許頻率偏差、負(fù)荷頻率調(diào)節(jié)效應(yīng)系數(shù)以及風(fēng)電負(fù)載率、允許的常規(guī)電源旋轉(zhuǎn)備用容量等因素有關(guān)系。解決風(fēng)電場與電網(wǎng)的匹配問題,常規(guī)電源開機容量占最大負(fù)荷的比例、風(fēng)電裝機容量占最大負(fù)荷的比例、風(fēng)電裝機容量占常規(guī)開機容量的比例可以參考式(410)~(412)進行。實際上,計算復(fù)雜度是O(n3),n是狀態(tài)數(shù)量。因此直接求解僅適用于小規(guī)模的MRP。大

規(guī)

模MRP的

求

解

通

常

使

用

迭

代

法。

常

用

的

迭

代

法

有:動

態(tài)

規(guī)

劃、蒙

特

卡

羅

評

估、

時

序

差

分

學(xué)

習(xí),后文會逐步講解這些方法。4.馬爾科夫決策過程相較于馬爾科夫獎勵過程,馬爾科夫決策過程多了一個行為集合A,它是這樣的一個元組:<S,A,P,R,γ>。看起來很類似馬爾科夫獎勵過程,但這里的P和R都與具體的行為a對應(yīng),而不像馬爾科夫獎勵過程那樣僅對應(yīng)于某個狀態(tài),A表示的是有限的行為的集合。具體的數(shù)學(xué)表達式如下:在學(xué)生馬爾科夫問題中,圖4.8所示為一個可能的MDP的狀態(tài)轉(zhuǎn)化圖。圖中的文字表示的是采取的行為,而不是先前的狀態(tài)名。對比之前的學(xué)生MRP示例可以發(fā)現(xiàn),即時獎勵與行為對應(yīng)了,同一個狀態(tài)下采取不同的行為得到的即時獎勵是不一樣的。由于引入了行為,容易與狀態(tài)名混淆,因此此圖沒有給出各狀態(tài)的名稱;此圖還把“通過”和“睡覺”狀態(tài)合并成一個終止?fàn)顟B(tài);另外當(dāng)選擇“看書”這個動作時,主動進入了一個臨時狀態(tài)(圖中用黑色小實點表示),隨后被動地被環(huán)境按照其動力學(xué)分配到另外三個狀態(tài),也就是說此時智能體沒有選擇權(quán)決定去哪一個狀態(tài)。策略π是概率的集合或分布,其元素π(a|s)為對過程中的某一狀態(tài)s采取可能的行為a的概率:一個策略完整地定義了個體的行為方式,也就是說定義了個體在各個狀態(tài)下的各種可能的行為方式以及其概率的大小。策略僅和當(dāng)前的狀態(tài)有關(guān),與歷史信息無關(guān);同時某一確定的策略是靜態(tài)的,與時間無關(guān);但是個體可以隨著時間更新策略。當(dāng)給定一個MDP:M=<S,A,P,R,γ>和一個策略π時,狀態(tài)序列S1,S2,…是一個馬爾科夫過程<S,Pπ>;同樣,狀態(tài)和獎勵序列S1,R2,S2,R3,S3,…是一個馬爾科夫獎勵過程<S,Pπ,Rπ,γ>,并且在這個獎勵過程中滿足下面的方程:通俗地講,在執(zhí)行策略π時,狀態(tài)從s轉(zhuǎn)移至s'的概率等于一系列概率的和,這一系列概率指的是在執(zhí)行當(dāng)前策略時,執(zhí)行某一個行為的概率與該行為能使?fàn)顟B(tài)從s轉(zhuǎn)移至s'的概率的乘積。獎勵函數(shù)表示如下:當(dāng)前狀態(tài)s下執(zhí)行某一指定策略得到的即時獎勵是該策略下所有可能行為得到的獎勵與該行為發(fā)生的概率的乘積的和。策略在MDP中的作用相當(dāng)于智能體可以在某一個狀態(tài)時做出選擇,進而有形成各種馬爾科夫過程的可能,而且基于策略產(chǎn)生的每一個馬爾科夫過程是一個馬爾科夫獎勵過程,各過程之間的差別是不同的選擇產(chǎn)生了不同的后續(xù)狀態(tài)以及對應(yīng)的不同的獎勵?；诓呗缘膬r值函數(shù),定義vπ(s)是在MDP下基于策略π的狀態(tài)價值函數(shù),表示從狀態(tài)s開始,遵循當(dāng)前策略時所獲得的期望;或者說在執(zhí)行當(dāng)前策略π時,衡量個體處在狀態(tài)s時的價值大小,數(shù)學(xué)表示如下:注意策略是靜態(tài)的、關(guān)于整體的概念,不隨狀態(tài)改變而改變;變化的是在某一個狀態(tài)時,依據(jù)策略可能產(chǎn)生的具體行為,因為具體的行為是有一定的概率的,策略就是用來描述各個不同狀態(tài)下執(zhí)行各個不同行為的概率。定義qπ(s,a)為行為價值函數(shù),表示在執(zhí)行策略π時,對當(dāng)前狀態(tài)s執(zhí)行某一具體行為a所能收獲的期望;或者說在遵循當(dāng)前策略π時,衡量對當(dāng)前狀態(tài)執(zhí)行行為a的價值大小。行為價值函數(shù)一般都是與某一個特定的狀態(tài)相對應(yīng)的,其公式如下:圖4.9解釋了行為價值函數(shù),其中vπ(s)(π(a|s))=0.5,γ=1。1)貝爾曼(Bellman)期望方程MDP下的狀態(tài)價值函數(shù)(見圖4.10)和行為價值函數(shù)與MRP下

的

價

值

函

數(shù)(見

圖4.11)可以改用下一時刻狀態(tài)價值函數(shù)或行為價值函數(shù)來表達,具體方程如下:其中:γ表示離開當(dāng)前狀態(tài)的獎勵。vπ(s)和qπ(s,a)的關(guān)系可由圖4.10和圖4.11所示。圖中,空心圓圈表示狀態(tài),黑色實心小圓表示的是動作本身,連接狀態(tài)和動作的線條僅僅把該狀態(tài)以及該狀態(tài)下可以采取的行為關(guān)聯(lián)起來?？梢钥闯?在遵循策略π時,狀態(tài)s的價值體現(xiàn)為在該狀態(tài)下遵循某一策略而采取所有可能行為的價值按行為發(fā)生概率的乘積求和,即有類似地,一個行為價值函數(shù)也可以表示成狀態(tài)價值函數(shù)的形式:式(4.28)表明,某一個狀態(tài)下采取一個行為的價值可以分為兩部分:其一是離開這個狀態(tài)的價值,其二是所有進入新的狀態(tài)的價值與其轉(zhuǎn)移概率乘積的和。如果組合起來,可以得到下面的結(jié)果,如圖4.12所示:也可以得到下面的結(jié)果,如圖4.13所示:在學(xué)生馬爾科夫問題中,圖4.14解釋了空心圓圈狀態(tài)的狀態(tài)價值是如何計算的,其遵循隨機策略,即所有可能的行為有相同的概率被選擇執(zhí)行:Bellman期望方程如下:2)最優(yōu)價值函數(shù)最優(yōu)狀態(tài)價值函數(shù)v*(s)指的是在從所有策略產(chǎn)生的狀態(tài)價值函數(shù)中,選取使?fàn)顟B(tài)s價值最大的函數(shù):類似地,最優(yōu)行為價值函數(shù)q*(s,a)指的是從所有策略產(chǎn)生的行為價值函數(shù)中,選取出狀態(tài)行為對<s,a>價值最大的函數(shù):最優(yōu)價值函數(shù)明確了MDP的最優(yōu)可能表現(xiàn),當(dāng)我們知道了最優(yōu)價值函數(shù)時,也就知道了每個狀態(tài)的最優(yōu)價值,這時便認(rèn)為MDP得到了解決。學(xué)生MDP問題的最優(yōu)狀態(tài)價值如圖4.15所示。學(xué)生MDP問題的最優(yōu)行為價值如圖4.16所示,其中q*(s,a),γ=1代表最優(yōu)價值。3)最優(yōu)策略若對于任何狀態(tài)s,遵循策略π的價值不小于遵循策略π'下的價值,則策略π優(yōu)于策略π':定理4.1.1對于任何MDP,下面幾點成立:(1)存在一個最優(yōu)策略,比任何其他策略更好或至少相等。(2)所有的最優(yōu)策略都有相同的最優(yōu)價值函數(shù)。(3)所有的最優(yōu)策略都具有相同的行為價值函數(shù)。一般地,可以通過最大化最優(yōu)行為價值函數(shù)來找到最優(yōu)策略:對于任何MDP問題,總存在一個確定性的最優(yōu)策略;同時如果我們知道最優(yōu)行為價值函數(shù),則表明已找到了最優(yōu)策略。在學(xué)生MDP問題

中,圖4.17所

示

為

最

優(yōu)

策

略,圖

中

雙

線

箭

頭

表

示

的

是

最

優(yōu)

策

略π*(a|s),γ=1的行為。4)Bellman最優(yōu)方程針對v*,一個狀態(tài)的最優(yōu)價值等于從該狀態(tài)出發(fā)采取的所有行為產(chǎn)生的行為價值中最大的那個行為價值,如圖4.18所示,其公式如下:針對q*,在某個狀態(tài)s下,采取某個行為的最優(yōu)價值由兩部分組成:一部分是離開狀態(tài)s的即刻獎勵,另一部分則是所有能到達的狀態(tài)s'的最優(yōu)狀態(tài)價值按出現(xiàn)概率求和。如圖4.19所示,其公式如下:組合起來,針對v*,如圖4.20所示,有針對q*,如圖4.21所示,有Bellman最優(yōu)方程(如圖4.22所示)學(xué)生MDP示例:Bellman最優(yōu)方程是非線性的,沒有固定的解決方案,可通過一些迭代方法來解決,如價值迭代算法、策略迭代算法、Q學(xué)習(xí)算法、Sarsa算法等,后續(xù)會逐步展開講解。4.1.4動態(tài)規(guī)劃1.動態(tài)規(guī)劃簡介動態(tài)規(guī)劃是運籌學(xué)的一個分支,是求解決策過程最優(yōu)化的過程。20世紀(jì)50年代初,美國數(shù)學(xué)家貝爾曼等人在研究多階段決策過程的優(yōu)化問題時,提出了著名的最優(yōu)化原理,從而創(chuàng)立了動態(tài)規(guī)劃。動態(tài)規(guī)劃的應(yīng)用極其廣泛,包括工程技術(shù)、經(jīng)濟、工業(yè)生產(chǎn)、軍事以及自動化控制等領(lǐng)域,并在背包問題、生產(chǎn)經(jīng)營問題、資金管理問題、資源分配問題、最短路徑問題和復(fù)雜系統(tǒng)可靠性問題等中取得了顯著的效果。其基本思想是將待求解問題分解成若干個子問題,先求解子問題,然后從這些子問題的解中得到原問題的解。適合于用動態(tài)規(guī)劃求解的問題,經(jīng)分解得到的子問題往往不是相互獨立的,因此在解決子問題的時候,通常需要將結(jié)果存儲起來用以解決后續(xù)復(fù)雜問題。這樣就可以避免大量地重復(fù)計算,節(jié)省了時間。動態(tài)規(guī)劃體現(xiàn)的是“分而治之”的思想。能夠通過動態(tài)規(guī)劃來解決的問題至少需要滿足以下兩個條件:(1)一個復(fù)雜問題的最優(yōu)解由數(shù)個小問題的最優(yōu)解構(gòu)成,可以通過尋找子問題的最優(yōu)解來得到復(fù)雜問題的最優(yōu)解。(2)子問題在復(fù)雜問題內(nèi)重復(fù)出現(xiàn),使得子問題的解可以被存儲起來重復(fù)利用。2.策略迭代算法策略迭代算法是動態(tài)規(guī)劃中求最優(yōu)策略的基本方法之一。它借助于動態(tài)規(guī)劃基本方程,交替使用“策略評估”和“策略改進”兩個步驟,求出逐次改進的、最終達到或收斂于最優(yōu)策略的策略序列。求解給定策略的狀態(tài)價值函數(shù)的過程叫作策略評估。策略評估的基本思路是從任意一個狀態(tài)價值函數(shù)開始,依據(jù)給定的策略,結(jié)合貝爾曼期望方程、狀態(tài)轉(zhuǎn)移概率和獎勵同步迭代更新狀態(tài)價值函數(shù),直至其收斂,得到該策略下最終的狀態(tài)價值函數(shù)。在用迭代法求解狀態(tài)價值函數(shù)時,先為所有狀態(tài)的價值函數(shù)設(shè)置初始值,然后用公式更新所有狀態(tài)的價值函數(shù),第k次迭代時狀態(tài)價值函數(shù)的計算公式為策略評估的目的是找到更好的策略,即策略改進。策略改進通過按照某種規(guī)則對當(dāng)前策略進行調(diào)整從而得到更好的策略。假設(shè)π'和π是兩個不同的策略,如果對于所有狀態(tài)s,都有Qπ[s,π'(s)]>Vπ(s),則稱策略π'比π更好?？梢员闅v所有狀態(tài)和所有動作,采用貪心策略獲得新策略。具體做法是對于所有狀態(tài)都按照下面的公式計算新的策略:每次選擇的都是能獲得最好回報的動作,用它們來更新每個狀態(tài)下的策略函數(shù),從而完成對策略函數(shù)的更新。策略迭代是策略評估和策略改進的結(jié)合。從一個初始策略開始,不斷地改進這個策略達到最優(yōu)解。在每次迭代中,首先進行策略評估,根據(jù)當(dāng)前策略估計其狀態(tài)價值函數(shù)。然后進行策略改進,根據(jù)評估結(jié)果調(diào)整策略以優(yōu)化其性能。最后計算新策略的狀態(tài)價值函數(shù),如此反復(fù)直到收斂。策略迭代的原理如圖4.23所示。3.價值迭代算法由于最優(yōu)策略對應(yīng)最優(yōu)價值函數(shù),因此可以通過直接求出最優(yōu)價值函數(shù)推出最優(yōu)策略,這就是價值迭代算法的思路。根據(jù)貝爾曼最優(yōu)化原理,如果一個策略是最優(yōu)策略,整體最優(yōu)的解的局部也一定最優(yōu),因此,最優(yōu)策略可以分解成兩部分:從狀態(tài)s到s'采用了最優(yōu)策略,在狀態(tài)s'時采用的策略也是最優(yōu)的。根據(jù)這一原理,每次選擇當(dāng)前回報和未來回報之和最大的動作,價值迭代的更新公式為價值迭代算法與策略迭代算法的區(qū)別在于,前者不是對某一策略的狀態(tài)價值函數(shù)進行計算的,而是直接收斂到最優(yōu)的價值函數(shù)。價值迭代算法的流程如算法4.2所示。4.1.5蒙特卡羅算法蒙特卡羅算法也稱為統(tǒng)計模擬方法、隨機抽樣技術(shù),是一種隨機模擬方法,它以概率和統(tǒng)計理論方法為基礎(chǔ),是可使用隨機數(shù)來解決很多計算問題的方法。將所求解的問題與一定的概率模型相聯(lián)系,用電子計算機實現(xiàn)統(tǒng)計模擬或抽樣,以獲得問題的近似解。由于該方法可以象征性地表示概率統(tǒng)一特征,故借用賭城蒙特卡羅命名。1.算法簡介蒙特卡羅算法通過隨機樣本來計算目標(biāo)函數(shù)的值,它使用隨機數(shù)來進行場景的模擬或者過程的仿真,其核心思想就是通過模擬出來的大量樣本集或者隨機過程去近似我們想要研究的實際問題對象。當(dāng)我們在強化學(xué)習(xí)中使用蒙特卡羅方法的時候,需要對來自不同片段或隨機過程中的每個狀態(tài)

動作對相應(yīng)的獎勵值取平均。最開始,我們可能無法對狀態(tài)價值有一個很好的預(yù)估,但是當(dāng)我們做出更多的嘗試以后,平均狀態(tài)價值會向它們的真實值靠近。2.蒙特卡羅預(yù)測蒙特卡羅預(yù)測是一種基于智能體與環(huán)境之間的交互片段來估計價值函數(shù)的方法。在這里先定義片段的概念,它是從某一狀態(tài)開始,執(zhí)行一些動作,直到終止?fàn)顟B(tài)為止的一個完整的狀態(tài)和動作序列,這類似于循環(huán)神經(jīng)網(wǎng)絡(luò)中的時間序列樣本。蒙特卡羅算法從這些片段樣本中學(xué)習(xí),估算出狀態(tài)價值函數(shù)和動作價值函數(shù)。實現(xiàn)方法非常簡單:按照一個策略執(zhí)行,得到一個狀態(tài)和回報序列,即片段;通過多次執(zhí)行,收集多個這樣的片段;然后基于這些片段樣本來估計價值函數(shù)。在蒙特卡羅算法中,狀態(tài)價值函數(shù)的估計值是所有片段中以該狀態(tài)計算得到的回報的平均值。具體實現(xiàn)時,根據(jù)給定的策略生成一些片段樣本:如果要計算狀態(tài)s的價值函數(shù),則在這些片段中找到s出現(xiàn)的位置,假設(shè)為st,然后按照狀態(tài)價值函數(shù)的定義計算它的價值函數(shù)值:可能會出現(xiàn)這種情況:遇到從狀態(tài)s離開后又返回此狀態(tài)的情形時,蒙特卡羅算法有兩種處理策略,即First-Visit和Every-Visit。前者只使用第一次到達狀態(tài)s時所計算的價值函數(shù)值,后者對每次進入狀態(tài)s時的價值函數(shù)值累加取平均。蒙特卡羅預(yù)測算法的流程如算法4.3所示。3.蒙特卡羅控制在動態(tài)規(guī)劃中介紹了策略迭代,現(xiàn)在可以把策略迭代運用到蒙特卡羅算法中。策略迭代包括策略評估和策略改進兩個部分。策略評估的過程與在動態(tài)規(guī)劃中一樣。在此主要介紹策略改進。對狀態(tài)

動作使用貪心策略,確保在一個狀態(tài)下有最高價值的動作:對于每一次策略改進,都需要根據(jù)qπt來構(gòu)造πt+1。策略改進通過下列方式實現(xiàn):式(4.46)表明πt+1優(yōu)于πt,即會在迭代策略改進后最終找到最優(yōu)策略。蒙特拉羅控制算法流程如算法4.4所示。與價值迭代算法類似,這里首先計算了所有的狀態(tài)

動作對的價值函數(shù),然后更新策略,將每種狀態(tài)下的動作置為使得動作價值函數(shù)最大的動作,反復(fù)迭代直至收斂4.1.6時序差分算法時序差分概念最早是由A.sammuel在他的跳棋算法中提出的。1988年,Sutton首次證明了時序差分算法在最小均方誤差上的收斂性。時序差分算法是強化學(xué)習(xí)中的另一種核心方法,它結(jié)合了動態(tài)規(guī)劃和蒙特卡羅算法的思想。與動態(tài)規(guī)劃相似,時序差分算法在估算的過程中使用了自舉;和蒙特卡羅算法一樣的是,它不需要在學(xué)習(xí)過程中了解環(huán)境的全部信息。最基本的TD算法用貝爾曼方程估計價值函數(shù)的值,然后構(gòu)造更新項。迭代更新公式為式中:Rt+1+γV(St+1)稱為TD目標(biāo)值,Rt+1+γV(St+1)-V(St)稱為TD誤差,α為步長參數(shù)。這種方法也叫作TD(0)或者單步TD。通過將目標(biāo)值改為在N步未來中的折扣回報和N步過后的估計狀態(tài)價值可實現(xiàn)N步TD。TD(0)學(xué)習(xí)算法流程如算法4.5所示。1.Sarsa算法———在線策略TD控制Sarsa算法是由Rummmy和Niranjan于1994年提出的。它的迭代更新公式如下:該算法描述的是這一過程:在一個狀態(tài)St下,選擇一個行為At,形成一個狀態(tài)-行為對(St,At),經(jīng)過與環(huán)境交互后得到回報Rt+1,然后進入下一個狀態(tài)St+1;選擇一個新的動作At+1產(chǎn)生第二個狀態(tài)-行為對(St+1,At+1),利用后一個狀態(tài)-行為對的值函數(shù)Q(St+1,At+1)更新前一個狀態(tài)-行為對的值函數(shù)Q(St,At)。Sarsa算法的流程如算法4.6所示。2.Q學(xué)習(xí)算法--離線策略TD控制Q學(xué)習(xí)算法是Watkins和Dayan于1992年提出的。它的要點是目標(biāo)值不再依賴所使用的策略，而只依賴狀態(tài)-動作對的價值函數(shù)。其更新公式如下:4.1.7算法實踐———迷宮尋寶本節(jié)通過“迷宮尋寶”來對上述內(nèi)容進行實踐,本節(jié)的“迷宮尋寶”主要參考了《強化學(xué)習(xí)》相關(guān)內(nèi)容。1.環(huán)境描述迷宮是一個5×5的網(wǎng)格世界,對應(yīng)的馬爾可夫決策模型共有24個狀態(tài),如圖4.24所示。網(wǎng)格世界每個格子的邊長是40像素,空心方塊表示智能體,邊長為30像素。狀態(tài)用空心智能體移動至當(dāng)前格子時,空心方塊與網(wǎng)格格子中心重疊后,空心方塊左上和右下角的坐標(biāo)表示。例如,網(wǎng)格世界第一行第一列的格子所代表的狀態(tài)可表示為(5,5,35,35),以此類推,可得到迷宮游戲的全部狀態(tài)空間。其中有七個陷阱(圖中實心方塊所在位置)和一個寶藏區(qū)(圖中實心圓所在位置)?？招姆綁K表示智能體,可執(zhí)行的行為分別為朝上、下、左、右移動一步,則動作空間標(biāo)記為A={0,1,2,3},0、1、2、3分別對應(yīng)上、下、左、右。在這個迷宮游戲中,智能體一旦進入陷阱位置,就獲得負(fù)1回報,游戲終止;智能體一旦進入寶藏區(qū),就獲得正1回報,游戲終止。除此之外,智能體任何移動的回報都為0;并且當(dāng)智能體位于網(wǎng)格世界邊緣格子時,任何使得智能體試圖離開格子世界的行為都會使得智能體停留在移動前的位置。對于智能體來說,它不清楚整個格子世界的構(gòu)造,不知道格子是長方形還是正方形,不知道格子世界的邊界在哪里,也不清楚陷阱和寶藏的具體位置。智能體能做的就是不斷地進行上下左右移動,與環(huán)境進行交互,通過環(huán)境反饋的回報不斷調(diào)整自己的行為。假設(shè)在此網(wǎng)格世界游戲中,智能體的狀態(tài)轉(zhuǎn)移概率,折扣因子γ=1。接下來求解此網(wǎng)格世界尋找寶藏的最優(yōu)策略。2.環(huán)境代碼下面根據(jù)上述內(nèi)容構(gòu)建網(wǎng)格尋寶環(huán)境,環(huán)境代碼主要由一個Maze類構(gòu)成,包含如下方法。def_build_maze(self):構(gòu)建迷宮的方法,該方法給出了陷阱位置、寶藏位置及智能體的初始位置;并且定義了動作空間,給出了狀態(tài)轉(zhuǎn)換過程以及行為回報。defstep(self,action):根據(jù)當(dāng)前行為，返回下一步的位置、立即回報，以及判斷游戲是否終止。defreset(self):根據(jù)當(dāng)前狀態(tài)，重置畫布，defrenderby_policy(self,policy,result_list):根據(jù)傳人策略進行界面渲染。環(huán)境代碼如下:3.算法詳情本節(jié)使用Sarsa算法對帶陷阱的網(wǎng)格世界馬爾可夫決策問題進行求解?？傮w思路是以ε-貪心策略采樣數(shù)據(jù)生成軌跡。針對每一條軌跡的每個時間步,進行次策略評估,根據(jù)下式更新狀態(tài)-行為對的行為值函數(shù):每條軌跡結(jié)束后,根據(jù)更新的值函數(shù)對策略進行改進。規(guī)定軌跡總數(shù)目為100條。超出軌跡數(shù)目之后,輸出最優(yōu)策略。具體操作過程如下。(1)初始化全部行為值函數(shù)Q(s,a)=0。當(dāng)前的q值以q表形式存儲,創(chuàng)建q表,代碼如下:(2)初始化環(huán)境,得到初始狀態(tài)s1。這里指的是智能體的初始位置,s1=(5,5,35,35),代碼如下:(3)基于狀態(tài)s1,遵循ε-貪心策略選擇行為為a1。例如,得到動作a1=2(表示向右移動一格),得到第一個狀態(tài)-行為對(s1,a1)。(4)動作a1作用于環(huán)境,獲得立即回報R1和下一個狀態(tài)s2,同時得到了軌跡是否終止的標(biāo)識。這里:s2=(45,5,75,35),R1=0,done=false(表示軌跡未終止)。代碼如下:(5)基于狀態(tài)s2,繼續(xù)遵循ε-貪心策略,得到行為a2。這里動作a2=0(表示向右移動一格),得到第二個狀態(tài)-行為對(s2,a2)。代碼如下:(6)通過第二個狀態(tài)-行為對(s2,a2)的行為值函數(shù)Q(s2,a2)更新第一個狀態(tài)-行為對(s2,a2)的行為值函數(shù)Q(s2,a2)。根據(jù)公式Q(s1,a1)←Q(s1,a1)+α[r+γQ(s2,a2)-Q(s1,a1)],計算得到Q(s1,a1)=0,緊接著,令s2=s1。代碼如下:(7)重復(fù)步驟(3)和(6),直至軌跡結(jié)束。(8)結(jié)合更新后的行為值函數(shù),采用ε-貪心法對原始策略進行更新。代碼如下:(9)重復(fù)步驟(2)~(8),直至軌跡數(shù)等于100。最終得到的最優(yōu)策略如圖4.25所示。圖4.25所示為智能體從起點出發(fā)找到寶藏的最優(yōu)路徑。最優(yōu)路徑所在狀態(tài)經(jīng)歷了多次探索,由此可得到比較準(zhǔn)確的最優(yōu)行為。而其他狀態(tài)經(jīng)歷次數(shù)很少,給出的最優(yōu)行為不精確。例如,寶藏左右兩側(cè)的網(wǎng)格位置,因為智能體從沒有經(jīng)歷過,因此其四個方向的行為值函數(shù)均為0,對應(yīng)的最優(yōu)行為為四個方向中的任意一個。為簡要地說明問題,僅列出最優(yōu)路徑經(jīng)歷的狀態(tài)及采取的最優(yōu)行為,見表4.3。其中最優(yōu)行為是帶有ε隨機性的隨機行為,以ε的概率選擇當(dāng)前最優(yōu)動作,以1-ε的概率隨機選擇一種行為。4.核心代碼Sarsa算法中最核心的方法是update()方法,循環(huán)遍歷100條軌跡中的每一個時間步;進行行為的選擇和行為值函數(shù)的更新，并基于行為值函數(shù)進行策略改進。update()方法調(diào)用的其他基礎(chǔ)方法均寫在RL類中，例如:defchoose_action(str(observation)):基于輸人狀態(tài),根據(jù)ε貪心策略選擇行為。deflearn(str(observation),action,reward,str(observation_),action_):Sarsa的值函數(shù)更新方法。由代碼可見，Sarsa算法自始至終都在維護一個q表(q_table，行為值函數(shù)表)，此表記錄了智能體所經(jīng)歷過的狀態(tài)-行為對的行為值函數(shù)，defgetpolicy(…):基于當(dāng)前g表，繪制最優(yōu)策略圖。具體代碼如下。4.2路徑規(guī)劃算法4.2.1傳統(tǒng)路徑規(guī)劃算法傳統(tǒng)路徑規(guī)劃算法包括Dijkstra算法、A*算法、D*算法、人工勢場法等,下面著重介紹Dijkstra算法和A*算法。1.Dijkstra算法Dijkstra算法由荷蘭計算機科學(xué)家EdsgerW.Dijkstra于1959年提出。Dijkstra算法是很有代表性的最短路徑算法,用于計算一個結(jié)點到其他結(jié)點的最短路徑。該算法指定一個點(源點)到其余各個結(jié)點的最短路徑,因此也叫作單源最短路徑算法。Dijkstra算法的思想是廣度優(yōu)

先

搜

索

貪

心

策

略。對

于

計

算

非

加

權(quán)

圖

中

的

最

短

路

徑,也

可

使

用

貪

心

算

法。Dijkstra算法是對貪心算法的推廣,以起始點為中心向外層擴展,并且每一次都選擇最優(yōu)的結(jié)點進行擴展,直到擴展到終點為止。Dijkstra算法可以劃歸為貪心算法,下一條路徑都是由當(dāng)前更短的路徑派生出來的更長的路徑。該算法在移動機器人路徑規(guī)劃領(lǐng)域應(yīng)用得非常廣泛,算法4.8為Dijkstra算法偽代碼。算法中,G為帶權(quán)重的有向圖,s是起點(源點),V表示G中所有頂點的集合,(u,v)表示頂點u到v有路徑相連,w(u,v)表示頂點u到v之間的非負(fù)權(quán)重。算法是通過為每個頂點u保留當(dāng)前為止找到的從s到v的最短路徑進行工作的。初始時,源點s的路徑權(quán)重被賦為0,所以d[s]=0。若對于頂點u存在能夠直接到達的邊(s,u),則把d[v]設(shè)為w(s,u),同時把所有其他源點s不能直接到達的頂點的路徑長度設(shè)為無窮大,即表示當(dāng)前還不知道任何通向這些頂點的路徑。當(dāng)算法結(jié)束時,d[v]中存儲的便是從s到u的最短路徑,如果路徑不存在,則其值是無窮大。Dijkstra算法中邊的拓展如下:如果存在一條從u到v的邊,那么從s到u的最短路徑可以通過將邊(s,u)添加到從s到u的路徑尾部拓展一條從s到v的路徑。這條路徑的長度是d[u]+w(u,v)。如果這個值比當(dāng)前已知的d[v]的值小,則可以用新值替代當(dāng)前d[v]中的值。拓展邊的操作,一直運行到所有的d[v]都代表從s到v的最短路徑的長度值。此算法的組織令d[u]達到其最終值時,每條邊(u,v)都只被拓展一次。算法維護兩個頂點集合S和Q。集合S保留所有已知最小d[v]值的頂點v,而集合Q則保留其他所有頂點。集合S的初始狀態(tài)為空,而后每一步都有一個頂點從Q移動到S。這個被選擇的頂點是Q中擁有最小d[u]值的頂點。當(dāng)一個頂點u從Q中轉(zhuǎn)移到S中時,算法對u的每條外接邊(u,v)進行拓展。同時,上述算法保留圖G中源點s到每一個頂點v的最短距離d[v],同時找出并保留v在此最短路徑上的“前趨”,即沿此路徑由s前往v,到達v之前所到達的頂點。其中,函數(shù)ExtractMin(Q)將頂點集合Q中擁有最小d[u]值的頂點u從Q中刪除并返回u。在移動機器人導(dǎo)航應(yīng)用中,通常只需要求出起點到目標(biāo)點間的最短距離,此時可在上述經(jīng)典算法結(jié)構(gòu)中添加判斷,判斷當(dāng)前點是否為目標(biāo)點,若為目標(biāo)點,即結(jié)束。2.A*算法作為Dijkstra算法的拓展,A*算法最早由Stanford研究院的PeterHart、NilsNilsson以及BertramRaphael于1968年發(fā)表,是一種啟發(fā)式搜索算法。A*算法作為啟發(fā)式搜索算法的典型代表,在移動機器人最短路徑問題中廣泛應(yīng)用。該算法最核心的部分是合理地設(shè)計估價函數(shù),利用估價函數(shù)評估路徑中頂點的價值。當(dāng)然,如果估價值和實際目標(biāo)值接近,就認(rèn)為估價函數(shù)是合理的。A*算法可以說是一個具有完備性的最優(yōu)搜索算法,是靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法。A*算法核心表達式為式中:f(n)是節(jié)點n的綜合優(yōu)先級。當(dāng)我們選擇下一個要遍歷的節(jié)點時,總會選取綜合優(yōu)先級最高(值最小)的節(jié)點。g(n)是節(jié)點n距離起點的代價。h(n)是節(jié)點n距離終點的預(yù)計代價,也就是A*算法的啟發(fā)函數(shù)。經(jīng)典的A*算法偽代碼見算法4.9。算法中創(chuàng)建了兩個表:一個是openSet表,用于存放已

經(jīng)

生

成

但

未

訪

問

過

的

節(jié)

點;一

個

是closedSet表,用

于

存

放

已

經(jīng)

訪

問

過

的

節(jié)

點。cameFrom[n]是從起點start到當(dāng)前節(jié)點的最佳路徑上的n的父節(jié)點,gScore[n]是從n到當(dāng)前

節(jié)

點

間

最

佳

路

徑

的

代

價,d(current,neighbor)是

從

當(dāng)

前

節(jié)

點current到

鄰

節(jié)

點neighbor之間邊

上

的

權(quán)

重。tentative_gScore是

從

開

始

節(jié)

點

經(jīng)

過current到neighbor的距離。若A*算法的估價函數(shù)中啟發(fā)式代價的影響增大,則該算法在路徑規(guī)劃中的搜索方向更趨向于有目的地接近終點,因此該算法的效率更高。另一方面,A*算法的估價函數(shù)直接將實際代價和啟發(fā)式代價相加。實際上,在最佳估價函數(shù)中,實際代價和啟發(fā)式代價的權(quán)重往往是不相等的。因此,為不同環(huán)境下的啟發(fā)式代價設(shè)定一定的權(quán)重,可以改善A*算法的評估功能。4.2.2基于采樣的路徑規(guī)劃算法路徑規(guī)劃算法大致可以分為兩類,一類是基于搜索的規(guī)劃,另一類是基于采樣的規(guī)劃?；诓蓸拥囊?guī)劃算法的核心在于隨機采樣,從父節(jié)點開始,隨機在地圖上生成子節(jié)點,連接父子節(jié)點并進行碰撞檢測,如果無碰撞,就擴展該子節(jié)點。這樣不斷地隨機擴展樣本點,直到生成一條連接起點和終點的路徑。采樣規(guī)劃算法中,常用的有概率路圖法和快速擴展隨機樹法。1.概率路圖法概率路圖法是由LydiaKavraki、Jean-ClaudeLatomde提出的一種基于圖搜索的算法,是基于啟發(fā)式節(jié)點增強策略的一種路徑規(guī)劃方法,很好地解決了在高維空間中構(gòu)造有效路徑圖的困難。該算法通過在構(gòu)形空間中進行采樣、對采樣點進行碰撞檢測、測試相鄰采樣點是否能夠連接來表示路徑圖的連通性。此方法的一個優(yōu)點是,其復(fù)雜度主要依賴尋找路徑的難度,跟整個規(guī)劃場景的大小和構(gòu)形空間的維數(shù)關(guān)系不大。概率路圖法主要分為兩個階段,即學(xué)習(xí)階段和查詢階段。在學(xué)習(xí)階段,隨機采樣大量的機器人位姿點,為每個節(jié)點搜索鄰居節(jié)點并建立連接,構(gòu)建出路標(biāo)地圖;在查詢階段,根據(jù)起始點、目標(biāo)點、路標(biāo)地圖信息,采用啟發(fā)式搜索算法從路標(biāo)圖中搜索出一條可行路徑。概率路圖法可以有效避免對位姿空間中的障礙物進行精確建模,能夠有效解決復(fù)雜的運動動力學(xué)約束下的路徑規(guī)劃問題1)學(xué)習(xí)階段學(xué)習(xí)階段可以在自由空間中盡可能隨機且均勻地進行采樣,然后連接各個點,構(gòu)建出一幅路徑網(wǎng)絡(luò)圖。PRM算法學(xué)習(xí)階段是指在地圖內(nèi)進行隨機采樣,對采樣點進行碰撞檢測,從而保證采樣點不會落在地圖障礙物內(nèi),采樣點隨機均勻地分布在自由無障礙空間內(nèi)。采樣完成后通過連接各個點構(gòu)建路徑網(wǎng)絡(luò)圖。構(gòu)建網(wǎng)絡(luò)圖時,采用從一個點開始向周圍點擴散的方法,如果兩個點之間可以連接,且沒有碰到障礙物,就把路線添加到網(wǎng)絡(luò)圖中,反之則舍棄,從而構(gòu)建出整幅路徑網(wǎng)絡(luò)圖,如圖4.26所示。其中:左下角圓點代表起始點,右上角圓點代表終點,四邊形為障礙物,小點為采樣點,細線為路徑網(wǎng)絡(luò)圖中的路徑。2)查詢階段查詢階段利用學(xué)習(xí)階段建立好的無向路徑網(wǎng)絡(luò)圖,在無向路徑網(wǎng)絡(luò)圖中設(shè)置好起點和終點,根據(jù)設(shè)置好的起點和終點搜索出一條符合需求的路徑,具體可以分為以下三步:(1)把地圖中離起始點和目標(biāo)點最近的兩個點分別進行連接。(2)在網(wǎng)絡(luò)圖中搜索路徑,找到起始點到目標(biāo)點的路徑。(3)找到路徑后,通過平滑處理,優(yōu)化路徑。最終結(jié)果如圖4.26(c)所示,深色粗線為規(guī)劃出的路徑。傳統(tǒng)的PRM算法中的采樣策略是均勻采樣策略,它在整個空間中采樣的概率處處相等,采樣點數(shù)目與空間的大小成正比,狹窄通道內(nèi)的采樣點數(shù)相對其他區(qū)域較少,不能很好地連通狹窄通道兩端的區(qū)域,所以當(dāng)機器人路徑規(guī)劃需要經(jīng)過狹窄通道時,往往效率低下,因此需要改進PRM算法。常用的改進算法之一是在PRM算法中引入人工勢場。對落在威脅體內(nèi)的點施加勢場力,使之移動到自由空間內(nèi),從而增加狹窄通道內(nèi)的節(jié)點數(shù)量,在不增加采樣次

數(shù)

的

情

況

下

完

成

路

線

圖

的

構(gòu)

建;另

一

種

則

是

將PRM算

法

與

蟻

群

算

法結(jié)合。2.快速擴展隨機樹法快速擴展隨機樹法是一種在多維空間中通過遞增采樣實現(xiàn)高效率的搜索規(guī)劃的方法,其主要優(yōu)點是能夠快速地在新場景中找到一條可行路徑解。它以一個初始點作為根節(jié)點,通過對狀態(tài)空間中的采樣點進行碰撞檢測,避免了對空間的建模,能夠有效地解決高維空間和復(fù)雜約束的路徑規(guī)劃問題。逐步提高擴展樹的分辨率,當(dāng)隨機樹中的葉子節(jié)點包含目標(biāo)點或進入了目標(biāo)區(qū)域時,便可以在隨機樹中找到一條由樹節(jié)點組成的從初始點到目標(biāo)點的路徑。RRT算法的流程如下:(1)將起點作為根節(jié)點。(2)在機器人的工作空間中,隨機生成一個位姿點。(3)在位姿樹上尋找(2)中位姿點的最近鄰位姿點。(4)在(3)中的兩個位姿點之間構(gòu)造插值點,判斷它們是否與障礙物碰撞。若不碰撞,則將(2)中的位姿加入位姿樹。(5)判斷隨機位姿點是否到達目標(biāo)點附近或迭代步數(shù)到達最大值,如到達目標(biāo)點,溯源獲得路徑。圖4.27所示為RRT算法在空間中的拓展過程。圖中,機器人的起始點在右下角,目標(biāo)位置在左上角,每條線代表樹中的拓展邊,通過不斷采樣遍歷工作中的可達空間尋找目標(biāo)位置。RRT算法見算法4.10。在原始RRT算法中,將起始位置初始化為隨機樹的父節(jié)點。先初始化樹并將起始位置插入樹中。然后通過在可達空間中選擇隨機的、無碰撞的節(jié)點,嘗試將樹擴展到該位置。這個階段繼續(xù)進行,對空間進行采樣并添加新的頂點和邊,直到達到最大允許頂點數(shù),或者根據(jù)設(shè)定的終止條件找到目標(biāo)。在算法描述的函數(shù)中,Δt稱為生長節(jié)點的預(yù)定步長。生長步長對樹的擴張可以產(chǎn)生顯著的影響。若步長過小,最終得到的隨機搜索樹會有很多短枝,需要更多的節(jié)點探索可達空間并找到可行路徑,整個算法的搜索時間也會變長。若步長過大,樹會有長枝,但是擴展樹將有可能頻繁地遇到障礙物而節(jié)點更新失敗,導(dǎo)致算法重新采樣新的位置,因此在指定生長步長方面需要選擇合適的值?；诳焖贁U展隨機樹的路徑規(guī)劃算法通過對狀態(tài)空間中的采樣點進行碰撞檢測,避免了對空間的建模,能夠有效地解決高維空間和復(fù)雜約束的路徑規(guī)劃問題。該方法的特點是能夠快速有效地搜索高維空間,通過狀態(tài)空間的隨機采樣點,把搜索導(dǎo)向空白區(qū)域,從而尋找一條從起始點到目標(biāo)點的規(guī)劃路徑,適合解決多自由度機器人在復(fù)雜環(huán)境下和動態(tài)環(huán)境下的路徑規(guī)劃。但RRT算法由于隨機性太強,也有一些缺點。由于隨機樹在自由空間中的生長方向隨機,同時障礙物不斷運動,因此在動態(tài)環(huán)境中路徑規(guī)劃的穩(wěn)定性較差。而且由該算法得到的路徑不是最優(yōu)的,不會收斂到漸進最優(yōu)解。若地圖中存在可行路徑解,基于搜索的路徑規(guī)劃算法則可以通過不停地迭代計算找到最優(yōu)路徑,RRT算法的目標(biāo)則是快速找到一條可行路徑,而這條可行路徑是由單個節(jié)點連接形成的,由于冗余節(jié)點的存在和連接方式造成的曲折,該路徑一定不是最優(yōu)路徑。此外,該算法還有搜索過于平均、浪費資源時間、偏離最優(yōu)解等缺陷,這些缺陷可在應(yīng)用中改進。4.2.3現(xiàn)代智能路徑規(guī)劃算法在未知動態(tài)環(huán)境下處理路徑規(guī)劃問題時,傳統(tǒng)的算法已經(jīng)無法滿足路徑規(guī)劃的相關(guān)要求,由此仿生智能算法應(yīng)運而生,該方法在解決移動機器人路徑規(guī)劃方面表現(xiàn)出色。常用的現(xiàn)代仿生智能路徑規(guī)劃算法有蟻群算法、遺傳算法、粒子群算法等。1.蟻群算法蟻群算法是一種用來尋找優(yōu)化路徑的概率型算法。它由MarcoDorigo于1992年在他的博士論文中提出,其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。這種算法具有分布計算、信息正反饋和啟發(fā)式搜索的特征,本質(zhì)上是進化算法中的一種啟發(fā)式全局優(yōu)化算法。螞蟻在尋找食物源時,會在其經(jīng)過的路徑上釋放一種信息素,并能夠感知其他螞蟻釋放的信息素。信息素濃度的大小表征到食物源路徑的遠近,信息素濃度越高,表示對應(yīng)的路徑距離越短。通常,螞蟻會以較大的概率優(yōu)先選擇信息素濃度較高的路徑,并釋放一定量的信息素,以增強該條路徑上的信息素濃度,這樣會形成一種正反饋。伴隨信息素的揮發(fā),選擇較差路徑的螞蟻數(shù)量減少,形成負(fù)反饋。這個不斷反饋的過程使得蟻群的搜索變成一個集體的“智能”行為。最終,螞蟻能夠找到一條從巢穴到食物源的最佳路徑,即最短距離。由上述分析可知,蟻群算法最重要的參數(shù)是路徑距離和信息素,進行路徑規(guī)劃前,應(yīng)先建立算法的數(shù)學(xué)模型。假定螞蟻總數(shù)為m,螞蟻從某個節(jié)點向另一個節(jié)點移動是由路徑上的信息素濃度決定的。在t時刻,螞蟻k從節(jié)點i移動到節(jié)點j的狀態(tài)轉(zhuǎn)移概率

為式中:allowedk是螞蟻k在下一步的可選路徑節(jié)點集合;信息啟發(fā)因子α表示路徑上的信息素對螞蟻選擇該路徑的影響程度,取值越大,信息素的作用越強;β是期望啟發(fā)因子,反映下一目標(biāo)點的距離在指導(dǎo)蟻群搜索過程中的相對重要程度,β值越大,轉(zhuǎn)移概率越靠近貪心算法;τij(t)是節(jié)點i和節(jié)點j間的信息素濃度;ηij(t)是啟發(fā)函數(shù),一般取節(jié)點i和節(jié)點j間歐幾里得距離的倒數(shù),即蟻群算法是正反饋算法,隨著時間的推移,某條路徑上的信息素值會累積到很大,啟發(fā)函數(shù)的作用會減弱,直至最終消失,故需要對信息素進行更新。信息素的更新可采用實時信息素更新與路徑信息素更新兩種方式,前者是指蟻群中每只螞蟻在到達其選擇的路徑節(jié)點后,對路徑節(jié)點的信息素進行更新,更新公式如下:式中:τ0

是節(jié)點信息素的初始值;可調(diào)參數(shù)ρ∈[0,1],是信息素?fù)]發(fā)系數(shù)。路徑信息素更新是指蟻群中的所有螞蟻從起點走到目標(biāo)點,完成一次迭代搜索之后,路徑(i,j)上的信息素更新,更新公式如下:式中有三種不同的基本蟻群算法模型,此處取Ant-Cycle模型中的算式:式中:Q是信息素強度,Lk

是螞蟻k所走的路徑的總長度。蟻群算法流程如圖4.28所示。按照上述傳統(tǒng)蟻群算法雖然能夠找到機器人的全局最優(yōu)路徑,但是效率不高,迭代次數(shù)較多,收斂較慢,當(dāng)環(huán)境模型更加復(fù)雜時,算法的時間和空間復(fù)雜度都會增長,因此需要對算法進行優(yōu)化。蟻群算法的優(yōu)化大致有兩個方向:一是優(yōu)化蟻群算法中參數(shù)的設(shè)定值,包括螞蟻群體的個數(shù)、信息素重要程度因子、啟發(fā)函數(shù)重要程度因子、信息素?fù)]發(fā)因子以及信息素釋放總量等;二是將蟻群算法和其他算法相結(jié)合,取長補短,以改進蟻群算法。2.遺傳算法遺傳算法最早由美國的JohnHolland于20世紀(jì)70年代提出,該算法是根據(jù)大自然中生物體的進化規(guī)律而設(shè)計提出的,是模擬達爾文生物進化論的自然選擇和遺傳學(xué)機理的生物進化過程的計算模型,也是一種通過模擬自然進化過程搜索最優(yōu)解的方法。該算法通過數(shù)學(xué)的方式,利用計算機仿真運算,將問題的求解過程轉(zhuǎn)換成類似生物進化中染色體基因的交叉、變異等過程。在求解較為復(fù)雜的組合優(yōu)化問題時,相對一些常規(guī)的優(yōu)化算法,通常能夠較快地獲得較好的優(yōu)化結(jié)果?；具z傳算法是一種群體型操作,該操作以群體中的所有個體為對象,只使用基本遺傳算子,即選擇算子、交叉算子和變異算子,其遺傳進化操作過程簡單,容易理解,是其他一些遺傳算法的基礎(chǔ),它不僅給各種遺傳算法提供了一個基本框架,同時也具有一定的應(yīng)用價值。選擇、交叉和變異算子是遺傳算法的3個主要操作算子,它們構(gòu)成了遺傳操作,使遺傳算法具有了其他方法沒有的特點。遺傳算法主要由染色體編碼、初始化種群、適應(yīng)度函數(shù)、遺傳算子、算法終止條件等模塊組成。以下將簡要介紹遺傳算法的步驟。1)染色體編碼(1)編碼。染色體編碼關(guān)系到解空間中的解在遺傳算法中的表示形式。從問題的解到基因型的映射稱為編碼,即把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法的搜索空間的轉(zhuǎn)換方法。遺傳算法在進行搜索之前先將解空間的解表示成遺傳算法的基因型串(也就是染色體)結(jié)構(gòu)數(shù)據(jù),這些串結(jié)構(gòu)數(shù)據(jù)的不同組合就構(gòu)成了不同的點。常見的編碼方法有二進制編碼、格雷碼編碼、浮點數(shù)編碼、各參數(shù)級聯(lián)編碼、多參數(shù)交叉編碼等。幾種編碼方式的特點如下:①

二進制編碼:組成染色體的基因序列是由二進制數(shù)表示的,具有編碼解碼簡單易用,交叉變異易于程序?qū)崿F(xiàn)等特點。②

格雷編碼:兩個相鄰的數(shù)用格雷碼表示,其對應(yīng)的碼位只有一個不相同,從而可以提高算法的局部搜索能力。這是格雷編碼相比二進制編碼而言所具備的優(yōu)勢。③

浮點數(shù)編碼:將個體范圍映射到對應(yīng)浮點數(shù)區(qū)間范圍,精度可以隨浮點數(shù)區(qū)間大小而改變.以二進制編碼為例,設(shè)某一參數(shù)的取值范圍為[U1,U2],用長度為k的二進制編碼符號來表示該參數(shù),則它總共產(chǎn)生2k種不同的編碼,參數(shù)與編碼的對應(yīng)關(guān)系如下:(2)解碼。解碼即遺傳算法染色體向問題解的轉(zhuǎn)換。假設(shè)某一個體采用二進制編碼,則對應(yīng)的解碼公式為2)初始化種群設(shè)最大進化代數(shù)為T,群體大小為M,交叉概率為Pc,變異概率為Pm,隨機生成M個個體作為初始化群體p0。3)適應(yīng)度函數(shù)適應(yīng)度函數(shù)表明個體或解的優(yōu)劣性。對于不同的問題,適應(yīng)度函數(shù)的定義方式不同。根據(jù)具體問題,計算群體P(t)中各個個體的適應(yīng)度。適應(yīng)度尺度變換是指算法迭代的不同階段能夠通過適當(dāng)改變個體的適應(yīng)度大小,進而避免群體間適應(yīng)度相當(dāng)而造成的競爭減弱,導(dǎo)致種群收斂于局部最優(yōu)解。尺度變換選用的經(jīng)典方法包括線性尺度變換、乘冪尺度變換以及指數(shù)尺度變換。(1)線性尺度變換:用一個線性函數(shù)表示,其中a為比例系數(shù),b為平移系數(shù),F為變換前適應(yīng)度尺度,變換后適應(yīng)度尺度F'如下:(2)乘冪尺度變換:將原適應(yīng)度尺度F取k次冪,其中k為冪,F為轉(zhuǎn)變前適應(yīng)度尺度,F'為轉(zhuǎn)變后適應(yīng)度尺度。(3)指數(shù)尺度變換:首先將原尺度乘以系數(shù)β,然后取反,將βF作為自然底數(shù)e的冪,其中系數(shù)β的大小決定了適應(yīng)度尺度變換的強弱。4)遺傳算子遺傳算法使用以下三種遺傳算子。(1)選擇。選擇操作從舊群體中以一定的概率選擇優(yōu)良個體組成新的種群,以繁殖得到下一代個體。個體被選中的概率跟適應(yīng)度值有關(guān),個體適應(yīng)度值越高,被選中的概率越大。以輪盤賭法為例,若設(shè)種群數(shù)為M,個體i的適應(yīng)度為fi,則個體i被選取的概率為當(dāng)個體選擇的概率給定后,產(chǎn)生[0,1]之間的均勻隨機數(shù)來決定由哪個個體參加交配。若個體的選擇概率大,則有機會被多次選中,那么它的遺傳基因就會在種群中擴大;若個體的選擇概率小,則被淘汰的可能性會大。(2)交叉。交叉操作是指從種群中隨機選擇兩個個體,通過兩個染色體的交換組合,把父串的優(yōu)秀特征遺傳給子串,從而產(chǎn)生新的優(yōu)秀個體。在實際應(yīng)用中,使用率最高的是單點交叉算子,該算子在配對的染色體中隨機選擇一個交叉位置,然后在該交叉位置對配對的染色體進行基因位變換。其他交叉算子有雙點交叉或多點交叉、均勻交叉、算術(shù)交叉,讀者可自行了解。(3)變異。為了防止遺傳算法在優(yōu)化過程中陷入局部最優(yōu)解,在搜索過程中,需要對個體進行變異。在實際應(yīng)用中,主要采用單點變異(也叫位變異),即只需要對基因序列中的某一個位進行變異。以二進制編碼為例,即0變?yōu)?,而1變?yōu)?,如圖4.29所示。群體P(t)經(jīng)過選擇、交叉、變異運算后得到下一代群體P(t+1)。5)算法終止條件若t≤T,則t←t+1,轉(zhuǎn)到步驟2;否則以進化過程中所得到的具有最大適應(yīng)度的個體作為最好的解輸出,終止運算。遺傳算法流程如圖4.30。由遺傳算法流程圖可以看出,進化操作過程簡單,容易理解,它給其他各種遺傳算法提供了一個基本框架。需要注意的是:遺傳算法有4個運行參數(shù)需要預(yù)先設(shè)定,即M:種群大小。T:遺傳算法的終止進化代數(shù)。Pc:交叉概率,一般為0.4~0.99。Pm:變異概率,一般取0.001~0.1。3.粒子群算法粒子群算法(PSO)是1995年Eberhart博士和Kennedy博士一起提出的。粒子群算法是通過模擬鳥群捕食行為設(shè)計的一種群智能算法。區(qū)域內(nèi)有大大小小不同的食物源,鳥群的任務(wù)是找到最大的食物源(全局最優(yōu)解)。鳥群在整個搜尋過程中,通過相互傳遞各自位置的信息,讓其他的鳥知道食物源的位置,最終整個鳥群都能聚集在食物源周圍,即我們所說的找到了最優(yōu)解,問題收斂。粒子群算法的目標(biāo)是使所有粒子在多維超體中找到最優(yōu)解。首先給空間中的所有粒子分配初始隨機位置和初始隨機速度。然后根據(jù)每個粒子的速度、空間中已知的全局最優(yōu)位置和粒子已知的歷史最優(yōu)位置依次推進每個粒子的位置。隨著計算的推移,通過探索和利用搜索空間中已知的有利位置,粒子圍繞一個或多個最優(yōu)點聚集。該算法設(shè)計玄妙之處在于它保留了最優(yōu)全局位置和粒子已知的最優(yōu)位置兩個信息。后續(xù)的實驗發(fā)現(xiàn),保留這兩個信息對于加快收斂速度以及避免過早陷入局部最優(yōu)解都具有較好的效果。這也奠定了后續(xù)粒子群算法改進方向的基礎(chǔ)。粒子的變化公式如下:式中:c1、c2是正常數(shù),稱為加速因子,c1調(diào)節(jié)粒子飛向自身最優(yōu)位置的步長,c2調(diào)節(jié)粒子飛向全局最優(yōu)位置的步長。rand()是隨機函數(shù),生成[0,1]的隨機數(shù),以增強搜索的隨機性;vid(t)表示粒子i在第t次迭代中第d維的速度分量;xid(t)表示粒子i在第t次迭代中第d維的位置分量;pid(t)表示粒子i在第t次迭代中第d維的歷史最優(yōu)位置,即在第t次迭代后,第i個粒子(個體)搜索得到的最優(yōu)解;gd(t)表示群體在第t次迭代中第d維的歷史最優(yōu)位置,即在第t次迭代后,整個粒子群的最優(yōu)解。粒子在探索過程中可能會離開探索空間,為了避免這種情況發(fā)生,將第d維的位置變化限定在位置的最大值與最小值之間,速度變化限定在最大速度的正負(fù)邊界值之間。粒子種群隨機產(chǎn)生粒子的初始位置和速度,計算每個粒子的適應(yīng)值,然后將每個粒子的適應(yīng)值與其經(jīng)歷過的最優(yōu)位置pBesti

的適應(yīng)值進行比較,若高,則將最優(yōu)位置的適應(yīng)值替換成當(dāng)前粒子的適應(yīng)值;同理,再將每個粒子的適應(yīng)值與全局經(jīng)歷的最優(yōu)位置gBesti的適應(yīng)值作比較,之后按式(4.62)和式(4.63)進行迭代,直至找到最滿意的解。粒子群算法流程如圖4.31所示。4.2.4算法實踐———最短路徑規(guī)劃1.問題描述給定地圖由35×35的柵格組成,已知起點s和終點e,現(xiàn)要規(guī)劃一條從起點到終點的最短路徑,其中黑色圍擋為障礙物(障礙物不可跨越),如圖4.32所示。節(jié)點每次可以從當(dāng)前柵格移動至周圍八個柵格中的任一柵格,即上下左右以及斜著移動,如圖4.33所示,當(dāng)節(jié)點上下左右移動一個柵格時,距離為1,當(dāng)節(jié)點斜著移動一個柵格時,距離為

分別用Dijkstra算法和A*算法從起點s開始逐步擴展,搜索出一條從起點到終點的最短路徑。2.Dijkstra算法Dijkstra算法使用寬度優(yōu)先搜索解決帶權(quán)有向圖的最短路徑問題。它是非常典型的最短路徑算法,因此可用于求解移動機器人行進路線中的一個節(jié)點到其他所有節(jié)點的最