李小川 劉媛華

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

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

DOIDOI：10.11907/rjdk.181021

中圖分類號：TP311

文獻標識碼：A 文章編號文章編號：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 引言

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

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

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

1.1 問題描述

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

1.2 參數(shù)定義

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

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

2.1 基本煙花算法

2.2 文化算法

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

2.3 煙花算法改進

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

2.4 算法流程描述

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

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

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

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

3.1 實驗仿真

為驗證本文提出的文化煙花算法求解復(fù)雜環(huán)境下電動汽車充電站選址規(guī)劃問題的效能，利用Matlab R2012a軟件，以擁有25個需求點的區(qū)域（見表1）為例進行仿真實驗，并與基本煙花算法、基本粒子群算法以及文獻＼[5＼]中提出的IPSO所求結(jié)果進行對比。仿真參數(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。每種算法獨立運行20次，最大迭代次數(shù)均為200。每個充電站的充電機數(shù)量為5～15臺，每臺充電機投入成本5萬元，充電站建設(shè)成本50萬元，設(shè)計年限為20年，貼現(xiàn)率5%，每臺充電機平均人力成本3.6萬元，平均維修成本0.8萬元，充電機發(fā)生故障的懲罰成本0.5萬元，平均故障次數(shù)10次，充電機每次故障的平均維修時間為2h，電動汽車充電電費單價為0.5元/KWh，每個充電站的最小車流量為30，電動汽車充電額定功率為20KW，充電機充電功率為500KW，每輛車年均充電100次，電動汽車充電的單位路途成本為0.5元，電動汽車充電平均等待時間為0.1h，相鄰充電站最小間距1.5km。

3.2 仿真結(jié)果分析

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

4 結(jié)語

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

參考文獻：

[1] 劉文霞，張蕾蕾，劉宗歧，等.城市純電動汽車發(fā)展模式論證方法[J].電力系統(tǒ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] 閆天澤，邱曉燕，劉延博，等.基于引入模擬退火思想的改進粒子群算法的電動汽車充電站最優(yōu)規(guī)劃[J].電測與儀表，2017，54（6）：11-16.

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

[5] 齊琳，姚儉，王心月.基于改進粒子群算法的電動汽車充電站布局優(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問題的研究[J].計算機工程與應(yīng)用，2017，53（3）：247-252.

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

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

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

[11] 李小川，劉媛華.基于改進煙花算法的物流配送中心選址研究[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] 黎明，江樂旗，陳昊.基于文化算法的無人飛行器航跡規(guī)劃[J].模式識別與人智能，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].控制與決策，2012，27（8）：1127-1132.

（責任編輯：黃 健）