基于改進蟻群算法的行駛工況構建及精度分析

劉炳姣, 石 琴, 仇多洋, 陳一鍇

(1.合肥工業大學 汽車與交通工程學院,安徽 合肥 230009; 2.合肥工業大學 機械工程學院,安徽 合肥 230009)

基于改進蟻群算法的行駛工況構建及精度分析

劉炳姣1, 石 琴1, 仇多洋2, 陳一鍇1

(1.合肥工業大學 汽車與交通工程學院,安徽 合肥 230009; 2.合肥工業大學 機械工程學院,安徽 合肥 230009)

文章以合肥市典型道路為例,選取5條城市道路進行數據采集,采用主成分分析與遺傳變異改進的蟻群算法(ant colony optimization,ACO)相結合的方法,構建了合肥市典型行駛工況。在劃分了運動學片段的基礎上,利用主成分分析法對13個運動學特征參數進行降維處理,以排名前3的主成分為聚類因子,用改進的蟻群算法對運動學片段樣本進行分類,通過組合類內運動學片段,完成代表性工況的構建,并對代表性工況進行精度分析。研究結果表明,與K-means聚類法、系統聚類法相比,改進的ACO能夠有效提高行駛工況的構建精度。

主成分分析;遺傳變異;蟻群算法(ACO);行駛工況(DC)

0 引 言

隨著科技的迅速發展,能源短缺和環境污染問題日益嚴重,節能減排已成為全世界的重大課題。汽車行駛工況(driving cycle,DC)是針對某一類型車輛在特定交通環境下用以描述車輛行駛特征的速度-時間曲線。它被用于評估車輛的污染物排放和燃油消耗狀況、新車型的技術開發等。

最近數十年,美國、歐洲、日本等國家和地區已根據其相應的車輛及交通狀況構建出各自的行駛工況。文獻[1]研究了馬爾可夫法在工況構建中的應用;文獻[2]用K-means聚類法構建了德黑蘭的行駛工況。近年來,國內學者在DC開發與構建方面也做了一些研究,文獻[3]研究了改進的短行程法在城市公交行駛工況中的應用;文獻[4]利用兩階段聚類法對西安市環衛車的行駛工況進行了研究;文獻[5]通過分析車輛速度及能耗狀態,構建了濟南市的行駛工況。

目前,構建行駛工況過程中使用最廣泛的是主成分分析和聚類分析相結合的方法,但因傳統聚類算法或對初始值過于敏感,或易陷入局部最優解,導致工況的構建精度過低。因此,本文對傳統蟻群算法(ant colony optimization,ACO)進行了改進,并以合肥市典型道路為例,利用主成分分析法與改進的ACO構建行駛工況,與常用的K-means算法和系統聚類法進行了精度對比,驗證了本文提出方法的有效性。

1 理論基礎

1.1 研究方法

主成分分析是數據降維的多元統計學方法,主要思想是通過對原始運動學片段的分析,提取少數幾個能綜合反映大部分特征參數信息的主成分,從而達到簡化數據的目的。聚類分析則用于反映不同類型片段的運動學特征[6]。

常見的聚類方法有K-means聚類法、系統聚類法、模糊聚類法、動態聚類法等。K-means算法容易陷入局部最優解,對唯一參數K值的選擇沒有固定規律可參考[7]。系統聚類法則難以確定結果類的數目,在聚類過程中產生的合并項和分裂項都無法回復,對結果有較大影響。而傳統的模糊聚類法對孤立點數據十分敏感,且因為其用迭代爬山式算法,所以易陷入局部極值點,得不到最優解[8]。

ACO 則是一種用來尋找優化路徑的機率型算法,但基本ACO在搜索過程中容易出現停滯現象,不利于發現更優解。若在ACO中引入遺傳算法中的變異因子,則可以很好地解決這一問題。

相比于其他算法,遺傳變異改進的ACO有如下優點:能夠在智能搜索的同時進行全局優化;有較強的穩健性和魯棒性,不會出現停滯現象;數據個體間不斷進行信息交換與傳遞,易于尋找更優解。

鑒于以上幾點,本文將主成分分析與遺傳變異的ACO相結合,用以構建行駛工況。

1.2 基本ACO

為解釋遺傳變異的ACO,首先需引入基本ACO的概念[9],簡述如下。

設N={1,2,…,n}為n個地點的集合,A={(i,j)|i,j∈N}為N中元素兩兩連接的集合,bi(t)表示t時刻位于地點i的螞蟻數,假設m只螞蟻都隨機選擇一個地點作為其出發地點,則有:

(1)

螞蟻在構建路徑的每一步中,按照隨機比例選擇下個要到達的地點,即

(2)

其中,i,j分別為起點和終點;τij(t)為時間t由i到j的信息素濃度;ηij=1/dij為能見度,是i,j兩點間距的倒數;allowedk為尚未訪問過的節點集合;α、β為常數,代表信息素和能見度的加權值。

每只螞蟻完成一次循環后,都會在其訪問過的路徑上留下相應信息素。

當所有螞蟻完成一次循環后,各路徑的信息素隨之更新,即

τij(t+n)=ρτij(t)+Δτij

(3)

(4)

其中,ρ(0<ρ<1)為信息殘留度;Δτij為迭代中邊ij的信息素增量。

ACO不斷地通過上述過程構建路徑和更新信息素,最終得以尋找到最優解。

1.3 遺傳變異改進的ACO

ACO作為一種本質并行的正反饋算法,個體間不斷進行信息傳遞和交流,易發現最優解。但基本ACO有一些缺陷,如搜索時間較長,很難在短時間內找到較好的路徑;當樣本數據量較大時會陷入局部最優解,過早收斂。

為解決這些問題,本文引入遺傳算法中變異率對基本ACO進行改進。具體方法如下:加入變異率p,并在所得最佳路徑內局部尋優;同時產生一個隨機數組,若數組中某值小于變異率p,則隨機改變其對應的路徑標記;隨后計算各樣本數據點到其相應的臨時聚類中心的最小歐式距離之和F′及本次迭代的最佳路徑,更新信息素,循環此過程直至尋找到最優解。

遺傳變異改進的ACO流程如圖1所示。

圖1 遺傳變異改進的ACO流程

2 試驗數據獲取與預處理

2.1 試驗與數據采集

為反映城市典型道路的車輛行駛工況,綜合考慮道路類型、車流密度、交叉口密度等因素,本文以合肥市區道路為例,選取5條(主干道的徽州大道、勝利路、明光路,次干道的桐城路,快速路的屯溪路)代表性的城市道路進行試驗及數據采集。

考慮時間因素對工況的影響,本次試驗采樣時間定為上午7:00—9:00,下午13:00—15:00、16:30—18:30,包括每天的早、晚高峰期及平峰期,持續4 d,含工作日及非工作日。試驗中某次行駛過程獲取的工況數據如圖2所示。

圖2 實測工況數據

試驗采用平均車流統計法,即駕駛員駕駛試驗車,在選定的時間和道路上隨平均車流行駛。數據使用OES-Ⅱ非接觸式光電速度傳感器采集,采集頻率為1 Hz,可獲得速度、加速度、路程以及時間等參數,最終得到4萬余組數據。

從圖2數據可以看出,車輛在行駛過程中會頻繁加速、減速、停車、啟動,為方便描述該過程,本文將整個行駛歷程劃分為多個數據單元,在此需引入運動學片段的概念。

2.2 運動學片段的劃分

一個運動學片段是指在速度時間變化曲線上,從上一個怠速狀態開始到下一個怠速狀態結束之間的運動學單元,如圖3所示。

圖3 運動學片段

參考國內外文獻,將試驗中采集到的數據按照以下原則進行運動學狀態定義。

(1) 勻速狀態。|a|<0.15 m/s2且v≠0的發動機連續工作狀態。

(2) 怠速狀態。a=0且v=0的發動機連續工作狀態。

(3) 加速狀態。a≥0.15 m/s2且v≠0的發動機連續工作狀態。

(4) 減速狀態。a≤-0.15 m/s2且v≠0的發動機連續工作狀態

以此為劃分規則,利用Matlab編程,對原始數據進行預處理,篩選得到126個有效的運動學片段。

2.3 運動學特征參數及參數矩陣

為準確描述各運動學片段,表征所用參數不可過少,否則會導致大量信息丟失;但參數過多,則會給分析過程增加不必要的難度和計算量。參考文獻[10-12]對運動學參數的選取,本文選取了加速比例Pa、減速比例Pd、勻速比例Pc、怠速比例Pi等13個能夠反映運動學片段特征的參數,以合理描述運動學片段。各運動學特征參數見表1所列。

以預處理階段得到的126個運動學片段及其特征參數為研究對象,得到樣本數×特征參數值的矩陣,見表2所列。

表1 運動學特征參數

注：平均運行速度指除怠速外的平均速度。

表2 運動學片段及其特征參數

2.4 主成分分析

主成分分析是利用降維思想,將多個參數轉換為少數綜合參數(即主成分)的過程。其中各主成分間沒有相關性,且都是原始參數的線性組合,從而不重疊地反映原始參數的大部分信息,以達到簡化問題的目的。

用SPSS軟件對126個運動學片段及其特征參數進行主成分分析,得到各主成分(用Mi表示,i=1,2,3,…,13)特征值的方差貢獻率及累計貢獻率,見表3所列。

表3 各主成分貢獻率

特征根是主成分影響力度的指標,代表引入該主成分后可解釋的原始變量的信息量。若特征根大于1,說明該主成分的解釋力度大于原變量的平均解釋力度,因此一般將特征根大于1、累計貢獻率大于85%作為主成分的納入標準。由表3可以看出,前3個主成分的特征根均大于1,且方差的累計貢獻率達到了90%,已足夠描述運動學片段的特征,因此本文選取排名前3的主成分進行分析。主成分表達式為:

Fi=ai1X1+ai2X2+…+aijXj

(5)

其中,Fi為第i主成分;Xj為標準化后的第j個特征參數;aij為第i主成分對應的第j個特征參數的系數。由(5)式可得前3個主成分的數值。

3 行駛工況的構建與驗證

3.1 聚類分析及結果

根據數據的交通特征,將運動學片段分為低速(多怠速、短運動學片段)、中速(加減速頻繁、片段長度適中)和高速(少怠速、長運動學片段)3類。對排名前3的主成分數值進行遺傳變異改進的蟻群聚類分析,并與常用的K-means聚類法及系統聚類法進行對比。遺傳變異改進的ACO聚類結果如圖4所示,K-means聚類結果和系統聚類部分結果分別見表4、表5所列。

圖4 遺傳變異改進的ACO聚類結果

表4 K-means聚類結果

表5 系統聚類部分結果

由圖4可以看出,用改進的ACO進行聚類,結果中第1類包括33個運動學片段,第2類包括55個運動學片段,第3類包括38個運動學片段。表4顯示了K-means聚類法得到的前3個主成分聚類中心坐標;表5則展示了系統聚類法部分運動學片段的聚類結果。

3.2 建立代表性工況

將各類運動學片段分別進行組合,形成3種運動學片段簇。代表性工況一般為1 200 s左右,按各類所占總時間長度比及每個運動學片段與其所屬運動學簇之間相關系數的大小,從改進的ACO聚類法形成的第1簇中選取片段110,第2簇中選取片段36、78、98,第3簇中選取片段29,擬合為代表性工況1。按照同樣的選取規則,在K-means聚類法第1類的17個運動片段中選取片段47,第2類的73個運動片段中選取片段78、98、32,第3類的36個運動片段中選取片段35、114擬合為代表性工況2。同理,在系統聚類法第1類的72個運動片段中選取片段98、78、36,第2類的36個運動片段中選取片段67、95、119,第3類的18個運動片段中選取片段110,擬合為代表性工況3。

因數據變化幅度較大,擬合工況會產生“毛刺”現象,本文用五點三次平滑法對不規則抖動的速度時間曲線進行濾波處理,以減少對代表性工況的影響,形成的最終工況如圖5所示。

圖5 3種擬合工況

3.3 基于特征參數的精度檢驗

為檢驗遺傳變異改進的ACO聚類法在行駛工況中應用的精度,給出3種方法擬合工況與試驗工況的相對誤差,見表6所列。

表6 3種擬合工況與試驗工況特征參數的相對誤差 %

本文引入平均誤差,以期全面考察所建工況的精度。平均誤差為:

(6)

其中,bn為各參數的權重;Pn為各參數的相對誤差。為簡化計算,本文定義所有權重均為1。由表6數據可計算得到工況1、工況2、工況3的平均誤差分別為3.64%、5.49%、4.51%。

由表6可以看出,以改進的ACO聚類法建立的擬合工況與試驗工況的相對誤差均在10%以內,且平均相對誤差僅為3.64%,精度明顯高于K-means均值聚類法及系統聚類法,說明了改進ACO在構建行駛工況中的優越性與有效性。

3.4 基于VA聯合分布的誤差分析

利用Matlab軟件計算3種擬合工況的速度-加速度(velocity-acceleration,VA)聯合分布平均誤差,結果見表7所列。繪制擬合工況與原始數據的VA聯合分布誤差圖,如圖6所示,以便更直觀地比較本文方法擬合的工況與原始數據的差異。

由表7可知,以改進ACO擬合的工況1的VA聯合分布誤差的平均值僅為0.26%,小于擬合工況2、工況3,這說明擬合工況1與試驗工況有極高的相似度,優于工況2與工況3。

由圖6可以看出,工況1與原始數據誤差較大的區域僅集中于0

表7 擬合工況VA聯合分布平均誤差

圖6 3種工況的VA聯合分布誤差

4 結 論

(1) 本文引入加速比例、減速比例、勻速比例、怠速比例、平均速度、平均運行速度、最大速度、最大加速度、最小加速度、速度標準差、加速度標準差、減速段平均加速度以及加速段平均加速度13個能夠反映合肥市典型道路與交通狀況的參數,用以描述工況特性。

(2) 通過主成分分析法對13個特征參數進行分析處理,提取出前3個主成分,并對其得分進行聚類分析,選取合適的運動學片段構建代表性工況。將改進ACO擬合的工況與K-means法、系統聚類法擬合的工況進行比較,結果表明,改進的ACO聚類精度更高。

(3) 以改進的ACO構建的代表性工況與原始數據相比,誤差小于4%,可以綜合反映合肥市實際道路交通狀況,這為行駛工況的構建提供了新的研究方法。但ACO作為一種近年來興起的模擬進化算法,仍有需要改進之處,如數據量大時,搜索時間較長。

[1] GONG Q,MIDLAM-MOHLWER S,MARANO V,et al.An iterative markov chain approach for generating vehicle driving cycles[J].SAE International Journal of Engines,2011(1):1035-1045.

[2] FOTOUHI A,MONTAZERI-GH M.Tehran driving cycle development using thek-means clustering method[J].Scientia Iranica,2013,20(2):286-293.

[3] 孫宏圖,宋希庚,王天靈.改進的城市公交循環工況開發方法[J].大連理工大學學報,2009,49(6):837-841.

[4] 孫強,白書戰,韓爾樑,等.基于試驗測量的瞬時行駛工況構建[J].吉林大學學報(工學版),2015,45(2):364-370.

[5] 黃萬友,程勇,李闖.基于車輛能耗狀態的濟南市道路行駛工況構建[J].西南交通大學學報,2013,47(6):989-995.

[6] 朱星宇,陳永強.SPSS多元統計分析方法及應用[M].北京:清華大學出版社,2011:241-248.

[7] 周大鐲,姜文波,李敏強.一個高效的多變量時間序列聚類算法[J].計算機工程與應用,2010,46(1):137-139.

[8] 嚴駿.模糊聚類算法應用研究[D].杭州:浙江大學,2006.

[9] 楊劍峰.蟻群算法及其應用研究[D].杭州:浙江大學,2007.

[10] 李友文,石琴,姜平.基于馬爾科夫過程的行駛工況構建中數據處理與分析[J].合肥工業大學學報(自然科學版),2010,33(4):491-494.

[11] ERICSSON E.Independent driving pattern factors and their influence on fuel-use and exhaust emission factors[J].Transportation Research Part D:Transport and Environment,2001,6(5):325-345.

[12] 艾國和,喬維高,李孟良,等.車輛行駛運動學參數構成分析[J].公路交通科技,2006,23(2):154-157.

Drivingcycleconstructionbasedonimprovedantcolonyoptimizationalgorithmandprecisionanalysis

LIU Bingjiao1, SHI Qin1, QIU Duoyang2, CHEN Yikai1

(1.School of Automobile and Traffic Engineering, Hefei University of Technology, Hefei 230009, China; 2.School of Mechanical Engineering, Hefei University of Technology, Hefei 230009, China)

Taking the measure data of five typical urban roads in Hefei City as an example, typical driving cycle(DC) of Hefei City is constructed with the method of principal component analysis and genetic variation improved ant colony optimization(ACO) algorithm. Based on the definition of the kinematic fragments, the method of principal component analysis is used to reduce the dimension of the 13 kinematic feature parameters, and the first three principal components are classified by the improved ACO algorithm. The representative DC is obtained through the combination of the class of kinematic fragments. The analysis of the precision is also conducted. The results show that compared withK-means clustering algorithm and system clustering algorithm, the improved ACO algorithm can improve the precision of DC construction effectively.

principal component analysis; genetic variation; ant colony optimization(ACO); driving cycle(DC)

2016-03-03；

2016-04-28

國家自然科學基金資助項目(71431003)

劉炳姣(1991-),女,新疆烏魯木齊人,合肥工業大學碩士生;石 琴(1963-),女,安徽蚌埠人,博士,合肥工業大學教授,博士生導師,通訊作者,E-mail:shiqing7081@sohu.com.

10.3969/j.issn.1003-5060.2017.10.001

U270.14

A

1003-5060(2017)10-1297-06

(責任編輯 胡亞敏)