基于混合算法的智能立體停車庫研究

2018-05-03 06:58:06張小龍楊國太

銅仁學院學報 2018年3期

關鍵詞：優化

張小龍，楊國太

（安徽工程大學機械與汽車工程學院，安徽蕪湖 241000）

0．引言

現在生活中汽車隨處可見，汽車總量也在不斷的增加。據權威部門統計，截止到2016年我國小型載客汽車已經接近1.5億輛，與上一年相比，其中私家車的增幅達到15.08%，增加近2000萬輛[1]。按照停車位需求：每輛汽車平均有1.2個停車位（一個基本停車位加0.2個公共停車位），可見停車位缺口非常之大。從目前數據[1]來看，我國汽車保有量與停車位之比約為4:1，停車位的滿足率不足30%。傳統地面停車位因受土地限制已不能滿足當下需求，立體停車庫逐漸興起。它在節約土地的同時還能有效地避免車輛意外受損以及被盜事件的發生，且它體積小，容量大，現在已經較廣泛應用在大型醫院，大型超市等車輛密集的公共場所。但是目前應用較為廣泛的立體車庫控制系統主要由PLC控制，受到其本身性能限制，具有響應速度慢，只能進行簡單的邏輯運算和順序控制的缺點，使它無法在大型停車庫上實現智能優化存取路徑，實現高效便捷的存取[1]。

考慮到遺傳算法和蟻群算法對于優化復雜大型立體停車庫運行軌跡有很大的優勢，可經過多次迭代尋找最優路徑，實現智能選擇。文中提出了結合二者優勢的混合算法，對立體停車庫存取過程的停車庫載車板運行路線進行優化，使得存取車更加高效、智能。

1．立體車庫車位調度模型

升降橫移式立體車庫是一種常見的立體停車庫。它主要是以框架為結構支撐，利用停車托盤為運動工具，利用升降橫移電機提供動力，實現停車庫各層車輛的存取。載車板的運行特點是：底層只能橫向移動；最高層的只能上升下降；中間不僅可以平移還可升降，且在每層都設置一個空位（不放載車板）作為通道供載車板升降時使用[6]。位于底層位置的車輛，無需移動其他托盤即可完成存取；底層以上各位置載車板存取車時首先對下方位置進行判斷：當下方位置不為空位時先對下方載車板進行左右平移，然后向下移動，也可自行移動至空位上方然后進行下移[3]。載車板運動的基本方式是：升降回到原位，平移不回到原位。立體車位模型如圖1所示。

從上面的車庫排列方式可以看出每次的存取方式有很多種，每種的動作方式也不相同，所以滿足條件的存取路線有很多。從這些路線中選擇用最短時間走完最少的路線是我們研究的要點。與此同時，為使立體停車庫安全工作，有許多限制條件：（1）底層車位上下受限，僅能左右運動；（2）頂層車位左右受限，僅能上下運動；（3）上升下降后的運動一定是左右移動；（4）車庫的最后一步是下降至一層位置[9]。

圖1 立體車庫模型圖Fig 1 Three-dimensional garagemodel diagram

2．混合算法設計

2．1．遺傳算法和蟻群算法簡介

遺傳算法（Genetic Algorithm）是一種概率搜索算法。其原理為利用編碼方式將解空間映射到相應的編碼空間，編碼與問題解一一對應，稱為染色體，再隨機確定一個起始種群（染色體數串）進行后續迭代[5]。對比生存理論，依據適應度的不同來挑選對應的染色體，然后根據不同的遺傳算子對確定的種群進行交叉異化，得到新的種群[2]。重新生成種群的環境適應性將比迭代以前的種群更好，最后進行重復進化，直到最后得到優化解。這時最后經過迭代生成的末代個體可以看作是所求最優解。

遺傳算法具有優異的整體搜索性能，較強的自適應性使它在工程實際問題中得到較為廣泛的應用。但它有一些缺點：局部尋優能力不足，收斂速度慢，容易早熟，尤其需要優化的參數較多時，遺傳算法的缺點更加明顯[5]。

蟻群算法（Ant Colony System）一種新型仿生類進化算法。它是通過模擬工蟻出巢覓食時尋找最短路徑的情形提出的。蟻群算法的基本原理是：大量工蟻向未知食物區域尋找食物，當其中一只工蟻找到后會向所在區域分泌一種傳遞信息的激素，通過這種信息素的擴散吸引其他工蟻到來，這樣找到食物的螞蟻就會越來越多[4]。在其它工蟻來此的路上，一些會沿著之前螞蟻走過的路，但有些螞蟻會重新尋找路線。如果新出現的路線比原來路線更短，那么越來越多的螞蟻會逐漸被引導至新開辟的短路線上。

蟻群算法采用正反饋機制，不斷收縮搜尋范圍，最后得到最優解。它的搜索過程通過分布式計算方式實現，多個個體同時進行并行計算，不僅提高了算法的計算能力和運行效率，而且容易找到整體最優解[3]。但是在運行初期信息素缺乏，無法在運行之前找到一個使它在面對各種情況時都能獲得最優性能的參數，導致時間效率低下。

2．2．混合算法的基本流程

基于遺傳算法與蟻群算法的混合算法可以使二者優勢互補，彌補兩者的短處。首先依靠遺傳算法的全面擇優能力、自適應性、快速性等來產生應用于蟻群算法的原始信息素分布。然后由蟻群算法的并行性和正反饋方式及求解效率高的特征，來求最優解[3]。這樣融合后的混合算法在時間效率上和求解效率上均優于單獨的遺傳算法和蟻群算法。混合算法的過程如圖2所示。

3．遺傳算法

3．1．編碼與解碼

立體停車庫的研究目標是在運動方向受限的前提下，行走最優路徑。分析車位的動作有五種狀態，分別是：靜止不動，向上移動，向下移動，向左移動，向右移動，然后進行參數編碼，具體方式是：個體的奇數位和偶數位分別代表車位號和運動方向，并且用數字0，1，2，3，4來表示車位的靜止不動，向上移動，向下移動，向左移動，向右移動。此處將解碼定義為編碼的逆過程。根據運動限制條件制定不同的懲罰函數，根據實際情況設計懲罰函數的情況有下面幾種：

（1）確定目標車位所在位置，一層停車板上下移動的與頂層停車板左右移動的；

（2）兩個相鄰車位運動并且朝一個方向的；

（3）最后一步的動作不是下降的；

（4）最后一步的車位不是目標車位的；

（5）停車板已經位于車庫的邊緣且在邊緣方向上繼續有動作的；

（6）在停車板下一步移動的方向位置上有其它停車板的；

（7）然后采用最佳保留選擇的方式將適應度值優的子代直接遺傳下去，或者通過交叉產生新子代再遺傳下去，將適應度不好的個體進行淘汰，這種優勝劣汰的選擇能夠使得迭代終止結果一定是歷代適應度最高的個體。

圖2 混合算法流程圖Fig.2 hybrid algorithm flow chart

3．2．交叉操作

對于一般遺傳算法中的交叉算子很難適應立體停車庫的調度特征，快速的將巡回路徑上優異性能傳給后代。為更好的解決這個問題，本文使用一種改進型的交叉算子，其具體如下：

（1）在每隊父輩個體（A1、A2）中隨機選擇兩個交叉點，兩交叉點中間編碼B1，B2；

（2）將父輩個體中A1與B2間的相同編碼去除，剩下的記為C1，相同可以得到C2；

（3）在C1的任意兩個基因間順序插入B2的整個基因片段，插入一次則會產生一個后代，然后再將B2的編碼倒置，進行相同操作。將D1記為兩次操作產生的子代。相同地，B1與C2也產生后代D2；

（4）選擇D1、D2中一個最優的個體遺傳下來。特別注意的是，由于調度解編碼的奇數位和偶數位分別代表立體停車庫的車位號以及他的運動方向，如果在交叉和變異操作時不將車位號與動作方向同時看做一個基因來進行操作，那么將會出現車位號與動作方向混亂的情況。

3．3．變異操作

為了得到最優解，本文引入變換變異算子來維護種群的多樣性，且可以防止遺傳算法的過早收斂。例如，對于路徑(1 2 3/4 5 6/7 8 9)，假設第一個切入點在3、4之間，第二個切入點在6、7之間，則得到的變換變異為(1 2 3/6 5 4/7 8 9)，它不僅保留了遺傳給下一代的優良基因片斷，而且又產生了新個體。新個體的復雜程度能夠有效地擴大搜索范圍。

利用遺傳算法經過以上步驟，進行n次迭代后將會生成幾組優化解作為車庫的動作，由此得到的優化解交于蟻群算法進行下一步的優化。

3．4．適應度計算與選擇復制

要獲取最優運動方案，首先選擇對應的評價函數，并設計相應的懲罰函數。研究的目標是在存取車過程中停車板運動路線最短，即車庫停車板運動次數最少。為了對比評價函數并計算選擇概率，評價函數的值要取正。

評價函數應盡量保證通用性，使其不用改變其中的參數，一個好的評價函數能在運行過程中自動修正其參數值，得到最優解。對于停車庫載車板的運行優化問題選用的評價函數如（1）式所示：

4．蟻群算法

由于蟻群算法的計算開銷大，從時效性和有效性等因素的考量，為避免混合算法在優化過程中過早停止，以及更好的與遺傳算法相銜接，本文采用一種改進的蟻群算法并使用精英保留策略[8]。改進的算法包含幾種蟻群，每種蟻群含有獨自的信息素。

4．1．初始狀態下信息素釋放

將遺傳算法得到的優化解作為蟻群算法的信息素，將組優化解分別作為幾個蟻群的獨立信息素，并且這幾種信息素的更新相互獨立，相互之間不受影響。設有n個節點，蟻群在(m，n)之間轉移：

則初始時刻各路徑上的信息素如式2所示：

4．2．接受信息素后的轉移概率

在螞蟻種群中，共在節點上隨機釋放m只螞蟻，初始時刻螞蟻在路徑選擇上的概率如（4）式所示：

4．3．信息素更新

當出現最優路線時，那只螞蟻要進行信息素的全局更新（6）、（7）、（8）式所示：

隨著循環的持續進行，經過最短路徑的螞蟻信息素不斷加強，當達到設定的循環周期后，可以得到整個循環最短路徑的信息素之和，如（9）式所示：

4．4．混合算法的復雜度分析

在程序的執行過程中，算法的時間復雜度定量的表達該算法的運行時間，空間復雜度是指計算所需的存儲單元數量，算法復雜性和空間復雜度都是指算法運行時所需的計算機資源的量。

對于混合算法中的遺傳算法由于其本質為二重迭代，時間復雜度小于n2，迭代次數一般不多，時間和空間復雜度主要體現在其中的蟻群算法中，設n是停車板數量，m是螞蟻數量，T是迭代次數，則時間復雜度如（10）式所示：

一般情況下，m=n 2/3，T=k n，當n趨近無窮大時(此時k會遠小于n)，time約等于n4；由space=3 n n+n m可得其空間復雜度如（11）式所示：

當n趨于無窮大時，space約等于n2。

5．實驗模擬與仿真

在MATLAB環境下，以本文的立體車庫為例，目標車位位于30號載車板的條件下，確定各遺傳算子參數，得到了部分實驗結果。按照本文的遺傳算子設計，種群規模為20，迭代次數為30代，交叉概率Pc=0.8，變異概率Pm=0.2。

經過遺傳算法的迭代并將最優解作為蟻群算法的信息素，繼續尋找最優路徑。經過實驗對比遺傳算法和混合算法的最優解的迭代曲線圖（圖3），可以看出遺傳算法局部尋優能力不足，具有收斂速度慢的特點，而混合算法的收斂速度明顯高于遺傳算法。通過蟻群算法和遺傳算法的時間響應速度對比（圖4），可以看出遺傳算法在響應速度上的不足：響應速度慢，時間效率低。結合遺傳算法和蟻群算法的混合算法（圖5），從圖5中可看出它可將兩者優點結合，響應時間短，收斂速度快，能夠較快的尋找到最優路徑。