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

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

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

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

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

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

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

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

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

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

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

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

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

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

2　粒子群算法設計

2.1基本粒子群算法

粒子群算法（PSO）是一種基于迭代搜尋最優(yōu)解的隨機優(yōu)化技術，其基本思想是通過群體中個體間的協(xié)作和信息共享來尋找最優(yōu)解［11］.在PSO算法中，首先將問題的可行解空間初始化為一群粒子，每個優(yōu)化問題的潛在最優(yōu)解均可視為搜索空間中的一個粒子，通過適應度函數(shù)評價種群中粒子的優(yōu)劣，對比粒子當前適應度值及其所經過的個體極值點pbest和全局極值點pgbest的適應度值，更新粒子當前最優(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表示當前粒子；參數(shù)c1和c2表示學習因子；r1和r2為隨機數(shù)，r1∈［0，1］，r2∈［0，1］；xid和vid分別表示粒子i在d維的當前位置和當前速度；pbest為粒子i在d維的個體極值點位置，pgbest為當前整個粒子群在d維中的全局極值點位置.

2.2基本遺傳算法

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

3　粒子群遺傳算法設計

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

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

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

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

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

3.2學習因子優(yōu)化

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

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

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

3.3交叉和變異概率調整公式

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

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

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

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

3.4算法具體實施步驟

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

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

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

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

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

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

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

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

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

Step 10：判斷算法是否滿足終止條件，若是，則算法結束，輸出結果，否則轉至Step 3.

4　仿真及分析

為驗證算法在AGV路徑規(guī)劃中的合理性和有效性，以可行路徑上30個坐標點的路徑尋優(yōu)為例，算法參數(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ù)，來驗證混合算法的性能.仿真結果如圖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ù)當前位置以及存取車位置，AGV運用上述算法均可快速搜索到一條自起點至終點的優(yōu)化路徑.

對比表1數(shù)據(jù)，結合圖中所示的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ī)劃結果Table 1 The results of AGV path planning under the condition of above algorithms

5　結 論

針對AGV存取車路徑規(guī)劃問題，有效地將粒子群算法和遺傳算法進行了融合，在標準粒子群算法和遺傳算法的基礎上，通過引入動態(tài)自適應調整策略，設計了一種動態(tài)自適應混合算法，并在MATLAB環(huán)境下對該混合算法進行了仿真測試.由仿真測試結果可得如下結論：在遍歷可行路徑各節(jié)點的前提下，根據(jù)AGV自身當前位置，運用文中所提算法均可快速搜索到一條自起點至終點的無交叉優(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］樊明，郭藝，贠超，等.基于自適應混合算法的智能存取系統(tǒng)動態(tài)路徑規(guī)劃［J］.系統(tǒng)仿真學報，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］王波，張曉磊.基于粒子群遺傳算法的云計算任務調度研究［J］.計算機工程與應用，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］喬俊飛，王超，劉昌芬.基于改進的自適應粒子群算法的給水管網(wǎng)優(yōu)化設計［J］.北京工業(yè)大學學報，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］.機械工程學報，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］馬國慶，李瑞峰，劉麗.學習因子和時間因子隨權重調整的粒子群算法［J］.計算機應用研究，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］趙遠東，方正華.帶有權重函數(shù)學習因子的粒子群算法［J］.計算機應用，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］任子武，傘冶.自適應遺傳算法的改進及在系統(tǒng)辨識中應用研究［J］.系統(tǒng)仿真學報，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

國家自然科學基金資助項目（51405246）；江蘇省產學研聯(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