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

張小龍，楊國(guó)太

（ 安徽工程大學(xué) 機(jī)械與汽車工程學(xué)院，安徽 蕪湖 241000）

0．引言

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

考慮到遺傳算法和蟻群算法對(duì)于優(yōu)化復(fù)雜大型立體停車庫(kù)運(yùn)行軌跡有很大的優(yōu)勢(shì)，可經(jīng)過(guò)多次迭代尋找最優(yōu)路徑，實(shí)現(xiàn)智能選擇。文中提出了結(jié)合二者優(yōu)勢(shì)的混合算法，對(duì)立體停車庫(kù)存取過(guò)程的停車庫(kù)載車板運(yùn)行路線進(jìn)行優(yōu)化，使得存取車更加高效、智能。

1．立體車庫(kù)車位調(diào)度模型

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

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

圖1 立體車庫(kù)模型圖Fig 1 Three-dimensional garagemodel diagram

2．混合算法設(shè)計(jì)

2．1．遺傳算法和蟻群算法簡(jiǎn)介

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

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

蟻群算法（Ant Colony System）一種新型仿生類進(jìn)化算法。它是通過(guò)模擬工蟻出巢覓食時(shí)尋找最短路徑的情形提出的。蟻群算法的基本原理是：大量工蟻向未知食物區(qū)域?qū)ふ沂澄?，?dāng)其中一只工蟻找到后會(huì)向所在區(qū)域分泌一種傳遞信息的激素，通過(guò)這種信息素的擴(kuò)散吸引其他工蟻到來(lái)，這樣找到食物的螞蟻就會(huì)越來(lái)越多[4]。在其它工蟻來(lái)此的路上，一些會(huì)沿著之前螞蟻?zhàn)哌^(guò)的路，但有些螞蟻會(huì)重新尋找路線。如果新出現(xiàn)的路線比原來(lái)路線更短，那么越來(lái)越多的螞蟻會(huì)逐漸被引導(dǎo)至新開(kāi)辟的短路線上。

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

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

基于遺傳算法與蟻群算法的混合算法可以使二者優(yōu)勢(shì)互補(bǔ)，彌補(bǔ)兩者的短處。首先依靠遺傳算法的全面擇優(yōu)能力、自適應(yīng)性、快速性等來(lái)產(chǎn)生應(yīng)用于蟻群算法的原始信息素分布。然后由蟻群算法的并行性和正反饋方式及求解效率高的特征，來(lái)求最優(yōu)解[3]。這樣融合后的混合算法在時(shí)間效率上和求解效率上均優(yōu)于單獨(dú)的遺傳算法和蟻群算法?；旌纤惴ǖ倪^(guò)程如圖2所示。

3．遺傳算法

3．1．編碼與解碼

立體停車庫(kù)的研究目標(biāo)是在運(yùn)動(dòng)方向受限的前提下，行走最優(yōu)路徑。分析車位的動(dòng)作有五種狀態(tài)，分別是：靜止不動(dòng)，向上移動(dòng)，向下移動(dòng)，向左移動(dòng)，向右移動(dòng)，然后進(jìn)行參數(shù)編碼，具體方式是：個(gè)體的奇數(shù)位和偶數(shù)位分別代表車位號(hào)和運(yùn)動(dòng)方向，并且用數(shù)字0，1，2，3，4來(lái)表示車位的靜止不動(dòng)，向上移動(dòng)，向下移動(dòng)，向左移動(dòng)，向右移動(dòng)。此處將解碼定義為編碼的逆過(guò)程。根據(jù)運(yùn)動(dòng)限制條件制定不同的懲罰函數(shù)，根據(jù)實(shí)際情況設(shè)計(jì)懲罰函數(shù)的情況有下面幾種：

（1）確定目標(biāo)車位所在位置，一層停車板上下移動(dòng)的與頂層停車板左右移動(dòng)的；

（2）兩個(gè)相鄰車位運(yùn)動(dòng)并且朝一個(gè)方向的；

（3）最后一步的動(dòng)作不是下降的；

（4）最后一步的車位不是目標(biāo)車位的；

（5）停車板已經(jīng)位于車庫(kù)的邊緣且在邊緣方向上繼續(xù)有動(dòng)作的；

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

（7）然后采用最佳保留選擇的方式將適應(yīng)度值優(yōu)的子代直接遺傳下去，或者通過(guò)交叉產(chǎn)生新子代再遺傳下去，將適應(yīng)度不好的個(gè)體進(jìn)行淘汰，這種優(yōu)勝劣汰的選擇能夠使得迭代終止結(jié)果一定是歷代適應(yīng)度最高的個(gè)體。

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

3．2．交叉操作

對(duì)于一般遺傳算法中的交叉算子很難適應(yīng)立體停車庫(kù)的調(diào)度特征，快速的將巡回路徑上優(yōu)異性能傳給后代。為更好的解決這個(gè)問(wèn)題，本文使用一種改進(jìn)型的交叉算子，其具體如下：

（1）在每隊(duì)父輩個(gè)體（A1、A2）中隨機(jī)選擇兩個(gè)交叉點(diǎn)，兩交叉點(diǎn)中間編碼B1，B2；

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

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

（4）選擇D1、D2中一個(gè)最優(yōu)的個(gè)體遺傳下來(lái)。特別注意的是，由于調(diào)度解編碼的奇數(shù)位和偶數(shù)位分別代表立體停車庫(kù)的車位號(hào)以及他的運(yùn)動(dòng)方向，如果在交叉和變異操作時(shí)不將車位號(hào)與動(dòng)作方向同時(shí)看做一個(gè)基因來(lái)進(jìn)行操作，那么將會(huì)出現(xiàn)車位號(hào)與動(dòng)作方向混亂的情況。

3．3．變異操作

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

利用遺傳算法經(jīng)過(guò)以上步驟，進(jìn)行n次迭代后將會(huì)生成幾組優(yōu)化解作為車庫(kù)的動(dòng)作，由此得到的優(yōu)化解交于蟻群算法進(jìn)行下一步的優(yōu)化。

3．4．適應(yīng)度計(jì)算與選擇復(fù)制

要獲取最優(yōu)運(yùn)動(dòng)方案，首先選擇對(duì)應(yīng)的評(píng)價(jià)函數(shù)，并設(shè)計(jì)相應(yīng)的懲罰函數(shù)。研究的目標(biāo)是在存取車過(guò)程中停車板運(yùn)動(dòng)路線最短，即車庫(kù)停車板運(yùn)動(dòng)次數(shù)最少。為了對(duì)比評(píng)價(jià)函數(shù)并計(jì)算選擇概率，評(píng)價(jià)函數(shù)的值要取正。

評(píng)價(jià)函數(shù)應(yīng)盡量保證通用性，使其不用改變其中的參數(shù)，一個(gè)好的評(píng)價(jià)函數(shù)能在運(yùn)行過(guò)程中自動(dòng)修正其參數(shù)值，得到最優(yōu)解。對(duì)于停車庫(kù)載車板的運(yùn)行優(yōu)化問(wèn)題選用的評(píng)價(jià)函數(shù)如（1）式所示：

4．蟻群算法

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

4．1．初始狀態(tài)下信息素釋放

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

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

4．2．接受信息素后的轉(zhuǎn)移概率

在螞蟻種群中，共在節(jié)點(diǎn)上隨機(jī)釋放m只螞蟻，初始時(shí)刻螞蟻在路徑選擇上的概率如（4）式所示：

4．3．信息素更新

當(dāng)出現(xiàn)最優(yōu)路線時(shí)，那只螞蟻要進(jìn)行信息素的全局更新（6）、（7）、（8）式所示：

隨著循環(huán)的持續(xù)進(jìn)行，經(jīng)過(guò)最短路徑的螞蟻信息素不斷加強(qiáng)，當(dāng)達(dá)到設(shè)定的循環(huán)周期后，可以得到整個(gè)循環(huán)最短路徑的信息素之和，如（9）式所示：

4．4．混合算法的復(fù)雜度分析

在程序的執(zhí)行過(guò)程中，算法的時(shí)間復(fù)雜度定量的表達(dá)該算法的運(yùn)行時(shí)間，空間復(fù)雜度是指計(jì)算所需的存儲(chǔ)單元數(shù)量，算法復(fù)雜性和空間復(fù)雜度都是指算法運(yùn)行時(shí)所需的計(jì)算機(jī)資源的量。

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

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

當(dāng)n趨于無(wú)窮大時(shí)，space約等于n2。

5．實(shí)驗(yàn)?zāi)M與仿真

在MATLAB環(huán)境下，以本文的立體車庫(kù)為例，目標(biāo)車位位于30號(hào)載車板的條件下，確定各遺傳算子參數(shù)，得到了部分實(shí)驗(yàn)結(jié)果。按照本文的遺傳算子設(shè)計(jì)，種群規(guī)模為20，迭代次數(shù)為30代，交叉概率Pc=0.8，變異概率Pm=0.2。

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

6．結(jié)論

通過(guò)對(duì)智能立體停車庫(kù)的運(yùn)行條件的分析，利用融合了遺傳算法和蟻群算法的混合算法對(duì)存取車時(shí)載車板的運(yùn)行路線的優(yōu)化，達(dá)到了運(yùn)行路線縮短，存取時(shí)間減少的目的。但由于實(shí)驗(yàn)所用的車庫(kù)比較簡(jiǎn)單沒(méi)有充分發(fā)揮出混合算法的全部?jī)?yōu)勢(shì)，下一步的重點(diǎn)是選擇更復(fù)雜的車庫(kù)并選用更合適的參數(shù)進(jìn)

圖3 遺傳算法和混合算法最優(yōu)解迭代曲線Fig.3 Genetic algorithm and hybrid algorithm optimal solution iterative curve

圖4 蟻群算法和遺傳算法迭代響應(yīng)時(shí)間Fig.4 Ant Colony Algorithm and GeneticAlgorithm Iterative Response Time

圖5 混合算法迭代曲線圖Fig 5Hybrid algorithm iteration curve

參考文獻(xiàn)：

[1]安旭，許凌云，劉松．基于RFID的智能立體停車場(chǎng)管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]．電子設(shè)計(jì)工程，2017，25（7）：119-122．

[2]王雷，蔡勁草，石鑫．基于改進(jìn)遺傳算法的多目標(biāo)柔性作業(yè)車間節(jié)能調(diào)度問(wèn)題[J]．南京理工大學(xué)學(xué)報(bào)，2017（4）：494-502．

[3]曹陽(yáng)，劉亞軍，俞琰．基于遺傳-蟻群算法的云計(jì)算任務(wù)調(diào)度優(yōu)化[J]．吉林大學(xué)學(xué)報(bào)：理學(xué)版，2016（5）：1077-1081．

[4]田松齡，陳東祥，王太勇，等．一種異步蟻群算法求解柔性作業(yè)車間調(diào)度問(wèn)題[J]．天津大學(xué)學(xué)報(bào)：自然科學(xué)與工程技術(shù)版，2016（9）：920-928．

[5]楊新武，楊麗軍．基于交叉模型的改進(jìn)遺傳算法[J]．控制與決策，2016（7）：1837-1844．

[6]方二喜，陳小平．基于遺傳算法的立體車庫(kù)車位調(diào)度研究[J]．計(jì)算機(jī)與數(shù)字程，2007（12）：43-46．

[7]吳玫，陸金桂．遺傳算法的研究進(jìn)展綜述[J]．機(jī)床與液壓，2008（3）：176-179．

[8]唐增明，蔣泰．一種改進(jìn)的動(dòng)態(tài)自適應(yīng)最大最小蟻群算法[J]．計(jì)算機(jī)與現(xiàn)代化，2008（3）：90-92．

[9]胡瑜，張惠云．智能立體停車庫(kù)計(jì)算機(jī)監(jiān)控系統(tǒng)[J]．天津科技大學(xué)學(xué)報(bào)，2006，21（2）：62-64．

[10]索跡，祁春清．智能立體停車場(chǎng)控制探討[J]．科技信息，2008（35）：101-102．

[11]鄭寶舉，袁永康，員超．智能立體停車庫(kù)控制系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J]．計(jì)算機(jī)測(cè)量與控制，2003，11（6）：426-429．