李軍民，李立博

(西安科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，陜西 西安710054)

0 引 言

人工魚群算法繼承了基本魚群算法的特性:從人工魚個(gè)體的最底層尋優(yōu)到整個(gè)魚群的全局尋優(yōu)。目前人工魚群算法在數(shù)值計(jì)算方面，已經(jīng)由解決一維靜態(tài)優(yōu)化問題發(fā)展到解決二維甚至更高維的動(dòng)態(tài)組合優(yōu)化問題，其特點(diǎn)就是無(wú)需借助目標(biāo)函數(shù)的梯度值等信息，僅使用目標(biāo)函數(shù)的函數(shù)值，在搜索全局最優(yōu)解的過程中具有一定的自適應(yīng)能力。特別是人工魚群算法對(duì)初值無(wú)要求、參數(shù)的選擇在某種程度上也不敏感，使得算法更加具有并行、全局、快速、跟蹤等特點(diǎn)。該算法已經(jīng)廣泛應(yīng)用到通信［1-3］、神經(jīng)網(wǎng)絡(luò)、數(shù)據(jù)挖掘、控制、交通等領(lǐng)域，同時(shí)為NP 類問題、參數(shù)優(yōu)化［4］、數(shù)值求解［5-7］、模型求解等問題［8-10］提供了很好的求解途徑。

蒙特卡羅算法［11-12］不同于求解確定性數(shù)值解的一些算法，它是從問題的相反關(guān)系出發(fā)，用于解決數(shù)學(xué)［13］、物理問題的不確定性數(shù)值解，其基本思想是:在概率統(tǒng)計(jì)層面尋找一個(gè)相似體，通過實(shí)驗(yàn)取樣的方法獲得相似體的近似解來解決數(shù)學(xué)、物理問題。采用基于蒙特卡羅算法的蒙特卡羅試驗(yàn)取代部分真實(shí)試驗(yàn)，節(jié)省了設(shè)計(jì)的完成時(shí)間和工作量，從而促進(jìn)解決了概率以及數(shù)值解問題的發(fā)展。

二重積分作為科學(xué)計(jì)算中一類相對(duì)重要的積分，人們一直追求如何方便快快地使用計(jì)算機(jī)程序求解其數(shù)值解。結(jié)合近幾年比較經(jīng)典的智能優(yōu)化算法—人工魚群算法和熟知的蒙特卡羅算法求解二重積分的數(shù)值解，將蒙特卡羅算法求解二重積分?jǐn)?shù)值解的思想引入到人工魚群算法中，改進(jìn)了人工魚群算法中的適應(yīng)度函數(shù)和積分求和式［14-17］。計(jì)算結(jié)果表明:采用混合算法和其他算法相比較，二重積分?jǐn)?shù)值解的精確度有所提高。

1 人工魚群和蒙特卡羅的混合算法

采用人工魚群算法求解二重積分的數(shù)值解，是基于被積函數(shù)的凹凸形狀來隨機(jī)的劃分積分區(qū)域，其思路是:首先在二重積分的積分范圍內(nèi)任意生成指定數(shù)目的點(diǎn);然后按照一定的規(guī)則，采用人工魚群算法對(duì)其進(jìn)行優(yōu)化，從而更好地求解二重積分的數(shù)值解，并克服傳統(tǒng)的求二重積分方法中的不足。

應(yīng)用蒙特卡羅方法來求二重積分的數(shù)值解，其中心思想是:序列化積分區(qū)域中產(chǎn)生的非均勻隨機(jī)點(diǎn)，將被積函數(shù)所對(duì)應(yīng)的隨機(jī)變量的算術(shù)平均值視為其積分的近似值，即

結(jié)合人工魚群算法和蒙特卡羅方法，來求解二重積分的數(shù)值解，主要是針對(duì)文獻(xiàn)［14］中人工魚群算法的適應(yīng)度函數(shù)和積分求和公式進(jìn)行改進(jìn)(分別參見2)和7))，引入蒙特卡羅求積分的思路。既保留其各自算法的優(yōu)點(diǎn)，又節(jié)省計(jì)算時(shí)間、提高計(jì)算精度、算法的收斂性較好，同時(shí)相對(duì)蒙特卡羅方法減少節(jié)點(diǎn)數(shù)目。

設(shè)關(guān)于x，y 的二元函數(shù)f(x，y)為區(qū)域D:a1≤x≤b1，a2(x)≤y≤b2(x)上滿足蒙特卡羅算法條件的有界函數(shù)［2］，采用混合人工魚群和蒙特卡羅算法求函數(shù)f(x，y)在區(qū)域D 上的二重積分的數(shù)值解的步驟如下

1)算法開始，設(shè)定人工魚群算法的參數(shù)，初始化人工魚;

2)計(jì)算每條人工魚的適應(yīng)度函數(shù)值，更新公告板;不同于文獻(xiàn)［1］該算法中人工魚的適應(yīng)度函數(shù)為

計(jì)算積分區(qū)域D 劃分成的每個(gè)小矩形的4 個(gè)頂點(diǎn)和矩形中心對(duì)應(yīng)的函數(shù)值，并找出這5 個(gè)函數(shù)值中的最小值Mini和最大值Maxi. 在這里若函數(shù)f(i)的值越趨于0，則表示該人工魚個(gè)體(即該分割方法)越優(yōu)［14］。

3)模擬執(zhí)行追尾、聚群行為，選擇優(yōu)的行為作為人工魚的前進(jìn)方向;

4)如果2 個(gè)行為都沒有改進(jìn)，則執(zhí)行覓食行為;

5)重復(fù)2);

6)判斷是否滿足結(jié)束條件:是繼續(xù)7)，否轉(zhuǎn)2);

7)計(jì)算二重積分的數(shù)值解并輸出結(jié)果，算法結(jié)束。

文中的積分求和公式，參照蒙特卡羅算法表示為

其 中 f(xi，yi)，f(xi+1，yi)，f(xi，yi+1)，f(xi+1，yi+1)，f(xmid，ymid)分別為積分區(qū)域D 劃分成的小矩形的4 個(gè)頂點(diǎn)和矩形中心對(duì)應(yīng)的函數(shù)值［14］，β = 8.

2 示例演算

已知這個(gè)二重積分的準(zhǔn)確值為5.100 170 0，在(0.0)點(diǎn)被積函數(shù)無(wú)定義，當(dāng)變量x 方向趨近下限時(shí)，函數(shù)圖形變化劇烈。文中算法的參數(shù)設(shè)置為

表1 幾種算法的積分值及相對(duì)誤差Tab.1 Integral value and the relative error of several algorithms

圖1 適應(yīng)度函數(shù)值和迭代次數(shù)、二重積分值和迭代次數(shù)的關(guān)系曲線Fig.1 Relation curves fitness function value and the number of iterations，the curve of double integral value and number of iterations

3 結(jié) 論

使用計(jì)算機(jī)方便快捷的求解二重積分的數(shù)值解，在數(shù)學(xué)問題領(lǐng)域中一直占據(jù)不可或缺的地位。將蒙特卡羅求解二重積分?jǐn)?shù)值解的思想引入到人工魚群算法中，改進(jìn)人工魚群算法中的適應(yīng)度函數(shù)和積分求和公式的人工魚群和蒙特卡羅混合算法更加有利于二重積分的數(shù)值解求解方法的發(fā)展。

在采用人工魚群算法和蒙特卡羅的混合算法求二重積分時(shí)，適應(yīng)度函數(shù)值相對(duì)趨近于0，二重積分值也基本收斂于積分值，分割點(diǎn)數(shù)目為100時(shí)，誤差已經(jīng)是0.000 410 7. 實(shí)驗(yàn)表明，文中提出的混合改進(jìn)算法在一定程度上使得分割點(diǎn)的數(shù)目得以減少，收斂的速度和計(jì)算的精度也有所提高。

References

［1］ 王軍偉，王興偉，黃 敏.一種基于禁忌人工魚群算法的智能QoS 組播路由算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，2009，30(9):1 720 -1 723.WANG Jun-wei，WANG Xing-wei，HUANG Min. Tabu artificial fish swarm algorithm based intelligent QoS multicast routing algorithm［J］.Journal of Chinese Computer Systems，2009，30(9):1 720 -1 723.

［2］ 羅景峰，王瑩瑩.基于魚群算法的全終端網(wǎng)絡(luò)可靠性優(yōu)化設(shè)計(jì)［J］.微電子學(xué)與計(jì)算機(jī)，2009，26(2):93 -96.LUO Jing-feng，WANG Ying-ying. Optimization design of ALL-terminal networks reliability base on fish-wwarm algorithms［J］.Microelectronics and Computer，2009，26(2):93 -96.

［3］ 王興偉，秦培玉，黃 敏.基于人工魚群的ABC 支持型QoS 單播路由機(jī)制［J］.計(jì)算機(jī)學(xué)報(bào)，2010，33(4):718 -725.WANG Xing-wei，QIN Pei-yu，HUANG Min. ABC supporting QoS unicast routing scheme based on the Artificial Fish Swarm［J］. Chinese Journal of Computers，2010，33(4):718 -725.

［4］ 王錫淮，鄭曉鳴，肖健梅.求解約束優(yōu)化問題的人工魚群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(3):40 -42.WANG Xi-huai，ZHENG Xiao-ming，XIAO Jian-mei.Artificial fish-swarm algorithm for solving constrained optimiza-tion problems［J］. Computer Engineering and Applications，2007，43(3):40 -42.

［5］ 周永權(quán)，張明，趙 斌.基于進(jìn)化策略方法求任意函數(shù)的數(shù)值積分［J］. 計(jì)算機(jī)學(xué)報(bào)，2008，21(2):196 -206.ZHOU Yong-quan，ZHANG Ming，ZHAO Bin. Solving numerical integration based on evolution strategy method［J］.Chinese Journal of Computers，2008，21(2):196 -206.

［6］ 王小華，何怡剛，曾喆昭.三角基函數(shù)神經(jīng)網(wǎng)絡(luò)算法在數(shù)值積分中的運(yùn)用研究［J］. 電子與信息學(xué)報(bào)，2004，26(3):394 -399.WANG Xiao-hua，HE Yi-gang，ZENG Zhe-zhao.Numerical integration study based on triangle basis neural network algorithm［J］.Journal of Electronics ＆ Information Technology，2004，26(3):394 -399.

［7］ 曲良東，何登旭，曾邵東.基于人工魚群算法的優(yōu)化分割數(shù)值積分算法［J］.計(jì)算機(jī)應(yīng)用與軟件，2009，26(11):58 -60.QU Liang-dong，HE Deng-xu，ZENG Shao-dong.Numerical integration with optim-ized segmentation based on artificial fish-school algorithm［J］. Computer Applications and Software，2009，26(11):58 -60.

［8］ 黃華娟，周永權(quán)，韋杏瓊，等.求解矩陣特征值得混合人工魚群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2010，46(6):56 -59.HUANG Hua-juan，ZHOU Yong-quan，WEI Xingqiong，et al. Hybrid artificial fish sch-ool algorithm for solving matrix eigenvalues［J］. Computer Engineering and Applications，2010，46(6):56 -59.

［9］ 王冬冬，周永權(quán).人工魚群算法在求解非線性方程組中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2007，24(6):242 -244.WANG Dong-dong，ZHOU Yong-quan.. Artificial fishswarm algorithm for solving nonlinear equations［J］.Application Research of Computers，2007，24(6):242 -244.

［10］ 曲良東，何登旭.改進(jìn)的人工魚群算法及其在近似求導(dǎo)中的應(yīng)用［J］. 微電子學(xué)與計(jì)算機(jī)，2009，26(5):122 -125.QU Liang-dong，HE Deng-xu. Improved artificial fish school algorithm and its application for solving numerical derivative［J］.Microel Ectronics ＆ Computer，2009，26(5):122 -125.

［11］ Robert C P，Casella G. Monte carlo statistical method(Second Edition)［M］.New York:Springer，2004.

［12］ 徐鐘濟(jì).蒙特卡羅方法［M］. 上海:上?？茖W(xué)技術(shù)出版社，1985.XU Zhong-ji. Monte carlo method［M］. Shanghai:Shanghai Science and Technology Press，1985.

［13］ 劉輝玲，葉 鋒.計(jì)算多重積分的均勻隨機(jī)數(shù)蒙特卡羅法的實(shí)現(xiàn)［J］.電腦知識(shí)與技術(shù)，2008，4(8):2 289-2 291.LIU Hui-ling，YE Feng.Realization of monte carlo method by using uniform random sequence for calculating multiple integrals［J］. Computer Knowledge and Technology，2008，4(8):2 289 -2 291.

［14］ 聶黎明，周永權(quán).用人工魚群算法求解二重?cái)?shù)值積分［J］.算機(jī)工程與應(yīng)用，2009，45(10):34 -37.NIE Li-ming，ZHOU Yong-quan. Using artificial fishswarm algorithm for solving two dimensional numerical integration［J］.Computer Engineering and Applications，2009，45(10):34 -37.

［15］ 李滿枝，王洪濤，張廣路. 蒙特卡羅法在二重積分中的改進(jìn)算法［J］. 海南師范大學(xué)學(xué)報(bào):自然科學(xué)版，2010，23(3):242 -244.LI Man-zhi，WANG Hong-tao，ZHANG Guang-lu.Calculation of double integrals based on monte carlo method［J］. Journal of Hainan Normal University:Natural Science，2010，23(3):242 -244.

［16］ 曹承志，張 坤，鄭海英，等. 基于人工魚群算法的BP 神經(jīng)網(wǎng)絡(luò)速度辨識(shí)器［J］. 系統(tǒng)仿真學(xué)報(bào)，2009，21(4):1 047 -1 050.CAO Cheng-zhi，ZHANG Kun，ZHENG Hai-ying，et al.BP neural network speed identifier based on Artificial Fish Algorithm［J］.Journal of System Simulation，2009，21(4):1 047 -1 050.

［17］ 謝竹誠(chéng)，周永權(quán).一種基于AFSA 與RST 分類規(guī)則挖掘算法［J］.微電子學(xué)與計(jì)算機(jī)，2009，26(3):182 -184.XIE Zhu-cheng，ZHOU Yong-quan.Mining classification rules algorithm based on AFSA and RST［J］.Microelectronics ＆ Computer，2009，26(3):182 -184.