杜 江 袁中華 王景芹

(河北工業(yè)大學(xué)電磁場(chǎng)與電器可靠性省部共建重點(diǎn)實(shí)驗(yàn)室 天津 300130)

一種基于灰預(yù)測(cè)理論的混合蛙跳算法

杜 江 袁中華 王景芹

(河北工業(yè)大學(xué)電磁場(chǎng)與電器可靠性省部共建重點(diǎn)實(shí)驗(yàn)室 天津 300130)

為提高混合蛙跳算法在優(yōu)化問題求解中的性能，提出一種基于灰預(yù)測(cè)理論的改進(jìn)混合蛙跳算法。該算法首先將基本算法的進(jìn)化模式進(jìn)行調(diào)整，強(qiáng)化了進(jìn)化過程中全局信息的交換；之后引入移動(dòng)步長(zhǎng)變異算子，根據(jù)進(jìn)化過程的不同階段和利用灰預(yù)測(cè)理論獲得進(jìn)化過程中最優(yōu)解進(jìn)步速度，并借鑒模糊控制思想對(duì)該變異算子進(jìn)行控制，進(jìn)而實(shí)現(xiàn)移動(dòng)步長(zhǎng)的自適應(yīng)調(diào)整。采用6個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)，與基本算法和已有改進(jìn)算法進(jìn)行性能對(duì)比分析，證明了改進(jìn)后的混合蛙跳算法在收斂精度、收斂速度和收斂成功率方面的優(yōu)越性及灰預(yù)測(cè)理論在算法改進(jìn)領(lǐng)域中的可行性。最后，將改進(jìn)算法應(yīng)用于10 kV油浸式配電變壓器優(yōu)化設(shè)計(jì)工作中，驗(yàn)證了該改進(jìn)算法的實(shí)用性。

混合蛙跳算法 灰預(yù)測(cè) 變異算子 優(yōu)化設(shè)計(jì)

0 引言

近年來，應(yīng)優(yōu)化問題之需求，各種智能仿生算法相繼被提出，如遺傳算法、粒子群算法、混合蛙跳算法(Shuffled Frog Leaping Algorithm，SFLA)等。其中，混合蛙跳算法于2003年由M.M.Eusuff等[1]提出，該算法是結(jié)合了模因算法和粒子群優(yōu)化算法的一種全新智能仿生算法，具有結(jié)構(gòu)簡(jiǎn)單、設(shè)置參數(shù)數(shù)量較少、魯棒性強(qiáng)等優(yōu)點(diǎn)，一經(jīng)提出便在計(jì)算機(jī)領(lǐng)域和許多工程領(lǐng)域得到了廣泛的應(yīng)用[2-6]。

然而，混合蛙跳算法也存在易陷入局部最優(yōu)、收斂精度不高和收斂成功率低等不足。為了提高該算法的整體性能，國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究與改進(jìn)。文獻(xiàn)[7]將變異算子引入算法，加強(qiáng)了青蛙種群的多樣性，增加了解空間的搜索范圍，降低了算法早熟的可能性。文獻(xiàn)[8]把加速因子的概念引入子種群內(nèi)部迭代中，提高了算法整體尋優(yōu)能力。文獻(xiàn)[9]將差分進(jìn)化機(jī)制有機(jī)地嵌入進(jìn)化過程中，改善了種群的多樣性，進(jìn)而提高了算法在復(fù)雜優(yōu)化問題中的尋優(yōu)能力。

本文針對(duì)基本混合蛙跳算法的不足，將算法的運(yùn)行模式予以調(diào)整，并引入移動(dòng)步長(zhǎng)變異算子和灰預(yù)測(cè)理論，進(jìn)而構(gòu)建一種基于灰預(yù)測(cè)理論的新模式混合蛙跳算法(New Model for Shuffled Frog Leaping Algorithm，PMSFLA)。仿真結(jié)果表明，改進(jìn)后的算法在收斂精度、收斂速度、收斂成功率以及實(shí)用性方面都具有較好的效果，算法的綜合性能得到了有效提升。

1 基本混合蛙跳算法

基本混合蛙跳算法是一種全局尋優(yōu)的啟發(fā)式智能仿生算法，其尋優(yōu)過程是模擬自然界中青蛙撲食現(xiàn)象。該算法每次進(jìn)化過程可分為兩大機(jī)制：種群混合排序機(jī)制和子種群內(nèi)部尋優(yōu)機(jī)制。種群混合排序機(jī)制，即種群中青蛙個(gè)體按照適應(yīng)度進(jìn)行排序、重新劃分子種群。子種群內(nèi)部尋優(yōu)機(jī)制，即子種群內(nèi)部進(jìn)化。

設(shè)蛙群由F個(gè)分布在D維解空間的青蛙個(gè)體組成，每個(gè)子種群中參與進(jìn)化青蛙個(gè)體的屬性均含有兩個(gè)D維矢量：Xi=(xi1，xi2，…，xiD)和Di=(di1，di2，…，diD)，其中，1≤i≤m，-Dimax≤Di≤Dimax，Dimax為最大移動(dòng)步長(zhǎng)。進(jìn)化式為

Di=rand( )×(Xi-Xw)

(1)

Xw(new)=Xw(old)+Di

(2)

Xw(new)=Xw(old)+rand( )×Dimax

(3)

式中，Di為移動(dòng)步長(zhǎng)；rand()表示取(0，1)區(qū)間的隨機(jī)數(shù)；Xw(old)、Xw(new)分別為進(jìn)化前、后的青蛙個(gè)體位置。當(dāng)式(2)為局部深度搜索時(shí)，Xi為子種群最優(yōu)個(gè)體位置Xb；當(dāng)式(2)為全局深度搜索時(shí)，Xi為整個(gè)種群最優(yōu)個(gè)體位置Xg，式(3)為隨機(jī)移動(dòng)公式。

算法根據(jù)適應(yīng)度判斷其位置的優(yōu)劣，每次進(jìn)化均是由子種群的最差個(gè)體參與，且每次進(jìn)化選擇進(jìn)行局部深度搜索、全局深度搜索和隨機(jī)移動(dòng)三種操作中的一種。

2 改進(jìn)的混合蛙跳算法

2.1 算法模式的調(diào)整

基本混合蛙跳算法中，青蛙種群按照適應(yīng)度排序、劃分子種群之后，每個(gè)子種群各自進(jìn)行內(nèi)部進(jìn)化，直到達(dá)到內(nèi)部進(jìn)化次數(shù)或滿足其他結(jié)束條件。之后，判斷是否滿足整個(gè)算法的結(jié)束條件，如果滿足則結(jié)束，否則再次進(jìn)行排序、劃分子種群、子種群內(nèi)部進(jìn)化，直到滿足整個(gè)算法的結(jié)束條件。此進(jìn)化過程的不足之處是：子種群內(nèi)部的多次進(jìn)化中，由于子種群進(jìn)化間不平衡性的存在，不能保證每次進(jìn)化均是以種群適應(yīng)度最優(yōu)的前m個(gè)個(gè)體為進(jìn)化目標(biāo)。

鑒于基本混合蛙跳算法的上述問題，本文對(duì)基本算法的進(jìn)化模式予以調(diào)整：將基本混合蛙跳算法中的種群混合排序(劃分子種群)機(jī)制與子種群內(nèi)部進(jìn)化機(jī)制進(jìn)行合并處理，即子種群內(nèi)部每進(jìn)行一次進(jìn)化就進(jìn)行一次種群混合排序(劃分子種群)。這種每次進(jìn)化前都進(jìn)行混合排序(劃分子種群)操作的運(yùn)行模式打破了子種群對(duì)青蛙個(gè)體進(jìn)化的限制，提高了局部深度搜索中進(jìn)化目標(biāo)的質(zhì)量，即保證了子種群每次局部深度搜索的進(jìn)化目標(biāo)都是全種群最優(yōu)秀的m個(gè)個(gè)體之一。如此調(diào)整之后構(gòu)成的新模式混合蛙跳算法，加強(qiáng)了算法全局信息的交換，簡(jiǎn)化了算法的進(jìn)化模式，對(duì)算法跳出局部極值點(diǎn)、提高進(jìn)化效率有很大幫助。

2.2 自適應(yīng)步長(zhǎng)思想的引入

在算法進(jìn)化過程中，采用合適的移動(dòng)步長(zhǎng)，可同時(shí)兼顧算法的收斂速度和收斂精度。所以，本文引入移動(dòng)步長(zhǎng)變異算子，自適應(yīng)調(diào)整移動(dòng)步長(zhǎng)的大小。

2.2.1 變異算子的引入

遺傳算法是一種經(jīng)典的現(xiàn)代優(yōu)化算法，廣泛應(yīng)用于工程領(lǐng)域中[10，11]。本文效仿遺傳算法，添加變異操作機(jī)制，自適應(yīng)地改變移動(dòng)步長(zhǎng)(移動(dòng)速度)的大小，是一種非常有效的提高求解性能的方法。本文在種群進(jìn)化的移動(dòng)步長(zhǎng)中，引入變異算子將式(1)改進(jìn)為[7]

Di=rand( )×bi(Xi-Xw)

(4)

式中，bi為移動(dòng)步長(zhǎng)的變異算子。

由式(4)可看出，變異算子的大小直接影響移動(dòng)步長(zhǎng)的大小，進(jìn)而影響蛙群對(duì)解空間的搜索范圍。顯然，bi取值較大時(shí)的移動(dòng)步長(zhǎng)較大，所搜索的解空間范圍就較大；反之，搜索空間較小。當(dāng)算法處于進(jìn)化前期，較大的移動(dòng)步長(zhǎng)可以提高算法收斂速度，使蛙群迅速聚集在最優(yōu)解附近；當(dāng)算法處于進(jìn)化后期，較小的移動(dòng)步長(zhǎng)可以減緩粒子在最優(yōu)解附近的往復(fù)振蕩，使算法更精確地收斂于最優(yōu)解。另外，當(dāng)算法具有較快的進(jìn)步速度時(shí)，較小的移動(dòng)步長(zhǎng)可較大可能地避免粒子跳過解空間內(nèi)較優(yōu)的位置；當(dāng)算法的進(jìn)步速度較慢時(shí)，說明算法很有可能陷入局部最優(yōu)，此時(shí)較大的移動(dòng)步長(zhǎng)有助于算法跳出局部最優(yōu)。

通過上述分析，本文最終確定了移動(dòng)步長(zhǎng)的變異算子bi的控制量：“算法進(jìn)化階段”和“算法進(jìn)步速度”。即這兩個(gè)控制量共同決定bi的取值。

2.2.2 灰預(yù)測(cè)控制器設(shè)計(jì)

灰預(yù)測(cè)控制器設(shè)計(jì)如圖1所示，其中S和V為變異系數(shù)控制器的輸入量，分別表示“算法進(jìn)化階段”和“算法進(jìn)步速度”兩個(gè)控制量的測(cè)量值。由這兩個(gè)控制量的測(cè)量值，通過控制規(guī)則共同決定變異算子bi的取值。

圖1 灰預(yù)測(cè)控制器設(shè)計(jì)Fig.1 Grey prediction controller design

2)算法進(jìn)步速度測(cè)量值V。設(shè)Yg1、Yg2分別表示相鄰兩次進(jìn)化種群最優(yōu)適應(yīng)度，用它們的差值Yg2-Yg1表示算法當(dāng)前的進(jìn)步速度。設(shè)vmark_min、vmark_max分別表示算法進(jìn)步速度的閾值，當(dāng)Yg2-Yg1∈(-∞，vmark_min]時(shí)，則認(rèn)為算法進(jìn)步速度較小，說明很可能收斂于局部最優(yōu)解附近，此時(shí)應(yīng)使bi取一較大值，這樣有助于算法跳出局部最優(yōu)解；當(dāng)Yg2-Yg1∈[vmark_max，+∞)時(shí)，則認(rèn)為算法進(jìn)步速度較大，此時(shí)應(yīng)使bi取一較小值，避免移動(dòng)步長(zhǎng)太大而漏掉解空間內(nèi)較好的解；當(dāng)Yg2-Yg1∈(vmark_min，max)，即進(jìn)步速度適中時(shí)，bi取一適中值。

傳統(tǒng)方法是得到Y(jié)g1之后，再進(jìn)行一次算法進(jìn)化得到Y(jié)g2，進(jìn)而作差由Yg2-Yg1判斷算法的進(jìn)步速度。然而這種獲取算法進(jìn)步速度的方法具有明顯的滯后性：若進(jìn)步速度顯示需要調(diào)整bi，則相當(dāng)于為了調(diào)整bi進(jìn)行了一次質(zhì)量很差的進(jìn)化。針對(duì)此問題，本文獲取進(jìn)步速度的方式不是進(jìn)行下一次的實(shí)際進(jìn)化，而是根據(jù)已有數(shù)據(jù)對(duì)下一次進(jìn)化結(jié)果進(jìn)行預(yù)測(cè)，根據(jù)預(yù)測(cè)結(jié)果求得當(dāng)前進(jìn)步速度，進(jìn)而調(diào)整變異算子bi的取值。這種“防患于未然”的控制思想，大大減少了徒勞的進(jìn)化代數(shù)，對(duì)減小算法運(yùn)行的盲目性、提高運(yùn)行效率具有顯著效果。

灰預(yù)測(cè)理論[12]是灰理論的一部分，具有所需原始數(shù)據(jù)少、環(huán)境適應(yīng)性強(qiáng)、預(yù)測(cè)精度高等優(yōu)點(diǎn)且計(jì)算量較小，因此本文采用灰預(yù)測(cè)理論對(duì)下一次進(jìn)化結(jié)果進(jìn)行預(yù)測(cè)。

結(jié)合變異算子的控制特點(diǎn)，對(duì)灰預(yù)測(cè)過程闡述如下。

(1)設(shè)置原始序列：x=(x(1)，x(2)，…，x(p))，其中p≥4，x(1)，x(2)，…，x(p)是最近的連續(xù)p次進(jìn)化的種群最優(yōu)適應(yīng)度。x(1)，x(2)，…，x(p)是一組遞增的序列。

(2)級(jí)比平滑檢驗(yàn)：利用式(5)進(jìn)行級(jí)比平滑檢驗(yàn)。

(5)

(3)白化型GM(1，1)建模。

①利用式(6)進(jìn)行AGO處理。

x(1)(q)=x(1)(q-1)+x(q) 1≤q≤p

(6)

且當(dāng)q=1時(shí)，x(1)(1)=x(1)。

②利用式(7)進(jìn)行MEAN處理。

z(1)(q)=0.5x(1)(q)+0.5x(1)(q-1) 2≤q≤p

(7)

③利用式(8)和式(9)求得發(fā)展系數(shù)a和灰作用量b。

(8)

(9)

④利用式(10)和式(11)求得GM(1，1)白化響應(yīng)式。

(10)

(11)

(4)殘差檢驗(yàn)：利用式(10)～式(12)求得殘差序列e(1)，e(1)，…，e(p)，進(jìn)而利用式(13)求得精度p。。

(12)

(13)

式中，e(1)=0。若p。<90%，說明原始數(shù)列的波動(dòng)性較大，即算法具有較快的進(jìn)步速度，則給變異算子bi賦一較小值，灰預(yù)測(cè)過程到此結(jié)束；否則說明此方法具有較高的預(yù)測(cè)精度，進(jìn)而繼續(xù)步驟(5)。

(5)利用式(14)預(yù)測(cè)下一次迭代后的最優(yōu)適應(yīng)度。

(14)

如果Yg_per-Yg較小，說明算法進(jìn)步速度較慢，則給變異算子bi賦一較大值；否則給變異系數(shù)bi賦一較小值。

3)當(dāng)這兩個(gè)控制量的“意見”出現(xiàn)分歧時(shí)，應(yīng)綜合考慮其對(duì)算法的影響，決定給變異算子bi賦以較大值bib、適中值bim還是較小值bil。綜上分析，并借助模糊控制的思想，得到變異算子控制規(guī)則見表1。

表1 控制規(guī)則Tab.1 Control rules table

2.3 改進(jìn)后算法流程

將基本混合蛙跳算法改進(jìn)后，得到一種基于灰預(yù)測(cè)理論的新模式混合蛙跳算法，算法流程如下：

1)對(duì)算法參數(shù)及蛙群進(jìn)行初始化。

2)計(jì)算每只青蛙個(gè)體的適應(yīng)度Yi。

3)對(duì)該蛙群按適應(yīng)度從優(yōu)到差進(jìn)行降優(yōu)排序。

4)將該青蛙種群分為m個(gè)青蛙子種群，具體劃分子種群方法描述如下：蛙群按適應(yīng)度從優(yōu)到差排序，第1只青蛙分給第1子種群，第2只青蛙分給第2子種群，…，第m只青蛙分給第m子種群，第m+1只青蛙分給第1子種群，第m+2只青蛙分給第2子種群，…，第F只青蛙分給第m子種群。

5)找出每個(gè)子種群中適應(yīng)度最優(yōu)的青蛙位置Xb和適應(yīng)度最差的青蛙位置Xw。

6)對(duì)每個(gè)子種群中適應(yīng)度最差的青蛙進(jìn)行更新處理。對(duì)其執(zhí)行的操作進(jìn)行選擇，包括局部深度搜索、全局深度搜索和隨機(jī)移動(dòng)。各操作描述如下：①首先試探局部深度搜索，利用式(2)和式(4)使子種群適應(yīng)度最差個(gè)體向子種群適應(yīng)度最優(yōu)個(gè)體方向前進(jìn)一步，如果Xw(new)的適應(yīng)度優(yōu)于Xw(old)的適應(yīng)度，則確定執(zhí)行局部深度搜索并跳轉(zhuǎn)至步驟7，否則拋棄局部深度搜索；②試探全局深度搜索：利用式(2)和式(4)使子種群適應(yīng)度最差個(gè)體向種群適應(yīng)度最優(yōu)個(gè)體方向前進(jìn)一步，如果Xw(new)的適應(yīng)度優(yōu)于Xw(old)的適應(yīng)度，則確定執(zhí)行全局深度搜索并跳轉(zhuǎn)至步驟7，否則拋棄全局深度搜索；③利用式(3)執(zhí)行隨機(jī)移動(dòng)。

7)計(jì)算更新后每只青蛙的適應(yīng)度Yi，并找出種群最優(yōu)適應(yīng)度Yg及其位置Xg。

8)如果算法當(dāng)前進(jìn)化代數(shù)i

9)判斷是否滿足結(jié)束條件，即判斷是否達(dá)到最大混合迭代次數(shù)N1或滿足最小允許誤差Δ。如果不滿足結(jié)束條件，則執(zhí)行步驟3；否則輸出優(yōu)化結(jié)果并結(jié)束。

3 仿真實(shí)驗(yàn)

3.1 變異參數(shù)的確定

通過前文的分析可知，變異參數(shù)bil、bim、bib的不同取值對(duì)PMSFLA的綜合性能有較大影響。若bil、bim、bib的取值分別在0.6～0.8、0.9～1.1、1.8～2.2之間，則PMSFLA的性能較好。本文通過實(shí)驗(yàn)法確定能夠使PMSFLA展現(xiàn)出優(yōu)秀性能的變異參數(shù)的最佳組合。表2給出了不同變異參數(shù)組合下算法PMSFLA對(duì)測(cè)試函數(shù)Schwefel的仿真結(jié)果，函數(shù)信息見表3。其中，PMSFLA的青蛙個(gè)體數(shù)F=48，子種群數(shù)m=8，最大移動(dòng)步長(zhǎng)Djmax=0.3，最大混合迭代次數(shù)N1=100，子種群內(nèi)部迭代次數(shù)N2=20，各控制參數(shù)pmark_min=0.5、pmark_max=0.75、vmark_min=0.05、vmark_max=0.5。表2中平均收斂精度為PMSFLA在10維度解空間內(nèi)運(yùn)行20次的平均收斂精度；收斂次數(shù)為算法PMSFLA在10維度解空間內(nèi)運(yùn)行20次中收斂精度達(dá)到10-20的次數(shù)，每次運(yùn)行的最大混合迭代次數(shù)為100次。

表2 Schwefel函數(shù)測(cè)試結(jié)果Tab.2 The test results of Schwefel function

由表2可看出，變異參數(shù)bib=2、bim=1、bil=0.8的組合可認(rèn)為是使PMSFLA展現(xiàn)非常優(yōu)異的綜合性能的最佳組合，因此，下文的仿真也將采用該參數(shù)組合。

3.2 實(shí)驗(yàn)設(shè)計(jì)

為了檢驗(yàn)本文改進(jìn)基本混合蛙跳算法思路的可行性，將MSFLA和PMSFLA與基本SFLA和葛等宇[7]提出的改進(jìn)算法(ImprovedShuffledFrogLeapingAlgorithm，ISFLA)做對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)選擇6個(gè)典型的測(cè)試函數(shù)進(jìn)行性能測(cè)試[13]，該6個(gè)測(cè)試函數(shù)的名稱、表達(dá)式等信息見表3。

實(shí)驗(yàn)的硬件環(huán)境為：WindowsXP系統(tǒng)，AMD雙核2.5GHzCPU，1.94G內(nèi)存。通過VC++軟件編寫程序進(jìn)行仿真實(shí)驗(yàn)。算法MSFLA、PMSFLA、SFLA和ISFLA的參數(shù)設(shè)置如下：青蛙個(gè)體數(shù)F=48，子種群數(shù)m=8，最大移動(dòng)步長(zhǎng)Djmax=0.3，最大混合迭代次數(shù)N1=200，子種群內(nèi)部迭代次數(shù)N2=20，各控制參數(shù)pmark_min=0.5、pmark_max=0.75、vmark_min=0.05、vmark_max=0.5、bib=2、bim=1、bil=0.8。本文實(shí)驗(yàn)從四個(gè)方面進(jìn)行驗(yàn)證。

表3 測(cè)試函數(shù)信息Tab.3 Test function information

1)固定算法進(jìn)化代數(shù)，根據(jù)多次實(shí)驗(yàn)的平均最優(yōu)解比較四種算法的求解精度。

2)固定算法進(jìn)化代數(shù)，通過記錄多次實(shí)驗(yàn)的運(yùn)行時(shí)間比較四種算法求解的計(jì)算量。

3)通過多次實(shí)驗(yàn)的平均進(jìn)化曲線比較四種算法的收斂速度。

4)固定收斂精度，結(jié)合進(jìn)化代數(shù)比較四種算法收斂的成功率。

3.3 實(shí)驗(yàn)結(jié)果及分析

3.3.1 算法求解精度對(duì)比

每種算法對(duì)每個(gè)測(cè)試函數(shù)在不同維度下均進(jìn)行20次實(shí)驗(yàn)，表4給出了該20次實(shí)驗(yàn)的平均最優(yōu)解。

由表4可看出，相對(duì)于SFLA，MSFLA在大多數(shù)優(yōu)化問題下都具有更高的求解精度；相對(duì)于另外兩種算法，PMSFLA在不同優(yōu)化問題下的求解精度均優(yōu)于其他三種算法。另外，PMSFLA與MSFLA的對(duì)比，體現(xiàn)了自適應(yīng)移動(dòng)步長(zhǎng)思想在求解精度方面的貢獻(xiàn)。此外由表4還可看出，由于不同測(cè)試函數(shù)在解空間內(nèi)的分布特性各異，PMSFLA對(duì)不同測(cè)試函數(shù)在其收斂精度方面的提高有著相對(duì)明顯的差異，對(duì)函數(shù)f2和函數(shù)f6收斂精度的提高比較有限。

表4 各函數(shù)在不同算法不同維度下的平均最優(yōu)解Tab.4 The average optimum solution of each function in the different algorithms under the different dimensions

3.3.2 算法求解計(jì)算量對(duì)比

設(shè)定解空間維度D=10。每種算法對(duì)每個(gè)測(cè)試函數(shù)進(jìn)行20次實(shí)驗(yàn)，每次實(shí)驗(yàn)進(jìn)行200次混合迭代，記錄該20次實(shí)驗(yàn)的總計(jì)算時(shí)間之和，見表5。

表5 各函數(shù)在不同算法下的運(yùn)行時(shí)間Tab.5 The runtime of each function in the different algorithms

表5中，SFLA與MSFLA的運(yùn)行時(shí)間對(duì)比顯示了對(duì)算法進(jìn)化模式的調(diào)整，使算法進(jìn)行混合迭代時(shí)計(jì)算量的增加；MSFLA與PMSFLA的運(yùn)行時(shí)間對(duì)比顯示了對(duì)算法移動(dòng)步長(zhǎng)的調(diào)整，使算法進(jìn)行混合迭代時(shí)計(jì)算量的增加。總體來講，MSFLA和PMSFLA的運(yùn)行時(shí)間略長(zhǎng)于SFLA，而與ISFLA的運(yùn)行時(shí)間基本相當(dāng)，說明MSFLA和PMSFLA在計(jì)算復(fù)雜度方面的增加非常有限。

3.3.3 算法收斂速度對(duì)比

設(shè)定解空間維度D=10。每種算法對(duì)每個(gè)測(cè)試函數(shù)進(jìn)行20次實(shí)驗(yàn)，得到200次混合迭代中每一代的平均最優(yōu)解數(shù)據(jù)，繪制收斂曲線，如圖2所示。同時(shí)為了較直觀地展示各算法的進(jìn)化趨勢(shì)，對(duì)其進(jìn)化數(shù)據(jù)取自然對(duì)數(shù)。圖2中函數(shù)f3的收斂曲線中SFLA與MSFLA兩條曲線幾乎重合。

圖2 各測(cè)試函數(shù)收斂曲線Fig.2 Evolution curves of each test function

由圖2可知，MSFLA在大多數(shù)優(yōu)化問題下的收斂速度都優(yōu)于SFLA；PMSFLA在函數(shù)f1下的收斂速度與SFLA和MSFLA相仿、比ISFLA較差，在其他函數(shù)下的收斂速度均優(yōu)于其他三種算法。另外，圖2中PMSFLA與MSFLA的收斂曲線對(duì)比，說明合理地移動(dòng)步長(zhǎng)能夠更快地尋得更優(yōu)解。

3.3.4 算法收斂成功率對(duì)比

設(shè)定各測(cè)試函數(shù)的收斂精度見表6，解空間維度D=10。每種算法對(duì)每個(gè)測(cè)試函數(shù)進(jìn)行50次實(shí)驗(yàn)，混合迭代次數(shù)達(dá)到200次時(shí)仍未達(dá)到指定收斂精度，則認(rèn)為此次實(shí)驗(yàn)沒有收斂。記錄收斂時(shí)算法進(jìn)行混合迭代的次數(shù)、收斂成功次數(shù)，并計(jì)算收斂成功率見表7，其中，收斂成功率=收斂成功次數(shù)/50。

表6 各測(cè)試函數(shù)收斂精度Tab.6 The convergence precision of each test function

表7 各測(cè)試函數(shù)收斂成功率Tab.7 Success rate of convergence of each test function

由表7可知，對(duì)于以上6個(gè)測(cè)試函數(shù)，相對(duì)于SFLA，MSFLA在部分優(yōu)化問題下的收斂成功率有所提高；PMSFLA的收斂成功率均高于其他三種算法。

綜上分析，本文提出的PMSFLA在收斂精度、收斂速度和收斂成功率方面都得到了滿意的效果，體現(xiàn)了PMSFLA的優(yōu)越性。

4 實(shí)用性驗(yàn)證

近年來，越來越多的智能優(yōu)化算法被用于解決電力系統(tǒng)領(lǐng)域的優(yōu)化問題[14-17]。為了檢驗(yàn)本文提出的PMSFLA的實(shí)用性，將該改進(jìn)算法應(yīng)用于10 kV級(jí)容量為200 kV·A 的油浸式配電變壓器優(yōu)化設(shè)計(jì)中，并將其優(yōu)化結(jié)果與窮舉法和某廠家人工設(shè)計(jì)結(jié)果作對(duì)比。

實(shí)驗(yàn)的硬件環(huán)境為：Windows XP系統(tǒng)，AMD雙核2.5 GHz CPU，1.94 G內(nèi)存。PMSFLA參數(shù)設(shè)置：青蛙種群中青蛙個(gè)體數(shù)F=20，子種群數(shù)m=5，每個(gè)子種群內(nèi)青蛙個(gè)體數(shù)n=4，最大移動(dòng)步長(zhǎng)Djmax=0.3，算法進(jìn)化代數(shù)N1=20，子種群內(nèi)部搜索次數(shù)N2=8，pmark_min=0.5，pmark_max=0.75，vmark_min=0.05，vmark_max=0.5，bib=2，bim=1，bil=0.8。

表8為不同優(yōu)化方式下以變壓器總成本為目標(biāo)函數(shù)，以鐵心直徑、低壓線圈匝數(shù)、低壓導(dǎo)線規(guī)格和高壓導(dǎo)線規(guī)格為變量的優(yōu)化結(jié)果。其中，變壓器總成本=制造成本+10年運(yùn)行成本。從目標(biāo)函數(shù)上看，PMSFLA的優(yōu)化結(jié)果比人工設(shè)計(jì)結(jié)果節(jié)省1.21%的總成本，比窮舉法獲得的優(yōu)化結(jié)果總成本只高0.12%。而從計(jì)算時(shí)間上看，窮舉法耗時(shí)38.35 min，而PMSFLA耗時(shí)為3.45 min，耗費(fèi)時(shí)間比為11.12倍。綜上所述，PMSFLA進(jìn)行變壓器優(yōu)化設(shè)計(jì)具有很大的優(yōu)勢(shì)，PMSFLA具有很強(qiáng)的工程實(shí)用性。

表8 10 kV油浸式配電變壓器優(yōu)化結(jié)果Tab.8 Optimization results of 10 kV oil-immersed distribution transformer

5 結(jié)論

本文對(duì)基本SFLA進(jìn)行改進(jìn)：調(diào)整算法的運(yùn)行模式，將基本混合蛙跳算法中的種群混合排序(劃分子種群)機(jī)制與子種群內(nèi)部進(jìn)化機(jī)制進(jìn)行合并處理；引入移動(dòng)步長(zhǎng)變異算子，并采用灰預(yù)測(cè)方式獲取最優(yōu)解進(jìn)步速度，實(shí)現(xiàn)了移動(dòng)步長(zhǎng)的動(dòng)態(tài)調(diào)整。仿真實(shí)驗(yàn)結(jié)果表明：本文提出的改進(jìn)混合蛙跳算法有效提高了算法的求解精度、收斂速度和收斂成功率，增強(qiáng)了算法的尋優(yōu)性能。本文采用的預(yù)測(cè)思想不僅適用于改進(jìn)混合蛙跳算法，也可應(yīng)用于其他優(yōu)化算法的改進(jìn)工作。最后通過將本文提出的PMSFLA應(yīng)用于10 kV油浸式配電變壓器優(yōu)化設(shè)計(jì)工作中，證明了該改進(jìn)算法的實(shí)用性和優(yōu)越性。

[1] Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Water Resour Plan Manage，2003，129(3)：210-225.

[2] 代永強(qiáng)，王聯(lián)國(guó)，施秋紅，等.改進(jìn)的混合蛙跳算法性能分析及其在電力系統(tǒng)經(jīng)濟(jì)調(diào)度中的應(yīng)用[J].電力系統(tǒng)保護(hù)與控制，2012，40(10)：77-83.

Dai Yongqiang，Wang Lianguo，Shi Qiuhong，et al.Performance analysis of improved SFLA and the application in economic dispatch of power system[J].Power System Protection and Control，2012，40(10)：77-83.

[3] 耿超，王豐華，蘇磊，等.基于人工魚群與蛙跳混合算法的變壓器Jiles-Atherton模型參數(shù)辨識(shí)[J].中國(guó)電機(jī)工程學(xué)報(bào)，2015，35(18)：4799-4807.

Geng Chao，Wang Fenghua，Su Lei，et al.Parameter identification of Jiles-Atherton model for transformer based on hybrid artificial fish swarm and shuffled frog leaping algorithm[J].Proceedings of the CSEE，2015，35(18)：4799-4807.

[4] 王茜，張粒子，舒雋，等.基于閾值選擇策略的改進(jìn)混合蛙跳算法在電網(wǎng)規(guī)劃中的應(yīng)用[J].電力系統(tǒng)保護(hù)與控制，2011，39(3)：34-39.

Wang Qian，Zhang Lizi，Shu Jun，et al.Application of improved shuffled frog leaping algorithm based on threshold selection strategy in transmission network planning[J].Power System Protection and Control，2011，39(3)：34-39.

[5] 張沈習(xí)，陳楷，龍禹，等.基于混合蛙跳算法的分布式風(fēng)電源規(guī)劃[J].電力系統(tǒng)自動(dòng)化，2013，37(13)：76-82.

Zhang Shenxi，Chen Kai，Long Yu，et al.Distributed wind power planning based on hybrid leapfrog algorithm[J].Automation of Electric Power Systems，2013，37(13)：76-82.

[6] 王介生，高憲文.基于改進(jìn)蛙跳算法的電渣重熔過程多變量PID控制器設(shè)計(jì)[J].控制與決策，2011，26(11)：1731-1734.

Wang Jiesheng，Gao Xianwen.Design of multivariable PID controller of electroslag remelting process based on improved shuffled frog leaping algorithm[J].Control and Decision，2011，26(11)：1731-1734.

[7] 葛宇，王學(xué)平，梁靜.改進(jìn)的混合蛙跳算法[J].計(jì)算機(jī)應(yīng)用，2012，32(1)：234-237.

Ge Yu，Wang Xueping，Liang Jing.Improved shuffled frog leaping algorithm[J].Journal of Computer Applications，2012，32(1)：234-237.

[8] Elbeltagi E，Hegazy T，Grierson D.A modified shuffled frog-leaping optimization algorithm application to project management[J].Structure and Infrastructure Engineering，2007，3(1)：53-60.

[9] 趙鵬軍，邵澤軍.一種新的改進(jìn)的混合蛙跳算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48(8)：48-50.

Zhao Pengjun，Shao Zejun.Novel improved shuffled frog leaping algorithm[J].Computer Engineering and Applications，2012，48(8)：48-50.

[10]肖曦，許青松，王雅婷，等.基于遺傳算法的內(nèi)埋式永磁同步電機(jī)參數(shù)辨識(shí)方法[J].電工技術(shù)學(xué)報(bào)，2014，29(3)：21-26.

Xiao Xi，Xu Qingsong，Wang Yating，et al.Parameter identification of interior permanent magnet synchronous motors based on genetic algorithm[J].Transactions of China Electrotechnical Society，2014，29(3)：21-26.

[11]鄧軍，郝艷捧，李立浧，等.復(fù)雜導(dǎo)線垂直斷面地勢(shì)下直流線路無線電干擾計(jì)算的信賴域正則化遺傳算法[J].電工技術(shù)學(xué)報(bào)，2014，29(10)：304-311.

Deng Jun，Hao Yanpeng，Li Licheng，et al.Trust region regularization genetic algorithm for radio interference of DC transmission lines passing through complex vertical section terrains of conductors[J].Transactions of China Electrotechnical Society，2014，29(10)：304-311.

[12]鄧聚龍.灰預(yù)測(cè)與灰決策[M].武漢：華中科技大學(xué)出版社，2002.

[13]陶新民，劉福榮，劉玉，等.定向多尺度變異克隆選擇優(yōu)化算法[J].控制與決策，2011，26(2)：175-181.

Tao Xinmin，Liu Furong，Liu Yu，et al.Clone selection optimization algorithm with directional multi-scale mutation[J].Control and Decision，2011，26(11)：175-181.

[14]劉華臣，王錫淮，肖健梅，等.基于群搜索算法的電力系統(tǒng)無功優(yōu)化[J].電力系統(tǒng)保護(hù)與控制，2014，42(14)：93-99.

Liu Huachen，Wang Xihuai，Xiao Jianmei，et al.Reactive power optimization based on group search optimizer[J].Power System Protection and Control，2014，42(14)：93-99.

[15]周超，田立軍.基于粒子群優(yōu)化算法的電壓暫降監(jiān)測(cè)點(diǎn)優(yōu)化配置[J].電工技術(shù)學(xué)報(bào)，2014，29(4)：181-187.

Zhou Chao，Tian Lijun.An optimum allocation method of voltage sag monitoring nodes based on particle swarm optimization algorithm[J].Transactions of China Electrotechnical Society，2014，29(4)：181-187.

[16]宮金林，王秀和.基于多目標(biāo)有效全局優(yōu)化算法的直線感應(yīng)電動(dòng)機(jī)優(yōu)化設(shè)計(jì)[J].電工技術(shù)學(xué)報(bào)，2015，30(24)：32-37.

Gong Jinlin，Wang Xiuhe.Optimal design of a linear induction motor using multi-objective efficient global optimization[J].Transactions of China Electrotechnical Society，2015，30(24)：32-37.

[17]程聲烽，程小華，楊露.基于改進(jìn)粒子群算法的小波神經(jīng)網(wǎng)絡(luò)在變壓器故障診斷中的應(yīng)用[J].電力系統(tǒng)保護(hù)與控制，2014，42(19)：37-42.

Cheng Shengfeng，Cheng Xiaohua，Yang Lu.Application of wavelet neural network with improved particle swarm optimization algorithm in power transformer fault diagnosis[J].Power System Protection and Control，2014，42(19)：37-42.

(編輯 張洪霞)

Shuffled Frog Leaping Algorithm Based on Grey Prediction Theory

DuJiangYuanZhonghuaWangJingqin

(Province-Ministry Joint Key Laboratory of Electromagnetic Field and Electrical Apparatus Reliability Hebei University of Technology Tianjin 300130 China)

To enhance the performance of shuffled frog leaping algorithm in solving optimization problems，a new model for hybrid leapfrog algorithm based on grey prediction theory was proposed.The algorithmic evolution model was adjusted to strengthen the ability to exchange the global information in the process of evolution.Then the algorithm implemented the mobile step self-adaption adjustment through introduced mobile step mutation operator.The mutation operator was controlled by the different stages of evolution and the optimal solution progress speed in the process of evolution obtained by grey prediction theory and the fuzzy control thoughts.The advantages of the improved hybrid leapfrog algorithm，such as the accuracy，convergent speed and success rate，and the feasibility of grey prediction theory in the field of algorithm improvement，is verified by comparison with the basic shuffled frog leaping algorithm and the known improved algorithm on performance through six standard test functions.Finally，the practicability of the improved algorithm is proved by applying it to 10 kV oil-immersed distribution transformer optimization design works.

Shuffled frog leaping algorithm，grey prediction，mutation operator，optimal design

2016-05-09 改稿日期2016-08-26

10.19595/j.cnki.1000-6753.tces.160634

TP301

杜 江 男，1972年生，博士，副教授，研究方向?yàn)樽儔浩鲀?yōu)化設(shè)計(jì)和現(xiàn)代智能仿生算法及其應(yīng)用。

E-mail：dj@hebut.edu.cn

袁中華 男，1991年生，碩士研究生，研究方向?yàn)樽儔浩鲀?yōu)化設(shè)計(jì)和現(xiàn)代智能仿生算法及其應(yīng)用。

E-mail：1003816201@qq.com(通信作者)

河北省自然科學(xué)基金(E2016202134)、河北省人社廳項(xiàng)目(A2013007001)、河北省科學(xué)技術(shù)研究與發(fā)展項(xiàng)目(13210129)和河北省高等學(xué)校創(chuàng)新團(tuán)隊(duì)領(lǐng)軍人才培育計(jì)劃項(xiàng)目(LJRC003)資助。