基于Bloch球面坐標(biāo)的改進(jìn)量子遺傳算法及其應(yīng)用

李家才，韓錕，鮑天哲

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410075)

?

基于Bloch球面坐標(biāo)的改進(jìn)量子遺傳算法及其應(yīng)用

李家才，韓錕，鮑天哲

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長沙 410075)

為解決量子遺傳算法(QGA)用于連續(xù)多峰函數(shù)優(yōu)化易陷入局部極值的問題, 提出一種基于Bloch球面坐標(biāo)的改進(jìn)量子遺傳算法(GLBQGA)：該算法通過引入新的全局-局部變異算子，在保證全局特性基礎(chǔ)上加入局部搜索機(jī)制，使算法在搜索到全局最優(yōu)近似解之后能通過局部鄰域搜索收斂到全局最優(yōu)精確解；算法還進(jìn)一步優(yōu)化量子轉(zhuǎn)角取值方案，在保證搜索空間不變的同時(shí)提高搜索效率。在機(jī)車二系支承載荷均勻性分配優(yōu)化調(diào)整及短時(shí)交通流多步預(yù)測(cè)中的應(yīng)用表明，GLBQGA有效克服了QGA早熟收斂的問題，在不顯著增加搜索時(shí)間的前提下提高了求解精度。

Bloch球面坐標(biāo)；量子遺傳算法；調(diào)簧；交通流預(yù)測(cè)

量子遺傳算法((Quantum Genetic Algorithm，QGA)是一種用量子相位表示種群元素的概率優(yōu)化算法[1]，它將量子的態(tài)矢量表達(dá)引入遺傳編碼，使得一條染色體可以表達(dá)多個(gè)態(tài)的疊加，并利用量子邏輯門實(shí)現(xiàn)染色體的演化[2]。由于單個(gè)染色體多樣性特征更好[3]，該算法對(duì)種群規(guī)模的需求明顯降低[4]，算法具有種群規(guī)模小、收斂速度快、全局搜索能力強(qiáng)[5-6]等優(yōu)點(diǎn)，近年來成為優(yōu)化領(lǐng)域的研究熱點(diǎn)。但測(cè)試發(fā)現(xiàn)QGA用于連續(xù)函數(shù)優(yōu)化時(shí)易出現(xiàn)早熟收斂，且易陷入局部極值[7]，為克服這一缺陷，學(xué)者們提出了大量的改進(jìn)量子遺傳算法，其中基于Bloch球面坐標(biāo)的量子遺傳算法(Bloch quantum genetic algorithm，BQGA)[8]因使用三鏈基因編碼且沒有選擇、交叉和復(fù)制運(yùn)算，獲得了搜索能力和優(yōu)化效率的綜合提高。但BQGA采用量子位沿Bloch球面較大幅度的旋轉(zhuǎn)作為變異操作，有可能使算法越過全局最優(yōu)解或產(chǎn)生振蕩，且BQGA在尋優(yōu)過程中搜索整個(gè)Bloch球面[6]，無疑降低了搜索效率。因此，本文提出一種引入新的全局-局部變異算子的Bloch球面坐標(biāo)量子遺傳算法(Global-Local Bloch quantum genetic algorithm, GLBQGA)，以期改善BQGA算法的魯棒性、加快算法收斂速度，且提高算法求解精度。將GLBQGA算法應(yīng)用于機(jī)車二系支承載荷均勻性分配優(yōu)化調(diào)整及短時(shí)交通流超前多步預(yù)測(cè)，應(yīng)用結(jié)果表明了GLBQGA算法的有效性。

1 GLBQGA算法基本思想

GLBQGA在文獻(xiàn)[8]提出的BQGA算法基礎(chǔ)上進(jìn)行以下改進(jìn)：

1)壓縮轉(zhuǎn)角參數(shù)取值范圍：將量子比特角度參數(shù)φ的取值區(qū)間由(0,2π)縮小到(0,3π/2)，可在保證搜索空間不變的同時(shí)提高搜索效率。

2)引入全局-局部變異算子：在變異操作中引入全局-局部變異算子取代量子非門，通過改變算子的全局-局部變異權(quán)重系數(shù)控制搜索過程中全局變異和局部變異的比重，在算法前期以全局變異為主，使量子位沿Bloch球面大幅度旋轉(zhuǎn)，充分利用整個(gè)解空間的信息進(jìn)行全局搜索，克服早熟；而在算法后期以局部變異為主，變異操作僅在個(gè)體所在鄰域內(nèi)進(jìn)行，充分利用已在最優(yōu)解附近分布個(gè)體所隱含的局部信息，提高算法的局部搜索能力，以找到全局最優(yōu)精確解。

3)引入自適應(yīng)操作：算法搜索過程中自適應(yīng)改變轉(zhuǎn)角步長和變異率，以改善收斂特性。

2 GLBQGA算法設(shè)計(jì)

2.1 編碼及解空間變換

在GLBQGA里，用量子位的Bloch球面坐標(biāo)作為染色體編碼。

在圖1所示的Bloch球面坐標(biāo)中，任何量子位都與球面上的一點(diǎn)對(duì)應(yīng)[6]，而通過量子位的角度參數(shù)φ和θ可以確定球面上的任一點(diǎn)，因此量子位可用球面坐標(biāo)表示為：

(1)

圖1 量子位的Bloch 球面表示Fig.1 Bloch sphere representation of a qubit

將pi定義為群體里的第i條染色體，其編碼如圖2所示：

圖2 染色體編碼Fig.2 Chromosome coding

圖2中，i=1,2,…Nind，Nind為種群規(guī)模，n為量子位數(shù)目。將量子位的三個(gè)坐標(biāo)看作三條并列的基因鏈[7]，每條基因鏈代表一組優(yōu)化解，則每條染色體含有以下三組優(yōu)化解：

(2)

采用線性變換實(shí)現(xiàn)定義在單位空間In=[-1,1]n內(nèi)的染色體向定義在優(yōu)化問題解空間內(nèi)的優(yōu)化解之間的變換，公式為：

(3)

式中，j=1,2,…n；bj和aj為優(yōu)化問題解空間的最大值和最小值。

2.2 搜索區(qū)域定義

傳統(tǒng)Bloch球面量子遺傳算法通常會(huì)對(duì)整個(gè)球面進(jìn)行搜索[8]，即轉(zhuǎn)角參數(shù)φij和θij的取值范圍分別為(0,2π)和(0,π)。這樣雖然擴(kuò)充了最優(yōu)解的個(gè)數(shù)，但也相應(yīng)擴(kuò)大了算法的搜索范圍。文獻(xiàn)[9]通過對(duì)連續(xù)問題可行解與Bloch球面對(duì)應(yīng)關(guān)系的研究發(fā)現(xiàn)，合理設(shè)置轉(zhuǎn)角參數(shù)的取值范圍可在保證實(shí)際搜索空間不變的前提下減少搜索時(shí)間。事實(shí)上，由圖3可知，當(dāng)轉(zhuǎn)角φij的取值范圍壓縮到(0,3π/2)時(shí)，sinφ與cosφ仍然覆蓋(-1,1)的解空間，此時(shí)量子比特同樣可以遍歷整個(gè)Bloch球面?；诖?，本文將φij和θij的取值范圍重新定義為(0,3π/2)和(0,π)，在保障搜索空間的同時(shí)進(jìn)一步提高算法效率。

圖3 φij和θij的取值范圍Fig.3 Reasonable ranges of parameters φijandθij

2.3 最優(yōu)染色體選擇

每條染色體有三個(gè)基因鏈，對(duì)應(yīng)三個(gè)目標(biāo)函數(shù)值，應(yīng)以最好的基因鏈代表該染色體，故按照式(4)確定該染色體的適應(yīng)度：

(4)

選擇種群中適應(yīng)度值最大的染色體為當(dāng)代最優(yōu)染色體，其三個(gè)基因鏈中目標(biāo)函數(shù)值最小者為當(dāng)代最優(yōu)基因鏈。

2.4 量子染色體的更新

區(qū)別于傳統(tǒng)遺傳算法，BQGA中，量子染色體的更新一般是通過旋轉(zhuǎn)門改變量子相位來實(shí)現(xiàn)的。它可以使當(dāng)前每個(gè)染色體向當(dāng)代最優(yōu)染色體靠近，并在逼近過程中產(chǎn)生更加優(yōu)良的個(gè)體，從而完成種群進(jìn)化。文獻(xiàn)[9]提出了一種較為有效的量子旋轉(zhuǎn)門，與原量子相位相乘后可使φ和θ分別旋轉(zhuǎn)Δφ和Δθ，其形式為:

U=

(5)

關(guān)于轉(zhuǎn)角方向，文獻(xiàn)[9]也給出了相應(yīng)的規(guī)則，可以通過當(dāng)前染色體與最優(yōu)染色體量三個(gè)量子位坐標(biāo)的代數(shù)運(yùn)算進(jìn)行判斷。對(duì)于轉(zhuǎn)角大小，本文采用轉(zhuǎn)角值隨迭代步長隨代數(shù)單調(diào)下降的調(diào)整策略，使之具有一定的自適應(yīng)性，具體為:

(6)

其中φ0的取值范圍是(0.005π,0.1π)；θ0=k0φ0，k0∈(0,1)。

2.5 全局-局部變異操作

傳統(tǒng)的量子遺傳算法常采用量子非門作為變異算子，依據(jù)變異概率隨機(jī)選擇每條染色體的若干量子位施加變異。該方法實(shí)際是使量子位沿Bloch球面進(jìn)行較大幅度的旋轉(zhuǎn)，在算法前期可充分利用整個(gè)解空間的信息，有利于克服早熟。但在算法迭代后期，特別是算法已收斂至全局最優(yōu)解附近時(shí)，這種量子位沿Bloch球面較大幅度旋轉(zhuǎn)的變異操作不能對(duì)搜索空間的細(xì)節(jié)進(jìn)行局部搜索，可能使搜索越過全局最優(yōu)解，甚至使搜索過程在全局最優(yōu)解附近產(chǎn)生振蕩而不能找到全局最優(yōu)精確解。在這種情況下，局部搜索顯得格外重要，此時(shí)應(yīng)充分利用個(gè)體所隱含的局部信息，提高算法的局部搜索能力，使算法收斂到全局最優(yōu)精確解。

基于此，借鑒蟻群算法中的局部搜索機(jī)制[10]，本文構(gòu)造了如下變異算子：

(7)

其中λ為全局-局部變異權(quán)重系數(shù)，λ∈(0,1)。該變異算子具有如下特征：

1)算子兼具全局和局部搜索特征，全局搜索和局部搜索力度由權(quán)重系數(shù)λ控制，λ越大，越突出全局搜索，當(dāng)λ取1時(shí)該算子退化為標(biāo)準(zhǔn)的量子非門變異操作；

2)可通過改變權(quán)重系數(shù)λ控制 GLBQGA搜索過程中全局變異和局部變異的比重：在算法前期，以全局變異為主，λ取接近1的較大值，使量子位沿Bloch球面大幅度旋轉(zhuǎn)，充分利用整個(gè)解空間的信息進(jìn)行全局搜索，克服早熟；而在算法后期以局部變異為主，λ取接近0的較小值，使變異操作僅在個(gè)體所在鄰域內(nèi)進(jìn)行，充分利用已在最優(yōu)解附近分布個(gè)體所隱含的局部信息，提高算法的局部搜索能力，以避免算法振蕩，提高算法精度。

對(duì)于很多優(yōu)化問題，特別是單峰性比較明顯的目標(biāo)函數(shù)，迭代后期的種群常常集中分布在最優(yōu)解附近，局部搜索顯得格外重要。此時(shí)GLBQGA算法中的局部搜索策略更有助于找到目標(biāo)函數(shù)的全局最優(yōu)精確解。

對(duì)應(yīng)于之前采用的自適應(yīng)策略，變異概率Pm的取值公式為：

(8)

其中變異參數(shù)Pm0∈(0.01,0.1)。

2.6 精英保留機(jī)制

同傳統(tǒng)遺傳算法一樣，精英保留機(jī)制可以使得種群不會(huì)退化，進(jìn)而保證GLBQGA算法在有限迭代內(nèi)以全概率收斂，具體策略為：

1)每一代最差染色體由這一代的最優(yōu)染色體替代；

2)每一代最優(yōu)染色體與歷史最優(yōu)染色體比較，若好于后者則將其替換，否則被其替換。

2.7 算法流程

步驟1：初始化各參數(shù)：設(shè)置種群規(guī)模Nind，迭代次數(shù)Gen，轉(zhuǎn)角步長參數(shù)φ0、k0、全局-局部變異的權(quán)重系數(shù)λ和變異概率Pm；

步驟2：生成初始種群，結(jié)合具體優(yōu)化問題利用式(3)進(jìn)行解空間變換，依據(jù)式(4)計(jì)算各染色體適應(yīng)度，并將其最優(yōu)染色體和最優(yōu)基因鏈作為歷史最優(yōu)染色體和基因鏈；

步驟3：利用式(6)中的量子旋轉(zhuǎn)門更新染色體，利用式(8)中的全局-局部變異算子完成變異，得到新種群；

步驟4：進(jìn)行解空間變換，計(jì)算各染色體適應(yīng)度；

步驟5：執(zhí)行精英保留機(jī)制；

步驟6：判斷迭代次數(shù)是否達(dá)到設(shè)定值，若是則結(jié)束迭代，輸出歷史最優(yōu)基因鏈在解空間的自變量值和目標(biāo)函數(shù)值；若否則轉(zhuǎn)步驟3。

3 GLBQGA算法在機(jī)車二系支承載荷調(diào)整中的應(yīng)用

機(jī)車輪(軸)重分配的均勻性直接影響到機(jī)車牽引粘著、制動(dòng)和動(dòng)力學(xué)性能[11]。具有兩系懸掛結(jié)構(gòu)的機(jī)車，其二系支承載荷分布狀態(tài)是影響機(jī)車輪軸重量分配的重要因素，將其視為剛性車體與多個(gè)支承彈簧構(gòu)成的超靜定空間力學(xué)系統(tǒng)，通過優(yōu)化算法對(duì)二系支承載荷進(jìn)行分配調(diào)整是改善輪(軸)重分配均勻性的有效途徑。

3.1 機(jī)車二系支承載荷優(yōu)化分配的數(shù)學(xué)模型

針對(duì)機(jī)車二系支承載荷調(diào)整優(yōu)化問題，文獻(xiàn)[11-14]構(gòu)建了相應(yīng)的優(yōu)化模型，比較常用的形式為：

(9)

3.2 GLBQGA算法的應(yīng)用及結(jié)果

二系支承載荷調(diào)整優(yōu)化問題的編碼及解空間變換公式為:

(10)

其中j=1,2,…,n，n表示量子位數(shù)，等于機(jī)車二系支承點(diǎn)的數(shù)量。

運(yùn)用本文提出的GLBQGA算法對(duì)國產(chǎn)HXD1B型電力機(jī)車車體實(shí)車數(shù)據(jù)進(jìn)行仿真調(diào)簧實(shí)驗(yàn)，算法參數(shù)選擇如下：設(shè)置種群規(guī)模Nind=20，迭代次數(shù)Gen=200，轉(zhuǎn)角步長φ0=0.1π，參數(shù)k0=0.5，全局-局部變異的權(quán)重系數(shù)在前120代取λ=1，后80代取λ=0.1，變異概率Pm=0.05，最大加墊量ΔHmax=7 mm。仿真結(jié)果如表1所示。

表1 HXD1B型機(jī)車初始二系載荷分布及優(yōu)化結(jié)果

Table 1 Initial distribution and optimization results of secondary spring load of locomotive HXD1B

支承點(diǎn)編號(hào)123456初始載荷/kN左69.5269.7169.3968.9170.4269.64右70.6370.8370.0970.3268.6167.69初始均方差/kN0.9122優(yōu)化后載荷/kN左70.0169.9969.9669.2369.2169.64右70.1270.0970.0669.3369.6169.29加墊量/mm左4.113.744.263.771.082.38右2.502.073.351.644.546.16優(yōu)化后的均方差/kN0.4116

由表1可知，利用GLBQGA算法求解出的最優(yōu)加墊序列對(duì)二系支承載荷進(jìn)行數(shù)值仿真，載荷均方差由初始的0.912 2 kN下降至0.411 6 kN。通過機(jī)車車體稱重調(diào)簧試驗(yàn)臺(tái)[14]測(cè)試可知，該加墊序列顯著優(yōu)化了二系載荷分布。

為進(jìn)一步驗(yàn)證該算法在全局搜索上的優(yōu)勢(shì)，將GLBQGA算法與文獻(xiàn)[11]提出的標(biāo)準(zhǔn)遺傳算法進(jìn)行比較，后者的有效性在機(jī)車二系支承載荷調(diào)整中已得到廣泛驗(yàn)證[11-14]。由于GLBQGA中每個(gè)染色體含有三條基因鏈，而每條基因鏈實(shí)際相當(dāng)于標(biāo)準(zhǔn)遺傳算法中的一個(gè)個(gè)體，因此后者的種群規(guī)模為60，迭代次數(shù)為200，其余參數(shù)的取值保持不變。兩種算法在200次迭代中的收斂曲線如圖4所示。

圖4 GA與GLBQGA的迭代曲線Fig.4 Iterative curves of GA and GLBQGA

由圖4可知：

1)標(biāo)準(zhǔn)遺傳算法在30代左右即完成收斂，而GLBQGA算法在50代以后仍有顯著的進(jìn)化，在一定程度上克服了遺傳算法早熟的弱點(diǎn)；

2)相同種群規(guī)模下，后者的搜索結(jié)果明顯好于前者，且通過算法分析可知時(shí)間復(fù)雜度基本相似，說明GLBQGA算法有著更為強(qiáng)大的搜索全局最優(yōu)精確解的能力，而這種求解精度的提高與算法迭代后期的局部搜索機(jī)制密切相關(guān)。

4 基于GLBQGA算法的短期交通流多步預(yù)測(cè)模型

交通誘導(dǎo)可以有效地改善城市交通擁擠，而實(shí)現(xiàn)城市交通誘導(dǎo)關(guān)鍵技術(shù)是對(duì)道路交通狀況的實(shí)時(shí)預(yù)測(cè)。從動(dòng)態(tài)規(guī)劃的角度來說，多步預(yù)測(cè)相比于單步預(yù)測(cè)更為重要，但預(yù)測(cè)難度也更高。現(xiàn)有的多步預(yù)測(cè)模型主要是基于循環(huán)一步外推法實(shí)現(xiàn)多步預(yù)測(cè)[16]，即在單步預(yù)測(cè)基礎(chǔ)上，將上一步預(yù)測(cè)的結(jié)果作為下一步預(yù)測(cè)的初始條件輸入，通過多次遞推過程實(shí)現(xiàn)對(duì)特定步數(shù)的預(yù)測(cè)。然而每一步的預(yù)測(cè)值中均攜帶有誤差，遞推過程不可避免地會(huì)產(chǎn)生誤差放大效應(yīng)，特別是一步預(yù)測(cè)已有較大誤差時(shí)，遞推后的多步預(yù)測(cè)可能會(huì)出現(xiàn)嚴(yán)重偏差。

考慮到短時(shí)交通流是一種前后關(guān)聯(lián)性較強(qiáng)的隨機(jī)過程，提出了一種基于GLBQGA算法的多步預(yù)測(cè)模型。該模型利用GLBQGA算法良好的學(xué)習(xí)能力，構(gòu)建了當(dāng)前時(shí)刻流量Xt與之前幾步時(shí)刻的流量Xt-n、Xt-(n+1)、Xt-(n+2)… (t為當(dāng)前時(shí)刻，n為預(yù)測(cè)步長)之間的函數(shù)關(guān)系，并將所得規(guī)律外推實(shí)現(xiàn)多步預(yù)測(cè)，從而避開了傳統(tǒng)算法在遞推過程中產(chǎn)生的誤差累計(jì)效應(yīng)。

4.1 多步預(yù)測(cè)模型的構(gòu)建

4.1.1 模型基本結(jié)構(gòu)

時(shí)間序列預(yù)測(cè)法在交通流預(yù)測(cè)領(lǐng)域有著廣泛的應(yīng)用，該模型結(jié)構(gòu)簡單，在數(shù)據(jù)充分的情況下有較高的預(yù)測(cè)精度[17]，是很多改進(jìn)多步預(yù)測(cè)算法的模型基礎(chǔ)[18-19]，且取得了良好的預(yù)測(cè)效果。參考該設(shè)計(jì)思路，本文采用AR模型為基本模型結(jié)構(gòu)，將實(shí)測(cè)數(shù)據(jù)序列擬合成一個(gè)線性參數(shù)模型，如式(11)所示：

(11)

4.1.2 編碼及解空間變換

根據(jù)交通流特性，GLBQGA算法的染色體在解空間變換后適宜采用[0,1]區(qū)間內(nèi)的有序?qū)崝?shù)編碼方式，具體的變換公式為：

(12)

由上式可得變換后的基因鏈：

(13)

4.1.3 目標(biāo)函數(shù)設(shè)計(jì)

結(jié)合式(11)，對(duì)于每一代進(jìn)化中的基因鏈，建立如下目標(biāo)函數(shù)：

(14)

4.2 實(shí)驗(yàn)結(jié)果與分析

筆者對(duì)長沙市湘府路某路段由西向東方向的機(jī)動(dòng)車流量進(jìn)行了視頻采集，每5 min統(tǒng)計(jì)一組，共100組，其中80組用于建模，20組用于預(yù)測(cè)。為了評(píng)價(jià)預(yù)測(cè)效果，選取平均絕對(duì)百分比誤差(MAPE)作為評(píng)價(jià)指標(biāo)，計(jì)算公式為：

(15)

AR模型建模的主要步驟包括時(shí)間序列預(yù)處理、模型定階、模型參數(shù)估計(jì)與超前預(yù)測(cè)計(jì)算等。預(yù)處理采用一階差分使其相對(duì)平穩(wěn)化；模型定階選擇FPE(最小最終預(yù)報(bào)誤差)準(zhǔn)則，經(jīng)計(jì)算判斷最優(yōu)擬合模型為AR(8)；參數(shù)估計(jì)選擇較為成熟、計(jì)算簡單可靠的矩估計(jì)法[20]。對(duì)AR(8)模型進(jìn)行差分逆運(yùn)算，可得超前一步預(yù)測(cè)模型：

0.196Xt-3…-0.049Xt-8

(16)

依據(jù)傳統(tǒng)多步預(yù)測(cè)模型的建模思路，將超前一步的預(yù)測(cè)結(jié)果用于超前兩步預(yù)測(cè)中，再將預(yù)測(cè)值用于超前三步預(yù)測(cè)，以此類推實(shí)現(xiàn)超前任意步數(shù)的預(yù)測(cè)，例如AR超前3步預(yù)測(cè)模型，則需要代入超前一步和超前兩步的值，如式(17)所示：

0.196Xt-1…-0.049Xt-6

(17)

參考AR模型，本文多步預(yù)測(cè)基礎(chǔ)模型采用AR(8)，如超前三步預(yù)測(cè)時(shí)，n=8，m=3，則超前三步預(yù)測(cè)模型如式(18)所示：

(18)

將式(18)和式(14)結(jié)合，構(gòu)建GLBQGA算法的目標(biāo)函數(shù)，其它參數(shù)設(shè)定與3.2節(jié)一致。讀取前80個(gè)樣本進(jìn)行AR(8)模型參數(shù)擬合，對(duì)后20個(gè)樣本進(jìn)行預(yù)測(cè)，AR(8)模型和基于GLBQGA算法優(yōu)化的AR(8)模型超前三步預(yù)測(cè)曲線分別如圖5和圖6所示。

圖5 AR(8)模型超前三步預(yù)測(cè)曲線Fig.5 Three-step ahead forecasting results of AR(8) model

圖6 GLBQGA模型超前三步預(yù)測(cè)曲線Fig.6 Three-step ahead forecasting results of GLBQGA

AR(8)模型和基于GLBQGA算法優(yōu)化的AR(8)模型超前三步預(yù)測(cè)結(jié)果的MAPE指標(biāo)如表2所示：

表2 AR(8)模型和GLBQGA算法優(yōu)化的AR(8)模型超前三步預(yù)測(cè)結(jié)果對(duì)比

Table 2 Comparison of Three-step ahead forecasting results of AR(8) and GLBQGA

預(yù)測(cè)模型后20個(gè)樣本超前三步預(yù)測(cè)結(jié)果的MAPE指標(biāo)AR(8)26.75%GLBQGA算法優(yōu)化的AR(8)模型13.21%

從圖5、圖6和表2可知，GLBQGA算法優(yōu)化的AR(8)模型的預(yù)測(cè)效果優(yōu)于傳統(tǒng)的AR(8)模型，以超前三步預(yù)測(cè)為例，預(yù)測(cè)平均相對(duì)誤差由26.75%下降到13.21%，下降了50.62%。應(yīng)用結(jié)果表明，相比傳統(tǒng)的AR模型，基于本文提出的GLBQGA算法所構(gòu)建的短時(shí)交通流多步預(yù)測(cè)模型在超前多步預(yù)測(cè)時(shí)有著更高的精度，對(duì)實(shí)際交通流特性的刻畫也更為理想。

5 結(jié)論

1)提出基于全局-局部變異的Bloch球面量子遺傳算法GLBQGA，該算法在傳統(tǒng)Bloch球面量子遺傳算法基礎(chǔ)上，通過引入全局-局部變異算子改進(jìn)傳統(tǒng)BQGA算法的變異操作，使GLBQGA算法在搜索后期具備較強(qiáng)的局部搜索能力，有效避免了算法振蕩，提高了算法精度；通過合理限制量子轉(zhuǎn)角參數(shù)范圍在保證傳統(tǒng)BQGA算法搜索空間不變的前提下提高算法效率。

2)基于GLBQGA算法的機(jī)車二系支承載荷優(yōu)化調(diào)整實(shí)驗(yàn)結(jié)果證明，在不增加時(shí)間復(fù)雜度的前提下，GLBQGA算法較標(biāo)準(zhǔn)遺傳算法有著更為強(qiáng)大的搜索全局最優(yōu)精確解的能力。

3) 針對(duì)短時(shí)交通流多步預(yù)測(cè)問題的特點(diǎn)，提出一種基于GLBQGA算法優(yōu)化AR模型的短時(shí)交通流多步預(yù)測(cè)方法，實(shí)驗(yàn)結(jié)果表明其預(yù)測(cè)效果明顯優(yōu)于傳統(tǒng)AR模型，為交通流多步預(yù)測(cè)提供了一種新思路。

[1] Nowotniak R, Kucharski J. Higher-order quantum-inspired genetic algorithms[C]// Computer Science and Information Systems (FedCSIS), 2014 Federated Conference on. IEEE, 2014:465-470.

[2] Malossini A, Blanzieri E, Calarco T. Quantum genetic optimization[J]. Evolutionary Computation, IEEE Transactions on, 2008, 12(2): 231-241.

[3] Khorsand A R, Akbarzadeh-T M R. Quantum gate optimization in a meta-level genetic quantum algorithm[C]//Systems, Man and Cybernetics, 2005 IEEE International Conference on. IEEE, 2005, 4: 3055-3062.

[4] 熊焰,陳歡歡,苗付友,等.一種解決組合優(yōu)化問題的量子遺傳算法QGA[J]. 電子學(xué)報(bào),2004,32(11):1855-1858. XIONG Yan, CHEN Huanhuan, MIAO Fuyou, et al. A quantum genetic algorithm to solve combinatorial optimization problem[J]. ACTA Electronica Sinica, 2004,32(11):1855-1858.

[5] 沈微微, 華明正, 李敏. 量子遺傳進(jìn)化算法的收斂性研究[J]. 信息技術(shù), 2013(10):161-164. SHEN Weiwei, HUA Mingzheng, LI Min. Study on convergence of quantum genetic evolution algorithm[J]. Information Technology, 2013(10):161-164.

[6] 易正俊，侯坤，何榮花. 自適應(yīng)Bloch球面的量子遺傳算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2012,48(35):57-61. YI Zhenjun，HOU Kun，HE Ronghua．Adaptive quantum genetic algorithm based on bloch sphere[J]．Computer Engineering and Applications, 2012, 48(35):57-61.

[7] 張葛祥, 金煒東. 量子遺傳算法的改進(jìn)及其應(yīng)用[J]. 西南交通大學(xué)學(xué)報(bào), 2003, 38(6):717-722. ZHANG Gexiang, JIN Weidong. Improvement of quantum genetic algorithm and its application[J]. Journal of Southwest Jiaotong University, 2003, 38(6):717-722.

[8] 李盼池. 基于量子位Bloch坐標(biāo)的量子遺傳算法及其應(yīng)用[J]. 控制理論與應(yīng)用, 2008, 25(6):985-989. LI Pan-chi. Quantum genetic algorithm based on Bloch coordinates of qubits and its application[J]. Control Theory & Applications, 2008, 25(6):985-989.

[9] 李士勇, 李盼池. 量子計(jì)算與量子優(yōu)化算法[M]. 哈爾濱：哈爾濱工業(yè)大學(xué)出版社, 2009,5: 86-95. Li Shiyong, Li Panchi. Quantum computation and quantum optimization algorithms[M]. HARBIN Institute of Technology Press, 2009,5: 86-95.

[10] 趙義武, 牛慶銀, 王憲成. 遺傳算法與蟻群算法的融合研究[J]. 科學(xué)技術(shù)與工程, 2010,10(16):4017-4020. ZHAO Yiwu,NIU Qingyin,WANG Xiancheng.Study on the combination of genetin algorith and Ant Algoicthm[J].Scicence Fechnology and Engineering, 2010,10(16):4017-4020.

[11] Pan D, Wang M, Zhu Y, et al. An optimization algorithm for locomotive secondary spring load adjustment based on artificial immune[J]. Journal of Central South University, 2013, 20(12): 3497-3503.

[12] 潘迪夫, 黎航, 韓錕. 基于遺傳算法的機(jī)車二系支承載荷調(diào)整優(yōu)化方法[J]. 中國鐵道科學(xué), 2005, 26(3): 83-87. PAN Difu , LI Hang , HAN Kun. Optimization model of locomotive secondary spring load adjustment based on genetic algorithm[J]. China Railway Science, 2005, 26(3): 83-87.

[13] 韓錕, 潘迪夫. 基于混合算法的機(jī)車二系彈簧載荷調(diào)整優(yōu)化方法[J]. 中國鐵道科學(xué), 2006, 27(2): 88-92. HAN Kun , PAN Difu. Optimization model for adjustment of locomotive secondary spring load based on hybrid algorithm[J]. CHINA RAILWAY SCIENCE, 2006, 27(2): 88-92.

[14] 楊本磊, 潘迪夫. 基于人工魚群算法的機(jī)車二系支承載荷調(diào)整優(yōu)化方法[J]. 計(jì)算機(jī)與現(xiàn)代化, 2011,(1): 53-54. YANG Benlei, PAN Difu. Optimization model of locomotive secondary spring load adjustment based on artificial fish-swarm algorithm[J].Computer and Modevnization, 2011,(1): 53-54.

[15] 潘迪夫, 韓錕, 曾亞波,等. 車體稱重調(diào)簧試驗(yàn)裝置及其應(yīng)用[J]. 電力機(jī)車與城軌車輛, 2003, 26(5):37-39. PAN Difu, HAN Kun, ZENG Yabo, et al. Locomotive secondary spring load test device and its application[J]. Electric Locomotives & Transit Vehicles, 2003, 26(5):37-39.

[16] 王秋蘭. 短時(shí)交通參數(shù)多步預(yù)測(cè)方法研究[D]. 長春: 吉林大學(xué), 2012. WANG Qiulan. Study on the multi-steps prediction method of short-time traffic parameters[D]. Changchun: Jilin University, 2012.

[17] 宋馳, 沈國江. 短時(shí)交通流預(yù)測(cè)模型綜述[J]. 自動(dòng)化博覽, 2012(6):84-87. SONG Chi, SHEN Guojiang. Survey on short-term traffic flow forecasting modelling[J]. Automation Panorama,2012(6):84-87.

[18] 韓超, 宋蘇, 王成紅. 一種改進(jìn)的短時(shí)交通流多步自適應(yīng)預(yù)測(cè)算法[J]. 公路交通科技, 2005, 22 (1):115-118. HAN Chao , SONG Su , WANG Chenghong. An improved multi-step adaptive forecasting method for short-term traffic flow[J]. Journal of Highway and Transportation Research and Development, 2005, 22 (1):115-118.

[19] 李明濤. 快速路短時(shí)間尺度地點(diǎn)交通參數(shù)多步預(yù)測(cè)方法研究[D]. 長春:吉林大學(xué)，2009. LI Mingtao. Study on the methods of located traffic parameters short-term and multi-steps prediction for expressway[D]. Changchun:: Jilin University, 2009.

[20] Soleimanimehr H, Nategh M J, Amini S. Prediction of machining force and surface roughness in ultrasonic vibration-assisted turning using neural networks[J]. Advanced Materials Research, 2009, 83(12): 326～334.

An improved bloch spherical quantum genetic algorithm and its application

LI Jiacai, HAN Kun, BAO Tianzhe

(School of Traffic &Transportation Engineering, Central South University, Changsha 410075, China)

An improved Bloch Spherical Quantum Genetic Algorithm (GLBQGA) was proposed to overcome the shortcoming of the quantum genetic algorithm (QGA), i.e., local optimization, when it is used for the optimization of continuous functions with many extreme values. In order to make sure the algorithm can converge to the exact solution of optimal local neighborhood search after searching global optimum approximation, a new variation of global-local operator was introduced, and a local search mechanism was established based on globally attributes. The quantum angular value program was further optimized, while ensuring the search space and improving the efficiency of search. Calculative examples were made in optimization of locomotive secondary uniform load distribution and application of short-time traffic flow prediction, and the results show that GLBQGA can overcome the QGA premature convergence problems, and improve precision without increasing search time significantly.

bloch spherical coordinate; quantum genetic algorithm; spring adjustment; traffic flow prediction

2016-03-05

國家自然科學(xué)基金資助項(xiàng)目(51305467)

韓錕(1977-)，女，湖北隨州人，副教授，博士，從事載運(yùn)工具智能測(cè)控技術(shù)及性能優(yōu)化研究；E-mail：hkun@csu.edu.cn

TP301.6；U260.72

A

1672-7029(2016)11-2262-08