基于人工蜂群算法的非线性方程组求解研究

《自动化仪表》第 34 卷第 2 期 2013 年 2 月 河北省教育厅自然科学基金资助项目( 编号: z2010165) ; 河北省教育厅自然科学青年基金资助项目( 编号: 2011226) 。 修改稿收到日期: 2012 － 03 － 11。 第一作者刘佳( 1980 － ) ，男，2007年毕业于太原科技大学计算机软 件与理论专业，获硕士学位，讲师;主要从事人工智能的研究。 基于人工蜂群算法的非线性方程组求解研究 Research on the Solving Method Based on Artificial Bee Colony Algorithm for Nonlinear Equations 刘 佳1 周真真2 夏少芳3 王军峰1 (石家庄铁路职业技术学院信息工程系1，河北 石家庄 050061; 石家庄科技工程职业学院信息工程系2，河北 石家庄 050800;邢台学院信息科学与技术系3，河北 邢台 054001) 摘 要:为了更有效地求解复杂的非线性方程组，引入了人工蜂群算法。考虑到人工蜂群算法后期表现出的收敛速度慢、容易陷入 局部最优值的缺点，提出了一种新的人工蜂群优化算法(IABC)。新算法对工蜂进行邻域搜索产生新解的进行了改进，引入了尝 试次数，修改了向新食物源靠拢的递进步长，加快了原有算法的收敛速度。试验结果表明，改进算法较好地平衡了全局搜索能力和局 部搜索能力，是一种求解非线性方程组的高效算法。 关键词:人工蜂群算法 非线性方程组 邻域搜索 全局优化 人工智能 中图分类号:TP391 + ． 9 文献标志码:A Abstract:To solve the complex nonlinear equations more effectively，the artificial bee colony (ABC)algorithm is introduced． Considering the demerit of artificial bee colony algorithm，i． e．，easily to fall into local optimum value because of the slow late convergence speed，an improved artificial bee colony (IABC)optimized algorithm is proposed． The new algorithm improves the method for producing new solution when bees are doing neighborhood search，introduces the number of attempts，modifies the progressive step moving to a new food resource，and accelerates the original convergence speed． The test result indicates that the improved algorithm well balances the global and local seeking capability，so it is a highly efficient algorithm for solving nonlinear equations． Keywords:Artificial bee colony algorithm Nonlinear equations Neighborhood search Global optimization Artificial intelligence 0 引言 非线性方程组的求解方法长期以来是数学和工程 应用中一个重要的研究内容。传统的解法主要有迭代 法、牛顿法、梯度法、共轭方向法等，但这些方法对方程 组的特性要求很高，对初值的要求很严格［1］，对复杂方 程组的求解还存在很多障碍。近年来各种人工智能优 化算法被广泛地应用在非线性方程组的求解中，包括 遗传算法(genetic algorithm，GA)［2 － 3］、微粒群算法 (particle swarm optimization，PSO)［4］、神经网络算法［5］ 等。这些算法求解时对初值的选取比较敏感，且容易 陷入局部极值，求解的精度不够。人工蜂群算法［6 － 7］ (artificial bee colony，ABC)是一种全局优化算法，与具 体问无关，只使用相应的函数值，并且算法对初值选 择不敏感，具有较强的鲁棒性和较好的收敛性能，已经 广泛应用到旅行商问题(traveling salesman problem， TSP)［8］、路径［9 － 11］等数值优化问题上，并取得了 较好的效果。 1 问题描述 非线性方程组的一般形式为: Qi(x)= 0 i = 1，2…，n (1) 式中:x = (x1，x2，…，xn)∈D 为矢量;D∈R n，D = {(x1，x2，…，xn)∣ ai≤xi≤bi，i = 1，2…，n }。 为便于人工蜂群算法求解，构造函数 T(x) : T(x)= ∑ n i = 1 Q2i(x槡 ) (2) 因此在解区间 D 内求解非线性方程组的问题就 转化为函数优化问题: Min T(x) (3) 式中:(x1，x2，…，xn)∈D。 求得满足条件的 T(x)时，对应的矢量 x即为方程 组的解。 2 ABC算法的基本原理 在 ABC算法［12］中，最小搜索模型包含三个基本 组成要素:食物源、蜂群、蜂群个体间的信息交流机制。 91 基于人工蜂群算法的非线性方程组求解研究 刘 佳，等 PROCESS AUTOMATION INSTRUMENTATION Vol. 34 No. 2 February 2013 食物源的位置代表优化问题的一个可能解，食物源的 花蜜量对应相应解的质量或者适应度。蜂群中工蜂按 分工不同，划分为引领蜂、跟随蜂、侦查蜂。工蜂的基 本行为有搜索食物源、为优质食物源引导跟随蜂和放 弃劣质食物源。一个食物源对应一个引领蜂，也就是 说食物源的个数等于引领蜂的个数。寻找花蜜量最高 的食物源就是一个寻找最优解的过程。 首先，ABC算法生成含有 NS 个解(食物源)的初 始种群。每个解 x i(i = 1，2，3，…，NS)是一个 D 维的 向量或者矢量。经过初始化，引领蜂、跟随蜂、侦查蜂 开始进行循环搜索，循环次数为 Cm。引领蜂先对对应 的食物源(解)进行一次邻域搜索，并将在邻域范围内 搜索到的新食物源与原来的食物源进行对比，最后选 择适应度较高的食物源。所有的引领蜂完成搜索之后 通过摇摆舞的形式将食物源的信息与其他跟随蜂共 享，故跟随蜂可以依据某种概率来选择到哪个食物源 采蜜。食物源的适应度越高，被选择的概率越大。随 后，跟随蜂选择完相应的食物源后，也在该食物源附近 做一次邻域搜索，并选择适应度较高的食物源。 在进行 Cm 次循环过程中，如果某个食物源(解)经 过 l次循环之后没有得到改善，那么这个解就要被丢 弃。假设被丢弃的解是 xi，那么就由侦查蜂通过式(4) 产生一个新的解来代替 xi。 xij = x j min + rand(0，1)×(x j max － x j min) (4) 式中:j∈{1，2，3，…，D}为 D 维解向量的任何一个分 量;xjmax、x j min为该分量的两个边界取值;rand(0，1)为 ［0，1］之间的随机数。 跟随蜂根据概率值 Pi 选择食物源是按照轮盘赌 方式进行的，Pi 根据式(5)进行计算: Pi = fi ∑ NS n = 1 fn (5) 式中:fi 为第 i个解的适应度。 引领蜂和跟随蜂在第 i 个解 x i 周围进行邻域搜 索，依据式(6)产生一个新解 v i: vij = xij －Φ ij ×(xij － xkj) vip = xip(p≠j{ ) (6) 式中:p、j∈{1，2，3，…，D}，k∈{1，2，3，…，NS}，p为除 j 外的其他维变量，k和 j都是随机生成的变量且 k≠i;Φij 为［－1，1］之间的随机数。 基本 ABC算法的唯一缺点是过早收敛、后期收敛 速度较慢。为了提高 ABC算法的收敛速度和精度，有 必要对其进行改进。改进后的算法已经成功应用到非 线性方程组的求解上。 3 改进的 ABC算法 3． 1 搜索食物源的创新方法 在基本的人工蜂群算法中，引领蜂和跟随蜂在第 i 个解 x i 周围进行邻域搜索，并依据式(6)产生新解。 公式中的 k是随机生成的，是与 i 不同的另一个解(食 物源)。解 xk 的适应度 fk并不一定优于 x i 的适应度 fi，因此算法在不知 xk 好坏的情况下，盲目地从解 x i 向 xk 靠拢，会大大增加算法的随机搜索性能，降低算 法的收敛速度。假如新搜索到的解 xk 的适应度 fk 大 于 fi，式(6)也是随机选择 x i 中的某一维变量 j 向 xk 的第 j维变量靠拢或进化，而不是全部维数都向着 xk 进化，同样也会增加算法搜索的盲目性，降低算法的效 率。针对以上存在的问题，按如下程序进行改进。 if(fk ＞ fi) {vi = xi +Φij × xk － xi ‖xk － xi‖ ;} if(fk ＜ fi) { for(i = 0;i ＜ Nt;i + +) if(fk ＞ fi) {vi = xi +Φij × xk － xi ‖xk － xi‖ ; break;} if(i≥Nt) { vij = xij －Φij ×(xij － xkj) vip = xip(p≠j{ ) } } 程序中 j∈{1，2，3，…，D}，针对每一个维数 j，都 产生一个［－ 1，1］之间的随机数 Φ ij。改进后结果表 明，如果 xk 优于 x i，那么将 x i 所有的变量都向着 xk 靠 拢，而不是某一维变量的靠拢，并且对靠拢递进的步长 进行了调整。如果 fk ＜ fi，则重新选择一个 xk，直到满 足fk ＞ fi为止;如果重复选择 Nt 后仍不能找到满足条 件的 k值，则按式(6)产生新解。 调整旧食物源向新食物源的递进步长，便于算 法得到更加高精度的解;最大尝试次数 N t 的引入， 加速了算法向高质量解的靠拢，提高了收敛到全局 最优解的速度，并在一定程度上帮助算法跳出了局 部最优值。仿真试验表明，算法的收敛性能得到大 大改进。 3． 2 求解非线性方程组的算法步骤 改进后的 ABC算法称为 IABC算法，IABC算法的 具体步骤如下。 ① 初始化各参数:食物源的个数 = 引领蜂的个 02 基于人工蜂群算法的非线性方程组求解研究 刘 佳，等 《自动化仪表》第 34 卷第 2 期 2013 年 2 月 数 =跟随蜂的个数 = NS、迭代次数 Cm 和 l、Nt 等参数。 ② 产生初始解集{x i | i = 1，2，3，…，NS}，并计算 各个解 x i 的适应度，记录目前最好的解。 ③ 置外循环 c = 1。 ④ 设置各个解的保留次数 si = 0。 ⑤ 针对各个引领蜂 i，按照 3． 1 节叙述的方法分 别产生新解 v i。如果 v i 的适应度大于 x i，则 x i = v i，si = 0;否则 x i 不变，si = si + 1。 ⑥ 计算各个解 x i 的适应度，并根据式(5)计算相 应的概率值 Pi。 ⑦ 每个跟随蜂根据相应的 Pi 选择食物源(解) ，并 按 3． 1节的方法进行邻域搜索产生新解 vi。如果 vi 的 适应度大于 xi，则 xi = vi，si =0;否则 xi 不变，si = si +1。 ⑧ 通过比较，记录目前最好的解。 ⑨ 检查各个解的保留次数，如果某个解 x i 的保留 次数 si = l，则将解 x i 丢弃，由侦查蜂根据式(4)产生 一个新解代替 x i，并置 si = 0。 ⑩ c = c + 1。 瑏瑡 如果 c ＜ Cm，则转步骤⑤;否则输出最好的解， 结束程序。 4 算例及 为了验证 IABC 算法的有效性，选择了比较复杂 的非线性方程组进行测试。方程组 1 和方程组 2 采用 文献［3］中的实例，方程组 3 采用文献［5］中的实例。 方程组 Q1(x) : 0． 05x21 － 0． 05x 2 2 － 0． 125x1 + 0． 1x2 － 3． 8 = 0 0． 1x1x2 － 0． 1x1 － 0． 125x2 + 0． 125 = 0 － 100≤xi≤ { 100 (7) 方程组 Q2(x) : x1 + 0． 25x 2 2x4x6 + 0． 75 = 0 x2 + 0． 405e (1 + x1x2)－ 1． 405 = 0 x3 － 0． 5x4x6 + 1． 5 = 0 x4 － 0． 605e 1 － x23 － 0． 395 = 0 x5 － 0． 5x2x6 + 1． 5 = 0 x6 － x1x5 = 0 － 5≤xi≤      5 (8) 方程组 Q3(x) : xx21 + x x1 2 － 5x1x2x3 － 85 = 0 x31 － x x3 2 － x x2 3 － 60 = 0 xx31 + x x1 3 － x2 － 2 = 0 － 2≤x1≤5，－ 1≤x2≤4，－ 1≤x3≤      2 (9) 分别运行 ABC、IABC和基本的 GA 算法各 30 次， 对三个方程组进行求解。求得的各个变量的值取最优 结果，各个方程组 T(x)的值取 30 次的平均值;IABC 算法中 NS 的值为 50，Cm 设置为 2 500，l 为 100、Nt 的 值为 5。数据结果如表 1 所示。 表 1 三种算法的结果对比 Tab． 1 Inter-comparison of the results from three of the algorithms 方程组 计算结果 理论值 GA ABC IABC Q1(x) (x1，x2) (10，1) (－ 7． 5，1) (9． 21，0． 62) (9． 21，0． 62) (9． 999，0． 999) (－ 7． 499，0． 999) (10． 000，1． 000) (－ 7． 500，1． 000) T(x) 0 7． 471 × 10 －1 1． 960 × 10 －5 1． 677 × 10 －6 Q2(x) (x1，x2，…，x6) (－ 1，1， － 1，1，－ 1，1) (－ 0． 85，0． 76，－ 1． 25， 0． 67，－ 1． 20，1． 01) (－ 1． 163，1． 131，－ 0． 989， 0． 972，－ 0． 955，1． 149) (－ 0． 999，0． 999，－ 1． 000， 0． 999，－ 1． 000，0． 999) T(x) 0 1． 624 × 10 －1 2． 249 × 10 －1 5． 374 × 10 －4 Q3(x) (x1，x2，x3) (4，3，1) (3． 98，2． 89，0． 68) (4． 002，3． 022，1． 063) (4． 000，3． 000，1． 000) T(x) 0 2． 370 1． 844 2． 347 × 10 －3 从表 1 可以看到，对于方程组 Q1(x) ，ABC 和 IABC算法运行 30 次能求出全部的解，而基本的 GA 算法只能收敛到一个解，而且精度不高。测试结果表 明，对于三个方程组，IABC 算法求解的效果明显优于 其他算法。 随机选取一次采用三种算法分别求解Q3(x)方程 组的进化过程，结果如图 1 和图 2 所示。从图 1 和图 2 也可以看出，IABC 算法明显优于 GA 算法和 ABC 算法。 图 1 ABC、IABC求解 Q3 ( x) 的仿真过程 Fig． 1 Simulation process of ABC，IABC solving for Q3 ( x) 12 基于人工蜂群算法的非线性方程组求解研究 刘 佳，等 PROCESS AUTOMATION INSTRUMENTATION Vol. 34 No. 2 February 2013 图 2 GA算法求解 Q3 ( x) 的仿真过程 Fig． 2 Simulation process of GA solving for Q3 ( x) 5 结束语 针对基本 ABC算法存在的不足，对蜂群邻域搜索 过程中产生新解的方法进行了改进。改进后的算法 IABC加快了原 ABC 算法向全局最优解的收敛速度， 避免了陷入局部最优解的缺点，提高了算法的收敛精 度。数值试验表明，改进后的算法优化效果明显，简单 易实现、鲁棒性好，可以用于求解复杂非线性方程组。 参考文献 ［1］ 史永宏，张茜．基于遗传算法优化的智能控制器［J］． 微型电脑 应用，2010，26(2) :33 － 34． ［2］ 罗亚中，袁端才，唐国金．求解非线性方程组的混合遗传算法［J］．计 算力学学报，2005，22(1):109 －112． ［3］ 周丽，姜长生．非线性方程组求解的一种新方法［J］． 小型微型 计算机系统，2008，29(9) :1709 － 1912． ［4］ 陈长忆，叶永春．基于粒子群算法的非线性方程组求解［J］． 计 算机应用与软件，2006，23(5) :137 － 138． ［5］ 孙银慧，白振兴，王兵．求解非线性方程组的迭代神经网络算法［J］． 计算机工程与应用，2009，45(6):55 －57． ［6］ 高卫峰，刘三阳，姜飞．混合人工蜂群算法［J］．系统工程与电子 技术，2011，33(5) :1167 － 1169． ［7］ 郑伟，刘静，曾建潮．人工蜂群算法及其在组合优化中的应用研 究［J］．太原科技大学学报，2010，31(6) :467 － 470． ［8］ 胡中华，赵敏．基于人工蜂群算法的 TSP 仿真［J］． 北京理工大 学学报:自然科学版，2009，29(11) :978 － 981． ［9］ 杨进，马良．蜂群优化算法在车辆路径问题中的应用［J］． 计算 机工程与应用，2010，46(5) :214 － 216． ［10］寇明顺，叶春明，陈子皓．应用蜜蜂繁殖进化型粒子群算法求解 车辆路径问题［J］．工业工程，2012，15(1) :23 － 27． ［11］李娅，王东．基于混沌扰动和邻域交换的蚁群算法求解车辆路 径问题［J］．计算机应用，2012，32(2) :444 － 447． ［12］肖永豪，余卫宇．基于蜂群算法的图像边缘检测［J］． 计算机应 用研究，2010，27(7) :2748 － 2749． (上接第 18 页) Jersey:Prentice-Hall，2002 ． ［2］ 柳玉甜，李昌刚，胡俊杰．非线性系统故障诊断与容错控制技术［J］． 自动化仪表，2011，32(9):1 －4． ［3］ Dorf R．现代控制系统［M］． 8 版．邹逢兴，译．北京:高等教育出 版社，2002． ［4］ 鲁兴举，彭学锋，郑志强． 一种双旋翼控制系统的建模与仿 真［J］．实验室研究与探索，2007，26(7) :27 － 30． ［5］ Quanser． 2DOF helicopter model［EB /OL］．［2011 － 12 － 08］． http:/ /www． quanser． com /english /html /products / fs _ product _ challenge． asp?lang_code = English＆pcat_code = exp-spe＆prod_ code = S2-2dofheli＆tmp1 = 1． ［6］ Wikipedia． Lagrangian mechanics［EB /OL］．［2011 － 12 － 28］． http:/ / en． wikipedia． org /wiki /Lagrangian_mechanics． ［7］ 孙世贤，黄圳圭．理论力学［M］．长沙:国防科技大学出版 社，1997． ［8］ Williams II R L，Lawrence D A． Linear state-space control systems［M］． New Jersey:John Wiley ＆ Sons，2007． ［9］ 赵万青，魏利胜，费敏锐． 基于 LQR 的双并联倒立摆系统的建 模与仿真［J］．自动化仪表，2009，30(4) :1 － 4． ［10］王进华．二次型最优控制问题中的权矩阵与最优控制律［J］．控 制与决策，2007，22(8) :943 － 945，950． ［11］郭阳宽，王正林．过程控制系统仿真［M］．北京:电子工业出版 社，2009． ［12］黄忠霖，黄京．控制系统 MATLAB计算及仿真［M］． 3 版．北京: 国防工业出版社， 檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨檨 2009． 行业信息 AMETEK推出两款超小型 VANEAXIAL 风扇 AMETEK Rotron现已推出两款配备无刷直流感应电机的超小型 Vaneaxial 风扇———Minimax 和 Nanos II /3 风 扇，为关键电子设备和光学设备提供高度可靠的局部冷却。Minimax 和 Nanos II /3 风扇采用具有集成化直流电子 驱动器的新外形，能够使用 28 V直流电源直接操作;其叶轮和导叶采取翼型优化设计，可实现最大的空气动力学 效率，并使噪声降低到最小程度;其尺寸小巧、质量轻，是便携式设备的理想选择。这两款超小型 Vaneaxial 风扇 能够长期可靠使用于要求极为严苛的过程关键电子设备和光学器件中，应用实例包括在坚固的密闭容器中进行 高负荷散热以及使少量气流流过传感器。这两款风扇均达到或超过 MIL － B － 28873 的要求及其他相应的美国 军用和商用航天各项技术规格指标。 更多信息请登陆 www． rotron． com。 22 基于人工蜂群算法的非线性方程组求解研究 刘 佳，等