一種基于蟻群遺傳算法的電梯群控算法設(shè)計(jì)

謝軼俍 李昂

（1.同濟(jì)大學(xué) 上海 2.三菱電梯）

一種基于蟻群遺傳算法的電梯群控算法設(shè)計(jì)

謝軼俍1李昂2

（1.同濟(jì)大學(xué) 上海 2.三菱電梯）

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

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

1 兩種算法的性能分析

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

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

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

圖1 蟻群和遺傳算法的速度與時(shí)間曲線(xiàn)圖

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

3 混合算法框架設(shè)計(jì)

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

4 電梯群控混合算法步驟設(shè)計(jì)

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

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

在確定之后開(kāi)始算法流程的描述。

（1）掃描外部召喚信號(hào)。

（2）當(dāng)有電梯系統(tǒng)有一個(gè)外召信號(hào)時(shí)候。

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

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

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

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

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

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

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

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

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

（12）則開(kāi)始遺傳部分的的計(jì)算

（13）將N個(gè)召喚對(duì)應(yīng)的N太電梯作為染色體進(jìn)行編碼。

（14）種群初始化，先隨機(jī)選出種群進(jìn)行編碼，同時(shí)蟻群算法的幾個(gè)較有效解也可以作為種群的一個(gè)補(bǔ)充。

（15）先計(jì)算每個(gè)個(gè)體適應(yīng)度。

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

（17）隨機(jī)重新排列群中的個(gè)體序列。

（18）計(jì)算兩兩相鄰個(gè)體交叉概率Pc按照此概率隨機(jī)單點(diǎn)交叉兩個(gè)體。即交叉操作。

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

（20）計(jì)算新一代種群中個(gè)體適應(yīng)度的值。

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

5 結(jié)語(yǔ)

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

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

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

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

TP18

A

1004-7344（2016）08-0329-02

2016-3-1

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