劉炳姣, 石 琴, 仇多洋, 陳一鍇
(1.合肥工業(yè)大學(xué) 汽車與交通工程學(xué)院,安徽 合肥 230009; 2.合肥工業(yè)大學(xué) 機(jī)械工程學(xué)院,安徽 合肥 230009)
基于改進(jìn)蟻群算法的行駛工況構(gòu)建及精度分析
劉炳姣1, 石 琴1, 仇多洋2, 陳一鍇1
(1.合肥工業(yè)大學(xué) 汽車與交通工程學(xué)院,安徽 合肥 230009; 2.合肥工業(yè)大學(xué) 機(jī)械工程學(xué)院,安徽 合肥 230009)
文章以合肥市典型道路為例,選取5條城市道路進(jìn)行數(shù)據(jù)采集,采用主成分分析與遺傳變異改進(jìn)的蟻群算法(ant colony optimization,ACO)相結(jié)合的方法,構(gòu)建了合肥市典型行駛工況。在劃分了運(yùn)動(dòng)學(xué)片段的基礎(chǔ)上,利用主成分分析法對(duì)13個(gè)運(yùn)動(dòng)學(xué)特征參數(shù)進(jìn)行降維處理,以排名前3的主成分為聚類因子,用改進(jìn)的蟻群算法對(duì)運(yùn)動(dòng)學(xué)片段樣本進(jìn)行分類,通過組合類內(nèi)運(yùn)動(dòng)學(xué)片段,完成代表性工況的構(gòu)建,并對(duì)代表性工況進(jìn)行精度分析。研究結(jié)果表明,與K-means聚類法、系統(tǒng)聚類法相比,改進(jìn)的ACO能夠有效提高行駛工況的構(gòu)建精度。
主成分分析;遺傳變異;蟻群算法(ACO);行駛工況(DC)
隨著科技的迅速發(fā)展,能源短缺和環(huán)境污染問題日益嚴(yán)重,節(jié)能減排已成為全世界的重大課題。汽車行駛工況(driving cycle,DC)是針對(duì)某一類型車輛在特定交通環(huán)境下用以描述車輛行駛特征的速度-時(shí)間曲線。它被用于評(píng)估車輛的污染物排放和燃油消耗狀況、新車型的技術(shù)開發(fā)等。
最近數(shù)十年,美國、歐洲、日本等國家和地區(qū)已根據(jù)其相應(yīng)的車輛及交通狀況構(gòu)建出各自的行駛工況。文獻(xiàn)[1]研究了馬爾可夫法在工況構(gòu)建中的應(yīng)用;文獻(xiàn)[2]用K-means聚類法構(gòu)建了德黑蘭的行駛工況。近年來,國內(nèi)學(xué)者在DC開發(fā)與構(gòu)建方面也做了一些研究,文獻(xiàn)[3]研究了改進(jìn)的短行程法在城市公交行駛工況中的應(yīng)用;文獻(xiàn)[4]利用兩階段聚類法對(duì)西安市環(huán)衛(wèi)車的行駛工況進(jìn)行了研究;文獻(xiàn)[5]通過分析車輛速度及能耗狀態(tài),構(gòu)建了濟(jì)南市的行駛工況。
目前,構(gòu)建行駛工況過程中使用最廣泛的是主成分分析和聚類分析相結(jié)合的方法,但因傳統(tǒng)聚類算法或?qū)Τ跏贾颠^于敏感,或易陷入局部最優(yōu)解,導(dǎo)致工況的構(gòu)建精度過低。因此,本文對(duì)傳統(tǒng)蟻群算法(ant colony optimization,ACO)進(jìn)行了改進(jìn),并以合肥市典型道路為例,利用主成分分析法與改進(jìn)的ACO構(gòu)建行駛工況,與常用的K-means算法和系統(tǒng)聚類法進(jìn)行了精度對(duì)比,驗(yàn)證了本文提出方法的有效性。
1.1 研究方法
主成分分析是數(shù)據(jù)降維的多元統(tǒng)計(jì)學(xué)方法,主要思想是通過對(duì)原始運(yùn)動(dòng)學(xué)片段的分析,提取少數(shù)幾個(gè)能綜合反映大部分特征參數(shù)信息的主成分,從而達(dá)到簡化數(shù)據(jù)的目的。聚類分析則用于反映不同類型片段的運(yùn)動(dòng)學(xué)特征[6]。
常見的聚類方法有K-means聚類法、系統(tǒng)聚類法、模糊聚類法、動(dòng)態(tài)聚類法等。K-means算法容易陷入局部最優(yōu)解,對(duì)唯一參數(shù)K值的選擇沒有固定規(guī)律可參考[7]。系統(tǒng)聚類法則難以確定結(jié)果類的數(shù)目,在聚類過程中產(chǎn)生的合并項(xiàng)和分裂項(xiàng)都無法回復(fù),對(duì)結(jié)果有較大影響。而傳統(tǒng)的模糊聚類法對(duì)孤立點(diǎn)數(shù)據(jù)十分敏感,且因?yàn)槠溆玫郎绞剿惴?所以易陷入局部極值點(diǎn),得不到最優(yōu)解[8]。
ACO 則是一種用來尋找優(yōu)化路徑的機(jī)率型算法,但基本ACO在搜索過程中容易出現(xiàn)停滯現(xiàn)象,不利于發(fā)現(xiàn)更優(yōu)解。若在ACO中引入遺傳算法中的變異因子,則可以很好地解決這一問題。
相比于其他算法,遺傳變異改進(jìn)的ACO有如下優(yōu)點(diǎn):能夠在智能搜索的同時(shí)進(jìn)行全局優(yōu)化;有較強(qiáng)的穩(wěn)健性和魯棒性,不會(huì)出現(xiàn)停滯現(xiàn)象;數(shù)據(jù)個(gè)體間不斷進(jìn)行信息交換與傳遞,易于尋找更優(yōu)解。
鑒于以上幾點(diǎn),本文將主成分分析與遺傳變異的ACO相結(jié)合,用以構(gòu)建行駛工況。
1.2 基本ACO
為解釋遺傳變異的ACO,首先需引入基本ACO的概念[9],簡述如下。
設(shè)N={1,2,…,n}為n個(gè)地點(diǎn)的集合,A={(i,j)|i,j∈N}為N中元素兩兩連接的集合,bi(t)表示t時(shí)刻位于地點(diǎn)i的螞蟻數(shù),假設(shè)m只螞蟻都隨機(jī)選擇一個(gè)地點(diǎn)作為其出發(fā)地點(diǎn),則有:
(1)
螞蟻在構(gòu)建路徑的每一步中,按照隨機(jī)比例選擇下個(gè)要到達(dá)的地點(diǎn),即
(2)
其中,i,j分別為起點(diǎn)和終點(diǎn);τij(t)為時(shí)間t由i到j(luò)的信息素濃度;ηij=1/dij為能見度,是i,j兩點(diǎn)間距的倒數(shù);allowedk為尚未訪問過的節(jié)點(diǎn)集合;α、β為常數(shù),代表信息素和能見度的加權(quán)值。
每只螞蟻完成一次循環(huán)后,都會(huì)在其訪問過的路徑上留下相應(yīng)信息素。
當(dāng)所有螞蟻完成一次循環(huán)后,各路徑的信息素隨之更新,即
τij(t+n)=ρτij(t)+Δτij
(3)
(4)
其中,ρ(0<ρ<1)為信息殘留度;Δτij為迭代中邊ij的信息素增量。
ACO不斷地通過上述過程構(gòu)建路徑和更新信息素,最終得以尋找到最優(yōu)解。
1.3 遺傳變異改進(jìn)的ACO
ACO作為一種本質(zhì)并行的正反饋算法,個(gè)體間不斷進(jìn)行信息傳遞和交流,易發(fā)現(xiàn)最優(yōu)解。但基本ACO有一些缺陷,如搜索時(shí)間較長,很難在短時(shí)間內(nèi)找到較好的路徑;當(dāng)樣本數(shù)據(jù)量較大時(shí)會(huì)陷入局部最優(yōu)解,過早收斂。
為解決這些問題,本文引入遺傳算法中變異率對(duì)基本ACO進(jìn)行改進(jìn)。具體方法如下:加入變異率p,并在所得最佳路徑內(nèi)局部尋優(yōu);同時(shí)產(chǎn)生一個(gè)隨機(jī)數(shù)組,若數(shù)組中某值小于變異率p,則隨機(jī)改變其對(duì)應(yīng)的路徑標(biāo)記;隨后計(jì)算各樣本數(shù)據(jù)點(diǎn)到其相應(yīng)的臨時(shí)聚類中心的最小歐式距離之和F′及本次迭代的最佳路徑,更新信息素,循環(huán)此過程直至尋找到最優(yōu)解。
遺傳變異改進(jìn)的ACO流程如圖1所示。
圖1 遺傳變異改進(jìn)的ACO流程
2.1 試驗(yàn)與數(shù)據(jù)采集
為反映城市典型道路的車輛行駛工況,綜合考慮道路類型、車流密度、交叉口密度等因素,本文以合肥市區(qū)道路為例,選取5條(主干道的徽州大道、勝利路、明光路,次干道的桐城路,快速路的屯溪路)代表性的城市道路進(jìn)行試驗(yàn)及數(shù)據(jù)采集。
考慮時(shí)間因素對(duì)工況的影響,本次試驗(yàn)采樣時(shí)間定為上午7:00—9:00,下午13:00—15:00、16:30—18:30,包括每天的早、晚高峰期及平峰期,持續(xù)4 d,含工作日及非工作日。試驗(yàn)中某次行駛過程獲取的工況數(shù)據(jù)如圖2所示。
圖2 實(shí)測工況數(shù)據(jù)
試驗(yàn)采用平均車流統(tǒng)計(jì)法,即駕駛員駕駛試驗(yàn)車,在選定的時(shí)間和道路上隨平均車流行駛。數(shù)據(jù)使用OES-Ⅱ非接觸式光電速度傳感器采集,采集頻率為1 Hz,可獲得速度、加速度、路程以及時(shí)間等參數(shù),最終得到4萬余組數(shù)據(jù)。
從圖2數(shù)據(jù)可以看出,車輛在行駛過程中會(huì)頻繁加速、減速、停車、啟動(dòng),為方便描述該過程,本文將整個(gè)行駛歷程劃分為多個(gè)數(shù)據(jù)單元,在此需引入運(yùn)動(dòng)學(xué)片段的概念。
2.2 運(yùn)動(dòng)學(xué)片段的劃分
一個(gè)運(yùn)動(dòng)學(xué)片段是指在速度時(shí)間變化曲線上,從上一個(gè)怠速狀態(tài)開始到下一個(gè)怠速狀態(tài)結(jié)束之間的運(yùn)動(dòng)學(xué)單元,如圖3所示。
圖3 運(yùn)動(dòng)學(xué)片段
參考國內(nèi)外文獻(xiàn),將試驗(yàn)中采集到的數(shù)據(jù)按照以下原則進(jìn)行運(yùn)動(dòng)學(xué)狀態(tài)定義。
(1) 勻速狀態(tài)。|a|<0.15 m/s2且v≠0的發(fā)動(dòng)機(jī)連續(xù)工作狀態(tài)。
(2) 怠速狀態(tài)。a=0且v=0的發(fā)動(dòng)機(jī)連續(xù)工作狀態(tài)。
(3) 加速狀態(tài)。a≥0.15 m/s2且v≠0的發(fā)動(dòng)機(jī)連續(xù)工作狀態(tài)。
(4) 減速狀態(tài)。a≤-0.15 m/s2且v≠0的發(fā)動(dòng)機(jī)連續(xù)工作狀態(tài)
以此為劃分規(guī)則,利用Matlab編程,對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理,篩選得到126個(gè)有效的運(yùn)動(dòng)學(xué)片段。
2.3 運(yùn)動(dòng)學(xué)特征參數(shù)及參數(shù)矩陣
為準(zhǔn)確描述各運(yùn)動(dòng)學(xué)片段,表征所用參數(shù)不可過少,否則會(huì)導(dǎo)致大量信息丟失;但參數(shù)過多,則會(huì)給分析過程增加不必要的難度和計(jì)算量。參考文獻(xiàn)[10-12]對(duì)運(yùn)動(dòng)學(xué)參數(shù)的選取,本文選取了加速比例Pa、減速比例Pd、勻速比例Pc、怠速比例Pi等13個(gè)能夠反映運(yùn)動(dòng)學(xué)片段特征的參數(shù),以合理描述運(yùn)動(dòng)學(xué)片段。各運(yùn)動(dòng)學(xué)特征參數(shù)見表1所列。
以預(yù)處理階段得到的126個(gè)運(yùn)動(dòng)學(xué)片段及其特征參數(shù)為研究對(duì)象,得到樣本數(shù)×特征參數(shù)值的矩陣,見表2所列。
表1 運(yùn)動(dòng)學(xué)特征參數(shù)
注:平均運(yùn)行速度指除怠速外的平均速度。
表2 運(yùn)動(dòng)學(xué)片段及其特征參數(shù)
2.4 主成分分析
主成分分析是利用降維思想,將多個(gè)參數(shù)轉(zhuǎn)換為少數(shù)綜合參數(shù)(即主成分)的過程。其中各主成分間沒有相關(guān)性,且都是原始參數(shù)的線性組合,從而不重疊地反映原始參數(shù)的大部分信息,以達(dá)到簡化問題的目的。
用SPSS軟件對(duì)126個(gè)運(yùn)動(dòng)學(xué)片段及其特征參數(shù)進(jìn)行主成分分析,得到各主成分(用Mi表示,i=1,2,3,…,13)特征值的方差貢獻(xiàn)率及累計(jì)貢獻(xiàn)率,見表3所列。
表3 各主成分貢獻(xiàn)率
特征根是主成分影響力度的指標(biāo),代表引入該主成分后可解釋的原始變量的信息量。若特征根大于1,說明該主成分的解釋力度大于原變量的平均解釋力度,因此一般將特征根大于1、累計(jì)貢獻(xiàn)率大于85%作為主成分的納入標(biāo)準(zhǔn)。由表3可以看出,前3個(gè)主成分的特征根均大于1,且方差的累計(jì)貢獻(xiàn)率達(dá)到了90%,已足夠描述運(yùn)動(dòng)學(xué)片段的特征,因此本文選取排名前3的主成分進(jìn)行分析。主成分表達(dá)式為:
Fi=ai1X1+ai2X2+…+aijXj
(5)
其中,Fi為第i主成分;Xj為標(biāo)準(zhǔn)化后的第j個(gè)特征參數(shù);aij為第i主成分對(duì)應(yīng)的第j個(gè)特征參數(shù)的系數(shù)。由(5)式可得前3個(gè)主成分的數(shù)值。
3.1 聚類分析及結(jié)果
根據(jù)數(shù)據(jù)的交通特征,將運(yùn)動(dòng)學(xué)片段分為低速(多怠速、短運(yùn)動(dòng)學(xué)片段)、中速(加減速頻繁、片段長度適中)和高速(少怠速、長運(yùn)動(dòng)學(xué)片段)3類。對(duì)排名前3的主成分?jǐn)?shù)值進(jìn)行遺傳變異改進(jìn)的蟻群聚類分析,并與常用的K-means聚類法及系統(tǒng)聚類法進(jìn)行對(duì)比。遺傳變異改進(jìn)的ACO聚類結(jié)果如圖4所示,K-means聚類結(jié)果和系統(tǒng)聚類部分結(jié)果分別見表4、表5所列。
圖4 遺傳變異改進(jìn)的ACO聚類結(jié)果
表4 K-means聚類結(jié)果
表5 系統(tǒng)聚類部分結(jié)果
由圖4可以看出,用改進(jìn)的ACO進(jìn)行聚類,結(jié)果中第1類包括33個(gè)運(yùn)動(dòng)學(xué)片段,第2類包括55個(gè)運(yùn)動(dòng)學(xué)片段,第3類包括38個(gè)運(yùn)動(dòng)學(xué)片段。表4顯示了K-means聚類法得到的前3個(gè)主成分聚類中心坐標(biāo);表5則展示了系統(tǒng)聚類法部分運(yùn)動(dòng)學(xué)片段的聚類結(jié)果。
3.2 建立代表性工況
將各類運(yùn)動(dòng)學(xué)片段分別進(jìn)行組合,形成3種運(yùn)動(dòng)學(xué)片段簇。代表性工況一般為1 200 s左右,按各類所占總時(shí)間長度比及每個(gè)運(yùn)動(dòng)學(xué)片段與其所屬運(yùn)動(dòng)學(xué)簇之間相關(guān)系數(shù)的大小,從改進(jìn)的ACO聚類法形成的第1簇中選取片段110,第2簇中選取片段36、78、98,第3簇中選取片段29,擬合為代表性工況1。按照同樣的選取規(guī)則,在K-means聚類法第1類的17個(gè)運(yùn)動(dòng)片段中選取片段47,第2類的73個(gè)運(yùn)動(dòng)片段中選取片段78、98、32,第3類的36個(gè)運(yùn)動(dòng)片段中選取片段35、114擬合為代表性工況2。同理,在系統(tǒng)聚類法第1類的72個(gè)運(yùn)動(dòng)片段中選取片段98、78、36,第2類的36個(gè)運(yùn)動(dòng)片段中選取片段67、95、119,第3類的18個(gè)運(yùn)動(dòng)片段中選取片段110,擬合為代表性工況3。
因數(shù)據(jù)變化幅度較大,擬合工況會(huì)產(chǎn)生“毛刺”現(xiàn)象,本文用五點(diǎn)三次平滑法對(duì)不規(guī)則抖動(dòng)的速度時(shí)間曲線進(jìn)行濾波處理,以減少對(duì)代表性工況的影響,形成的最終工況如圖5所示。
圖5 3種擬合工況
3.3 基于特征參數(shù)的精度檢驗(yàn)
為檢驗(yàn)遺傳變異改進(jìn)的ACO聚類法在行駛工況中應(yīng)用的精度,給出3種方法擬合工況與試驗(yàn)工況的相對(duì)誤差,見表6所列。
表6 3種擬合工況與試驗(yàn)工況特征參數(shù)的相對(duì)誤差 %
本文引入平均誤差,以期全面考察所建工況的精度。平均誤差為:
(6)
其中,bn為各參數(shù)的權(quán)重;Pn為各參數(shù)的相對(duì)誤差。為簡化計(jì)算,本文定義所有權(quán)重均為1。由表6數(shù)據(jù)可計(jì)算得到工況1、工況2、工況3的平均誤差分別為3.64%、5.49%、4.51%。
由表6可以看出,以改進(jìn)的ACO聚類法建立的擬合工況與試驗(yàn)工況的相對(duì)誤差均在10%以內(nèi),且平均相對(duì)誤差僅為3.64%,精度明顯高于K-means均值聚類法及系統(tǒng)聚類法,說明了改進(jìn)ACO在構(gòu)建行駛工況中的優(yōu)越性與有效性。
3.4 基于VA聯(lián)合分布的誤差分析
利用Matlab軟件計(jì)算3種擬合工況的速度-加速度(velocity-acceleration,VA)聯(lián)合分布平均誤差,結(jié)果見表7所列。繪制擬合工況與原始數(shù)據(jù)的VA聯(lián)合分布誤差圖,如圖6所示,以便更直觀地比較本文方法擬合的工況與原始數(shù)據(jù)的差異。
由表7可知,以改進(jìn)ACO擬合的工況1的VA聯(lián)合分布誤差的平均值僅為0.26%,小于擬合工況2、工況3,這說明擬合工況1與試驗(yàn)工況有極高的相似度,優(yōu)于工況2與工況3。