基于粒子群ISODATA 電梯交通模式識別

蔡麗霞

（河南工業職業技術學院網絡管理中心,河南南陽,473000)

1 電梯交通流的模式及數據采集、分析

電梯交通流有著其自身的特點，可以用電梯群服務系統的乘客數、乘客出現的周期和分布情況來描述。電梯交通流的特征往往隨著高層建筑用途的不同而有所差異，對于典型的辦公建筑，電梯交通流通常具有以下幾種主要模式：上行高峰模式、下行高峰模式、雙路模式、平衡的層間模式以及空閑模式等。在采集電梯交通流數據時，通常需要統計的交通流特征數據有：單位時間內進入門廳的乘客數、離開門廳的乘客數及層間移動的乘客數等。通常將測試對象建筑的5min 內客流特征數據作為一個樣本點進行采集。對采集的較長時間（如一周）內的數據進行聚類分析，得到近期內的主要電梯交通模式。

2 粒子群優化算法介紹

粒子群算法（Particle Swarm Optimization，PSO）是在智能計算領域中除了蟻群算法、魚群算法之外的另一種基于群體智能的優化算法。在PSO 算法中每個粒子都對應著優化問題的一個潛在解，同時每個粒子都有一個由適應度函數決定的適應度值（適應度函數由優化的目標函數構造），粒子的速度決定了粒子移動的方向和距離。

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

其中：idV 表示第i 個粒子在第d 維變量上的速度，ω 為慣性權重，1c 和2c 是學習參數，

rand（）是定義在0-1 間的隨機數。

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

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

3.1 k 均值聚類算法的數學描述

并且使得離散度評價函數

達到最優，其中 Zj為第j 個聚類中心，d ( Xi, Zj)為第j 個聚類中的樣本 Xi到其聚類中心的距離，一般采用歐氏距離。因此，聚類評價函數 Jc就是樣本集中各個樣本到其對應的聚類中心距離的總和。

3.2 迭代自組織數據分析算法（ISODATA）

ISODATA 算法的步驟如下：

（1）初始化控制參數和聚類中心：K 為預期聚類數，L 為在每次迭代中最多可進行的合并操作數，itmax為最大循環數，Nmin為聚類中所允許的最少樣本數，dcmin為所允許的兩個聚類中心間的最小距離，smax為類內各個特征分量的相對標準差上限，dmax為樣本到聚類中心所允許的最大距離。并且初始化聚類中心。

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

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

（4）計算每類內中樣本各分量的最大相對標準差s，若s＞smax同時滿足下列條件之一則對該類進行分裂操作：①該類中樣本總數超過規定值的一倍以上，即該類中的數據點過多；②當前聚類中心數cnum＜k/2。分裂時，在待分裂的聚類中心對應分量上分別加上和減去k2*s 得到兩個新的聚類中心，其中0＜k2＜1。

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

3.3 粒子群ISODATA 算法的編碼與適應度函數的設計

為進行粒子群優化，每個粒子還具有對應維數的速度和適應度值。由于樣本向量的維數是d ，因此對于第i 個粒子的位置是Ki× d 維變量，。需要說明的是在粒子群ISODATA 算法中每個粒子的聚類中心數Ki不是定值，而是隨著聚類的過程而變化的。

綜上，群中粒子采用如下結構進行編碼：

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

在粒子群算法中適應度通常與結果的優劣呈正相關，而在ISODATA 等均值聚類算法中其分類評價函數通常與分類結果的好壞成負相關。為了統一這兩個指標，將粒子的適應度值取為

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

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

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

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

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

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

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

新粒子群的迭代自組織數據分析（ISODATA）優化：將新得到的群中粒子，采用迭代自組織數據分析算法（ISODATA）進行一次聚類，將聚類結果作為新的粒子位置。

（5）如果達到終止條件（得到足夠好的位置或達到最大迭代次數），則結束優化過程，否則轉步驟（2）。

4 仿真結果及實驗

圖1 某辦公大樓電梯交通流統計數據

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

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

5 結論

基于粒子群的迭代自組織分析算法，易于編程實現，運算速度快，同時具有一定的全局和局部搜索能力，分類準確且有一定的自主性。該算法具有較強的實用性和適應性，能夠顯著提高電梯群控系統的工作效率。

圖2 粒子群ISODATA 聚類算法結果

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

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