張 強(qiáng), 姜慧清, 王 穎, 郭玉潔

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院, 黑龍江 大慶 163318)

0 引 言

混洗蛙跳算法[1](SFLA: Shuffled Frog Leaping Algorithm)在求解優(yōu)化問題時(shí)具有以下優(yōu)勢： 1) 采用多族群的種群結(jié)構(gòu), 使其能很好地求解具有不連續(xù)的、 非凸的、 存在局部最優(yōu)等特點(diǎn)的復(fù)雜目標(biāo)函數(shù), 且易實(shí)現(xiàn)并行計(jì)算； 2) 采用多子群全局尋優(yōu)和局部尋優(yōu)相結(jié)合的模因進(jìn)化機(jī)制, 使算法擁有較好的全局尋優(yōu)能力和快速收斂效率, 已被應(yīng)用于函數(shù)優(yōu)化[2-3]、 車間調(diào)度[4]、 故障診斷[5]、 聚類問題[6]和圖像處理[7]等多個(gè)領(lǐng)域。但SFLA在解決多模優(yōu)化問題時(shí)也存在尋優(yōu)精度低、 易于陷入局部最優(yōu)的問題。許多學(xué)者在族群多樣化[8-9]、 進(jìn)化方式改進(jìn)[10-13]和算法融合[14-15]等方面做了一些研究。分析其原因主要是由混洗蛙跳算法的分組方法與進(jìn)化方式引起的。SFLA的分組是通過適應(yīng)值降序排序后進(jìn)行分組, 導(dǎo)致最后一個(gè)子群的青蛙都不如之前子群中的青蛙, 而SFLA的進(jìn)化方式是先參照子群內(nèi)最優(yōu)青蛙, 再參照族群內(nèi)最優(yōu)青蛙, 這樣最后子群的青蛙可能需要較多的進(jìn)化計(jì)算, 并且最差青蛙進(jìn)化公式中沒有有效借鑒族群內(nèi)其他青蛙的進(jìn)化信息, 導(dǎo)致子群易于被限制在較小的尋優(yōu)空間。元胞自動(dòng)機(jī)[16](CA: Cellular Automata)是依據(jù)一定演化規(guī)則在離散時(shí)間維上同步演化的動(dòng)力學(xué)系統(tǒng), 能通過簡單的局部轉(zhuǎn)換規(guī)則模擬全局演化的復(fù)雜情況, 已廣泛應(yīng)用于社會(huì)、 經(jīng)濟(jì)和科學(xué)研究的相關(guān)領(lǐng)域[17-18]。目前元胞自動(dòng)機(jī)理論與智能進(jìn)化算法相結(jié)合方面的研究主要有元胞遺傳算法[19]、 元胞微粒群算法[20]、 元胞蝙蝠算法[21]和元胞差分進(jìn)化算法[22]等。Elbeltagi等[23]通過研究得知SFLA在求解一些離散和連續(xù)優(yōu)化問題的成功率和尋優(yōu)速度優(yōu)于遺傳算法、 模因算法和蟻群算法。筆者提出基于元胞自動(dòng)機(jī)的改進(jìn)混洗蛙跳算法(CA_SFLA: improved Shuffled Frog Leaping Algorithm based on Cellular Automata), 該算法利用元胞自動(dòng)機(jī)的鄰域結(jié)構(gòu)和演化規(guī)則保持青蛙族群內(nèi)個(gè)體的多樣性, 利用改進(jìn)的進(jìn)化方式和混沌變異方式進(jìn)化青蛙個(gè)體的3種狀態(tài), 進(jìn)而平衡局部搜索和全局尋優(yōu)的關(guān)系, 提高算法在搜索空間的尋優(yōu)速度和精度。

1 基本混洗蛙跳算法

1.1 種群初始化

混洗蛙跳算法將每只青蛙看作待優(yōu)化問題的一個(gè)解, 設(shè)定青蛙族群規(guī)模為P(P=mn), 其中m為子群個(gè)數(shù),n為子群內(nèi)青蛙個(gè)數(shù), 最大進(jìn)化代數(shù)T, 子群內(nèi)部進(jìn)化次數(shù)為t。

1.2 子群劃分

計(jì)算每個(gè)青蛙的適應(yīng)度f(X), 并按降序排序, 依據(jù)

Gk={X(j)k,f(j)k|X(j)k=

X(k+m(j-1)),f(j)k=f(k+m(j-1))}

(1)

將青蛙族群分成m個(gè)子群Gk, 每個(gè)子群內(nèi)共有n個(gè)青蛙, 具體分組示意如圖1所示。設(shè)定蛙群中適應(yīng)值最好的青蛙為Pg, 其中X(j)k為第k個(gè)分組里第j個(gè)青蛙,j=1,2,…,n;k=1,2,…,m。

圖1 蛙跳算法分組示意圖Fig.1 Schematic diagram of leapfrog algorithm grouping

1.3 子群內(nèi)青蛙進(jìn)化

設(shè)定每個(gè)子群內(nèi)最優(yōu)解為Xb, 最差解為Xw, 利用

(2)

(3)

1.4 種群信息共享及算法終止條件

每個(gè)子群分別迭代指定次數(shù)后, 如果達(dá)到群體進(jìn)化最大進(jìn)化代數(shù)T或是滿足尋優(yōu)精度, 則輸出結(jié)果; 否則將所有青蛙個(gè)體整合完成青蛙種群的信息共享, 繼續(xù)執(zhí)行子群劃分、 子群個(gè)體進(jìn)化直到滿足算法終止條件。

2 元胞混洗蛙跳算法原理

2.1 元胞自動(dòng)機(jī)的構(gòu)成

在元胞混洗蛙跳算法中, 每個(gè)青蛙作為一個(gè)獨(dú)立的元胞被放在元胞自動(dòng)機(jī)的網(wǎng)格里。此時(shí)元胞混洗蛙跳算法可以由4元組A={Ld,S,N,f}定義, 其中元素定義如下。

1)Ld表示元胞空間。從理論上講元胞空間的維數(shù)是任意的, 但隨著維數(shù)的增加空間結(jié)構(gòu)復(fù)雜度則越大, 在實(shí)際應(yīng)用中常用的是二維元胞自動(dòng)機(jī)(d=2)。

2)S表示元胞的狀態(tài)?？紤]到青蛙個(gè)體存在冬眠的生理現(xiàn)象, 筆者算法設(shè)定青蛙個(gè)體的元胞狀態(tài)有生、 休眠和死3種狀態(tài), 分別用0、1、2表示, 在算法運(yùn)行時(shí)進(jìn)行初始化。

3)N表示元胞的鄰域。常用的鄰域模型有馮·諾依曼型、 摩爾型和擴(kuò)展摩爾型(見圖2)。筆者選用摩爾型鄰域模型, 即每個(gè)元胞周圍有8個(gè)元胞青蛙個(gè)體。

a 馮·諾依曼型 b 摩爾型 c 擴(kuò)展摩爾型

2.2 元胞混洗蛙跳算法原理

2.2.1 個(gè)體狀態(tài)演化規(guī)則

筆者算法利用元胞的鄰域結(jié)構(gòu)代替基本蛙跳算法的分組方法, 進(jìn)而克服經(jīng)典混洗蛙跳算法分組的缺點(diǎn)。文獻(xiàn)[13]利用中心元胞鄰域內(nèi)個(gè)體的數(shù)量確定其狀態(tài), 而在求解具體應(yīng)用問題時(shí)則需要根據(jù)優(yōu)化問題的特征構(gòu)建元胞個(gè)體的演化規(guī)則, 否則會(huì)由于不適合的演化規(guī)則而引發(fā)生命危機(jī)。設(shè)每個(gè)元胞具有“生”、 “休眠”和“死”3種狀態(tài)。定義如下。

1) “生”狀態(tài)。如果該中心元胞青蛙個(gè)體滿足所有約束條件或鄰域周圍有滿足約束條件的青蛙個(gè)體, 則狀態(tài)設(shè)置為“生”狀態(tài)。

2) “休眠”狀態(tài)。如果該元胞青蛙個(gè)體不是鄰域所有元胞中的最差青蛙, 本身不滿足約束條件, 周圍也沒有滿足約束條件的個(gè)體, 則狀態(tài)設(shè)置為“休眠”狀態(tài), 當(dāng)周圍有滿足約束條件的元胞青蛙時(shí)被復(fù)活為“生”狀態(tài)。

3) “死”狀態(tài)。如果該元胞青蛙是鄰域所有元胞中最差的青蛙, 且不滿足優(yōu)化問題的約束條件, 周圍也沒有滿足約束條件的青蛙個(gè)體, 則置為“死”狀態(tài)。

算法運(yùn)行初始時(shí)根據(jù)元胞青蛙個(gè)體的適應(yīng)值設(shè)置相應(yīng)的狀態(tài), 此時(shí)不考慮優(yōu)化問題的約束條件。具體初始化方式如下： 1) 計(jì)算所有元胞青蛙個(gè)體的適應(yīng)值平均值, 設(shè)置元胞青蛙個(gè)體適應(yīng)值超過平均值的青蛙個(gè)體狀態(tài)為“生”狀態(tài)； 2)青蛙個(gè)體適應(yīng)值小于平均值的個(gè)體設(shè)置前一半個(gè)體的狀態(tài)為“休眠”狀態(tài), 剩下的個(gè)體設(shè)置為“死”狀態(tài)。

2.2.2 個(gè)體進(jìn)化方式改進(jìn)

經(jīng)典蛙跳算法子群最差個(gè)體在進(jìn)化過程中沒有有效借鑒族群內(nèi)其他青蛙的進(jìn)化信息, 導(dǎo)致算法在求解多維復(fù)雜優(yōu)化問題時(shí)容易落入局部最優(yōu)解。筆者所提元胞混洗蛙跳算法每次更新的是狀態(tài)為“生”或是“死”的元胞青蛙, 將該元胞青蛙與其鄰域內(nèi)的元胞青蛙構(gòu)成元胞混洗蛙跳算法的子種群, 這樣該元胞會(huì)出現(xiàn)以下3種更新狀態(tài)。

1) 狀態(tài)1。該元胞的狀態(tài)為“活”, 且該元胞是該子群的最優(yōu)值且滿足所有約束條件, 依據(jù)SFLA的進(jìn)化方式是不需要更新的, 但社會(huì)學(xué)原理研究表明, 優(yōu)秀個(gè)體的附近更易找到更優(yōu)個(gè)體, 即局部最優(yōu)青蛙個(gè)體附近有可能存在更優(yōu)的青蛙個(gè)體。筆者借鑒鯨魚算法通過模擬座頭鯨在一個(gè)縮小的圓圈內(nèi)繞著獵物游動(dòng), 同時(shí)沿著螺旋形的路徑游動(dòng)的捕食行為獲取局部最優(yōu)個(gè)體周圍的更優(yōu)個(gè)體, 按照

(4)

計(jì)算生成個(gè)體的適應(yīng)值, 如果優(yōu)于當(dāng)前個(gè)體則替換。其中Xg(t)為全局最優(yōu)青蛙所在的位置,D′=|Xg(t)-X(t)|,A=2α·r-α,p為[0,1]隨機(jī)概率,l為[-1,1]隨機(jī)概率。α在迭代過程中從2～0線性遞減；r為[0,1]隨機(jī)數(shù)組成的向量。

2) 狀態(tài)2。該元胞的狀態(tài)為“活”, 但本身不滿足約束條件, 則可以根據(jù)鄰域的滿足約束條件的個(gè)體進(jìn)行更新。首先選擇中心元胞鄰域內(nèi)滿足約束條件且適應(yīng)值最小的青蛙個(gè)體作為子群里局部最優(yōu)解Xb(t), 按照式(2)更新當(dāng)前中心元胞個(gè)體的位置, 如果適應(yīng)值有改善且滿足約束條件, 則替換當(dāng)前個(gè)體; 否則采用

(5)

更新個(gè)體。其中Xg(t)為族群最優(yōu)青蛙所在的位置。

3) 狀態(tài)3。該元胞的狀態(tài)為“死”, 應(yīng)用k階Chebyshev混沌映射對(duì)個(gè)體進(jìn)行映射, 如下

X(t+1)=cos(karccosX(t)),k≥2

(6)

其中k為偶數(shù)時(shí)產(chǎn)生的混沌映射序列隨機(jī)性更好, 生成的青蛙個(gè)體新位置呈現(xiàn)遍歷性和多樣性, 可有效地在收斂區(qū)域以外空間搜索全局最優(yōu)位置。

2.3 元胞混洗蛙跳算法流程

元胞混洗蛙跳算法流程如圖3所示。

圖3 元胞混洗蛙跳算法流程圖Fig.3 Flowchart of cellular shuffled frog leaping algorithm

3 實(shí)驗(yàn)仿真

3.1 函數(shù)極值優(yōu)化

為了深入研究SFLA_CA算法的性能(約束條件設(shè)置為元胞個(gè)體的適應(yīng)值優(yōu)于元胞鄰域內(nèi)所有個(gè)體的適應(yīng)度平均值), 將其與SFLA[1]、 MSFLA(Modified Shuffled Frog Leaping Algorition)[10]、 MSFLA1[11]、 ISFLA[12]和MSFLA2[13]進(jìn)行了比較。10個(gè)測試函數(shù)包括單峰問題和多峰問題。所有實(shí)驗(yàn)均在Intel(R)Core(TM)i7 8750H CPU雙核處理器2.20 GHz和2.21 GHz上實(shí)現(xiàn), 具有16 GByte內(nèi)存物理地址擴(kuò)展。所有算法均在Microsoft Windows 10 Professional環(huán)境下用MATLAB R2014a進(jìn)行編碼和實(shí)現(xiàn)。各算法的參數(shù)設(shè)置如下： SFLA_CA、 SFLA、 MSFLA、 MSFLA1、 MSFLA2和ISFLA的種群個(gè)數(shù)均設(shè)置為P=64, 分組個(gè)數(shù)為8, 子群內(nèi)個(gè)體數(shù)為8, 每個(gè)算法分別計(jì)算20次取平均值。測試函數(shù)如表1所示, 每種算法分別對(duì)10個(gè)函數(shù)的500維進(jìn)行優(yōu)化對(duì)比, 性能對(duì)比結(jié)果如表2所示。

表1 10個(gè)典型優(yōu)化函數(shù)

從表2可以看出, 對(duì)單峰函數(shù)F1-F3所提算法的尋優(yōu)性能效果明顯優(yōu)于其他對(duì)比算法。對(duì)多峰函數(shù)F6和F8, 即使是500維優(yōu)化也能找到全局最優(yōu)解。對(duì)函數(shù)F4、F5和F7, SFLA_CA與MSFLA2的尋優(yōu)效果相似, 但SFLA_CA的平均值和標(biāo)準(zhǔn)差要好一些。對(duì)F9和F10, SFLA_CA與其他改進(jìn)算法相比, 尋優(yōu)效果要好幾個(gè)數(shù)量級(jí)。分析其原因： 1) 利用元胞自動(dòng)機(jī)的鄰域結(jié)構(gòu)和演化規(guī)則可以降低算法的選擇壓力, 有利于保持尋優(yōu)過程中青蛙種群的多樣性, 增加迭代過程中尋找到更優(yōu)個(gè)體的幾率, 有利于避免算法陷入局部最優(yōu)解； 2) 對(duì)“生”的個(gè)體利用螺旋方式在最優(yōu)個(gè)體周圍查找更優(yōu)解加速了算法的收斂速度和計(jì)算精度； 3) 對(duì)“休眠”的個(gè)體在進(jìn)化過程中借鑒了周圍鄰域的個(gè)體, 較好地平衡了個(gè)體進(jìn)行局部尋優(yōu)和全局探索； 4) 對(duì)“死”的個(gè)體則采用混沌策略增加了種群個(gè)體的多樣性。

表2 500維函數(shù)優(yōu)化性能對(duì)比

3.2 油田措施規(guī)劃方案優(yōu)化

實(shí)際油田生產(chǎn)過程中, 有些措施的有效期可能會(huì)影響下一年的產(chǎn)量, 即當(dāng)年的投入效益會(huì)延續(xù)到下一年, 所以有必要對(duì)近幾年的措施工作進(jìn)行統(tǒng)一安排, 做到產(chǎn)出投入經(jīng)濟(jì)效益最大化。筆者以措施規(guī)劃年(文中規(guī)劃期為3年)的產(chǎn)出投入比f(X,Y)最大化為優(yōu)化目標(biāo), 以每年的規(guī)劃增油量、 增液量和增注量等為約束條件, 并考慮措施和受效增油遞減率, 可得到模型的具體形式如下

其中N為井?dāng)?shù)目,L為措施數(shù),M為措施年數(shù),k為年份,Xij為第i口油井實(shí)施措施數(shù)j,Yij為第i口水井實(shí)施措施數(shù)j,aij為第i口井實(shí)施措施j的初始日增油,bij為第i口井實(shí)施措施j的初始日增注,cij為第i口井實(shí)施措施j的初始日增液,tij為第i口井實(shí)施措施j的有效天數(shù),dij為第i口井實(shí)施措施j的本年有效天數(shù),gij為第i口油井實(shí)施措施數(shù)j的遞減率,hij為第i口水井實(shí)施措施數(shù)j的遞減率,ck為第k年的油價(jià),ek為第k年的噸油成本、rk為第k年的噸水費(fèi)用、uk為第k年的噸液費(fèi)用,pijk為在第k年的第i口井實(shí)施措施j的單價(jià),H是油井年度增油目標(biāo),J是水井年度增油目標(biāo),Q為年度增液目標(biāo),R為年度增注目標(biāo),α為誤差百分比,Lij為油井或水井的措施上限數(shù),Mij為第i口井實(shí)施措施數(shù)j的月份, [S,E]為實(shí)施措施月份的區(qū)間,vk-1為規(guī)劃前一年的措施對(duì)當(dāng)年增油量的影響,qk-1為規(guī)劃前一年的措施對(duì)當(dāng)年增注量的影響,zk-1為規(guī)劃前一年的措施對(duì)當(dāng)年增液量的影響, 計(jì)算方法即第k-1年實(shí)施某項(xiàng)措施的有效期dij減去第k-1年措施有效天數(shù)tij, 再乘以每天的增油量或是增液量或是增注量。

結(jié)合某采油廠3年的措施規(guī)劃工作, 可規(guī)劃的措施油水井共用3 283口, 每年所采取的措施及工作量上限及施工安排的月份如表3所示, 應(yīng)用SFLA_CA、 SFLA、 MSFLA、 MSFLA1、 ISFLA和MSFLA2求解油田措施模型, 算法的參數(shù)設(shè)置如同3.1節(jié), 實(shí)驗(yàn)結(jié)果如表4所示。

表3 措施上限及實(shí)施月份

從表4的實(shí)驗(yàn)對(duì)比結(jié)果可知, 對(duì)于最優(yōu)值、 最差值和平均值, 筆者所提的SFLA_CA優(yōu)化結(jié)果最好。主要原因是該優(yōu)化問題的編碼方式是將3283口井及措施的月份作為變量, 所以需要優(yōu)化的維數(shù)較高, 而筆者算法在求解高維問題時(shí)具有較快的收斂速度和尋優(yōu)精度。

表4 6種算法年度產(chǎn)出投入比結(jié)果對(duì)比

4 結(jié) 語

筆者基于元胞自動(dòng)機(jī)的優(yōu)勢提出一種求解約束優(yōu)化問題的元胞混洗蛙跳算法, 通過對(duì)3種不同狀態(tài)的個(gè)體實(shí)施不同的進(jìn)化規(guī)則加速尋優(yōu)性能, 并通過個(gè)體狀態(tài)演化規(guī)則完成個(gè)體狀態(tài)的轉(zhuǎn)變, 降低了算法的選擇壓力, 保證了尋優(yōu)過程中蛙群的多樣性。通過經(jīng)典基準(zhǔn)函數(shù)測試和油田措施規(guī)劃方案優(yōu)化效果對(duì)比, 可知筆者算法對(duì)求解高維優(yōu)化問題具有很好的適應(yīng)性。