人工鱼群和蒙特卡罗混合算法的应用*

李军民，李立博

(西安科技大学 计算机科学与技术学院，陕西 西安710054)

0 引 言

人工鱼群算法继承了基本鱼群算法的特性:从人工鱼个体的最底层寻优到整个鱼群的全局寻优。目前人工鱼群算法在数值计算方面，已经由解决一维静态优化问题发展到解决二维甚至更高维的动态组合优化问题，其特点就是无需借助目标函数的梯度值等信息，仅使用目标函数的函数值，在搜索全局最优解的过程中具有一定的自适应能力。特别是人工鱼群算法对初值无要求、参数的选择在某种程度上也不敏感，使得算法更加具有并行、全局、快速、跟踪等特点。该算法已经广泛应用到通信［1-3］、神经网络、数据挖掘、控制、交通等领域，同时为NP 类问题、参数优化［4］、数值求解［5-7］、模型求解等问题［8-10］提供了很好的求解途径。

蒙特卡罗算法［11-12］不同于求解确定性数值解的一些算法，它是从问题的相反关系出发，用于解决数学［13］、物理问题的不确定性数值解，其基本思想是:在概率统计层面寻找一个相似体，通过实验取样的方法获得相似体的近似解来解决数学、物理问题。采用基于蒙特卡罗算法的蒙特卡罗试验取代部分真实试验，节省了设计的完成时间和工作量，从而促进解决了概率以及数值解问题的发展。

二重积分作为科学计算中一类相对重要的积分，人们一直追求如何方便快快地使用计算机程序求解其数值解。结合近几年比较经典的智能优化算法—人工鱼群算法和熟知的蒙特卡罗算法求解二重积分的数值解，将蒙特卡罗算法求解二重积分数值解的思想引入到人工鱼群算法中，改进了人工鱼群算法中的适应度函数和积分求和式［14-17］。计算结果表明:采用混合算法和其他算法相比较，二重积分数值解的精确度有所提高。

1 人工鱼群和蒙特卡罗的混合算法

采用人工鱼群算法求解二重积分的数值解，是基于被积函数的凹凸形状来随机的划分积分区域，其思路是:首先在二重积分的积分范围内任意生成指定数目的点;然后按照一定的规则，采用人工鱼群算法对其进行优化，从而更好地求解二重积分的数值解，并克服传统的求二重积分方法中的不足。

应用蒙特卡罗方法来求二重积分的数值解，其中心思想是:序列化积分区域中产生的非均匀随机点，将被积函数所对应的随机变量的算术平均值视为其积分的近似值，即

结合人工鱼群算法和蒙特卡罗方法，来求解二重积分的数值解，主要是针对文献［14］中人工鱼群算法的适应度函数和积分求和公式进行改进(分别参见2)和7))，引入蒙特卡罗求积分的思路。既保留其各自算法的优点，又节省计算时间、提高计算精度、算法的收敛性较好，同时相对蒙特卡罗方法减少节点数目。

设关于x，y 的二元函数f(x，y)为区域D:a1≤x≤b1，a2(x)≤y≤b2(x)上满足蒙特卡罗算法条件的有界函数［2］，采用混合人工鱼群和蒙特卡罗算法求函数f(x，y)在区域D 上的二重积分的数值解的步骤如下

1)算法开始，设定人工鱼群算法的参数，初始化人工鱼;

2)计算每条人工鱼的适应度函数值，更新公告板;不同于文献［1］该算法中人工鱼的适应度函数为

计算积分区域D 划分成的每个小矩形的4 个顶点和矩形中心对应的函数值，并找出这5 个函数值中的最小值Mini和最大值Maxi. 在这里若函数f(i)的值越趋于0，则表示该人工鱼个体(即该分割方法)越优［14］。

3)模拟执行追尾、聚群行为，选择优的行为作为人工鱼的前进方向;

4)如果2 个行为都没有改进，则执行觅食行为;

5)重复2);

6)判断是否满足结束条件:是继续7)，否转2);

7)计算二重积分的数值解并输出结果，算法结束。

文中的积分求和公式，参照蒙特卡罗算法表示为

其 中 f(xi，yi)，f(xi+1，yi)，f(xi，yi+1)，f(xi+1，yi+1)，f(xmid，ymid)分别为积分区域D 划分成的小矩形的4 个顶点和矩形中心对应的函数值［14］，β = 8.

2 示例演算

已知这个二重积分的准确值为5.100 170 0，在(0.0)点被积函数无定义，当变量x 方向趋近下限时，函数图形变化剧烈。文中算法的参数设置为

表1 几种算法的积分值及相对误差Tab.1 Integral value and the relative error of several algorithms

图1 适应度函数值和迭代次数、二重积分值和迭代次数的关系曲线Fig.1 Relation curves fitness function value and the number of iterations，the curve of double integral value and number of iterations

3 结 论

使用计算机方便快捷的求解二重积分的数值解，在数学问题领域中一直占据不可或缺的地位。将蒙特卡罗求解二重积分数值解的思想引入到人工鱼群算法中，改进人工鱼群算法中的适应度函数和积分求和公式的人工鱼群和蒙特卡罗混合算法更加有利于二重积分的数值解求解方法的发展。

在采用人工鱼群算法和蒙特卡罗的混合算法求二重积分时，适应度函数值相对趋近于0，二重积分值也基本收敛于积分值，分割点数目为100时，误差已经是0.000 410 7. 实验表明，文中提出的混合改进算法在一定程度上使得分割点的数目得以减少，收敛的速度和计算的精度也有所提高。

References

［1］ 王军伟，王兴伟，黄 敏.一种基于禁忌人工鱼群算法的智能QoS 组播路由算法［J］.小型微型计算机系统，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］ 罗景峰，王莹莹.基于鱼群算法的全终端网络可靠性优化设计［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］.计算机学报，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］ 王锡淮，郑晓鸣，肖健梅.求解约束优化问题的人工鱼群算法［J］.计算机工程与应用，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］ 周永权，张明，赵 斌.基于进化策略方法求任意函数的数值积分［J］. 计算机学报，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］ 王小华，何怡刚，曾喆昭.三角基函数神经网络算法在数值积分中的运用研究［J］. 电子与信息学报，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］ 曲良东，何登旭，曾邵东.基于人工鱼群算法的优化分割数值积分算法［J］.计算机应用与软件，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］ 黄华娟，周永权，韦杏琼，等.求解矩阵特征值得混合人工鱼群算法［J］.计算机工程与应用，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］ 王冬冬，周永权.人工鱼群算法在求解非线性方程组中的应用［J］.计算机应用研究，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］. 微电子学与计算机，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］ 徐钟济.蒙特卡罗方法［M］. 上海:上海科学技术出版社，1985.XU Zhong-ji. Monte carlo method［M］. Shanghai:Shanghai Science and Technology Press，1985.

［13］ 刘辉玲，叶 锋.计算多重积分的均匀随机数蒙特卡罗法的实现［J］.电脑知识与技术，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］ 聂黎明，周永权.用人工鱼群算法求解二重数值积分［J］.算机工程与应用，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］. 海南师范大学学报:自然科学版，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］. 系统仿真学报，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］ 谢竹诚，周永权.一种基于AFSA 与RST 分类规则挖掘算法［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.