戰(zhàn)彥君,張玲華,2

(1.南京郵電大學(xué) 通信與信息工程學(xué)院,江蘇 南京 210003;2.江蘇省通信與網(wǎng)絡(luò)技術(shù)工程研究中心,江蘇 南京 210003)

0 引 言

近年來(lái),煤炭、石油、天然氣等化石燃料的大量消耗,使得能源危機(jī)和環(huán)境問(wèn)題日益嚴(yán)重[1]。為了有效應(yīng)對(duì),中國(guó)提出了碳達(dá)峰、碳中和目標(biāo),致力于構(gòu)建以電能為核心的清潔、低碳、高效能源體系,大力推廣電動(dòng)汽車是其中的重要一環(huán)。與燃油汽車不同的是,電動(dòng)汽車?yán)m(xù)航能力較差,因此要在城市中布設(shè)充電樁。由于實(shí)際城市中建筑的限制以及區(qū)域需求不同,充電樁的分布具有隨機(jī)性和不均勻性,假如充電樁和電力調(diào)度中心之間供電線路規(guī)劃不合理,必然會(huì)大大增加建設(shè)成本和電力傳輸過(guò)程中的損耗。為此,研究合適的充電樁供電線路模型,以最高效率和最低成本對(duì)充電樁供電十分重要。

受到灰狼圍捕和狩獵的行為啟發(fā),Mirjalili等人于2014年提出了灰狼算法[2](gray wolf optimization,GWO)。相較于粒子群算法[3]、遺傳算法[4]、蟻群算法[5]等經(jīng)典智能優(yōu)化算法,該算法具有結(jié)構(gòu)簡(jiǎn)單、參數(shù)少、求解精度高且速度快[6]等優(yōu)點(diǎn),被廣泛應(yīng)用于經(jīng)濟(jì)調(diào)度[7]、作業(yè)車間調(diào)度[8]、圖像分割[9]和云計(jì)算資源負(fù)荷預(yù)測(cè)[10]等諸多領(lǐng)域。但是,GWO算法存在易陷入局部最優(yōu)解、初始種群分布不均勻和后期收斂速度慢[11]等缺點(diǎn)。該文提出一種基于Tent混沌映射[12]和自適應(yīng)收斂因子的改進(jìn)灰狼優(yōu)化算法(ITAGWO),將其應(yīng)用于城市電動(dòng)汽車充電樁供電線路規(guī)劃中。首先,針對(duì)初始種群分布不均勻,采用Tent混沌映射來(lái)產(chǎn)生種群初始可行解,以豐富種群的多樣性;其次,將線性收斂因子改為非線性自適應(yīng)收斂因子,平衡其局部搜索和全局搜索能力,加快收斂速度;最后,改進(jìn)灰狼圍捕獵物時(shí)的位置更新公式,以不同權(quán)重采納三類頭狼的經(jīng)驗(yàn),并加入隨機(jī)擾動(dòng)因子。對(duì)區(qū)域的充電樁進(jìn)行供電線路規(guī)劃仿真,與傳統(tǒng)灰狼算法、粒子群算法(particle swarm optimization,PSO)、遺傳算法(genetic algorithm,GA)、免疫算法[13](immune algorithm,IA)、模擬退火算法[14](simulated annealing algorithm,SA)、布谷鳥算法[15](cuckoo search algorithm,CSA)、教與學(xué)算法[16](teaching-learning-based optimization,TLBO)進(jìn)行了對(duì)比。在到達(dá)全局最優(yōu)解的前提下,該算法迭代次數(shù)少、收斂速度快且穩(wěn)定性好,相比于其他智能算法具有明顯優(yōu)勢(shì)。

1 模型構(gòu)建

該文主要提出一種充電樁供電線路規(guī)劃模型,在連接區(qū)域中所有充電樁的同時(shí),以路徑最短為目標(biāo)。模型可以描述為:在區(qū)域中有n個(gè)充電樁,并且充電樁坐標(biāo)位置已知,供電線路從其中某一充電樁出發(fā),依次為區(qū)域中所有充電樁輸電,每個(gè)充電樁都只被經(jīng)過(guò)一次。當(dāng)區(qū)域中充電樁數(shù)目過(guò)多時(shí),單線路輸電效率過(guò)低,此時(shí)將區(qū)域分成多個(gè)子區(qū)域,每個(gè)子區(qū)域采用一條供電線路將區(qū)域內(nèi)的充電樁遍歷,可以顯著縮短供電時(shí)間,提高充電樁輸電效率。為構(gòu)建適當(dāng)模型,作以下假設(shè):

(1)不考慮實(shí)際的交通道路情況,僅以直線距離為例;

(2)不考慮線路中僅有部分充電樁需要供電的情況,假設(shè)每次輸電每個(gè)充電樁都需要被充電;

(3)假設(shè)電力調(diào)度中心距離哪個(gè)充電樁近,就以該充電樁為起點(diǎn);

(4)不考慮充電樁需求量超過(guò)線路輸送容量的情況,假設(shè)每次輸電都能滿足所有充電樁的需求;

(5)當(dāng)劃分子區(qū)域時(shí),假設(shè)各子區(qū)域中的供電線路都與單調(diào)度線路模型一致。

1.1 單調(diào)度線路模型構(gòu)建

(1)區(qū)域中第i個(gè)充電樁和第j個(gè)充電樁之間的距離Dij的計(jì)算公式為:

(1)

其中,xi和yi表示充電樁i的橫縱坐標(biāo);xj和yj表示充電樁j的橫縱坐標(biāo);n表示區(qū)域中的充電樁個(gè)數(shù)。

(2)定義0-1變量來(lái)判斷是否經(jīng)過(guò)某個(gè)充電樁:

(2)

(3)為了以最小運(yùn)輸成本給充電樁輸電,就要使供電線路的總路徑長(zhǎng)度最小,所以目標(biāo)函數(shù)的函數(shù)表示為:

(3)

其中,約束條件表示調(diào)度線路必須經(jīng)過(guò)每個(gè)充電樁,并且只經(jīng)過(guò)一次。

1.2 多調(diào)度線路模型構(gòu)建

當(dāng)區(qū)域中充電樁數(shù)量過(guò)多時(shí),為了有效提高輸電效率,將區(qū)域劃分成多個(gè)子區(qū)域,分多條線路對(duì)供電樁進(jìn)行高效率輸電。在充電樁總數(shù)為n的情況下,將區(qū)域分成p個(gè)子區(qū)域,第k個(gè)子區(qū)域中的充電樁個(gè)數(shù)為xk(k=1,2,…,p)。

(1)在第k個(gè)子區(qū)域中,第i個(gè)充電樁和第j個(gè)充電樁之間的距離Dikjk計(jì)算公式為:

(4)

其中,xik和yik表示第k個(gè)子區(qū)域中充電樁i的橫縱坐標(biāo);xjk和yjk表示第k個(gè)子區(qū)域中充電樁j的橫縱坐標(biāo)。

(2)定義0-1變量來(lái)判斷是否經(jīng)過(guò)第k個(gè)子區(qū)域中某個(gè)充電樁。

(5)

(3)要遍歷子區(qū)域中的每個(gè)充電樁,同時(shí)供電線路總長(zhǎng)度最短,目標(biāo)函數(shù)表達(dá)式為:

(6)

其中,p表示所劃分的子區(qū)域個(gè)數(shù);xk表示第k個(gè)子區(qū)域中充電樁的個(gè)數(shù);約束條件表示第k條供電線路必須經(jīng)過(guò)子區(qū)域k中每個(gè)充電樁,且只經(jīng)過(guò)一次,所有子區(qū)域中充電樁總數(shù)為m。

2 傳統(tǒng)灰狼算法

2.1 灰狼種群的等級(jí)制度

灰狼種群具有十分嚴(yán)格的等級(jí)制度,狼群具體劃分為α狼、β狼、δ狼、ω狼四類[17]。其中α狼是種群中的最高領(lǐng)導(dǎo)者,負(fù)責(zé)管理種群和各項(xiàng)重要決策事務(wù);β狼的職責(zé)是協(xié)助α狼做出決策和管理整個(gè)種群,傳送上級(jí)指令并反饋信息;δ狼服從前兩類狼的調(diào)度命令,從事偵查、放哨等底層管理事務(wù),能力不足或者生病的α狼、β狼也會(huì)降級(jí)成δ狼;而ω狼是種群的基本組成成員,等級(jí)最低且數(shù)量最多,需要服從三類頭狼的命令,對(duì)于維持種群平衡有著不可或缺的作用。

圖1 灰狼種群等級(jí)金字塔

灰狼狼群的捕獵行為分成跟蹤、包圍和獵殺三個(gè)階段。首先,灰狼群體會(huì)對(duì)目標(biāo)獵物進(jìn)行追蹤;之后,由α狼帶領(lǐng)整個(gè)狼群對(duì)目標(biāo)獵物進(jìn)行全方位的包圍;最后,α狼指揮最靠近獵物的β狼、δ狼對(duì)獵物進(jìn)行獵殺,若是獵物逃脫,由狼群中其余灰狼繼續(xù)進(jìn)行圍獵,直到最終捕獲獵物。

2.2 灰狼算法GWO

假設(shè)搜索空間為D維,數(shù)量為N的灰狼組成種群,其中第i只灰狼的位置記為:Xi=(Xi1,Xi2,…,XiD),將種群中適應(yīng)度值前三個(gè)分別記為α狼、β狼和δ狼,種群中其它個(gè)體全部記為ω狼。

(1)在跟蹤和包圍獵物的過(guò)程中,相應(yīng)的數(shù)學(xué)模型為:

(7)

(8)

(9)

(10)

(2)在狼群鎖定目標(biāo)獵物的位置后,α狼會(huì)帶領(lǐng)β狼和δ狼包圍獵物。通常這三類狼對(duì)目標(biāo)獵物的潛在位置更加了解,所以狼群其他成員根據(jù)三者的位置判斷獵物的位置并不斷更新自身位置,向著目標(biāo)獵物靠近。狼群圍獵行為的數(shù)學(xué)模型如式(11)～式(13)所示:

(11)

(12)

(13)

根據(jù)式(13)所求步長(zhǎng),最終確定灰狼個(gè)體下一步的更新位置。

3 改進(jìn)灰狼算法(ITAGWO)

3.1 Tent混沌映射

針對(duì)GWO隨機(jī)產(chǎn)生初始可行解導(dǎo)致的初始種群分布不均勻、物種多樣性差的缺陷,采用Tent混沌映射的方法產(chǎn)生初始種群,其良好的多樣性和遍歷性有效提高了求解精度和收斂速度。Tent映射也即帳篷映射,是一種分段的線性映射,因其函數(shù)圖像酷似帳篷而得名,其函數(shù)表示如下:

(14)

由于u=1/2時(shí),Tent映射是具有均勻分布的典型序列,對(duì)不同的參數(shù)有近似一致的分布密度,因而該文引用u=1/2的Tent映射公式,如式(15)所示:

(15)

3.2 非線性收斂因子

在灰狼算法中,收斂因子a的選取決定算法的局部和全局搜索能力[18]。傳統(tǒng)灰狼算法的收斂因子是從2線性遞減到0的,而在實(shí)際優(yōu)化問(wèn)題中灰狼算法的搜索過(guò)程比較復(fù)雜,線性遞減的收斂因子導(dǎo)致算法的搜索能力弱[19]。該文采用非線性遞減的方式改進(jìn)收斂因子[20]:前期遞減速度慢,較大的a值增強(qiáng)全局搜索能力,避免陷入局部最優(yōu)解;后期收斂速度慢,較小的a值增強(qiáng)局部搜索能力 ,加快收斂速度。這種非線性收斂機(jī)制可以協(xié)調(diào)灰狼算法的局部和全局搜索能力,并且a值切換具備自適應(yīng)性。改進(jìn)收斂因子表達(dá)式如式(16)所示:

(16)

其中,k為調(diào)節(jié)系數(shù),它的取值決定著a隨著迭代次數(shù)增加而遞減的速度,該文取為e[6];t為當(dāng)前迭代次數(shù);tmax為最大迭代次數(shù)。

3.3 隨機(jī)擾動(dòng)

傳統(tǒng)灰狼算法中,ω狼的位置更新是等權(quán)重地參考三類頭狼的位置信息,在搜索后期所有灰狼都會(huì)向α狼、β狼、δ狼附近區(qū)域靠攏,這樣極易陷入局部最優(yōu),影響算法的收斂速度。該文采用的位置更新公式采用不同的權(quán)重參考三類頭狼的位置信息,對(duì)級(jí)別越高的狼參考權(quán)重相應(yīng)越大,以加快收斂速度;并加入了隨機(jī)擾動(dòng)以防止陷入局部最優(yōu)解,其公式表達(dá)如下:

(17)

3.4 改進(jìn)灰狼算法流程

改進(jìn)灰狼算法流程如圖2所示。

圖2 改進(jìn)灰狼算法流程

4 仿真實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)仿真軟件為Matlab R2018b。參照元啟發(fā)式算法比較文獻(xiàn)[21]和各算法的參考文獻(xiàn)中對(duì)實(shí)驗(yàn)參數(shù)的設(shè)置,結(jié)合實(shí)際實(shí)驗(yàn)過(guò)程中算法的性能和收斂效果,對(duì)各個(gè)算法的參數(shù)設(shè)置如下:GWO和ITAGWO的種群大小為100;CSA的種群大小為100,鳥蛋被發(fā)現(xiàn)概率為0.3,步長(zhǎng)因子α為0.015,萊維飛行中的β因子為1;PSO中粒子數(shù)量為500,個(gè)體學(xué)習(xí)因子為0.1,社會(huì)學(xué)習(xí)因子為0.075,慣性因子為1;IA的抗體種群個(gè)數(shù)為100,免疫選擇比例為20%,抗體克隆擴(kuò)增倍數(shù)為5,種群刷新比例為抗體種群的30%;SA的初始溫度為1 000,終止溫度為1e-3,降溫因數(shù)為0.9,Metropolis準(zhǔn)則鏈長(zhǎng)為200,種群大小為100;GA的種群規(guī)模為100,交叉概率為0.7,變異概率為0.001;TLBO的種群大小為100。查閱群智能算法相關(guān)文獻(xiàn)發(fā)現(xiàn),其迭代次數(shù)一般設(shè)置為100～500,結(jié)合實(shí)驗(yàn)迭代終止時(shí)次數(shù)均在50以內(nèi)的情況,考慮到未來(lái)更復(fù)雜區(qū)域和更龐大數(shù)量充電樁的場(chǎng)景,該文所有算法的終止迭代次數(shù)均為300次,種群搜索維度為10。

假設(shè)空間中存在一個(gè)100 km*100 km的正方形區(qū)域,坐標(biāo)范圍為(0,0)到(100,100),將空間劃分成四個(gè)子區(qū)域,每個(gè)子區(qū)域中有10個(gè)充電樁,以區(qū)域中充電樁全部連接時(shí)總線路長(zhǎng)度最小為目標(biāo)進(jìn)行實(shí)例仿真,各區(qū)域充電樁的坐標(biāo)見表1。

表1 各區(qū)域充電樁坐標(biāo)

區(qū)域中所有充電樁的坐標(biāo)位置分布情況見圖3。

圖3 區(qū)域充電樁位置分布

4.2 算法對(duì)比分析

利用ITAGWO和七種比較算法對(duì)表1中的充電樁仿真五次,雖然各種算法求得最優(yōu)解的迭代次數(shù)不同,但其所求的最優(yōu)解是相同的,且其最優(yōu)供電線路也一致。各算法五次仿真的平均迭代次數(shù)和最優(yōu)迭代次數(shù)見表2,最優(yōu)供電線路規(guī)劃方案見圖4。

表2 各算法在四區(qū)域的迭代次數(shù)

圖4 各區(qū)域能源調(diào)度路線規(guī)劃

由表2,ITAGWO與其他七種比較智能算法都可以找到最優(yōu)解,但I(xiàn)TAGWO的迭代次數(shù)更少,收斂速度更快,且迭代次數(shù)間方差較小,更具穩(wěn)定性。

在區(qū)域一,各比較算法中GWO的平均迭代次數(shù)和最優(yōu)迭代次數(shù)均最少,ITAGWO的平均迭代次數(shù)和最優(yōu)迭代次數(shù)分別比GWO提高了31.6%和40%;在區(qū)域二,各比較算法中GWO的平均迭代次數(shù)和最優(yōu)迭代次數(shù)均最少,ITAGWO的最優(yōu)迭代次數(shù)雖然與GWO一致,但平均迭代次數(shù)提高了25.8%;在區(qū)域三,各比較算法中IA的平均迭代次數(shù)最少,GWO的最優(yōu)迭代次數(shù)最少,ITAGWO的平均迭代次數(shù)比IA提高了18.5%,最優(yōu)迭代次數(shù)比GWO提高25%;在區(qū)域四,各比較算法中GWO的平均迭代次數(shù)和最優(yōu)迭代次數(shù)均最少,ITAGWO的平均迭代次數(shù)和最優(yōu)迭代次數(shù)分別比GWO提高了39.5%和33.4%。

5 結(jié)束語(yǔ)

針對(duì)城市中電動(dòng)汽車充電樁分布的隨機(jī)性和不均勻性,將灰狼算法用于其供電線路規(guī)劃。GWO算法存在易陷入局部最優(yōu)解、初始種群分布不均勻和后期收斂速度慢等缺點(diǎn),該文提出一種基于Tent混沌映射和自適應(yīng)收斂因子的ITAGWO算法。實(shí)例仿真結(jié)果表明,在到達(dá)最優(yōu)解的前提下,ITAGWO比其余七種算法的迭代次數(shù)少、收斂速度快且穩(wěn)定性好,可以很好地應(yīng)用于充電樁供電線路規(guī)劃。