基于優(yōu)化遺傳算法城市立體車庫信號調(diào)度算法的研究＊

張書茂

（安徽城市管理職業(yè)學(xué)院，安徽合肥 230000）

0.引言

近年來，經(jīng)濟(jì)的高速發(fā)展，生活質(zhì)量的不斷提高，除了公用車輛的數(shù)量相對穩(wěn)定，私家車數(shù)量上迅速增長，立體車庫應(yīng)運(yùn)而生，目前大都是地下城市立體車庫，同普通停車場主要區(qū)別是層數(shù)的增加，有一部分立體車庫，已經(jīng)安裝有升降裝置的，在空間上得到了一定的優(yōu)化利用，但是相當(dāng)一部分還是依據(jù)信號的順序?qū)ι笛b置即堆垛機(jī)的調(diào)度控制，即單體控制[1]，那么對堆垛機(jī)的調(diào)度優(yōu)化方面還需要進(jìn)一步的研究，提出了一種基于遺傳算法堆垛機(jī)的路徑優(yōu)化算法[2]，為立體車庫的堆垛機(jī)路徑優(yōu)化提供參考。

1.遺傳算法

1.1 相關(guān)概念

1975 年J.Holland 教授提出遺傳算法簡稱GA。其主要思想是通過多次迭代方式在實(shí)際問題空間里，求解達(dá)到一定程度的最優(yōu)解。

1.2 常用操作

在遺傳算法迭代的過程中，因?yàn)橹豢紤]內(nèi)部信息，適應(yīng)度函數(shù)對迭代的次數(shù)和運(yùn)行時間起著決定性作用。適應(yīng)度函數(shù)g(x)主要有：（1）目標(biāo)函數(shù)為參數(shù)；（2）估算參數(shù)Dmax|min為參數(shù)；（3）通過界限值D 參數(shù)（保守估計）。

實(shí)際運(yùn)行中，會產(chǎn)生兩種極端的現(xiàn)象：

第一種：差異比較大特殊的個體，對優(yōu)化選擇的趨勢影響到全局。第二種：差異比較小的個體，對優(yōu)化效率有一定的影響。為了減少以上個體的數(shù)量，對適應(yīng)度函數(shù)g(x)要滿足如下要求：

圖1 遺傳算法流程圖

(1)g(x)函數(shù)要連續(xù)性，正值區(qū)間，具體值。

(2)g(x)在保證目標(biāo)函數(shù)的條件下，簡單線性化。

(3)g(x)的參數(shù)在達(dá)到目標(biāo)函數(shù)要求范圍內(nèi)，通用化。

1.3 算法流程（圖1）

2.遺傳算法的改進(jìn)

2.1 相關(guān)思路

在遺傳算法求解最短路徑的問題上，除了適應(yīng)度g(x)函數(shù)有很重要的特點(diǎn)外，在初始化種群中求解的空間范圍中的個體也很重要，通常是隨機(jī)選取后進(jìn)行迭代運(yùn)算[3]，那么在求解空間的選擇或者樣本空間的選擇也很重要，不同的樣本空間的選擇，得到的結(jié)果也是不同的，為了保證在樣本空間具有一定的連續(xù)性相關(guān)性，提高遺傳算法的運(yùn)行時間和空間的效率，引入蟻群算法(Ant Colony algorithm)，對求解空間的樣本進(jìn)行優(yōu)化，提升遺傳算法。

蟻群算法是通過蟻群尋找食物的整個過程的思想，即個體之間交流信息找到最佳路徑。

2.2 相關(guān)概念

假設(shè)立體車庫有n 個停車位，先求解樣本空間然后求解最佳路徑。其中n 個停車位表示為n 個節(jié)點(diǎn)，dij代表第i 和第j 個節(jié)點(diǎn)的距離，其中i，j ∈n。

n個停車位對應(yīng)n個螞蟻，作為各個螞蟻的位置的初始化。

相關(guān)說明: Aijα(t)表示節(jié)點(diǎn)i 與節(jié)點(diǎn)j，t 時刻路徑上的剩余信息。 Bijβ(t)表示節(jié)點(diǎn)i 與節(jié)點(diǎn)j 的概率值，通常用1/dij表示，其中的α 和β 是用來調(diào)節(jié)的參數(shù)，該公式表明：選中的概率與該節(jié)點(diǎn)的信息量成正比，與距離成反比。

每個螞蟻k 都有一個線性表結(jié)構(gòu)L 與之對應(yīng)，用來記錄所訪問過的節(jié)點(diǎn)。其中用ρ 表示L 的內(nèi)容更替的程度[4]。

所有節(jié)點(diǎn)完成一次遍歷后，每個節(jié)點(diǎn)的信息調(diào)整如下：

2.3 改進(jìn)方法

步驟1：n 個螞蟻對應(yīng)n 個停車位。

（3）循環(huán)結(jié)束條件進(jìn)行判斷，滿足跳出循環(huán)，反之繼續(xù)循環(huán)。

步驟4：通過步驟3 的結(jié)果然后進(jìn)行遺傳算法的求解。

2.4 相關(guān)說明

通過分析，α=1，β=5，ρ=0.5 比較穩(wěn)定，C,Q 基本沒有影響，一般取值為C=10，Q=100。特別說明一點(diǎn)：一般循環(huán)體選用次數(shù)或者兩次遺傳運(yùn)算結(jié)果的差異值[6]（差異值允許的一定范圍）。

3.數(shù)據(jù)分析

表1 空停車位表

假設(shè)在某一個立體車庫的某層車庫，每個停車位之間長度為1m，寬度也為1m，堆垛機(jī)的運(yùn)行速度勻速為1m/s,本仿真實(shí)驗(yàn)不考慮時間進(jìn)行測試，本車庫總共停車位為225 個，其中209 已經(jīng)停滿，還有16 個車位為空位，空車位的坐標(biāo)，如表1 所示。

（2）通過傳統(tǒng)的遺傳算法得的路徑為：A-C-J-F-B-IE-M-H-P-D-G-L-K-O-N-A,對應(yīng)的路徑長度為：9+8+7+5+10+2+4+6+13+5+8+10+5+10+3+11=116，因?yàn)閭鹘y(tǒng)的遺傳算法求得結(jié)果不一定是最優(yōu)的結(jié)果，是相對優(yōu)解（允許在一定的范圍）。

（3）通過蟻群算法優(yōu)化初始種群，再進(jìn)行遺傳算法求解最短路徑:A-F-B-E-I-M-H-G-P-J-L-N-O-B-K-D-A,對應(yīng)的路徑長度：8+5+10+2+4+6+10+5+5+2+4+3+3+9+3+21=100。

可以得到傳統(tǒng)遺傳算法得到解是相對優(yōu)解，通過蟻群算法初始化種群后在進(jìn)行遺傳運(yùn)算得到的解更好一些。

通過算法得分析可以得到，通過蟻群算法初始化種群后，遺傳算法得運(yùn)算空間的基本解決，在通過適應(yīng)度函數(shù)進(jìn)行微調(diào)就基本達(dá)到相對的優(yōu)解。

4.結(jié)語

本文探討了立體車庫信號調(diào)度堆垛機(jī)的最短路徑的問題，討論的案例是在平面二維車庫進(jìn)行的，適應(yīng)度的平方差比較小，邊緣的適應(yīng)度高的節(jié)點(diǎn)以及客戶停車時間的參數(shù)對路徑的選擇的影響有待進(jìn)一步的研究。