遺傳算法非線性方程組的研究范文

本站小編為你精心準備了遺傳算法非線性方程組的研究參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《電子科技雜志》2014年第五期

1遺傳算法求解非線性方程組的改進

1.1搜索空間方面的改進搜索空間是遺傳算法求解非線性方程組中由定義域D決定的一個或多個范圍。搜索空間的大小，在一定程度上決定了求解的效率。曾毅［6］提出了一種將種群中的個體按照適應值從大到小排列，根據前N位個體變量的對應二進制編碼最高位與最優解對應的二進制編碼的最高位是否相同的情況，對搜索空間進行縮小和移動的方法。該方法使得每個變量對應的二進制編碼長度無需過長，便可求出高精度的解。成媛媛等提出了根據歷代最優解將搜索區間不斷劃分成較小的區間，不斷在各個小的搜索區間遞歸地調用動態自適應遺傳算法，直到達到精度要求或小區間寬度為零停止的方法。這一方法較好地克服了傳統方法的局限性，能夠在較大的初始區間上以概率為1搜索到區間內的全部解，并能較好地實現并行計算，大幅提高了一般遺傳算法求解非線性方程組的收斂速度和穩定性。排新穎等提出了一種梯度的變異步長，即在迭代開始時使用大的步長來進行全局尋優，在后期基本確定真正解的區間時，采用較小的步長進行局部細化搜索。從上述文獻來看，在搜索空間方面的改進，主要以動態縮小搜索空間等為主。縮小了搜索空間，意味這提高了求解的速度。因此，這些改進將是對基本遺傳算法求解非線性方程組的一種有效補充。

1.2編碼方面的改進綜上所述，在基本遺傳算法求解非線性方程組的過程中，采用了二進制編碼。其在程序上易于實現，但實踐發現，該編碼也帶來了編碼和解碼誤差等問題。因此，曾毅，彭靈翔［10］均提出了在求解過程的編碼環節使用實數編碼來替代二進制編碼，從而省略了復雜的編碼和解碼過程。實數編碼雖使得設計和分析難度增加，但通用性較好，可方便地表示范圍較大的數，便于在較大的空間進行搜索，同時也改善了遺傳算法的計算復雜性，提高了運算效率。傳統二進制編碼存在Hamming懸崖問題。對于二進制編碼方法表示的個體，變異操作有時雖只是一個基因座的差異，而對應的參數值卻相差較大。但若使用格雷碼來對個體進行編碼，則編碼串之間的一位差異，對應的參數值也只有微小的差別。這就相當于增強了遺傳算法的局部搜索能力，便于對連續函數進行局部空間搜索。因此AngelFernandoKuri－Morales采用格雷碼，取得了較好的使用效果。

1.3傳算子方面的改進在使用遺傳算法求解非線性方程組時，一般會使用到選擇、交叉和變異3個算子。選擇算子一般通過賭輪法，交叉和變異操作一般采用根據經驗所得的固定概率。羅亞中等在算子設計時以聯賽競爭算子為選擇算子，該算子可直接通過比較個體的目標函數值完成操作，因此該文的遺傳算法適應度函數直接選擇為優化目標函數。文中采用了最優保存策略，即當前群體中最優個體不參與交叉運算和變異運算，而是用其來替代本代群體中經過交叉、變異操作后所產生的最差個體。胡小兵等通過設計特定的交叉概率和變異概率函數，實現了交叉概率Pc和變異概率Pm的動態改變，從而增加求解過程中算法的進化能力和收斂速度。田巧玉等采用了啟發式交叉的方式，使用參數“Ratio”指定子輩離較好適應度的父輩有多遠。如:父輩是parent1和parent2，而parent1有較好的適應度，則啟發式交叉生成的子輩如下child=parent2+Ratio*(parent1－parent2)(4)該文中還采用了Gaussian變異算子。此變異算子在進行變異操作時，將一正態分布、具有均值的隨機數加入到父向量的每一項，替換原有的基因值。該Gaussian變異算子由兩個參數“Scale”和“Shrink”決定。

針對采用非線性排序，排序的結果通常易陷入局部解。徐紅提出了設置參數r，將適應值差別因素以r的比例加入到選擇中，能改善搜索性能。參數r的設計及由此得到的交叉概率p''''如下交叉前排序的作用使相鄰個體的適應度差別最小，特性相對集中。即采用先排序后交叉可能帶來兩種效果:(1)加快收斂速度。(2)形成未成熟收斂。希望出現的是前一種情況，因而在搜索初期采用交叉前排序的操作以期提高搜索效率。彭靈翔等在變異算子上使用了最佳個體保留算子和滅絕與移民算子。采用最佳個體保留算子是一種常見的做法，可將有最好適應度的染色體群作為種子傳到下一代。滅絕與移民算子在當交配池中的染色體幾乎相同時，或最佳個體的適應度在一定代數內的增幅小于門檻值時起作用。滅絕與移民過程一般分為兩部分，開始將最佳染色體之外的染色群全部滅絕。然后移民產生Np－1個新的染色體。移民過程是:從第2個到Np/2個染色體用產生初始種群的方法產生父輩染色體。其余染色體用最佳適應度的染色體通過變異產生。綜上所述，對于算子的改進，主要采用動態變化來替代固定概率的方式。無論哪種改進，均以加快收斂速度和防止早熟為主要目的。從各文獻提供的實驗數據來看，均取得了一定的效果。

2混合遺傳算法求解非線性方程組

混合遺傳算法求解非線性方程組主要是通過遺傳算法與其他算法相結合等手段來求解的。

與經典迭代方法的混合遺傳算法中的雜交算子和變異算子能在全變量空間內搜索方程組的解，經典迭代方法能在收斂點附近局部細致地搜索解。若能將兩者混合，有可能發揮好兩類算法各自的優勢而取得更好的求解效果。目前文獻中主要提出了兩類混合策略。(1)將經典迭代方法作為算法的一個遺傳算子。趙明旺采用牛頓迭代算法與遺傳算法結合的混合算法求解非線性方程組，其混合策略是:對子代群體中每個個體以概率Pn進行牛頓算子迭代搜索，產生的新迭代值取代父代加入子代群體。該文認為確定牛頓算子概率Pn的大小需考慮的因素為:1)所求解的非線性方程組牛頓法迭代過程的收斂性。若其迭代過程收斂較快，則相應的Pn可取較小值。否則，則取較大值。2)預定的繁殖代數。若預定的繁殖代數較大，則相應的Pn可取小一些。否則，取大一些。

進一步地，趙明旺在文獻中將上述思想推廣運用至求解相容非線性方程組問題，即求解方程數與變量數可能不一致的情況。羅亞中等，屈穎爽均提出了將擬牛頓法與遺傳算法相結合的混合算法求解非線性方程組。文獻依據自適應混合算子概率Pn對群體利用擬牛頓法進行局部搜索，此文設計了兩類混合算子:擬牛頓迭代混合算子和Powell混合算子，并進行了分析比較。擬牛頓混合算子的構造方法是:以被選中個體的染色體為初始點進行擬牛頓迭代操作，若算法收斂則以收斂點作為個體新的染色體，若不收斂則不改變個體的染色體。Powell混合算子的構造方法是:以個體的染色體為初始點進行Powell尋優計算，以優化結果作為個體新的染色體。而文獻的中心思想是只對每一代的最優個體利用擬牛頓法進行精細局部搜索。其文中認為自適應混合算子概率Pn應該隨著進化的增加而變大，最后趨近于一個常數P0，因此提出了如下公式其中，T為遺傳算法中設置的最大代數;t為當前進化代數;常數P0∈(0，1］反映了局部強搜索算子對每個個體的最大可能作用程度。P0大則混合算子對遺傳算法搜索空間的局部開采愈充分，但相應的計算成本愈大，此文選擇P0=0.10。屈穎爽將知名的擬牛頓法—BFGS方法與遺傳算法進行混合，其混合策略與趙明旺的一致，即對子代群體中每個個體以概率Pn進行擬牛頓算子迭代搜索產生的新迭代值取代父代加入子代群體。值得注意的是此文利用有限Markov理論建立了基于基本遺傳算法與BFGS算法的混合算法的全局收斂性定理，即證明了保留當前最好解的混合算法收斂到全局最優解。王鵬進一步改進了屈穎爽的工作，主要體現在兩個方面:(1)擬牛頓迭代步驟中，首先計算每個體的適應值，從中選擇性能好的個體按一定的概率進行擬牛頓迭代。(2)對個體的擬牛頓迭代僅進行一次，在取得良好效果的同時節省了計算量。排新穎等考慮將梯度法與遺傳算法混合，其主要思想是用梯度對最優個體進行局部尋優。選擇的下降方向是待優化函數負梯度方向，設置一個步長L，在當前點進行局部尋優:若尋優后的函數值小于原來函數值的λ(λ＜1)倍，則尋優成功，更新當前個體，否則L=Lμ，直到L小于一個設定的值。

曹春紅等將幾何約束問題轉化為非線性方程組的形式，并用牛頓迭代算法與遺傳算法結合的混合算法求解，取得了較好的效果，其混合策略與趙明旺一致。周麗等提出了一種混合小生境遺傳算法與擬牛頓算法求解非線性方程組的新方法，其混合策略與羅亞中等一致。對于由小生境遺傳算法產生的一代種群，除最優個體外以一定的概率Pn選擇其中的個體采用擬牛頓法進行局部尋優，如果尋優后的個體適應度值高于尋優前的適應度值，以優化的結果替換尋優前的個體，否則說明此個體不收斂，不進行替換操作。

3采用經典迭代方法進行求解

C.L.Karr等提出了一種求解非線性方程組的混合算法，此法中遺傳算法主要為牛頓迭代算法提供好的初值。此文以求取Gauss－Legendre求積公式節點與系數形成的非線性方程組為典型例子，說明了牛頓迭代算法對求解此類方程組時對迭代初始值高度敏感，而混合算法的求解效果相當不錯。田巧玉等在實現遺傳算法與擬牛頓法相結合的思路是:在應用遺傳算法進行優化設計的基礎上，采用擬牛頓法進行二次優化，將獲得的結果作為最優的設計結果，即首先運行遺傳算法，找到最優點附近的一個點，將它作為擬牛頓法的初始點，以找到目標函數的最小值。此文給出了遺傳算法迭代終止條件有兩個:一是進化到指定的最大代數;另一個是適應度限，即當前代的最佳適應度值小于或等于規定的值時就停止。吳國輝等考慮到遺傳算法全局群體搜索能力及該算法在起始搜索階段速度非常快的特點，提出先用遺傳算法進行n步迭代，直至其收斂結果滿足預期要求，進入擬牛頓法的收斂域之內，然后將遺傳算法迭代結果作為擬牛頓法迭代初始值繼續迭代至精確解。此文對遺傳算法迭代的控制辦法是當前群體平均適應度小于等于預先設定的精度值。

3.1與其他智能算法的混合遺傳算法是模仿自然選擇和遺傳機制的一種智能優化算法，研究者已將其與其他智能算法如模擬退火算法等進行混合，或者融入如量子計算原理、生物免疫思想等以構造出更具優勢的新的智能算法。

3.2遺傳退火算法模擬退火算法是由Metropolis等基于熱力學的退火機制提出來的一種對退火過程進行模擬的算法。遺傳算法具有較強的全局搜索能力但容易陷入早熟，而模擬退火算法具較強的局部把握能力，但全局搜索能力不足。因此對兩者取長補短的遺傳退火算法應運而生，并成功用于全局優化問題的求解。付振岳等將遺傳退火算法進一步加以改進并應用到含有超越函數的非線性方程組的求解。

3.3量子遺傳算法

量子遺傳算法由Narayanan等人最早提出的，并經Han等人發展的一種基于量子計算原理的概率優化方法，其用量子位編碼來表示染色體，用量子門作用和量子門更新來完成進化搜索，具有種群規模小、全局尋優能力強的特點，已成功用于求解TSP與0－1背包等問題，獲得了比傳統遺傳算法更好的效果。杜娟等提出了一種基于混合量子遺傳算法的非線性方程組求解方法。為克服量子遺傳算法的求解精度低和加強局部搜索能力，采用擬牛頓法作為一個強局部搜索算子，把量子遺傳算法的尋優結果作為擬牛頓法的初值，取得了較好的效果。徐紅提出了一種改進量子遺傳算法求解非線性方程組的新方法，結果表明此法具有較高的收斂可靠性及較高的精度，對于非線性方程組求解問題具有良好的適應性，特別是一些很難求解的方程組，利用此方法求解更有意義。

3.3免疫遺傳算法免疫遺傳算法是近年來基于生物免疫機制提出的一種新的智能計算算法，其將生物免疫系統的學習、記憶和多樣性的特點引入遺傳算法。由于兼顧了搜索速度、全局搜索能力和局部搜索能力，免疫遺傳算法正成為優化設計領域的研究熱點之一。王景芳等提出了一種烴類蒸汽轉化反應器物料衡算的非線性方程組的免疫遺傳算法求解方法，取得了良好的效果。該算法由于在遺傳算法的基礎上引入了高斯變異和基于抗體濃度的更新策略調節機制，能有效地保持抗體的多樣性，從而避免了遺傳算法中存在的早熟收斂問題。

4并行遺傳算法求解非線性方程組

遺傳算法具有并行性，其按并行方式搜索一個種群數目的點，而不是單點。其的并行性表現在以下兩個方面:一是內在并行性，本身適應大規模并行。最簡單的并行方式是讓若干臺甚至是數千臺計算機各自進行獨立種群的演化計算，運行過程中甚至不進行任何通信，等到運算結束時才通信比較，選取最佳個體。這種并行處理方式對并行系統結構并無任何限制和要求，即遺傳算法適合在目前所有的并行機或分布式系統上進行并行處理，尤其適用現在PC機多線程多進程的并行計算。二是遺傳算法的內含并行性。由于遺傳算法采用種群的方式組織搜索，因而可同時搜索解空間的多個區域，并相互交流信息。使用這種搜索方式，雖然每次只執行與種群規模n成比例的計算，但實質上已進行了大約O(n3)次有效搜索，這就使遺傳算法能以較少的計算獲得較大的收益。目前并行遺傳算法的實現方案分3類:主從式模式(Master－SlaveModel)、粗粒度模型(Coarse－GrainedModel)和細粒度模型(Fine－GrainedModel)。并行遺傳算法正廣泛應用于各個領域，已有人將并行遺傳算法用在非線性方程組求解上。劉燦文等提出一種自適應并行遺傳算法:采用粗粒度模型，將初始種群分為3個子種群，并讓這3個子群體按照特點互補的演化規律在并行機的3個進程上分別進化，定期移植或交換部分優秀個體。其中進程0為主進程，主要任務之一是保存自身進化而得的優秀個體并吸收另外兩個進程進化而得的優秀個體，使不遭受破壞，目的在于保持優秀個體的多樣性。對交叉和變異概率針對不同進程、不同階段設置不同的值，來提高進化效率，如進程0中的子群體在進化中具有較低的交叉率和變異率，使得優秀個體不易被破壞，而對進程1和進程2用較高的交叉率和變異率，尤其在進化后期，用以探測新的超平面上的優秀個體，不斷為進程0提供新的超平面上的優秀個體，防止進程0“早熟”并加快其收斂到全局最優的速度。付振岳等［35］針對一些復雜的含有三角函數或是對數的非線性方程組用遺傳算法進行求解，由于該類問題涉及的求解空間大，遺傳算法需要更大的初始化種群，為提高算法的性能，引入了并發機制和最大堆來提高硬件利用率和降低某些關鍵步驟的時間復雜度。根據CPU的利用率和計算等待時間的比率以及CPU的個數，設置合適的線程數，采用細粒度模型，將種群根據線程數分割成相應的組群，每個線程對組群先后進行堆初始化→交叉→堆初始化→變異→堆初始化→淘汰等操作，設置一個全局變量記錄全體線程在執行遺傳退火算法中產生的最優個體，每個線程在完成一輪遺傳退火行為后，將本組群的最優值與全局最優值進行比較，若本組群最優值優于全局最優值，則用本組群最優值替換全局最優值，反之，則用全局最優值替換本組群最優值。該算法有效地提高了遺傳退火算法的性能，加快了求解的速度。

5結束語

文中分析了遺傳算法求解非線性方程組的研究現狀。從所列的文獻看，大部分的研究工作主要集中在對遺傳算法求解線性方程組各個環節的改進中，也有不少學者提出了遺傳算法與其他智能算法混合使用來求解的方法，比如模擬退火算法、量子計算原理等。還有眾多研究者結合了計算機多處理器技術和并行運算技術，提出了并行遺傳算法這一新概念。從現有遇到的問題看，對該問題的研究尚有不足，需對其進行深一步的研究。未來的工作，可包括兩個方面:一在現有模型基礎上，研究如何將遺傳算法與局部優化方法結合，以便有效提高解的質量。另一方面朝并行模型混合化方向研究。可以預期，隨著計算機技術的進步和生物學研究的深入，遺傳算法求解非線性方程組將更具通用性和有效性。

作者：吳龍任紅民畢惟紅單位：杭州科技職業技術學院信息工程學院浙江大學數學系科學與工程計算研究所