二進制阿基米德優化算法及其應用

李春生,盧羿州

(1.東北石油大學 計算機與信息技術學院,黑龍江 大慶 163319;2.黑龍江省石油大數據與智能分析重點實驗室,黑龍江 大慶 163319)

0 引 言

組合優化問題的研究在交通運輸、通訊網絡和工業工程等領域有著廣泛的應用意義。合理的資源組合優化有助于降低成本的支出和提高生產效率。因而,組合優化問題成為了社會關注的熱點。隨著實際問題的復雜化,枚舉法、動態規劃法和回溯法等傳統方法的時間復雜度隨之提高,導致求解困難。因此,科研人員熱衷于使用元啟發式算法進行求解。

元啟發式算法采取種群進化機制,初始化大量個體,根據目標函數進行全局和局部搜索,以得到最優解。元啟發式算法包含粒子群、遺傳算法和蝙蝠算法等優化算法,被廣泛用于求解路徑優化[1]、資源調度[2]和參數優化[3]等問題,并取得了良好的效果。但對于較大解空間的組合優化問題,存在求解慢和易陷入局部最優解等問題。

Fatma A. Hshim等人[4]于2020年提出了阿基米德優化算法(Archimedes Optimization Algorithm,AOA)。AOA算法具有簡單、效率高和適應性強等特點,主要用于求解連續優化問題[5-7],且效果較好。但對于離散的組合優化問題不能直接進行求解,同時依然存在陷入局部最優解的現象。為此,有必要研究一種二進制阿基米德優化算法(Binary Archimedes Optimization Algorithm,BAOA)解決0-1背包問題、資源調度和投資組合等優化問題。

借鑒部分二進制優化算法的思想并引用北極熊算法[8]的出生與死亡規則,該文提出了一種用于求解組合優化問題的BAOA算法。通過對比實驗,驗證BAOA算法解決組合優化問題的有效性。

1 阿基米德優化算法

阿基米德優化算法[4]可以描述為具有位置、體積、密度和加速度四個屬性的對象群體,在流體中尋找最佳平衡位置的過程。AOA算法描述如下:

(1)對象初始化。假設群體有M個對象,搜索空間為P維,移動范圍為[a,b],迭代次數為T,則群體X可表示為[X1,X2,…,XM]T,那么X中的第m個對象可以表示為[Xm1,Xm2,…,Xmp],m=1,2,…,M。通過公式(1)～(4)初始化第m(m=1,2,…,M)個對象的位置L、體積V、密度D和加速度A,公式中的rand表示取0～1之間的隨機數。

(1)

(2)

(3)

(4)

(2)更新對象m的密度和體積。迭代次數T加1,計算其最佳位置Lbest、最佳密度Dbest、最佳體積Vbest和最佳加速度Abest。根據公式(5)和(6)更新對象m的密度和體積。

(5)

(6)

(3)更新對象m的加速度,計算歸一化加速度。在該階段,AOA算法提出了轉移算子TF和密度因子d,用于全局和局部搜索之間的轉換。TF和d的計算公式如(7)和(8)所示。當TF≤0.5時,表示對象發生碰撞,進行全局搜索,根據公式(9)更新對象m的加速度;當TF>0.5時,表示對象未發生碰撞,進行局部搜索,根據公式(10)更新對象m的加速度。歸一化加速度的計算公式如(11)所示,用于全局與局部的搜索平衡。

(7)

(8)

(9)

(10)

(11)

式中,Dmr、Vmr和Amr表示隨機對象的密度、體積和加速度,u=0.9,l=0.1。

(4)更新對象m的位置。當TF≤0.5時,根據公式(12)更新對象m的位置;當TF>0.5時,根據公式(13)更新對象m的位置。

(12)

(13)

T=C3×TF

(14)

(15)

式中,C1、C2、C3、C4為常數,Lrand表示隨機對象的位置。

2 二進制阿基米德優化算法的研究

在實際組合優化問題中,每個對象可能以二維矩陣或高維矩陣進行編碼,該文以二維矩陣為例進行描述。編碼表示如下:

(16)

2.1 二進制轉換函數的選取

二進制粒子群優化算法[9]、二進制鯨魚優化算法[10]和二進制磁力優化算法[11]等大多數二進制算法,均是采用轉換函數將連續空間映射到0,1空間。

Seyedali Mirjalili[12]和Ghosh K K[13]等人,通過對比實驗得到以下結論:轉換函數變化率的大小決定優化速度與解的質量;V型函數相較于S型函數,對算法的性能有一定的提升。在文獻[14]中提到轉換函數作為中轉系統應具有以下特征: 轉換函數值的大小,表示0和1相對轉變的概率;速度絕對值的大小與轉換函數值的大小相一致;位置距離的大小與轉換函數值的大小相一致。

綜上,在對編碼無要求的情況下,BAOA算法選用V型轉換函數,以位置距離差作為參數進行空間映射。在對編碼中行或列包含1的個數有要求的情況下,搜索空間會被放大,存在算法進化失效的現象。例如,要求編碼中每一列只能存在一個1時,搜索空間由CR擴大為2的CR次方。為此,需要在位置更新過程中限制0和1出現的次數。因為S型轉換函數的sigmoid函數是根據條件直接設置0或1,較V型轉換函數相對可控,所以對編碼有要求時,使用S型函數作為轉換函數更為有利。在后續實驗中會進行驗證。

2.2 二進制阿基米德優化算法

BAOA算法是在AOA算法的基礎上根據編碼要求,選取合適轉換函數、sigmoid函數及引用北極熊算法的出生與死亡規則。主要改進如下:

(1)在初始化階段,根據需求對第m個對象的位置和加速度生成由0或1組成的矩陣。

(2)根據公式(5)～公式(15)更新對象m的屬性后,選取適當的轉換函數,并以對象m與最佳位置的距離作為參數,更新對象m的位置。當對編碼無要求時,轉換函數和sigmoid函數如式(17)和式(18)所示。當對編碼有要求時,即要求某一行或某一列有n個1,轉換函數和sigmoid函數如式(19)和式(20)所示。

r=1,2,…,R,c=1,2,…,C

(17)

r=1,2,…,R,c=1,2,…,C

(18)

r=1,2,…,R,c=1,2,…,C

(19)

r=1,2,…,R,c=1,2,…,C

(20)

(3)引用北極熊算法的出生與死亡規則,并進行部分修改。當最優解長時間保持不變時,根據公式(21)對適應度為后10%的對象進行位置更新。

(21)

2.3 BAOA算法的執行步驟

Step1:初始化對象群體,根據編碼條件隨機生成每個對象的屬性;將每個對象的坐標帶入適應度函數,計算得到最佳位置Lbest、最佳體積Vbest、最佳密度Dbest和最佳加速度Abest。

Step2:迭代次數加1,根據公式(5)和(6)更新所有對象的體積和密度。

Step3:根據公式(7)～公式(11),首先,計算轉移算子和密度因子;其次,更新對象的加速度;最后,計算歸一化加速度。

Step4:根據公式(12)～公式(15),首先,更新對象的位置;其次,根據編碼條件選取公式(17)(18)或公式(19)(20)對更新后的位置進行二進制映射;最后,根據更新后的位置,重新計算最佳位置Lbest、最佳體積Vbest、最佳密度Dbest和最佳加速度Abest。

Step5:如果最優解長時間穩定不變,則根據公式(21)對自適應度的后10%的對象進行位置更新。

Step6:重復循環步驟2～步驟5,直至滿足條件結束循環。

2.4 BAOA算法有效性分析

通常算法會從開拓能力和開采能力、收斂性與計算復雜度等方面進行分析。由于BAOA算法的基本核心為AOA算法,且在文獻[4]中已分析了AOA算法的開拓能力和開采能力,因此后續將從收斂性與計算復雜度兩個方面對BAOA算法進行分析。

BAOA算法與其他啟發式算法一樣,每次迭代都會對對象的屬性及全局最優結果進行更新,使對象向自適應度最優的位置靠近。在理想情況下,經過無窮次的迭代更新,必然能夠搜索到所有的可能解,找出最優解。因此,理論上BAOA算法具有收斂性。在實際情況中,BAOA算法依然存在陷入局部最優的現象,引用北極熊算法的出生與死亡規則,以減少陷入局部最優解的次數,其有效性將在后續實驗中進行驗證。

最大執行次數等于迭代次數與群體個數的乘積。對象數量和迭代次數分別影響了BAOA算法的搜索范圍和覆蓋率。算法的計算量來源于適應度函數的計算,在一個執行周期內將進行一組適應度函數的計算。假設群體對象個數為M,最大迭代次數為T,一組適應度函數有q個計算公式,則BAOA算法的計算量sum≤M×T×q,計算復雜度較低,可以有效地減少最優解的搜索時間。

3 實驗分析及算法應用

3.1 組合優化問題描述

組合最優化問題是運籌學的一個分支,通常屬于NP問題。是指在給定有限的子集簇中,尋找使某種指標達到最優子集的問題[10]?？梢院唵蔚乩斫鉃?在離散的空間下求解某個問題的最大或最小值。典型的0-1背包問題,調度問題和材料選配問題等都屬于組合優化問題。數學模型表示如下:

min(f(x))或max(f(x));x∈S

(22)

s.t.Cmin≤h(x)

(23)

式中,f(x)表示所需要優化的目標函數;h(x)為約束函數;Cmin和Cmax為約束條件;S表示所有可能解組成的集合。

后續,通過模擬求解0-1背包問題及BAOA算法在熱力管道保溫結構優化項目中的應用,驗證BAOA算法求解組合優化問題的可行性。

3.2 0-1背包問題實驗與分析

0-1背包問題是典型的組合優化問題,具體描述如下:有一個最大容量為Vmax的背包,現有t件商品,第i件商品的體積為Vi,價值為Pi,需要求出選擇哪些商品,可以在背的包容量范圍內價值最大。數學模型表示如下:

(24)

對于含有約束函數優化模型,通常會采用懲罰系數法進行求解,公式(24)通過懲罰系數法轉換如公式(25)所示,式中γ為懲罰系數。

Vi-Vmax),xi=0,1

(25)

為了充分驗證BAOA算法的性能,引用文獻[15]中的6個經典0-1背包問題實例(k1,k2,k3,k4,k7,k10)進行對比實驗,編號設為I1～I6。并與非引用出生與死亡規則的二進制阿基米德優化算法(BAOA-NB)和文獻[15]中引用的其他算法進行對比。BAOA與BAOA-NB算法的參數設置如下:C1=2,C2=6,C3=2,C4=0.7,I1～I4問題的群體個數為50,最大迭代次數為800;I5和I6問題的群體個數為200,最大迭代次數為3 000。對每個問題分別運算20次,根據性能指標(最優結果、最差結果、達到最優結果所需的平均迭代次數及陷入局部最優次數),對BAOA算法進行評價。對比結果如表1所示,表中A/B表示總價值/體積,-表示不存在。

表1 0-1背包問題結果對比

從表1中的數據可以看出,BAOA算法對于上述6組背包問題都可以搜索到最優結果;總體上迭代次數會隨問題維度的增加而增加。對于高維度問題BAOA算法依然存在陷入局部最優的現象,但其最差解依然優于一部分優化算法的最優解。由此可知,BAOA算法具有良好的全局搜索性與收斂性。

對比BAOA算法和BAOAO-NB算法的性能指標可以得出,引用北極熊算法的出生與死亡規則,可以有效地提高算法的搜索效率并減少陷入局部最優的次數。

3.3 BAOA算法在熱力管道保溫結構優化項目中的應用

管道保溫結構老化不僅會造成能源的浪費,同時也會對人員及設備構成潛在的威脅。為此,對保溫性能不合格的保溫結構進行及時、準確的優化調整極為重要。優化管道保溫結構的材料選配,是根據管道的工藝和位置來設置最大的材料鋪設層數,選擇合適的保溫材料進行組合。

3.3.1 保溫結構優化的概念及公式描述

管道保溫結構的材料選配,在使經濟效益最大化的基礎上,還需考慮以下三個方面:散熱損失達到國家標準;材料在允許溫度內使用;防止工作人員接觸管道燙傷。管道保溫結構優化公式[16]如下,公式中符號及解釋如表2所示。

表2 符號及相關解釋

(1)總對流換熱系數h,包含保溫結構外表面與空氣間的對流換熱系數和輻射換熱折合的對流換熱系數兩個部分。計算公式如下:

(2)保溫材料的導熱系數與接觸溫度有關,通常選用平均溫度tm進行計算。其具體計算公式如下:

λ=λ0+btm

(27)

(3)管道散熱損失的計算公式如下:

(4)保溫結構外表面溫度的計算公式如下:

(29)

(5)保溫結構每層材料接觸面的溫度計算公式如下:

(30)

(6)在國內一般企業按5～10年可回收建設投資,材料使用年限取7,基本符合國情,年經濟效益函數如下:

(31)

總體數學模型中的目標函數如公式(32)所示,約束函數如公式(33)所示。

max(V(x))

(32)

(33)

3.3.2 實驗內容與分析

模擬發電站在對保溫結構的優化過程。選取3段蒸汽管道,12種保溫材料(M1～M12),進行實驗分析。

表3給出了管道的長度、管徑、介質溫度和當前保溫結構的散熱損失等信息。

表4給出了保溫材料的基本屬性信息。

表3 管道屬性

表4 保溫材料屬性

基于3組管道,選取混合離散粒子群算法(DPSO-SA)[2]、二進制北極熊算法(BPBO)[17]和使用對編碼無要求的二進制阿基米德優化算法(實驗中用BAOA-V表示)。通過對比DPSO-SA和BPBO算法,驗證BAOA算法的性能。通過對比BAOA-V算法,驗證對編碼有要求時,使用S型轉換函數具有相對優勢。為防止BPBO和BAOA-V算法出現大規模的進化失效的現象,則將其結合DPSO-SA算法中的進化策略作為對比對象。

參數設置如下,群體數量為200,最大迭代次數為1 200;DPSO-SA:ω=0.9,c1=c2=1.5,ω_max=0.9,ω_min=0.4,初始溫度為10 000,冷卻因子為0.9,v_max=10,v_min=-10,BPBO:種群數量百分比R=0.75,最大視野距離Vp=0.3,出生與死亡的隨機變量K=0.25;BAOA和BAOA-V:C1=2,C2=6,C3=2,C4=0.7。

每組實驗分別運行50次,取最大經濟效益、最小經濟效益、到達最優解的平均迭代次數和標準差等作為對比指標。表5給出了實驗中4種算法的各項指標數值,其中A、B、C表示三組管道的實驗指標。圖1(a)-(b)、(c)-(d)、(e)-(f)分別展示了通過4種算法得到的經濟效益和取得最優解時的迭代次數。

表5 實驗中4種算法的各項指標數值

圖1 實驗結果

三段管道的可鋪設層數為:3、4和5,表明了實驗中三組實驗的解空間不同。結合表5和圖1可以得到如下結論:

(1)4種算法都可以得到最大經濟效益。隨著解空間的增大,算法的平均迭代次數、陷入局部最優解的次數和標準差都隨之增大。

(2)從圖1(a)(c)(e)可以看出,BAOA算法陷入局部最優解的次數明顯少于其他3種算法,說明在對編碼有要求時,BAOA算法的全局搜索性強并具有良好的收斂性。從圖1(b)(d)(f)可以看出,BAOA算法達到最優解時的迭代次數明顯少于其他3種算法,說明對編碼有要求時,BAOA算法搜索速度快。從表5中的標準差指標可以得出,BAOA算法具有良好的穩定性。

(3)對比BAOA和BAOA-V算法的性能指標可以得出, 在對編碼有要求時,使用S型轉換函數進行二進制映射效果更好。

4 結束語

在阿基米德優化算法的基礎上,引入轉換函數和北極熊算法的出生與死亡規則,提出了一種用于求解組合優化問題的二進制阿基米德優化算法。通過6組0-1背包問題的仿真實驗,驗證了BAOA算法對編碼無要求的組合優化問題,具有較好的收斂性和搜索速度。引用北極熊算法的出生與死亡規則,可以使BAOA算法更好地進行全局搜索,減少陷入局部最優解的次數。通過在熱力管道保溫結構優化項目中的應用,驗證了對于編碼有要求的組合優化問題,BAOA算法具有較好的收斂性和穩定性。同時也驗證了,在對編碼中行或列包含1的個數有要求的情況下,選用S型轉換函數更為有利。

未來,使用BAOA算法求解其他場景的組合優化問題時,還需要在目前研究的基礎上,進一步解決更加具體的問題。