張志宇 張會林 徐 輝 葉玉鳳

(上海理工大學光電信息與計算機工程學院 上海 200093)

基于遺傳交叉改進粒子群算法的充電站布局

張志宇 張會林 徐 輝 葉玉鳳

(上海理工大學光電信息與計算機工程學院 上海 200093)

為了合理地規(guī)劃城市電動汽車充電站布局，采用一種基于遺傳交叉改進粒子群算法的尋優(yōu)處理方案。在傳統(tǒng)粒子群算法的基礎上，引入局部極值對速度更新公式進行優(yōu)化，采用自適應慣性權重，并且對當前種群的最優(yōu)解和每個粒子最優(yōu)解進行交叉操作產(chǎn)生新解。最后通過改進后算法對城市算例進行求解。結果驗證了模型的有效性和準確性，表明改進算法在保持全局最優(yōu)解的同時能提高70%收斂速度，有效降低總成本、提高便利性。

充電站 粒子群算法 遺傳交叉 慣性權重

0 引 言

隨著全球能源日趨緊張，生態(tài)環(huán)境日益惡化，新能源汽車的開發(fā)與應用問題已經(jīng)成為各國汽車工業(yè)積極探索的焦點[1]?？萍及l(fā)展推動電動汽車電池技術的不斷革新，使得許多歐美國家的電動汽車產(chǎn)業(yè)逐步規(guī)?；袊蔡岢龅?020年電動汽車保有量達到500萬輛的發(fā)展計劃[2]。因此，如何合理建設城市電動汽車充電站是現(xiàn)階段所面臨的首要任務。

目前，根據(jù)電動汽車充電的方式不同，電動汽車充電設施可以分為充電樁、充電站、換電站三種類型。楊現(xiàn)青等[3]簡要分析了影響充電站布局規(guī)劃的因素，考慮需求點分布，建立了收益最大化得非線性目標函數(shù)，但是只考慮到了建設和運營成本，忽略了用戶的出行使用成本。應夏暉等[4]構建了基于充電站運營費用和用戶充電費用的最小化模型，并用遺傳算法進行了求解，遺傳求解時采用固定的交叉變異概率，容易導致優(yōu)良基因遭到破壞，從而陷入局部最優(yōu)。馮超等[5]將標準遺傳算法和交叉定位分配算法結合，形成一種新的混合算法，建立多種群協(xié)同進化搜索，但是由于種群數(shù)量多，可能造成算法計算量大和求解時間長的現(xiàn)象。Pan等[6]充分考慮城市電網(wǎng)的電網(wǎng)結構強度，在分析正常城市生活荷載變化的時空特征的基礎上，提出了一種新的集中充電站布局策略。通過上述分析可知，雖然國內外有諸多文獻對充電站的布局規(guī)劃有過研究，但是考慮問題時并不是很全面，導致算法尋優(yōu)的效果不是很理想。因此，本文建立了以經(jīng)濟性和便利性為目標的充電站模型，著重改進了傳統(tǒng)的粒子群算法，并且引入遺傳算法的交叉操作，利用改良后的算法對城市小區(qū)實例進行了驗證求解，最終確定了充電站的規(guī)劃布局。

1 影響充電站規(guī)劃的因素

1.1 交通便利性

交通便利性主要體現(xiàn)在充電站附近的車道情況和車流量大小[7]。車道數(shù)量越多，車流量越大，則這點的交通便利性越好，充電站建設在這里能夠利益最大化。當然，充電站的服務半徑不宜過大或過小，太大了不能滿足電動汽車的續(xù)航范圍，太小了會導致過于集中以至于經(jīng)濟浪費。

1.2 充電需求量

充電需求量是指某一時間段特定區(qū)域內一定數(shù)量的電動汽車對電能的需求量，它直接影響充電站的地理位置選取和所需提供的功率的大小。只有建設充電容量足夠大的充電站，才能滿足待充汽車的需求量。因此，在對充電站進行規(guī)劃之前，先應該計算出當前區(qū)域的電動汽車充電總負荷量。

1.3 經(jīng)濟性

經(jīng)濟性最優(yōu)是充電站建設的重要目標之一。這主要表現(xiàn)在兩個方面，一方面投資者希望投資建設費用和運行成本最低；另一方面用戶希望能花費最少的費用獲得最好的充電服務，具體體現(xiàn)在用戶從需求點到達充電站所消耗的路上成本最小，它和需求點到充電站的距離成正比例關系。

2 選址模型

2.1 經(jīng)濟性

經(jīng)濟性主要從三個方面考慮，分別是初期投資固定成本、充電站運行成本和用戶充電成本。

MinZ=Z1+Z2+Z3

(1)

(2)

式中：Z1為初期投資固定成本。F為購地、變壓器、充電機及其他設備費用，m為充電站數(shù)目，n為充電站運行年限，r為投資回收率。

(3)

式中：Z2為充電站運行成本(維護費用、材料、人員工資等)。運行成本折算到初始投資費用，α為折算系數(shù)。

Z3=c·k·η·t(∑i∈I∑j∈JgijniDij)×10-4

(4)

式中：Z3為一年充電費用，c為一年天數(shù)365，k為每輛車每天充電次數(shù)，η為道路的曲折系數(shù)，t為汽車行駛每公里成本，I為充電需求點的集合，J為充電站的集合，gij為點i是否到充電站j充電(到j充電則為1，否則為0)，ni為需求點i處需充電的汽車數(shù)量，Dij為點i到充電站j的直線距離。

約束條件：

(5)

式(5)的目的是保證在充電過程中只到一個充電站充電。

Dij≤Rj

(6)

式(6)的目的是充電半徑應該大于汽車到充電站的距離。

∑i∈IPi≤Sje(Sj)cosφj

(7)

式中：Pi為到j充電站充電的電動汽車所需負荷，Sj為j充電站容量，e(Sj)為負載率，cosφj為功率因數(shù)。式(7)的目的是為了保證充電站的容量要大于到該充電站充電的電動汽車的所需總負荷。

2.2 交通便利性

在這里交通便利性以各用戶到相應充電站的平均距離來表征，可以表征為：

(8)

充電站數(shù)目確定：

(9)

式(9)表示每天到充電站充電的所有汽車總充電需求量比上充電站充電的電動汽車的所需總負荷取整加1。

3 算法優(yōu)化

粒子群算法(PSO)屬于進化算法的一種，起源于對鳥群捕食的行為研究[8]。PSO算法的研究對象是一群隨機粒子，它們有各自自己的屬性(位置和速度)。這些粒子在空間中運動不斷地更新自己，并且能夠保留記憶每個粒子到當前為止所找到的最優(yōu)位置以及所有粒子目前找到的全局最優(yōu)位置。通過不斷地更新速度和位置來獲取最優(yōu)解。

標準PSO算法的數(shù)學表述為：假設在一個q維搜索空間中有m個粒子，第i個粒子的位置向量和速度向量分別為：

xi=(xj1,xi2,…,xid)

vi=(vi1,vi2,…,vid)

通過式(10)、式(11)的每一次迭代來更新速度和位置：

vid(t+1)=w×vid(t)+C1×rand1×

[pid(t)-xid(t)]+c2×rand2×

[pdk(t)-xid(t)]

(10)

xid(t+1)=xid(t)+vid(t+1)

(11)

式中：vid(t+1)為更新后的速度，w為慣性因子(表示搜索范圍)，vid(t)為當前粒子速度，c1、c2為加速因子，rand1、rand2為[0，1]之間的隨機數(shù)，xid(t)為當前粒子的位置，pid(t)、pgd(t)分別為粒子個體和全局的極值。xid(t+1)為更新后的粒子位置，xid(t)為當前粒子位置。

PSO算法規(guī)則簡單，易于實現(xiàn)，收斂速度較快，特別是在算法運行的初期，但是它也有精度較低和容易陷入局部最優(yōu)等缺點。在式(10)中，我們可以看到粒子的速度更新依賴于粒子自身的歷史最優(yōu)值pid(t)和全局歷史最優(yōu)值pgd(t)。這是在對全局進行搜索，忽略了對局部搜索的力度，一定程度上可能使算法不能取得正確的最優(yōu)解。因此，在這里引入一個當代種群粒子的最優(yōu)值pnd(t)，它能更好地實現(xiàn)粒子和群體之間的信息交流。實現(xiàn)局部搜索和全局搜索的結合，提高精準度。更新后的速度公式為：

vid(t+1)=w×vid(t)+c1×α×rand1×

[pid(t)-xid(t)]+c2×rand2×

[pgd(t)-xid(t)]+c1×(1-α)×

rand1×[pnd(t)-xid(t)]

(12)

從式(12)可知，改進后的粒子速度與自身歷史最優(yōu)值pid(t)和全局歷史最優(yōu)值pgd(t)以及當代種群粒子的最優(yōu)值pnd(t)，理論上能夠使PSO算法在保證收斂性的同時不陷入局部最優(yōu)。其中α是一個可變權重值，體現(xiàn)了粒子的速度更新在參考粒子個體最優(yōu)值的同時，一定比重地參考當代種群的最優(yōu)值。當然，慣性權重也是一個和重要的參數(shù)，它直接影響算法的收斂精度，這里利用線性慣性權重，更新公式為：

w(t+1)=4w(t)(1-t)

(13)

遺傳算法(GA)是一種模仿自然界生物進化的全局搜索優(yōu)化方法，借鑒了達爾文的進化論和孟德爾的遺傳學說[9]。遵循生物進化中優(yōu)勝劣汰、適者生存的原理，通過編碼與不斷進化尋優(yōu)，最終獲得最優(yōu)解函數(shù)值。在GA算法中，主要依靠選擇、交叉和變異三個操作。交叉操作是遺傳算法產(chǎn)生后代的主要方式，通過交叉實現(xiàn)父代個體的信息交流，這也是新個體的主要產(chǎn)生形式。而PSO算法中，粒子之間并沒有直接通過信息交流來產(chǎn)生新的解。因此，在這里引入GA算法的交叉操作，對PSO算法的迭代結果(全局最優(yōu)位置和每個粒子的最優(yōu)位置)進行交叉操作，理論上能夠利用信息交流產(chǎn)生新解，有效地跳出局部收斂。交叉公式為：

sid=rpid(t)+(1-r)pgd(t)

(14)

式中，sid(t)為進行完第t代交叉后的產(chǎn)生的第i個粒子的d維量，r為(0，1)之間的隨機數(shù)。

算法步驟：

1) 初始化參數(shù)，設定粒子數(shù)量和最大進化代數(shù)，隨機初始化粒子的位移，速度選取[0，1]的隨機數(shù)，并且對慣性權重w，最大進化代數(shù)tmax個體最優(yōu)解pid(t)，全局最優(yōu)值pgd(t)以及初代種群粒子的最優(yōu)值pnd(t)進行設定。

2) 計算目標函數(shù)，并對初始種群進行評價，計算改進后的慣性權重，利用式(11)、式(12)對粒子進行位置速度更新。

3) 將該粒子的更新后新位置和原來的pid進行比較，若前者由于后者，則將pid替換；若pid優(yōu)于pgd，則令pgd=pid。

4) 判斷所有粒子是否迭代更新完畢，完畢則進行下一步操作，否則轉到步驟2)繼續(xù)。

5) 利用式(14)對已經(jīng)迭代完成的粒子進行遺傳交叉操作。

6) 如果t

4 驗證分析

為驗證本文所提出算法(簡稱LWGPSO)的可行性和有效性，利用以下選址實例進行測試。上海市一個規(guī)劃區(qū)面積為13 km2,在規(guī)劃時間內電動汽車的保有量為2 357輛，通過分析汽車的分布情況，確定劃分為20個充電需求小區(qū)。小區(qū)的幾何坐標中心及電動汽車數(shù)量如表1所示。

表1 小區(qū)坐標及電動汽車數(shù)量

續(xù)表1

在規(guī)劃區(qū)內建設充電站為電動汽車提供持續(xù)電能，需要先對一些必要的參數(shù)進行合理化的選取，如初始投資費用、充電效率、充電服務半徑等。部分參數(shù)設置如表2所示。

表2 規(guī)劃區(qū)內參數(shù)選取

計劃在規(guī)劃區(qū)內建設充電站供電動汽車補給電量，通過粗略計算確定需要建設5座充電站，現(xiàn)有10座候選充電站的位置如表3所示。

表3 候選充電站坐標

在這里采用PSO和改進后的LWGPSO算法分別對選址問題進行編碼，運用MATLAB對實例編寫程序，可以得到模型的優(yōu)化結果。最終確定充電站及服務小區(qū)分別如表4、表5所示。

表4 (PSO算法)充電站坐標及服務小區(qū)

表5 (LWGPSO算法)充電站坐標及服務小區(qū)

根據(jù)表4、表5所示的結果，我們可以確定出LWGPSO算法求得的充電站的選址分布情況，如圖1所示。兩種算法求解的迭代圖如圖2所示。

圖1 LWGPSO算法確定的充電站及服務小區(qū)

圖2 兩種算法的迭代曲線

從圖2可知，PSO求解選址問題需要進化140代左右，最終確定的最優(yōu)解函數(shù)值為48.6，經(jīng)過計算得到充電站運行年費用為1 586.91萬元；而經(jīng)過優(yōu)化后的LWGPSO算法只需要進化40代就能取得最優(yōu)解函數(shù)值為48.3，波動次數(shù)少，經(jīng)過計算得到充電站運行年費用為1 558.32萬元。兩種選址算法的性能比較如表6所示。

表6 兩種選址算法結果比較

通過結果比較可以看出，對PSO算法優(yōu)化并結合GA算法后，明顯加快了算法求解的收斂速度。不僅減少了算法計算時間和迭代次數(shù)，同時也對目標數(shù)值有所優(yōu)化。各個充電站服務劃分明確，基本上符合就近充電原則，實現(xiàn)了費用和便利的雙優(yōu)化目標。

5 結 語

本文對影響充電站規(guī)劃選址的因素進行深入分析，建立了合理化的選址模型，利用改進后的LWGPSO算法求解規(guī)劃問題。改進后的算法處理問題時不僅更加準確，而且克服了PSO算法容易陷入局部最優(yōu)、收斂速度慢等缺點，在一定程度上使得計算結果更優(yōu)于傳統(tǒng)算法。通過對算例的仿真求解，取得了相應的結果，并且更進一步驗證了算法的可行性和模型的準確性，為充電站布局規(guī)劃工作提供了一定的理論經(jīng)驗。

[1] 張寶中.新能源光伏汽車充電站發(fā)展現(xiàn)狀與分析[J].科技與創(chuàng)新,2016(16):106-107.

[2] 朱柯羽.城市電動汽車充電站選址規(guī)劃研究[J].科技展望,2016,26(8):263-264.

[3] 楊現(xiàn)青,劉法勝,楊玲玲,等.電動汽車充電站選址優(yōu)化研究[J].交通科技與經(jīng)濟,2016,18(3):14-18.

[4] 應夏輝,李錦霞.電動汽車充電站的選址優(yōu)化研究[J].交通科技與經(jīng)濟,2014,16(1):43-46.

[5] 馮超,周步祥,林楠.電動汽車充電站規(guī)劃的多種群混合遺傳算法[J].電力系統(tǒng)及其自動化,2013,25(6):123-129.

[6] Pan Z J,Zhang Y.A novel centralized charging station planning strategy considering urban power network structure strength[J].Electric Power Systems Research,2016,136:100-109.

[7] 楊鐸.計及電動汽車電池集中充電站接入的電網(wǎng)穩(wěn)定性分析[D].北京:華北電力大學電氣與電子工程學院,2014.

[8] 張俊溪,張嘉桐,張玉梅.一種改進的粒子群優(yōu)化算法[J].陜西師范大學學報,2016,44(2):15-20.

[9] 陳香.解決面試工作安排中專家資源合理分配問題[J].湖南農(nóng)機,2014,41(10):29-30.

LAYOUTOFCHARGINGSTATIONSBASEDONIMPROVEDPARTICLESSWARMOPTIMIZATIONWITHGENETICCROSSOVER

Zhang Zhiyu Zhang Huilin Xu Hui Ye Yufeng

(SchoolofOptical-ElectricalandComputerEngineering,UniversityofShanghaiforScienceandTechnology,Shanghai200093,China)

In order to plan the layout of electric vehicle charging station reasonably, this paper adopts an optimization scheme based on improved particle swarm optimization with genetic crossover. On the basis of traditional particle swarm optimization, the local extremum is introduced to optimize the speed updating formula, and the adaptive inertia weight is adopted. A new solution is generated by the cross operation of the optimal solution of the current population and each particle optimal solution. At last, the improved algorithm is used to solve the urban examples. The results verify the validity and accuracy of the model, and show that the improved algorithm can improve the convergence rate of 70% while getting the global optimal solution and effectively reduce the total cost, improve the convenience.

Charging station Particle swarm optimization Genetic crossover Inertia weight

TP3 TP18

A

10.3969/j.issn.1000-386x.2017.10.049

2016-12-01。滬江基金資助項目(B1402/D1402)。張志宇，碩士生，主研領域：模式識別與人工智能。張會林，副教授。徐輝，碩士生。葉玉鳳，碩士生。