粒子群算法在鐵路雙層規(guī)劃模型求解中的應(yīng)用

郝鵬海+程曉榮

摘要：在眾多群體智能優(yōu)化算法中，粒子群算法是一種原理相對(duì)簡單的啟發(fā)式算法，與其他仿生算法相比，它所需的代碼和參數(shù)相對(duì)較少。該文先介紹了標(biāo)準(zhǔn)的粒子群優(yōu)化算法，在原有算法的基礎(chǔ)上加入慣性權(quán)重因子[ω]，對(duì)算法進(jìn)行了優(yōu)化。最后通過粒子群算法對(duì)一種依據(jù)高速鐵路票價(jià)建立的雙層規(guī)劃模型進(jìn)行求解。

關(guān)鍵詞：粒子群算法；慣性因子；雙層規(guī)劃；求解

中圖分類號(hào)：TP31 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）26-0238-02

隨著經(jīng)濟(jì)的發(fā)展，高速鐵路已經(jīng)成為人們越來越青睞出行方式，票價(jià)也是人們關(guān)注的主要問題之一，定制一個(gè)合理的票價(jià)是鐵路首要考慮的問題，要在使鐵路的利益最大化和乘客的滿意度之間進(jìn)行權(quán)衡，從而制定一個(gè)合理的票價(jià)。雙層規(guī)劃模型最早在研究非平衡經(jīng)濟(jì)市場競爭時(shí)提出，這一模型在制定高速鐵路的票價(jià)過程中同樣適用。

通過鳥群捕食過程中，每一只鳥之間的合作，達(dá)到團(tuán)體最優(yōu)的行為，美國學(xué)者Eberhart、Kennedy提出一種基于個(gè)體尋求團(tuán)體最優(yōu)解的算法—粒子群算法（PSO）[1]。粒子群算法的基本機(jī)制是通過迭代算法實(shí)現(xiàn)的，首先在固定的范圍內(nèi)生成一組隨機(jī)數(shù)當(dāng)作粒子，通過迭代函數(shù)刷新粒子的運(yùn)行速度和在固定范圍內(nèi)的位置，通過最優(yōu)解函數(shù)尋找最優(yōu)解。因此本文采用粒子群算法來尋求雙層規(guī)劃函數(shù)的最優(yōu)解。

1 粒子群算法

隨機(jī)產(chǎn)生的每一個(gè)粒子的位置首先被確定為該粒子的最優(yōu)解。每次迭代中，首先會(huì)刷新粒子的位置和速度，然后與最優(yōu)解比較，最后保存更符合目標(biāo)函數(shù)的解為最優(yōu)解。所有粒子中更符合目標(biāo)函數(shù)的為全局最優(yōu)解[2]。迭代在達(dá)到規(guī)定的次數(shù)或者目標(biāo)函數(shù)到達(dá)可以接受的誤差時(shí)結(jié)束。

PSO中并沒有太多的參數(shù)，下面介紹常見的幾種參數(shù)。

（1） 粒子數(shù)：粒子即個(gè)體，例如鳥群中的一只鳥就可以看做一個(gè)粒子，通常粒子數(shù)取10-30可滿足需要，對(duì)于部分復(fù)雜的問題，粒子數(shù)可以取100-300之間，為了體現(xiàn)粒子的多樣性并且找尋最優(yōu)的優(yōu)化路徑。

（2） 慣性權(quán)重[ω]：[ω]是粒子持續(xù)移動(dòng)的慣性參數(shù)，能使離子數(shù)組擴(kuò)大搜尋范圍，有利于整個(gè)粒子種群搜索最優(yōu)解。[ω]在改進(jìn)后的粒子群算法中具有相當(dāng)重要的作用，[ω]決定了原始速度在下一次迭代中所占的比例，一般在迭代的過程中[ω]不斷遞減，這樣可以在算法初始具有良好的全局搜索能力，隨著搜索的進(jìn)行，逐步確定最優(yōu)區(qū)域，算法的局部搜索能力也隨之提升。

（3） 最大速度Vmax：Vmax決定粒子在循環(huán)中移動(dòng)的最遠(yuǎn)距離，即粒子當(dāng)前位置和最優(yōu)位置之間的區(qū)域的準(zhǔn)確度。Vmax不宜太大或者太小，太大粒子會(huì)飛過最優(yōu)位置，太小會(huì)導(dǎo)致局部最優(yōu)[3]。

（4） 學(xué)習(xí)因子[c1]和[c2]：[c1]、[c2]用于調(diào)整每一個(gè)粒子自身經(jīng)驗(yàn)和社會(huì)經(jīng)驗(yàn)在其移動(dòng)搜索中的作用，表示每一個(gè)粒子飛向本身最優(yōu)解和全局最優(yōu)解的位置的隨機(jī)加速項(xiàng)的權(quán)重，一般都取值為2。

1.1 數(shù)學(xué)模型

基本粒子群算法的執(zhí)行順序如圖1所示，具體步驟為：

1） 初始化粒子群：初始化粒子群中粒子的數(shù)量和每一個(gè)粒子應(yīng)該包含的特性，包括每一個(gè)粒子的初始化速度和初始化位置。

2） 根據(jù)要優(yōu)化的問題確定合適的適應(yīng)度函數(shù)來評(píng)定每一個(gè)粒子。

3） 把整個(gè)粒子群中每個(gè)粒子的適應(yīng)度值與此粒子的歷史最優(yōu)解比較，若適用度值大于該粒子歷史最優(yōu)解，更新該粒子歷史最優(yōu)解。

4） 把整個(gè)粒子群中每個(gè)粒子的適用度值與全局歷史最優(yōu)解比較，若適用度值大于全局歷史最優(yōu)解，更新該粒子歷史最優(yōu)解。

5） 通過循環(huán)迭代不斷更新粒子速度和位置。

6） 重復(fù)1）-5）步驟，直到滿足停止條件（誤差達(dá)到可接受的范圍或達(dá)到最大迭代數(shù)）停止迭代為止。

2 車票模型構(gòu)建

2.1 雙層規(guī)劃模型

上層函數(shù)通過設(shè)置的值影響下層函數(shù)，n是m的函數(shù)，通常稱函數(shù)n=n（m）為反應(yīng)函數(shù)。雙層規(guī)劃能夠解決兩個(gè)層次之間的統(tǒng)一與協(xié)調(diào)，雙層規(guī)劃中的上層函數(shù)的決策并不直接影響下層函數(shù)的決策，兩者是指導(dǎo)和被指導(dǎo)的關(guān)系，下層函數(shù)在上層函數(shù)結(jié)果的指導(dǎo)下，可以在約束范圍內(nèi)進(jìn)行自由決策。因此，上層函數(shù)在決策時(shí)也要考慮下層函數(shù)的自由決策會(huì)對(duì)自己產(chǎn)生的影響。

2.2 鐵路票價(jià)模型

高速鐵路的票價(jià)直接影響旅客的選擇，而旅客在各種交通工具中的所占比重反過來也會(huì)影響票價(jià)的制定，因此鐵路管理部門就是上層函數(shù)，而旅客出行選擇就是下層函數(shù)。文獻(xiàn)[5]研究了雙層規(guī)劃模型在鐵路票價(jià)中的應(yīng)用，本文在文獻(xiàn)[5]的基礎(chǔ)上構(gòu)建的模型如下：

2.2.1 上層模型構(gòu)建

鐵路的廣義費(fèi)用和客流量正相關(guān)。通過查閱資料，在本篇論文里我們采用冪函數(shù)形式。通用形式為：[fs（ds）=αqβs+Es]。其中[fs（ds）]是鐵路運(yùn)營的廣義費(fèi)用，[qs]是鐵路客流量，[α]和[β]是權(quán)重系數(shù)，[Es]是其余的可預(yù)測費(fèi)用。

3 基于粒子群算法求解雙層規(guī)劃函數(shù)

雙層規(guī)劃問題的求解十分困難，它是一個(gè)NP-HARD問題，尤其是對(duì)于變量較多的情況下，其全局最優(yōu)解難以求出[7]。粒子群算法是一種群體智能優(yōu)化算法，能夠解決很多全局收斂以及全局優(yōu)化的問題，并且它所需的代碼和參數(shù)相對(duì)較少，因此把粒子群算法用于雙層規(guī)劃優(yōu)化求解具有一定的可行性。

粒子群算法本質(zhì)是基于迭代算法實(shí)現(xiàn)，因此本文采用基于粒子群算法的雙層迭代規(guī)劃算法，雙層規(guī)劃下層模型是旅客均衡模型，采用Frank-Wolfe算法對(duì)其進(jìn)行求解，采用標(biāo)準(zhǔn)的粒子群改進(jìn)算法求解上層模型，然后上下層反復(fù)迭代直至逼近最優(yōu)解。

求解過程如下：

（1） 初始化粒子群參數(shù)。學(xué)習(xí)因子[c1]和[c2]取2，粒子種群數(shù)量m取20，粒子初始位置[Xs]和初始速度[Vs]，最大權(quán)重因子[ωmax]0.99，最小權(quán)重因子[ωmin]0.01，更新速度的范圍是[-0.05，0.05]，滿足下層規(guī)劃函數(shù)的始解[ns]隨機(jī)產(chǎn)生，[ns]是不同交通方式s的客流量，[Ps]為第s個(gè)粒子的初始位置，[Pb]是粒子群中的最優(yōu)位置。

（2） 把上層規(guī)劃中粒子s的位置即票價(jià)[Xs]代入下層函數(shù)，然后利用Frank-Wolfe算法求得最優(yōu)解[y?s]，即各種類列車的客流量。

（3） 把[Xs]和[y?s]代入上層函數(shù)，所得到的函數(shù)值[F（Xs，y?s）]就是粒子s的適應(yīng)度。

（4） 若更新后粒子的適應(yīng)度比[Ps]的適應(yīng)度高，則用[Xs]替代[Ps]，若更新后粒子的適應(yīng)度比粒子群中所有粒子的適應(yīng)度都要高，則用[Xs]替代[Pb]。

（5） 若此時(shí)函數(shù)已經(jīng)收斂，則跳轉(zhuǎn)到（7），否則根據(jù)公式1-1和1-2計(jì)算出更新后粒子的速度和位置，然后重復(fù)步驟（2）（3）（4）。

（6） 迭代結(jié)束，輸出最優(yōu)解[Pb]。

4 總結(jié)

合理的運(yùn)用粒子群算法可以簡化很多復(fù)雜函數(shù)的求解問題，并且實(shí)現(xiàn)資源的最大化利用，自粒子群算法被提出以來，有很多的改進(jìn)機(jī)制，也被應(yīng)用在了各種方面，在高速鐵路方面的應(yīng)用目前還并不是很成熟，本文通過反復(fù)迭代雙層規(guī)劃函數(shù)，逼近最優(yōu)票價(jià)，在鐵路的利潤最大化和乘客的滿意度之間取得了平衡。

參考文獻(xiàn)：

[1] 唐娜. 改進(jìn)粒子群算法及其應(yīng)用研究[D].合肥工業(yè)大學(xué)，2016.

[2] 吳高超. 基于粒子群算法的路徑規(guī)劃問題研究[D].燕山大學(xué)，2016.

[3] 寧必鋒.一種改進(jìn)的粒子群算法在解非線性方程組中的應(yīng)用[J].吉林化工學(xué)院學(xué)報(bào)，2013（30）；114-116.

[4] 任愛紅.幾類復(fù)雜雙層規(guī)劃問題的算法研究及應(yīng)用[D].西安電子科技大學(xué)，2014.

[5] 姜達(dá).基于不同運(yùn)輸方式競爭的高速鐵路票價(jià)制定方法研究[D].西南交通大學(xué)，2014.

[6] 王修華.客運(yùn)專線票價(jià)制定機(jī)理研究[J].鐵道勘察，2008（2）：91-94

[7] 李和成，王宇平.幾類非線性雙層規(guī)劃問題的混合遺傳算法[J].系統(tǒng)工程與電子技術(shù)，2005，30（6）：1265-1272.endprint