【文章內(nèi)容簡介】 自然界生物優(yōu)勝劣狀的進(jìn)化過程：群體中個(gè)體的適應(yīng)度越 高，其生存的機(jī)會就越多，而通過交叉，變異等操作，在下一代中產(chǎn)生了適應(yīng)度更高或者說性能更好的個(gè)體。在這一過程中，雖然隨機(jī)處理有助于這種優(yōu)化過程，但真正的原因和機(jī)制是什么？為何遺傳算法所依賴的基本遺傳操作，即選擇，交叉，變異能使遺傳算法體現(xiàn)出其它算法所沒有的魯棒性，自適應(yīng)性和全局優(yōu)化等特點(diǎn)？ Holland 提出的模式定理奠定了深入研究這些問題的理論基礎(chǔ)（見附錄 A：遺傳算法的理論基礎(chǔ) —— 模式定理）。 遺傳算法利用了生物進(jìn)化和遺傳的思想，與傳統(tǒng)的搜索方法相比較，它采用了許多獨(dú)特的方法和技術(shù)。主要有： （ 1）遺 傳算法不是直接作用在解空間上，而是利用解的某種編碼表示。這一特點(diǎn)，使遺傳算法具有廣泛的應(yīng)用領(lǐng)域。 （ 2）遺傳算法是采用同時(shí)處理群體中多個(gè)個(gè)體的方法，即同時(shí)對搜索空間中多個(gè)解進(jìn)行評估，并行的“爬”多個(gè)峰。這一特點(diǎn)使遺傳算法具有較好的全局搜索能力，減少了陷入局部優(yōu)解的風(fēng)險(xiǎn)。同時(shí)，這使遺傳算法本身也十分易于并行化。 （ 3）遺傳算法只使用解的適應(yīng)度函數(shù)（目標(biāo)函數(shù)）信息進(jìn)行搜索，而不需要導(dǎo)數(shù)或其它輔助信息。遺傳算法的這一特點(diǎn)使它幾乎可以處理任何問題。 （ 4）遺傳算法不是采用確定性規(guī)則，而是采用概率的變遷規(guī)則來指 導(dǎo)它的搜索方向。但遺傳算法采用概率僅僅是作為一種工具來引導(dǎo)其搜索過程朝著搜索空間的更優(yōu)化 恒泰艾普石油 天然氣 技術(shù) 服務(wù)股份 有限公司 SAGA 技術(shù)手冊 15 的解區(qū)域移動。因此雖然看起來它是一種盲目搜索方法，但實(shí)際上有明確的搜索方向。 盡管遺傳算法比其它傳統(tǒng)方法有更強(qiáng)的魯棒性，但它更擅長全局搜索而局部搜索能力不足。 1993 年 Kreinovich 等人研究發(fā)現(xiàn)，標(biāo)準(zhǔn)遺傳算法存在著進(jìn)化過程變慢的問題。它可以用極快的速度達(dá)到最優(yōu)解的 90% 左右，但要達(dá)到真正的最優(yōu)解則要花費(fèi)很大的時(shí)間。 1990 年 Kitano 經(jīng)過對比實(shí)踐指出：如果兼顧收斂速度和解的品質(zhì)兩個(gè)指標(biāo)，單純的遺傳 算法未必比其它搜索方法更優(yōu)越。實(shí)際上，如果控制群體向某個(gè)或幾個(gè)個(gè)體集中的速度過快，則求得全局極值的概率將變小，如果過慢，遺傳算法則退化為 Monte Carlo 完全隨機(jī)試驗(yàn)算法。 四、目標(biāo)函數(shù)的確定 全局尋優(yōu)求解大靜校正過程中的目標(biāo)函數(shù)是疊加能量，由于實(shí)際的地震記錄排列有限，因此 計(jì)算疊加能量的變化可采用局部計(jì)算，不需要重新疊加所有的 CMP 道集，只需要重新疊加那些與修改的炮點(diǎn)靜校正或檢波點(diǎn)靜校正有關(guān)的 CMP 道集，即炮點(diǎn)靜校正 is 只直接影響所有共中心點(diǎn) y 中的子集iS?的疊加能量，檢波點(diǎn)靜校正 jr 只影響jr?的疊加能量。涉及到 is 的疊加能量為： ? ? ? ? ? ?? ?? ? ??? ?? ?????? ???iSi y t h hyjhyiyhiS rstdsE2 (9) 而其它的炮點(diǎn)靜校正 ks , jk? 和 jr 保持不變。同樣地涉及到 jr 的疊加能量為： ? ? ? ? ? ?? ? 2? ? ??? ?? ?????? ???jrj y t hyjhyih yhjr rstdrE (10) 而 kr , ik? 和 is 保持不變。計(jì)算 ? ?is sEi 和 ? ?jr rEj 比炮點(diǎn)靜校正和檢波點(diǎn)靜校正同時(shí)修改時(shí)的計(jì)算要簡單。 對一個(gè) CMP 道集而言， f（ t）是和炮點(diǎn)（或檢波點(diǎn)） i 有關(guān)的記錄道， h（ t）是其余道的疊加道。將與炮點(diǎn)（或檢波點(diǎn)） i 有關(guān)的記錄道串聯(lián)構(gòu)成一個(gè)長的記錄道 F（ t），并將相對應(yīng)的疊加道串聯(lián)構(gòu)成一個(gè)長的疊加道 H（ t），則由炮點(diǎn)（或檢波點(diǎn)） i 處的時(shí)移τ引起的能量變化的為 ? ? ? ?? ?? ? ? ?)()(2)()()(222tHtFtHtFtHtFEttt??????????????? (11) 恒泰艾普石油天然氣技術(shù)服務(wù)股份有限公司 SAGA 技術(shù)手冊 16 上式在優(yōu)化算法中既作為模擬退火的能量函數(shù)，又作為遺傳算法中的適應(yīng)度函數(shù)來使用。 五、溫度更新函數(shù)的選取 模擬退火算法的性能主要取決于控制溫度下降過程的溫度更新函數(shù)，溫度更新函數(shù)的確定不僅與優(yōu)化問題的本身有關(guān)，而且與產(chǎn)生隨機(jī)變量的概率密度函數(shù)有關(guān)。在實(shí)際中一般都是根據(jù)概率密度函數(shù)按照某種啟發(fā)式方法確定適當(dāng)?shù)臏囟雀潞瘮?shù)。 模擬退火算法同其它啟發(fā)性隨機(jī)搜索方法的搜索過程一樣，首先按照一定的概率分布在較大的范圍內(nèi)隨機(jī)地產(chǎn)生試探點(diǎn)，以實(shí)現(xiàn)大范 圍的粗略搜索，然后逐步縮小隨機(jī)產(chǎn)生試點(diǎn)的范圍，使搜索過程逐漸變?yōu)榫植康木?xì)搜索。模擬退火算法就是通過適當(dāng)?shù)乜刂茰囟鹊淖兓^程實(shí)現(xiàn)大范圍的粗略搜索與局部的精細(xì)搜索相結(jié)合的搜索策略。 由于發(fā)生隨機(jī)變量的概率密度函數(shù)以及接收試探點(diǎn)為新的當(dāng)前迭代點(diǎn)的接受概率都和溫度有關(guān)，所以，當(dāng)溫度較高時(shí)，隨機(jī)產(chǎn)生的試探點(diǎn)的散布范圍較大，并且能夠以較大的概率接受使目標(biāo)函數(shù)值增加的試探點(diǎn)，從而實(shí)現(xiàn)大范圍搜索。隨著溫度逐漸下降，隨機(jī)產(chǎn)生的試探點(diǎn)越來越集中在當(dāng)前迭代點(diǎn)的局部范圍內(nèi)，那么，在溫度較低時(shí)，模擬退火將近似于傳統(tǒng)的隨機(jī)搜索算法 ，因而一旦陷入局部最優(yōu)解將艱難逃脫出來。因此，為了提高模擬退火算法求得全局最優(yōu)解的可靠性和計(jì)算效率，一方面要保持適當(dāng)?shù)臏囟认陆邓俣?，另一方面要使產(chǎn)生的隨機(jī)變量保持一定的散布程度，使隨機(jī)產(chǎn)生的試探點(diǎn)不能都集中在當(dāng)前迭代點(diǎn)的局部范圍內(nèi)。顯然，當(dāng)產(chǎn)生隨機(jī)變量概率分布函數(shù)與溫度有關(guān)時(shí)，溫度更新函數(shù)不僅決定了溫度的下降速度，而且還決定了整個(gè)退火過程中所產(chǎn)生的隨機(jī)變量的散布程度，即溫度更新函數(shù)決定著模擬退火的全局收斂能力。 我們在遺傳算法中引入了 Boltzmann 生存機(jī)制，因此，溫度更新函數(shù)對遺傳算法搜索也具有同樣 的意義。 和 （ 1984 ）提出溫度更新函數(shù) ? ?kTTk ?? 1log/0 (12) 并以理論證明了概率分布函數(shù)呈 Boltzmann 分布時(shí) ,對數(shù)更新函數(shù)式 (12) 可使 SA 收斂于最優(yōu)解。 和 (1986) 提出溫度更新函數(shù) 恒泰艾普石油 天然氣 技術(shù) 服務(wù)股份 有限公司 SAGA 技術(shù)手冊 17 ? ?kTTk ?? 1/0 (13) 也從理論上證明按（ 13）式降溫可使 SA 收斂于全局最優(yōu)解。 Ingber(1987) 給出的溫度更新函數(shù)是 ? ?NMk kCTT /100 e x p ??? (14) 并證明其收斂性。 Rothman(1985)采用的溫度更新函數(shù)是 TK ＝ T0 α K (15) 揚(yáng)若黎和顧基發(fā) (1997) 給出了溫度更新函數(shù)為： 11 ??????? ?? kmk TkkT (16) 并證明于可收斂于全局最優(yōu) ,而且可以適當(dāng)?shù)倪x擇 m 的值可以控制溫度的下降速度。 式（ 12） — 式（ 16）式 中的參數(shù)意義分別是 T0 是起始溫度， K 為迭代次數(shù)， C0 為常數(shù)， N、 M 為參數(shù)空間的長度，α為衰減因子（ 0α 1）， m 為≥ 1 的給定常數(shù) 。 在我們的尋優(yōu)算法中，選用了（ 16）式作為溫度更新函數(shù)。式中參數(shù) 0T 和 m 的選擇是： 起始溫度 0T 的選?。撼跏紲囟鹊倪x取主要使初期搜索過程完全隨機(jī)化，而不局限于某個(gè)區(qū)域?yàn)槟康?。根?jù)尹成（ 1997）的研究和我的實(shí)驗(yàn)。 ?T 就能使概率分布值小于 ，完全能夠滿足空間搜索過程的遍歷性原則。 m 的選?。焊鶕?jù)學(xué)者的研究及我的實(shí)驗(yàn)， m 取值為 3 ，能夠較好地滿足退火要求。 我們選取的溫度更新函數(shù)，實(shí)現(xiàn)了自動確定溫度的下降速度和溫度控制，不需要作參數(shù)實(shí)驗(yàn)工作，也不需要人為確定參數(shù)。 六、退火遺傳算法的實(shí)現(xiàn) 退火遺傳算法思路 模擬退火使用基于概率的雙向隨機(jī)搜索技術(shù)并在理論上被證明是一種以概率 1 收斂于全局最優(yōu)解的啟發(fā)性優(yōu)化算法，但要經(jīng)過無限次的變化?，F(xiàn)有的遺傳算法適用范圍廣，魯棒性強(qiáng)，但缺乏較強(qiáng)的局部搜索能力，沒有判定當(dāng)前解是否達(dá)到最優(yōu)解的合理準(zhǔn) 恒泰艾普石油天然氣技術(shù)服務(wù)股份有限公司 SAGA 技術(shù)手冊 18 則（從而，沒有合理的停機(jī)準(zhǔn)則）等缺陷，因此 ，很多研究者都期望遺傳算法和模擬退火法相結(jié)合以形成更有效的算法。 和 （ 1987 年）將退火進(jìn)度引入 GA 的循環(huán)過程中，提出了熱動力遺傳算子，基本思想是遺傳算子的概率不再是一個(gè)常數(shù)，而是根據(jù)退火進(jìn)度由一個(gè) Boltzmann 分布來確定。 等人（ 1989 ）提出利用遺傳算法演化一組解，而每一演化代使用 SA 對演化解進(jìn)行局部搜索以改進(jìn) GA 的性能。劉勇等人（ 1995 ）使用類似的搜索策略。穆文全（ 1996 ）將 Motroplis 準(zhǔn)則引入到 GA 中的交叉和變異操作中，對每一個(gè)交叉和變異的后代均按一定概率接收為新一代。王雪梅等人（ 1997 ）在傳統(tǒng) GA 的生存策略中引入 Boltzmann 生存機(jī)制。尹成（ 1997 ）利用 GA 逼進(jìn) SA 中每個(gè)溫度下的準(zhǔn)平衡狀態(tài)。吳志遠(yuǎn)等人（ 1998 ）通過自適應(yīng)的退火懲罰因子提高 GA 的求解精度。 在尹成研究的基礎(chǔ)上，我們提出一種改進(jìn)的 SA 和 GA 相結(jié)合的優(yōu)化算法。其主要思想是： 1) 利用概率分布函數(shù)來產(chǎn)生 GA 的群體初值。 2) 在遺傳操作中引入 Boltzmann生存機(jī)制。 3)SA 和 GA 交替運(yùn)行 ，對 GA 的每一演化代使用 SA 對演化解進(jìn)行局部搜索以改進(jìn) GA 的性能。 ⑴利用概率分布函數(shù)產(chǎn)生 GA 群體初值 利用概率分布函數(shù)產(chǎn)生的 GA 的群體初值是引用尹成的研究成果。 對于群體中的每個(gè)個(gè)體的初值選取，遺傳算法并無明確的要求，但是某一個(gè)參變量對能量函數(shù)的重要性，可以通過概率分布函數(shù)完全反映出來。我們根據(jù)概率分布函數(shù)，隨機(jī)地產(chǎn)生該參變量的若干候選值，再隨機(jī)組成群體中每個(gè)個(gè)體的初始狀態(tài)，這使得個(gè)體初值的針對性強(qiáng)，使遺傳算法搜索具有更高效率。 ⑵在遺傳操作中引入 Boltzmann 生存機(jī)制 遺傳算法的生存策略可以 歸結(jié)為：當(dāng)新生代的適應(yīng)值 f 大于群體平均適應(yīng)值 f 時(shí)被接收。但存在著這樣的情況，例如 GA 欺騙問題，適應(yīng)值高的山峰被一些低谷所包圍（要達(dá)到山峰必須經(jīng)過低谷），即低適應(yīng)值群中也可能會包含有用的模式。因此，在遺傳搜索中也應(yīng)當(dāng)有接受差解的可能性。為此，我們在傳統(tǒng) GA 的生存策略中引入 Boltzmann生存機(jī)制：設(shè)新產(chǎn)生的適應(yīng)值為 f，群體平均適應(yīng)值為 f ，當(dāng) ff? 時(shí)，接收新個(gè)體；否則，以一定概率接受新個(gè)體，接收 概率為 ? ?? ?Tff /exp ??? ,其中 T 為溫度。 恒泰艾普石油 天然氣 技術(shù) 服務(wù)股份 有限公司 SAGA 技術(shù)手冊 19 ⑶用 SA 技術(shù)對 GA 演化解進(jìn)行局部搜索以改進(jìn) GA 性能 遺傳算法同時(shí)保持著若干個(gè)解，通過交叉和變異生成新解，一定程度上保證了解的多樣性，起到了廣泛搜索的作用，但單純的遺傳算法缺乏集中搜索的機(jī)制。因此，我們應(yīng)用模擬退火技術(shù)，在遺摶算法搜索到較優(yōu)解的基礎(chǔ)上進(jìn)行集中搜索， SA、 GA 反復(fù)重復(fù)搜索直到滿足終止條件。 退火遺傳的數(shù)值計(jì)算 合成記錄的參數(shù)是：每炮 24 道 , 端點(diǎn)放炮，共 19 炮， 12 次覆蓋， 4ms 采樣，60 個(gè) CMP 點(diǎn)，期望輸出能量 (疊加能量 )為 4146，期望疊加見圖 5。 圖 6 是對理論模型加了擾動后的疊加 , 剖面上反射同相軸全部打亂，一點(diǎn)影子都見不著。 圖 7 是擾動時(shí)移量 , 最大時(shí)移量為正負(fù) 48ms。 我們在東芝筆記本電腦 (型號 480CDT) 上用時(shí) 1270 秒， 迭代 3338 次才退出計(jì)算，收斂能量為 3633，與期望能量比為 % 。 圖 5 期望疊加 圖 6 加了擾動后 的疊加 圖 7 擾動 時(shí)移量 恒泰艾普石油天然氣技術(shù)服務(wù)股份有限公司 SAGA 技術(shù)手冊 20 圖 8 是 SAGA 的能量曲線。 圖 9 為 SAGA 法輸出的疊加剖面，形態(tài)基本正確，但產(chǎn)生了時(shí)移，即存在零空間現(xiàn)象。 圖 10 是 SAGA 法求出的靜校正與已知擾動時(shí)移的比較，求出的靜校正基本符合期望輸出。在這里需要指出的是，檢波點(diǎn)兩端靜校差異較大，是因?yàn)槎它c(diǎn)檢波點(diǎn)覆蓋次數(shù)太低所致。