蟻群優(yōu)化圖著色算法在智能小區(qū)中的運(yùn)用*

魏 娟

(江西服裝學(xué)院商學(xué)院，江西 南昌 330201)

智能小區(qū)[1]是智慧城市里的基本單元，是通過(guò)物聯(lián)網(wǎng)、移動(dòng)互聯(lián)網(wǎng)、云計(jì)算和信息智能終端等信息技術(shù)建立的住宅小區(qū)服務(wù)和管理集成系統(tǒng)，使小區(qū)管理者、用戶與各類智慧系統(tǒng)完成各種形式的信息交互，讓居民在吃、住、行、游等方面體驗(yàn)舒適快捷的現(xiàn)代化數(shù)字生活，同時(shí)使管理更高效.智能小區(qū)通常是采用地理信息系統(tǒng)(Geographic Information System，簡(jiǎn)稱GIS) 的網(wǎng)格化管理，將小區(qū)里的各種動(dòng)態(tài)數(shù)據(jù)和信息在地圖網(wǎng)格中顯現(xiàn)出來(lái)，并實(shí)時(shí)更新數(shù)據(jù)[2].為了在地圖網(wǎng)格中清晰且直觀地展現(xiàn)這些信息，可以利用蟻群算法在網(wǎng)格里進(jìn)行著色，但是在顏色數(shù)太多時(shí)，該算法無(wú)法對(duì)著色色數(shù)進(jìn)行控制，從而出現(xiàn)處理的信息雜亂無(wú)章的現(xiàn)象[3].筆者將對(duì)蟻群算法進(jìn)行優(yōu)化，以解決智能小區(qū)網(wǎng)格著色問(wèn)題.

1 圖著色問(wèn)題描述

圖著色問(wèn)題(Graph Coloring Problem，簡(jiǎn)稱GCP)又稱著色問(wèn)題.GCP多應(yīng)用于組合分析和實(shí)際生活中，如最大支配集、二次分配和最大覆蓋等典型的組合問(wèn)題，又如工藝設(shè)計(jì)、科學(xué)技術(shù)和企業(yè)管理等領(lǐng)域的問(wèn)題.在數(shù)學(xué)上，GCP的定義是從無(wú)向圖公式G=(V,E)而來(lái)的，V表示頂點(diǎn)集合，E表示邊集合.GCP就是將V分成K個(gè)顏色組，每組之間無(wú)相鄰的頂點(diǎn)，都是單獨(dú)集，對(duì)其進(jìn)行優(yōu)化就是將K值最小化.GCP主要包括點(diǎn)著色、邊著色和組合地圖的面著色等，而邊著色和組合地圖的面著色經(jīng)一定的變換后，都可以轉(zhuǎn)化成等價(jià)的點(diǎn)著色.點(diǎn)著色即對(duì)圖G的頂點(diǎn)處著色，使得任何相鄰頂點(diǎn)都涂上不同的顏色.若用K種顏色可以實(shí)現(xiàn)對(duì)圖G的頂點(diǎn)進(jìn)行著色，則稱圖G是K點(diǎn)可著色的；若K是圖G的最小著色數(shù)，則稱圖G是K色圖.

2 蟻群算法

M Dorigo根據(jù)螞蟻覓食原理提出了模擬自然環(huán)境中螞蟻真實(shí)覓食行為的算法，稱為蟻群算法.其根本思想是螞蟻在覓得食物之后，總能找到最優(yōu)路徑將食物運(yùn)回巢穴，這是因?yàn)槊恐晃浵仌?huì)在它所經(jīng)過(guò)的路徑上釋放一種叫做信息素(pheromone)的揮發(fā)性物質(zhì)，螞蟻在行動(dòng)過(guò)程中可以感知該物質(zhì)的強(qiáng)度，從中獲取有關(guān)信息并開(kāi)展相應(yīng)行動(dòng)[4].因此，蟻群算法其實(shí)是一種在圖G中尋找優(yōu)化路徑的機(jī)率型算法，是一類關(guān)于種群的啟發(fā)式搜索仿生進(jìn)化系統(tǒng)[5].

采用蟻群算法對(duì)一個(gè)給定的圖形著色，設(shè)C是顏色集，C={c1,c2,c3,…,cp}，V是頂點(diǎn)集，V={v1,v2,v3,…,vn}，螞蟻總數(shù)為m.為了著色準(zhǔn)備，構(gòu)建圖G的鄰接矩陣D=(Dij)，其中

用著色表S=(Siq)記錄螞蟻的著色行動(dòng).令Siq=1表示螞蟻經(jīng)過(guò)頂點(diǎn)vi，這時(shí)用cq對(duì)頂點(diǎn)vi著色，即

(1)

其中：ηij是啟發(fā)式信息，

(2)

NumC是頂點(diǎn)vi-1著色后用的總顏色數(shù)；α和β(α,β∈{1,2,3,4})分別是信息素量Tij和啟發(fā)式信息ηij對(duì)螞蟻著色的影響參數(shù).

3 蟻群優(yōu)化圖著色算法

圖1 著色和褪色過(guò)程Fig. 1 Coloring and Fading Process

著色和褪色過(guò)程中存在著色不成功的問(wèn)題.這個(gè)問(wèn)題可通過(guò)如下5個(gè)步驟解決：

(ⅰ)設(shè)置各參數(shù)信息，包括循環(huán)次數(shù)NC、初始化蟻群數(shù)antCount、蟻群最大色數(shù)Max(4≤Max≤P)，以及影響參數(shù)α和β等.為了記錄螞蟻的爬行線路，增設(shè)一個(gè)路徑信息tour，初始是點(diǎn)的次序；同時(shí)將antCount置于點(diǎn)1，設(shè)NumC=1，最開(kāi)始著色螞蟻t=1.

(ⅱ)螞蟻t對(duì)圖全面著色，主要是指對(duì)點(diǎn)tour[a]著色和褪色，直到全部點(diǎn)都著色.其中a是已著色點(diǎn)數(shù)，開(kāi)始時(shí)a=1.假設(shè)進(jìn)行了褪色的過(guò)程，那么a就是a-1.

(ⅲ)所有螞蟻都全部著色，則記錄最好的著色；不然，t++，返回步驟(ⅱ).

(ⅳ)由(1)，(2)式改變信息素量Tij和啟發(fā)式信息ηij.

(ⅴ)假設(shè)循環(huán)次數(shù)NC已經(jīng)達(dá)到，那么輸出的就是當(dāng)前最優(yōu)的解；否則，是NC++.這時(shí)需要進(jìn)入下一次循環(huán)，將antCount置于點(diǎn)1，設(shè)NumC=1，最開(kāi)始著色螞蟻t=1.

4 蟻群優(yōu)化圖著色算法與蟻群算法的對(duì)比

在Windows7環(huán)境下，采用Java軟件，設(shè)置迭代次數(shù)1 000，蟻群數(shù)20，對(duì)比分析蟻群優(yōu)化圖著色算法與蟻群算法的著色色數(shù)和運(yùn)轉(zhuǎn)時(shí)間，如圖2所示.

a 色數(shù)性能對(duì)比 b 運(yùn)轉(zhuǎn)時(shí)間對(duì)比圖2 蟻群優(yōu)化圖著色算法與蟻群算法的性能對(duì)比Fig. 2 Performance Comparison Between Ant Colony Optimization Graph Coloring Algorithmand Ant Colony Algorithm

從圖2a可以看出，在GCP的解決中，蟻群優(yōu)化圖著色算法能夠有效地將色數(shù)控制在Max范圍里，優(yōu)于蟻群算法.從圖2b可以看出，隨著圖的復(fù)雜性不斷增加，蟻群優(yōu)化圖著色算法的運(yùn)轉(zhuǎn)時(shí)間比蟻群算法的少.由此可知，無(wú)論是求解色數(shù)方面，還是運(yùn)轉(zhuǎn)時(shí)間方面，蟻群優(yōu)化圖著色算法的性能都優(yōu)于蟻群算法，尤其是在圖復(fù)雜性極高的環(huán)境下，蟻群優(yōu)化圖著色算法還能減小并控制著色色數(shù)，實(shí)現(xiàn)四色著色.

5 蟻群優(yōu)化圖著色算法的運(yùn)用

將蟻群優(yōu)化圖著色算法運(yùn)用在智能小區(qū)中，對(duì)智能小區(qū)的網(wǎng)格進(jìn)行著色.其主要過(guò)程如下：

(1)在GIS中獲取地理數(shù)據(jù)信息，并根據(jù)主要街道繪制小區(qū)網(wǎng)格；然后從GIS空間數(shù)據(jù)的拓?fù)潢P(guān)聯(lián)中獲取每個(gè)網(wǎng)格間的鄰接關(guān)聯(lián)，并將鄰接關(guān)聯(lián)導(dǎo)入到relation.dat文檔中.

(2)將relation.dat文檔中讀取的數(shù)據(jù)應(yīng)用到蟻群優(yōu)化圖著色算法中，對(duì)讀取的數(shù)據(jù)進(jìn)行著色，然后回著色表S.

(3)依照著色表S對(duì)網(wǎng)格著色.

將蟻群優(yōu)化圖著色算法運(yùn)用于南昌市某智能小區(qū)中，其最大色數(shù)Max設(shè)為4.根據(jù)該小區(qū)街道的特點(diǎn)，將小區(qū)分成8個(gè)網(wǎng)格，采用蟻群優(yōu)化圖著色算法獲得著色色數(shù)是3.在對(duì)網(wǎng)格進(jìn)行著色時(shí)，采用深灰色色調(diào)，透明度為20%，50%，80%.小區(qū)網(wǎng)格化著色結(jié)果如圖3所示.

圖3 小區(qū)網(wǎng)格化著色結(jié)果Fig. 3 Cell Grid Coloring Results

6 結(jié)語(yǔ)

蟻群優(yōu)化圖著色算法彌補(bǔ)了蟻群算法的不足.尤其是在圖復(fù)雜性較高的環(huán)境下，蟻群優(yōu)化圖著色算法能減小并控制著色色數(shù)，實(shí)現(xiàn)四色著色，使得智能小區(qū)里的各種動(dòng)態(tài)數(shù)據(jù)和信息在地圖網(wǎng)格中更加清晰且直觀地展現(xiàn)，從而在智能小區(qū)社會(huì)服務(wù)過(guò)程中表現(xiàn)出服務(wù)“零距離”、居民訴求 “全響應(yīng)” 和社會(huì)管理 “全覆蓋”等優(yōu)點(diǎn)，值得在智能小區(qū)服務(wù)中推廣應(yīng)用.