一種基于蟻群算法求方程組數(shù)值解的新方法

1、一種基于蟻群算法求方程組數(shù)值解的新方法葉 楠（四川大學(xué) 電氣信息學(xué)院 ，成都，610065，） 摘要：解方程組是工程研究中的基本問題.本文提出了一種基于蟻群算法求方程組數(shù)值解的新方法.首先，引入方程組求解模型；然后，介紹了一種用于連續(xù)函數(shù)優(yōu)化的蟻群算法；最后，分析了該法的特點(diǎn)和性能.實(shí)驗(yàn)結(jié)果表明該法是有效可行的，進(jìn)一步提高解精度與求解效率的關(guān)鍵在于對(duì)蟻群算法本身的研究. 關(guān)鍵詞： 蟻群算法 方程組 連續(xù)函數(shù)優(yōu)化 中圖法分類號(hào)： TP301.6 文獻(xiàn)標(biāo)識(shí)碼： ANew method based on ant colony system for resolving equation groupsY

2、e Nan(College of Electrical Information , Sichuan university , Chengdu , 610065 , China)Abstract: Resolving equation groups is a principal problem in engineering study. A new method for resolving equation groups is proposed, which is based on Ant Colony System. First, the resolving model of equation

3、 group is described; then， according to Ant Colony System, an algorithm for continuous function optimization is introduced; finally the performance is analyzed. The results of experiment show that the new method is effective and feasible, and the key to improve the precision of results and the effic

4、iency of the resolving process lies in the further research of the Ant Colony System.Keywords: ant colony system equation group continuous function optimization 1.引言 （Introduction）求解方程組（本文指的是：求方程組的數(shù)值解）是實(shí)際工程應(yīng)用研究中的常見問題.各種方程組的解法長期以來一直是數(shù)學(xué)界和工程界的一個(gè)重要研究方向.因?yàn)榉匠探M特性的復(fù)雜多樣性，目前的研究成果大都是僅對(duì)某一類特定方程組的解法；對(duì)許多方程形式復(fù)雜的方程組

5、，甚至還沒有有效的解法.蟻群算法是一種解決復(fù)雜問題的有效方法，具有很強(qiáng)的通用性1.本文根據(jù)求解方程組問題的共同特點(diǎn)，基于蟻群算法建立了一個(gè)適用于各類方程組求解的通用模型.在此模型基礎(chǔ)上，引入了一種新的求方程組數(shù)值解的通用算法.實(shí)驗(yàn)證明此算法是有效可行的；求解精度與效率的進(jìn)一步提高與蟻群算法的品質(zhì)有關(guān).2.方程組求解思想的引入 （The appearance of equation groups solution） 設(shè)一個(gè)方程組，由n個(gè)方程組成，每個(gè)方程涉及m個(gè)變量： X X = , = X| 另設(shè) , X . (1) 求解上述方程組等價(jià)于下面一個(gè)求極值問題：求一X，使式（1）取得最小值，當(dāng)其最

6、小值為0時(shí)，所對(duì)應(yīng)的X，即為原方程組的解；當(dāng)其最小值不為0時(shí)，則此方程組無解. 3.算法描述 （Algorithm description） 為描述問題清晰和壓縮篇幅需要起見，對(duì)于涉及n個(gè)方程，m個(gè)自變量的方程組求解算法的描述過程一律基于一元方程求解過程的描述.只要理解了算法的實(shí)質(zhì)，從一元方程推廣到多元方程組便不難.另外，對(duì)于蟻群算法的一般模型及應(yīng)用場(chǎng)合，本文也不另作介紹，有興趣者可參閱文獻(xiàn)4. 設(shè)問題要求精確到小數(shù)點(diǎn)后d位，則自變量x可以用d個(gè)十進(jìn)制數(shù)來近似表示.我們就可以構(gòu)造如下d*10+2個(gè)“城市”：這些城市分為d+2層；其中首尾兩層分別僅含一個(gè)城市：一個(gè)為起始城市，一個(gè)為終止城市；中間

7、d層，從左往右分別表示自變量的十分位、百分位這些城市中，只有k-1層與k層（k2,d+2）之間的各個(gè)城市有連接通路.記k-1層中代表十進(jìn)制數(shù)a的城市與k層代表十進(jìn)制數(shù)b的城市之間的連接上殘留的信息量為.螞蟻n在一次循環(huán)中第m步所在城市用T(n,m)表示，并設(shè)螞蟻總數(shù)為.首先用一個(gè)較小的值初始化所有的.讓每只螞蟻的第一步為0，即令T(n,1)=0 (n=1,2,., ).然后，就為每一只螞蟻選擇路徑.若螞蟻n當(dāng)前所在的城市為T(n,k-1)=a,根據(jù)如下公式選擇每只螞蟻下一步應(yīng)該到達(dá)的城市：（2） 其中，q為0，1上的隨機(jī)數(shù)，是0，1上的常數(shù)，用于確定偽隨機(jī)選擇的概率. 表示用偽隨機(jī)選擇來確定下

8、一步要走的城市，也就是根據(jù)下式計(jì)算螞蟻選擇下一層中每一個(gè)城市的概率，然后按此概率用遺傳算法中的轉(zhuǎn)盤式選擇法確定要選擇的城市： （3） 其中，p(a,b)表示從當(dāng)前城市a轉(zhuǎn)移到下一層的城市b的概率.由于本算法中僅允許螞蟻有上一層的城市向下一層的城市轉(zhuǎn)移，所以這個(gè)公式與普通蟻群算法的轉(zhuǎn)移概率計(jì)算公式有所不同. 當(dāng)每只螞蟻按上面的公式到達(dá)了d+1層時(shí)，都將轉(zhuǎn)移到d+2層的唯一城市0. 螞蟻在城市上建立路徑的過程中，要不斷地在經(jīng)過的路徑上按公式（4）減弱上面殘留的信息量，這樣就可以減小下一只螞蟻選擇同樣路徑的概率，除非經(jīng)過多次循環(huán)后已確定一條極優(yōu)的路徑.這個(gè)過程叫做殘留信息量的局部更新. （4） 其中

9、，為（0，1）上的常數(shù)，表示路徑上殘留信息量減弱的速度. 當(dāng)所有螞蟻都按上面的步驟完成了一次循環(huán)，這時(shí)就對(duì)路徑上的信息量進(jìn)行全局更新.首先對(duì)每只螞蟻選擇的路徑解碼，計(jì)算出螞蟻n對(duì)應(yīng)的自變量值：（5）然后，計(jì)算每只螞蟻對(duì)應(yīng)的函數(shù)值，并選擇出函數(shù)值最小的螞蟻，稱為最優(yōu)螞蟻. （6） 對(duì)這只最優(yōu)螞蟻經(jīng)過路徑上的信息量按下式做全局更新： （7） 其中i=T(,k-1), j=T(,k), k2,d+2, 為（0，1）上的常數(shù). 至此就完成了一個(gè)循環(huán).反復(fù)進(jìn)行上面的步驟直到達(dá)到指定的循環(huán)次數(shù)或得到的解在一定的循環(huán)次數(shù)后沒有改進(jìn). 將算法的具體求解過程歸納如下： （1） 初始化各條路徑的信息量；（2） 將

10、所有螞蟻置于初始城市；（3） 對(duì)所有的k-1到k層城市執(zhí)行步驟（4）(8);（4） 對(duì)每只螞蟻執(zhí)行步驟（5）（6）；（5） 根據(jù)公式（2）和（3）選擇螞蟻在第k層應(yīng)該到達(dá)的城市；（6） 每只螞蟻選擇城市后都立即按公式（4）執(zhí)行信息量的局部更新規(guī)則；（7） 根據(jù)公式（5）（7）評(píng)選出最優(yōu)螞蟻并執(zhí)行信息量的全局更新規(guī)則；（8） 判斷是否滿足終止條件.如滿足，則結(jié)束計(jì)算輸出計(jì)算結(jié)果計(jì)算.(說明：對(duì)于多元方程組求解，可增設(shè)自變量，具體可參閱文獻(xiàn)3.) 4.算法性能分析和實(shí)驗(yàn)結(jié)果 （Performance analysis and experiment results） 本算法的數(shù)學(xué)模型概括了方程組求解

11、的本質(zhì)特點(diǎn)，從而決定了算法的通用性，使其具有很強(qiáng)的適應(yīng)性.不管方程是否可微、連續(xù)或形式復(fù)雜，方程組是否完備、良態(tài)或有解，都不影響其求解.為證明本算法是有效可行的，本次實(shí)驗(yàn)選取文獻(xiàn)2中的某些具有代表性的方程（組）進(jìn)行對(duì)比求解. =0.8,=0.8,d=7,運(yùn)行循環(huán)次數(shù)：1000 表 1 與文獻(xiàn)2之對(duì)比結(jié)果Table 1 The comparative results to reference 3序號(hào)方程組文獻(xiàn)3算法解求解時(shí)間（s）本文算法解求解時(shí)間（s）1|sin(30x)|(1-|x|/2)-0.9739626=0x(-100,100)x=0.051825.41x=0.05180.12x,y-

12、2，2x=0.2909y=0.000036.90x=0.2909y=0.00190.23x,y,z-1.732,1.732x=1.0000y=0.9998z=1.000151.57x=0.9390y=1.0600z=0.99720.3表 2 選取典型函數(shù)測(cè)試之結(jié)果Table 2 The results of selective functions序號(hào)方程組本文算法解求解時(shí)間1X=73.550740.1s2X=0.605830.1s30.3s5.結(jié)束語 （Conclusion and valuation） 本文提出了一種基于蟻群算法求方程組數(shù)值解的通用算法.實(shí)驗(yàn)結(jié)果表明此算法是有效可行的，尤其在

13、求解一元方程時(shí)，其求解精度與速度都非常優(yōu)越；但在求解多元方程組時(shí)，精度有所下降，但速度仍然非?？?因此本算法可作為工程應(yīng)用研究的一個(gè)通用工具.參考文獻(xiàn) （References）1Macro Dorigo,Vittorio Maniezzo,Alberto Colorni. The Ant System: Optimization by a colony of cooperating agentsA.IEEE Transactions on Systems, Man,and Cybernetics,Part-B,Vol.26,No.1, pp.1-13,1996,2胡小兵，吳樹范等. 一種基于遺

14、傳算法求代數(shù)方程組數(shù)值解的新方法J. 控制理論與應(yīng)用. 2002.19（8）：567-570Hu xiao-bing,Wu Shu-fan. New method based on genetic algorithm for resolving algebraic equation groupsJ.Control Theory and Applications,2002,19(8): 567-570(Ch).3陳燁. 下限未知函數(shù)優(yōu)化蟻群算法A. 青島大學(xué)學(xué)報(bào)增刊-2003年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集. 2003（8）Chen Ye. Ant Colony System for Optimization of Function with Lower Bound UnknownA. Journal of Qing Dao University (Natural Science Edition) Vol.16.Suppl.Aug:2003(Ch). 4魏平，熊偉清. 用于一般函數(shù)優(yōu)化的蟻群算法J. 寧波大學(xué)學(xué)報(bào)（理工版）.2001.14（4）：52-55Wei Ping,Xiong Wei-Qing. Ant Colony Algorithm for General Fu