李小川 劉媛華

摘要：針對(duì)電動(dòng)汽車充電站規(guī)劃問(wèn)題，建立以最小化充電站服務(wù)與用戶需求綜合成本為目標(biāo)的數(shù)學(xué)模型，并提出基于文化思想的改進(jìn)煙花算法求解該問(wèn)題。將煙花算法嵌入文化算法計(jì)算框架中，進(jìn)行底層搜索尋優(yōu)，提取其進(jìn)化過(guò)程中的有用信息組成信仰空間知識(shí)。信仰空間以粒子群迭代規(guī)則更新知識(shí)并通過(guò)接受函數(shù)指導(dǎo)種群空間進(jìn)化，以提高搜索效率。仿真實(shí)驗(yàn)結(jié)果證明，文化煙花算法在求解電動(dòng)汽車充電站規(guī)劃問(wèn)題時(shí)具有良好的穩(wěn)定性和較高的求解效率。

關(guān)鍵詞：電動(dòng)汽車充電站；最優(yōu)規(guī)劃；煙花算法；文化算法

DOIDOI：10.11907/rjdk.181021

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)文章編號(hào)：1672-7800（2018）008-0017-04

英文摘要Abstract：In order to optimize the layout of electric vehicle charging station，a mathematical model for the minimum gross costs of charginge station and users was established and an improved fireworks algorithm based on cultural algorithm was proposed.The initial fireworks algorithm was embedded in the computational framework of cultural algorithm to do the bottom search.The favorable information of the current optimal solution was taken as the knowledge of the belief space to guide the evolution direction of the fireworks through the acceptance function and improve the search efficiency.The simulation experiments show that the cultural fireworks algorithm has high stability and efficiency in solving the planning problem of electric vehicle charging station.

英文關(guān)鍵詞Key Words：electric vehicle charging station；optimal planning；fireworks algorithm；cultural algorithm

0 引言

電動(dòng)汽車符合當(dāng)今綠色出行理念，受到各國(guó)政策的大力支持，我國(guó)電動(dòng)汽車銷量也逐年增加。與此同時(shí)，充電站等基礎(chǔ)設(shè)施的缺乏限制了電動(dòng)汽車的大范圍推廣[1]。因此，研究充電站的合理布局問(wèn)題具有重要現(xiàn)實(shí)意義，受到各國(guó)學(xué)者的廣泛關(guān)注。Awasthi等[2]首先利用遺傳算法求解充電站選址問(wèn)題，再采用粒子群算法對(duì)求得的解作進(jìn)一步優(yōu)化，提高了尋優(yōu)精度；閆天澤等[3]基于模擬退火思想對(duì)粒子群算法慣性權(quán)重進(jìn)行改進(jìn)，通過(guò)算例驗(yàn)證了算法的可行性；馮超等[4]基于GIS提出多種群混合遺傳算法求解充電站布局規(guī)劃問(wèn)題，有效避開(kāi)了不適宜建立站點(diǎn)的區(qū)域；齊琳等[5]基于K中心點(diǎn)云模型思想調(diào)整粒子群算法慣性權(quán)重，增強(qiáng)了算法局部搜索能力。以上智能算法在求解精度方面已經(jīng)取得一定成果，但是大多數(shù)求解效率較低。因此，本文嘗試?yán)脽熁ㄋ惴ǖ谋l(fā)性以提高該問(wèn)題的求解效率。

煙花算法（Fireworks Algorithm，F(xiàn)WA）是一種具有爆發(fā)性的新型智能優(yōu)化算法，由北京大學(xué)學(xué)者Tan等[6]于2010年受到煙花爆炸過(guò)程可產(chǎn)生不同爆炸半徑和火花個(gè)數(shù)的啟發(fā)而提出。該算法原理簡(jiǎn)單明確、參數(shù)少、搜索效率高且較易于實(shí)現(xiàn)，已成功應(yīng)用于工作車間調(diào)度[7-8]、背包問(wèn)題[9]、Web服務(wù)優(yōu)化[10]、物流中心選址[11]等組合優(yōu)化領(lǐng)域，但目前尚未有文獻(xiàn)用煙花算法求解充電站規(guī)劃問(wèn)題。文化算法（Cultural Algorithm，CA ）由Reynolds[12]受人類通過(guò)吸取經(jīng)驗(yàn)指導(dǎo)自身或他人行為的啟發(fā)而提出，對(duì)智能算法的自組織過(guò)程賦予顯性指導(dǎo)條件。CA為智能算法的改進(jìn)提供了一種思想，各種符合CA結(jié)構(gòu)的算法都可作為種群空間的一部分參與進(jìn)化[13]，從而提高基本算法的性能。本文提出一種文化煙花算法（Cultural Fireworks Algrithm，CWPA）用于求解電動(dòng)汽車充電站規(guī)劃問(wèn)題，將煙花算法嵌入文化算法計(jì)算框架，煙花算法作為種群空間進(jìn)行底層迭代尋優(yōu)，提取其進(jìn)化過(guò)程中的有用信息組成信仰空間知識(shí)，信仰空間獨(dú)立進(jìn)化更新知識(shí)并通過(guò)接受函數(shù)指導(dǎo)種群空間進(jìn)化方向，避免進(jìn)化的盲目性，從而提高搜索效率，為電動(dòng)汽車充電站規(guī)劃問(wèn)題求解提供了一種新思路。

1 電動(dòng)汽車充電站規(guī)劃數(shù)學(xué)模型

1.1 問(wèn)題描述

電動(dòng)汽車充電站規(guī)劃問(wèn)題可描述為：在同時(shí)滿足充電站和用戶雙方需求的前提下，通過(guò)建立合理的選址和定容方案，使充電站建設(shè)成本、人力成本、維護(hù)成本等服務(wù)成本，以及用戶電費(fèi)成本、路途成本、排隊(duì)等待等需求成本之和最小化。同時(shí)還需滿足以下條件：①每個(gè)充電站的充電機(jī)數(shù)量需控制在一定范圍內(nèi)；②充電站應(yīng)盡量分散，相互之間距離不宜過(guò)??；③每個(gè)充電站覆蓋的服務(wù)區(qū)域不宜過(guò)大，即用戶與最近充電站間距不宜過(guò)大；④每個(gè)充電站的車流量需控制在一定范圍內(nèi)；⑤充電機(jī)充電負(fù)荷應(yīng)大于電動(dòng)汽車充電負(fù)荷。

1.2 參數(shù)定義

式（2）表示最小化充電站服務(wù)和用戶需求綜合成本的目標(biāo)函數(shù)；式（3）～（8）分別表示各項(xiàng)成本分量；式（9）約束了每個(gè)充電站充電機(jī)數(shù)量范圍；式（10）約束了每個(gè)充電站車流量范圍；式（11）約束了充電站總數(shù)范圍；式（12）表示每個(gè)充電站的服務(wù)半徑不能過(guò)大；式（13）表示相鄰充電站間距不宜過(guò)??；式（14）表示充電機(jī)充電負(fù)荷大于電動(dòng)汽車充電負(fù)荷。

2 求解電動(dòng)汽車充電站規(guī)劃的煙花文化算法

2.1 基本煙花算法

2.2 文化算法

文化算法為上層信仰空間（也稱信度空間）和底層種群空間組成的雙層并行結(jié)構(gòu)[15]，基本框架如圖1所示。信仰空間以接受函數(shù)的形式記錄種群迭代過(guò)程中的有用信息，并對(duì)其分析總結(jié)形成知識(shí)，以指導(dǎo)種群空間中粒子的后續(xù)進(jìn)化過(guò)程。文化算法框架為混合算法的協(xié)同進(jìn)化提供了模型[16]，雙層空間的信息共享機(jī)制使算法的自適應(yīng)進(jìn)化效率更高。

2.3 煙花算法改進(jìn)

針對(duì)電動(dòng)汽車充電站規(guī)劃問(wèn)題提出基于文化思想的改進(jìn)煙花算法，煙花算法作為種群空間進(jìn)行底層尋優(yōu)，可以充分利用其強(qiáng)局部搜索能力，對(duì)此類不定點(diǎn)連續(xù)性區(qū)域的搜索效率較高。但是煙花算法個(gè)體之間進(jìn)化獨(dú)立，也容易陷入局部最優(yōu)，為此選取每次迭代中的部分較優(yōu)煙花作為信仰空間群體，以粒子群算法的迭代過(guò)程進(jìn)行知識(shí)演化，并通過(guò)Accept（）函數(shù)指導(dǎo)煙花群體進(jìn)化過(guò)程。兩空間信息共享、相互促進(jìn)，使算法同時(shí)具有較強(qiáng)的局部和全局搜索能力。

2.4 算法流程描述

（1）初始化算法參數(shù)，包括煙花個(gè)數(shù)n1、爆炸半徑基數(shù)A、火花基數(shù)S、火花個(gè)數(shù)約束常數(shù)α與β、高斯變異煙花數(shù)m、最大迭代次數(shù)G、初始接受代數(shù)accept_stepinit。

（2）采用數(shù)值型編碼初始化n1個(gè)煙花，設(shè)置信仰空間為空集。

（3）算法迭代。種群空間按照式（15）-（22）進(jìn)行迭代尋優(yōu)，信仰空間取煙花群體規(guī)模的2/3，按照粒子群算法的搜索過(guò)程進(jìn)行自身迭代更新，每次迭代中提取當(dāng)前最優(yōu)煙花作為知識(shí)替換信仰空間中的最差個(gè)體。

3 仿真結(jié)果與分析

3.1 實(shí)驗(yàn)仿真

為驗(yàn)證本文提出的文化煙花算法求解復(fù)雜環(huán)境下電動(dòng)汽車充電站選址規(guī)劃問(wèn)題的效能，利用Matlab R2012a軟件，以擁有25個(gè)需求點(diǎn)的區(qū)域（見(jiàn)表1）為例進(jìn)行仿真實(shí)驗(yàn)，并與基本煙花算法、基本粒子群算法以及文獻(xiàn)＼[5＼]中提出的IPSO所求結(jié)果進(jìn)行對(duì)比。仿真參數(shù)為：①CFWA參數(shù)為：煙花種群規(guī)模15，爆炸半徑基數(shù)為A=2，基本爆炸火花數(shù)S=20，高斯變異煙花數(shù)l=6，α=0.05，β=05，初始接受代數(shù)accept_stepinit=5；②FWA基本參數(shù)與CFWA相同；③PSO參數(shù)為：種群規(guī)模15，學(xué)習(xí)因子c1=c2=2，慣性權(quán)重w=0.7。每種算法獨(dú)立運(yùn)行20次，最大迭代次數(shù)均為200。每個(gè)充電站的充電機(jī)數(shù)量為5～15臺(tái)，每臺(tái)充電機(jī)投入成本5萬(wàn)元，充電站建設(shè)成本50萬(wàn)元，設(shè)計(jì)年限為20年，貼現(xiàn)率5%，每臺(tái)充電機(jī)平均人力成本3.6萬(wàn)元，平均維修成本0.8萬(wàn)元，充電機(jī)發(fā)生故障的懲罰成本0.5萬(wàn)元，平均故障次數(shù)10次，充電機(jī)每次故障的平均維修時(shí)間為2h，電動(dòng)汽車充電電費(fèi)單價(jià)為0.5元/KWh，每個(gè)充電站的最小車流量為30，電動(dòng)汽車充電額定功率為20KW，充電機(jī)充電功率為500KW，每輛車年均充電100次，電動(dòng)汽車充電的單位路途成本為0.5元，電動(dòng)汽車充電平均等待時(shí)間為0.1h，相鄰充電站最小間距1.5km。

3.2 仿真結(jié)果分析

表2為CFWA、FWA、PSO以及文獻(xiàn)[5]提出的IPSO4種算法求解電動(dòng)汽車充電站規(guī)劃問(wèn)題統(tǒng)計(jì)結(jié)果，圖2～圖4分別為CFWA、FWA和PSO求得的最優(yōu)規(guī)劃方案。由表2可知，CFWA所求最優(yōu)綜合成本為392.96萬(wàn)元，充電站個(gè)數(shù)為5個(gè)，F(xiàn)WA和PSO所求最優(yōu)綜合成本分別為470.28和527.93萬(wàn)元，充電站個(gè)數(shù)均為6個(gè)，說(shuō)明CFWA求解結(jié)果較FWA和PSO更優(yōu)；在平均綜合成本方面，CFWA的結(jié)果明顯優(yōu)于FWA和PSO，說(shuō)明CFWA具有更好的穩(wěn)定性；在平均收斂代數(shù)和平均收斂時(shí)間方面，CFWA也優(yōu)于FWA和PSO，說(shuō)明CFWA求解效率更高；CFWA求得充電站個(gè)數(shù)與IPSO相同，但最優(yōu)綜合成本與收斂時(shí)間均優(yōu)于IPSO。總體而言，CFWA相較于FWA和PSO，在求解電動(dòng)汽車選址規(guī)劃問(wèn)題時(shí)表現(xiàn)出更優(yōu)的性能，較IPSO求解效率更高。

4 結(jié)語(yǔ)

本文首次嘗試采用煙花算法求解電動(dòng)汽車充電站選址規(guī)劃問(wèn)題，將煙花算法嵌入文化算法計(jì)算框架，信仰空間利用兩空間的信息共享機(jī)制指導(dǎo)種群空間進(jìn)化方向，改進(jìn)了基本煙花算法在求解電動(dòng)汽車充電站選址規(guī)劃研究時(shí)易陷入局部最優(yōu)的不足，提高了全局搜索能力。實(shí)驗(yàn)仿真驗(yàn)證了基于文化思想的改進(jìn)煙花算法在求解電動(dòng)汽車充電站選址規(guī)劃研究問(wèn)題時(shí)的高效性和穩(wěn)定性。

參考文獻(xiàn)：

[1] 劉文霞，張蕾蕾，劉宗歧，等.城市純電動(dòng)汽車發(fā)展模式論證方法[J].電力系統(tǒng)自動(dòng)化，2014，38（24）：34-40.

[2] AWASTHI A，VENKITUSAMY K，PADMAN S.Optimal planning of electric vehicle charging station at the distribution system using hybrid optimization algorithm[J].Energy，2017，133（5）：70-78.

[3] 閆天澤，邱曉燕，劉延博，等.基于引入模擬退火思想的改進(jìn)粒子群算法的電動(dòng)汽車充電站最優(yōu)規(guī)劃[J].電測(cè)與儀表，2017，54（6）：11-16.

[4] 馮超，周步祥，林楠，等.電動(dòng)汽車充電站規(guī)劃的多種群混合遺傳算法[J].電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)，2013，25（6）：123-129.

[5] 齊琳，姚儉，王心月.基于改進(jìn)粒子群算法的電動(dòng)汽車充電站布局優(yōu)化[J].公路交通科技，2017，34（6）：136-143.

[6] TAN Y，ZHU Y C.Fireworks algorithm for optimization[C].International Conference on Advances in Swarm Intelligence，2010：355-364.

[7] 包曉曉，葉春明，黃霞.煙花算法求解JSP問(wèn)題的研究[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（3）：247-252.

[8] 曹磊，葉春明，黃霞.應(yīng)用混沌煙花算法求解置換流水車間問(wèn)題[J].計(jì)算機(jī)應(yīng)用與軟件，2016，33（11）：188-192.

[9] 薛俊杰，王瑛，孟祥飛，等.二進(jìn)制反向?qū)W習(xí)煙花算法求解多維背包問(wèn)題[J].系統(tǒng)工程與電子技術(shù)，2017，39（2）：451-458.

[10] 張以文，吳金濤，趙姝，等.基于改進(jìn)煙花算法的Web服務(wù)組合優(yōu)化[J].計(jì)算機(jī)集成制造系統(tǒng)，2016，22（2）：422-432.

[11] 李小川，劉媛華.基于改進(jìn)煙花算法的物流配送中心選址研究[J].軟件導(dǎo)刊，2017，16（11）：153-156.

[12] REYNOLDS R G.An introduction to cultural algorithms [C].Proceedings the 3rd Annual Conference on Evolutionary Programming，1994：131-139.

[13] 黎明，江樂(lè)旗，陳昊.基于文化算法的無(wú)人飛行器航跡規(guī)劃[J].模式識(shí)別與人智能，2017，30（2）：152-161.

[14] GAO H Y，DIAO M.Cultural firework algorithm and its application for digital filters design[J].International Journal of Modeling，Identification and Control，2011，14（4）：324-331.

[15] REYNOLDS R G，KINNAIRD H L.Optimization problem solving with auctions in cultural algorithms [J].Memetic Computing，2013，5（2）：83-94.

[16] 吳亞麗，徐麗青.一種基于粒子群算法的改進(jìn)多目標(biāo)文化算法[J].控制與決策，2012，27（8）：1127-1132.

（責(zé)任編輯：黃 ?。?/p>