天牛須搜索與遺傳的混合算法

趙玉強(qiáng)，錢 謙，周田江，伏云發(fā)

1(昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院，昆明 650500) 2(云南省計(jì)算機(jī)技術(shù)應(yīng)用重點(diǎn)實(shí)驗(yàn)室，昆明 650500)

1 引 言

近年來，眾多模擬自然界生物行為和物理變化特性的智能優(yōu)化算法[1]被相繼提出，這些算法的問題依賴度低且易于實(shí)現(xiàn)，一經(jīng)提出便受到廣泛關(guān)注.天牛須搜索算法(Beetle Antennae Search Algorithm,BAS)[2]是2017年提出的模仿甲蟲類(以天牛為例)生物覓食過程的智能優(yōu)化算法，該算法基于單個(gè)體搜索，結(jié)構(gòu)簡(jiǎn)單，在求解單峰值問題時(shí)有較好的收斂速度和求解精度，在許多領(lǐng)域中得到廣泛應(yīng)用[3-5].但是，BAS算法是單個(gè)個(gè)體搜索，并非群體尋優(yōu)，所以該算法缺乏一定的多樣性，在后期尋優(yōu)中容易陷入局部最優(yōu)值，不利于復(fù)雜問題的求解，因此，許多學(xué)者對(duì)其進(jìn)行了改進(jìn)，文獻(xiàn)[6]將單個(gè)體搜索變成群體搜索來提高尋優(yōu)能力，將BAS算法與花朵授粉算法結(jié)合提出了BASFPA算法，文獻(xiàn)[7]將BAS算法與神經(jīng)網(wǎng)絡(luò)結(jié)合用于預(yù)測(cè)風(fēng)暴潮災(zāi)害并取得了一定成果.遺傳算法(Genetic Algorithm,GA)[8]是一類理論較為完備的仿生優(yōu)化算法，大部分的研究圍繞在如何平衡對(duì)現(xiàn)有解的挖掘和對(duì)未知解的探索上，因?yàn)檫@很大程度上決定著種群的多樣性，進(jìn)而對(duì)算法的尋優(yōu)能力和尋優(yōu)速度產(chǎn)生重要的影響，現(xiàn)有文獻(xiàn)對(duì)GA的改進(jìn)主要體現(xiàn)在對(duì)選擇、交叉和變異算子的改進(jìn)上[9-11]，但這些改進(jìn)往往依賴給定的某些參數(shù)或執(zhí)行順序，這使算法對(duì)某些臨界參數(shù)比較敏感且不容易控制，反而有可能讓算法陷入混亂的狀態(tài)，為此，許多學(xué)者將遺傳算法與其他算法結(jié)合提出了許多混合算法[12-15]，以此來彌補(bǔ)遺傳算法自身的缺陷，相關(guān)研究在一定程度上取得了較好的結(jié)果.

在對(duì)BAS和GA的不足之處和各自優(yōu)勢(shì)的互補(bǔ)性進(jìn)行分析的基礎(chǔ)上，本文提出了一種基于BAS與GA的混合優(yōu)化算法(Hybrid Optimization Algorithm Based on BAS and GA，BASGA).該算法先分別對(duì)兩種算法進(jìn)行了有針對(duì)性的改進(jìn)，以最大限度發(fā)揮算法各自的優(yōu)勢(shì)，然后再將兩者互補(bǔ)結(jié)合，產(chǎn)生新算法.具體來說，首先對(duì)BAS算法進(jìn)行改進(jìn)，提出基于多向探路模型的變步長(zhǎng)反饋策略用以更新天牛個(gè)體的位置，并將改進(jìn)的BAS嵌入到GA中來提升算法整體的收斂速度和精度.之后，為了提高種群的多樣性，設(shè)計(jì)了一種擴(kuò)展的多子代競(jìng)爭(zhēng)交叉方式提高GA的探索能力，同時(shí)采用自適應(yīng)方法調(diào)節(jié)交叉和變異概率以控制種群的多樣性.最后，以函數(shù)優(yōu)化問題為例與其他學(xué)者提出的混合算法進(jìn)行了對(duì)比，實(shí)驗(yàn)結(jié)果證明BASGA算法在單峰值和多峰值函數(shù)優(yōu)化求解中都具有較好的尋優(yōu)性能.

2 基本算法的原理

2.1 GA算法的基本原理

遺傳算法有不同的編碼形式，本文采用實(shí)數(shù)編碼的遺傳算法.GA算法主要通過選擇、交叉和變異操作來求解問題解.其中，選擇操作是挖掘已有個(gè)體信息的主要手段，大多采用賭輪或隨機(jī)抽樣等比例方式來選擇一定數(shù)量的優(yōu)質(zhì)個(gè)體并放入下一代種群中，以確保種群的進(jìn)化方向.交叉和變異算子的作用是探索新的解：

1)交叉操作

實(shí)數(shù)GA大多采用算術(shù)交叉的方式進(jìn)行染色體的雜交，以實(shí)現(xiàn)基因重組的目的.對(duì)任意兩個(gè)染色體X和Y，其產(chǎn)生的子代X′,Y′可用式(1)表示：

X′=X+r1(Y-X)

Y′=X+r2(Y-X)

(1)

其中，r1和r2均是D個(gè)由(0,1)內(nèi)均勻分布的隨機(jī)數(shù)組成的向量，D是問題維度.

2)變異操作

在實(shí)數(shù)GA中，有多種方式實(shí)現(xiàn)對(duì)染色體的變異操作，大多數(shù)變異的基本原理是在原染色體上施加一個(gè)步長(zhǎng)擾動(dòng)來改變?nèi)旧w的基因以達(dá)到變異的目的，如式(2)所示.

X′=X+ε

(2)

其中，X′是變異后的染色體，X是原染色體，ε是步長(zhǎng)擾動(dòng)因子.

常用的變異策略有均勻變異、非均勻變異、高斯變異、柯西變異等.

2.2 BAS算法的基本原理

BAS算法通過天牛個(gè)體在可行域中不斷更新位置來找到全局最佳解.假設(shè)個(gè)體在D維解空間中的位置為X=(X1,X2,…,XD)，則其左右兩只觸須的位置Xr和Xl可以被定義為式(3)所示的模型：

(3)

個(gè)體在解空間不斷對(duì)左右觸須附近位置的適應(yīng)度進(jìn)行計(jì)算并向適應(yīng)度高的位置方向進(jìn)行移動(dòng).當(dāng)前位置個(gè)體Xt根據(jù)式(4)的規(guī)則移動(dòng)到下一個(gè)位置：

(4)

3 天牛須與遺傳混合算法

BAS算法側(cè)重過程搜索，有利于單峰問題的求解，GA算法是種群進(jìn)化尋優(yōu)，有利于多峰值問題的優(yōu)化.根據(jù)BAS算法和GA算法各自的優(yōu)勢(shì)，本小節(jié)提出兩者混合的算法.在混合之前，首先對(duì)兩種算法的優(yōu)點(diǎn)做進(jìn)一步的強(qiáng)化，BAS算法進(jìn)一步提高單個(gè)體尋優(yōu)的速度和局部搜索能力，而GA算法則增強(qiáng)種群多樣性以充分發(fā)揮其在全局尋優(yōu)中的優(yōu)勢(shì).

3.1 基于多向感知探路反饋的BAS算法

3.1.1 多向感知模型的構(gòu)建

傳統(tǒng)BAS算法中天牛觸須提供了一種非左即右的探索方向，如圖1(a)所示，個(gè)體只在當(dāng)前位置兩側(cè)的觸須方向計(jì)算適應(yīng)度大小并進(jìn)行比較，但因?yàn)橛|須朝向的隨機(jī)性，導(dǎo)致個(gè)體有很大可能會(huì)錯(cuò)過當(dāng)前位置附近更好的解，進(jìn)而影響算法的搜索性能.實(shí)際上，甲蟲觸須在自然界中能夠呈全角度轉(zhuǎn)動(dòng)的狀態(tài)，并未被局限于兩個(gè)相對(duì)方向，受此啟發(fā)，本文建立多向感知模型，通過式(5)在個(gè)體當(dāng)前位置產(chǎn)生n個(gè)單位向量作為右觸須轉(zhuǎn)動(dòng)的探知方向，而左觸須的探知方向取該向量的負(fù)值：

圖1 天牛觸須方向感知模型

(5)

其中，D表示求解問題的維度，rand是隨機(jī)數(shù)產(chǎn)生函數(shù).如圖1(b)所示，與傳統(tǒng)BAS只有兩個(gè)探索方向不同，新的多向模型包含了n對(duì)探索方向，增大了個(gè)體對(duì)當(dāng)前周圍位置的探索范圍，而且，算法可通過調(diào)節(jié)n的大小來調(diào)控探索的范圍，因此多向模型能進(jìn)一步提高算法的尋優(yōu)能力和收斂速度.

在多向感知模型的基礎(chǔ)上，通過式(6)可得到每對(duì)左右觸須頂點(diǎn)在解空間所處的位置：

Xrl={(Xri,Xli)|i∈[1,n]}

(6)

其中，X是天牛質(zhì)心的位置，Xrl是每對(duì)左右觸須頂點(diǎn)的位置，Xri和Xli分別是第i對(duì)左右觸須頂點(diǎn)的位置，l是質(zhì)心到天牛觸須頂點(diǎn)的距離長(zhǎng)度.特別說明，天牛質(zhì)心一般取天牛頭部中間位置，即兩觸須的中間位置.

3.1.2 變步長(zhǎng)的探路反饋更新策略

傳統(tǒng)BAS算法中個(gè)體的位置更新只在兩個(gè)感知方向上，并且不論更新后的新位置優(yōu)劣如何，都將作為新一代個(gè)體參與下次操作，假設(shè)更新后的個(gè)體比更新前的個(gè)體差，則算法會(huì)演變?yōu)橄虮畴x全局最優(yōu)解的方向搜索，因此，一種變步長(zhǎng)的探路反饋更新策略被提出用來解決這一難題.首先，天牛個(gè)體通過式(7)以步長(zhǎng)δ在多向感知模型產(chǎn)生的n對(duì)左右觸須方向上進(jìn)行更新，并得到n個(gè)反饋個(gè)體的位置Xf，然后在n個(gè)反饋個(gè)體中選取最佳個(gè)體用與當(dāng)前個(gè)體進(jìn)行比較，如果前者優(yōu)于后者，則將最佳個(gè)體替代當(dāng)前個(gè)體，反之，仍然采用當(dāng)前個(gè)體參與下一輪操作.

(7)

這種通過事先探路式的更新和比較可以有效的增強(qiáng)局部搜索能力，但這可能產(chǎn)生一個(gè)問題，如果當(dāng)前個(gè)體經(jīng)比較后不采取位置的更新，而δ和l經(jīng)過很多代的不斷縮小后變的不足以使當(dāng)前個(gè)體探索更廣泛的空間，這會(huì)導(dǎo)致當(dāng)前個(gè)體容易持續(xù)多代保持不更新的狀態(tài).基于以上考慮，本文設(shè)計(jì)如圖2所示的δ和l的更新規(guī)則.

圖2 參數(shù)更新規(guī)則流程圖

如果當(dāng)前個(gè)體進(jìn)行了更新操作，說明在當(dāng)前參數(shù)δ和l的作用下是可以繼續(xù)尋找最優(yōu)解的，則δ和l兩個(gè)參數(shù)都不更新；如果當(dāng)前個(gè)體沒有進(jìn)行更新操作，說明在當(dāng)前個(gè)體附近有很大概率并不存在比當(dāng)前個(gè)體位置更好的位置了，當(dāng)然，這并不排除沒有發(fā)現(xiàn)個(gè)體周圍更好的位置的情況，所以用一個(gè)很小的排除概率pe來表示當(dāng)前個(gè)體周圍還有更好的位置沒有被發(fā)現(xiàn)，所以δ和l在這種情況下依舊不采取更新措施，拋開這種特殊情況，則需要通過式(8)來更新δ和l來改變感知范圍，以找到更好的位置解.

lt=0.95lt-1+0.01

δt=0.95δt-1

(8)

其中，t是當(dāng)前迭代次數(shù).

3.2 改進(jìn)的GA算法

3.2.1 擴(kuò)展的多子代競(jìng)爭(zhēng)雜交算子

在GA中，交叉算子負(fù)責(zé)探索新的解，組合產(chǎn)生新的個(gè)體，尤其在后期種群個(gè)體同類化嚴(yán)重的狀況下，交叉對(duì)維護(hù)種群的多樣性起到了重要的作用.假設(shè)求解問題維度為2，基本整體算術(shù)交叉如圖3(a)所示，兩父代個(gè)體產(chǎn)生的子代只能在父代之間的解區(qū)域內(nèi)產(chǎn)生，這不利于充分挖掘父代的優(yōu)質(zhì)基因.為了能夠?qū)Ω复鷤€(gè)體周圍區(qū)域進(jìn)行短距離的探索，有研究采用了擴(kuò)展的算術(shù)交叉方法[16]，通過改變算術(shù)交叉中的隨機(jī)數(shù)范圍使子代個(gè)體能夠跳出父代個(gè)體圍成的解區(qū)域.例如，將式(1)中的隨機(jī)數(shù)范圍從0到1擴(kuò)展為從-0.5到1.25，從圖3(b)可以看出，改進(jìn)后的子代分布不再被局限于父代解空間之間，而是隨機(jī)分布在父代周圍.

圖3 交叉示意圖

上述改進(jìn)雖然讓子代具有了較為活躍的分布，但如果兩父代差異過大，那么子代將分布于廣泛的解空間范圍內(nèi)，在一定程度上將增加算法的隨機(jī)性.并且，子代的產(chǎn)生只與兩個(gè)父代有關(guān)聯(lián)，而與種群其他個(gè)體無關(guān)，拋開遺傳學(xué)說，從種群進(jìn)化角度來看，這種封閉式的進(jìn)化從本質(zhì)上弱化了種群之間相互學(xué)習(xí)的優(yōu)勢(shì)，不利于群體的進(jìn)化.因此，本文在前人的擴(kuò)展交叉方法的基礎(chǔ)上提出了一種差分多子代競(jìng)爭(zhēng)交叉策略，首先讓父代按照擴(kuò)展算術(shù)交叉的方式產(chǎn)生兩個(gè)子代，然后讓父代與種群其余兩個(gè)個(gè)體通過差分操作再次產(chǎn)生兩個(gè)子代，比較4個(gè)子代的優(yōu)劣，取最優(yōu)的兩個(gè)子代作為新的個(gè)體參與算法下一步的操作.綜上，本文的交叉方式將按照式(9)進(jìn)行操作：

(9)

其中，Xc是子代個(gè)體，Xf是父代個(gè)體.Xi和Xj是種群中與父代個(gè)體互不相同的兩個(gè)個(gè)體.r是隨機(jī)數(shù)，將通過式(10)加以描述.

(10)

通過上述的差分多子代競(jìng)爭(zhēng)交叉方式，產(chǎn)生的子代既可以充分挖掘父代周圍的信息，又可以增強(qiáng)種群個(gè)體間優(yōu)質(zhì)基因的交互性.

3.2.2 交叉概率和變異概率的自適應(yīng)改進(jìn)

交叉概率(pc)和變異概率(pm)是影響算法挖掘與探索平衡的關(guān)鍵參數(shù).傳統(tǒng)GA采用固定的pc和pm取值，但取值不易控制，如果取值過大，會(huì)增加算法的隨機(jī)性，反之，會(huì)影響算法的收斂能力.為此，不少學(xué)者提出了自適應(yīng)改變pc和pm的方法，并取得了一定的效果[17,18].本文采取一種非線性自適應(yīng)調(diào)節(jié)pc和pm的方法來縮減交叉和變異的頻率，進(jìn)而調(diào)控種群個(gè)體對(duì)解空間的搜索頻率.自適應(yīng)調(diào)節(jié)pc和pm的具體公式見式(11)，這一改進(jìn)方法已經(jīng)在本文作者之前所發(fā)表的文獻(xiàn)[19]中進(jìn)行了報(bào)道，因此不再進(jìn)行詳述.簡(jiǎn)單來說，如圖4(a)所示，在進(jìn)化前期交叉概率較大，能夠有效提高前期種群物種豐富程度，而在進(jìn)化接近結(jié)束時(shí)，交叉概率變小，能夠提高算法的收斂能力.自適應(yīng)調(diào)節(jié)pm的具體公式如式(12)所示，圖4(b)中實(shí)體曲線表示pm的取值，從該曲線可以看出，個(gè)體適應(yīng)度會(huì)隨著(f-favg)的增大而減小，這種變化規(guī)律很好的保護(hù)了優(yōu)質(zhì)個(gè)體.

(11)

其中：A是控制曲線曲率的參數(shù)，g是當(dāng)前進(jìn)化代數(shù)，G是總進(jìn)化代數(shù)，pcmax是最大交叉概率，pcmin是最小交叉概率.

(12)

其中，fmax和favg分別是種群最大個(gè)體適應(yīng)度和平均適應(yīng)度，f是種群當(dāng)前個(gè)體適應(yīng)度，pmmax和pmmin分別是最大和最小變異概率.

圖4 交叉示意圖

3.3 混合策略

BASGA算法采用一種簡(jiǎn)單的混合策略，將改進(jìn)后的BAS算法加入到改進(jìn)后的GA算法中對(duì)每代初始種群的個(gè)體進(jìn)行BAS操作，成為改進(jìn)GA種群適應(yīng)度的一個(gè)算子.在算法的前期階段，個(gè)體間的差別較大，執(zhí)行改進(jìn)BAS算法時(shí)，優(yōu)質(zhì)個(gè)體只需執(zhí)行很少次迭代便可達(dá)到預(yù)期效果，而劣質(zhì)個(gè)體則需要執(zhí)行較多次迭代，因此改進(jìn)BAS算法的迭代次數(shù)采用固定值是不合理的，應(yīng)根據(jù)個(gè)體的優(yōu)劣程度進(jìn)行區(qū)別對(duì)待.此外，本文在改進(jìn)BAS算法中通過相鄰代最優(yōu)個(gè)體(Xbest)的適應(yīng)度差值來判斷算法是否可以停止，如果該差值連續(xù)很多代(偽代碼中設(shè)置為ξ代)都小于一個(gè)設(shè)定的數(shù)值ε，則認(rèn)為算法很難再尋優(yōu)下去，即算法終止.具體判斷規(guī)則按照以下算法1所示的偽代碼進(jìn)行：

算法1.BAS算法終止規(guī)則偽代碼

1.t=0

3.t=t+1

4. Ift>ξ

5. 算法終止

6.end

另外，如果改進(jìn)GA中種群所有個(gè)體都參與改進(jìn)BAS算法會(huì)過早降低種群的多樣性，因此參與改進(jìn)BAS運(yùn)算的個(gè)體數(shù)量被設(shè)定為種群規(guī)模的10%.

3.4 BASGA算法的流程

通過對(duì)上述算法的描述，給出本文算法的流程圖和實(shí)現(xiàn)步驟，如圖5所示.

圖5 BASGA算法流程圖

BASGA算法實(shí)現(xiàn)步驟如下：

步驟1.設(shè)定算法初始參數(shù)，包括種群規(guī)模、維度和天牛須搜索算法需要的參數(shù)并生成初始種群；

步驟2.計(jì)算種群個(gè)體的適應(yīng)度值，根據(jù)適應(yīng)度值確定全局最優(yōu)個(gè)體；

步驟3.種群個(gè)體優(yōu)劣的評(píng)價(jià).計(jì)算種群個(gè)體的適應(yīng)度值；

步驟4.從種群中選出規(guī)定數(shù)量的個(gè)體參與改進(jìn)BAS算法的操作；

步驟5.根據(jù)式(5)和式(6)建立多向感知模型，計(jì)算各方向上感知觸須所處的位置；然后個(gè)體進(jìn)行基于反饋策略的位置更新，并且更新步長(zhǎng)和質(zhì)心到觸須的長(zhǎng)度；

步驟6.判斷是否滿足改進(jìn)BAS操作的結(jié)束條件，如果滿足結(jié)束條件則轉(zhuǎn)入步驟7；反之，轉(zhuǎn)入步驟3；

步驟7.種群進(jìn)行遺傳操作，分別參與選擇操作、交叉操作和變異操作；

步驟8.判斷是否滿足改進(jìn)GA的結(jié)束條件，如果滿足，則輸出最優(yōu)個(gè)體和最優(yōu)解；反之，轉(zhuǎn)入步驟2.

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

4.1 測(cè)試函數(shù)及對(duì)比算法

為了測(cè)試本文提出的BASGA算法的性 能，對(duì)表1給出的12個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行了仿真實(shí)驗(yàn)，其中，單峰值測(cè)試函數(shù)(f1～f6)用來測(cè)試算法挖掘群體信息的能力(稱為開采能力)和收斂精度,多峰值測(cè)試函數(shù)(f7～f12)用來測(cè)試算法探尋種群之外其他信息的能力(稱為勘探能力)和解決復(fù)雜優(yōu)化問題的能力.本節(jié)選取近年來新提出的BASFPA和IGPSO[20]兩種混合算法作為對(duì)比算法，其中BASFPA算法是天牛須搜索算法與花朵授粉算法的混合，該算法依靠天牛須搜索算法來加快花朵授粉算法的收斂速度，具有較好的收斂效果;IGPSO算法是遺傳算法與粒子群算法的混合，具有典型性.

表1 標(biāo)準(zhǔn)測(cè)試函數(shù)

Table 1 Standard test functions

函數(shù)名字搜索范圍最優(yōu)值f1.Sphere[-100,100]D0f2.Tablet[-100,100]D0f3.DeJong[-100,100]D0f4.Schwefel1.2[-100,100]D0f5.Easom[-10,10]D-1f6.Sumofdiff.power[-100,100]D0f7.Girewank[-600,600]D0f8.Ackley[-32,32]D0f9.Alpine[-10,10]D0f10.Giunta[-10,10]D0f11.Salomon[-100,100]D0f12.Noncont_Rastrigin[-5.12,5.12]D0

實(shí)驗(yàn)選取了3個(gè)指標(biāo)評(píng)價(jià)算法的性能：1)均值(Mean)，該指標(biāo)是算法多次運(yùn)行的最優(yōu)適應(yīng)度的均值，反應(yīng)求解質(zhì)量的好壞，均值越小，說明算法結(jié)果越好;2)標(biāo)準(zhǔn)差(Std)，該指標(biāo)是實(shí)際最優(yōu)值與均值之間的標(biāo)準(zhǔn)差，能夠反應(yīng)算法求解的穩(wěn)定性，Std越小，則算法的穩(wěn)定性越好;3)成功率(SR)，該指標(biāo)是函數(shù)被求解成功的次數(shù)占總執(zhí)行次數(shù)的比值，其中，函數(shù)求解成功是指求解結(jié)果優(yōu)于指定的求解精度(12個(gè)測(cè)試函數(shù)在不同維度下的求解精度標(biāo)準(zhǔn)在表2中均有設(shè)置).

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

為了公平起見，在算法參數(shù)設(shè)置上，BASFPA算法和IGPSO算法的參數(shù)與原文獻(xiàn)保持一致(種群規(guī)模N除外)，詳細(xì)參數(shù)可以參考相應(yīng)文獻(xiàn).三種算法都采用實(shí)數(shù)編碼，種群規(guī)模為60，運(yùn)行代數(shù)都為200代.本文提出的BASGA算法采用高斯變異[21]和保留最佳個(gè)體的選擇方法[22]，相關(guān)參數(shù)設(shè)定為：觸須感知方向數(shù)量n=5，排除概率pe=0.05，初始步長(zhǎng)δ=5，質(zhì)心到觸須距離初值l=0.5，A=10，pcmin=0.6，pcmax=0.9，pmmin=0.01，pmmax=0.1，ξ=10，ε=10-3.

實(shí)驗(yàn)將分為兩個(gè)部分進(jìn)行：一是單峰值函數(shù)的優(yōu)化，待求解問題的維度被設(shè)定為10維、30維和60維(除函數(shù)f5維度為2、5和10外).二是多峰值函數(shù)的優(yōu)化，將分別從5維、15維和30維進(jìn)行求解.所有測(cè)試在Windows10操作系統(tǒng)，MATLAB2016b仿真平臺(tái)上進(jìn)行.每種算法獨(dú)立運(yùn)行30次，記錄均值、方差和成功率.

表2 函數(shù)不同維度下的求解精度

Table 2 Solving accuracy of functions in different dimensions

函數(shù)維度D=10D=30D=60函數(shù)維度D=5D=15D=30f110-810-610-4f710-810-610-3f210-810-510-2f810-510-310-1f310-810-610-4f910-510-1100f410-810-410-1f1010-310-210-1f?510-5(D=2)10-2(D=5)10-1(D=10)f1110-210-1100f610-1010-710-4f1210-2100101

說明：因?yàn)楹瘮?shù)f5的數(shù)學(xué)特性導(dǎo)致最小值不容易求解，維度的增高會(huì)加大算法的求解難度，因此求解維度不宜過高，分別設(shè)置為2、5和10.

4.2.1 單峰值函數(shù)優(yōu)化下的性能分析

表3給出了3種算法對(duì)6個(gè)單峰測(cè)試函數(shù)的優(yōu)化結(jié)果對(duì)比.在收斂成功率上，BASFPA算法經(jīng)常出現(xiàn)SR為0的情況，說明了該算法的收斂能力是這三種混合算法中最差的.BASGA算法在整體上都有不錯(cuò)的收斂成功率，尤其是對(duì)函數(shù)f2特定10維和30維的優(yōu)化上，成功率相比其余兩個(gè)算法要高很多，說明該算法具有更強(qiáng)的收斂能力和尋優(yōu)能力.從均值的對(duì)比來看，BASGA算法整體上要好于其他兩種算法，而IGPSO算法要好于BASFPA算法.尤其是在對(duì)函數(shù)f3特定30維和60維的優(yōu)化上，BASGA算法的尋優(yōu)精度接近10-15，遠(yuǎn)遠(yuǎn)超過了其他兩種算法，特別地，函數(shù)f5的數(shù)學(xué)特性類似廣袤平原中的一口水井，解空間內(nèi)的域值相似度較高，會(huì)對(duì)算法尋優(yōu)造成方向上的干擾，從表3對(duì)該函數(shù)的優(yōu)化數(shù)據(jù)可以看出，三種算法在10維下都沒有尋找到最優(yōu)解，但是在2維的優(yōu)化中，BASGA算法尋找到了理論最優(yōu)值，而IGPSO和BASFPA算法雖然尋找到了函數(shù)域值的下降區(qū)域，但是并沒有繼續(xù)搜索下去，這也說明兩種算法的搜索能力較BASGA算法偏弱.

從表3標(biāo)準(zhǔn)差的對(duì)比中可以看出算法IGPSO的Std值與其對(duì)應(yīng)均值之間有相對(duì)明顯的差距，而BASGA算法和BASFPA算法的Std值與其對(duì)應(yīng)Mean值之間的差距相對(duì)較小.在對(duì)函數(shù)f2特定30維和60維的優(yōu)化中，IGPSO算法的Std值與其Mean值之間的差距尤其明顯，說明該算法每次運(yùn)行后的結(jié)果波動(dòng)較大，穩(wěn)定性較差.反觀BASGA算法的Std值與其均值之間的差距均保持在10-1個(gè)精度之內(nèi)，穩(wěn)定性要強(qiáng)于其余兩種算法.

為了更加直觀的反映算法的收斂速度，給出了函數(shù)f1～f12在特定維度下的收斂曲線對(duì)比圖.從圖6(a)-圖6(f)中可以看出，BASGA算法在單峰值函數(shù)優(yōu)化中相比于其余兩種算法具有更快的尋優(yōu)速度和更高的收斂精度，而BASFPA算法從整體上看表現(xiàn)最差，尤其是函數(shù)f5的收斂曲線，BASGA算法一開始就表現(xiàn)出了很好的收斂能力，在不足40代內(nèi)就達(dá)到了規(guī)定的求解精度，IGPSO算法雖然也達(dá)到了精度要求，但與前者算法相比收斂較為緩慢，而BASFPA算法在后期的表現(xiàn)最差.

表3 三種算法對(duì)測(cè)試函數(shù)f1～f6的尋優(yōu)結(jié)果比較

Table 3 Comparisons of three algorithms for optimizing test functionsf1～f6

函數(shù)維度BASFPAMeanStdSRIGPSOMeanStdSRBASGAMeanStdSRf1104.77E-056.90E-0602.29E-099.63E-0993%3.75E-138.12E-13100%303.36E-049.4059E-0405.76E-068.64E-0639%8.4394E-091.3214E-09100%605.39E-017.68E-0208.97E-067.81E-0696%3.29E-077.10E-07100%f2103.98E+012.54E+0001.16E-056.89E-058%8.20E-084.53E-0873%302.81E+033.49E+0202.49E-031.28E-033%1.23E-057.35E-0548%607.16E+038.41E+0201.91E-021.87E-0259%4.04E-021.41E-0255%f3101.44E-059.55E-0627%9.79E-163.85E-17100%2.57E-217.25E-22100%302.64E-014.43E-0204.64E-064.94E-0665%1.80E-141.31E-15100%607.29E+012.68E+0106.32E-018.15E-0204.53E-137.88E-13100%f4107.24E-044.16E-0402.46E-065.25E-0633%2.56E-096.54E-0971%302.94E-035.94E-0402.69E-016.26E-0202.43E-068.47E-06100%607.70E+017.81E+003%1.56E-023.57E-0261%1.03E-049.25E-04100%f521.00E-041.96E-0439%2.39E-147.49E-12100%0.00E+001.22E-14100%59.92E-018.01E-0209.91E-015.44E+0009.90E-016.88E-019%101.00E+009.01E-0101.00E+009.13E-0101.00E+007.43E-010f6101.64E-032.78E-0401.01E-077.28E-0810%5.37E-144.00E-15100%302.00E-035.50E-0307.40E-067.69E-0640%1.39E-121.27E-1294%601.74E+036.48E+0208.00E-049.14E-0487%7.80E-125.31E-13100%

4.2.2 多峰值函數(shù)優(yōu)化下的性能分析

表4是6個(gè)多峰函數(shù)的優(yōu)化結(jié)果，通過對(duì)比分析，在尋優(yōu)精度上，BASGA算法不論低維和高維都要好于其他兩種算法，尤其是在低維優(yōu)化中表現(xiàn)出了很好的尋優(yōu)性能.特別是在f8的優(yōu)化中，BASGA在15維下的均值精度是10-5，遠(yuǎn)遠(yuǎn)好于其余算法.在收斂成功率方面，三種算法都容易出現(xiàn)很高成功率和很低的成功率兩個(gè)極端，通過對(duì)函數(shù)f11結(jié)果的分析可知，當(dāng)維度為15和30時(shí)，BASGA算法的SR都是100%，其余算法的SR為0，說明BASGA算法在30次實(shí)驗(yàn)中每次都能跳出局部極值進(jìn)而收斂到規(guī)定的精度范圍之內(nèi)，而其余兩種算法因?yàn)橄萑刖植孔顑?yōu)解而無法達(dá)到規(guī)定的收斂精度.

從圖6(g)-圖6(l)可以看出，BASGA算法在多峰值問題求解中也有很好的搜索性能，根據(jù)函數(shù)f7的優(yōu)化曲線可知，IGPSO算法在60代之前其收斂曲線下降非?？?，但在60代之后曲線呈持平狀態(tài)，該算法的特點(diǎn)是前期有很好的收斂性能，但中后期容易陷入局部最優(yōu)值的僵局，反觀BASGA算法雖然前期下降緩慢，但中后期開始快速收斂，表明BASGA算法能夠保持良好的多樣性，在復(fù)雜的多峰問題中也有良好的尋優(yōu)能力.

表4 三種算法對(duì)測(cè)試函數(shù)f7～f8的尋優(yōu)結(jié)果比較

Table 4 Comparisons of three algorithms for optimizing test functionsf7～f8

函數(shù)維度BASFPAMeanStdSRIGPSOMeanStdSRBASGAMeanStdSR52.33E-028.67E-0302.72E-092.30E-0950%1.90E-135.94E-14100%f7151.27E-054.15E-0542%1.27E-054.15E-0542%1.66E-096.59E-09100%301.11E+013.15E+0001.53E+021.68E+0101.15E-094.61E-10100%52.16E-013.15E-0203.61E-062.65E-0653%1.21E-062.10E-0691%f8158.59E-019.12E-0106.23E+001.44E-0104.71E-054.75E-05100%302.52E+005.40E-0101.7E+015.41E+0001.36E-049.50E-04100%54.23E-036.79E-0404.50E-068.15E-0784%7.63E-088.35E-09100%f9153.03E-015.79E-0162%1.08E+018.30E+00100%1.30E-034.40E-04100%302.56E+008.88E-0140%2.99E+019.45E+0005.32E-024.15E-03100%56.16E-026.28E-0303.58E-026.60E-0310%1.17E-035.95E-0483%f10154.92E-015.23E-0108.31E-013.71E-0130%3.52E-032.86E-0388%308.94E-012.75E-0250%9.38E+008.59E-0107.58E-023.07E-0390%51.00E-013.04E-0156%1.11E-012.53E-0250%9.98E-023.03E-02100%f11151.11E+009.31E-0105.71E+003.79E-0109.93E-024.92E-03100%302.29E+009.14E-0101.57E+012.66E+0001.99E-014.87E-02100%52.22E+008.96E-0102.00E-071.33E-07100%1.11E-079.89E-08100%f12152.70E+011.88E+0104.85E+008.16E+0056%6.00E+009.21E-0179%307.99E+17.11E+0001.52E+024.01E+0101.30E+013.35E+0031%

圖6 三種算法的尋優(yōu)曲線對(duì)比

5 結(jié) 論

針對(duì)遺傳算法和天牛須搜索算法的優(yōu)缺點(diǎn)，本文從揚(yáng)長(zhǎng)避短的思想出發(fā)，率先提出了兩種算法混合的優(yōu)化算法(簡(jiǎn)稱BASGA算法)，該算法通過建立多向模型和反饋更新策略來提高算法的局部搜索能力和尋優(yōu)速度，本文還將交叉算子進(jìn)行了擴(kuò)展改進(jìn)，并動(dòng)態(tài)的改變交叉和變異參數(shù)值，使算法能夠在復(fù)雜的多峰問題中也具有較好的全局尋優(yōu)能力.函數(shù)優(yōu)化實(shí)驗(yàn)證明，BASGA算法能夠很好的克服天牛須搜索算法后期的陷入局部極值問題和遺傳算法收斂過慢的缺點(diǎn)，具有較好的處理單、多峰值優(yōu)化問題的能力.