快速公交線路選線決策規(guī)則獲取方法

湯旻安, 王曉明, 李 瀅

(1. 蘭州交通大學 自動化與電氣工程學院,蘭州 730070;2. 蘭州理工大學 機電工程學院,蘭州 730050)

快速公交線路選線決策規(guī)則獲取方法

湯旻安*1,2, 王曉明2, 李 瀅1

(1. 蘭州交通大學 自動化與電氣工程學院,蘭州 730070;2. 蘭州理工大學 機電工程學院,蘭州 730050)

城市快速公交線路選線決策規(guī)則的優(yōu)劣直接關系到公交線路的客運能力能否滿足城市客流的需求.本文根據(jù)現(xiàn)有公交線路的交通調查客運能力數(shù)據(jù),結合 BRT 線路的“大運量、快速性”特點,發(fā)現(xiàn)并提取隱藏在其中的重要選線決策規(guī)則.針對選線決策問題中的多變量因素具有不確定性的特點,提出一種基于模糊神經網絡實現(xiàn)決策規(guī)則獲取的方法.給出了基于模糊推理的 BP 神經模糊系統(tǒng)結構及算法,通過神經網絡提高其學習能力,采用 GA 改進的算法思想克服 BP 神經網絡存在的局限.最后通過實例研究驗證了模型和算法的有效性,結果可為公共交通線路選線、規(guī)劃方案的制定提供參考.

智能交通;線路選線;遺傳神經模糊網絡;快速公交;決策規(guī)則

1 引 言

快速公交系統(tǒng)(Bus Rapid Transit,BRT),是一種介于快速軌道交通(Rapid Rail Transit,RRT) 與常規(guī)公交(Normal Bus Transit,NBT) 之間的新型公共客運系統(tǒng),是一種大運量交通方式,通常也被稱作“地面上的地鐵系統(tǒng)”.其典型的特點突出了“大運量、快速性、舒適性”.城市快速公共交通線路建設中的選線多根據(jù)城市區(qū)域規(guī)劃或既有城市路網中的交通主干道來考慮選擇,但不同于 NBT 選線, NBT 線路一般為突出區(qū)域交通“連通性”,“大運量、快速性”不作為主要考慮因素.好的線路選線決策能使公共交通發(fā)揮更大的效用[1,2].根據(jù)現(xiàn)行既有 NBT 線路的交通調查客運能力數(shù)據(jù),發(fā)現(xiàn)并提取隱藏在其中的 BRT 重要選線決策規(guī)則.提取決策規(guī)則是數(shù)據(jù)挖掘中的一項重要內容,它從已知數(shù)據(jù)中挖掘一定規(guī)則(規(guī)則集)來描述各類數(shù)據(jù)的特征,并使用獲得的規(guī)則,預測未知數(shù)據(jù)的類別,進行知識發(fā)現(xiàn)和模式識別.獲取知識、運用知識進行管理與決策一直是制約城市交通管理與控制的瓶頸問題[3].在對于決策規(guī)則的獲取中,文獻[4,5]提出了基于粗糙集理論的最簡決策規(guī)則挖掘算法.文獻[6,7]引入模糊聚類,提出實現(xiàn)規(guī)則決策的層次型模糊神經網絡.

本文研究快速公交線路選線決策規(guī)則提取問題.根據(jù)現(xiàn)行公共汽車線路的道路客運能力交通調查數(shù)據(jù),結合快速公交線路要求的“大運量、快速性”特點需求,提取出快速公交線路選線的決策規(guī)則.提出利用模糊邏輯系統(tǒng)對不定量變量處理的優(yōu)點,通過神經網絡改進其學習能力不足的缺點,采用 GA 改進克服 BP 神經網絡局限性.采用集成優(yōu)化算法,建立決策規(guī)則獲取模型,對模型進行改進優(yōu)化,并設計相應的求解算法.

2 神經模糊系統(tǒng)模型

模糊邏輯系統(tǒng)技術與神經網絡技術相結合,有神經模糊系統(tǒng) NFS 和模糊神經系統(tǒng) FNN 兩種形式[8,9].神經模糊系統(tǒng)是按照模糊邏輯系統(tǒng)的運算步驟分步分層構建的.基于 BP 神經網絡的Mamdani模糊系統(tǒng)結構如圖1 所示.第一層,輸入層;第二層,計算第一層各輸入分量屬于各語言變量值模糊集合的隸屬函數(shù),每個節(jié)點代表一個語言變量值;第三層,每個節(jié)點代表一條模糊規(guī)則,用來匹配模糊規(guī)則前件,計算出每條規(guī)則的適配度;第四層,實現(xiàn)第三層適配度的歸一化運算,節(jié)點數(shù)與第三層相同;第五層,輸出層,即為模糊判決層,實現(xiàn)從模糊到清晰化的計算.

圖1 基于 BP 神經網絡的 Mamdani模糊系統(tǒng)結構Fig.1 Structure of Mamdani fuzzy system based on BP neural network

系統(tǒng)的輸出如式(1)所示:

3 神經模糊系統(tǒng)的學習算法

由圖1知,系統(tǒng)從本質上是一種多層前饋神經網絡,參照 BP 網絡的誤差反傳方法來設計、調整參數(shù)的學習算法,假設系統(tǒng)的各輸入分量的模糊分割數(shù)是預先確定的,那么需要學習和調整的參數(shù)包括連接權W以及第二層的隸屬度函數(shù)的尺寸信息.選用 Gaussian 函數(shù)作為隸屬度函數(shù)則包括各個隸屬度函數(shù)的中心值

按照 BP 網絡誤差反傳的方法設計、調整參數(shù)的學習算法.設誤差代價函數(shù)如式(2)所示:

式中 N表示系統(tǒng)的輸出數(shù)量;P表示訓練模式數(shù);tpi和 ypi分別表示訓練輸入模式 p 在網絡的第 i個節(jié)點的期望輸出和實際計算輸出.利用誤差反傳算法來計算然后利用一階梯度尋優(yōu)算法來調節(jié)

4 改進的神經模糊系統(tǒng)

4.1 文獻NFS模型研究

針對上述的神經Mamdani模糊系統(tǒng)的缺點——精度不高、訓練時間長,文獻提出了一種改進的網絡結構,改進的網絡有四層,包括輸入層、隸屬函數(shù)生成層、推理層及模糊判決層[10].MIMO 的模糊規(guī)則可分解為多個 MISO 的模糊規(guī)則.不失一般性,以兩輸入一輸出的系統(tǒng)為例,系統(tǒng)結構如圖2所示.

圖2 改進的神經 Mamdani模糊系統(tǒng)結構Fig.2 Improved neural Mamdani fuzzy system structure

如圖2 所示,改進的網絡輸出如式(3)所示:

研究發(fā)現(xiàn),系統(tǒng)輸出式(3)有別于式(1)表示的系統(tǒng)輸出,兩模型之間既有聯(lián)系也有本質上的區(qū)別.因而該模型是一種新的改進的模糊神經網絡系統(tǒng),運用 Stone-Weirstrass 定理容易證明該模型具有全局逼近性質[10].

分析發(fā)現(xiàn),上述改進的結構模型仍存在以下幾個方面的不足:

(1) 第二層模糊隸屬度生成函數(shù)子空間的劃分和 Gaussian 函數(shù)參數(shù) (cij,ρij) 依賴于人的經驗,存在很大主觀性;

(2) 基于梯度下降法的傳統(tǒng) BP 參數(shù)學習方法存在不足;

(3) 推理層的結論數(shù)是根據(jù) K-means 聚類的方法對樣本聚類后得到的,是分步進行的,在網絡中不能根據(jù)樣本特征及網絡性能自動地調整規(guī)則結論數(shù);

(4) K-means 聚類方法自身也存在不足[11,12,13].

綜上所述,在考慮上述改進的基礎上,不對推理層的結論數(shù)進行異步 K-means 聚類處理,而是通過對模型的學習算法進行改進.提出采用 GA 與BP 算法的集成混合學習算法,根據(jù)網絡的性能對模糊神經網絡連接權值和 Gaussian 隸屬函數(shù)參數(shù)(cij,ρij) 同時進行優(yōu)化的方法.

4.2 GA 改進的 NFS 模型建立

4.2.1 參數(shù)的確定及編碼方案

用 GA 優(yōu)化模糊神經網絡時,需要同時優(yōu)化網絡的規(guī)則數(shù)、相應的權值、每個輸入變量對應模糊子集的隸屬度函數(shù)參數(shù)值.

假定系統(tǒng)有 N個輸入變量,每個變量在其論域上被劃分為 M 個模糊子集.那么網絡第二層的節(jié)點數(shù)目為 N·M 個,網絡第三層的節(jié)點數(shù)目為MN個,即表示該模糊系統(tǒng)最多有 MN條規(guī)則.用矩陣 WN·M表示第二層與第三層的節(jié)點連接情況,其中 wij=0,表示節(jié)點不相連;wij=1,表示節(jié)點相連.因為 WN·M表示各個輸入變量所屬模糊子集間的相互匹配關系,而同一變量的各個模糊子集不能匹配成一條規(guī)則,所以 WN·M中有“1”的個數(shù)最多為 N· MN,此時代表系統(tǒng)取完全規(guī)則數(shù)的情形.相應連接權值 (w1,w2,…,wm) 隨 WN·M中“1” 的變化而變化.

在使用 GA 時,需要確定編碼參數(shù)的變化范圍,對于每個輸入變量 xi,其模糊劃分數(shù)為 M,其隸屬度函數(shù)的中心、寬度賦初值由下列的式(4)-式(8)給出.

由此,給定 c1(i) 的取值范圍為

ρ1(i) ≥ 0 取值范圍為

[0,α·ρ1(1)];[0,α·ρ2(2)];…;[0,α·ρ1(M)]式中 α ＞ 1 用來控制 ρ1(i) ≥ 0 的變化范圍.

對參數(shù)的編碼使用二進制編碼形式.GA 的一個染色體對應一個待求解問題的解,算法中每個染色體分為 4 個基因段,Chr=[c,ρ,W,w].

4.2.2 適應度函數(shù)

適應度函數(shù)表示為

式中 E 為神經網絡的輸出MAE;B=N·MN為最大規(guī)則數(shù);R 為模糊神經網絡規(guī)則數(shù),即矩陣WN×·M中有“1” 的行個數(shù),且每個個體中至少有 1條模糊規(guī)則前件,即 R ≥ 1.這樣做的目的是在保證樣本逼近精度的前提下使網絡的結構盡量簡單.

4.2.3 遺傳操作設計

選擇算子,采用優(yōu)勢保留與輪盤選擇法作為選擇算子.其中,M=種群×20%.

交叉算子,采用兩點交叉算子,對實數(shù)編碼基因段采用實值重組方式的中間重組方式進行交叉.本文采用一種自適應Pc和Pm方法,用適合度函數(shù)來衡量算法的收斂狀況,其表達式為:,其中分別為群體中的最大適應度和平均適合

-度;fmax-f體現(xiàn)了群體的收斂程度;k1,k2≤ 1.0為常數(shù).

變異算子,按照變異概率在群體中隨機選出變異個體,對于被選中的個體,在字長范圍內按均勻分布隨機選出變異的字符.

4.3 GA 改進 FNN 算法步驟

利用 GA 進行網絡結構和參數(shù)優(yōu)化,應用 BP算法進行快速局部搜索,GA 保證全局優(yōu)化.求解具體方法如下:

輸入 給定現(xiàn)有多條公交線路的客運能力交通調查數(shù)據(jù)及各條線路基于 BRT“大運量、快速性”需求功能要求的專家決策給定的線路優(yōu)良度;該輸入的給定是采用常規(guī)公交系統(tǒng)(NBT)的基礎數(shù)據(jù),按照 BRT 選線的特殊性要求而分析得到.

輸出 模糊神經網絡規(guī)則數(shù)、相應連接權值、隸屬度函數(shù)參數(shù)(cij, ρij) 值.

Step1樣本數(shù)據(jù)的預處理,將樣本數(shù)據(jù)歸一化處理.

Step2初始化GA相關參數(shù):種群大小pop_size;最大遺傳代數(shù) max_gen;交叉概率 Pc參數(shù) k1、變異概率 Pm參數(shù) k2.

Step3結合具體問題根據(jù)染色體編碼方案Chr=[c,ρ,W,w],生成隨機初始種群,將每個個體表示為染色體的基因編碼.

Step4計算個體的適應度值.

Step5對種群進行遺傳操作,并判斷 W 基因編碼中有“1”的行數(shù),如果行數(shù)為 0,則隨機將 W中某一基因位賦為“1”,否則轉第向 6 步.

Step6在一定的規(guī)則個數(shù)下對每個個體實施 BP 算法,調整參數(shù) c 、 ρ 、 w,獲得 Chr*=[c, ρ,W,w],計算適應度值.

Step7令 gen=gen+1, 如 果 gen ＜max_gen,轉向第 5 步進行迭代操作;否則停止迭代,輸出最優(yōu)個體 best_chr,則得到最優(yōu)的網絡的規(guī)則數(shù)與相應的權值及每個輸入變量對應模糊子集的隸屬度函數(shù)參數(shù)(cij,ρij) 值.

5 實例研究

5.1 研究對象及樣本數(shù)據(jù)

學習樣本及數(shù)據(jù)采用文獻《蘭州市綜合交通規(guī)劃—機動車 OD·客運交通·停車調查報告》中的數(shù)據(jù).依據(jù)現(xiàn)行公共汽車 67 條線路對城市快速公交干線選線進行模糊規(guī)則提取實例研究,根據(jù)BRT“大運量、快速性”的特點,在此選擇現(xiàn)有公交線路車速屬性和客流量屬性作為系統(tǒng)輸入.分別為高峰期上行(1)、高峰期下行(2)、平峰期上行(3)、平峰期下行(4)共4種車速屬性數(shù)據(jù)和單車單向全線高峰期上行(5)、高峰期下行(6)、平峰期上行(7)、平峰期下行(8)共 4 種客流量屬性,此 8種輸入數(shù)據(jù),用來提取快速公交干線選址的模糊規(guī)則.在 NFS 網絡條件下,首先對數(shù)據(jù)進行預處理,歸一化處理后的數(shù)據(jù)如表1所示.

表1 用于規(guī)則獲取的現(xiàn)有公交線路數(shù)據(jù)Table1 Used for rule acquisition of the existing data from bus lines

5.2 試驗各種參數(shù)選擇

利用 Matlab R2010a 及神經網絡工具箱、遺傳算法優(yōu)化工具箱進行算例計算.GA 相關參數(shù)的設置為: 種 群 規(guī) 模 pop_size=30; 最大迭代次數(shù)max_gen=200,k1=0.5,k2=0.1,N=8,M=3, W 的位數(shù)為 52 488.同時,在保證參數(shù) c 、ρ保留 4位小數(shù)精度的二進制位長.BP 參數(shù)調整的步驟為200 步.

受遺傳算法的隨機性影響,每次運行得到的結果均不一樣,對多次計算選擇得到優(yōu)化后的一組(cij, ρij) 參數(shù)如表2 所示.

表2 一組模糊規(guī)則參數(shù)表Table2 Fuzzy rules parameter table

由表2 可知,GA-FNN 將每個輸入分量和輸出分為三個模糊集合.根據(jù)計算結果,表中數(shù)據(jù)各輸入分量的隸屬度函數(shù)圖形如圖3、圖4 所示.

圖3 車速隸屬度函數(shù)Fig.3 Membership function of speed

圖4 流量隸屬度函數(shù)Fig.4 Membership function of vehicle flow rate

5.3 模糊規(guī)則提取

如前 5.2 的結果,選取提取的 2 條模糊規(guī)則如表3所示.

表3 提取的決策規(guī)則Table3 Extraction of decision rules

5.4 提取規(guī)則對比及分析

在上述數(shù)據(jù)的基礎上,將算法改進前后獲得的決策規(guī)則進行對比如表4所示.

表4 提取的決策規(guī)則對比Table4 Comparison of extraction decision rules

為進一步判定獲取的決策規(guī)則對選線的模式識別,根據(jù)表1的各條現(xiàn)行線路客運能力數(shù)據(jù),進行線路篩選可獲得快速公交線路.結合研究對象的實際路網狀況,可獲得快速公交線路路由為途經 103、105、109、124、33、50、56、58號線路的路由為最優(yōu).

6 研究結論

本文根據(jù) BRT 線路的“大運量、快速性”特點,以常規(guī)公交線路的客運能力“客流量屬性、車速屬性”交通調查數(shù)據(jù)為基礎,研究了快速公交線路選線決策規(guī)則的獲取方法,針對 BRT 選線決策問題中的多變量(客流量、車速)因素不確定的特點,提出一種基于模糊神經網絡實現(xiàn)決策規(guī)則獲取的方法,并給出了基于模糊推理的 BP 神經模糊系統(tǒng)結構及算法.通過神經網絡提高其學習能力,采用GA 改進的算法思想克服 BP 神經網絡存在的局限,設計了基于遺傳改進的模糊神經網絡算法的求解方法.并對該模型進行了實例驗證和分析.結果表明,客流量、車速因素的考慮將對 BRT 線路選線結果產生明顯影響,因此該模型用于 BRT 選線問題是可行的.

[1] LI Q,WANG Y J,ZHOU Y.Readjustment effect analysis of public bus network in Beijing[J].Journal of Transportation Systems Engineering and Information Technology,2008,8(2):27-33.

[2] 文國瑋.城市交通與道路系統(tǒng)規(guī)劃[M]. 北京:清華大學出版社,2009.[WEN G W.The urban traffic& road system planning[M]. Beijing: Tsinghua University Press,2009.]

[3] 劉銳,嚴寶杰,黃志鵬.城市公共交通網絡的復雜性分析[J].交通運輸系統(tǒng)工程與信息,2009,9(3): 17-22.[LIU R,YAN B J,HUANG Z P.Complexity analysis of urban public transit network[J].Journal of Transportation Systems Engineering and Information Technology,2009,9(3):17-22.]

[4] 錢進,孟祥萍,劉大有,等.一種基于粗糙集理論的最簡決策規(guī)則挖掘算法[J].控制與決策,2007,22 (12):1368-1372.[QIAN J,MENG X P,LIU D Y, et al.A mining algorithm for concise decision rules based on rough setstheory [J]. Controland Decision,2007,22(12):1368-1372.]

[5] 鄂旭,邵良杉,張毅智,等. 一種基于粗糙集理論的規(guī)則提取方法[J]. 計算機科學,2011,38(1): 232-235.[E X,SHAO L S,ZHANG Y Z,et al. Method of rule extraction based on rough set theory [J].Computer Science,2011,38(1):232-235.]

[6] 杜建鳳,宋梅,張璋,等. 模糊神經網絡在決策專家系統(tǒng)中的研究與應用[J].系統(tǒng)工程與電子技術, 2002,24(2):45-47,53.[DU J F,SONG M, ZHANG Z,et al.Research and application of fuzzy neural network in decision expert system[J].Systems Engineering and Electronics,2002,24(2):45-47,53.]

[7] 許翔,張東波,王耀南,等. 基于論域空間模糊劃分的粗集神經網絡[J].計算機工程,2010,36(21): 199-201.[XU X,ZHANG D B,WANG Y N,et al. Rough set neural network based on fuzzy partition in universal space[J].Computer Engineering,2010,36 (21):199-201.]

[8] Ishigami Hideyuki.Structure optimization of fuzzy neural network by genetic algorithm[J].Fuzzy Sets and Systems,1995,71(3):257-264.

[9] Tahmasebi Pejman.A hybrid neural networks-fuzzy logic-genetic algorithm for grade estimation[J]. Computers and Geosciences,2012,4:18-27.

[10] Leung FHF.An improved genetic-algorithm-based neural-tuned neural network[J].International Journal of Computational Intelligence and Applications,2008, 7(4):469-492.

[11] Malek Hamed,Ebadzadeh Mohammad Mehdi,Rahmati Mohammad.Three new fuzzy neural networks learning algorithms based on clustering,training error and genetic algorithm[J].Applied Intelligence,2012, 37(2):280-289.

[12] WANG Y Q.Application of elevator group control system based on genetic algorithm optimize BP fuzzy neuralnetwork[C]//Proceedings ofthe World Congress on IntelligentControland Automation, 2008,8702-8705.

[13] GERETTI Luca.The synthesis of a stochastic artificial neural network application using a genetic algorithm approach[J].Advances in Imaging and Electron Physics,2011,168:1-63.

Decision Rule Acquisition of Route Selection for Rapid Transit Line

TANG Min-an1,2,WANG Xiao-ming2,LI Ying1
(1.School of Automation and Electrical Engineering,Lanzhou Jiaotong University.,Lanzhou 730070,China; 2.School of Mechanical and Electronical Engineering,Lanzhou University of Technology,Lanzhou 730050,China)

Decision rule of route selection for rapid transit line determines the public transport effect. According to the current existing bus lines ability of passenger traffic survey data,combining with “ rapidity, mass transit” characteristics of BRT lines,this paper is to find and extract important decision rules of route selection,For the problem of route selection,it is required to acquire evolution rule of system status from the changes of multiple environment variable factors,and all kinds of factors are of “ fuzziness” uncertainty characteristics.FLS has the advantages of processing non-quantitative variable,but has the disadvantage of deficient learning capability.The BP neural fuzzy system structure and algorithm is given based on fuzzy inference,to improve its learning capability.Meanwhile,in order to overcome the existing limitations of BP neural network,it puts forward the thought of algorithm improved on the basis of GA.The model and effectiveness of the algorithm are clarified by computational experiments.The results can provide reference for the transit route selection and planning.

intelligent transportation;route selection;genetic neural fuzzy network;rapid transit; decision rule

1009-6744(2014)01-0158-08

U491.1

A

2013-06-19

2013-08-03錄用日期:2013-08-16

國家自然科學基金項目(61263004);甘肅省自然科學研究基金項目(0803RJZA020);甘肅省科技支撐計劃項目(090GKCA009,1304GKCA023).

湯旻安(1973-),男,陜西勉縣人,博士,副教授.*通訊作者:tangminan@yahoo.com