郝鵬海+程曉榮

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

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

中圖分類號：TP31 文獻標識碼：A 文章編號：1009-3044（2017）26-0238-02

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

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

1 粒子群算法

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

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

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

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

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

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

1.1 數(shù)學模型

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

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

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

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

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

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

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

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

2.1 雙層規(guī)劃模型

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

2.2 鐵路票價模型

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

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

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

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

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

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

求解過程如下：

（1） 初始化粒子群參數(shù)。學習因子[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]隨機產(chǎn)生，[ns]是不同交通方式s的客流量，[Ps]為第s個粒子的初始位置，[Pb]是粒子群中的最優(yōu)位置。

（2） 把上層規(guī)劃中粒子s的位置即票價[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ù)已經(jīng)收斂，則跳轉(zhuǎn)到（7），否則根據(jù)公式1-1和1-2計算出更新后粒子的速度和位置，然后重復(fù)步驟（2）（3）（4）。

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

4 總結(jié)

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

參考文獻：

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

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

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

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

[5] 姜達.基于不同運輸方式競爭的高速鐵路票價制定方法研究[D].西南交通大學，2014.

[6] 王修華.客運專線票價制定機理研究[J].鐵道勘察，2008（2）：91-94

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