謝軼俍 李昂

（1.同濟大學 上海 2.三菱電梯）

一種基于蟻群遺傳算法的電梯群控算法設計

謝軼俍1李昂2

（1.同濟大學 上海 2.三菱電梯）

隨著社會的不斷深入，以及高層樓宇的不斷涌現(xiàn)，多臺電梯單獨服務的電梯系統(tǒng)已經(jīng)無法滿足人們對于電梯的需要了。多臺電梯如果需要更好地提高效率，那就需要一種好的群控方法，來對電梯群進行控制。本文算法的主要目標是在于將蟻群算法與遺傳算法進行融合，然后再將電梯調(diào)度的基本模型引入蟻群遺傳算法中，通過遺傳算法中概率選擇、交叉、變異等一系列操作手段，提高電梯調(diào)度系統(tǒng)的全局搜索能力以及蟻群算法快速的求解能力，優(yōu)勢互補，在算法收斂以后，得到較好的電梯群控調(diào)度方案。

蟻群算法；遺傳算法；電梯群控

1 兩種算法的性能分析

蟻群算法及遺傳算法在計算的過程中，本質(zhì)上可以并行計算、即其具有并行性。它們之間的信息是可以相互交流，協(xié)同處理。同時，遺傳算法不受條件的約束，在對電梯群控參數(shù)進行一一編碼形成2進制編碼的染色體后，通過交叉和變異操作，使其具有了全局搜索解的能力的，這樣一來在面對多個召喚同時出現(xiàn)的復雜調(diào)度及非線性問題，它具有很好的解決能力。當然遺傳算法同樣有其缺點，根據(jù)遺傳算法在求解到一定范圍時往往會出現(xiàn)冗余的迭代，使得反饋信息無法完全被利用，導致求解效率不高。蟻群算法因為其正反饋機制所以其求解的效率相對較好，但是蟻群算法的缺點是其在初始化階段由于信息素較少，如果問題規(guī)模很大那么其相對來說效率將會變慢。

2 兩種算法混合的可行性分析

我們可以設想一下，如果我們能將這兩種算法優(yōu)勢互補，從而能克服兩者可能存在的缺點，那求解的效率一定會有所提高產(chǎn)生一種在時間和求解上效率都比較高的蟻群遺傳算法，相關研究表明蟻群和遺傳算法的速度與時間曲線如圖1所示。

圖1 蟻群和遺傳算法的速度與時間曲線圖

我們可以從圖上得知，遺傳算法在t0～t1時間具有很快的速度，在t2這個點有了下降的趨勢，在過了tc時刻之后求解的效率就降低了。蟻群算法在t0～t1時間速率并不是很高，缺乏信息素致使其搜索緩慢，隨著信息素積累，過了tc它的求解收斂速度開始提高。那我們的初步思想是在前期在某些系統(tǒng)問題不復雜的情況下，利用蟻群算法處理問題，后期當系統(tǒng)復雜度提升時利用有全面搜索能力的遺傳算法進行求解，再利用蟻群的特性進行最優(yōu)解的求解，并作為遺傳算法的種群的一個補充。

3 混合算法框架設計

作為電梯群控系統(tǒng)來說，其非常大的特點是實時性，這個特性大大影響了算法的搜索以及算法對于最優(yōu)值計算的能力。由實時性伴隨而來的其實就是系統(tǒng)的隨機性，隨機性則導致了單純地求出最優(yōu)解實際意義并不大，因為某個特定情況的最優(yōu)解，不一定始終就是最優(yōu)解。結(jié)合實際來分析就是當召喚信號由乘客發(fā)出后，即便系統(tǒng)通過本身的算法計算出最優(yōu)化的分配方案，但是由于隨機性的存在，電梯的環(huán)境條件其實隨時都在發(fā)生改變。那么當時的最優(yōu)分配方案在電梯被分配到用戶呼叫樓層后就已經(jīng)不是最優(yōu)的分配方案了。因此本算法中在選擇電梯的分配方式時是具有選擇性地在每隔一段時間后就會重新啟動遺傳算法進行最優(yōu)方案的搜索及電梯分派工作。對電梯轎廂的分派系統(tǒng)進行及時修正，簡單地說就是在多個用戶先后發(fā)出多個召喚信號時根據(jù)情況選擇最優(yōu)的電梯調(diào)度多目標優(yōu)化方案。上述過程的具體流程圖如圖2所示。

4 電梯群控混合算法步驟設計

首先我們先確定了引入蟻群算法和遺傳算法的條件：

圖2 電梯群控混合算法的流程圖

在確定之后開始算法流程的描述。

（1）掃描外部召喚信號。

（2）當有電梯系統(tǒng)有一個外召信號時候。

（3）分析各轎廂目前的狀態(tài)。

（4）引入蟻群算法，并有多目標函數(shù)作為蟻群算法信息素濃度。

（5）求該調(diào)度方案的目標函數(shù)值與暫優(yōu)方案進行比較。

（6）若該方案暫優(yōu)，將其道路上整體信息素更新。然后信息素揮發(fā)。

（7）若不是則信息素直接揮發(fā)。

（8）算法是否收斂，不收斂則繼續(xù)進行搜索。

（9）算法若收斂，將若個優(yōu)秀調(diào)度方案作為遺傳算法的補充放入數(shù)據(jù)庫。

（10）繼續(xù)掃描外召信號，若一段時間繼續(xù)沒有外召信號，則以蟻群算法的最優(yōu)解作為最佳調(diào)度。

（11）若在一段時間內(nèi)出現(xiàn)多個外召信號。

（12）則開始遺傳部分的的計算

（13）將N個召喚對應的N太電梯作為染色體進行編碼。

（14）種群初始化，先隨機選出種群進行編碼，同時蟻群算法的幾個較有效解也可以作為種群的一個補充。

（15）先計算每個個體適應度。

（16）保留最優(yōu)個體的策略選出N個個體。即選擇操作。

（17）隨機重新排列群中的個體序列。

（18）計算兩兩相鄰個體交叉概率Pc按照此概率隨機單點交叉兩個體。即交叉操作。

（19）計算每個個體的變異概率Pm按照此概率隨機變異得到下一代種群。即變異操作。

（20）計算新一代種群中個體適應度的值。

（21）是否滿足終止條件，不滿足則繼續(xù)進行，滿足則求得電梯調(diào)度最優(yōu)解。

5 結(jié)語

本文在求解電梯群控系統(tǒng)中首先提出了將蟻群算法及遺傳算法結(jié)合運用于電梯群控之中的思想。既加大了電梯的行駛效率、減少了消耗，在減輕轎廂擁擠度等方面，做出了多目標優(yōu)化的嘗試.而且還以模擬研究確認了此公式的可行性。截止到目前為止，這兩種算法同時應用在電梯群控系統(tǒng)中的探討還相當少。并對針對蟻群遺傳算法的基礎條件、數(shù)字建構、做出了重點探討。有效設計了這兩個算法的融合步驟及應用條件。

[1]劉立東，蔡淮.融入遺傳算法的混合蟻群算法[J].計算機工程與設計，2014，05：1248～1249+1252.

[2]黃立君，許永花.遺傳算法和蟻群算法融合求解電梯群控[J].東北農(nóng)業(yè)大學學報，2014，04：109～113.

[3]肖宏峰，譚冠政.基于遺傳算法的混合蟻群算法[J].計算機工程與應用，2014，16：42～45+134.

TP18

A

1004-7344（2016）08-0329-02

2016-3-1

謝軼俍（1985-），男，浙江紹興人，工程師，本科，從事控制工程工作。