论文研究-一种全局和声搜索算法求解绝对值方程.pdf

所需积分/C币:9 2019-07-22 21:07:00 1.85MB .PDF
16
收藏 收藏
举报

绝对值方程Ax-|x|=b是一个不可微的NP-hard问题。在假设矩阵A的奇异值大于1时, 给出了一个求解绝对值方程的全局和声搜索算法。新的和声搜索算法使用了位置更新和小概率变异策略, 实验结果表明, 该算法具有较强的全局搜索能力, 且收敛快、数值稳定性好、参数少等优点, 是求解绝对值方程的一种有效算法。
3278· 计算机应用研究 第30卷 时间(取50次的平均值)。 出了n=30、50、100、500时各种算法运行50次的平均适应值 表1四种算法运行50次的统计结果比较(n=30) 收敛曲线和最优目标值的盒图。 算法最优适应值平均适应值最差遹应值标准差运行时间/s AVEL 5 AVEl CHS9.2027e+041.6059e+052.7417e+053.6202e+048.3957e-01 HSDE, 6 +051.1423e+01.6868c+062.0711e+054.7793c+O0 AVE HSDE I +52.2649+054.3形925e+056.60162e+045.C517e+O0 NGHS5.4170e-091.5357e-072.1749e-063.4313e-078.1919e-0 CHS8.4102c+031.6495e+042.6750c+044.1129+038.1480c-01 10 UISDE5.5664e+041.2532e+051.7641e+052.5885e+044.7705c+CC 10 004081.216 CHS HSDE IHSDE NGHS IHSDE1.1704e+042.2954e+043.87C9e+047.0819e+034.9189+C0 NGHS1.5215e-042.5292-032.3585e-023.4687e-038 01 AVE2 02 AVE CHS1.0808e+032.2158e+033.646e+036.0179e+027 16 HSD6.7723e+U31.36579+041.9395∈+042.8165e+034.4762e+CU 10题 14 AVE3 o 1 THSDE 2 +033.4559+034.8272c+035.6147c+024.9C08c+C0 NGHS 2 077.3469e-064.8087e-058.3835e-067.9148e-01 表2四种算法运行50次的统计结果比较(n=50) 2FEr 算法最无适应值平均适应值最差适应值标准差运行时间/s 0040.81.2162 CHS HSDE THSDE NGHS iterator CHS1.4076e+C61.9600e+002.5592e+062.6971+058.6353e-01 AVE AⅴE HSDE7.2721e+C69.7055e+061.1462e+078.6967e+057.185le+00 AVel 10 HSDF.1.9524e+C62.8504+063.9498+064.5986+057.9645e+00 三10 NGHS7.9466e-032.4554e-027.9851e-021.4501e-028.5382e-01 CHS2.2685e+053.8416e+055.7613c+057.6330+048.5858e-01 HSDE1.7613e+C62.78le+062.57%6e+062.3648 10 10 2000 IHSDE3.8619e+055.9135e+059.2489+059.986le+047.9347e+0 004081.2162 NGHs9.5062e-014.9388e+001.4936e+012.6038e+008.8145e-01 CHS HSDE IESDE NGHS 7.8880+038.4927e-01 HSDE1.4533e+052.06l7e+052.4764e+052.5512e+047.7924e+00 图1平均适应度线和最优目标值分布(=30) D5.02lle+047.5099+041.02386+051.2826e+048.5660e+(U AVEl AVET 102 NGHS7.1840e-022.4648e-016.9349e-011.1961e-018.6134e-01 10 表3四种算法运行50次的统计结果比较(n=100) 104 算法最話应倌平均适应值量差应佰标准差运行时间/s 10 HSDE4.0257e+074.83l6e+075.l648e+072.4598c+061.1835e+01 CHS HSDE IHSDE NGHS IISD1.5808e+071.8704e+072.1684e+071.4164e+061.3024e+0l Iteration VE NGHS4.1379e+027.5540e+021.2507e+032.0802e+021.0317e+00 CHS8.2487e+C61.1055e 1.3449∈+071.1606e+061.035fe+O0 HSD3.0548e+073.63679+们74.138Ce+U72.0790e+061.2283e+O 10 0.5 s10 0 HSDE2.9494e+C63.253le+003.5407e+01.6005e+051.212lt+01 04081216 CHS HSDE THSDE NGHS Iteration HSDF.1.3489e+0 10e+061.9430e+061.4926e+051.3342e+01 HS1.6158e+033. 036.2288e+039.4701e+021.0377 AVE 表4四种算浤运行50次的统计结果比较(n=500) 算法最优适应值平均适应值最差适应值标差运行时问/s HSDE4.7890e+C85.0700e+085.22T0e+088.75 20y> ge +0I 0000 0.5 AVE HSDE2.7699c+C82.9283+083.0824c+087.215 6.2238c+O1 10004081 CES HSDE IHSDE NGHS iteration 10 NGHS2.4853e+072.7896e+073.1636e+071.2396e+065.6629e+0 CllS4.3478e+094.7459e+095.C696t+091.478le+085.9196e+C0 冬2平均适应度曲线和最优目标值分布(m=50 HSDE8.3652e+C98.9958+099.4959+092.2628e+085.932e+01 AVEZ 从表1~4中的统计结果可以看出,针对求解AVE问题 HSDF4.9755e+095.3479+m95.6429e+091.4731+086 N(HS算法计算结果明显优于CHS、HSD和HSDE;整体趋势 NGHS5.1505e+085.9110e+086.4987e+083.3433+075.7371e+00 CH4.0863e+C84.3636g+04.5%85e+U81.1142+们76.C9U7e+(0 是NGHS>>CHS>HSDE>HSDE。这表明NGHS算法具有 HSDE6.5450e+C86.9220e+087.2491e+081.5024e+075.976Ce+O 更强的全局搜索能力;对大规模的AⅤE问题,NGHS算法在运 THSDE4.6276e+C85.0695e+085.4273c+081.5747e+076.292fe+Cl 行时间上也能达到CHS算法的水平。由于HSDE与 IHSDE算 NGHS1.2001.406701.5+022+65.9200法中加入了差分操作和混沖序列,因此算法运行时间大于经哄 为了更清楚地给出四种算法的拽索能力.图1-4分别给的和声搜索算法。 第11期 雍龙泉:一种全局和声搜索算法求解绝对值方程 3279 4结束语 [3 ROHN J. On unique solvability of the absolute value equation[ J] tim lett,2009,3(4) AVE问题是一个NP-hard问题,本文使用一种仝局和声搜 [4 ROHN J. An alyorithm for solving the: absolute value equation[ J] 索算法来求解AVE问题,并通过一系列的数值实验验证了 Electronic Journal of Linear Algebra, 2009(18): 589-599 NGHS的性能。实验结果表明NCHS算法具有较强的全局搜5!mON. An algorithm for computing all solutions of an absolute value equation[J. Optim Lett, 2012, 6(5): 851-856 索能力,为求解大规模的AVE问题提供了一种新的解决思路。[6 MANGASARIAN O I, MEYER R. Absolute value equation avEl AvEl Linear Algebra and Its Applications, 2006, 419(5): 359-367 死钟中 pppppMEDD 7 MANGASARIN O L. Absolute value programming J 1. Computa 园 104 ion and Application [8 MANGASARIN O L. Absolute value equation solution via concave 10 minimization J. Optim Lett, 2007, 1(1): 3-8 0.5 9 MANGASARIN O L A generlaized Newton method for absolute value CHS HSDE IHSDE \GH Iteration 104 quations[ J. Optim Lett, 2002, 3 l01-108. AVE2 x10 AVE2 10 MANGASARIN O L. Knapsack feasibility as an absolute value equ 3.5 tion solvable by successive linear programming JI. Optim Lett 10 35251 2009,3(2):161-170 [11 CACCETTA L, QU Biao, ZHOU Guang-lu. a globally and quadrati cally convergent method for absolute value equations[ I. Computa 0 tional Optimization and Applications, 2010, 48(1): 45-58 04081.216 CHS HSDE IHSDE NGHS iteration [12 PROKOPYEV 0. On equivalent reformulations for 3.510° AVE equations[ J]. Computational Optimization and Applications 2009,44(3):363-372 13 HU Shen-long, HUANG Zheng-hai. A note on absolute value equa ions[J]. Optim Lett,2010,4(3):417-424 [14]魏庆举.绝对值方程的广义牛頓算法及其收敛挂[D].北京:北京 交通大学,2009 0040 iterati .2 1.62 CHS HSDE IHSDE NGHS 15 ZHANG C, WEI Q J. Global and finite convergence of a generalized 图3平均适应度曲线和最优目标值分布(n=100) Newton method for absolute value cquations [J] Journal of Optimi AVEL AVEl zation Theory and Applications, 2009, 143(2): 391-403 10 「16雍龙泉.绝对值等式问趑的一个求解方法「J].科技导报,20lU 28(5):60-62 「17丨雍龙泉.迭代法求解实对称矩阵绝对值方程「J].西南大学学报 2012,34(5):32-37 [I8]雍龙泉.基于差分进化—单纯形混合算法求解绝对值方程[J] 01 004081216 CHS HSDE IHSDE NGHS 计算机应用研究,2011,28(9):3327-3329 lleraliojl 「19]雍龙泉.基于凝聚函数的和声搜索算法求解绝对值方裎「J].计 AVE2 103 AVE2 算机应用研究,2011,28(8):2922-2926 I 20 GEEM Z W, KIM J H, LOGANATHAN C V. A new heuristic optimi zation algorithm: harmony search [J]. Simulation, 2001, 76(2): 60- [21]ALIA O, MANDAVA R. The variants of the harmony seare h algo- rithm: an overview[ J. Artificial Intelligence Review, 2011, 36 16 CHS HSDE ISDE NGES iteration (1):49-68. AVe 103 AVE [22 ZOU De-xuan, GAO Li-qun, WU Jian-hua, et al. A novel global har- 一NCRE 7654 mony search algorithm for reliability problems J. Computers In dustrial Engineering, 2010, 58(2): 307-316 L 23 ZOU De-xuan, GAO Li-qun, LI S, et aL. Solving 0-1 knapsack prob- 钟半 lem by a novel global harmony search algorithm[ J]. Applied Soft 004081.216 CHS HSDE IHSDE NGHS Computing,2011,11(2):1556-1564 eatlon [24]雍龙泉,和声搜索算法研究进展[J.汁算机系统应用,2011,20 图4平均适应度曲线和最优目标值分布(n=500) (7):244-248 参考文献 [25 CHAKRABORTY P, ROY GG, DAS S, et aL. An improved harmony 1 ROHN J. Systems of linear interval equations[ J 1. Linear Algebl search algorithm with differential mutation operator[I. Journal Fun and Its Applications, 1989, 126: 32-78 damenta Informaticae, 2009, 95(4): 401-426 L2」RONJ. A theorem of the alternatives for the equation Au+Blx-[26]雍龙泉,拓守恒.基于凝聚函数的拟牛頓算法求解绝对值方程 b[J. Linear and Multilinear Algebra, 2004, 52(6): 421-426 [J].系统科学与数学,2012,32(11):1427-1436

...展开详情
试读 4P 论文研究-一种全局和声搜索算法求解绝对值方程.pdf
立即下载 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-一种全局和声搜索算法求解绝对值方程.pdf 9积分/C币 立即下载
1/4
论文研究-一种全局和声搜索算法求解绝对值方程.pdf第1页

试读结束, 可继续读1页

9积分/C币 立即下载