基于粒子群遺傳算法的泊車系統(tǒng)路徑規(guī)劃研究

王 輝，朱龍彪，朱天成，陳紅艷，邵小江，朱志慧

（1.南通大學(xué)機械工程學(xué)院，江蘇南通　226019；2.中國聯(lián)合通信網(wǎng)絡(luò)有限公司江蘇省分公司，江蘇南京　210024；3.江蘇金冠立體停車股份有限公司，江蘇南通　226003）

基于粒子群遺傳算法的泊車系統(tǒng)路徑規(guī)劃研究

王 輝1，朱龍彪1，朱天成2，陳紅艷1，邵小江1，朱志慧3

（1.南通大學(xué)機械工程學(xué)院，江蘇南通226019；2.中國聯(lián)合通信網(wǎng)絡(luò)有限公司江蘇省分公司，江蘇南京210024；3.江蘇金冠立體停車股份有限公司，江蘇南通226003）

針對智能停車庫自動導(dǎo)引運輸車（automated guided vehicle，AGV）存取車路徑規(guī)劃問題，提出了一種基于粒子群和遺傳算法的動態(tài)自適應(yīng)混合算法.在標(biāo)準(zhǔn)粒子群算法和遺傳算法的基礎(chǔ)上，通過引入動態(tài)自適應(yīng)調(diào)整策略分別對慣性權(quán)重系數(shù)、學(xué)習(xí)因子以及交叉變異概率公式進行了優(yōu)化.在進化初期，通過在慣性權(quán)重系數(shù)和學(xué)習(xí)因子之間建立動態(tài)聯(lián)動關(guān)系來實現(xiàn)對粒子速度和位置的實時有效更新；在進化后期，通過引入自適應(yīng)遺傳算法的交叉、變異操作來增強混合算法的全局搜索能力，提高算法的進化速度和收斂精度.為驗證混合算法的可行性和有效性，選用MATLAB軟件對其進行仿真測試.仿真測試結(jié)果顯示，與禁忌搜索算法、蟻群算法以及遺傳算法相比，混合算法表現(xiàn)出較強的全局搜索能力和較好的收斂性能，表明混合算法可行和有效.

粒子群算法；遺傳算法；泊車系統(tǒng)；AGV；路徑規(guī)劃

汽車保有量的急劇增加伴隨著泊車位供應(yīng)不足與泊車位需求增長過快的過剩矛盾日益凸顯，造成了城市交通擁擠、停車困難等社會問題，成為制約城市經(jīng)濟和社會發(fā)展的瓶頸.而基于AGV平面移動式智能停車庫的出現(xiàn)，則很好地解決了這一難題.與傳統(tǒng)平面車庫和機械式立體車庫相比，該智能車庫具有停車占地面積少、有效存車數(shù)量多、車輛存取自動化程度高、性價比高以及安全可靠性高等優(yōu)點，可實現(xiàn)無人自動存取車、AGV自動充電以及車庫自動計費等諸多功能［1］.研究平面移動式智能停車庫的核心是解決AGV存取車路徑規(guī)劃問題.目前，針對路徑規(guī)劃問題，國內(nèi)外相關(guān)學(xué)者已做了大量研究工作，并相繼提出了禁忌搜索算法［2］、模擬退火算法［3］、遺傳算法［4］、蟻群算法［5］以及粒子群算法［6］等.

粒子群算法（PSO）是由Eberhart和Kennedy于1995年基于鳥群捕食行為而提出的一種群體智能優(yōu)化算法.該算法保留了種群的全局搜索策略，可通過速度—位移模型和自身記憶特性實現(xiàn)動態(tài)跟蹤及實時調(diào)整搜索策略等功能，具有算法設(shè)計簡單、易于實現(xiàn)、需調(diào)整參數(shù)較少、收斂速度快、全局搜索能力強等優(yōu)點，一經(jīng)提出便引起了學(xué)者的關(guān)注和研究，并在函數(shù)優(yōu)化、路徑規(guī)劃、神經(jīng)網(wǎng)絡(luò)訓(xùn)練以及自動控制等領(lǐng)域得到了廣泛應(yīng)用.樊明等［4］通過建立慣性權(quán)重系數(shù)、認知系數(shù)與收縮因子三者之間的聯(lián)動關(guān)系和引入遺傳算法的交叉與變異操作對粒子群算法進行了改進，并將改進算法用于智能存取系統(tǒng)，解決了存取系統(tǒng)的路徑優(yōu)化問題；王波等［6］通過引入遺傳算法的交叉與變異操作對粒子群算法進行了改進，并將改進的粒子群算法用于云計算任務(wù)調(diào)度中，通過仿真測試驗證了算法的可行性和有效性；喬俊飛等［7］提出采用改進的動態(tài)自適應(yīng)粒子群算法解決給水管網(wǎng)優(yōu)化問題，仿真試驗結(jié)果顯示改進算法具有較強的全局搜索能力和較快的收斂速度.

遺傳算法是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索優(yōu)化方法，該算法借鑒了達爾文的進化論和孟德爾的遺傳學(xué)說，具有易于實現(xiàn)、可處理復(fù)雜問題、可實現(xiàn)并行搜索、算法效率高以及魯棒性強等特點，被廣泛用于解決圖像處理、人工智能、路徑規(guī)劃以及生產(chǎn)調(diào)度等領(lǐng)域的問題.Imen等［5］針對機器人在靜態(tài)環(huán)境中的路徑規(guī)劃問題，提出將蟻群算法與遺傳算法進行有效結(jié)合，并通過仿真測試驗證了算法的可行性和有效性；雷偉軍等［8］提出將改進的遺傳算法用于解決多模型加工路徑規(guī)劃問題，縮短了多模型的整體加工路徑長度；徐翔等［9］通過引入新的交叉變異概率公式對基本遺傳算法進行了改進，然后將改進算法運用到智能體路徑規(guī)劃中，仿真結(jié)果顯示改進算法的收斂性能和全局搜索能力都有明顯提高.

針對智能停車庫AGV存取車路徑規(guī)劃問題，結(jié)合粒子群和遺傳算法的優(yōu)點，提出了一種融合粒子群和遺傳算法的自適應(yīng)混合算法（APSOGAA）.該混合算法在標(biāo)準(zhǔn)粒子群算法和遺傳算法的基礎(chǔ)上，通過引入動態(tài)自適應(yīng)調(diào)整策略分別對慣性權(quán)重系數(shù)、學(xué)習(xí)因子以及交叉變異概率公式來進行優(yōu)化.進化初期，為平衡算法全局和局部搜索能力，提高搜索效率和改善收斂性能，通過在慣性權(quán)重系數(shù)和學(xué)習(xí)因子之間建立動態(tài)聯(lián)動關(guān)系，實現(xiàn)對粒子速度和位置的實時有效更新；進化后期，為防止粒子陷入局部最優(yōu)，出現(xiàn)早熟問題，通過引入自適應(yīng)遺傳算法的交叉、變異操作來增強粒子多樣性，拓展粒子解空間，增強算法全局搜索能力，提高算法進化速度和收斂精度.為驗證混合算法的可行性和有效性，最后選用MATLAB軟件對其進行了仿真測試.

1　問題描述及數(shù)學(xué)模型

當(dāng)AGV從預(yù)存停車位出發(fā)到目標(biāo)停車位取出車輛，然后再將其運回到預(yù)存車位，這個過程可簡化為TSP問題.TSP作為優(yōu)化組合領(lǐng)域的經(jīng)典NP難題，備受國內(nèi)外學(xué)者關(guān)注和研究.Basu［2］提出用禁忌搜索算法解決TSP問題；Wang等［3］提出用改進的模擬退火算法解決TSP問題；Aditi等［10］提出用粒子群蟻群混合算法來解決TSP問題.此處AGV路徑規(guī)劃的TSP問題可定義為：在已知AGV可行路徑節(jié)點的前提下，AGV從預(yù)存停車位出發(fā)，遍歷各個可行路徑節(jié)點1次，然后將目標(biāo)車輛運送至預(yù)存停車位，在此過程中確定一條可使AGV運行距離最短的可行路徑.數(shù)學(xué)模型可描述為：根據(jù)可行路徑節(jié)點坐標(biāo)，建立賦權(quán)圖G=（Q，E），其中，Q表示節(jié)點集合，Q=｛1，2，…，n｝，E表示各節(jié)點間形成的可行路徑，dij表示i，j節(jié)點間的歐式距離，可按照式（1）計算得到，對于不連通節(jié)點間的權(quán)值可賦值inf（無窮大）.數(shù)學(xué)模型可表示為：

式中：i，j表示可行路徑上的節(jié)點；D表示整個循環(huán)路徑總長度.

2　粒子群算法設(shè)計

2.1基本粒子群算法

粒子群算法（PSO）是一種基于迭代搜尋最優(yōu)解的隨機優(yōu)化技術(shù)，其基本思想是通過群體中個體間的協(xié)作和信息共享來尋找最優(yōu)解［11］.在PSO算法中，首先將問題的可行解空間初始化為一群粒子，每個優(yōu)化問題的潛在最優(yōu)解均可視為搜索空間中的一個粒子，通過適應(yīng)度函數(shù)評價種群中粒子的優(yōu)劣，對比粒子當(dāng)前適應(yīng)度值及其所經(jīng)過的個體極值點pbest和全局極值點pgbest的適應(yīng)度值，更新粒子當(dāng)前最優(yōu)個體極值點和全局最優(yōu)極值點，然后按照方程式（3）和（4）分別對粒子的速度和位置進行更新，最終實現(xiàn)粒子在可行解空間中的尋優(yōu).

在d維搜索空間中，粒子i的位置和速度可分別表示為Xi=｛xi1，xi2，…，xin｝和Vi=｛vi1，vi2，…，vin｝.粒子i的速度和位置可按照式（3）和式（4）進行更新：

式中：j表示粒子的搜索空間，i表示當(dāng)前粒子；參數(shù)c1和c2表示學(xué)習(xí)因子；r1和r2為隨機數(shù)，r1∈［0，1］，r2∈［0，1］；xid和vid分別表示粒子i在d維的當(dāng)前位置和當(dāng)前速度；pbest為粒子i在d維的個體極值點位置，pgbest為當(dāng)前整個粒子群在d維中的全局極值點位置.

2.2基本遺傳算法

遺傳算法是由美國Holland教授借鑒生物界進化規(guī)律而提出的一種啟發(fā)式隨機搜索方法，主要由編碼、選擇、交叉、變異以及解碼操作組成.該算法模擬了自然選擇和遺傳中發(fā)生的復(fù)制、交叉和變異等現(xiàn)象，從任意初始種群出發(fā)，通過隨機選擇、交叉和變異等操作，按照“適者生存、優(yōu)勝劣汰”的進化原則，產(chǎn)生一群更適應(yīng)環(huán)境的個體.優(yōu)化群體經(jīng)過多代繁衍進化，最后收斂到一群最適應(yīng)環(huán)境的個體，通過對優(yōu)化個體解碼，可得到問題的最優(yōu)解或次最優(yōu)解.

3　粒子群遺傳算法設(shè)計

在AGV存取車路徑規(guī)劃中，選用標(biāo)準(zhǔn)粒子群算法和遺傳算法雖然能夠使AGV規(guī)劃出一條從起始位置到目標(biāo)位置的強魯棒性優(yōu)化路徑，但依然存在諸多不足，主要表現(xiàn)為收斂速度慢、搜索效率較低、易出現(xiàn)早熟或停滯以及易陷入局部最優(yōu)等.針對上述問題，通過引入動態(tài)自適應(yīng)調(diào)整策略，設(shè)計了一種動態(tài)自適應(yīng)混合算法.

3.1慣性權(quán)重優(yōu)化

由標(biāo)準(zhǔn)粒子群算法中粒子速度更新方程可知，粒子的飛行速度直接影響著算法全局搜索能力.粒子飛行速度越大，則搜索能力就越強，其飛到全局最優(yōu)解區(qū)域的可能性就越大.但當(dāng)飛行速度過大時，粒子極易飛越最優(yōu)解而轉(zhuǎn)向其他區(qū)域；當(dāng)飛行速度過小時，粒子會因無法找到解空間的最佳位置而陷入局部最優(yōu).為對粒子飛行速度進行有效控制和約束，Shi等在標(biāo)準(zhǔn)粒子算法模型中引入了慣性權(quán)重系數(shù)ω，粒子的速度和位置更新公式可更改為［12］：

慣性權(quán)重系數(shù)ω是PSO算法中一個極為重要的控制參數(shù)，直接影響著粒子的搜索能力和算法的收斂速度.較大的慣性權(quán)重系數(shù)有利于增強算法的全局搜索能力和提高收斂速度，但會降低算法局部搜索能力且不易得到精確全局最優(yōu)解；較小的慣性權(quán)重系數(shù)有利于提高收斂精度和得到精確最優(yōu)解，但會削弱全局搜索能力和降低收斂速度.因此，選擇合理的慣性權(quán)重系數(shù)ω對增強算法搜索能力和提高收斂速度是極為重要的.為平衡粒子群算法的全局和局部搜索能力，選用非線性動態(tài)慣性權(quán)重對粒子群算法進行了改進，更改后的權(quán)重系數(shù)公式如下［13］：

式中：ωmax為ω的最大值，ωmin為ω的最小值，一般取ωmax=0.9，ωmin=0.4；f表示粒子當(dāng)前的適應(yīng)度值，favg和fmin分別表示當(dāng)前所有粒子的平均適應(yīng)度值和最小適應(yīng)度值.

3.2學(xué)習(xí)因子優(yōu)化

學(xué)習(xí)因子c1和c2是PSO算法的另外一組重要參數(shù)，決定了粒子自我認知和社會認知對粒子運行軌跡的影響，反映了群體中各粒子間的信息交流［14］.當(dāng)學(xué)習(xí)因子c1取較大值時，過多的粒子會聚集在局部區(qū)域內(nèi)徘徊；當(dāng)學(xué)習(xí)因子c2取較大值時，會促使粒子在局部最小值范圍內(nèi)過早收斂.因此，選擇合適的學(xué)習(xí)因子對增強算法搜索能力和提高收斂精度與速度極為重要.在PSO算法中，學(xué)習(xí)因子一般為常數(shù)，取值通常為c1=c2=2，但在實際應(yīng)用中，學(xué)習(xí)因子也存在其他取值方式，常見的有同步變化和異步變化，此處采用異步變化的學(xué)習(xí)因子對PSO算法進行改進，以實現(xiàn)對學(xué)習(xí)因子的動態(tài)調(diào)整.更改后的學(xué)習(xí)因子公式如下［15］：

式中：參數(shù)c1，s和c2，s分別表示學(xué)習(xí)因子c1和c2的初始值，c1，e和c2，e分別表示學(xué)習(xí)因子c1和c2的迭代終值；t表示當(dāng)前迭代次數(shù)，tmax表示最大迭代次數(shù).多數(shù)情況下，上式中的參數(shù)進行如下設(shè)置可取得較好效果：c1，s=c2，s=2.5，c1，e=c2，e=0.5.

由更改后的學(xué)習(xí)因子公式和速度與位置更新公式分析可知：在算法進化初期，粒子具有較強的自我學(xué)習(xí)能力和較弱的社會學(xué)習(xí)能力，有利于強化粒子全局搜索能力；在進化后期，粒子具有較強的社會學(xué)習(xí)能力和較弱的自我學(xué)習(xí)能力，有利于提高粒子的收斂速度和收斂精度，確保粒子能夠收斂到全局最優(yōu).

3.3交叉和變異概率調(diào)整公式

在算法進化后期，為防止粒子陷入局部最優(yōu)及出現(xiàn)早熟問題，此處通過引入自適應(yīng)遺傳算法的交叉、變異操作來增強PSO算法的全局搜索能力，提高算法的收斂速度和收斂精度.

交叉、變異操作是產(chǎn)生新個體的關(guān)鍵環(huán)節(jié)，分別影響著遺傳算法的全局和局部搜索能力，通常情況下交叉概率Pc取較大值，變異概率Pm取較小值.對于交叉概率Pc，取值越大，則產(chǎn)生新個體的速度就越快，但過大的Pc會使得群體優(yōu)良模式被破壞的可能性增大，致使具有高適應(yīng)度的優(yōu)良個體被破壞；Pc過小則會使得新個體產(chǎn)生速度變得緩慢，致使搜索過程停滯不前，影響算法的全局搜索能力.對于變異概率Pm，若取值過小，則不利于產(chǎn)生新個體結(jié)構(gòu)，且算法易出現(xiàn)早熟；若取值過大，則會使得群體中具有較高適應(yīng)度的個體被破壞的可能性增大，導(dǎo)致算法性能下降.因此，選擇合理的交叉、變異概率對增強算法搜索能力和改善算法收斂性能有著極為重要的作用.

針對不同問題，Pc和Pm的確定工作異常繁瑣、復(fù)雜，而且也很難找到理想通用的Pc和Pm.另外，固定的Pc和Pm無法保證算法在優(yōu)化空間中搜索到全局最優(yōu)解，也很難適應(yīng)搜尋過程中不同取值需求.為此，Srinivas等人［16］提出了一種自適應(yīng)遺傳算法，在該算法中，Pc和Pm可根據(jù)適應(yīng)度變化而自行調(diào)整.但在個體適應(yīng)度和最大適應(yīng)度取相同值的情況下，交叉、變異概率取值同時為零，易使算法出現(xiàn)早熟收斂，陷入局部最優(yōu)解.基于此，對Srinivas提出的自適應(yīng)算法作進一步改進，將群體中具有最大適應(yīng)度的個體交叉、變異概率分別提高到Pc2和Pm2，以確保具有最大適應(yīng)度的個體的交叉、變異概率在進化過程中不出現(xiàn)零值，避免算法出現(xiàn)停滯問題.在進化過程中，為確保每代優(yōu)良個體不被破壞，可采用精英選擇策略，將每次迭代產(chǎn)生的優(yōu)良個體直接復(fù)制到下一代.改進后的交叉、變異概率公式如下［17］：

式中：參數(shù)Pc1和Pm1分別表示交叉概率和變異概率的最大值；參數(shù)fmax和favg分別表示粒子群中最大適應(yīng)度值和各次迭代的平均適應(yīng)度值；參數(shù)f′和f分別表示要交叉?zhèn)€體中較大的適應(yīng)度值和要變異個體的適應(yīng)度值.多數(shù)情況下，上式中的參數(shù)進行如下設(shè)置可取得較好效果：Pc1=0.9，Pc2=0.6，Pm1=0.1，Pm2=0.001.

3.4算法具體實施步驟

Step 1：建立AGV運行環(huán)境模型，確定可行路徑上各節(jié)點坐標(biāo)位置，并對各節(jié)點坐標(biāo)進行編號；

Step 2：初始化算法各參數(shù)，以整數(shù)方式對粒子個體進行編碼，隨機生成一個規(guī)模為m的粒子群，設(shè)定粒子的初始位置和初始速度；

Step 3：由適應(yīng)度函數(shù)方程式計算出各粒子適應(yīng)度值，對比分析各粒子適應(yīng)度值，并根據(jù)適應(yīng)度值優(yōu)劣來更新粒子的個體最佳位置pbest和全局最佳位置pgbest；

Step 4：根據(jù)式（7）、（8）及式（9）分別對慣性權(quán)重系數(shù)ω和學(xué)習(xí)因子c1及c2進行更新；

Step 5：根據(jù)式（5）和式（6）更新粒子的速度和位置；

Step 6：由適應(yīng)度函數(shù)方程式計算出各粒子適應(yīng)度值，并根據(jù)適應(yīng)度值優(yōu)劣來更新粒子的個體最佳位置pbest和全局最佳位置pgbest；

Step 7：根據(jù)適應(yīng)度函數(shù)計算各粒子適應(yīng)度值，對比各粒子適應(yīng)度值，按照交叉概率式（10）選擇需要交叉的個體和群體，完成個體最優(yōu)交叉和群體最優(yōu)交叉操作；

Step 8：按照式（11），粒子進行變異操作，產(chǎn)生新粒子；

Step 9：由適應(yīng)度函數(shù)方程式計算出新粒子適應(yīng)度值，并根據(jù)適應(yīng)度值優(yōu)劣來更新粒子的個體最佳位置pbest和全局最佳位置pgbest；

Step 10：判斷算法是否滿足終止條件，若是，則算法結(jié)束，輸出結(jié)果，否則轉(zhuǎn)至Step 3.

4　仿真及分析

為驗證算法在AGV路徑規(guī)劃中的合理性和有效性，以可行路徑上30個坐標(biāo)點的路徑尋優(yōu)為例，算法參數(shù)設(shè)置如下：在禁忌搜索算法中，禁忌長度為50，候選解為200，最大步數(shù)為500；蟻群算法中，螞蟻數(shù)量為40，α=1，β=5，ρ=0.1，最大迭代次數(shù)為500；遺傳算法中，種群規(guī)模為500，Pc=0.9，Pm=0.05，最大迭代次數(shù)為500；混合算法中，種群規(guī)模為500，最大迭代次數(shù)為500.在MATLAB環(huán)境下分別對禁忌搜索算法、蟻群算法、遺傳算法及混合算法進行仿真測試.通過對比上述算法仿真數(shù)據(jù)，來驗證混合算法的性能.仿真結(jié)果如圖1至圖4所示.

圖1　禁忌搜索算法路徑軌跡迭代圖Fig.1 Path trajectory iteration graph of TSA

圖2　蟻群算法路徑軌跡迭代圖Fig.2 Path trajectory iteration graph of ACO

圖3　遺傳算法路徑軌跡迭代圖Fig.3 Path trajectory iteration graph of GA

圖4　混合算法路徑軌跡迭代圖Fig.4 Path trajectory iteration graph of hybrid algorithm

圖1至圖4所示為AGV在各算法下的存取車路徑運行軌跡迭代圖，圖中虛線代表AGV存取車路徑運行軌跡曲線，實線代表各算法下AGV的迭代路徑變化曲線.由圖可知，在遍歷可行路徑各節(jié)點的前提下，根據(jù)當(dāng)前位置以及存取車位置，AGV運用上述算法均可快速搜索到一條自起點至終點的優(yōu)化路徑.

對比表1數(shù)據(jù)，結(jié)合圖中所示的AGV運行軌跡可知，AGV采用禁忌搜索算法規(guī)劃的路徑長度為852.59m，蟻群算法為860.865 2m，遺傳算法為855.266 6m，混合算法為847.492 3m，在路徑長度方面，混合算法比禁忌搜素算法減少了5.097 7m，比蟻群算法減少了13.372 9m，比遺傳算法減少了7.774 3m.在迭代次數(shù)方面，禁忌搜索算法在第329代開始收斂，蟻群算法為第80代，遺傳算法為第127代，混合算法為第76代，很顯然，混合算法具有較快的收斂速度.綜上分析可知，混合算法在搜索路徑長度和收斂速度方面都是最優(yōu)的，表明混合算法具有較快搜索速度、較高搜索效率的優(yōu)點.

表1　各算法下AGV路徑規(guī)劃結(jié)果Table 1 The results of AGV path planning under the condition of above algorithms

5　結(jié) 論

針對AGV存取車路徑規(guī)劃問題，有效地將粒子群算法和遺傳算法進行了融合，在標(biāo)準(zhǔn)粒子群算法和遺傳算法的基礎(chǔ)上，通過引入動態(tài)自適應(yīng)調(diào)整策略，設(shè)計了一種動態(tài)自適應(yīng)混合算法，并在MATLAB環(huán)境下對該混合算法進行了仿真測試.由仿真測試結(jié)果可得如下結(jié)論：在遍歷可行路徑各節(jié)點的前提下，根據(jù)AGV自身當(dāng)前位置，運用文中所提算法均可快速搜索到一條自起點至終點的無交叉優(yōu)化路徑；與禁忌搜索算法、蟻群算法以及遺傳算法相比，混合算法規(guī)劃的路徑長度最短；路徑迭代圖顯示混合算法具有較好收斂性能、較快搜索速度、較高搜索效率以及較短搜索路徑長度的優(yōu)點.

［1］CHARLES E B，BRIAN G P，CHRISTIAN A Y，et al. Automated automotive vehicle parking/storage system：US12855017［P］.2014-05-27.

［2］BASU S.Tabu search implementation on traveling salesman problem and its variations：a literature survey［J］. American Journal of Operations Research，2012，2（2）：163-173.

［3］WANG Yong，TIAN De，LI Yu-hua.An improved simulated annealing algorithm for travelling salesman problem［J］.International Journal of Online Engineering，2013，9（4）：28-32.

［4］樊明，郭藝，贠超，等.基于自適應(yīng)混合算法的智能存取系統(tǒng)動態(tài)路徑規(guī)劃［J］.系統(tǒng)仿真學(xué)報，2013，25（7）：1543-1548.

FAN Ming，GUO Yi，YUN Chao，et al.Adaptive hybrid algorithm for dynamic path planning problem of intelligent access system［J］.Journal of System Simulation，2013，25（7）：1543-1548.

［5］IMEN C，ANIS K，SAHAR T，et al.Smartpath：an efficient hybrid ACO-GA algorithm for solving the global path planning problem of mobile robots［J］.International Journal of Advanced Robotic Systems，2014，11（1）：1-15.

［6］王波，張曉磊.基于粒子群遺傳算法的云計算任務(wù)調(diào)度研究［J］.計算機工程與應(yīng)用，2015，51（6）：84-88.

WANG Bo，ZHANG Xiao-lei.Task scheduling algorithm based on particle swarm optimization genetic algorithms in cloud computing environment［J］.Computer Engineering and Applications，2015，51（6）：84-88.

［7］喬俊飛，王超，劉昌芬.基于改進的自適應(yīng)粒子群算法的給水管網(wǎng)優(yōu)化設(shè)計［J］.北京工業(yè)大學(xué)學(xué)報，2014，40（7）：1035-1040.

QIAO Jun-fei，WANG Chao，LIU Chang-fen.Optimal design of a water supply system based on improved selfadaptive particle swarm algorithm［J］.Journal of Beijing University of Technology，2014，40（7）：1035-1040.

［8］雷偉軍，程筱勝，戴寧，等.基于改進遺傳算法的多模型加工路徑規(guī)劃［J］.機械工程學(xué)報，2014，50（11）：153-161.

LEI Wei-jun，CHENG Xiao-sheng，DAI Ning，et al. Multi-model machining path planning based on improved genetic algorithm［J］.Journal of Mechanical Engineering，2014，50（11）：153-161.

［9］徐翔，梁瑞仕，楊會志.基于改進遺傳算法的智能體路徑規(guī)劃仿真［J］.計算機仿真，2014，31（6）：357-361.

XU Xiang，LIANG Rui-shi，YANG Hui-zhi.Path planning for agent based on improved genetic algorithm［J］. Computer Simulation，2014，31（6）：357-361.

［10］ADITI K，MAITI M K，MAITI M.Profit maximization of TSP through a hybrid algorithm［J］.Computers and Industrial Engineering，2015，88：229-236.

［11］PINKEY C，KUSUM D，MILLIE P.Novel inertia weight strategies for particle swarm optimization［J］. Memetic Computing，2013，5（3）：229-251.

［12］SHI Y，EBERHART R.Monitoring of particle swarm optimization［J］.Frontiers of Computer Science in China，2009，3（1）：31-37.

［13］AHMAD N，MEHDI E M，REZA S.A novel particle swarm optimization algorithm with adaptive inertia weight［J］.Applied Soft Computing Journal，2011，11（4）：3658-3670.

［14］馬國慶，李瑞峰，劉麗.學(xué)習(xí)因子和時間因子隨權(quán)重調(diào)整的粒子群算法［J］.計算機應(yīng)用研究，2014，31（11）：3291-3294.

MA Guo-qing，LI Rui-feng，LIU Li.Particle swarm optimization algorithm of learning factors and time factor adjusting to weights［J］.Application Research of Computers，2014，31（11）：3291-3294.

［15］趙遠東，方正華.帶有權(quán)重函數(shù)學(xué)習(xí)因子的粒子群算法［J］.計算機應(yīng)用，2013，33（8）：2265-2268.

ZHAO Yuan-dong，F(xiàn)ANG Zheng-hua.Particle swarm optimization algorithm with weight function's learning factor［J］.Journal of Computer Applications，2013，33（8）：2265-2268.

［16］SRINIVAS M，PATNAIK L M.Adaptive probabilities of crossover and mutation in genetic algorithms［J］. IEEE Transactions on Systems，Man and Cybernetics，1994，24（4）：656-667.

［17］任子武，傘冶.自適應(yīng)遺傳算法的改進及在系統(tǒng)辨識中應(yīng)用研究［J］.系統(tǒng)仿真學(xué)報，2006，18（1）：41-43.

RRN Zi-wu，SAN Ye.Improved adaptive genetic algorithm and its application research in parameter identification［J］.Journal of System Simulation，2006，18（1）：41-43.

Research on path planning of parking system based on PSO-genetic hybrid algorithm

WANG Hui1，ZHU Long-biao1，ZHU Tian-cheng2，CHEN Hong-yan1，SHAO Xiao-jiang1，ZHU Zhi-hui3
（1.School of Mechanical Engineering，Nantong University，Nantong 226019，China；2.Jiangsu Branch，China United Network Communications Group Co.，Ltd.，Nanjing 210024，China；3.Jiangsu Jinguan Solid Parking System Engineering Co.，Ltd.，Nantong 226003，China）

Aiming at path planning problem of AGV accessing cars，the dynamic adaptive hybrid algorithm was proposed by combining particle swarm optimization（PSO）with genetic algorithm（GA）.Based on the standard PSO and GA，inertia weight coefficient，learning factor and the formula of crossover and mutation probability were optimized and improved with the dynamic adaptive adjustment strategy.In the initial stage of algorithm evolution，the dynamic linkage relation built between inertia weight coefficient and learning factor were utilized to deal with real-time updates of particle's velocity and position.In the later stage of evolution，in order to strengthen global search ability of hybrid algorithm and improve evolution speed and convergence precision of the algorithm，crossover and mutation operators of adaptive genetic algorithm（AGA）were introduced.Finally，MATLAB was used to verify the feasibility and effectiveness of hybrid algorithm.The simulation results showed the global search ability and convergence performance of hybrid algorithm were optimal by being compared with tabu search algorithm（TSA），ant colonyalgorithm（ACO）and GA.The conclusion indicates that the hybrid algorithm is feasible and effective.

particle swarm optimization；genetic algorithm；parking system；AGV；path planning

TP 301.6

A

1006-754X（2016）02-0195-06

10.3785/j.issn.1006-754X.2016.02.014

2015-11-16.本刊網(wǎng)址·在線期刊：http：//www.journals.zju.edu.cn/gcsjxb

國家自然科學(xué)基金資助項目（51405246）；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新基金資助項目（BY2014081-07）.

王輝（1989—），男，河南周口人，碩士生，從事機電控制和智能算法研究，E-mail：whzl2014@126.com. http：//orcid.org//0000-0002-0563-5801

朱龍彪，男，教授，從事機電控制和故障診斷等研究，E-mail：zhulb@ntu.edu.cn. http：//orcid.org//0000-0001-7105-4258