王紅愛,呂曉艷,朱建生,周亮瑾
(中國鐵道科學研究院 電子計算技術研究所,北京 100081)
鐵路客票發(fā)售和預訂系統(tǒng) (以下簡稱客票系統(tǒng)) 自1996年開始應用以來,實現(xiàn)了全路聯(lián)網(wǎng)售票,推出窗口售票、自動售票機售票、電話訂票、互聯(lián)網(wǎng)購票等多種方式,極大地方便了旅客購票。為避免鐵路客流高峰時期的購票擁擠,一般需要調整客票預售期。目前,主要依據(jù)歷史數(shù)據(jù)和專家經(jīng)驗制定客票預售期,人為因素較多。因此,提出基于粒子群算法的鐵路客票預售期計算模型,以預測售票量為基礎,通過調整客票發(fā)售期的適用度函數(shù),達到每日均衡發(fā)售客票的目標。
粒子群優(yōu)化算法 (PSO) 是一種進化計算技術,1995年由 Eberhart 和 kennedy 提出[1],源于對鳥群捕食行為的研究。PSO 是一種基于迭代的優(yōu)化算法,系統(tǒng)初始化為一組隨機解,通過迭代搜尋最優(yōu)值。在每一次迭代中,粒子通過跟蹤2個極值來更新自己,一個極值是粒子本身所找到的最優(yōu)解,稱為個體極值 pbest;另一個極值是整個種群當前找到的最優(yōu)解,稱為全局極值 gbest。如果將部分粒子代替整個種群進行搜索,得到的極值是局部極值。粒子在搜索過程中,根據(jù)個體極值和全局極值,更新自己的速度和位置。
式中:vi為粒子速度;w 為慣性權重,用于平衡全局搜索和局部搜索,可以改善粒子群優(yōu)化算法,使群體勘探和開發(fā)能力在整個計算過程中合理分配;pi是當前粒子位置;r是介于 (0,1) 之間的隨機數(shù);c1、c2是學習因子,通常 c1=c2=2;每一維粒子的速度都會被限制在一個最大速度 vmax之內,如果某一維更新后的速度超過用戶設定的 vmax,那么這一維的速度就被限定為 vmax。
每個粒子在解空間內不斷搜索與更新其個體極值和全局極值,直到滿足條件后停止。基本粒子群算法如圖1所示。
具體實現(xiàn)過程如下。
第1步:初始化粒子群:初始化粒子群中所有粒子的特征,包括粒子個數(shù)、速度和位置。
第2步:使用根據(jù)優(yōu)化問題目標定義的適應度函數(shù)對所有粒子進行評價。
第3步:將種群中每個粒子的適應度值與其個體極值比較,如果適應度值大于個體極值,則更新該粒子的個體極值。
第4步:將種群中每個粒子的適應度值與全局極值比較,如果適應度值大于全局極值,則更新每個粒子所在種群的全局極值。
第5步:不斷迭代粒子速度及位置。
第6步:重復以上步驟,直到滿足算法的迭代停止條件 (達到一定誤差或者達到最大循環(huán)次數(shù))為止。
基于 PSO 算法建立鐵路客票預售期調整優(yōu)化模型,如圖2所示。該模型的思想是:預測預售期售票量,基于粒子群算法計算售票量的平滑度,對預售期進行優(yōu)化,使得售票量的平滑度達到最優(yōu)。
為均衡系統(tǒng)資源,平滑預售期內日售票量差異,設置目標函數(shù)。
式中:xi為每日售票量;x均為預售期內平均每日售票量。
根據(jù)鐵路客票預售期的實際情況,設置模型參數(shù)。
圖1 基本粒子群算法
圖2 基本粒子群算法的應用模型圖
(1)粒子數(shù)。一般取 20~40。一般情況下,取 10個粒子即可以得到較好的效果。對于比較難的問題或者特定問題,粒子數(shù)可以取到 100~200。鐵路普通票的最大預售期為 20 天,取 20個粒子。
(2)vmax。最大速度決定粒子在循環(huán)中的最大移動距離,通常設定為粒子的范圍寬度。例如,粒子 (x1,x2,…,xi) 屬于[-5,5],則 vmax的大小為10。
(3)學習因子。c1和 c2通常等于 2。不過在文獻中也有其他的取值,但是一般 c1等于 c2,并且范圍在 0和4之間。在此,取c1=c2=2.5。
(4)停止條件。設置日售票量峰值與日售票量均值的差值占均值的百分比作為停止條件。
(5)慣性權重。慣性權重表示原來的速度在下一步迭代中所占的比重,通常取較大值時,算法具有較強的全局搜索能力;反之,算法具有較強的局部搜索能力。對于 Schaffer 的f6函數(shù),當 vmax≤2時,使用接近于1的慣性權重;當vmax≥3 時,取w=0.8 較好[2]。如果沒有 vmax的信息,使用 0.8 作為權重也是一種很好的選擇。一般設置 w 隨著計算的進行而不斷減小,以使得算法在運行初期有較好的全局搜索能力,而在末期有比較好的局部搜索能力。根據(jù)經(jīng)驗,w 的取值范圍為 [0,1.4]比較合適,但是通常當 w 取值在 [0.8,1.2]之間時,算法收斂較快?;诖?,取慣性權重值為 0.8 。
以2012年春運節(jié)前客票銷售數(shù)據(jù)為樣本數(shù)據(jù)集,進行平滑度仿真實驗,確定預售期調整優(yōu)化方案。初始數(shù)據(jù)集:{1 763 447,1 530 622,1 087 933,1 038 916,1 000 560,1 477 520}。粒子范圍為[1 000 560,1 763 447],vmax的取值為 762 887。預售期內售票量的平滑度仿真結果如圖3所示,實驗統(tǒng)計量如表1所示。從圖3可見,不同的預售期售票曲線的平滑度不同。從表1可見,設置預售期為 13d時,評價指標綜合最佳,平滑度最優(yōu)。從減輕系統(tǒng)壓力方面考慮,建議調整預售期為 13 d。
圖3 預售期內售票量的平滑度仿真圖
仿真實驗的結果表明,通過 PSO 算法調整預售期可以平滑日售票量,減輕系統(tǒng)壓力。但是在圖3中的最優(yōu)曲線表明,在優(yōu)化過程中,存在指定售票日預售期內售票量高峰轉移的現(xiàn)象,因此該解為局部最優(yōu)解,這與權重參數(shù) w 的選取有關。
表1 仿真實驗統(tǒng)計量
基于粒子群算法建立鐵路客運預售期模型,研究結果表明,該模型能夠較好地優(yōu)化預售期內日售票量的平滑度,對于均衡系統(tǒng)資源、制定合理的預售期具有一定指導意義。2011年開始全面實現(xiàn)互聯(lián)網(wǎng)售票及電話訂票業(yè)務,鐵路客運售票量在特定時期如春運、暑運、十一、五一等階段不同售票方式的歷史數(shù)據(jù)有限,因此,該仿真實驗存在局限性。在下一步的研究中,一方面可在歷史數(shù)據(jù)充足的條件下對適用度函數(shù)的參數(shù)進行優(yōu)化,另一方面可以根據(jù)不同的售票方式建立多層次應用模型,完善算法。
[1]Kennedy J,Eberhart R C. Particle Swarm Optimization[M]//IEEE Service Center. Proceedings of IEEE International Conference on Neural Networks. Piscataway,New Jersey:IEEE Service Center,1995,4:1942-1948.
[2]Yuhui Shi,Russell Eberhart. A Modified Particle Swarm Optimizer[M]//IEEE Press. Proceedings of IEEE World Congress on Computational Intelligence in:Evolutionary Computation. Anchorage,AK USA:IEEE Press,1998:69-73.