王春麗,趙書強(qiáng),李 勇

(1.紹興電力局,浙江 紹興 312000;2.華北電力大學(xué) 電氣與電子工程學(xué)院,河北 保定 071003)

基于改進(jìn)量子遺傳算法的輸電網(wǎng)規(guī)劃方法

王春麗1,趙書強(qiáng)2,李 勇1

(1.紹興電力局,浙江 紹興 312000;2.華北電力大學(xué) 電氣與電子工程學(xué)院,河北 保定 071003)

量子遺傳算法是基于量子計(jì)算原理的概率優(yōu)化方法,改進(jìn)了動(dòng)態(tài)調(diào)整量子旋轉(zhuǎn)門策略,并結(jié)合量子交叉和量子變異操作,使算法具有更快的收斂速度和全局尋優(yōu)能力。輸電網(wǎng)規(guī)劃是復(fù)雜的大規(guī)模非線性組合優(yōu)化問題,提出了一種基于改進(jìn)量子遺傳算法的輸電網(wǎng)規(guī)劃模型。算例表明,該方法能夠快速有效地獲得全局經(jīng)濟(jì)最優(yōu)的輸電網(wǎng)規(guī)劃方案。

輸電網(wǎng)規(guī)劃;量子遺傳算法;量子旋轉(zhuǎn)門;量子交叉;量子變異

0 引 言

采用傳統(tǒng)的啟發(fā)式方法,如逐步擴(kuò)展法、逐步倒推法可得到一個(gè)較好的可行解,但并不能保證是最優(yōu)的。近年來發(fā)展的人工智能算法,如遺傳算法[2]、模擬退火法[3]、蟻群算法[4]、粒子群算法[5]等,為求解輸電網(wǎng)規(guī)劃問題提供了新的思路,能夠在一定程度上克服傳統(tǒng)優(yōu)化算法的缺陷,保證了最優(yōu)解的獲得,但其處在發(fā)展階段,仍然存在著一些不足之處,如尋優(yōu)速度慢、運(yùn)算時(shí)間長和局部收斂等。

量子遺傳算法是將量子計(jì)算與進(jìn)化算法相結(jié)合,使用量子技術(shù)中的概念以提高進(jìn)化算法編碼的多樣性,從而加快計(jì)算速度,保證優(yōu)化的全局收斂性,但同樣也存在 “早熟”和易陷入局部最優(yōu)解的缺點(diǎn)。本文改進(jìn)了算法的動(dòng)態(tài)調(diào)整量子旋轉(zhuǎn)門策略,并結(jié)合輸電網(wǎng)規(guī)劃的特點(diǎn),對(duì)規(guī)劃模型進(jìn)行了求解和驗(yàn)證。

1 量子遺傳算法

AjitNarayanan和 Mark Moore1996年提出了量子遺傳算法的概念,它是一種量子計(jì)算理論與遺傳算法相結(jié)合的概率搜索優(yōu)化算法：用量子位編碼表示染色體,用量子門作用和量子門更新完成進(jìn)化搜索。

量子遺傳算法的本質(zhì)特征就是充分利用了量子態(tài)的疊加性和相干性。它以量子計(jì)算的一些概念和理論為基礎(chǔ),用量子位編碼來表示染色體,通過量子門更新種群來完成進(jìn)化搜索,與傳統(tǒng)遺傳算法相比,能夠更容易地在探索與開發(fā)之間取得平衡,具有種群規(guī)模小、收斂速度較快、全局尋優(yōu)能力強(qiáng)的特點(diǎn)。

1.1 量子比特編碼

量子遺傳算法建立在量子態(tài)的矢量表達(dá)基礎(chǔ)上,其最小的信息單位為量子比特。將量子比特的概率幅表示應(yīng)用于染色體的編碼,使得一條染色體可以表達(dá)多個(gè)態(tài)的疊加。一個(gè)量子比特的狀態(tài)可由兩個(gè)量子態(tài)的疊加表示為：

對(duì)于一個(gè)具有 m個(gè)量子比特的系統(tǒng),用量子比特方法表示的染色體個(gè)體為：

由上式定義的染色體可以表示 2m個(gè)狀態(tài),比傳統(tǒng)遺傳算法具有更好的多樣性。隨著 |α|2和|β|2趨于 1或 0,量子比特染色體收斂于一個(gè)狀態(tài),這時(shí)多樣性消失,算法收斂,即量子比特同時(shí)具有 “開發(fā)”和 “探尋”的特性。

1.2 量子旋轉(zhuǎn)門

量子旋轉(zhuǎn)門是量子變換門的一種,通過量子門的旋轉(zhuǎn)來進(jìn)化種群,采用_的量子旋轉(zhuǎn)門為：

古代皇帝用的“玉璽（）”就是印章，那時(shí)，印章作為當(dāng)權(quán)者的專有物，是其身份和權(quán)力的有力證明，是統(tǒng)治臣民的工具。

式中：θ為量子門的旋轉(zhuǎn)角,取值為：θ=k?f(αi,βi);其中,k是一個(gè)與算法收斂速度有關(guān)的系數(shù),k必須取值合理,若太大,算法搜索的網(wǎng)格就很大,容易出現(xiàn)早熟現(xiàn)象,即收斂于局部極值點(diǎn);反之,若太小,算法搜索的網(wǎng)格就很小,速度太慢,甚至?xí)顟B(tài)。將 k定義為一個(gè)與進(jìn)化代數(shù)有關(guān)的變量,以便自適應(yīng)地調(diào)整搜索網(wǎng)格的大小。

式中：t為迭代次數(shù);maxt是一個(gè)根據(jù)優(yōu)化問題復(fù)雜性而定的一個(gè)常數(shù)。

2 量子遺傳算法的改進(jìn)策略

2.1 動(dòng)態(tài)調(diào)整旋轉(zhuǎn)角機(jī)制

由于旋轉(zhuǎn)變異角 θ的幅度影響收斂速度,但是若幅值度太大,又會(huì)導(dǎo)致早熟[6]。故本文采用動(dòng)態(tài)調(diào)整量子門旋轉(zhuǎn)角 θ大小,即在算法運(yùn)行初期和當(dāng)前個(gè)體與最優(yōu)個(gè)體較遠(yuǎn)時(shí),搜索的網(wǎng)格較大,從而增加了算法的收斂速度;在算法運(yùn)行末期和當(dāng)前個(gè)體與最優(yōu)個(gè)體接近時(shí),搜索的網(wǎng)格較小,從而實(shí)現(xiàn)了精度搜索,有利于尋得最優(yōu)解。

IQGA采用量子旋轉(zhuǎn)門更新策略完成種群的更新操作,量子旋轉(zhuǎn)門的旋轉(zhuǎn)角度的確定方法如表1所示。旋轉(zhuǎn)角 θi的取值：

式中：n為當(dāng)前的進(jìn)化代數(shù); MAXN為終止代數(shù);K為 0到 1之間的常數(shù);fmin為目標(biāo)最小值,若目標(biāo)最小值未知,則選取已計(jì)算出的最小值替代fmin;f為當(dāng)前個(gè)體計(jì)算出的目標(biāo)值;f′min為當(dāng)前種群中的最小值。

表 1 旋轉(zhuǎn)角度的確定方法Tab.1 Method of judged rotating angle

2.2 量子交叉

GA的搜索能力通過交叉操作得以飛躍的提高,因而在 QGA中引入量子交叉操作,充分利用量子態(tài)的干涉性,讓所有染色體信息產(chǎn)生更多的新模式,極大地提高了算法的搜索能力。本節(jié)中在執(zhí)行量子交叉時(shí),首先在種群中除最優(yōu)個(gè)體以外,按交叉概率 Pc選取若干個(gè)個(gè)體,再將選中的每個(gè)個(gè)體中的染色體次序隨機(jī)重新排列,最后對(duì)所有選中個(gè)體的染色體按照對(duì)角重新排列組合,生成新染色體。

2.3 量子變異

本節(jié)采用量子變異操作防止算法陷入局部最優(yōu)解。由于量子態(tài)具有糾纏性,在量子變異時(shí)采用單點(diǎn)變異方式[7]就能有效防止早熟,因此本節(jié)采用單點(diǎn)變異方式的量子變異操作：以一定概率選擇種群中的個(gè)體,為選中的個(gè)體隨機(jī)產(chǎn)生一個(gè)變異位并互換變異位的概率幅。

3 基于改進(jìn)量子遺傳算法的輸電網(wǎng)規(guī)劃方法

3.1 輸電網(wǎng)規(guī)劃模型

作為初步研究,本節(jié)所述的為傳統(tǒng)的單階段確定性輸電網(wǎng)規(guī)劃模型,即僅考慮基態(tài)運(yùn)行方式下的過負(fù)荷約束,輸電網(wǎng)規(guī)劃的數(shù)學(xué)模型如下：

對(duì)線路潮流的約束采用罰函數(shù)的方法處理,引入罰因子 α將不滿足線路潮流的約束加入到目標(biāo)函數(shù)中,得到新的目標(biāo)函數(shù)：式中：Ψ為不滿足線路潮流約束的集合;α為懲罰因子。

3.2 求解步驟

(1)采取直接量子編碼的方法,使每一條待選線路對(duì)應(yīng)染色體中的一位,用一對(duì)量子比特表示,并初始化種群 P(t);然后解碼,生成的染色體的相應(yīng)位為 “1”時(shí),表示投建對(duì)應(yīng)線路,為“0”時(shí),表示不投建對(duì)應(yīng)線路。

(2)將每條染色體對(duì)應(yīng)的新增線路與已有線路一起形成待評(píng)價(jià)的網(wǎng)絡(luò),進(jìn)行連通性校驗(yàn),并計(jì)算所有染色體對(duì)應(yīng)的目標(biāo)函數(shù)值式 (9)。

(3)評(píng)價(jià)種群中各個(gè)體的適應(yīng)度,保存最優(yōu)的個(gè)體,不參加以下步驟的處理,直接復(fù)制到下一代群體中。

(4)判斷是否滿足收斂條件,若滿足,則輸出結(jié)果,停止計(jì)算;若不滿足,則轉(zhuǎn)為下一步。

(5)t=t+1,用改進(jìn)量子門 U(θ)更新 P(t),生成 P(t+1);執(zhí)行量子交叉、量子交叉變異;轉(zhuǎn)步驟 (3)。

其中,采用收斂的判據(jù)有兩個(gè)：迭代次數(shù)超過上限;群體中的最優(yōu)值經(jīng)多次迭代保持不變。滿足其中之一即停止迭代,輸出最優(yōu)解。

4 算例分析

以 18節(jié)點(diǎn)系統(tǒng)網(wǎng)絡(luò)[1]為例,說明改進(jìn)量子遺傳算法的收斂性能,節(jié)點(diǎn)數(shù)據(jù)和線路數(shù)據(jù)與文獻(xiàn)[1]中相同。圖 1為該 18節(jié)點(diǎn)系統(tǒng)網(wǎng)絡(luò)路徑示意圖,系統(tǒng)原有 10個(gè)節(jié)點(diǎn)、9條線路 (圖中實(shí)線所示),候選線路 33條 (圖中虛線所示)。計(jì)算時(shí),種群規(guī)模 N=100,變異概率 Pm=0.08,交叉概率Pc=0.5, α=104。

圖1 18節(jié)點(diǎn)網(wǎng)絡(luò)路徑示意圖Fig.1 Schematic diagram o f network path for 18-bus system

比較本文改進(jìn)量子遺傳算法與量子遺傳算法[7]在求解輸電網(wǎng)規(guī)劃問題上的收斂性能。采用兩種算法對(duì)該算例進(jìn)行獨(dú)立計(jì)算 20次,得到的最優(yōu)規(guī)劃方案與文獻(xiàn) [2,5]相同,如圖 2所示。本文方法,平均迭代次數(shù)為 62.65;而量子遺傳算法[7],平均迭代次數(shù)為 91.95。兩種算法的收斂性能比較如圖 3所示,從中可以看出,本文提出的改進(jìn)量子遺傳算法提高了算法的收斂速度和全局收斂性能,能夠快速并有效地求解輸電網(wǎng)規(guī)劃問題。

圖2 最優(yōu)規(guī)劃方案Fig.2 Network planning optimal result

圖3 收斂性比較Fig.3 Comparison of convergence

5 結(jié) 論

本文將改進(jìn)量子遺傳算法應(yīng)用于輸電網(wǎng)規(guī)劃,通過對(duì)量子遺傳算法的動(dòng)態(tài)調(diào)整量子旋轉(zhuǎn)門策略進(jìn)行改進(jìn),并結(jié)合量子交叉、量子變異操作,提高了算法在解決輸電網(wǎng)規(guī)劃問題中的收斂速度和全局收斂性能。

[1]程浩忠,張焰.電力系統(tǒng)規(guī)劃 [M].北京：中國電力出版社,2008.

[2]葉在福,單淵達(dá).基于邊界搜索策略的遺傳算法在電網(wǎng)擴(kuò)展規(guī)劃中的應(yīng)用 [J].中國電機(jī)工程學(xué)報(bào),2000,20(11)：41-45.

Ye Zaifu,Shan Yuanda.A new transm ission network expansion planning using improved genetic algorithm based on borderline search strategy[J].Proceedings of the CSEE,2000,20(11)：41-45.

[3]顧潔,陳章潮,包海龍.混合遺傳-模擬退火算法在電網(wǎng)規(guī)劃中的應(yīng)用 [J].上海交通大學(xué)學(xué)報(bào),1999,33(4)：485-487.

Gu Jie,Cheng Zhangchao,Bao Hailong.Application of mixed genetic simulated annealing algorithms in electric network planning[J].Journal of Shang Hai Jiao Tong University,1999,33(4)：485-487.

[4]霍海保,程浩忠,呂干云,等.基于模式記憶并行蟻群算法的輸電網(wǎng)規(guī)劃 [J].中國電機(jī)工程學(xué)報(bào),2005,25(9)：17-22.

Zhai Haibao,Cheng haozhong,Lu ganyun,et al.Transm ission network planning based on schema recording parallel Ant colony Algorithm[J].Proceedings of the CSEE,2005,25(9)：17-22.

[5]常伯濤,范穎,趙書強(qiáng),等.基于改進(jìn)粒子群算法的輸電網(wǎng)擴(kuò)展規(guī)劃 [J].華北電力大學(xué)學(xué)報(bào) (自然科學(xué)版),2008,35(4)：13-17.

Chang Botao,Fan Ying,Zhao Shuqiang,etal.Transmission network expansion planning based on improved particle swarm optimization[J].Journal of North China Electric Power University(Natural Science Edition),2008,35(4)：13-17.

[6]黃友銳.智能優(yōu)化算法及其應(yīng)用 [M].北京：國防工業(yè)出版社,2008.

[7]邢煥來,潘煒,鄒喜華.一種解決組合優(yōu)化問題的改進(jìn)型量子遺傳算法 [J].電子學(xué)報(bào),2007,35(10)：1999-2002.

Xing Huanlai,Pan Wei,Zou Xihua.A novel improved quantum genetic algorithm for combinatorial optimization problems[J],Acta Electronica Sinica,2007,35(10)：1999-2002.

Transm ission Network Expansion Planning Based on Improved Quantum Genetic Algorithm

Wang Chunli1,Zhao Shuqiang2,LiYong1
(1.Shaoxing Municipal Electric Power Company,Shaoxing 312000,China;2.School of Electrical and Electronic Engineering,North China Electric Power University,Baoding 071003,China)

Quantum genetic algorithm is themethod ofprobabilistic optim ization based on the principles ofquantum compution.In this paper,A dynamic adjustment of the quantum rotation gate is improved,and quantum crossover and quantum mutation is combined,which makes ithas a faster convergence speed and global optimization ability.Transmission network planning is a complex large-scale nonlinear optimization problem,a transmission network plannning based on improved quantum genetic algorithm is proposed.The example shows that the method is fast and effective access to the global economic optimal transm ission network planning.

transmission network planning;quantum genetic algorithm(QGA);quantum rotation gate;quantum crossover;quantum mutation

T M715

A

2010-04-08。

王春麗 (1981-),女,助理工程師,從事線損管理工作,E-mail：liyong8112@163.com。