螢火蟲(chóng)算法改進(jìn)及其在公交線網(wǎng)優(yōu)化設(shè)計(jì)中的應(yīng)用

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

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

1.引言

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

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

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

（1）

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

3.螢火蟲(chóng)算法

3.1 基本算法

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

（2）

（3）

（4）

（5）

3.2 改進(jìn)的螢火蟲(chóng)算法

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

（6）

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

3.3 解的可行性檢測(cè)

檢測(cè)公交路線是否滿足限制條件，就是檢驗(yàn)站點(diǎn)之間是否連通，對(duì)于不滿足條件的公交路線則通過(guò)隨機(jī)交叉站點(diǎn)修正到滿足條件。鄰接矩陣表示路線連通情況[6]，當(dāng)站點(diǎn)i和j在某條線路上相鄰時(shí)，，否則，這樣TP是公交路線圖的臨接矩陣表示。

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

解群的表示是采用矩陣存儲(chǔ)當(dāng)前乘車路線解群，，例如以4*4的矩陣表示有4條公交線路和最多4個(gè)公交站點(diǎn)的路線解群，行為公交路線，列為站點(diǎn)標(biāo)號(hào)，對(duì)于站點(diǎn)實(shí)際數(shù)小于最大站點(diǎn)數(shù)的情況，在相應(yīng)位置用0表示。

5.實(shí)驗(yàn)仿真

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

表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可以看出，非劣解在目標(biāo)那個(gè)鍵分布比較均勻，基本均分布在Pareto最優(yōu)解的前沿面，并且也可看出乘客利益和運(yùn)營(yíng)企業(yè)的利益是一對(duì)矛盾體，具有博弈特色，在設(shè)置公交線路時(shí)需要權(quán)衡兩者設(shè)置線路，使兩者均能達(dá)到能夠接受的程度。

圖1 Pareto最優(yōu)解

6.結(jié)束語(yǔ)

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

參考文獻(xiàn)

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

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

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

[4]劉好德，楊曉光.基于改進(jìn)遺傳算法的公交線網(wǎng)優(yōu)化設(shè)計(jì)研究[J].計(jì)算機(jī)工程與應(yīng)用，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)化問(wèn)題[J].計(jì)算機(jī)工程與科學(xué)，2012，34（9）：109-112.

基金項(xiàng)目：河北省教育廳資助科研項(xiàng)目（項(xiàng)目編號(hào)：QN20132019）;唐山市科技計(jì)劃項(xiàng)目（項(xiàng)目編號(hào)：131302118a）。

作者簡(jiǎn)介：曹秀爽（1978—），女，碩士，實(shí)驗(yàn)師，主要研究方向：智能控制，人工智能。