趙文清 王繼發(fā)

（華北電力大學(xué)計(jì)算機(jī)系 保定 071003）

1 引言

電動汽車的動力采用對電動車充電，放置充放電電瓶作為存放電動汽車驅(qū)動動力的承載裝置，但是電瓶對電動汽車所能承擔(dān)的動力有限。因此，對于電動汽車充電問題便成為當(dāng)今社會致力于研究該內(nèi)容的專家學(xué)者的“重頭戲”，在滿足電動汽車日常充電的需求的基礎(chǔ)上，還需對充電路徑進(jìn)行深入研究并給予優(yōu)化，以此保證日漸增多的電動汽車在最有效的時間內(nèi)完成對車輛的充電。

電動汽車充電路徑規(guī)劃可以從多個角度進(jìn)行分析。文獻(xiàn)［1～2］考慮交通網(wǎng)絡(luò)和配電網(wǎng)絡(luò)等路徑引導(dǎo)制約因素，將交通路況信息阻礙和充電樁電力調(diào)度作為研究目標(biāo)，達(dá)到路徑規(guī)劃目的。文獻(xiàn)［3］把動態(tài)路徑規(guī)劃問題分割成初始階段路徑選擇和充電樁資源搶奪，把多目標(biāo)路徑規(guī)劃的時間離散化處理，佐以資源智能預(yù)警，實(shí)現(xiàn)動態(tài)網(wǎng)絡(luò)規(guī)劃。文獻(xiàn)［4～7］將路徑規(guī)劃算法作為主要研究對象，通過優(yōu)化算法提高多目標(biāo)路徑的收斂與搜索能力。文獻(xiàn)［8］針對非滿載問題進(jìn)行研究，探索最優(yōu)解的性質(zhì)，分析總結(jié)了較緊的上下界，以及路徑規(guī)劃過程的最壞情況與解決方案。

本文通過對交通網(wǎng)絡(luò)、配電網(wǎng)絡(luò)、車輛本身的各項(xiàng)屬性進(jìn)行分析，定量的設(shè)置電動汽車在路徑規(guī)劃過程采用智能水滴算法所涉及到的速度、泥土量等數(shù)據(jù)，利用智能水滴算法的數(shù)學(xué)模型，采用libsvm 對所選數(shù)據(jù)列表進(jìn)行預(yù)測分析，獲取交叉驗(yàn)證精度，確定最佳路徑，實(shí)現(xiàn)智能水滴算法在電動汽車充電路徑規(guī)劃上的應(yīng)用。

2 智能水滴算法模型構(gòu)建

2.1 智能水滴及其算法

智能水滴算法是根據(jù)自然界水滴匯集成流，然后流入大海的過程中“自由選擇”流經(jīng)路徑的現(xiàn)象仿真得到的，Shah-Hosseini 根據(jù)水滴的這些屬性，將之命名為智能水滴（IWD），從而演化出智能水滴算法［9］。根據(jù)水滴的特性可以構(gòu)建出抽象的數(shù)學(xué)模型，這種模型的屬性主要是包含水滴中攜帶的泥土量soil 和水滴在不斷更新泥土量的同時不斷變化的速度velocity。文獻(xiàn)［10～12］描述了智能水滴算法的實(shí)現(xiàn)原理及其合理性，文獻(xiàn)［13～14］建立模型驗(yàn)證了其性能的優(yōu)勢，文獻(xiàn)［15～16］分析算法的局限性，優(yōu)化智能水滴的尋優(yōu)方式，提高算法的搜索能力。文獻(xiàn)［17～19］采用不同算法與智能水滴算法混合，使用改進(jìn)的智能水滴算法在車場分配和路徑搜索選擇上展開研究。

2.2 智能水滴算法數(shù)學(xué)模型

智能水滴所擁有的兩個重要屬性是水滴經(jīng)過路徑所含泥土量和水滴的當(dāng)前速率。但是由于水的流動特性，導(dǎo)致這兩個屬性都是處于變化狀態(tài)的，因此，智能水滴算法的目的是按照某些約束力，從某個節(jié)點(diǎn)到下一個節(jié)點(diǎn)找到水滴前進(jìn)的最佳的一條路徑。

通過數(shù)學(xué)定量分析對智能水滴算法進(jìn)行定量分析。假設(shè)水滴的當(dāng)前位置為i，此時的速度為velocity（i），下一節(jié)點(diǎn)的位置為j，j位置的速度為velocity（j），由速度與從i 到j(luò) 的泥土量soil（i，j）成非線性反比關(guān)系可知表達(dá)式為

其中，as、bs、cs為用戶預(yù)先設(shè)定的靜態(tài)參數(shù)。

在水滴位置的變化過程中，水滴的含沙量的變化量和路徑中的變化量是相等的，泥土量的變化量和水滴移動所需的時間呈現(xiàn)非線性反比關(guān)系：

其中，as、bs、cs為可設(shè)定的模擬參數(shù)。time(i，j)為時間函數(shù)。

當(dāng)水滴在兩節(jié)點(diǎn)間移動過程中，水滴中的含沙量和路徑中河道的泥土量在實(shí)時變化時的公式更新可以表示為

其中，ρn∈(0，1)，權(quán)重系數(shù)，一般取值0.9。

水滴的位置在時刻變化，在水滴到達(dá)下一節(jié)點(diǎn)前，會有多項(xiàng)泥土量的阻礙，也會形成多條路徑的選擇，水滴為了更快、更容易到達(dá)下一節(jié)點(diǎn)，會選擇一條最佳路徑進(jìn)行前進(jìn)，在這條路徑中，水滴在行進(jìn)時的含沙量最少，速度最大。按照智能水滴在兩節(jié)點(diǎn)間位置移動，假設(shè)路徑概率為(j)，表達(dá)式為

其中，soil(i，j)兩個節(jié)點(diǎn)間的泥土量；VC(IWD)為智能水滴節(jié)點(diǎn)集合；f(soil(i，j))的表達(dá)式如下：

其中，ε為極小的正數(shù)，其作用是保證函數(shù)f的分母不為零。函數(shù)g 是i，j 兩個位置之間泥土量的修正函數(shù)，表達(dá)式如下：

其中，函數(shù)min 表示當(dāng)前節(jié)點(diǎn)未流過的所有路徑的泥土量的最小值。

為實(shí)現(xiàn)尋找水滴流入大海的最優(yōu)路徑，可以在智能水滴算法的的數(shù)學(xué)模型的基礎(chǔ)上進(jìn)行模擬水滴選擇路徑的流程。將擬定解決的問題數(shù)據(jù)集作為輸入信息，得到的優(yōu)化解為輸出信息。采用迭代的方式對數(shù)據(jù)集的迭代，當(dāng)?shù)螖?shù)不夠或者是精度沒有滿足，隨機(jī)選擇當(dāng)前節(jié)點(diǎn)，然后根據(jù)數(shù)學(xué)條件選擇下一節(jié)點(diǎn)，選擇的依據(jù)是水滴的含沙量和河床中所含泥土量。

3 基于IWD算法的路徑規(guī)劃

3.1 智能水滴算法設(shè)計(jì)

路徑規(guī)劃需要考慮電動汽車在行駛過程中可能出現(xiàn)的各種阻礙。在本文中，將可能出現(xiàn)在道路規(guī)劃中的交通網(wǎng)絡(luò)、配電網(wǎng)絡(luò)、電動汽車本身阻礙看作智能水滴算法的泥土量，在泥土量不同的情況下，選擇路徑的概率也會不同，根據(jù)路徑情況，選擇路徑概率大的最為最優(yōu)路徑。根據(jù)最優(yōu)路徑，產(chǎn)生最優(yōu)規(guī)劃方案。

3.2 智能水滴算法模擬實(shí)現(xiàn)

上一節(jié)中提到將交通網(wǎng)絡(luò)、配電網(wǎng)絡(luò)、車輛本身所產(chǎn)生的對充電路徑造成阻礙的一些因素看作智能水滴的泥土量，將不同類型的泥土量進(jìn)行量化模擬。在泥土量設(shè)置中，設(shè)置了51 項(xiàng)泥土量，在大數(shù)據(jù)的模擬環(huán)境能夠更好地展現(xiàn)智能水滴算法的特點(diǎn)。根據(jù)模擬的泥土量數(shù)據(jù)，在智能水滴的兩個屬性的基礎(chǔ)上，對數(shù)據(jù)進(jìn)行處理，從而實(shí)現(xiàn)路徑選擇的目的。

根據(jù)智能水滴算法，聲明路徑中的泥土量pathsoil 并對其進(jìn)行初始化，將路徑中的泥土量設(shè)置初始值為1000。將智能水滴分代迭代，設(shè)置為30代，每代執(zhí)行以下操作。

創(chuàng)建IWD，對IWD 進(jìn)行迭代，隨機(jī)選擇設(shè)定泥土量的行數(shù)，在選擇的行數(shù)長度中計(jì)算pathsoil 范圍內(nèi)的一部分，然后更新IWD 訪問列表，查找IWD從i 到j(luò) 的概率，其中j 不在訪問路徑列表中。將每一代的IWD 數(shù)據(jù)分為10 個子集，把每個IWD 從當(dāng)前位置移動到下一位置，直到把自己全部遍歷。一個子集的開始，根據(jù)智能水滴算法的數(shù)學(xué)模型，在路徑泥土量pathsoil 矩陣范圍內(nèi)計(jì)算g(soil(i，j))、智能水滴f(soil(i，k))集合元素之和，找到最小泥土量（minsoil(i，j)）。此時檢查i 是否在訪問列表當(dāng)中，根據(jù)式（7）計(jì)算泥土量，并計(jì)算下一個數(shù)據(jù)，信息增益排序?yàn)V波器對輸入的數(shù)據(jù)采用搜索排序，對602條數(shù)據(jù)的51個屬性進(jìn)行排序，標(biāo)準(zhǔn)化概率。

根據(jù)排序數(shù)組標(biāo)準(zhǔn)化排序，獲取新特征排序，然后更新IWD。首先獲取IWD 的初始速度和位置，在驗(yàn)證中，設(shè)置水滴的初始速度velocity為100，含沙量soilcontent 為0，然后計(jì)算速度，按照式（1）進(jìn)行更新，設(shè)置av=1，cv=1，bv=0.01；計(jì)算泥土量，根據(jù)式（3）對泥土量進(jìn)行更新，設(shè)置as=1，bs=1，cs=0.01，ρ=0.9。

基于選定的位置創(chuàng)建簡化數(shù)據(jù)集，利用Matlab運(yùn)行l(wèi)ibsvm，根據(jù)svmtrain創(chuàng)建動態(tài)數(shù)據(jù)預(yù)測結(jié)果，獲取交叉驗(yàn)證精度。然后進(jìn)行下一代的迭代，經(jīng)歷30 代的迭代，更新最佳路徑，選擇最大概率的IWD，更新每條路徑的泥土量soil(i，j)，根據(jù)訪問列表中的特征將全局最佳路徑寫入文件，輸出最佳路徑作為智能水滴的最佳路徑。

4 路徑規(guī)劃模型分析

4.1 函數(shù)驗(yàn)證

智能水滴算法是利用智能水滴速度和泥土量這兩個屬性，加之本身具有的靈活性，對路徑進(jìn)行優(yōu)化。在對智能水滴算法的驗(yàn)證中，使用四種測試函數(shù)對智能水滴進(jìn)行驗(yàn)證，通過函數(shù)本身與設(shè)定值之間的圖像展示，可以直觀地看出算法的有效性。

4.1.1 Rosenbrock函數(shù)驗(yàn)證

函數(shù)表達(dá)式為f(x1，x2)=-10 ≤x1，x2≤10。該函數(shù)使用的是二維函數(shù)，設(shè)置全局的最小值f(1，1)=0。Rosenbrock 函數(shù)立體圖見圖1。根據(jù)立體圖可以看出二維Rosenbrock函數(shù)在最低點(diǎn)取得全局最小值，可以測試求解方法的執(zhí)行能力。該函數(shù)的仿真實(shí)驗(yàn)函數(shù)值收斂曲線見圖2，通過圖線的曲線走勢，可以找到最優(yōu)值。

圖1 Rosenbrock函數(shù)立體圖

圖2 Rosenbrock函數(shù)仿真實(shí)驗(yàn)函數(shù)值收斂曲線

4.1.2 Beale函數(shù)驗(yàn)證

函數(shù)表達(dá)式為f(x)=(1.5-x1+x1x2)2+(2.25-，-4.5 ≤x1，x2≤4.5 。該函數(shù)使用的是二維函數(shù)，設(shè)置全局的最小值為X*=(3，0.5)，f(X)*=0。二維Beale函數(shù)的立體圖見圖3。根據(jù)立體圖可以看出二維Beale 函數(shù)是多峰函數(shù)，多峰函數(shù)可以測試全局最優(yōu)和局部最優(yōu)的搜索能力。

圖3 二維Beale函數(shù)的立體圖

4.1.3 Rastrigin函數(shù)驗(yàn)證

函數(shù)表達(dá)式為f(x)=cos(2πx2))+20 ，-5.12 ≤x1，x2≤5.12 。該函數(shù)使用的是二維函數(shù)，設(shè)置全局的最小值為f(0)=0。二維Rastrigin 函數(shù)的立體圖見圖4，根據(jù)立體圖可以看出二維Rastrigin函數(shù)是多峰函數(shù)，多峰函數(shù)可以測試函數(shù)的局部極值。該函數(shù)的仿真實(shí)驗(yàn)函數(shù)值收斂曲線見圖5。

圖4 二維Rastrigin函數(shù)的立體圖

圖5 二維Rastrigin函數(shù)仿真實(shí)驗(yàn)函數(shù)值收斂曲線

4.1.4 Griewank函數(shù)驗(yàn)證

圖6 二維Griewank仿真實(shí)驗(yàn)函數(shù)值收斂曲線

4.2 數(shù)據(jù)迭代最優(yōu)值

智能水滴算法在上述測試函數(shù)的測試中，通過立體圖和曲線觀察發(fā)現(xiàn)，智能水滴算法是可以實(shí)現(xiàn)算法的有效性的，根據(jù)測試函數(shù)的函數(shù)表達(dá)式和原有設(shè)定的值，求解出數(shù)據(jù)算法的最優(yōu)值和迭代的次數(shù)，見表1。通過數(shù)據(jù)可以直觀地看出智能水滴算法的迭代情況。

表1 四種函數(shù)驗(yàn)證智能水滴算法找到的最優(yōu)值和迭代次數(shù)

通過表1 可見，二維Rosenbrock 函數(shù)在迭代153 次達(dá)到最優(yōu)值，二維Beale函數(shù)在迭代162 次達(dá)到最優(yōu)值，二維Rastrigin函數(shù)和二維Griewank 函數(shù)在迭代200 次基本趨于理論最優(yōu)值。從數(shù)據(jù)值看，智能水滴算法在有限的迭代次數(shù)后達(dá)到最優(yōu)值。

5 結(jié)語

研究基本實(shí)現(xiàn)了智能水滴與電動汽車充電路徑的結(jié)合，從數(shù)據(jù)結(jié)果可以看出，智能水滴算法在電動汽車充電路徑規(guī)劃上是可行的。智能水滴算法的運(yùn)用是一個很便利、能夠動態(tài)掌握電動汽車的充電路徑規(guī)劃，但是有些方面的不適用是需要改進(jìn)的。后期，將主要針對智能水滴算法的改進(jìn)進(jìn)行研究，并研究數(shù)據(jù)挖掘以及大數(shù)據(jù)分析對人類生活的便利程度。