一種離散混合蛙跳算法及其應用①

張 強,郭玉潔

(東北石油大學 計算機與信息技術學院,大慶 163318)

混合蛙跳算法(Shuffled Frog Leaping Algorithm,SFLA)[1]是Eusuff 和Lansey 通過模擬青蛙種群的覓食過程而設計出的一種群智能優化算法,具有概念簡單、參數少且全局尋優能力強等優點.目前,許多研究學者將其成功應用到不同的工程領域,雷德明等[2]提出一種新型蛙跳算法(SFLA),用于求解低碳混合流水車間調度問題,得到高效率的調度方案.徐俊等[3]將改進后的混合蛙跳算法(ISFLA)用于求解云工作流調度,實驗證明相同的迭代次數下ISFLA 優化的效果更好.張萍等[4]將人工魚群與蛙跳算法結合起來改進矢量匹配法,實現電壓傳輸函數的有理擬合.陳科尹等[5]提出一種改進的混合蛙跳算法,有效解決了傳統采摘機器人相機標定方法的不足.蔡寧等[6]提出一種融入Pareto思想的改進混合蛙跳算法(SFLA)用于求解實際資源約束下拆卸線平衡問題,實驗證明改進SFLA 具有良好的綜合求解優勢.楊哲等[7]將改進實數編碼混合蛙跳算法(IR-SFLA)和二進制編碼的(IB-SFLA)分別應用到水電站經濟負荷分配和機組組合問題,實驗證明IR-SFLA 算法能有效提升水資源利用效率,IB-SFLA在求解大規模機組電力調度問題時可獲得高質量的解.張異[8]設計一種求解包裝配送問題的混沌蛙跳布谷鳥算法,實驗證明CFLCSA 可以得到高效率的配送策略.艾子義等[9]提出一種新型蛙跳算法(SFLA)用于求解低碳柔性作業車間調度問題,實驗表明新型SFLA 具有較強的搜索能力和競爭力.李榮波等[10]針對標準混合蛙跳算法的不足,提出一種改進混合蛙跳算法(ISFLA),來求解梯級水庫優化調度問題,得到了較好的優化結果.

目前,針對SFLA 算法已有了許多先進的研究成果,但對于離散混合蛙跳算法的理論研究相對較少,且缺乏相對的實際應用研究.因此,本文提出了一種離散混合蛙跳算法(Discrete Shuffled Frog Leaping Algorithm,DSFLA),在DSFLA 算法中引入擾動系數來調控最劣解的跳躍方向,從而協調迭代過程中算法的全局探索和局部開發能力；并將擾動系數作為閾值,引用螺旋更新位置來改進族群內個體的更新策略,精細算法的局部搜索能力；同時為了提高算法的全局探索能力,隨機選擇種群內的參照個體進行位置更新；此外采用全局最優解變異提高種群的多樣性,有助于算法跳出局部最優；最后利用改進的Sigmoid 函數對SFLA 進行離散化處理保證了個體的多樣性.對改進效果進行仿真驗證,并將DSFLA 與其它9 種優化算法在求解油田措施規劃模型上進行對比,DSFLA 取得了很好的尋優效果.

1 離散混合蛙跳算法原理

1.1 基本混合蛙跳算法

基本混合蛙跳算法(SFLA)[1]數學模型思想是：一個濕地里有若干塊石頭,青蛙可以在石頭上跳躍尋找食物最多的點,每只青蛙帶有不同的信息,將青蛙種群分為不同的組,通過不同的青蛙個體進行信息交流,實現局部搜索,當局部搜索進行到一定程度時,混合種群中的各組青蛙,實現種群內部的信息交換.根據這一仿生機制,基本蛙跳算法的尋優過程主要由4 部分組成.

(1)種群初始化

在濕地中隨機生成N個青蛙組成的初始種群,其中d維解空間的第i個青蛙表示為Xi={xi1,xi2,···,xid},i=1,2,···,N.

(2)劃分族群

通過計算種群內青蛙的適應度值,根據該值對青蛙進行降序排列；并將種群劃分為m個族群,每個族群包含n個青蛙,其中N=m×n.

(3)局部搜索

① 基于局部最優解的族群內個體更新策略

將第i個族群中最優解和最劣解分別標記為Xib,Xiw,D為跳躍步長,[Dmin,Dmax]為跳躍步長的范圍,在迭代過程中循環對每個族群中的Xiw進行局部搜索,族群最優解的更新方式如式(1)、式(2)所示.若得到的新解Xi′w的適應度值優于Xiw,則取代原來族群中的解；否則將進行操作②.

② 基于全局最優解的族群內個體更新策略

將種群中適應度最好的解標記為Xg,采用全局最優解Xg代替Xib更新Xiw,全局最優解的更新方式如公式(3)和(4)所示,若產生的新解Xi′w仍未優于Xiw；則進行操作③,隨機產生一個新解取代Xiw.

③ 隨機生成新個體更新策略

其中,rand為[0,1]隨機數組成的向量,Dmax表示跳躍步長的最大邊界值.

(4)全局混合

將完成局部搜索后的族群個體重新混合并排序,再次分組和進行族群內部更新,直到算法滿足結束條件.

1.2 離散混合蛙跳算法原理

1.2.1 族群內個體更新原理改進

基本混合蛙跳算法的族群內個體更新策略主要體現在族群內最劣解不斷向最優解的位置方向移動.當迭代到達一定程度后,族群內最優解和全局最優解難以被更新,最劣解朝某一固定方向不斷跳躍,易導致算法陷入局部最優.為了提高算法跳出局部最優的能力,本文引入擾動系數A來調節個體的跳躍步長,并將擾動系數A作為概率閾值,采用標準SFLA族群個體更新位置和螺旋更新位置兩種策略來模擬青蛙的覓食行為.基本混合蛙跳算法的跳躍步長規則如圖1所示,可以看出族群中的最劣解Xw跳躍位置的范圍,被限定在當前位置與族群最優位置之間,這種跳躍規則限制了算法的搜索空間.因此,本文引入擾動系數A來調控青蛙的跳躍步長.由式(7)可知,A的取值范圍是[?α,α]中一個隨機值,當|A|＞1時,青蛙將擴大跳躍范圍,有更大的可能去尋找潛在優秀解(改進后的跳躍步長規則如圖2所示)；當|A|≤1時,蛙群將縮小跳躍范圍在局部區域進行精細搜索.在迭代初期,擾動系數的值較大,保證算法的全局搜索能力,隨著迭代的增加,擾動系數逐漸減小,保證算法的局部搜索能力,從而平衡SFLA算法在優化過程中的全局探索和局部開發能力.

其中,t表示當前迭代次數,Tmax表示最大迭代次數,rand為[0,1]隨機數組成的向量.

圖1 基本跳躍步長規則

圖2 改進的跳躍步長規則

由進化理論可知優秀個體的周圍很大程度上存在更多的潛在優秀個體；基本SFLA 算法的迭代后期,族群內最優解保持不變,易導致算法陷入局部最優.為了提高算法的局部搜索能力,引用螺旋更新位置策略來改進族群內個體的更新方式,螺旋更新位置策略使最劣解沿著螺旋運動軌跡向最優解的位置方向移動,螺旋運動方式能對最優解附近區域進行更加全面精細的搜素,尋找到更多潛在的優秀解.本文將引入的擾動系數作為閾值,當|A|≤1時,采用螺旋更新位置策略；當|A|＞1時,則采用標準SFLA 族群內個體更新策略.其更新公式表達如下：

其中,l為[-1,1]隨機概率,b為限定對數螺旋形狀的常數(通常值取1),Xib表示族群內最優位置.

1.2.2 隨機搜索策略

在基本混合蛙跳算法迭代過程中,隨機生成新個體的更新策略具有一定的混亂性和無序性,不利于算法的收斂.因此本文通過隨機選擇種群中的一個青蛙個體作為參照青蛙,以此來尋找其它更優的解.這樣既實現了種群內部信息的充分交流,同時增強了算法的搜索能力,使該算法能在全局范圍內進行搜索.其更新公式表達如下：

其中,Xrand表示一個隨機位置向量,rand為[0,1]隨機數組成的向量.

1.2.3 全局最優解變異

全局最優解作為重要的信息源會影響整個群體的走勢,但在種群迭代后期,全局最優解難以被更新,易導致算法停滯.因此,本文借鑒2-opt 方法對全局最優解進行變異,通過讓種群內鄰域解參與到信息交互中,從而增加種群的多樣性,有助于算法在迭代后期跳出局部最優.其更新公式表達如下：

其中,Xg表示全局最優位置,d表示優化空間的維度.

根據文獻[11]提出的通過計算種群的多樣性度量值來評測種群多樣性的方法,在DSFLA 算法中引入全局最優解變異策略,利用式(13)計算的其種群的多樣性度量值,并將結果與標準SFLA 算法做對比,對比結果如圖3所示.

圖3 種群多樣性度量

其中,Tmax表示最大迭代次數,N表示種群規模,D表示數據維數,xtij表示迭代t次第i個種群的第j個分量,表示所有種群的第j個分量的平均值.上述間距公式,Q(t)表示種群多樣性度量值,其值越大表示種群平均間距越大,種群多樣性越大.

由圖3可知,隨著迭代次數的不斷增加,DSFLA算法種群多樣性度量值逐漸趨向于比SFLA 算法較大的一個值,因此DSFLA 算法的種群性多樣性更大.

1.2.4 離散化原理

由于實際工程應用中所計算的變量都是離散的,因此,本文提出一種離散二進制蛙跳算法編碼方式對青蛙位置進行離散化處理.為了保證迭代過程中青蛙的位置只能取0 或1,通常使用Sigmoid 函數[12]將位置壓縮到[0,1]區間,其公式如式(14)、式(15)所示,式(14)中的矩陣運算需用到“./”.利用標準Sigmoid 函數對青蛙個體位置映射的結果如圖4所示,可以看出,映射結果大都集中在0.35～0.65 之間,若直接用標準Sigmoid 函數對映射結果離散化處理,則個體容易產生“靠攏”現象,會導致算法陷入局部最優,過早停滯.

為了提高算法的搜索能力,本文通過對最優位置和當前位置的差值進行映射,同時建立跳躍步長D與位置轉換概率間的關系來改進Sigmoid 函數；映射結果如圖5所示,可以看出,映射結果值分布在0～1 之間,更好的保證了離散化后個體的多樣性,為算法的優化過程奠定了多樣性基礎.改進后的Sigmoid 函數公式表達如下：

其中,xg表示當前最優位置,x表示位置向量,D表示跳躍步長,VarS ize表示維數大小.“./”和“.*”表示矩陣運算,在計算中保持矩陣維度一致.

圖4 標準Sigmoid 函數

圖5 改進Sigmoid 函數

1.3 離散混合蛙跳算法

離散混合蛙跳算法(DSFLA)的具體操作步驟如算法1 所示.

算法1.離散混合蛙跳算法1.初始化參數(種群規模N,族群數m,維數D,局部搜索次數L,最大迭代次數Tmax)；2.隨機生成初始青蛙種群；for t=1:Tmax 3.4.應用式(6)、式(7)更新參數,計算每個個體 的適應度值F,按照適應度值降序排列,并進行族群劃分；for j=1:L α,A xi 5.

6.7.計算第i 個族群的局部最優解xib,局部最劣解xiw,全局最優解xg；if |A|≤1 for i=1:m 8.x′iw 9.應用式(6)～式(9)得到新的；10.else x′iw 11 應用式(6)～式(9)得到新的；12.end if x′iw x′iw 13.應用式(15)～式(17)對更新后的個體 進行離散化處理,得到新的；if F(x′iw) better than F(xiw)14.xiw=x′iw 15.else 16.x′iw 17.應用式(3)、式(4)得到新的；x′iw x′iw 18.應用式(15)～式(17)對更新后的個體 進行離散化處理,得到新的；if F(x′iw) better than F(xiw)19.xiw=x′iw 20.else 21.x′iw 22.應用式(10)、式(11)得到新的；x′iw x′iw 23.應用式(15)～式(17)對更新后的個體 進行離散化處理,得到新的；xiw=x′iw 24.end if 25.

26.end if 27.end for 28.end for xg x′g 29.應用式(12)對全局最優解 進行變異,得到新的；if F(x′g) better than F(xg)30.xg=x′g;31 F(xg)=F(x′g)32.；33.end for end if 34.

2 實驗仿真測試

本文選用了9 個常用的基準測試函數[13]如表1所示.將離散混合蛙跳算法(DSFLA),同基本混合蛙跳算法(SFLA)[1],鯨魚優化算法(WOA)[14],灰狼算法(GWO)[15],飛蛾撲火算法(MFO)[16],布谷鳥算法(CSA)[17],蝙蝠算法(BAT)[18],多元宇宙算法(MVO)[19],粒子群算法(PSO)[20],烏賊算法(CFA)[21]9 種優化算法進行實驗對比.參數設置如表2所示,最大迭代次數為100,種群數為60,重復10 次,采用平均值(mean),標準差值(std)以及迭代中的最優值(best)來評價算法的性能.

表1 基準測試函數

表3為10 種優化算法在9 個測試函數中的實驗結果對比.圖6～圖14為對應的迭代圖.以最優值和平均值為評判標準,通過比較10 種算法的優化結果可知,在函數參數條件設定相同的情況下,DSFLA 尋優結果最好.上述實驗結果主要原因是DSFLA 引入擾動系數更新策略來隨機選取族群最優解的位置作為最劣解的跳躍方向,可以更好的平衡算法在不同迭代時期的全局搜索和局部開發能力,使青蛙可以更快的靠近食物；同時將擾動系數作為閾值,引用螺旋更新位置來改進族群內個體更新策略,對最優解位置附近進行精細搜索,使青蛙能夠更準確的找到食物的位置,從而提高了算法局部搜索的精度.

以方差為評判標準,DSFLA 的收斂精度和方差都較優于其它9 種算法.實驗結果主要原因是在迭代過程中,其它個體會逐漸集中在最優個體的位置附近,導致算法過早停滯；DSFLA 算法通過全局最優解變異的方式增加種群的多樣性,避免青蛙個體全部聚集在某個局部最優位置；同時采用隨機搜索策略,提高算法的全局搜索能力.

綜上所述,針對標準混合蛙跳算法在求解高維復雜函數時存在收斂精度低和尋優速度慢等問題,本文采用的改進的策略能夠明顯提高了DSFLA 算法的收斂速度和尋優性能.

表2 算法參數設置

表3 實驗結果對比表

圖6 F1 迭代圖

圖7 F2 迭代圖

圖8 F3 迭代圖

圖9 F4 迭代圖

圖10 F5 迭代圖

圖11 F6 迭代圖

圖12 F7 迭代圖

圖13 F8 迭代圖

圖14 F9 迭代圖

3 基于DSFLA 的油田措施方案優化

本文以年度利潤和累積利潤投入比最大為目標函數,建立油田措施規劃模型,通過和其它9 種算法優化結果進行對比,分析DSFLA 在優化油田措施規劃中的性能.

3.1 實驗油田措施規劃數學模型

(1)目標函數

油田措施規劃問題是在滿足油田開采的約束條件的前提下,分配開采井組,使油田的年度利潤和累積利潤投入比最大,其目標函數如下：

式中,F1是年度利潤,F2是累積利潤,N為井數目,K為措施數,a,b,c分別是噸油成本、噸水成本、噸液成本,d為遞減率,t為開發時間,x1ij為第i口油井第j個措施的年度增油量,y1ij為第i口水井第j個措施的年度增油量,z1ij為第i口井第j個措施的年度增液量,w1ij為 第i口井第j個措施的年度增注量,x2ij為第i口油井第j個措施的累積增油量,y2ij為第i口水井第j個措施的累積增油量,z2ij為第i口井第j個措施的累積增液量,w2ij為第i口井第j個措施的累積增注量,priceij是第i口井措施數為j的價格.

(2)約束條件

1)措施增油量約束

式中,to是油井增油目標,取值為7.1×104t,te是水井增油目標,取值為7.5×104t,? 為誤差百分比,取值為0.03.

2)措施增液量和增注量約束

式中,tl是 增液量上限,取值為18×104t,ti是增注量上限,取值為30×104m3.

3)措施數上限約束

式中,Limitij是采油井的措施數上限.

3.2 實驗分析

為驗證所提算法在求解油田措施規劃模型中的性能,本章采用10 種優化算法針對2490 口措施井進行方案分配.算法的參數設置如表1所示,最大迭代次數為1000,種群大小為100,實驗結果如圖15,圖16所示.圖15,圖16表示的是10 種優化算法迭代情況圖.表4,表5表示10 種優化算法得到的最優值、最差值、平均值和標準差.

圖15 年度利潤對比圖

圖16 累積利潤對比圖

由表4和表5的實驗結果可知,從最優值、最差值方面來看,DSFLA 得到的優化結果最好.在迭代過程中,DSFLA 算法引入擾動系數更新策略,更好的調控族群內最劣解和最優解之間的距離；并將擾動系數作為閾值,使用基于族群最優解的個體更新位置和螺旋更新位置兩種策略,精細算法的局部搜索能力；此外,為了增加種群多樣性,采用全局最優解變異的方式；同時,采用隨機搜索策略來提高算法的全局搜索能力；為了保證離散化處理后青蛙種群的多樣性,采用改進的Sigmoid 函數離散化位置向量,避免種群的多樣性不會在離散化處理后突然驟減,提高了算法跳出局部最優的能力.

從標準差和平均值方面可知,DSFLA 算法相較于其它算法有較好的穩定性.此外,從圖15和圖16中可知,相較于其它算法,CSA 算法最早陷入局部最優,BAT、GWO、MFO、WOA 和PSO 算法在600 代左右停滯,SFLA 算法在700 代以后也不再變化,而DSFLA算法的收斂曲線在700 以后仍有上升的趨勢,由于最優解變異和隨機搜索策略提高了DSFLA 在迭代后期跳出局部最優能力,并且擾動系數更新策略擴大DSFLA算法的搜索空間,因此同其他9 種算法相比,DSFLA可以得到高質量的解.

綜上所述,DSFLA 算法在求解油田措施規劃模型時,能夠顯著提升油田開采的經濟效益.

4 結論與展望

本文提出一種離散混合蛙跳算法(DSFLA),該算法引入擾動系數、螺旋位置更新策略、隨機搜索策略以及全局最優解變異策略來對標準混合蛙跳算法的更新策略進行改進,此外，為了讓改進的算法更適合求解離散優化問題,利用改進的Sigmoid 函數對位置進行離散化處理.通過9 個基準測試函數的實驗結果表明了改進策略的高效性,并成功的將其應用到油田措施規劃模型優化問題中,結果表明,與其它9 種算法的優化結果相比,DSFLA 算法求解質量更優.今后將進一步研究本算法在其它工程領域的應用.