二進(jìn)制阿基米德優(yōu)化算法及其應(yīng)用

李春生,盧羿州

(1.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,黑龍江 大慶 163319;2.黑龍江省石油大數(shù)據(jù)與智能分析重點(diǎn)實(shí)驗(yàn)室,黑龍江 大慶 163319)

0 引 言

組合優(yōu)化問題的研究在交通運(yùn)輸、通訊網(wǎng)絡(luò)和工業(yè)工程等領(lǐng)域有著廣泛的應(yīng)用意義。合理的資源組合優(yōu)化有助于降低成本的支出和提高生產(chǎn)效率。因而,組合優(yōu)化問題成為了社會(huì)關(guān)注的熱點(diǎn)。隨著實(shí)際問題的復(fù)雜化,枚舉法、動(dòng)態(tài)規(guī)劃法和回溯法等傳統(tǒng)方法的時(shí)間復(fù)雜度隨之提高,導(dǎo)致求解困難。因此,科研人員熱衷于使用元啟發(fā)式算法進(jìn)行求解。

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

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

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

1 阿基米德優(yōu)化算法

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

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

(1)

(2)

(3)

(4)

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

(5)

(6)

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

(7)

(8)

(9)

(10)

(11)

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

(4)更新對(duì)象m的位置。當(dāng)TF≤0.5時(shí),根據(jù)公式(12)更新對(duì)象m的位置;當(dāng)TF>0.5時(shí),根據(jù)公式(13)更新對(duì)象m的位置。

(12)

(13)

T=C3×TF

(14)

(15)

式中,C1、C2、C3、C4為常數(shù),Lrand表示隨機(jī)對(duì)象的位置。

2 二進(jìn)制阿基米德優(yōu)化算法的研究

在實(shí)際組合優(yōu)化問題中,每個(gè)對(duì)象可能以二維矩陣或高維矩陣進(jìn)行編碼,該文以二維矩陣為例進(jìn)行描述。編碼表示如下:

(16)

2.1 二進(jìn)制轉(zhuǎn)換函數(shù)的選取

二進(jìn)制粒子群優(yōu)化算法[9]、二進(jìn)制鯨魚優(yōu)化算法[10]和二進(jìn)制磁力優(yōu)化算法[11]等大多數(shù)二進(jìn)制算法,均是采用轉(zhuǎn)換函數(shù)將連續(xù)空間映射到0,1空間。

Seyedali Mirjalili[12]和Ghosh K K[13]等人,通過對(duì)比實(shí)驗(yàn)得到以下結(jié)論:轉(zhuǎn)換函數(shù)變化率的大小決定優(yōu)化速度與解的質(zhì)量;V型函數(shù)相較于S型函數(shù),對(duì)算法的性能有一定的提升。在文獻(xiàn)[14]中提到轉(zhuǎn)換函數(shù)作為中轉(zhuǎn)系統(tǒng)應(yīng)具有以下特征: 轉(zhuǎn)換函數(shù)值的大小,表示0和1相對(duì)轉(zhuǎn)變的概率;速度絕對(duì)值的大小與轉(zhuǎn)換函數(shù)值的大小相一致;位置距離的大小與轉(zhuǎn)換函數(shù)值的大小相一致。

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

2.2 二進(jìn)制阿基米德優(yōu)化算法

BAOA算法是在AOA算法的基礎(chǔ)上根據(jù)編碼要求,選取合適轉(zhuǎn)換函數(shù)、sigmoid函數(shù)及引用北極熊算法的出生與死亡規(guī)則。主要改進(jìn)如下:

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

(2)根據(jù)公式(5)～公式(15)更新對(duì)象m的屬性后,選取適當(dāng)?shù)霓D(zhuǎn)換函數(shù),并以對(duì)象m與最佳位置的距離作為參數(shù),更新對(duì)象m的位置。當(dāng)對(duì)編碼無要求時(shí),轉(zhuǎn)換函數(shù)和sigmoid函數(shù)如式(17)和式(18)所示。當(dāng)對(duì)編碼有要求時(shí),即要求某一行或某一列有n個(gè)1,轉(zhuǎn)換函數(shù)和sigmoid函數(shù)如式(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)引用北極熊算法的出生與死亡規(guī)則,并進(jìn)行部分修改。當(dāng)最優(yōu)解長(zhǎng)時(shí)間保持不變時(shí),根據(jù)公式(21)對(duì)適應(yīng)度為后10%的對(duì)象進(jìn)行位置更新。

(21)

2.3 BAOA算法的執(zhí)行步驟

Step1:初始化對(duì)象群體,根據(jù)編碼條件隨機(jī)生成每個(gè)對(duì)象的屬性;將每個(gè)對(duì)象的坐標(biāo)帶入適應(yīng)度函數(shù),計(jì)算得到最佳位置Lbest、最佳體積Vbest、最佳密度Dbest和最佳加速度Abest。

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

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

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

Step5:如果最優(yōu)解長(zhǎng)時(shí)間穩(wěn)定不變,則根據(jù)公式(21)對(duì)自適應(yīng)度的后10%的對(duì)象進(jìn)行位置更新。

Step6:重復(fù)循環(huán)步驟2～步驟5,直至滿足條件結(jié)束循環(huán)。

2.4 BAOA算法有效性分析

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

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

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

3 實(shí)驗(yàn)分析及算法應(yīng)用

3.1 組合優(yōu)化問題描述

組合最優(yōu)化問題是運(yùn)籌學(xué)的一個(gè)分支,通常屬于NP問題。是指在給定有限的子集簇中,尋找使某種指標(biāo)達(dá)到最優(yōu)子集的問題[10]?？梢院?jiǎn)單地理解為,在離散的空間下求解某個(gè)問題的最大或最小值。典型的0-1背包問題,調(diào)度問題和材料選配問題等都屬于組合優(yōu)化問題。數(shù)學(xué)模型表示如下:

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

(22)

s.t.Cmin≤h(x)

(23)

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

后續(xù),通過模擬求解0-1背包問題及BAOA算法在熱力管道保溫結(jié)構(gòu)優(yōu)化項(xiàng)目中的應(yīng)用,驗(yàn)證BAOA算法求解組合優(yōu)化問題的可行性。

3.2 0-1背包問題實(shí)驗(yàn)與分析

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

(24)

對(duì)于含有約束函數(shù)優(yōu)化模型,通常會(huì)采用懲罰系數(shù)法進(jìn)行求解,公式(24)通過懲罰系數(shù)法轉(zhuǎn)換如公式(25)所示,式中γ為懲罰系數(shù)。

Vi-Vmax),xi=0,1

(25)

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

表1 0-1背包問題結(jié)果對(duì)比

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

對(duì)比BAOA算法和BAOAO-NB算法的性能指標(biāo)可以得出,引用北極熊算法的出生與死亡規(guī)則,可以有效地提高算法的搜索效率并減少陷入局部最優(yōu)的次數(shù)。

3.3 BAOA算法在熱力管道保溫結(jié)構(gòu)優(yōu)化項(xiàng)目中的應(yīng)用

管道保溫結(jié)構(gòu)老化不僅會(huì)造成能源的浪費(fèi),同時(shí)也會(huì)對(duì)人員及設(shè)備構(gòu)成潛在的威脅。為此,對(duì)保溫性能不合格的保溫結(jié)構(gòu)進(jìn)行及時(shí)、準(zhǔn)確的優(yōu)化調(diào)整極為重要。優(yōu)化管道保溫結(jié)構(gòu)的材料選配,是根據(jù)管道的工藝和位置來設(shè)置最大的材料鋪設(shè)層數(shù),選擇合適的保溫材料進(jìn)行組合。

3.3.1 保溫結(jié)構(gòu)優(yōu)化的概念及公式描述

管道保溫結(jié)構(gòu)的材料選配,在使經(jīng)濟(jì)效益最大化的基礎(chǔ)上,還需考慮以下三個(gè)方面:散熱損失達(dá)到國(guó)家標(biāo)準(zhǔn);材料在允許溫度內(nèi)使用;防止工作人員接觸管道燙傷。管道保溫結(jié)構(gòu)優(yōu)化公式[16]如下,公式中符號(hào)及解釋如表2所示。

表2 符號(hào)及相關(guān)解釋

(1)總對(duì)流換熱系數(shù)h,包含保溫結(jié)構(gòu)外表面與空氣間的對(duì)流換熱系數(shù)和輻射換熱折合的對(duì)流換熱系數(shù)兩個(gè)部分。計(jì)算公式如下:

(2)保溫材料的導(dǎo)熱系數(shù)與接觸溫度有關(guān),通常選用平均溫度tm進(jìn)行計(jì)算。其具體計(jì)算公式如下:

λ=λ0+btm

(27)

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

(4)保溫結(jié)構(gòu)外表面溫度的計(jì)算公式如下:

(29)

(5)保溫結(jié)構(gòu)每層材料接觸面的溫度計(jì)算公式如下:

(30)

(6)在國(guó)內(nèi)一般企業(yè)按5～10年可回收建設(shè)投資,材料使用年限取7,基本符合國(guó)情,年經(jīng)濟(jì)效益函數(shù)如下:

(31)

總體數(shù)學(xué)模型中的目標(biāo)函數(shù)如公式(32)所示,約束函數(shù)如公式(33)所示。

max(V(x))

(32)

(33)

3.3.2 實(shí)驗(yàn)內(nèi)容與分析

模擬發(fā)電站在對(duì)保溫結(jié)構(gòu)的優(yōu)化過程。選取3段蒸汽管道,12種保溫材料(M1～M12),進(jìn)行實(shí)驗(yàn)分析。

表3給出了管道的長(zhǎng)度、管徑、介質(zhì)溫度和當(dāng)前保溫結(jié)構(gòu)的散熱損失等信息。

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

表3 管道屬性

表4 保溫材料屬性

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

參數(shù)設(shè)置如下,群體數(shù)量為200,最大迭代次數(shù)為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:種群數(shù)量百分比R=0.75,最大視野距離Vp=0.3,出生與死亡的隨機(jī)變量K=0.25;BAOA和BAOA-V:C1=2,C2=6,C3=2,C4=0.7。

每組實(shí)驗(yàn)分別運(yùn)行50次,取最大經(jīng)濟(jì)效益、最小經(jīng)濟(jì)效益、到達(dá)最優(yōu)解的平均迭代次數(shù)和標(biāo)準(zhǔn)差等作為對(duì)比指標(biāo)。表5給出了實(shí)驗(yàn)中4種算法的各項(xiàng)指標(biāo)數(shù)值,其中A、B、C表示三組管道的實(shí)驗(yàn)指標(biāo)。圖1(a)-(b)、(c)-(d)、(e)-(f)分別展示了通過4種算法得到的經(jīng)濟(jì)效益和取得最優(yōu)解時(shí)的迭代次數(shù)。

表5 實(shí)驗(yàn)中4種算法的各項(xiàng)指標(biāo)數(shù)值

圖1 實(shí)驗(yàn)結(jié)果

三段管道的可鋪設(shè)層數(shù)為:3、4和5,表明了實(shí)驗(yàn)中三組實(shí)驗(yàn)的解空間不同。結(jié)合表5和圖1可以得到如下結(jié)論:

(1)4種算法都可以得到最大經(jīng)濟(jì)效益。隨著解空間的增大,算法的平均迭代次數(shù)、陷入局部最優(yōu)解的次數(shù)和標(biāo)準(zhǔn)差都隨之增大。

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

(3)對(duì)比BAOA和BAOA-V算法的性能指標(biāo)可以得出, 在對(duì)編碼有要求時(shí),使用S型轉(zhuǎn)換函數(shù)進(jìn)行二進(jìn)制映射效果更好。

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

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

未來,使用BAOA算法求解其他場(chǎng)景的組合優(yōu)化問題時(shí),還需要在目前研究的基礎(chǔ)上,進(jìn)一步解決更加具體的問題。