人工智能遺傳算法論文(2)
人工智能遺傳算法論文
人工智能遺傳算法論文篇二
人工智能之遺傳算法論文
摘 要：非線性方程組的求解是數(shù)值計(jì)算領(lǐng)域中最困難的問(wèn)題，大多數(shù)的數(shù)值求解算法例如牛頓法的收斂性和性能特征在很大程度上依賴于初始點(diǎn)。但是對(duì)于很多高維的非線性方程組， 選擇好的初始點(diǎn)是一件非常困難的事情。本文采用了遺傳算法的思想，提出了一種用于求解非線性方程組的混合遺傳算法。該混合算法充分發(fā)揮了遺傳算法的群體搜索和全局收斂性。選擇了幾個(gè)典型非線性方程組，考察它們的最適宜解。
關(guān)鍵詞：非線性方程組;混合遺傳算法;優(yōu)化
1. 引言
遺傳算法是一種通用搜索算法，它基于自然選擇機(jī)制和自然遺傳規(guī)律來(lái)模擬自然界的進(jìn)化過(guò)程，從而演化出解決問(wèn)題的最優(yōu)方法。它將適者生存、結(jié)構(gòu)化但同時(shí)又是隨機(jī)的信息交換以及算法設(shè)計(jì)人的創(chuàng)造才能結(jié)合起來(lái)，形成一種獨(dú)特的搜索算法，把一些解決方案用一定的方式來(lái)表示，放在一起成為群體。每一個(gè)方案的優(yōu)劣程度即為適應(yīng)性，根據(jù)自然界進(jìn)化“優(yōu)勝劣汰”的原則，逐步產(chǎn)生它們的后代，使后代具有更強(qiáng)的適應(yīng)性，這樣不斷演化下去，就能得到更優(yōu)解決方案。 隨著現(xiàn)代自然科學(xué)和技術(shù)的發(fā)展，以及新學(xué)科、新領(lǐng)域的出現(xiàn)，非線性科學(xué)在工農(nóng)業(yè)、經(jīng)濟(jì)政治、科學(xué)研究方面逐漸占有極其重要的位置。在理論研究和應(yīng)用實(shí)踐中，幾乎絕大多數(shù)的問(wèn)題都最終能化為方程或方程組，或者說(shuō)，都離不開(kāi)方程和方程組的求解。因此，在非線性問(wèn)題中尤以非線性方程和非線性方程組的求解最為基本和重要。傳統(tǒng)的解決方法，如簡(jiǎn)單迭代法、牛頓法、割線法、延拓法、搜索法、梯度法、共軛方向法、變尺度法，無(wú)論從算法的選擇還是算法本身的構(gòu)造都與所要解決的問(wèn)題的特性有很大的關(guān)系。很多情況下,算法中算子的構(gòu)造及其有效性成為我們解決問(wèn)題的巨大障礙。而遺傳算法無(wú)需過(guò)多地考慮問(wèn)題的具體形式，因?yàn)樗且环N靈活的自適應(yīng)算法，尤其在一些非線性方程組沒(méi)有精確解的時(shí)候，遺傳算法顯得更為有效。而且，遺傳算法是一種高度并行的算法，且算法結(jié)構(gòu)簡(jiǎn)單，非常便于在計(jì)算機(jī)上實(shí)現(xiàn)。本文所研究的正是將遺傳算法應(yīng)用于求解非線性方程組的問(wèn)題。
2. 遺傳算法解非線性方程組
為了直觀地觀察用遺傳算法求解非線性方程組的效果，我們這里用代數(shù)非線性方程組作為求解的對(duì)象
問(wèn)題描述：
非線性方程組指的是有n個(gè)變量(為了簡(jiǎn)化討論，這里只討論實(shí)變量方程組)的方程組
𝑓𝑖 x1,x2,…,xn =0 𝑖=1,2,…,𝑚
中含有非線性方程。其求解是指在其定義域內(nèi)找出一組數(shù)x∗ x1,x2,…,xn 能滿足方程組中的每一個(gè)方程。這里，我們將方程組轉(zhuǎn)化為一個(gè)函數(shù)
F x1,x2,…,xn = 𝑓𝑖
i=0
則求解方程組就轉(zhuǎn)化為求一組值x∗ x1,x2,…,xn 使得F x∗ =0成立。即求使函數(shù)F x1,x2,…,xn 取得最小值0的一組數(shù)，于是方程組求解問(wèn)題就轉(zhuǎn)變?yōu)楹瘮?shù)優(yōu)化問(wèn)題
3. 遺傳算子
遺傳算子設(shè)計(jì)包括交叉算子、變異算子和選擇算子的設(shè)計(jì)。
(1)交叉算子
算術(shù)交叉算子是實(shí)數(shù)編碼遺傳算法中應(yīng)用最廣泛的一種算子, 該算子描述如下:
假設(shè)在兩個(gè)體X 1 和X 2 之間進(jìn)行算術(shù)交叉, 則交叉運(yùn)算后所產(chǎn)生出的兩個(gè)新個(gè)體為
∗X1=aX1+(1−a)X2 ∗ X2= 1−a X1+aX2
其中a是在[0，1]區(qū)間內(nèi)的參數(shù)，它可以是一個(gè)常數(shù)，也可以是由進(jìn)化所決定的變量，本文選擇為[ 0，1] 區(qū)間上的隨機(jī)數(shù)。
(2)變異算子
設(shè)被選中變異的個(gè)體的染色體為Xk, 隨機(jī)產(chǎn)生一個(gè)擾動(dòng)方向pk, 整個(gè)變異操作的過(guò)程是以Xk為起點(diǎn), 沿方向pk尋求最優(yōu)點(diǎn)作為新的染色體, 即完成如下一維搜索運(yùn)算:
min∅ τ =F Xk+τpk
本文以黃金分割方法搜索得到最優(yōu)步長(zhǎng)τ° , 則變異后個(gè)體的新染色體Xk′
′Xk=Xk+τ°pk
(3)選擇算子
傳統(tǒng)的標(biāo)準(zhǔn)選擇算子一方面要求適應(yīng)度函數(shù)大于零, 給適應(yīng)度函數(shù)的選擇帶了一定的困難; 另一方面基于適應(yīng)值的排序選擇算子是造成算法早熟、收斂速度慢的主要原因。為避免上述問(wèn)題, 本文采用了既具有較高確定性和一定隨機(jī)性的聯(lián)賽競(jìng)爭(zhēng)法為選擇算子, 聯(lián)賽規(guī)模取為3。由于遺傳算法中有許多隨機(jī)因素的影響, 當(dāng)前群體的最好個(gè)體可能會(huì)被破壞, 影響算法的運(yùn)行效率和收斂性, 因此采用了最優(yōu)保存策略, 即當(dāng)前群體中最優(yōu)個(gè)體不參與交叉運(yùn)算和變異運(yùn)算, 而是用它來(lái)替代本代群體中經(jīng)過(guò)交叉、變異操作后所產(chǎn)生的最差個(gè)體。
4. 實(shí)例驗(yàn)證
我們?yōu)榱蓑?yàn)證這個(gè)遺傳算法是否能夠找到我們需要的合適解，選取下面
的非線性方程組來(lái)驗(yàn)證：
x1+x2+x3−0.5=0
x1x2+x2x3+x3x1+7.5=0
222x1+x2+x3−15.25=0
運(yùn)行得到的結(jié)果為：得出來(lái)的結(jié)果為逼近準(zhǔn)確解
第2 / 5頁(yè)
ans = 0 -2 1
由此可知能找到合適的解的。
參考文獻(xiàn)：
[1]陳明. 基于進(jìn)化遺傳算法的優(yōu)化計(jì)算[J]. 軟件學(xué)報(bào), Vol.9 No.11, 1998.11:876-879.
[2]陳火旺. 遺傳程序設(shè)計(jì)(之一)[J]. 計(jì)算機(jī)科學(xué), 1995.22(6):12-15.
[3]馮果忱. 非線形方程組迭代解法[M]. 上?？茖W(xué)技術(shù)出版社, 1989.
看了“人工智能遺傳算法論文”的人還看了：