天牛須遺傳雜交算法的研究與應(yīng)用

馮曉東，黃世榮，戴冠鷗，楊偉家，羅堯治

1.紹興文理學(xué)院 土木工程學(xué)院，浙江 紹興 312000

2.浙江大學(xué) 建筑與土木工程學(xué)院，杭州 310000

數(shù)學(xué)優(yōu)化在求解大多數(shù)工程優(yōu)化問(wèn)題時(shí)受限于其可應(yīng)用數(shù)學(xué)模型的苛刻條件，工程應(yīng)用日益復(fù)雜的需求促進(jìn)了隨機(jī)優(yōu)化類(lèi)方法的快速發(fā)展，特別是元啟發(fā)式算法（Meta-Heuristic Algorithms）這一類(lèi)從自然規(guī)律中獲取靈感，模仿運(yùn)行機(jī)制并完成自我學(xué)習(xí)的高效計(jì)算算法，具體有群智能算法（Swarm Intelligence，SI）、進(jìn)化算法（Evolutionary Algorithms，EA）等。EA中有一類(lèi)經(jīng)典的普適性優(yōu)化方法——遺傳算法（Genetic Algorithm，GA），其優(yōu)化結(jié)果通常獨(dú)立于問(wèn)題本身，因此普遍適用于工程領(lǐng)域。但與此同時(shí)，該算法無(wú)法充分利用問(wèn)題的特性加快其優(yōu)化效率；其優(yōu)化結(jié)果通常只是近似解，且需要通過(guò)適當(dāng)?shù)臉?gòu)造措施保證算法的收斂性，這也是元啟發(fā)式算法劣勢(shì)。

為克服元啟發(fā)式算法收斂性差、計(jì)算效率低等問(wèn)題，部分學(xué)者提出了基于各類(lèi)元啟發(fā)式算法的雜交算法并形成了許多有意義的研究成果。Juang[1]提出基于遺傳算法與粒子群算法（Particle Swarm Optimization，PSO）的雜交算法（Genetic Algorithm and Particle Swarm Optimization，GAPSO），其中PSO 變量通過(guò)群體交互和自我交互的方式提高解的質(zhì)量，GA 組織變量形成種群模擬優(yōu)勝劣汰和自然繁殖等現(xiàn)象提高求解效率，GAPSO的提出標(biāo)志著SI和EA雜交的開(kāi)始、個(gè)體和群體相互作用的開(kāi)始。李亞非[2]以物種的競(jìng)爭(zhēng)和協(xié)同進(jìn)化現(xiàn)象為指導(dǎo)思想設(shè)計(jì)了GAPSO，其中算法框架以協(xié)同進(jìn)化思想為指導(dǎo)決定了雜交算法中主次分屬，有助于理解雜交算法的組成結(jié)構(gòu)和作用。Ghamisi[3]提出的GAPSO，以側(cè)重并結(jié)合GA 的選擇作用來(lái)減少PSO 的無(wú)效計(jì)算量。Feng[4]提出的GAPSO，以PSO 為主體將GA 的交叉和變異算子作為增強(qiáng)局部搜索能力的手段，有效解決PSO早熟收斂問(wèn)題。此外，姜向遠(yuǎn)[5]和李帥[6]分別提出天牛須搜索算法（Beetle Antennae Search，BAS）并證明收斂與步長(zhǎng)有關(guān)，建立并初步完善BAS理論。周田江[7]提出結(jié)合模擬退火的雜交天牛須算法（Simulated Annealing and Adaptive Beetle Antennae Search Algorithm，SABAS），橫向?qū)Ρ攘送嘶鹚惴ê吞炫Ｈ核惴ú⒆C明SABAS在多維問(wèn)題上有較好的尋優(yōu)能力。陳婷婷[8]將PSO 與BAS雜交，加強(qiáng)個(gè)體探索作用的同時(shí)有效減輕PSO中個(gè)體對(duì)歷史最優(yōu)和局部最優(yōu)的依賴，在個(gè)體探索引導(dǎo)群體的方式上提供了新思路。上述雜交算法主要通過(guò)加強(qiáng)個(gè)體的探索，提升個(gè)體和群體之間的相互作用，從而解決原始算法局部搜索能力弱的問(wèn)題。但雜交過(guò)程中通常會(huì)引入新的參數(shù)，這在一定程度上增加了算法復(fù)雜度，從而使其應(yīng)用受限[9]。

BAS 與GA 的雜交可以在一定程度解決上述問(wèn)題。首先BAS 算法核心代碼僅4 行，便于改寫(xiě)和拓展。其次BAS對(duì)象為單一個(gè)體，作為輔助的進(jìn)化策略對(duì)GA整個(gè)框架影響較小并有助于保持自身獨(dú)立性。本文提出基于數(shù)據(jù)驅(qū)動(dòng)的天牛須遺傳雜交算法，針對(duì)BAS 特點(diǎn)改寫(xiě)成BA搜索算子以增強(qiáng)算法局部搜索能力；通過(guò)數(shù)據(jù)驅(qū)動(dòng)策略，利用歷代種群變量和相應(yīng)目標(biāo)函數(shù)變化的靈敏度映射得到啟發(fā)規(guī)則，達(dá)到區(qū)分變量并優(yōu)化進(jìn)化路徑，減少無(wú)效運(yùn)算量從而降低雜交算法復(fù)雜度。最后通過(guò)平面十桿桁架尺寸優(yōu)化算例，說(shuō)明本方法的有效性及穩(wěn)定性。

1 算法概述

1.1 遺傳算法（GA）

GA 通過(guò)選擇、交叉和變異三種遺傳算子實(shí)現(xiàn)算法收斂。選擇通過(guò)個(gè)體相互間競(jìng)爭(zhēng)逐漸逼近問(wèn)題的最優(yōu)解；交叉和變異歸為遺傳運(yùn)算，分別是GA 產(chǎn)生新個(gè)體的主要方法和產(chǎn)生新個(gè)體的次要途徑，其中變異影響GA的局部搜索能力和種群的多樣性。交叉和變異相互配合來(lái)模擬基因在繁殖創(chuàng)造新后代過(guò)程的作用，共同完成對(duì)解空間的全局搜索和局部搜索（圖1）。

圖1 交叉和變異算子示意圖Fig.1 Schematic diagram of crossover and mutation operators

僅采用選擇、交叉和變異三個(gè)遺傳算子的遺傳算法被稱為標(biāo)準(zhǔn)遺傳算法（Canonical Genetic Algorithm，CGA）。江濤[10]和馮愛(ài)蘭[11]等人改進(jìn)的遺傳算法采用精英選擇策略（圖2）分別解決路徑優(yōu)化問(wèn)題和訂單分配優(yōu)化問(wèn)題，并保證歷史最優(yōu)個(gè)體不會(huì)因選擇、交叉和變異操作而丟失或破壞，從而增強(qiáng)全局的收斂能力。自適應(yīng)遺傳算法（Adaptive Genetic Algorithm，AGA）中自適應(yīng)概率可以通過(guò)遺傳運(yùn)算使相應(yīng)馬爾科夫鏈過(guò)程變?yōu)榉驱R次，也是一種得到全局最優(yōu)的收斂途徑。

圖2 末尾淘汰的精英保留策略Fig.2 Elitist model

1.2 天牛須搜索算法（BAS）

圖3為BAS模型的簡(jiǎn)化，其仿生原理基于天牛的覓食行為：天牛使用兩個(gè)觸角來(lái)檢測(cè)空間中食物的氣味并決定其自身前進(jìn)方向從而逐漸向食物靠近。

圖3 天牛須搜索算法模型簡(jiǎn)化Fig.3 Simplified BAS model

其核心步驟如下：

（1）隨機(jī)生成方向向量并標(biāo)準(zhǔn)化。

其中，N是變量的空間維度，rands(?)是隨機(jī)函數(shù)。

（2）計(jì)算左右須的坐標(biāo)。

其中，xt為t時(shí)刻天牛的坐標(biāo)，dt是t時(shí)刻質(zhì)心到須的水平投影搜索距離。

（3）確定左右觸角的氣味強(qiáng)度，用f(xl)和f(xr)代替左右位置，f(x)是目標(biāo)函數(shù)。

（4）根據(jù)兩須對(duì)應(yīng)的氣味，決定天牛下一時(shí)刻移動(dòng)位置。

其中，δt為t時(shí)刻的步長(zhǎng)。

（5）搜索距離和步長(zhǎng)更新。

其中，d0代表人為設(shè)定的最小步長(zhǎng)，ηd和ηδ分別為搜索距離和步長(zhǎng)更新的衰減系數(shù)。

2 基于數(shù)據(jù)驅(qū)動(dòng)的天牛須遺傳雜交算法（BAGA）

鄭文萍等人[12]基于遺傳算法提出的蛋白質(zhì)復(fù)合物識(shí)別算法（Genetic Algorithm based Graph Clustering，GAGC）擴(kuò)大了圖聚類(lèi)算法的搜索空間，從而增強(qiáng)算法的局部搜索能力有助于提升算法的性能。本文針對(duì)AGA 精英選擇策略和擴(kuò)大采樣空間策略時(shí)，由于選擇壓力過(guò)大進(jìn)而全局搜索能力過(guò)強(qiáng)導(dǎo)致算法早熟且收斂效果差；因?yàn)榱P函數(shù)無(wú)法利用不可行解域等問(wèn)題提出一種局部搜索策略——天牛須搜索算子（Beetle Antennae Operator，BA）。BA利用精英個(gè)體從不可行解域得到優(yōu)良個(gè)體，通過(guò)擴(kuò)大解的搜索空間以增加算法的局部探索能力。

具體為可行解通過(guò)BA的局部改良從不可行解領(lǐng)域得到優(yōu)質(zhì)不可行解，再由修復(fù)算子修正成可行解重新進(jìn)入種群排序，自適應(yīng)精英選擇策略將會(huì)自動(dòng)選擇末尾淘汰個(gè)數(shù)以平衡算法增加的局部搜索能力。

2.1 天牛須搜索算子（BA）

BA 由BAS 改進(jìn)并主要考慮的對(duì)象為類(lèi)精英個(gè)體的優(yōu)良可行解，其在約束邊界附近對(duì)變異敏感極易違反約束成為不可行解，需要新的變異步長(zhǎng)策略和變異維度選擇策略。只改變變異率和交叉率的AGA，其變異步長(zhǎng)跨度不穩(wěn)定且變異對(duì)象隨機(jī)選擇，因此當(dāng)可行解搜索至不可行解附近時(shí)，由于外部施加的高壓極易成為不可行解而喪失被選擇進(jìn)入下一代迭代的機(jī)會(huì)。

針對(duì)AGA變異機(jī)理上最小步長(zhǎng)和變異對(duì)象選擇的應(yīng)用局限，雜交BA 后的天牛須遺傳雜交算法（Hybrid algorithm of Beetle Antennae and Genetic Algorithm，BAGA），有針對(duì)性加強(qiáng)了算法的局部探索能力。以下為執(zhí)行BA的三個(gè)基本假定：

假定1天牛自身的目標(biāo)函數(shù)值會(huì)影響到下一步前進(jìn)方向的決策選擇。

假定2天牛的左右須坐標(biāo)可以用兩個(gè)步驟深化得到。（1）左右探頭，如圖4（b）；（2）確定左右方向后，上下擺動(dòng)左右須探索解的復(fù)合影響，圖4（d）為探索后的效果示意圖。

假定3天牛在任意解空間中搜索時(shí)，有且僅有兩個(gè)方向和n根觸須，分別作為探索的次數(shù)和探索時(shí)變異的變量個(gè)數(shù)。先左（右）探頭確定方向再左右須來(lái)感知?dú)馕恫⒌玫阶螅ㄓ遥┓较虻臍馕吨?，反方向相同?/p>

各假定的具體解釋如下：

假定1 是對(duì)BAS 坐標(biāo)策略中缺少對(duì)照自身目標(biāo)函數(shù)值可能導(dǎo)致盲目前進(jìn)丟失自身歷史較優(yōu)解的改進(jìn)。在求最小值問(wèn)題時(shí)，式（4）改為式（11）可保證任意時(shí)刻f(xt+1)不大于f(xt)，賦予保持現(xiàn)有狀態(tài)選擇的可能性。

假定2 以天變量多維度變異來(lái)模擬天牛須上下擺動(dòng)搜索的耦合影響，體現(xiàn)在式中對(duì)步長(zhǎng)h的設(shè)定。以圖4（d）舉例：算法模型左探頭xl來(lái)闡明須的上下擺動(dòng)舉例：左須選擇變量xi后保持不動(dòng)，同時(shí)右須選擇非i變量探索變異。

圖4 二維天牛須搜索算子簡(jiǎn)化模型示意圖Fig.4 Simplified diagram of 2-dimensional BA model

假定3 是拓展多維BA（n≥2）以適應(yīng)不同的問(wèn)題需求的補(bǔ)充設(shè)定。n代表任意探頭方向上代表的矢量坐標(biāo)變量被挑選變異的變量總數(shù)，如圖4（d）所示，n=2代表xl左探頭方向的矢量坐標(biāo)被選中了兩個(gè)變量變異并用紅色標(biāo)記顯示。由于算法模型左右對(duì)稱{n|n=2knum,knum∈N*}，knum代表單側(cè)須的根數(shù)。

BA核心步驟如下：

（1）生成步長(zhǎng)

其中，e是單位變異步長(zhǎng)矩陣，hmin是研究問(wèn)題背景下變量的最小變異單位，n為天牛須的須數(shù)亦是BA 的維度；N是變量的維度，Δh是選擇變異維度矩陣。x是變量的集合[x1,x2,…,xN]，代表單一個(gè)體。ObjV=f(x)為種群中個(gè)體x對(duì)應(yīng)的目標(biāo)函數(shù)值，p函數(shù)輸入x和對(duì)應(yīng)ObjV可確定變量變異的維度。

（2）確定左右須坐標(biāo)

（3）確定下一步方向

針對(duì)一般問(wèn)題，BA 對(duì)局部搜索能力提升效果由步長(zhǎng)h和天牛須維度n決定。優(yōu)良個(gè)體極易違背約束的特性決定了h和n的取值原則：保證效率下分別取最小變異單位hmin和維度n的下限。hmin的下限一般由不同數(shù)學(xué)模型的定義域類(lèi)型決定。如桁架結(jié)構(gòu)尺寸優(yōu)化問(wèn)題中，離散變量可采用hmin=1，n=2；連續(xù)變量可采用變量的最小精度，無(wú)精度要求時(shí)可取定義域下限的1%～10%。

此外連續(xù)變量宜采用自適應(yīng)函數(shù)，由下限構(gòu)成主要取值并關(guān)聯(lián)代數(shù)gen和種群目標(biāo)函數(shù)標(biāo)準(zhǔn)差σ的迭代變化而變化。其中hmin和n（n≥2）隨著gen的變大、σ的變小分別影響hmin和n的下降速率。

值得一提在BA 流程圖（圖5）中，輸出對(duì)象的目標(biāo)函數(shù)fgen(x)始終小于等于輸入f1(x)，且輸出的目標(biāo)函數(shù)經(jīng)過(guò)自適應(yīng)罰函數(shù)處理。結(jié)合圖6 的天牛須算子改良個(gè)體示意圖所示有助于理解天牛須算子的主要特性：如何利用精英個(gè)體在不可行解域產(chǎn)生優(yōu)質(zhì)不可行解從而實(shí)現(xiàn)局部探索跳出局部解。

圖5 天牛須變異算子的流程和結(jié)果Fig.5 BA flowchart and output results

圖6 天牛須搜索算子原理示意圖Fig.6 Schematic diagram of BA

圖6（a）演示了優(yōu)良個(gè)體經(jīng)過(guò)天牛須局部改良分別為可行解和不可行解前后的變化情況。圖6（b）為綠色可行解個(gè)體經(jīng)過(guò)天牛須局部改良后，其目標(biāo)函數(shù)小于藍(lán)色優(yōu)秀個(gè)體且滿足約束成為下一代藍(lán)色優(yōu)良個(gè)體的簡(jiǎn)單演示；圖6（c）為紅色不可行解個(gè)體經(jīng)過(guò)天牛須局部改良后，不滿足約束但經(jīng)過(guò)自適應(yīng)罰函數(shù)處理其目標(biāo)函數(shù)仍小于藍(lán)色優(yōu)秀個(gè)體的簡(jiǎn)單演示。該紅色不可行解在不可行解域進(jìn)行局部探索后由修復(fù)算子修復(fù)成為下一代藍(lán)色優(yōu)良個(gè)體并進(jìn)入種群參與整體搜索。

這種以生物天牛為載體實(shí)現(xiàn)利用優(yōu)良個(gè)體主動(dòng)轉(zhuǎn)變到不可行解域探索得到優(yōu)質(zhì)不可行解的策略有不錯(cuò)的跳出極值能力，在3.3節(jié)中的補(bǔ)充實(shí)驗(yàn)中表現(xiàn)良好，有較高的收斂率可以說(shuō)明。

2.2 數(shù)據(jù)驅(qū)動(dòng)和啟發(fā)規(guī)則

Farzaneh[13]利用歷史數(shù)據(jù)驅(qū)動(dòng)進(jìn)化算法策略（Data-Driven Evolutionary Computation，DDEC），通過(guò)歷史數(shù)據(jù)與目標(biāo)函數(shù)通過(guò)擬合的方式得到個(gè)體對(duì)應(yīng)的目標(biāo)函數(shù)值，降低重復(fù)運(yùn)算的成本。BAGA與DDEC同樣是利用優(yōu)化問(wèn)題的歷史數(shù)據(jù)優(yōu)化減少運(yùn)算量，不同之處在于數(shù)據(jù)驅(qū)動(dòng)實(shí)現(xiàn)優(yōu)化的方法不同。BAGA 不依靠離線數(shù)據(jù)，算法持續(xù)運(yùn)行的同時(shí)以減少運(yùn)算對(duì)象的方式實(shí)現(xiàn)運(yùn)算量的優(yōu)化。

圖7為原理示意圖，根據(jù)數(shù)據(jù)驅(qū)動(dòng)策略以歷代數(shù)據(jù)和對(duì)應(yīng)目標(biāo)函數(shù)值作為輸入變量，通過(guò)編寫(xiě)的映射函數(shù)對(duì)變量進(jìn)行基于目標(biāo)函數(shù)值靈敏度分析的歸類(lèi)得到啟發(fā)規(guī)則，其元素為{0,1}，0代表低影響變量，1代表重要變量。根據(jù)啟發(fā)規(guī)則采取不同的進(jìn)化策略，進(jìn)而減少無(wú)關(guān)變量的無(wú)效變異。

圖7 歷史數(shù)據(jù)驅(qū)動(dòng)的基本原理Fig.7 Fundamentals of historical data-driven

具體為天牛須算子產(chǎn)生的不可行解進(jìn)入修復(fù)算子后，根據(jù)啟發(fā)規(guī)則對(duì)不同變量的分類(lèi)實(shí)現(xiàn)其進(jìn)化路徑的分類(lèi)，低影響變量將與定義域下限采用二分法梯度下降，降低其對(duì)目標(biāo)函數(shù)的影響；重要變量則維持原交叉變異進(jìn)化路徑。

此外，本文數(shù)據(jù)驅(qū)動(dòng)產(chǎn)生的啟發(fā)規(guī)則，其元素僅為{0,1}，足夠簡(jiǎn)潔且產(chǎn)生分類(lèi)的計(jì)算依據(jù)為算法迭代過(guò)程中產(chǎn)生的大量歷史數(shù)據(jù)，無(wú)外界信息的輸入。像遺傳算法會(huì)出現(xiàn)欺騙現(xiàn)象使種群陷于局部解成為早熟類(lèi)似，大數(shù)據(jù)中也有錯(cuò)誤的數(shù)據(jù)，但數(shù)據(jù)驅(qū)動(dòng)策略具有一定的魯棒性，可以根據(jù)啟發(fā)規(guī)則反饋到種群中得到的結(jié)果從而自行調(diào)整。

圖8 中啟發(fā)規(guī)則在50 代前后時(shí)編號(hào)為2 的變量權(quán)重被歸類(lèi)為1，經(jīng)過(guò)算法的迭代運(yùn)算最終在60代其權(quán)重重新回到了0 并穩(wěn)定到算法結(jié)束。這體現(xiàn)了數(shù)據(jù)驅(qū)動(dòng)策略具有一定的魯棒性。

圖8 具有一定魯棒性數(shù)據(jù)驅(qū)動(dòng)Fig.8 Schematic of data-driven strategy with degree of robustness

迭代過(guò)程中數(shù)據(jù)越多，數(shù)據(jù)驅(qū)動(dòng)樣本分類(lèi)更能歸類(lèi)出不同變量的重要性從而得到更加精確的啟發(fā)規(guī)則；啟發(fā)規(guī)則越準(zhǔn)確，越能體現(xiàn)變量對(duì)目標(biāo)函數(shù)的敏感性，得到正確的數(shù)據(jù)；正確的大數(shù)據(jù)加上數(shù)據(jù)驅(qū)動(dòng)策略，進(jìn)而實(shí)現(xiàn)數(shù)據(jù)鏈的加速閉環(huán)，結(jié)果就是數(shù)據(jù)越多，啟發(fā)規(guī)則越準(zhǔn)確。

下面給出了映射規(guī)則的偽代碼，是變量對(duì)結(jié)構(gòu)經(jīng)濟(jì)性靈敏度分類(lèi)實(shí)現(xiàn)的代碼依據(jù)。

平面十桁架尺寸優(yōu)化的映射規(guī)則偽代碼

本文的映射遞歸規(guī)則可以在各種結(jié)構(gòu)的尺寸優(yōu)化應(yīng)用背景下，針對(duì)經(jīng)濟(jì)性為目標(biāo)函數(shù)分類(lèi)得出不同類(lèi)型的結(jié)構(gòu)變量對(duì)目標(biāo)靈敏度分類(lèi)。

2.3 BAGA算法分析

BAGA通過(guò)天牛須算子加強(qiáng)局部搜索能力，利用歷史數(shù)據(jù)驅(qū)動(dòng)得到的敏感性規(guī)律（啟發(fā)規(guī)則）加以區(qū)分變量得到重要性分類(lèi)進(jìn)而優(yōu)化進(jìn)化路徑有助于降低算法雜交增加的計(jì)算量。圖9 給出了BAGA 的流程圖，2.1節(jié)的天牛須搜索算子和2.2節(jié)的數(shù)據(jù)驅(qū)動(dòng)策略在算法流程圖中依次對(duì)應(yīng)綠色標(biāo)注部分。

圖9 BAGA算法流程框架圖Fig.9 BAGA algorithm flowchart

設(shè)置對(duì)照組分別研究BAGA 中天牛須搜索算子和數(shù)據(jù)驅(qū)動(dòng)對(duì)于收斂和減少?gòu)?fù)雜度的作用，如圖10所示。對(duì)比BAGA和AGA在10桿優(yōu)化問(wèn)題下的性能表現(xiàn)，圖10（a）所示的AGA 曲線僅在算法前期30 代就局部收斂陷入局部解，BAGA 在20 代左右收斂于全局最優(yōu)解。BAGA不僅兼?zhèn)銩GA的全局搜算能力較高的優(yōu)點(diǎn)并改進(jìn)AGA高全局收斂能力但低局部搜索能力的問(wèn)題。

圖10 BAGA中各改進(jìn)部分對(duì)算法整體的影響示意圖Fig.10 Diagram of influence of each improved part in BAGA on whole algorithm

2.3.1 數(shù)據(jù)驅(qū)動(dòng)策略在算法中的具體作用

對(duì)比圖10（a）中有無(wú)啟發(fā)規(guī)則的BAGA 兩條曲線，可以發(fā)現(xiàn)無(wú)啟發(fā)規(guī)則的BAGA多運(yùn)算了40代并在60代左右收斂到全局最優(yōu)。同時(shí)圖10（b）中記錄了有無(wú)啟發(fā)規(guī)則的兩種BAGA算法隨機(jī)10次所得目標(biāo)函數(shù)值和計(jì)算量的關(guān)系，其中橫向柱狀圖對(duì)比了10 組具體收斂的次數(shù)（詳細(xì)數(shù)據(jù)見(jiàn)表1），曲線圖刻畫(huà)了2 個(gè)對(duì)照組獨(dú)立重復(fù)10次的平均目標(biāo)函數(shù)和對(duì)應(yīng)結(jié)構(gòu)分析次數(shù)的平均值，根據(jù)表1中數(shù)據(jù)可得有啟發(fā)規(guī)則的平均值為16 278.4次，無(wú)啟發(fā)規(guī)則的平均值為23 406.8 次，減少了7 128.4次，平均提高了43.8%的效率（7 128.4/16 278.4×100%）。

表1 2個(gè)對(duì)照組重復(fù)10次所得收斂時(shí)的結(jié)構(gòu)分析次數(shù)Table 1 Number of structural analyses obtained when two controls are repeated for 10 times

本文不同于DDEC使用離線數(shù)據(jù)進(jìn)行評(píng)估[14]，提出的數(shù)據(jù)驅(qū)動(dòng)策略不對(duì)數(shù)據(jù)和目標(biāo)函數(shù)的關(guān)系進(jìn)行擬合，而是通過(guò)甄別數(shù)據(jù)和目標(biāo)函數(shù)之間的靈敏度，以啟發(fā)規(guī)則的方式賦予數(shù)據(jù)可以定義和區(qū)分的優(yōu)化價(jià)值，從而減少運(yùn)算復(fù)雜度。

2.3.2 天牛須搜索在算法中的具體作用

控制變量發(fā)現(xiàn)數(shù)據(jù)驅(qū)動(dòng)策略對(duì)收斂到全局最優(yōu)解并無(wú)影響，相反圖10（a）中無(wú)天牛須的BAGA 曲線直到算法結(jié)束仍然無(wú)法收斂到全局最優(yōu)解。做定量實(shí)驗(yàn)，擴(kuò)大樣本驗(yàn)證天牛須對(duì)于算法收斂是否起到關(guān)鍵作用。100 次重復(fù)實(shí)驗(yàn)得到BAGA 最優(yōu)解為2 490.56 kg，平均值為2 490.72 kg，標(biāo)準(zhǔn)差為2.61，收斂率為99%；1 000次重復(fù)實(shí)驗(yàn)最優(yōu)解為2 490.56 kg，平均值為2 491.43 kg，標(biāo)準(zhǔn)差為8.05，收斂率為98%；但AGA 重復(fù)實(shí)驗(yàn)1 000次都沒(méi)有收斂，在補(bǔ)充實(shí)驗(yàn)中設(shè)置循環(huán)代數(shù)為10 000代，可得到AGA最終收斂。圖10（a）中沒(méi)有BA的AGA曲線和重復(fù)實(shí)驗(yàn)分別說(shuō)明BA對(duì)局部尋優(yōu)有提升作用并有98%的收斂率驗(yàn)證BA的穩(wěn)定性。

圖9的BAGA種群更新迭代后，種群優(yōu)良個(gè)體通過(guò)BA 在不可行解域產(chǎn)生“非支配”的不可行解，改善GA的局部搜索能力；不可行解利用修復(fù)算子回到種群中參與下一代的排序和選擇；最后通過(guò)自適應(yīng)精英算子控制的整體改良擴(kuò)散其影響并作用到種群，可以適當(dāng)削弱或增強(qiáng)局部搜索帶給種群的影響從而平衡全局搜索能力。

自適應(yīng)精英策略以邏輯判斷的方式比較目標(biāo)函數(shù)值自適應(yīng)調(diào)整末尾淘汰的范圍，放大或減少BA對(duì)種群的影響，從而平衡局部搜索和全局搜索能力，以兩者較高且平衡的方式提高綜合搜索效率。圖11為定量實(shí)驗(yàn)中種群個(gè)體收斂歷史演變情況，迭代過(guò)程中種群個(gè)體根據(jù)目標(biāo)函數(shù)值分布可以簡(jiǎn)單分為3類(lèi)，A區(qū)為收斂個(gè)體，C 區(qū)為收斂前的種群個(gè)體，B 區(qū)為天牛須搜索設(shè)定范圍的個(gè)體。

如果不平衡局部搜索能力和全局搜索能力，任由局部搜索能力增加將會(huì)如圖11（a）所示。圖11（a）中種群個(gè)體收斂全局最優(yōu)解，但其B區(qū)因?yàn)樘炫Ｋ阉魉阕訉?dǎo)致局部搜索能力強(qiáng)于全局搜索能力，過(guò)多的局部解增加了種群多樣性但種群整體無(wú)法正常收斂，在數(shù)據(jù)上具體表現(xiàn)為種群目標(biāo)函數(shù)標(biāo)準(zhǔn)差不為0。通過(guò)擴(kuò)大末尾淘汰范圍并采取邏輯判斷的方式自適應(yīng)調(diào)整BA作用個(gè)體進(jìn)而擴(kuò)散到種群的影響，如圖11（b）中的B區(qū)所示，個(gè)體編號(hào)1～10的個(gè)體和種群全部個(gè)體收斂于全局最優(yōu)解從而種群收斂。

圖11 局部和全局搜索能力對(duì)個(gè)體目標(biāo)函數(shù)分布影響示意圖Fig.11 Graph of local and global search capability on individual objective function distribution

圖11（c）為100次獨(dú)立重復(fù)中唯一一次不收斂的情況，屬于高壓選擇下有較高的全局搜索能力和局部搜索能力，但仍在指定代數(shù)下無(wú)法跳出局部解，BA的作用說(shuō)明可以在圖中較好體現(xiàn)。B 區(qū)整體目標(biāo)函數(shù)分布呈現(xiàn)類(lèi)梯形，其區(qū)域內(nèi)的個(gè)體向局部最優(yōu)解方向2 498.28 kg下降，直角腰為C 區(qū)與B 區(qū)的分界線，代表精英個(gè)體在23代搜索到局部最優(yōu)解；綠色斜腰為A區(qū)與B區(qū)的分界線，代表種群編號(hào)為10～40的個(gè)體逐漸從末尾編號(hào)40開(kāi)始向首項(xiàng)編號(hào)前10 個(gè)體靠近收斂的狀態(tài)，但由于天牛須搜索算子的緣故，個(gè)體編號(hào)為1～10 范圍內(nèi)的個(gè)體圍繞著局部最優(yōu)解在開(kāi)發(fā)尋找全局最優(yōu)解，導(dǎo)致編號(hào)前10的種群目標(biāo)函數(shù)分布在大于局部最優(yōu)解，該現(xiàn)象在圖11（a）的B區(qū)中表現(xiàn)更為明顯。

3 算例分析

設(shè)定BAGA在種群大小為NIND，記錄每次獨(dú)立實(shí)驗(yàn)迭代100代停止時(shí)的種群目標(biāo)函數(shù)，再重復(fù)獨(dú)立實(shí)驗(yàn)text_num次可用矩陣OBJVtext_num×NIND表示，行代表實(shí)驗(yàn)次數(shù)，列代表個(gè)體編號(hào)，text_num取值1 000，NIND取值40，共40 000 個(gè)數(shù)據(jù)作為數(shù)據(jù)樣本研究算法的性能，分別計(jì)算平均值--------ObjV，標(biāo)準(zhǔn)差σ和成功率P。此外min_ObjV定義為OBJV每行中的最小值。計(jì)算公式依次為：

其中，STDEV.P(?)為EXCEL 軟件中求總體標(biāo)準(zhǔn)差函數(shù)。對(duì)min_OBJV進(jìn)行邏輯判斷是否等于指定函數(shù)值賦值元素0和1，可得列向量p，1代表算法找到最優(yōu)解，0 代表算法陷入局部解，沒(méi)有找到最優(yōu)解。min(?) 為MATLAB中求最小值函數(shù)，[]代表空。

3.1 目標(biāo)函數(shù)和罰函數(shù)

在滿足約束的條件下，尺寸優(yōu)化經(jīng)濟(jì)最佳效益方案的設(shè)計(jì)目標(biāo)函數(shù)往往與結(jié)構(gòu)自重有關(guān)，在桁架結(jié)構(gòu)的尺寸優(yōu)化中通常將構(gòu)件的截面面積作為設(shè)計(jì)變量，以結(jié)構(gòu)質(zhì)量最輕為目標(biāo)建立目標(biāo)函數(shù)，尋求一組截面積使結(jié)構(gòu)的重量最輕且滿足約束條件（應(yīng)力、位移等），屬于單目標(biāo)優(yōu)化問(wèn)題。通常，每個(gè)設(shè)計(jì)變量都是從基于生產(chǎn)標(biāo)準(zhǔn)的離散截面列表中選擇的，離散變量桁架結(jié)構(gòu)優(yōu)化模型如公式（15）所示：

其中，ObjV(X)是目標(biāo)函數(shù)，由結(jié)構(gòu)自重f(X)和罰函數(shù)g(X)組成，X是設(shè)計(jì)變量面積。N是變量的空間維度，ρi是第i根桿件材料的密度，Ai是第i根桿件的橫截面面積，li是第i根桿件的長(zhǎng)度；M為節(jié)點(diǎn)的編號(hào)，是應(yīng)力約束，k是荷載態(tài)，nk是荷載態(tài)的總組數(shù)，σik是第i根桿件在第k組荷載態(tài)下的應(yīng)力，[σi] 是第i根桿件最大的允許拉壓應(yīng)力；是第j根桿件在第k組荷載下l方向的位移約束，ujlk是第j根桿件在第k組荷載下l方向的位移，[ujl]是第j根桿件在l方向的最大允許位移，ND為桿件的自由度。S是橫截面面積變量的定義域，sn是S的變量維度。

3.2 平面十桿桁架尺寸優(yōu)化

圖12給出了一個(gè)平面十桿桁架的結(jié)構(gòu)示意圖，該結(jié)構(gòu)包含10個(gè)桿件和6個(gè)節(jié)點(diǎn)。彈性模量和密度分別E=68 947.57 MPa(107psi)，ρ=2.7×103kg/m3(0.1 lb/in3) 。節(jié)點(diǎn)5和節(jié)點(diǎn)6施加豎向荷載P=444.8 kN(100 kpsi)；每個(gè)節(jié)點(diǎn)允許豎向位移和橫向位移為±50.8 mm(±2 in)；以各桿件的橫截面積(mm2)為設(shè)計(jì)變量，設(shè)計(jì)變量的定義域S=[1.62，1.80，1.99，2.13，2.38，2.62，2.63，2.88，2.93，3.09，3.13，3.38，3.47，3.55，3.63，3.84，3.87，3.88，4.18，4.22，4.49，4.59，4.80，4.97，5.12，5.74，7.22，7.97，11.5，13.5，13.9，14.2，15.5，16.0，16.9，18.8，19.9，22.0，22.9，26.5，30.0，33.5]×645，(1in2=645 mm2)；每根桿件的允許應(yīng)力為±172.37 MPa(±25 000 psi)。

圖12 平面十桿桁架模型Fig.12 Plane 10-bar truss model

表2 中列出了不同元啟發(fā)式算法對(duì)桁架10 桿模型尺寸優(yōu)化100代后得到結(jié)果。由表2可知本文BAGA優(yōu)化結(jié)果桁架總用鋼量為2 490.56 kg，與前人研究結(jié)果相同，證明了算法的可行性及準(zhǔn)確性。值得一提的是，除AGA（參數(shù)見(jiàn)表3）以外的其他元啟發(fā)式算法皆在指定100運(yùn)行代內(nèi)獲得了最優(yōu)尺寸方案，但BAGA在穩(wěn)定性和成功率方面有更好的表現(xiàn)。對(duì)比TLBO和ACO的標(biāo)準(zhǔn)差，BAGA 的標(biāo)準(zhǔn)差為8.05，在1 000 次獨(dú)立重復(fù)實(shí)驗(yàn)，98%的概率成功收斂至最優(yōu)解。

表2 桁架模型尺寸優(yōu)化結(jié)果和對(duì)比Table 2 Results and comparison for truss model size optimization

表3 本文算例中AGA自適應(yīng)參數(shù)設(shè)置Table 3 Adaptive parameter setting for AGA

圖13 所示為BAGA 和AGA 對(duì)平面十桿桁架模型尺寸優(yōu)化的收斂歷史曲線和種群目標(biāo)函數(shù)歷代分布圖，共迭代100代以目標(biāo)函數(shù)（結(jié)構(gòu)自重+罰函數(shù)）為追蹤對(duì)象，從1 000 次定量實(shí)驗(yàn)中隨機(jī)選取一組具有代表性的數(shù)據(jù)做收斂過(guò)程中的定性分析。結(jié)果表明：AGA 無(wú)法在指定代數(shù)內(nèi)有效收斂且陷入局部最優(yōu)解。BAGA 運(yùn)行至15 代左右時(shí)精英個(gè)體找到最優(yōu)解，種群目標(biāo)函數(shù)平均值在20代收斂到全局最優(yōu)解附近，并在30代σ為0完成收斂。在后續(xù)實(shí)驗(yàn)中，設(shè)置最大迭代次數(shù)為10 000，AGA收斂。

圖13（a）中AGA 前期10 代目標(biāo)函數(shù)值呈階梯狀下降，表明AGA的自適應(yīng)算子對(duì)局部搜索有提升作用。但在10代至60代目標(biāo)函數(shù)值在較長(zhǎng)時(shí)間變化緩慢，直至50代左右出現(xiàn)新的波動(dòng)且隨后再次陷入局部解，如圖13（a）的子圖中所示。相比AGA，圖13（b）中BAGA在15代左右尋到最優(yōu)解，種群個(gè)體的平均值在20代靠近最優(yōu)解。

AGA 中期陷入局部解較長(zhǎng)時(shí)間，期間有兩次階梯狀下降但間隔時(shí)間較長(zhǎng)。同時(shí)圖13（b）中罰函數(shù)隨著種群逐漸滿足約束條件而迅速歸零，AGA 從13 代開(kāi)始便無(wú)法有效利用不可行解。以上現(xiàn)象表明自適應(yīng)算子在中期尋優(yōu)效率不高，更主要在高選擇壓力下基因操作得到優(yōu)質(zhì)不可行解通過(guò)罰函數(shù)加權(quán)無(wú)法與可行解競(jìng)爭(zhēng)，另一方面，自適應(yīng)變異和重組只能從當(dāng)前可行解尋優(yōu)，搜索空間變小一方面降低了局部尋優(yōu)能力。自適應(yīng)無(wú)法滿足需求、高選擇壓力、解的空間縮減三方面削弱了局部搜索能力，最終解在中后期陷于局部解并無(wú)法收斂。

圖13 BAGA和GA典型收斂歷史曲線比較Fig.13 Comparison of typical convergence history curves of BAGA and GA

同樣是罰函數(shù)，BAGA 的罰函數(shù)項(xiàng)在11 代歸零失去導(dǎo)向作用，但圖13（c）中由40個(gè)個(gè)體組成的種群目標(biāo)函數(shù)值在有效下降，并最終在30 代完成全部收斂。圖13（c）可以簡(jiǎn)單分為三區(qū)：30代之后，種群收斂并呈現(xiàn)出較大區(qū)域的平穩(wěn)，定義為A 區(qū)；15 代之前，定義為C 區(qū)；算法找到最優(yōu)解后的15～30 代之間，定義為B 區(qū)，因?yàn)榫€(gè)體找到最優(yōu)解，迅速反饋到整個(gè)種群中，B 區(qū)表現(xiàn)為隨著迭代代數(shù)增加種群目標(biāo)函數(shù)平均值有較大幅度的下降趨勢(shì)。

本文算例中啟發(fā)規(guī)則通過(guò)區(qū)分變量并采用不同的進(jìn)化策略可以減少運(yùn)算量、加速算法收斂。圖14（a）展示了迭代過(guò)程中的啟發(fā)規(guī)則變化情況，僅利用前20 代歷史數(shù)據(jù)并保持穩(wěn)定為[1 0 1 1 0 0 1 1 0]，體現(xiàn)了映射規(guī)則的偽代碼中數(shù)據(jù)驅(qū)動(dòng)代碼的高效性；編號(hào)為2、5、6、10的個(gè)體對(duì)目標(biāo)函數(shù)的歷史敏感性分類(lèi)屬性波動(dòng)更替，最終在20 代全部確定為0，也證明了本文數(shù)據(jù)驅(qū)動(dòng)策略具有一定的魯棒性。

此外，啟發(fā)規(guī)則對(duì)桿件分類(lèi)的結(jié)果吻合拓?fù)鋬?yōu)化在相同荷載條件下的主要傳力路徑關(guān)，符合一定的工程經(jīng)驗(yàn)。圖14（b）、（c）依次為線寬代表?xiàng)U件尺寸的尺寸優(yōu)化和以灰度代表變密度大小的拓?fù)鋬?yōu)化，圖14（c）采用變密度法[18]以過(guò)濾灰度為0.5作圖，對(duì)比圖14（b）可見(jiàn)變密度法所得傳力路徑與啟發(fā)規(guī)則分類(lèi)變量重要性的尺寸優(yōu)化結(jié)果無(wú)較大出入，證明了啟發(fā)規(guī)則分類(lèi)桿件的正確性，具有一定的物理意義。

圖14 算法優(yōu)化結(jié)果與拓?fù)鋬?yōu)化的傳力路徑對(duì)應(yīng)Fig.14 Optimization results of algorithm correspond to transmission path of topology optimization

啟發(fā)規(guī)則不是算法收斂的必要條件，它是隨機(jī)優(yōu)化在歷代數(shù)據(jù)內(nèi)歸納總結(jié)的有序優(yōu)化方或物理規(guī)律，有助于通過(guò)減少運(yùn)算量的方式提高計(jì)算效率。BA算子從優(yōu)秀個(gè)體出發(fā)開(kāi)發(fā)不可行解域得到優(yōu)秀不可行解的方式主導(dǎo)并加強(qiáng)了局部搜索能力，通過(guò)保證解的多樣性才是確保全局收斂的有效措施[19]。

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

強(qiáng)化個(gè)體的探索引導(dǎo)種群，通過(guò)BA 對(duì)個(gè)體的開(kāi)發(fā)彌補(bǔ)GA個(gè)體探索的空白，提出了BAGA增強(qiáng)高壓選擇下算法的局部搜索能力。針對(duì)變量對(duì)目標(biāo)函數(shù)的靈敏度分類(lèi)，基于數(shù)據(jù)驅(qū)動(dòng)改進(jìn)后的BAGA 減少了算法雜交后的復(fù)雜度，數(shù)值模擬實(shí)驗(yàn)對(duì)比可得BAGA 具有可行性和準(zhǔn)確性，相比于現(xiàn)有的元啟發(fā)式算法具有更好的穩(wěn)定性。

BA算子本身以個(gè)體探索為方式便于移植到其他算法是競(jìng)爭(zhēng)和合作協(xié)作進(jìn)化的新算子。可以通過(guò)修改天牛搜索算子中的參數(shù)增加個(gè)體和群體的相互作用，將其拓展到更為復(fù)雜的應(yīng)用背景，為其他算法在不同優(yōu)化階段增強(qiáng)其導(dǎo)向作用和局部搜索能力。

數(shù)據(jù)驅(qū)動(dòng)策略對(duì)不同變量基于目標(biāo)函數(shù)的靈敏度分析，可得到啟發(fā)規(guī)則并根據(jù)對(duì)應(yīng)進(jìn)化策略的權(quán)重優(yōu)化變量的進(jìn)化路徑，降低雜交算法增加的運(yùn)算量。數(shù)據(jù)驅(qū)動(dòng)下的靈敏度啟發(fā)規(guī)則，其原理不依賴于具體的問(wèn)題，可適用于求解其他工程問(wèn)題，具有較強(qiáng)的可移植性。此外變量的分類(lèi)亦可增強(qiáng)算法的導(dǎo)向作用，提高計(jì)算的運(yùn)行效率和穩(wěn)定性。