遺傳算法及其在非線性方程組求解中的應(yīng)用研究

王愛(ài)華

(南充職業(yè)技術(shù)學(xué)院，四川 南充 637131)

1 引 言

電子信息技術(shù)和網(wǎng)絡(luò)技術(shù)飛速發(fā)展，其相關(guān)學(xué)科交叉所形成的數(shù)學(xué)模型中非線性方程組問(wèn)題日益增多，其重心可歸結(jié)為各種非線性方程組的求解問(wèn)題．目前，關(guān)于求解非線性方程組的相關(guān)理論和方法已較成熟，但對(duì)于求解方法的有效性研究卻不夠深入．主要原因在于計(jì)算上所具有的復(fù)雜性容易導(dǎo)致求解結(jié)果陷入局部最優(yōu)．本文討論了如何改進(jìn)遺傳算法以及如何利用改進(jìn)后的遺傳算法求解非線性方程組．

2 遺傳算法及其改進(jìn)

圖1 基本遺傳算法流程圖Fig.1 Flow chart of basic genetic algorithm

2．1 遺傳算法的算法流程

遺傳算法是通過(guò)模擬個(gè)體組成群體的整體狀況，進(jìn)行選擇、交叉和變異等操作，以選取搜索空間中的最優(yōu)解． 其算法過(guò)程及流程圖(圖1)分別如下:

a)設(shè)置種群的最大進(jìn)化代數(shù)T 和遺傳操作算子，然后隨機(jī)生成初始種群p(0);

b)對(duì)種群p(t)中每個(gè)個(gè)體進(jìn)行適應(yīng)度評(píng)價(jià)，并計(jì)算種群的平均適應(yīng)度;

c)根據(jù)優(yōu)勝劣汰，選擇保留優(yōu)秀個(gè)體，淘汰種群中適應(yīng)度較低的個(gè)體;

d)為生成新的個(gè)體，依據(jù)選擇概率，將種群之間進(jìn)行交叉運(yùn)算;

e)對(duì)新個(gè)體進(jìn)行交叉、變異操作，計(jì)算下一代種群p(t+1);

f)對(duì)t、T 進(jìn)行比較，若t ＞T 或等于設(shè)置精度，則這一代為最優(yōu)個(gè)體，計(jì)算終止;若t≤T，則t→t+1，從第b)步繼續(xù)計(jì)算．

2．2 遺傳算法的收斂性

評(píng)價(jià)迭代算法性能的重要指標(biāo)是收斂性和收斂速度，目前基本上都是用標(biāo)準(zhǔn)遺傳算法(又稱(chēng)S 遺傳算法)模型［1］來(lái)分析遺傳算法收斂性的各種結(jié)論．

設(shè)f(Sk*)=max{f(s(1，k)，s(2，k)，…，s(n，k))}是第k 次進(jìn)化迭代時(shí)群體{s(j，k)}中的最大適應(yīng)度值為此時(shí)的群體最優(yōu)串(若，則令，否則(s(1)，s(2)，…，S(n))}是遺傳算法所求問(wèn)題的全局最大適應(yīng)度值，全局最優(yōu)串(其中為有效基因，若在某處基因位上，群體中所有串中不存在該基因位的有效基因，則稱(chēng)群體有效基因缺失［1］)．則當(dāng)且僅當(dāng)=1 成立時(shí)，稱(chēng)遺傳算法是概率性全局收斂的．其中為的概率．

現(xiàn)已證明，如果在進(jìn)化迭代過(guò)程中，遺傳算法在保留最優(yōu)串的情況下隨機(jī)地以雜交和變異搜索算子，全局優(yōu)化問(wèn)題可通過(guò)遺傳算法持續(xù)對(duì)空間進(jìn)行搜索來(lái)完成，全局最優(yōu)解將通過(guò)1 為概率找到，該結(jié)論稱(chēng)為遺傳算法的極限分析定理［2］．

2．3 遺傳算法的不足

遺傳算法雖然具有較好的全局搜索能力，但也存在不足:一是遺傳算法的全局收斂性理論基礎(chǔ)是二進(jìn)制編碼，對(duì)于其他編碼方式還無(wú)有效證明;二是遺傳算法對(duì)搜索空間進(jìn)行持續(xù)搜索時(shí)，可能出現(xiàn)多峰優(yōu)化問(wèn)題，獲得的最優(yōu)解不一定是全局最優(yōu)解，這時(shí)將重新選擇此類(lèi)其他基因，導(dǎo)致有效基因缺失，出現(xiàn)早熟收斂現(xiàn)象．

2．4 遺傳算法的改進(jìn)

2．4．1 采用浮點(diǎn)數(shù)編碼方式 浮點(diǎn)數(shù)編碼能改善由二進(jìn)制編碼造成的如準(zhǔn)確度低、計(jì)算時(shí)間長(zhǎng)、計(jì)算量大等一系列問(wèn)題．在計(jì)算機(jī)中任意某個(gè)實(shí)數(shù)可近似表示為:一個(gè)整數(shù)或定點(diǎn)數(shù)(即尾數(shù))乘以某個(gè)基數(shù)(計(jì)算機(jī)中通常以2 為基數(shù))的整數(shù)次冪［3］．在計(jì)算機(jī)內(nèi)，浮點(diǎn)數(shù)可表示為如下格式:

Ms 表示數(shù)的符號(hào)位，0、1 分別表示正、負(fù)號(hào);M 表示數(shù)的尾數(shù)部分，采用定點(diǎn)小數(shù)形式表示，可用原碼(或補(bǔ)碼)等編碼方式．

利用浮點(diǎn)數(shù)編碼一方面可以擴(kuò)大搜索范圍，降低算法的復(fù)雜性，提高運(yùn)算效率;另一方面可以結(jié)合其他優(yōu)化方式，提高求解精度．

2．4．2 確定恰當(dāng)?shù)倪m應(yīng)度函數(shù) 適應(yīng)度函數(shù)值(遺傳算法中非負(fù))的大小決定了遺傳算法的收斂效率、找到最優(yōu)解的能力以及被遺傳到下一代的概率．

在許多實(shí)際問(wèn)題中，往往需要求最小費(fèi)用，這時(shí)可將求最小目標(biāo)根據(jù)適應(yīng)度函數(shù)非負(fù)原則轉(zhuǎn)換為求最大目標(biāo)的形式，變換關(guān)系式為:

式(1)中，f(m)為適應(yīng)度函數(shù)，g(m)為目標(biāo)函數(shù)，m 為模型參數(shù)，Cmax為一個(gè)待定的、合適的且相對(duì)較大的實(shí)數(shù)．選擇Cmax方式有:事先指定的一個(gè)較大(小)的數(shù);進(jìn)化到當(dāng)代為止的最大(小)目標(biāo)函數(shù)值;當(dāng)代或最近幾代群體中的最大(小)目標(biāo)函數(shù)值［4］．

此外，因遺傳算法還存在另一些問(wèn)題，比如對(duì)參數(shù)選擇敏感、進(jìn)化過(guò)程中早熟收斂而后期收斂停滯等．這時(shí)又可通過(guò)另一種變換(Goldberg 線性比例變換)來(lái)解決，變換公式為:

f(x)、g(x)分別為變換前后的適應(yīng)度函數(shù)值．

根據(jù)概率式轉(zhuǎn)移規(guī)則，由種群中各個(gè)體的適應(yīng)度大小確定下一步搜索方向．事實(shí)上，使用(1)和(2)式計(jì)算所得出的個(gè)體適應(yīng)度值，不會(huì)讓所有問(wèn)題結(jié)果收斂速度一致，需要降低較高的個(gè)體適應(yīng)度值克服早熟，增加較低的個(gè)體適應(yīng)度值避免后期停滯［5］．

2．4．3 搜索遺傳算子 遺傳算子主要有三種類(lèi)型:復(fù)制算子(reproduction)、雜交算子(crossover)和變異算子(mutation)［6］，因?yàn)檫z傳算法是通過(guò)一系列的遺傳算子來(lái)進(jìn)行的，所以搜索遺傳算子有較重要的作用，步驟如下:

第一步:選擇算子

采用的選擇概率計(jì)算方式為:

其中n 為種群大小，i 為個(gè)體排序序號(hào)，η+∈［1，2］，η-=2 -η+．

遺傳算法在選擇時(shí)容易出現(xiàn)個(gè)別個(gè)體在種群中迅速繁殖，個(gè)體適應(yīng)度彼此非常接近，搜索不能有效進(jìn)行．這時(shí)可采用變換適應(yīng)度函數(shù)尺度大小的方法來(lái)解決，即令:

第二步:交叉算子

遺傳算法中的交叉操作體現(xiàn)了信息交換的思想，即子代包含了父代的信息特征．交叉算子是一種進(jìn)化計(jì)算，通過(guò)它可生成基因更加優(yōu)良的個(gè)體．交叉算子的設(shè)計(jì)和實(shí)現(xiàn)要求在產(chǎn)生優(yōu)良的新個(gè)體情況下又不能破壞表現(xiàn)優(yōu)良的編碼串模式．在交叉時(shí)要注意，必須嚴(yán)格控制好交叉概率，交叉概率過(guò)大可能破壞遺傳模式，交叉概率過(guò)小則不易產(chǎn)生新個(gè)體．

第三步:變異算子

變異算子的作用是通過(guò)調(diào)整個(gè)體編碼中的部分基因值大小來(lái)改善遺傳算法的局部搜索能力，讓從局部出發(fā)搜索所得的個(gè)體最大程度地逼近最優(yōu)解．同時(shí)，算子因基因值的新舊替換而得到變異，改變了個(gè)體編碼串的結(jié)構(gòu)，保持了種群的多樣性，防止早熟［5］．

3 基于改進(jìn)后的遺傳算法對(duì)于非線性方程組的求解

3．1 非線性方程組的定義

非線性方程組是關(guān)于n 個(gè)變量的n 個(gè)方程，一般形式為:

3．2 非線性方程組的兩種求解方法

3．2．1 非數(shù)值算法 以往對(duì)非線性方程組的求解，所選擇的算法在計(jì)算時(shí)比較復(fù)雜．如:Newton 法、直線迭代法等．運(yùn)用等價(jià)思想，將非線性方程組的求解轉(zhuǎn)為函數(shù)優(yōu)化問(wèn)題，如下式:

其中Φ 為方程組解的區(qū)間，并且當(dāng)F(X)取最大值1 時(shí)，對(duì)應(yīng)的為非線性方程組的解，其具體解法筆者在此不再作贅述．

3．2．2 爬山算法［7］爬山搜索是向值增加的方向持續(xù)移動(dòng)的簡(jiǎn)單循環(huán)過(guò)程——登高(從單獨(dú)的當(dāng)前一個(gè)狀態(tài)出發(fā)，移動(dòng)到與之相鄰的狀態(tài)(見(jiàn)圖2))．它將會(huì)在達(dá)到一個(gè)“頂峰”(相鄰狀態(tài)中沒(méi)有比它更高的值)時(shí)終止．爬山搜索是局部最優(yōu)搜索，適合于最優(yōu)化問(wèn)題．

圖2 最優(yōu)化問(wèn)題Fig.2 Optimization problem

爬山搜索法趨于在得出解答前減少需訪問(wèn)的節(jié)點(diǎn)數(shù)，因此適用于很多場(chǎng)合．但是，它可能存在三種弊?。皇翘摷偕椒宓膯?wèn)題，此時(shí)搜索求解將涉及到大量的回溯;二是“平穩(wěn)地帶”問(wèn)題，此時(shí)所有可能的下一步搜索的好壞程度都一樣，那么爬山法就不如深度優(yōu)先搜索法好;三是“山脊”問(wèn)題，運(yùn)算時(shí)在回溯中將數(shù)次越過(guò)山脊，爬山算法無(wú)效．

3．3 用改進(jìn)后的遺傳算法求解非線性方程組的可行性分析

可見(jiàn)，遺傳算法局部搜索能力較差且存在“早熟”現(xiàn)象，爬山算法又難以對(duì)全局進(jìn)行求解．如果綜合爬山算法和遺傳算法的優(yōu)缺點(diǎn)，既可避免爬山算法的缺點(diǎn)，又可提高遺傳算法的局部搜索能力，將使求解非線性方程組問(wèn)題得到有效解決．

3．4 用改進(jìn)后的遺傳算法求解非線性方程組的具體步驟

根據(jù)以上分析，用改進(jìn)后的遺傳算法求解非線性方程組的執(zhí)行步驟可總結(jié)如下:

(1)將非線性方程組問(wèn)題轉(zhuǎn)化為函數(shù)優(yōu)化問(wèn)題求解;

(2)確定策略變量、定求解空間、交叉、變異概率等，并設(shè)置變量上下限;

(3)確定編碼方式;

(4)計(jì)算第一代種群適應(yīng)度，確定個(gè)體的優(yōu)劣狀況;

(5)對(duì)種群進(jìn)行尋優(yōu)，結(jié)合跨世代精英選擇策略和錦標(biāo)賽選擇法進(jìn)行選擇操作;

(6)根據(jù)自適應(yīng)交叉、自適應(yīng)變異概率及自適應(yīng)爬山算子進(jìn)行交叉操作、非均勻變異操作作局部搜索;

(7)尋找最優(yōu)個(gè)體，并進(jìn)行判斷，確定非線性方程組的最優(yōu)解．

4 結(jié)束語(yǔ)

綜上，通過(guò)采用浮點(diǎn)數(shù)編碼方式、確定恰當(dāng)?shù)倪m應(yīng)度函數(shù)及搜索遺傳算子等三個(gè)方面可對(duì)遺傳算法進(jìn)行改進(jìn)．用改進(jìn)后的遺傳算法求解非線性方程組，將改觀遺傳算法的全局收斂和爬山算法的局部收斂現(xiàn)象，有效降低求解非線性方程組的復(fù)雜度，提高解的準(zhǔn)確度．

［1］ 李 楠．考慮完整交易費(fèi)用組合投資模型的混合遺傳算法求解［D］． 天津大學(xué)碩士論文，2005．

［2］ 王學(xué)鳳．金盆水庫(kù)優(yōu)化調(diào)度研究［D］．西安理工大學(xué)碩士論文，2003．

［3］ 劉正紅．浮點(diǎn)數(shù)的教學(xué)難點(diǎn)及對(duì)策［J］．網(wǎng)友世界，2012(16):231 -233．

［4］ 蔡松柏，沈蒲生．關(guān)于非線性方程組求解技術(shù)［J］．湖南大學(xué)學(xué)報(bào)(自然科學(xué)版)，2011，27(3):189 -192

［5］ 任文杰．人工神經(jīng)網(wǎng)絡(luò)在地基土液化判別及等級(jí)評(píng)價(jià)中的應(yīng)用［D］．河北工業(yè)大學(xué)碩士論文，2002．

［6］ 黃海濱．遺傳算法中遺傳算子的分析［J］．玉林師范學(xué)院學(xué)報(bào)，2001(09):25 -27．

［7］ 張慶雅．楊火箭發(fā)動(dòng)機(jī)法蘭連接系統(tǒng)模糊可靠性分析［D］．西北工業(yè)大學(xué)博士論文，2003．