陳曉敏,王家偉

(重慶交通大學(xué) 信息科學(xué)與工程學(xué)院,重慶 600074)

列車停站方案是列車開行方案的基本內(nèi)容,停站方案的優(yōu)化是保證列車開行方案合理化的必要環(huán)節(jié).優(yōu)化列車停站方案可以方便游客出行,節(jié)約游客出行時間,滿足旅客的多方面需要,從而吸引節(jié)點客流,提高鐵路運(yùn)輸部門的運(yùn)營收益,降低營運(yùn)成本[1].為了能更好的為鐵路運(yùn)輸組織提供輔助決策,亟待解決列車停站方案優(yōu)化問題.

停站方案模型的求解主要包括數(shù)學(xué)解析法和智能優(yōu)化算法[2].數(shù)學(xué)解析法雖然精確能保證解的質(zhì)量,但很難在有效時間內(nèi)獲得最優(yōu)解,且算法復(fù)雜度高.Wang等人[3]將粒子群算法與模擬退火算法結(jié)合,利用模擬退火算法的局部搜索能力提高了粒子群算法的搜索效率.陳世明等人[4]將捕食策略引入到粒子群算法中,并提出一種自適應(yīng)速度限制方式,使得算法在大范圍搜索時更易跳出局部最小解.嚴(yán)藝等人[5]對基本的遺傳算法進(jìn)行FPDC法和MOGA法相結(jié)合實現(xiàn)算法的改進(jìn),并用來求解列車開行方案多目標(biāo)規(guī)劃模型.

近年來,粒子群算法(PSO)憑借其易實現(xiàn),算法效率高等特點獲得了廣泛的應(yīng)用.Liu[6]提出了動態(tài)算法權(quán)重及異步調(diào)整學(xué)習(xí)因子的方法來優(yōu)化分?jǐn)?shù)階控制器參數(shù),得到了較好的優(yōu)化參數(shù).Ali等人[7]針對大規(guī)模優(yōu)化問題,提出一種基于三種機(jī)制的混合粒子優(yōu)化與遺傳算法,該算法將粒子群算法用于平衡探測和開發(fā)階段.Lin等人[8]通過混合遺傳粒子群算法來設(shè)計多域二進(jìn)制過濾器,該算法包括自適應(yīng)參數(shù),重組,變異操作.Wu等人[9]在面向服務(wù)的制造業(yè)多任務(wù)調(diào)度問題中,提出了一種混合離散粒子群優(yōu)化遺傳算法,算法采用整數(shù)編碼來建立粒子位置矩陣和服務(wù)位置方案的關(guān)聯(lián),根據(jù)自我認(rèn)識能力,社會認(rèn)識能力及以前的速度和位置來更新位置,同時引入遺傳算法的交叉和變異操作來適應(yīng)離散空間,實驗證明所提算法的有效性.粒子群算法通過保存?zhèn)€體最優(yōu)和集體最優(yōu)來完成極值尋優(yōu),算法復(fù)雜度低且收斂速度較快,但是隨著迭代次數(shù)的增多,存在粒子相似度高、易陷入收斂于局部最優(yōu)等問題[10].量子遺傳算法利用量子比特的概率幅進(jìn)行染色體編碼,并引入量子門機(jī)制對染色體進(jìn)行更新[11],通過量子選擇、交叉、變異等算子來改變種群的染色體信息,但是量子遺傳算法在解決復(fù)雜優(yōu)化問題時會存在全局搜索能力極強(qiáng)而局部搜索能力較差和早熟收斂等缺點.

針對以上這些問題,本文將粒子群算法與量子遺傳算法相結(jié)合,提出了一種改進(jìn)的多目標(biāo)混合粒子群算法(QGA_PSO).算法在粒子群算法的基礎(chǔ)上,引入量子遺傳算法的量子比特編碼、量子旋轉(zhuǎn)門及量子交叉和變異.在利用旋轉(zhuǎn)門更新粒子時,直接將速度更新公式應(yīng)用于角度更新,而不是將速度更新公式作為角度的增量表達(dá)式,加快了收斂速度.另外,該算法還加入了遺傳算法的交叉和變異算子,豐富了粒子的多樣性,使粒子跳出局部最優(yōu)解.最后通過一個實例證明了該方法的有效性,期望能為該城際鐵路列車停站方案的制定和優(yōu)化提供有效的科學(xué)依據(jù).

1 高速鐵路列車停站方案模型

假設(shè)高速鐵路旅客運(yùn)輸網(wǎng)絡(luò)其中為列車途經(jīng)車站的集合,i代表車站在鐵路線上的空間順序為列車的集合.

式(1)表示列車tk在車站si是否停站,0表示不停,1表示停.

現(xiàn)假設(shè)有起訖點相同,流量大小已知的客流,在輸送完所有客流的條件下,為使旅客旅行時間最小同時區(qū)段可達(dá)性最大,減少鐵路運(yùn)輸企業(yè)的費用,建立了如下所示的列車停站方案多目標(biāo)多約束模型：

目標(biāo)函數(shù)1.旅客旅行時間最少

其中,qt,i,j表示列車t從i站到j(luò)站的在途旅客量,wh表示列車在h站的停車耗費時間,xt,h表示列車t在h站停站與否.一般情況下,列車等級相同,停站次數(shù)也相同,旅行時間相差較小,因此可以用旅客乘車區(qū)間的停站等待時間來代替實際旅行所花費的時間.即把各個乘車區(qū)間在途旅客等待時間最小作為模型的優(yōu)化目標(biāo).

目標(biāo)函數(shù)2.區(qū)段可達(dá)性最大化

αj表示車站Sj的等級系數(shù),指標(biāo)越大,表示該車站等級越高.區(qū)段可達(dá)性使得該區(qū)間所開行的列車在車站等級系數(shù)越大的車站停站次數(shù)越多.

列車能力約束：

ξi,j,m表示第m個區(qū)間是否在i站與j站之間,是為1,不是為0.ct表示列車定員.確保列車各個區(qū)間的客流量都不超過列車定員.

客流量約束：

客流量約束,將OD客流加載到列車上,滿足OD的最大服務(wù)頻率.

停站總次數(shù)約束：

式(6)為列車途經(jīng)各車站的停站總次數(shù)約束,由于列車的停站方式對車站的通行能力有很大影響,而停站次數(shù)也會影響列車的旅行速度.因此可以根據(jù)客流量計算各車站的停站次數(shù)上下限值.

2 混合粒子群算法優(yōu)化

2.1 粒子群算法原理[12]

粒子群算法通過模仿自然界動物的行為來尋找最優(yōu)解.在粒子群算法中,每個優(yōu)化問題的解都是搜索空間中的一只鳥,我們稱之為“粒子”.粒子群算法初始化為一群隨機(jī)粒子(隨機(jī)解).然后通過迭代找到最優(yōu)解.在每一次迭代中,通過計算更新粒子速度和位置信息,更新個體粒子的最優(yōu)解,進(jìn)行粒子更新操作.基本算法是：

上述表述式中,x代表目標(biāo)所在地點,v代表目標(biāo)的瞬時速度,pbest為個體最優(yōu)解,gbest為全局最優(yōu)解.

2.2 量子遺傳算法簡介

2.2.1 量子遺傳算法原理[13]

量子遺傳算法中,主要引入了量子位(或量子比特)和量子疊加態(tài)兩個概念.在量子計算中,量子位為最小的信息單位.一個量子位可以用三種狀態(tài)來表示,即0態(tài),1態(tài)和之間的任意疊加態(tài).其狀態(tài)如下描述：

其中,α,β為量子位對應(yīng)態(tài)的概率幅,量子被觀測為態(tài)的概率用表示,被觀測為態(tài)的概率為需要滿足歸一化條件

2.2.2 量子門

目前量子門已經(jīng)有很多種,有量子非門,量子受控非門,Hadamard門,量子旋轉(zhuǎn)門等.按照量子遺傳算法的計算特點,選擇量子旋轉(zhuǎn)門作為更新方式較為適合.旋轉(zhuǎn)門的的表達(dá)式如下：

通過量子門的變換矩陣可以實現(xiàn)種群更新,更新過程如下：

θki是旋轉(zhuǎn)角,其大小和對應(yīng)的符號由設(shè)計的調(diào)整策略確定.

2.3 混合粒子群算法設(shè)計

將粒子群算法的速度更新方式引入到量子遺傳算法,利用量子遺傳算法的量子比特編碼染色體[14],量子位對應(yīng)的概率幅代表一個粒子的解,采用量子旋轉(zhuǎn)門的變換實現(xiàn)種群的更新,同時利用粒子群算法的速度更新方式來調(diào)整量子門的旋轉(zhuǎn)角.每個染色體占據(jù)兩個位置,同時加入量子交叉,量子變異等遺傳算子,提高了粒子群體的多樣性,避免算法陷進(jìn)局部最優(yōu).

2.3.1 停站方案編碼

量子位的概率幅代表一趟列車在該站停與不停的概率,因此列車停站方案編碼采用式(7)的編碼方式.假設(shè)路網(wǎng)中存在n個車站,列車集合得到停站方案的染色體表達(dá)機(jī)制如式(7).

該染色體基因數(shù)為列車路過車站的個數(shù),即染色體含有n個量子比特位,代表某列車停站方案的一個可行解.根據(jù)量子遺傳算法的一般方法,基因位的初始概率幅取值都為使其在所有可行解中有相同的取值概率[15].

2.3.2 粒子群更新方式

粒子群算法的速度更新公式來更新量子旋轉(zhuǎn)門的旋轉(zhuǎn)角,旋轉(zhuǎn)角更新如下：

θpki表示個體最優(yōu)旋轉(zhuǎn)角,θgki表示全局最優(yōu)旋轉(zhuǎn)角,ω表示慣性權(quán)重,采用如下的遞減函數(shù)[16]：

ω使算法隨著迭代次數(shù)的增加全局搜索能力逐漸降低而局部搜索能力逐步增強(qiáng).i為當(dāng)前迭代次數(shù),n為粒子群大小;c1為學(xué)習(xí)因子和r2為[0,1]之間的隨數(shù),i=1,2,···,N,k=1,2,···,K,K為粒子數(shù).更新后的粒子形式如下：

旋轉(zhuǎn)角正負(fù)會影響旋轉(zhuǎn)門方向,因此首先設(shè)計好調(diào)整方針.θ值過大,會導(dǎo)致早熟;反之則會不易收斂.通常取

直接利用粒子群算法的位置更新公式來動態(tài)調(diào)整量子門旋轉(zhuǎn)角度的大小和方向.采用這種方式主要是：(1) 減少參數(shù)的數(shù)目,簡化算法;(2) 更新方程具有記憶能力,不僅可以向粒子自身的局部最優(yōu)信息學(xué)習(xí),也可以向社會的全局最優(yōu)信息學(xué)習(xí),并且使用ω使得全局和局部搜索能力得到平衡,加快收斂速度.

2.3.3 混合粒子群算法流程

QGA_PSO求解鐵路列車停站方案模型的具體步驟如下所示：

1) 確定粒子群算法的基本參數(shù),如群體規(guī)模,粒子長度等.將所有染色體的量子比特初始化為

2) 按照前文染色體編碼方式隨機(jī)生成初始粒子pop.當(dāng)前迭代次數(shù)

3) 計算每個粒子各自對應(yīng)的目標(biāo)函數(shù)的值,并記下最優(yōu)個體及其對應(yīng)的適應(yīng)度值;

4) 進(jìn)行迭代判斷,當(dāng)滿足給定的停止條件時退出,否則繼續(xù)步驟5);

5) 利用式(8)更新θ;

6) 計算當(dāng)前各粒子所對應(yīng)的各目標(biāo)函數(shù)值,當(dāng)粒子的目標(biāo)函數(shù)值大于前一次的值時,更新粒子,否則粒子保持不變;

7) 根據(jù)交叉概率,對粒子進(jìn)行一致性交叉概率,對粒子進(jìn)行一致性交叉操作;

8) 根據(jù)變異概率,對種群進(jìn)行變異操作;

9) 記下最優(yōu)個體及其對應(yīng)的適應(yīng)度值;

10) 根據(jù)概率函數(shù)求問題的解空間.當(dāng)時否則

11) 迭代次數(shù)t=t+1,返回步驟4).

2.3.4 算法分析

將算法應(yīng)用于離散多目標(biāo)的ZDT1函數(shù)優(yōu)化問題,以驗證算法的適用性.ZDT1函數(shù)在兩個目標(biāo)函數(shù)上的最優(yōu)值分別為0和1.首先隨機(jī)設(shè)置種群規(guī)模為50,迭代次數(shù)100,固變異概率pm,對于不同的量子交叉概率pc,得到的性能對比表如下：

表1 不同pc取值算法性能對比

從結(jié)果可以看出,當(dāng)pc很小時,收斂性交叉,隨著pc的增大,交叉作用促使個體向最優(yōu)解進(jìn)化.當(dāng)pc=0.8時算法得到最好的收斂性.當(dāng)pc超過0.9時,群體多樣性降低,個體易收斂于局部最優(yōu)解.

然后固定量子交叉概率為0.8,針對不同的pm取值得到的性能對比見表2.

表2 不同pm取值算法性能對比

同樣,適當(dāng)增加變異概率能使個體收斂到最優(yōu)值,取pm=0.08.

接下來將改進(jìn)算法與量子遺傳算法(QGA)以及量子粒子群算法作對比,得到各算法在兩個目標(biāo)函數(shù)上的取值如圖1和圖2所示.

由上圖可知,QGA_PSO算法能以較快速度收斂于最優(yōu)解.相比其余兩種算法,其在收斂算法和算法精度上都有相應(yīng)的提高,證明了本文算法的有效性.

3 實例驗證和結(jié)果分析

采用2015年12月1日某區(qū)段客流進(jìn)行驗證.全路運(yùn)行圖開行24列速度為300 km/h的下行列車.

圖1 ZDT目標(biāo)函數(shù)1仿真結(jié)果

圖2 ZDT目標(biāo)函數(shù)2仿真結(jié)果

3.1 數(shù)據(jù)準(zhǔn)備

3.1.1 客運(yùn)站點等級劃分

車站等級是影響列車停站方案的一個關(guān)鍵因素,因此有必要對經(jīng)過的車站進(jìn)行車站等級劃分.本文采用文獻(xiàn)[17]提出的灰色關(guān)聯(lián)度分析方法得到各車站的等級系數(shù),為列車停站方案的區(qū)段可達(dá)性計算奠定基礎(chǔ).各車站等級系數(shù)如表3所示.

3.1.2 列車開行對數(shù)

以某區(qū)段2015年12月1日OD客流為依據(jù)進(jìn)行分析.對于某一開行區(qū)段列車停站方式主要包括4種：(1) 開行直達(dá)列車;(2) 開行大站停列車;(3) 開行大站套小站的列車;(4) 開行站站停列車.考慮到本文主要是優(yōu)化高速鐵路列車的開行方案,為了保證旅客旅行速度,不開行站站停列車.計算各類停站方案旅客列車開行方案時,需要已知不同停站方案列車吸引客流的比例,以此比例將OD客流分配到不同停站列車上去,本文采用文獻(xiàn)[18]的站間客流吸引比例來分擔(dān)客流.根據(jù)各等級車吸引站間客流的比例以及OD客流數(shù)據(jù),得到總共開行21列列車,其中直達(dá)列車4列,大站停列車6列,擇站停列車11列.

表3 車站等級系數(shù)

3.2 列車停站方案求解

粒子群參數(shù)設(shè)置：結(jié)合問題規(guī)模及第2節(jié)中的分析,設(shè)置種群大小50,粒子維數(shù)11(車站數(shù)),迭代次數(shù)100,交叉概率0.8,變異概率0.08,車站等級系數(shù),車站客流量等.利用Matlab7.0軟件編程進(jìn)行計算得到列車停站方案,迭代10次達(dá)到穩(wěn)定值.原停站方案列車開行24列,中間總停站43次,優(yōu)化后的停站方案列車開行21列車,中間總停站28次,相對于以前的停站方案,優(yōu)化后的停站方案在滿足客流量的基礎(chǔ)上減少了列車開行對數(shù)及停站次數(shù),使得旅客的旅行時間減少了,同時減少了的鐵路部門的開行費用.如圖3所示為優(yōu)化后的列車停站方案示意圖.

圖3 列車停站方案

3.3 算法性能對比

為了驗證本文算法的有效性,將本算法與文獻(xiàn)[15]和文獻(xiàn)[19]從運(yùn)行時間,目標(biāo)函數(shù)及解的多樣性進(jìn)行對比.

(1) 三種算法運(yùn)行時間對比見表4.

表4 運(yùn)行時間對比

(2) 三種算法在目標(biāo)函數(shù)方面的比較可由表4及圖4分析得知.改進(jìn)后的算法運(yùn)行時間更短,區(qū)段可達(dá)性也有相應(yīng)的提高,目標(biāo)函數(shù)收斂更快,大約在迭代15次的時候就收斂了,量子遺傳算法和離散量子粒子群算法在迭代到50次以后才收斂,且收斂后的目標(biāo)函數(shù)值未到最小.可見,改進(jìn)后的算法效率更高.

(3) 為能更好的評價本文中停站方案解的多樣性,在此定義多樣性為某一列車的停站方案與其余列車停站方案的差異.因為停站方案的解為0或1的二進(jìn)制,因此多樣性為不同解之間的漢明距離,即

由上式計算出3種算法的多樣性對比如表5所示.

圖4 目標(biāo)函數(shù)值對比

表5 算法多樣性對比

由表5知改進(jìn)后的算法在多樣性上比BQPSO有的明顯的提高,但是和QGA相比,多樣性沒有明顯的優(yōu)勢.這是因為本文的編碼方式和QGA的編碼方式相同.

4 總結(jié)

基于粒子群算法存在易陷入局部最優(yōu),不適用于離散空間等缺點,本文將量子遺傳算法引入到粒子群算法中,提出了改進(jìn)的量子遺傳粒子群算法(QGA_PSO).算法首先將染色體編碼為量子比特的形式,每個染色體表示粒子的兩個位置,減少粒子種群的大小;其次,根據(jù)標(biāo)準(zhǔn)PSO的速度更新公式,更新量子旋轉(zhuǎn)門的角度,加快收斂速度,同時引入量子交叉和量子變異增加群體多樣性.算例仿真表明,提出的QGA_PASO相對于QGA,BQPSO能在更短時間內(nèi)收斂,且得到的停站方案在滿足旅客量的基礎(chǔ)上使得旅客旅行時間縮短同時減少鐵路企業(yè)開行列車費用,對鐵路客運(yùn)管理部門有一定的指導(dǎo)作用.

1 張小炳,倪少權(quán),潘金山.基于均衡性和可達(dá)性的高速鐵路列車停站方案優(yōu)化.計算機(jī)應(yīng)用研究,2017,34(7)：1962-1965.

2 于劍,張星臣,許璐.軌道交通開行方案優(yōu)化模型研究綜述.武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2016,40(1)：195-200.

3 Wang S,Zhao P,Qiao K.Study on passenger train stopping scheme based on improved particle swarm optimization algorithm.Proceedings of 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems.Shanghai,China.2009.821-826.

4 陳世明,賴毅平,江冀海.面向列車運(yùn)行調(diào)整問題的粒子群算法研究.計算機(jī)應(yīng)用研究,2010,27(12)：4460-4463.

5 嚴(yán)藝,葉玉玲.基于改進(jìn)的遺傳算法的城際鐵路開行方案研究.2014第九屆中國智能交通年會論文集.廣州,中國智能交通協(xié)會.2014.29-37.

6 Liu XY.Optimization design on fractional order PID controller based on adaptive particle swarm optimization algorithm.Nonlinear Dynamics,2016,84(1)：379-386.[doi：10.1007/s11071-015-2553-8]

7 Ali AF,Tawhid MA.A hybrid particle swarm optimization and genetic algorithm with population partitioning for large scale optimization problems.Ain Shams Engineering Journal,2016,8(2)：191-206.

8 Lin J,Zhao HY,Ma Y,et al.New hybrid genetic particle swarm optimization algorithm to design multi-zone binary filter.Optics Express,2016,24(10)：10748-10758.[doi：10.1364/OE.24.010748]

9 Wu SY,Zhang P,Li F,et al.A hybrid discrete particle swarm optimization-genetic algorithm for multi-task scheduling problem in service oriented manufacturing systems.Journal of Central South University,2016,23(2)：421-429.[doi：10.1007/s11771-016-3087-z]

10 姜明媚.城際鐵路列車停站方案優(yōu)化研究[碩士學(xué)位論文].北京：北京交通大學(xué),2015.

11 Narayanan A,Moore M.Quantum-inspired genetic algorithms.Proceedings of IEEE International Conference on Evolutionary Computation.Nagoya,Japan.1999.61-66.

12 許可,陳云飛.粒子群算法研究概述.福建電腦,2015,31(9)：83-84.

13 蔣林利.量子遺傳算法研究現(xiàn)狀綜述.廣西科技師范學(xué)院學(xué)報,2016,31(2)：130-134.

14 Han KH,Kim JH.Genetic quantum algorithm and its application to combinatorial optimization problem.Proceedings of the 2000 Congress on Evolutionary Computation.La Jolla,CA,USA.2002.1354-1360.

15 汪健雄.改進(jìn)的多目標(biāo)量子遺傳算法及其在旅客列車開行方案中的應(yīng)用[博士學(xué)位論文].北京：中國鐵道科學(xué)研究院,2012.

16 Shi YH,Eberhart RC.Parameter selection in particle swarm optimization.Proceedings of the 7th International Conference on Evolutionary Programming VII.San Diego,CA,USA.1998.591-600.

17 徐斌.高速鐵路列車停站方案研究[碩士學(xué)位論文].北京：北京交通大學(xué),2012.

18 江雨星.高速鐵路旅客列車開行方案編制方法研究[碩士學(xué)位論文].蘭州：蘭州交通大學(xué),2015.

19 李士勇,李盼池.求解連續(xù)空間優(yōu)化問題的量子粒子群算法.量子電子學(xué)報,2007,24(5)：569-574.