改進人工蜂群算法及其在工程設計中的應用

李 波,宋婧媛,張邦成

(長春工程學院 a.計算機技術與工程學院; b.吉林應急管理學院; c.機電工程學院,長春 130012)

0 引 言

工程設計問題通常需要在一組嚴格的規范約束下和在相互沖突的優化目標(例如:項目的成本和產品的穩健性,或產品的重量和產品的尺寸)之間做出妥協。因此工程中的設計問題可以被建模為受約束的多目標優化問題(CMOP:Constraint Multi-Objective Problem)[1]。

雖然工程設計問題與一般的CMOP具有相同的數學形式,但在實際應用中,工程設計問題的目標函數和約束通常具有較高的計算代價,即目標函數的計算過程需要消耗較多的時間和計算資源。由于很多工程設計問題的目標函數是不連續的,并且有些問題的目標函數缺少先驗知識,難以通過仿真對其進行建模,往往只能把目標函數作為黑盒進行優化,這極大地增加了優化問題的難度。因此,需要設計準確且高效的優化算法對問題進行優化。

近年來,群智能優化算法在智能優化領域取得了很大突破,對多目標優化和受約束的優化問題都具有較好的求解性能[2]。群智能優化算法包括蟻群算法(ACO:Ant Colony Optimization)、粒子群優化算法(PSO:Particle Swarm Optimization)、ABC(Artificial Bee Colony)算法等。其中AOC算法是受自然界中螞蟻搜索食物行為的啟發,其基于對自然界真實蟻群的集體覓食行為的研究,模擬真實的蟻群協作過程,在求解性能上具有很強的魯棒性和搜索較好解的能力。但AOC算法計算量大,求解所需的時間長,收斂速度慢,易陷入局部最優[3]。PSO算法具有相當快的逼近最優解的速度,可有效地對系統的參數進行優化,其優勢在于求解一些連續函數的優化問題。但PSO算法容易產生早熟收斂、局部尋優能力較差等問題[4]。ABC算法自提出便受到研究者的廣泛關注,目前ABC算法及其變種算法已被應用于單目標、多目標以及有約束優化問題的求解,且已在不同的應用領域中證明了其有效性。因為ABC具有多樣的搜索策略,能在優化過程中根據算法的歷史搜索情況靈活地對算法的搜索策略進行調整,所以ABC具有較高的求解精度,且算法的穩定性和健壯性較高,特別適用于較為復雜的優化問題[5]。

ABC算法源于對蜂群內部分工機制及其覓食行為的模擬。產生智能行為的蜂群覓食模型主要由食物源、受雇傭的覓食者、非受雇傭的覓食者以及針對食物源的招募行為、放棄食物源的行為構成。該算法也被用于求解各種多目標優化問題,但ABC算法在處理這類問題時存在收斂速度慢、種群盲目搜索以及算法開發能力有限等不足[6]。在多目標優化中,優化目標之間往往存在一定的聯系。在實際應用中優化目標之間通常是互相沖突的,在對一個優化目標進行優化時,解在其他目標上的質量往往會下降,即多目標優化問題(MOP:Multi-Objective Problem)中的優化目標很難被同時優化[7]。在使用ABC算法求解MOP問題時,往往無法找出一個MOP的最優解。

因此,筆者在ABC算法基礎上引入了群智能優化和進化優化中常見的交叉、變異算子,結合算法的基本原理提出了一種基于支配和分解的多目標ABC算法,稱為MOABC/DD(Multi-Objective Artificial Bee Colony based on Dominance and Decomposition)。MOABC/DD借鑒了群智能優化和進化優化中常見的交叉、變異算子,通過交叉和變異算子兩個步驟后生成一個新候選解。為保證候選解的多樣性,設計了一種基于分解的多目標優化策略,該策略采用在目標空間中均勻分布的一組權重向量,將MOP分解為若干個標量子問題。同時每個權重向量取與其距離最近的T個權重向量作為其鄰居(neighbor)。在基于分解的搜索過程中,每個權重向量對應一個子問題,每個子問題會選擇自己的最優解[8]。因此算法設計了基于鄰居的交叉和變異策略,從而使其有針對性地進行搜索,提高了可行解的質量[6]。

1 相關知識

ABC算法包含3個搜索階段,即3種不同類型的搜索策略,分別為雇傭蜂、觀察蜂和偵察蜂搜索[9]。算法模擬蜂群尋找蜜源并采蜜的過程將蜜蜂分為不同的工種,所有工種共同的目標為找到優質蜜源。在ABC算法中,不同搜索策略的目標均為搜索到優質解,將候選解(對應蜜源)稱為食物源。

為更好地理解超多目標優化問題及Pareto支配的思想,需要明確以下概念。

定義1(帕累托支配關系(Pareto dominance relationship)) 當且僅當?ft(xi)≤ft(xj),且?ft(xi)

定義2(非支配個體(non-dominated individual)) 個體xi是種群中的非支配個體,當且僅當不存在任何個體xj,滿足xj支配xi。

定義3(Pareto最優解集(PS:Pareto Set)) 超多目標優化算法中,不被任何候選解所支配的個體稱為非支配解,它們所構成的集合稱為Pareto最優解集。

定義4(Pareto前沿(PF:Pareto Front)) Pareto前沿是由理論上優化問題的最優解集合擬合而成的目標空間中的一個超平面。在實驗研究中,通常使用已知的非支配解的集合代表問題的Pareto前沿。

圖1對已有的多目標優化策略進行了分類,并給出了典型算法名稱。已有的多目標優化算法根據其優化策略可分為基于分解、支配和指標的3種多目標優化算法[10]。其中基于分解和支配的多目標優化策略是多目標優化當中常見的2種優化策略。

圖1 已有多目標優化算法分類

基于分解的多目標優化策略將MOP分解為能覆蓋目標空間的多個單目標子問題,并對子問題進行并行且獨立的求解; 算法用所有子問題的最優解對PF進行擬合。通常,基于分解的優化策略利用一組指向目標空間不同方向且分布均勻的向量對問題進行分解,這組向量通常被稱作權重向量(weight vector)或參考向量(reference vector)。這些向量將目標空間分解為若干個子區域。算法可以令每個權重向量對應一個標量子問題,這樣MOP就被分解為了若干個單目標問題。每個子問題的最優解都可以用于表示PF的一部分。算法用所有子問題的最優解構成PS,對問題的PF進行擬合。由于權重向量的分布是均勻的,所以這類算法能較好地擬合PF的形狀。采用基于分解的求解策略時,算法只需計算各個候選解在每個子問題上的適應度,時間開銷能得到較好控制,因此基于分解的基于指標的多目標進化算法(MaOEA)具有較高的優化效率。

基于支配的多目標優化的基本思路為利用帕累托支配規則對候選解進行選擇,從而選取優質解啟發算法的后續優化。最常見的基于支配的選擇方法為,首先選取候選解中的非支配解,再選擇剩余候選解中的較優解,直至選取到足夠的候選解為止?；谥涞乃惴ㄍㄟ^借助帕累托規則能妥善處理進行多目標優化時面臨的失去選擇壓力的問題。采用基于支配的思路處理多目標優化問題時需要注意的是,有時會出現選擇的解不足以填充種群或其數量超出種群規模的問題。在這種情況下,很多基于支配的多目標優化策略針對算法演進過程中喪失選擇壓力的問題引入了額外的候選解評價機制,使算法在種群的每一子代都能選取高質量的個體構成新的種群[11]。

2 改進的人工蜂群算法

2.1 算法框架

筆者提出了一種改進的多目標ABC算法(MOABC/DD),用于求解CMOP。該算法結合了多目標優化中常見的基于分解的多目標優化策略和基于支配的多目標優化策略,從而在促進算法收斂和維持解的多樣性之間達到平衡,使算法在具有較高的求解效率的同時能產生對問題的PF擬合效果較好的非支配解集。

算法1描述了MOABC/DD的算法框架,算法在初始化階段,隨機初始化N個隨機食物源,同時初始化一組權重向量λ={λ1,λ2,…,λN},并根據各優化目標對應的目標函數對食物源進行評價。算法交替執行雇傭蜂搜索和觀察蜂搜索,并根據特定條件執行偵察蜂搜索,通過重復執行不同類型的搜索行為,不斷提高解的質量[12]。最終在算法達到終止條件時,終止執行搜索并輸出其搜索到的非支配可行解。MOABC/DD算法提出了基于分解的雇傭蜂、基于支配的觀察蜂和基于優化進程的偵察蜂3種搜索策略[13]。通過3種不同類型的搜索策略,MOABC/DD兼顧算法的收斂性能和解的多樣性,并保證得到CMOP的可行解。

算法1 MOABC/DD算法框架。

輸入:搜索空間Ω;

輸出:非支配解;

1) 初始化N為隨機食物源;

2) 初始化權重向量λ={λ1,λ2,…,λN};

3) 根據權向量λ生成子問題;

4) 評價食物來源的客觀價值;

5) While終止條件不滿足do:

6) 執行蜂蜜搜索;

7) 執行旁觀者蜂搜索;

8) for每個子問題do:

9) if如果沒有更新k次迭代then:

10) 執行偵察蜂搜索行為;

11) end

12) end

13) 更新NA;

14) end

15) 輸出非支配可行解。

2.2 新候選解生成策略

ABC的基本思想為通過模擬蜜蜂采蜜的行為對搜索空間進行搜索。蜜蜂的搜索即產生新候選解的過程。ABC需要算法不斷生成新候選解,通過將新生成的候選解與舊候選解進行比較淘汰劣質候選解,從而促進算法向候選解的質量提高的方向收斂,最終搜索到問題的最優解或近似最優解[14]。MOABC/DD借鑒了群智能優化和進化優化中常見的交叉、變異算子,通過交叉和變異算子兩個步驟后生成一個新候選解。為保證候選解的多樣性,筆者設計了一種基于分解的多目標優化策略,該策略采用在目標空間中均勻分布的一組權重向量,將MOP分解為若干個標量子問題。同時每個權重向量取與其距離最近的T個權重向量作為其鄰居(neighbor)。在基于分解的搜索過程中,每個權重向量對應一個子問題,每個子問題會選擇自己的最優解[15]。因此算法設計了基于鄰居的交叉和變異策略。其中變異算子為

ui=xr1+F(xr2-xr3),

(1)

其中ui為第i個權重向量對應的交叉算子產出解,xr1、xr2、xr3分別為從第i個權重向量和其鄰居權重向量對應的子問題最優解中隨機選擇出的3個個體,F為交叉因子,用于控制交叉算子產生的新解的個體在搜索空間中可能存在的范圍。

在通過變異算子得到ui后,算法進一步通過變異算子對其進行修改,并得到一個新的候選解vi。該變異算子為

(2)

其中vi,j為新候選解vi的第j個維度,rand(0,1)為產生0～1之間隨機實數的隨機數函數,但服從均勻分布,cr為交叉概率,xi,j為第i個權重向量對應的原最優解xi的第j個維度。

2.3 基于分解的雇傭蜂搜索策略

算法2描述了MOABC/DD中基于分解的雇傭蜂搜索策略。雇傭蜂搜索階段通過進行基于分解的多目標優化能保證解在目標空間中的分布較為均勻,即具有較好的解的多樣性[16]。維持解的多樣性對多目標優化十分關鍵,因為多樣性對后續的搜索以及最終得到的解對PF的擬合程度具有重要的影響。

雇傭蜂策略采用懲罰邊界交叉(PBI:Penalty-Based Boundary Intersection)分解策略設計各子問題。因此子問題的數量與權重向量的數量相等。對第i個權重向量,對應的子問題為

minimizegpbi(x|λi,z*)=d1+θd2, subject tox∈Ω,

(3)

其中

(4)

d2=‖F(x)-(z*-d1λi)‖,

(5)

由于各子問題通過式(3)轉化為標量化的函數,所以在算法進行解的評價和選擇時,各子問題可擁有唯一的最優解?；诜纸獾牟呗院喕硕嗄繕藘灮脑u價和選擇過程,對提高算法效率具有重要意義。

雇傭蜂搜索策略起始時計算權重向量之間的幾何距離,每個權重向量選擇與其歐氏距離最近的T個權重向量作為其鄰居[17]。然后算法根據權重向量構建N個子問題,并從食物源中為每個子問題選擇最優解。之后,對每個食物源,算法根據式(1)和式(2)執行變異算子和交叉算子,從而產生一個新候選解。隨后計算新生成的候選解在各目標函數上的取值,并從已有食物源和新生成的候選解中為每個子問題選擇各子問題的最優解。最后用子問題的最優解更新食物源。

算法2 基于分解的雇傭蜂搜索。

輸入:N種食物來源; 權向量λ={λ1,λ2,…,λN};

輸出:N個更新的食物來源;

1) 計算權向量之間的距離;

2) for每個權重向量do:

3) 選擇T個最接近的權值向量作為其鄰居;

4) end

5) while終止條件不滿足do:

6) for每只受雇的蜂蜜do:

7) 執行變異運算符;

8) 執行交叉運算;

9) end

10) 評估每個新解決方案的客觀價值;

11) 融合食物來源和新的解決方案;

12) 根據權向量λ={λ1,λ2,…,λN}生成子問題;

13) for對每個子問題do:

14) 找到最優解;

15) end

16) 更新食物來源;

17) End

2.4 算法復雜度分析

根據算法2,雇傭蜂、觀察蜂和偵察蜂階段的時間復雜度均為O(n2)。因此,MOABC/DD的時間復雜度為O(n2)。需要注意的是,在優化過程中并不總是處于執行偵察蜂階段。同時,MOABC/DD不需要外部解集用于維護非支配解,它只維護一套食物源。因此,其空間復雜度為O(n)。

3 改進的人工蜂群算法在機電執行器設計問題中的應用

將所提算法應用于機電執行器設計問題(MODAct:Modification Actuators),該問題為一種實際的工程設計問題。機電執行器是由電動機和齒輪箱組成的系統,其作用是使其他組件在位置控制設置或動作生成過程中旋轉。機電執行器被廣泛應用于多種不同的應用中。由于機電執行器應用范圍廣,各種設計目標之間相互沖突,對問題具有嚴格的限制,所以機電執行器的設計問題是一種典型的工程設計CMOP。在機電執行器設計問題中應用對筆者提出的改進多目標ABC,能對該算法求解CMOP的性能進行測試和分析。

3.1 問題定義

在筆者的機電執行器設計問題中,目標機電執行器由步進電機、k級齒輪(一級齒輪由一個主動小齒輪和一個從動大齒輪構成)和一個容納各部件的容器構成。一個機電執行器可以被建模為包含k+1個組件的組件鏈,各組件分別包括:1) 預測組件輸出速度、輸出扭矩以及與組件相關約束的物理模型; 2) 代價模型ci; 3) 用于創建和組裝機電執行器系統的幾何模型?；谖锢砟Ｐ秃痛鷥r模型,或通過檢查幾何模型,可將機電執行器設計問題的優化目標和約束表示為數學形式。

對問題建模,當計算步進電機的性能時,假設步進電機處于穩態運行的前提下,步進電機的參數θ可從現有商用兩相步進電機的5種可能的參數組合中進行選擇[18]。定子線圈繞組可通過縮放填充因子FF或電阻Rscale進行調整。所有步進電機都由一個嚙合的圓柱形表示,其直徑和高度與其實際尺寸相對應。他們的成本代價由兩部分組成:組件的固定貢獻和其所選繞組的可變部分。問題中齒輪被建模為符合ISO標準的鋼齒輪,其特征包含齒數Zi{1,2},輪廓偏移xi{1,2),模數mi和厚度bi。齒輪的三維構成方式通過圓柱形嚙合關系進行幾何表示。齒輪的代價通過齒輪的體積進行估算[19]。作用于每個部件上的轉速和扭矩可從電機開始依次計算。在本研究中機電執行器各組件之間的能量流被認為是完美的(即沒有能量損失和完美的剛性連接)。對給定的輸入條件(電源電壓Um、最大電流Imax和所需的輸出轉速ω),可以計算輸出端的扭矩T。一組由電源電壓、電流、所需速度和扭矩構成的參數構成為一個工作點(operating point)。輸出端與所需扭矩的偏差稱為扭矩過剩[20]。齒輪的三維位置由每個齒輪級的兩個決策變量指定:1) 沿軸的平移di,2) 小齒輪和從動輪之間的角度γi。使用所有嚙合輪廓的組合檢測組件間的碰撞并計算系統邊界框的大小。最后,采用凸面形的外殼,假設壁厚固定,所需的材料成本選擇被添加到總成本中。使用這種建模方法,機電執行器設計問題的目標在于找到一組在指定工作點運行的合適電機和齒輪參數,并保證其符合齒輪的機械完整性、空間配置等約束[21]。

搜索空間對應機電執行器每個組件的組合。齒輪和電機的決策變量均為整型。為了使更多的優化算法被用于機電執行器設計問題中,筆者定義的MODAct問題將整型變量與相關的連續變量組合為一個實數,其整數部分表示整型變量,小數部分則映射到其他變量。具體映射方式為:

1) 電機選擇變量和填充因子FF共同組成變量mF;

2) 齒輪的齒數Zi{1,2}和其齒廓位移構成變量Zxi{1,2}。

在筆者所采納的MODAct測試用例中,設置k=3,并設計了5種不同的目標函數,通過不同目標函數的組合,可構建不同的MODAct基準測試用例。具體優化目標設計如下。

1) 總成本最小化:

(6)

2) 最大化每個考慮的工作點的最小過剩扭矩

(7)

其中ΔTj=Tj-Tdesired,j。

3) 最大化所有齒輪彎曲SF和點蝕SH的安全系數的調和平均值

(8)

4) 最大化電能到機械能的轉換效率

(9)

5) 最小化轉換率

(10)

基于對以上目標函數的組合,文中的MODAct問題可以分為5類:1) CS,2) CT,3) CTS,4) CTSE,5) CTSEI,各自對應上面5個參數的組合。

此外,MODAct考慮了機電執行器設計中常見的各種不同約束。這些約束可被分為4類:1) 對齒輪的約束(如足夠的接觸比、有限的滑動速度、無干擾、足夠的彎曲和機械強度等); 2) 最小化扭矩過載工作點; 3) 邊界框尺寸的上限(bby≤50 mm且bbz≤35 mm); 4) 從輸出軸到所需坐標的距離限制在5 mm之內。

以上4種不同類型的約束的復雜性不同,而且存在于機電執行器設計過程中的不同階段,例如約束1)和2)通常存在于MODAct的早期階段; 有些約束對應特定的應用規格和需求,例如約束3)和4)對機電執行器的技術規格提出了具體要求。不同的約束可以與不同的MODAct優化目標進行組合。將以上的4種約束與5種不同的MODAct問題進行組合能得到20個基準MODAct測試用例,將這些基準測試用例使用目標名稱加約束類型進行命名。例如CTS類型的MODAct問題與約束2)結合可以得到基準測試用例CTS2。

表1給出了所有的測試用例實例與目標空間約束的參數個數(n、m、p、q),其測試用例的搜索空間上下界分別為

表1 MODAct基準測試用例

x(L)=[0,0.3,9,30,0.3,5,020,-π,9,30,0.3,5,020,-π,9,30,0.3,5,020,-π],

(11)

x(U)=[5-10-6,2,41-10-6,81-10-6,1,15,20,π,

41-10-6,81-10-6,1,15,20,π,41-10-6,81-10-6,1,15,20,π]。

(12)

需要注意的是,除存在2種不同要求的最小扭矩過剩約束外,所有的約束都獨立于優化目標。由表1可知,文中的MODAct基準測試用例均可以建模為CMOP,且優化目標的數量從2個到4個不等。隨著優化目標數量的上升,問題優化的難度也隨之升高,因此能對算法的求解精度和效率進行有效驗證。

3.2 實驗結果比較

該實驗對比了MOABC/DD和NSGA-Ⅱ、NSGA-Ⅲ、C-TAEA算法在20個機電執行器設計測試用例上的優化結果,將MOABC/DD算法和各對比算法分別獨立運行31次。如上所述,機電執行器設計問題中的一部分優化目標為最小化優化問題,另一部分優化目標為最大化優化問題。為方便算法對基準測試用例進行優化,在實驗前統一將所有的最大化優化目標轉化為最小化優化目標,轉化方法為求原優化目標的倒數。采用HV(hypervolume)指標對各算法產生的非支配解的質量進行評價。在對各算法的結果進行HV指標計算時,先對所有的優化結果進行標準化,即將各優化目標的目標值轉化為0～1之間的實數,然后將HV指標計算的參考點設為r=(r1,r2,…,rm)T,滿足r1=r2=…=rm=1。

31次獨立重復實驗中各算法的HV指標如表2所示。其中每個算法在每個測試用例上對應4個數值,4個數值之間以符號“/”作為間隔,其中第1個數值為獨立重復實驗HV指標的均值,第2個為HV指標的最優值,第3個為HV指標的最差值,第4個為獨立重復實驗所統計的HV指標的標準差。HV的均值、最優值和最差值均為越大越好,HV的標準差越小表明算法求解的穩定性越強,因此認為HV標準差應盡量小。

表2 各測試用例上實驗結果的HV指標

由表2可看出,MOABC/DD在20個基準測試用例中的5個測試用例上同時取得了HV均值、最優值、最差值和標準差的最優結果; 其在18個測試用例上取得了最優的HV均值; 在12個測試用例上取得了最優的HV最優值,在16個測試用例上取得了最優的HV最差值; 在12個測試用例上取得了最優的HV標準差。實驗結果表明,當CMOP約束類型和優化目標數量不同時,MOABC/DD都具有較為優異的優化性能。在大多數基準測試用例上MOABC/DD的實驗結果都具有較高的精度,且在獨立重復實驗中,MOABC/DD的優化穩定性也較強。NSGA-Ⅱ/Ⅲ和C-TAEA在約束級別為3和4的MODAct實例上的性能不足,而其代表了常見和簡單的機械設計問題?？紤]到問題CS3和CS4,超過75%的NSGA-Ⅱ優化運行獲得了近似的帕累托前沿,其超體積為50%或小于最著名的帕累托前沿,而C-TAEA未能找到有效的解決方案[22]。與其他算法相比,MOABC/DD具有更適用于MODAct問題的優化性能。

為比較MOABC/DD與對比算法在4個典型的機電執行器設計問題的基準測試用例上對PF的擬合情況,根據各算法在獨立執行中得到的解在目標空間中的映射進行繪圖,結果如圖2所示。橫坐標為最小化優化問題的變量,縱坐標為最大化優化問題的變量。因此,在4個測試用例中,解的位置越靠近左上角,算法產生的解對PF的擬合情況越好。由圖2可見,MOABC/DD在4個測試用例上對PF的擬合效果較好,其產生的解在目標空間中的位置不僅更接近坐標系第1象限的左上方,而且解的分布也更為均勻,因此MOABC/DD產生的解對選取的4個測試用例的擬合效果是參與實驗的算法中最好的。

圖2 各算法對PF的擬合情況比較

4 結 語

筆者在ABC算法基礎上引入了群智能優化和進化優化中常見的交叉、變異算子,并結合算法的基本原理提出了一種改進的MOABC/DD算法。將一種實際的機電執行器設計問題作為工程設計問題的基準測試用例對提出的MOABC/DD進行了驗證。實驗結果表明,所提出的MOABC/DD算法在求解機電執行器設計問題基準測試用例時,與典型算法相比,具有較好的問題求解精度。通過比較多次重復實驗的實驗結果可知MOABC/DD的實驗結果較為穩定,證明了MOABC/DD具有較高的求解穩定性和健壯性。