基于粒子群ISODATA 電梯交通模式識(shí)別

蔡麗霞

（河南工業(yè)職業(yè)技術(shù)學(xué)院網(wǎng)絡(luò)管理中心,河南南陽(yáng),473000)

1 電梯交通流的模式及數(shù)據(jù)采集、分析

電梯交通流有著其自身的特點(diǎn)，可以用電梯群服務(wù)系統(tǒng)的乘客數(shù)、乘客出現(xiàn)的周期和分布情況來(lái)描述。電梯交通流的特征往往隨著高層建筑用途的不同而有所差異，對(duì)于典型的辦公建筑，電梯交通流通常具有以下幾種主要模式：上行高峰模式、下行高峰模式、雙路模式、平衡的層間模式以及空閑模式等。在采集電梯交通流數(shù)據(jù)時(shí)，通常需要統(tǒng)計(jì)的交通流特征數(shù)據(jù)有：?jiǎn)挝粫r(shí)間內(nèi)進(jìn)入門廳的乘客數(shù)、離開(kāi)門廳的乘客數(shù)及層間移動(dòng)的乘客數(shù)等。通常將測(cè)試對(duì)象建筑的5min 內(nèi)客流特征數(shù)據(jù)作為一個(gè)樣本點(diǎn)進(jìn)行采集。對(duì)采集的較長(zhǎng)時(shí)間（如一周）內(nèi)的數(shù)據(jù)進(jìn)行聚類分析，得到近期內(nèi)的主要電梯交通模式。

2 粒子群優(yōu)化算法介紹

粒子群算法（Particle Swarm Optimization，PSO）是在智能計(jì)算領(lǐng)域中除了蟻群算法、魚(yú)群算法之外的另一種基于群體智能的優(yōu)化算法。在PSO 算法中每個(gè)粒子都對(duì)應(yīng)著優(yōu)化問(wèn)題的一個(gè)潛在解，同時(shí)每個(gè)粒子都有一個(gè)由適應(yīng)度函數(shù)決定的適應(yīng)度值（適應(yīng)度函數(shù)由優(yōu)化的目標(biāo)函數(shù)構(gòu)造），粒子的速度決定了粒子移動(dòng)的方向和距離。

PSO 的工作過(guò)程是：初始化時(shí)隨機(jī)得到一群粒子（優(yōu)化問(wèn)題的隨機(jī)解），然后通過(guò)迭代尋找最優(yōu)解。在每一次迭代中，粒子通過(guò)跟蹤兩個(gè)“極值”來(lái)更新自己。一個(gè)極值是粒子本身所找到的最優(yōu)解，稱作個(gè)體極值（pBest）；另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，稱作全局極值（gBest）。在每次迭代中找到這兩個(gè)最優(yōu)解后就可以根據(jù)如下的公式來(lái)更新自己的速度和位置：

其中：idV 表示第i 個(gè)粒子在第d 維變量上的速度，ω 為慣性權(quán)重，1c 和2c 是學(xué)習(xí)參數(shù)，

rand（）是定義在0-1 間的隨機(jī)數(shù)。

需要說(shuō)明的是，慣性權(quán)重ω 體現(xiàn)的是粒子繼承先前速度的能力，一個(gè)較大的慣性權(quán)重有利于全局搜索，而一個(gè)較小的慣性權(quán)重更便利與局部搜索。因此為了更好的平衡算法的全局和局部搜索能力，使用線性遞減慣性權(quán)重的方法。

3 基于粒子群的迭代自組織數(shù)據(jù)分析算法（ISODATA）的聚類算法

3.1 k 均值聚類算法的數(shù)學(xué)描述

并且使得離散度評(píng)價(jià)函數(shù)

達(dá)到最優(yōu)，其中 Zj為第j 個(gè)聚類中心，d ( Xi, Zj)為第j 個(gè)聚類中的樣本 Xi到其聚類中心的距離，一般采用歐氏距離。因此，聚類評(píng)價(jià)函數(shù) Jc就是樣本集中各個(gè)樣本到其對(duì)應(yīng)的聚類中心距離的總和。

3.2 迭代自組織數(shù)據(jù)分析算法（ISODATA）

ISODATA 算法的步驟如下：

（1）初始化控制參數(shù)和聚類中心：K 為預(yù)期聚類數(shù)，L 為在每次迭代中最多可進(jìn)行的合并操作數(shù)，itmax為最大循環(huán)數(shù)，Nmin為聚類中所允許的最少樣本數(shù)，dcmin為所允許的兩個(gè)聚類中心間的最小距離，smax為類內(nèi)各個(gè)特征分量的相對(duì)標(biāo)準(zhǔn)差上限，dmax為樣本到聚類中心所允許的最大距離。并且初始化聚類中心。

（2）按照最短距離原則將樣本集中的各個(gè)樣本進(jìn)行分類并且檢查每一類中的樣本數(shù)是否小于Nmin，若某類內(nèi)元素過(guò)少則刪除該類，并將落在其中的樣本重新分類。計(jì)算分類后的參數(shù)：聚類中心和改組聚類中心對(duì)應(yīng)的誤差平方和。

（3）判斷停止、分裂或是合并：設(shè)當(dāng)前迭代次數(shù)和聚類中心數(shù)分別為it 和cnum。若迭代次數(shù)達(dá)到規(guī)定的最大次數(shù)（it＞itmax）或聚類算法收斂，結(jié)束聚類過(guò)程；若cnum＜k/2 或k/2＜cnum＜2k 且it 為奇數(shù)，迭代次數(shù)it+1 并轉(zhuǎn)至(4)進(jìn)行分裂操作；若cnum＞2k或k/2＜cnum＜2k 且it 為偶數(shù)，迭代次數(shù)it+1 轉(zhuǎn)至(5)進(jìn)行合并操作。

（4）計(jì)算每類內(nèi)中樣本各分量的最大相對(duì)標(biāo)準(zhǔn)差s，若s＞smax同時(shí)滿足下列條件之一則對(duì)該類進(jìn)行分裂操作：①該類中樣本總數(shù)超過(guò)規(guī)定值的一倍以上，即該類中的數(shù)據(jù)點(diǎn)過(guò)多；②當(dāng)前聚類中心數(shù)cnum＜k/2。分裂時(shí)，在待分裂的聚類中心對(duì)應(yīng)分量上分別加上和減去k2*s 得到兩個(gè)新的聚類中心，其中0＜k2＜1。

（5）計(jì)算各聚類中心間的距離dij，將滿足dij＜dcmin的各類合并，若需合并類數(shù)N＞L 則只合并前L 個(gè)。合并時(shí)，將待合并兩類的樣本劃分到一類求出重心即得到新的聚類中心。

3.3 粒子群ISODATA 算法的編碼與適應(yīng)度函數(shù)的設(shè)計(jì)

為進(jìn)行粒子群優(yōu)化，每個(gè)粒子還具有對(duì)應(yīng)維數(shù)的速度和適應(yīng)度值。由于樣本向量的維數(shù)是d ，因此對(duì)于第i 個(gè)粒子的位置是Ki× d 維變量，。需要說(shuō)明的是在粒子群ISODATA 算法中每個(gè)粒子的聚類中心數(shù)Ki不是定值，而是隨著聚類的過(guò)程而變化的。

綜上，群中粒子采用如下結(jié)構(gòu)進(jìn)行編碼：

其中Zi和Vi都是d 維列向量分別代表粒子的位置和速度，F(xiàn)(X)為該粒子的適應(yīng)度函數(shù)。

在粒子群算法中適應(yīng)度通常與結(jié)果的優(yōu)劣呈正相關(guān)，而在ISODATA 等均值聚類算法中其分類評(píng)價(jià)函數(shù)通常與分類結(jié)果的好壞成負(fù)相關(guān)。為了統(tǒng)一這兩個(gè)指標(biāo)，將粒子的適應(yīng)度值取為

其中：C 是正常數(shù)，具體取值根據(jù)實(shí)際情況給定，eps 是十分微小的正數(shù)，以保證在 Jci= 0時(shí) F ( Xi)為有限值。

3.4 基于粒子群ISODATA 算法的交通流模式識(shí)別

（1）初始化粒子群：將各粒子隨機(jī)的分配到K（預(yù)期聚類數(shù)）個(gè)聚類中，采用迭代自組織數(shù)據(jù)分析算法（ISODATA）進(jìn)行一次聚類，將聚類結(jié)果作為一個(gè)粒子的位置并初始化粒子的速度。反復(fù)進(jìn)行N 次，完成粒子群的初始化。根據(jù)2 節(jié)中對(duì)電梯交通流特點(diǎn)的分析，在實(shí)際算法和數(shù)據(jù)采集中，數(shù)據(jù)點(diǎn)為 xi＝( xi1, xi2, xi3)，其中 xi1, xi2,xi3分別表示第i 個(gè)采樣時(shí)間段內(nèi)，進(jìn)入門廳的客流量、走出門廳的客流量及層間的客流量。

（2）更新每個(gè)粒子的個(gè)體極值：計(jì)算每個(gè)粒子的適應(yīng)度值 F ( Xi)，若 F ( Xi)好于其經(jīng)歷最好位置pBest 的適應(yīng)度值pFBest，更新個(gè)體極值pBest 和其對(duì)應(yīng)的適應(yīng)度值pFBest，即令

pBest =Xi, pFBest＝F ( Xi)；否則二者的值保持不變。

（3）更新粒子群的全局極值：若 F ( Xi)好于整個(gè)粒子群經(jīng)歷最好位置gBest 的適應(yīng)度值gFBest，更新粒子群的全局極值gBest 和其對(duì)應(yīng)的適應(yīng)度值gFBest，即令 gBest =Xi,g FBest =F ( Xi)；否則二者的值保持不變。

（4）更新群中粒子的位置和速度：根據(jù)式（1）和（2）逐個(gè)更新群中粒子的速度和位置。

新粒子群的迭代自組織數(shù)據(jù)分析（ISODATA）優(yōu)化：將新得到的群中粒子，采用迭代自組織數(shù)據(jù)分析算法（ISODATA）進(jìn)行一次聚類，將聚類結(jié)果作為新的粒子位置。

（5）如果達(dá)到終止條件（得到足夠好的位置或達(dá)到最大迭代次數(shù)），則結(jié)束優(yōu)化過(guò)程，否則轉(zhuǎn)步驟（2）。

4 仿真結(jié)果及實(shí)驗(yàn)

圖1 某辦公大樓電梯交通流統(tǒng)計(jì)數(shù)據(jù)

運(yùn)用基于粒子群的ISODATA 算法對(duì)該辦公大樓的電梯交通流進(jìn)行數(shù)據(jù)分析，根據(jù)已知采集的數(shù)據(jù)的數(shù)字特征（均值、平方差、分布情況等）和辦公大樓的實(shí)際功用對(duì)算法的參數(shù)進(jìn)行如下設(shè)置：粒子群數(shù) N = 12，初始慣性權(quán)重 wsatrt＝0.9預(yù)期，最小慣性權(quán)重 wend＝0.4，學(xué)習(xí)參數(shù) c1＝常數(shù) C＝1, eps＝10-10；預(yù)期聚類中心數(shù) K = 5，每次迭代中最多合并操作次數(shù) L= 3，最大循環(huán)次數(shù)itmax=1000，聚類中最少樣本數(shù)Nmin=10，兩個(gè)聚類中心間允許的最小距離dcmin=10，類內(nèi)各個(gè)特征分量的標(biāo)準(zhǔn)差上限smax=5，樣本到聚類中心所允許的最大距離dmax=30。

通過(guò)更改預(yù)期聚類數(shù)K，驗(yàn)證了該算法在確定聚類數(shù)目上有一定的自主能力。在其他參數(shù)保持不變的情況下，當(dāng)K 取3-8 之間的值時(shí)，得到的實(shí)際聚類數(shù)均為5，可見(jiàn)該算法在選擇聚類樹(shù)木上有一定的自主性。同樣的，更改聚類中最少樣本數(shù)Nmin、類內(nèi)各個(gè)特征分量的標(biāo)準(zhǔn)差上限smax等均影響實(shí)際的聚類結(jié)果。最大循環(huán)次數(shù)itmax、粒子種群規(guī)模N 等影響著算法的速度。

5 結(jié)論

基于粒子群的迭代自組織分析算法，易于編程實(shí)現(xiàn)，運(yùn)算速度快，同時(shí)具有一定的全局和局部搜索能力，分類準(zhǔn)確且有一定的自主性。該算法具有較強(qiáng)的實(shí)用性和適應(yīng)性，能夠顯著提高電梯群控系統(tǒng)的工作效率。

圖2 粒子群ISODATA 聚類算法結(jié)果

[1] 楊廣全,朱昌明,王向紅等.基于粒子群 K 均值聚類算法的電梯交通模式識(shí)別[J]控制與決策, 2007, 22(10)1139-1142

[2] 丁蕊,董紅斌,馮憲彬.用于分類問(wèn)題的粒子群優(yōu)化遺傳算法[J]計(jì)算機(jī)工程2009,35(17)201-203