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

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

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

1遺傳算法求解非線性方程組的改進(jìn)

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

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

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

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

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

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

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

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

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

3采用經(jīng)典迭代方法進(jìn)行求解

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

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

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

3.3量子遺傳算法

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

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

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

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

5結(jié)束語

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

作者：吳龍任紅民畢惟紅單位：杭州科技職業(yè)技術(shù)學(xué)院信息工程學(xué)院浙江大學(xué)數(shù)學(xué)系科學(xué)與工程計(jì)算研究所