人工魚(yú)群和蒙特卡羅混合算法的應(yīng)用*

李軍民，李立博

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

0 引 言

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

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

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

1 人工魚(yú)群和蒙特卡羅的混合算法

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

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

結(jié)合人工魚(yú)群算法和蒙特卡羅方法，來(lái)求解二重積分的數(shù)值解，主要是針對(duì)文獻(xiàn)［14］中人工魚(yú)群算法的適應(yīng)度函數(shù)和積分求和公式進(jìn)行改進(jìn)(分別參見(jià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)上滿(mǎn)足蒙特卡羅算法條件的有界函數(shù)［2］，采用混合人工魚(yú)群和蒙特卡羅算法求函數(shù)f(x，y)在區(qū)域D 上的二重積分的數(shù)值解的步驟如下

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

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

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

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

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

5)重復(fù)2);

6)判斷是否滿(mǎn)足結(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)系曲線(xià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é)問(wèn)題領(lǐng)域中一直占據(jù)不可或缺的地位。將蒙特卡羅求解二重積分?jǐn)?shù)值解的思想引入到人工魚(yú)群算法中，改進(jìn)人工魚(yú)群算法中的適應(yīng)度函數(shù)和積分求和公式的人工魚(yú)群和蒙特卡羅混合算法更加有利于二重積分的數(shù)值解求解方法的發(fā)展。

在采用人工魚(yú)群算法和蒙特卡羅的混合算法求二重積分時(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］ 王軍偉，王興偉，黃 敏.一種基于禁忌人工魚(yú)群算法的智能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］ 羅景峰，王瑩瑩.基于魚(yú)群算法的全終端網(wǎng)絡(luò)可靠性?xún)?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］ 王興偉，秦培玉，黃 敏.基于人工魚(yú)群的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)化問(wèn)題的人工魚(yú)群算法［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ú)群算法的優(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)，韋杏瓊，等.求解矩陣特征值得混合人工魚(yú)群算法［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ú)群算法在求解非線(xià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)的人工魚(yú)群算法及其在近似求導(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］. 上海:上海科學(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).用人工魚(yú)群算法求解二重?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］ 李滿(mǎn)枝，王洪濤，張廣路. 蒙特卡羅法在二重積分中的改進(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］ 曹承志，張 坤，鄭海英，等. 基于人工魚(yú)群算法的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 分類(lèi)規(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.