群智能優(yōu)化算法在路徑規(guī)劃中的應(yīng)用

張文輝，王晨宇

(1.2.桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院，廣西 桂林 541004)

0引言

在移動(dòng)機(jī)器人相關(guān)技術(shù)研究中，導(dǎo)航技術(shù)是其核心，而路徑規(guī)劃是導(dǎo)航技術(shù)研究的一個(gè)重要環(huán)節(jié)和組成部分。傳統(tǒng)的路徑規(guī)劃方法主要有人工勢(shì)場(chǎng)法，柵格法，自由空間法等，這些傳統(tǒng)的路徑規(guī)劃方法或是為局部極小值問(wèn)題無(wú)法求出最優(yōu)路徑，或是在復(fù)雜環(huán)境下求解速度過(guò)慢。此外，某些傳統(tǒng)算法在多障礙或動(dòng)態(tài)的環(huán)境下可能無(wú)法獲得可行路徑。群智能算法因?yàn)榫哂休^強(qiáng)的全局搜索能力和并行處理能力，能夠較好的適應(yīng)復(fù)雜的環(huán)境，可以用來(lái)解決傳統(tǒng)的路徑規(guī)劃算法存在的問(wèn)題。本文主要介紹了三種群智能算法以及它們?cè)诼窂揭?guī)劃中最近的相關(guān)研究，并對(duì)算法的實(shí)驗(yàn)結(jié)果進(jìn)行了對(duì)比。最后，總結(jié)了群智能算法應(yīng)用在路徑規(guī)劃中存在的問(wèn)題，提出了今后主要的研究方向。

1路徑規(guī)劃中的群智能算法

群智能(Swarm Intelligence)這一表述最早在1989年由Gerardo Beni在分子自動(dòng)機(jī)系統(tǒng)中提出。群智能算法是模仿自然界的生物群體的自治行為來(lái)構(gòu)造和優(yōu)化算法[1]。在SI系統(tǒng)中，每個(gè)成員個(gè)體根據(jù)其他成員及其環(huán)境的信息調(diào)整自己的行為，不斷地進(jìn)行簡(jiǎn)單自組織的局部行為，再通過(guò)不同個(gè)體之間的信息交流，進(jìn)而實(shí)現(xiàn)群體智能。群智能算法由于其分布性、自組織性、較強(qiáng)的魯棒性等優(yōu)點(diǎn)，已經(jīng)成功應(yīng)用在函數(shù)優(yōu)化等領(lǐng)域。因?yàn)槿褐悄芩惴ň哂休^好的魯棒性，以及并行搜索等特點(diǎn)，近年來(lái)許多學(xué)者將其應(yīng)用到優(yōu)化路徑規(guī)劃的算法之中。許多研究者借助群智能算法的這些特點(diǎn)和優(yōu)勢(shì)，對(duì)傳統(tǒng)的路徑規(guī)劃方法進(jìn)行優(yōu)化，取得了顯著的效果。許多研究人員的相關(guān)實(shí)驗(yàn)表明，將群智能算法與傳統(tǒng)路徑規(guī)劃方法結(jié)合，能夠有效提高算法的性能和效率。

1.1人工魚(yú)群算法

1.1.1 人工魚(yú)群算法簡(jiǎn)介

人工魚(yú)群算法(Artificial Fish Swarm Algorithm, AFSA)是模擬魚(yú)群在自然環(huán)境中尋找食物的群智能算法，是由我國(guó)學(xué)者李曉磊[2]提出的。在人工魚(yú)系統(tǒng)中，每條人工魚(yú)個(gè)體根據(jù)周?chē)h(huán)境的食物濃度以及周?chē)閿?shù)量來(lái)決定將要進(jìn)行的行為，主要有覓食行為、追尾行為、聚群行為。其中，覓食行為是個(gè)體向更優(yōu)解的方向前進(jìn)的個(gè)體尋優(yōu)過(guò)程，追尾行為和聚群行為是個(gè)體與周?chē)h(huán)境相互交互的過(guò)程。經(jīng)過(guò)多次迭代操作之后，大部分人工魚(yú)將會(huì)聚集在食物濃度最好的區(qū)域，即尋找到最優(yōu)解。借助人工魚(yú)群算法的較強(qiáng)的并行搜索能力和快速的全局尋優(yōu)能力，能較好地提高路徑規(guī)劃的結(jié)果。人工魚(yú)群算法的流程圖如圖1所示。

圖1 人工魚(yú)群算法流程圖

使用人工魚(yú)群算法進(jìn)行路徑規(guī)劃的實(shí)驗(yàn)中，將要進(jìn)行路徑規(guī)劃的區(qū)域通過(guò)建模方法(柵格法，自由空間法，鏈路圖法)轉(zhuǎn)化為解空間。其中，目標(biāo)點(diǎn)代表著食物濃度最高的點(diǎn)，距離目標(biāo)點(diǎn)越遠(yuǎn)的點(diǎn)食物濃度越低，多條人工魚(yú)在解空間中進(jìn)行并行搜索，通過(guò)同伴之間的相互影響，不斷向著食物濃度更高的方向前進(jìn)，從到達(dá)目標(biāo)點(diǎn)的人工魚(yú)所經(jīng)過(guò)的路徑中選擇最優(yōu)的路徑作為路徑尋優(yōu)結(jié)果。但是傳統(tǒng)的人工魚(yú)群算法存在著后期收斂速度慢，尋優(yōu)精度不高的問(wèn)題，許多研究者提出了相關(guān)的改進(jìn)方法。

1.1.2 人工魚(yú)群算法改進(jìn)路徑規(guī)劃方法

黃宜慶等[3]提出基于多策略混合人工魚(yú)群算法。處于局部極值周?chē)娜斯~(yú)個(gè)體由于視野原因無(wú)法尋找到全局極值，引入加權(quán)平均距離策略為人工魚(yú)選擇合適的視野，保證收斂速度并且防止陷入局部最優(yōu)。采用對(duì)數(shù)遞增函數(shù)作為移動(dòng)因子，能更好的定位前進(jìn)方向，保證全局收斂速度和收斂精度。在算法中增加高斯變異策略，增加了種群多樣性，能夠提高全局搜索能力。

在原始人工魚(yú)群算法中，人工魚(yú)的視野，步長(zhǎng)等參數(shù)都是固定的，固定參數(shù)會(huì)導(dǎo)致算法的適應(yīng)能力較弱。比如，步長(zhǎng)不變可能會(huì)導(dǎo)致在算法前期因?yàn)椴介L(zhǎng)過(guò)小而收斂速度慢，或是在算法后期因?yàn)椴介L(zhǎng)過(guò)大而產(chǎn)生振蕩現(xiàn)象。與采用固定參數(shù)的原始人工魚(yú)群算法相比，加入了自適應(yīng)策略的人工魚(yú)群算法能夠根據(jù)當(dāng)前搜索環(huán)境的差異，自適應(yīng)地選取適合的參數(shù)，進(jìn)而能夠提高算法的搜索性能。

由于在人工魚(yú)群算法中，最優(yōu)解會(huì)保留在公告牌中，個(gè)體間不會(huì)分享最優(yōu)解信息，這意味著它缺乏自上而下的信息交互，這會(huì)降低算法的搜索效率。Li等[4]采用混合策略，將差分進(jìn)化引入到人工魚(yú)群算法中。通過(guò)變異，交叉和選擇操作，使人工魚(yú)個(gè)體擺脫局部最優(yōu)，提高收斂速度。李君等[5]利用最速下降法替代部分覓食行為，保證后期的人工魚(yú)每次行為之后都是向適應(yīng)度較優(yōu)的方向前進(jìn)，減少了人工魚(yú)行為的隨機(jī)性，提高了算法的收斂速度。鄧濤等[6]提出了一種免疫人工魚(yú)群網(wǎng)絡(luò)算法，引入精英魚(yú)策略，簡(jiǎn)化聚群行為和追尾行為，構(gòu)造免疫人工魚(yú)群網(wǎng)絡(luò)。在減少了計(jì)算時(shí)間的同時(shí)，能有效加快跳出局部極值的速度。姚凌波等[7]借鑒反向?qū)W習(xí)中反向解的原理，將反向解作為新的引導(dǎo)點(diǎn)，調(diào)整人工魚(yú)的狀態(tài)，提高了發(fā)掘潛在較優(yōu)解的機(jī)率，避免其陷入局部最優(yōu)。

在算法后期，人工魚(yú)個(gè)體大部分集中在環(huán)境中的極值點(diǎn)附近，同伴之間的相互影響會(huì)越來(lái)越弱，所以算法的后期收斂速度變慢。以上改進(jìn)算法通過(guò)減少算法的隨機(jī)性，增加較優(yōu)個(gè)體的影響力，從而提高算法的收斂速度。

針對(duì)人工魚(yú)群算法收斂精度不高以及不容易跳出局部極值的問(wèn)題，許多學(xué)者采用將傳統(tǒng)人工魚(yú)群算法與其他智能算法相結(jié)合得到新的混合算法。周金治等[8]提出了基于差分進(jìn)化與模擬退火的人工魚(yú)群算法，采用模擬退火算法對(duì)適應(yīng)度最高的狀態(tài)進(jìn)行細(xì)化搜索，解決陷入局部最優(yōu)解的情況，引入差分策略提高搜索后期的尋優(yōu)精度，逼近最優(yōu)解。張淦[9]向傳統(tǒng)人工魚(yú)群算法中引入了螢火蟲(chóng)算法中的吸引度概念，在每次迭代過(guò)程中，最低濃度的個(gè)體會(huì)在行動(dòng)時(shí)會(huì)受到最高濃度個(gè)體的吸引，處在局部最優(yōu)解附近的人工魚(yú)個(gè)體會(huì)向著全局最優(yōu)個(gè)體所在方向前進(jìn)，能夠加快收斂速度。實(shí)驗(yàn)表明，算法的收斂速度得到了較大提升，并且具備一定的跳出局部極值的能力。

人工魚(yú)群算法的優(yōu)點(diǎn)是具有較好的并行搜索能力，并且對(duì)初始值要求不高，魯棒性較強(qiáng)，在應(yīng)用于路徑該規(guī)劃問(wèn)題中時(shí)可以在較短的時(shí)間內(nèi)尋找到接近最優(yōu)路徑的可行解。缺點(diǎn)是算后期收斂速度慢，收斂精度低的?，F(xiàn)有的研究主要對(duì)算法的參數(shù)調(diào)整，個(gè)體更新提出了改進(jìn)策略，或是將人工魚(yú)群算法與其他算法融合，彌補(bǔ)算法的不足。改進(jìn)后算法與原始人工魚(yú)群算法相比，算法性能在各方面都有較大提升。

1.2蟻群算法

1.2.1 蟻群算法簡(jiǎn)介

蟻群算法(Ant Colony Algorithm,ACA)是20世紀(jì)90年代由意大利學(xué)者M(jìn)arco Dorigo等人[10]首先提出來(lái)的一種基于種群的模擬進(jìn)化算法，是受自然界中螞蟻尋找食物過(guò)程中發(fā)現(xiàn)路徑的行為啟發(fā)而來(lái)的最早是用于解決旅行商(TSP)問(wèn)題。在蟻群系統(tǒng)中，每一個(gè)螞蟻個(gè)體在尋找食物的過(guò)程中，都會(huì)在走過(guò)的路徑留下一定濃度的信息素，而螞蟻在選擇路徑時(shí)候會(huì)更傾向于選擇信息素強(qiáng)度更大的路徑，因此人工蟻群是一種基于正反饋的分布式協(xié)作系統(tǒng)。算法流程如圖2所示。

圖2 人工蟻群算法流程圖

1.2.2 蟻群算法改進(jìn)路徑規(guī)劃方法

蟻群算法目前主要有兩種改進(jìn)方向，一種是改進(jìn)信息素的更新方式、路徑尋優(yōu)狀態(tài)選擇策略、參數(shù)調(diào)整，另一種是將蟻群算法與其他算法進(jìn)行融合。

尚曉磊[11]對(duì)信息素更新公式行改進(jìn)，結(jié)合最大—最小值螞蟻算法，將信息素的濃度劃分在一定范圍之間，當(dāng)一個(gè)種群的所有螞蟻都到達(dá)目標(biāo)柵格后，在更新信息素時(shí)，派出反向螞蟻對(duì)路徑進(jìn)行全局信息素更新，避免局部最優(yōu)，從而改善算法的執(zhí)行效率。為了提高算法的全局搜索能力，使其盡快找到最優(yōu)路徑，Yu等[12]采用信息素自適應(yīng)衰減規(guī)則，在選擇下一步時(shí)考慮信息素和距離，而不僅僅考慮信息素濃度。在蟻群算法中，信息素的更新規(guī)則影響著算法的全局搜索能力和局部搜索能力。

以上改進(jìn)算法對(duì)信息素的更新公式進(jìn)行了改進(jìn)，避免了信息素平均分配導(dǎo)致蟻群算法收斂速度下降的問(wèn)題。同時(shí)解決了螞蟻容易陷入局部最優(yōu)和滯后搜索的問(wèn)題，使得蟻群可以根據(jù)實(shí)際情況在原有路徑和新路徑之間得到更好的選擇。

針對(duì)在復(fù)雜環(huán)境中，蟻群搜索路徑效率慢，劣質(zhì)解影響算法的運(yùn)行速度的問(wèn)題，王欽釗[13]等結(jié)合人工勢(shì)場(chǎng)法對(duì)蟻群算法改進(jìn)，通過(guò)人工勢(shì)場(chǎng)計(jì)算路徑點(diǎn)的適應(yīng)值，初始化信息素矩陣來(lái)獲得高質(zhì)量的初始解，并在算法尋優(yōu)階段引入勢(shì)場(chǎng)力導(dǎo)向算子，改算法能有效降低路徑搜索時(shí)候的盲目性和隨機(jī)性，保證蟻群搜索的全局性。趙峰等[14]設(shè)計(jì)了一種實(shí)時(shí)性的，能夠動(dòng)態(tài)調(diào)整的自適應(yīng)搜索半徑蟻群算法。該算法將路徑規(guī)劃的區(qū)域劃分為若干個(gè)子區(qū)域，根據(jù)環(huán)境的復(fù)雜程度自適應(yīng)地調(diào)整搜索半徑，尋找到所有最優(yōu)局部目標(biāo)點(diǎn)，之后再尋找全局最優(yōu)目標(biāo)點(diǎn)。傳統(tǒng)的蟻群算法中，螞蟻搜索路徑只與信息素有關(guān)，目標(biāo)方向與路徑選擇沒(méi)有直接影響，算法的搜索效率比較低。柳長(zhǎng)安[15]等提出根據(jù)目標(biāo)點(diǎn)吸引機(jī)制，自適應(yīng)調(diào)整啟發(fā)函數(shù)，提高算法的收斂速度，機(jī)器人可以快速地避開(kāi)障礙物安全到達(dá)目標(biāo)點(diǎn)。

蟻群算法的路徑選擇是基于信息素的濃度的，在復(fù)雜環(huán)境中，蟻群算法在初始搜索時(shí)由于缺少信息素的參與會(huì)產(chǎn)生許多劣質(zhì)解，影響算法的運(yùn)行效率，加入初始化信息能夠提高初始解的質(zhì)量。在算法搜索時(shí)，增加目標(biāo)點(diǎn)對(duì)路徑的影響使路徑的選擇更具方向性，降低算法搜索時(shí)的隨機(jī)性和盲目性，能夠有效減少劣質(zhì)解的產(chǎn)生。實(shí)驗(yàn)表明改進(jìn)后的算法的收斂速度比傳統(tǒng)蟻群算法有了較大提升，能夠較好地適應(yīng)復(fù)雜的動(dòng)態(tài)環(huán)境。

于樹(shù)科等[16]提出了融合了蟻群算法和遺傳算法的方法，蟻群算法的反饋機(jī)制使其能夠利用系統(tǒng)中的反饋信息，進(jìn)行全局尋優(yōu)能力。而遺傳算法搜搜速度快，適合大范圍搜索。算法前期，用遺傳算法產(chǎn)生的最優(yōu)解來(lái)初始化蟻群算法的信息素。算法后期利用蟻群算法的收斂速度快來(lái)尋找最優(yōu)路徑。

個(gè)人認(rèn)為蟻群算法具有較強(qiáng)的自適應(yīng)能力和魯棒性，是一種全局搜索算法，利用信息素正反饋和信息共享機(jī)制來(lái)尋找最優(yōu)路徑是蟻群算法最大的特點(diǎn)，能夠很好地應(yīng)用于路徑規(guī)劃的問(wèn)題中。但是蟻群算法的計(jì)算量大，易陷入局部最優(yōu)解。現(xiàn)有的改進(jìn)算法主要是對(duì)蟻群算法的信息素更新方式，路徑選擇方式改進(jìn)，或是融合蟻群算法與其它群智能算法。

2.3粒子群算法

2.3.1 粒子群算法簡(jiǎn)介

算法(Particle Swarm Optimization, PSO)是Kennedy和Eberhart于1995年提出的群智能優(yōu)化算法[17]，已經(jīng)被廣泛應(yīng)用于訓(xùn)練神經(jīng)網(wǎng)絡(luò)、功能優(yōu)化和各類(lèi)基于過(guò)程的分析應(yīng)用。其基本思想是所有粒子通過(guò)適應(yīng)度函數(shù)確定飛行速度，并由速度決定粒子在解空間中的搜索行為。每個(gè)粒子都有一個(gè)由目標(biāo)函數(shù)決定的適應(yīng)值，并知道給粒子本身發(fā)現(xiàn)的適應(yīng)值最好的位置以及整個(gè)群體的粒子發(fā)現(xiàn)的最好位置。粒子通過(guò)自身經(jīng)驗(yàn)和群體經(jīng)驗(yàn)來(lái)決定下一步的行為。

在路徑尋優(yōu)算法中，每個(gè)粒子的位置代表一個(gè)可行解即有效路徑，通過(guò)不斷更新迭代最終找到評(píng)價(jià)最優(yōu)的函數(shù)值即最優(yōu)解。與其他算法相比，粒子群算法具有簡(jiǎn)單易實(shí)現(xiàn)、收斂速度快、控制參數(shù)少等優(yōu)點(diǎn)，并適用于復(fù)雜非線性問(wèn)題及離散優(yōu)化問(wèn)題。但PSO算法也是一種隨機(jī)啟發(fā)式算法，其自身存在一些不足，初始化粒子的隨機(jī)性較強(qiáng)，影響粒子群的尋優(yōu)效率和可靠性，依賴歷史最優(yōu)導(dǎo)致算法后期的局部搜索能力較差。粒子群算法的流程圖如圖3所示。

圖3 粒子群的速度和位置更新

1.3.2 粒子群算法改進(jìn)路徑規(guī)劃方法

粒子群算法由于粒子搜索的隨機(jī)性，存在著收斂速度差、局部尋優(yōu)能力弱的缺點(diǎn)，方昕[18]結(jié)合A星搜索算法的思想，初始化種群生成含有啟發(fā)信息的粒子群，引入平滑度調(diào)整粒子搜索方向，使用慣性權(quán)重來(lái)控制算法的局部搜索能力和全局搜索能力，提高了算法的收斂精度。楊景明等[19]提出一種多目標(biāo)自適應(yīng)混沌粒子群優(yōu)化算法，該算法對(duì)全局最優(yōu)粒子采用了一種新型動(dòng)態(tài)加權(quán)方法，并引入了自適應(yīng)變異策略，算法在不同時(shí)期能夠自適應(yīng)地調(diào)整參數(shù)，不僅提高了最優(yōu)解的質(zhì)量，而且提高了最優(yōu)解的均勻性。

粒子群算法依賴全局歷史最優(yōu)解和個(gè)體歷史最優(yōu)解，可以很好地利用群體信息，收斂性強(qiáng)。但是依賴歷史信息容易導(dǎo)致算法在搜索后期的種群多樣性較差，局部搜索能力不足。針對(duì)多目標(biāo)問(wèn)題要求得到的非劣解能夠盡可能分布均勻且覆蓋廣泛，張超[20]提出了混合粒子群算法與人工蜂群算法的混合算法，兼顧了收斂性能和多樣性。為了減弱個(gè)體對(duì)歷史最優(yōu)解的依賴，自適應(yīng)的調(diào)整每個(gè)個(gè)體歷史最優(yōu)解的加速因子，使個(gè)體歷史最優(yōu)解的影響逐漸降低，讓更加優(yōu)秀的全局歷史最優(yōu)解發(fā)揮更大的作用。

針對(duì)粒子群算法過(guò)早收斂問(wèn)題文獻(xiàn)，劉潔[21]提出了自適應(yīng)權(quán)重策略。在粒子群算法中，慣性權(quán)重較大時(shí)會(huì)提高算法的全局搜索能力，慣性權(quán)重較小的時(shí)候算法偏向于局部搜索。將利用個(gè)體粒子的速度和群體粒子的離散度來(lái)動(dòng)態(tài)地調(diào)整慣性權(quán)重，能夠避免陷入局部最優(yōu)解。為了提高算法的準(zhǔn)確性和穩(wěn)定性，在位置更新中引入了自然選擇方法，保持種群多樣性。實(shí)驗(yàn)證明，改進(jìn)后的算法有效地提升了收斂速度、加強(qiáng)了算法的全局搜索能力。

Guo等[22]根據(jù)移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題的總體設(shè)計(jì)，提出了模糊神經(jīng)網(wǎng)絡(luò)的控制方法，該方法結(jié)合了模糊控制和神經(jīng)網(wǎng)絡(luò)。改進(jìn)的粒子群算法用于調(diào)整模糊神經(jīng)網(wǎng)絡(luò)的參數(shù)，以更好地實(shí)現(xiàn)移動(dòng)機(jī)器人的路徑規(guī)劃。神經(jīng)網(wǎng)絡(luò)具有較強(qiáng)的容錯(cuò)性和自適應(yīng)學(xué)習(xí)的能力，能夠有效地分析和融合環(huán)境中的信息。模糊控制具有邏輯推理的能力，在處理結(jié)構(gòu)化知識(shí)方面更為有效。該算法結(jié)合了神經(jīng)網(wǎng)絡(luò)與模糊控制的優(yōu)點(diǎn)，融合神經(jīng)網(wǎng)絡(luò)的自學(xué)習(xí)能力和模糊控制的模糊推理能力，并利用粒子群算法對(duì)模糊神經(jīng)網(wǎng)絡(luò)的參數(shù)進(jìn)行優(yōu)化，增加了算法的搜索精度。

粒子群算法具有簡(jiǎn)單易實(shí)現(xiàn)，收斂速度快，適應(yīng)性強(qiáng)等優(yōu)點(diǎn)。但是粒子群算法同其他群智能算法一樣，存在著易陷入局部最優(yōu)的問(wèn)題。目前的改進(jìn)放方法對(duì)粒子群的更新策略、參數(shù)調(diào)整進(jìn)行了改進(jìn)，或者是利用粒子群算法的優(yōu)勢(shì)將粒子群算法與神經(jīng)網(wǎng)絡(luò)或者其他智能算法相融合。

2群智能算法性能比較

每種群智能算法在應(yīng)用到路徑規(guī)劃的時(shí)候都有其優(yōu)點(diǎn)，但也會(huì)存在不足。存在的比較大問(wèn)題是結(jié)果易陷入局部最優(yōu)，收斂速度慢，收斂精度低等問(wèn)題?？偨Y(jié)結(jié)果如表1所示。

表1 各群智能算法優(yōu)化路徑規(guī)劃存在的優(yōu)缺點(diǎn)比較

人工魚(yú)群算法在應(yīng)用到路徑規(guī)劃時(shí)，具有收斂速度快，對(duì)初始參數(shù)不敏感，魯棒性高，較強(qiáng)的全局搜索能力等優(yōu)點(diǎn)。但是算法后期的搜索速度慢，而且人工魚(yú)容易在局部最優(yōu)解附近徘徊，導(dǎo)致收斂精度下降。目前已應(yīng)用于組合優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、約束優(yōu)化、電力系統(tǒng)負(fù)荷預(yù)測(cè)、參數(shù)估計(jì)、多目標(biāo)優(yōu)化等題，并且取得了良好的效果。

人工蟻群算法本身就是模仿螞蟻尋找路徑而來(lái)，在進(jìn)行路徑的時(shí)候具有正反饋，分布式協(xié)作和信息共享的特點(diǎn)。但是蟻群算法的計(jì)算時(shí)間比較長(zhǎng)，而且依賴于信息素的影響，可能當(dāng)出現(xiàn)較優(yōu)路徑的時(shí)候由于信息素含量的影響出現(xiàn)停滯現(xiàn)象。蟻群算法最初用于解決旅行商問(wèn)題。已經(jīng)陸續(xù)滲透到其他領(lǐng)域中，如二次分配問(wèn)題、大規(guī)模集成電路設(shè)計(jì)、通訊網(wǎng)絡(luò)中的路由問(wèn)題以及負(fù)載平衡問(wèn)題、車(chē)輛調(diào)度問(wèn)題、數(shù)據(jù)聚類(lèi)問(wèn)題、區(qū)域性無(wú)線電頻率自動(dòng)分配問(wèn)題等。

粒子群算法的參數(shù)較少，易于實(shí)現(xiàn)，收斂精度高，算法早期的收斂速度快，但是局部搜索能力差，后期搜索速度慢。粒子群算法最早應(yīng)用于訓(xùn)練人工神經(jīng)網(wǎng)絡(luò)，隨后，粒子群算法被廣泛地應(yīng)用于函數(shù)優(yōu)化、 約束優(yōu)化、 模式分類(lèi)、機(jī)器人路徑規(guī)劃、 信號(hào)處理、模式識(shí)別等工程領(lǐng)域。

3結(jié)束語(yǔ)

本文主要從群智能算法對(duì)路徑規(guī)劃研究成果進(jìn)行了論述。傳統(tǒng)的路規(guī)劃方法由于計(jì)算時(shí)間長(zhǎng)，處理復(fù)雜環(huán)境能力弱等問(wèn)題并不能很好的得到一條最優(yōu)路徑。群智能優(yōu)化算法因?yàn)槠毡榫哂蟹植夹裕越M織性，較強(qiáng)的魯棒性的優(yōu)點(diǎn)，被廣泛地應(yīng)用在路徑規(guī)劃領(lǐng)域，并取得了一定的成果，但是仍有一些問(wèn)題需要解決。比如，改進(jìn)后算法雖然在一定條件下避免了陷入局部最優(yōu)，或是增強(qiáng)了跳出局部極值的能力，但是依然存在著陷入局部最優(yōu)的可能性。有的算法收斂速度較快，但是會(huì)發(fā)生早熟現(xiàn)象，影響收斂精度。

對(duì)參數(shù)的調(diào)整能夠改變算法的性能，如何設(shè)置最優(yōu)參數(shù)適應(yīng)不同的環(huán)境也是一種優(yōu)化問(wèn)題。路徑規(guī)劃算法應(yīng)用場(chǎng)景不斷拓展，為了滿足多約束條件的目標(biāo)優(yōu)化，將多種算法進(jìn)行融合是一種主要的方法。目前的路徑規(guī)劃研究多是在已知靜態(tài)的二維環(huán)境下進(jìn)行實(shí)驗(yàn)，隨著技術(shù)領(lǐng)域的不斷拓展，復(fù)雜三維環(huán)境下的動(dòng)態(tài)路徑規(guī)劃是未來(lái)研究的趨勢(shì)。