螢火蟲算法改進及其在公交線網(wǎng)優(yōu)化設計中的應用

【摘要】螢火蟲算法是一種新穎的群智能優(yōu)化算法，在該類優(yōu)化領(lǐng)域中的應用很少。將螢火蟲算法應用在公交線網(wǎng)優(yōu)化問題中。公交線網(wǎng)優(yōu)化是一個復雜的多目標優(yōu)化問題，是影響公共交通效率的關(guān)鍵問題。根據(jù)算法和問題的特點，設計了基于矩陣的解表示方法。為解決GSO算法優(yōu)化精度底、收斂速度慢的缺陷，提出自適應調(diào)整熒光素揮發(fā)因子ρ的螢火蟲算法，通過matlab編程仿真，結(jié)果表明改進后的算法能將多目標的優(yōu)化問題收斂到Pareto最優(yōu)解，并具有均勻分布的Pareto曲線，證明能有效的解決公交線網(wǎng)優(yōu)化問題。

【關(guān)鍵詞】螢火蟲算法;公交線網(wǎng);多目標優(yōu)化;Pareto最優(yōu)解

1.引言

公共交通一直是節(jié)能減耗和緩解交通堵塞的最好交通方式，城市公交網(wǎng)絡設計的目標需要考慮公交運營企業(yè)的利益和用戶的利益這對矛盾體。線網(wǎng)優(yōu)化以其自身的數(shù)學復雜性及約束條件復雜性，使得優(yōu)化變的非常難。文獻[1]將禁忌搜索算法應用在公交線網(wǎng)的優(yōu)化中，利用已有知識構(gòu)造禁忌表，優(yōu)化不能全面反應實際情況;文獻[2]以公共交通效率最大為目標，利用遺傳禁忌算法進行優(yōu)化;文獻[3]的多目標模型除了考慮出行總時間和公交運營企業(yè)年收益率，還考慮進污染排放率、乘客直達率等，并應用遺傳蟻群算法進行優(yōu)化，雖然全面，也增加了計算的復雜性，并且有的目標是重復的，像直達率與出行時間;文獻[4]將蟻群算法應用在公交線網(wǎng)的優(yōu)化中，分別考慮了乘客總出行時間和公交運營投入，本文在此基礎上，將乘客利益和運營企業(yè)利益作為優(yōu)化目標，通過混沌加權(quán)[5]求得在不同側(cè)重方面下達到的公交效率最大的目標。螢火蟲算法（Glowworm Swarm Optimization，GSO）是Krishnanand和Ghose提出的一種新的群智能算法，已在函數(shù)優(yōu)化領(lǐng)域得到成功應用，但在組合優(yōu)化方面的應用還很少，尤其是針對大規(guī)模的多目標優(yōu)化問題，本文將GSO算法用于公交線網(wǎng)問題的優(yōu)化，不但豐富了公交線網(wǎng)問題的優(yōu)化算法，也拓寬了螢火蟲算法的應用領(lǐng)域。

2.公交線網(wǎng)優(yōu)化問題

公交線網(wǎng)的模型對整個線網(wǎng)的優(yōu)化起著決定性作用，通過已有的站點和路網(wǎng)優(yōu)化得到最優(yōu)線網(wǎng)，是多目標規(guī)劃問題，綜合乘客利益和運營企業(yè)利益這對矛盾體的考慮，引入權(quán)重控制系數(shù)，調(diào)節(jié)雙方利益在整個線路運營中的不同權(quán)值，求解不同地域不同側(cè)重點下的最優(yōu)目標。公交線網(wǎng)模型如式（1）所示：

（1）

式中：是權(quán)重控制系數(shù)，;m公交線路總數(shù);n為站點數(shù)目;為問題的解，是矢量的元素，線路被選中時為1，否則為0;為從站點i到j的乘客量;為從站點i到j的總出行時間;為第k條線路的發(fā)車次數(shù);為第k條線路的長度。

3.螢火蟲算法

3.1 基本算法

基本GSO中主要有4個過程：熒光素更新、概率選擇、位置更新和動態(tài)決策域更新。分別如式（2）～（5）所示：

（2）

（3）

（4）

（5）

3.2 改進的螢火蟲算法

研究表明，螢火蟲算法中螢光素揮發(fā)因子ρ影響算法搜索性能。從式（2）可看出，ρ較小時，搜索過程受前一代熒光素影響較大，搜索隨機性減弱，易陷入局部最優(yōu);ρ較大時，搜索過程受前一代熒光素影響較小，隨機性增強，導致收斂速度降低。對于大規(guī)模的多目標優(yōu)化問題，影響更為突出。本文通過自適應變化的熒光素揮發(fā)因子ρ來改善算法的性能。當算法陷入局部最優(yōu)時，以式（6）自適應調(diào)整：

（6）

式中：k為迭代次數(shù)，C為調(diào)節(jié)因子，N為解群個數(shù);的最大值，防止過大降低算法收斂速度。

3.3 解的可行性檢測

檢測公交路線是否滿足限制條件，就是檢驗站點之間是否連通，對于不滿足條件的公交路線則通過隨機交叉站點修正到滿足條件。鄰接矩陣表示路線連通情況[6]，當站點i和j在某條線路上相鄰時，，否則，這樣TP是公交路線圖的臨接矩陣表示。

4.改進螢火蟲算法在線網(wǎng)優(yōu)化中的應用

解群的表示是采用矩陣存儲當前乘車路線解群，，例如以4*4的矩陣表示有4條公交線路和最多4個公交站點的路線解群，行為公交路線，列為站點標號，對于站點實際數(shù)小于最大站點數(shù)的情況，在相應位置用0表示。

5.實驗仿真

本文采用文獻[8]中測試路網(wǎng)實例，以節(jié)點2、4、5、9、14、16、22、24為首末站點，以建立5條公交線路為例，應用改進螢火蟲算法進行仿真。

表1 線網(wǎng)優(yōu)化結(jié)果

線路 路經(jīng) 權(quán)重值

1 2-3-4-6-5 a1

2 4-10-16-19-21-24 a1

3 2-8-9-13-15-20-21-22 a1>a2

4 14-13-10-11-17-18-22 a1>a2

5 14-15-16-19-21-24 a1>a2

由圖1可以看出，非劣解在目標那個鍵分布比較均勻，基本均分布在Pareto最優(yōu)解的前沿面，并且也可看出乘客利益和運營企業(yè)的利益是一對矛盾體，具有博弈特色，在設置公交線路時需要權(quán)衡兩者設置線路，使兩者均能達到能夠接受的程度。

圖1 Pareto最優(yōu)解

6.結(jié)束語

本文分別考慮了乘客利益和公交運營企業(yè)的利益，將公交線路模型處理成適合螢火蟲算法求解的模型，提出了一種熒光素揮發(fā)因子自適應改進策略，實例結(jié)果表明了該方法的可行性。并從多目標的角度將最優(yōu)解收斂到Pareto最優(yōu)解的前沿，從計算設計的線路網(wǎng)絡及Pareto最優(yōu)解圖來看，改進算法在一定程度上提高了規(guī)劃的質(zhì)量和效率。因此，改進螢火蟲算法應用于城市公交線網(wǎng)規(guī)劃的方法是可行和有效的。

參考文獻

[1]閆繼濤，李俊強，邵國金.城市公交路線網(wǎng)絡優(yōu)化[J].計算機測量與控制，2010，18（7）：1667-1668，1683.

[2]周媛，鄧衛(wèi)，胡啟洲.基于遺傳禁忌算法的城市公交線網(wǎng)優(yōu)化研究[J].武漢理工大學學報（交通科學與工程版），2011，35（1）：42-45.

[3]李昆志，沈凌，黃科宏.基于遺傳蟻群混合算法的公交線網(wǎng)優(yōu)化模型[J].中國集體經(jīng)濟，2011，（36）：84-85.

[4]劉好德，楊曉光.基于改進遺傳算法的公交線網(wǎng)優(yōu)化設計研究[J].計算機工程與應用，2007，43（8）：10-14.

[5]Li Bing，Cao Xiu-shuang.Research on Chaos Optimization of Multi-Objective Problems With Chaos Weights[C].Proceedings of The Second International Conference on Modelling and Simulation，2009，248-251.

[6]趙毅，鐘聲.基于遺傳算法的城市公交路線優(yōu)化問題[J].計算機工程與科學，2012，34（9）：109-112.

基金項目：河北省教育廳資助科研項目（項目編號：QN20132019）;唐山市科技計劃項目（項目編號：131302118a）。

作者簡介：曹秀爽（1978—），女，碩士，實驗師，主要研究方向：智能控制，人工智能。