基于分段随机扰动幅值的随机并行梯度下降算法研究_吴健

求解一类双层规划的自适应变异动态差分进化算法吴亮红;徐睿;左词立;曾照福;段伟涛【摘要】针对一类上层函数和约束函数不具有凸性和可微性要求,而下层函数可微且凸的非线性双层规划问题,首先通过Karush-Kuhn-Tucher(KKT)条件将双层规划问题转换为单层约束非线性规划问题,并结合非固定多段映射罚函数法和精确罚函数法对约束条件进行无约束化处理,然后提出一种改进的动态差分进化算法优化对系列无约束优化问题进行求解.对8个测试实例进行数值计算并与现有算法进行比较.测试结果表明,所提方法是一种求解该类双层规划问题的有效方法.【期刊名称】《中南大学学报（自然科学版）》【年(卷),期】2016(047)010【总页数】9页(P3436-3444)【关键词】双层规划;KKT条件;罚函数法;差分进化算法【作者】吴亮红;徐睿;左词立;曾照福;段伟涛【作者单位】湖南科技大学信息与电气工程学院,湖南湘潭,411201;湖南科技大学信息与电气工程学院,湖南湘潭,411201;湖南科技大学信息与电气工程学院,湖南湘潭,411201;湖南科技大学信息与电气工程学院,湖南湘潭,411201;湖南科技大学信息与电气工程学院,湖南湘潭,411201【正文语种】中文【中图分类】TP18双层规划问题(BLPP)是一类具有主从递阶结构的系统优化问题。

由于这种模型更能描述实际系统的阶层关系和更全面地体现决策者的意愿，故在经济、军事、交通、电力和工程等众多领域具有十分重要的理论意义和应用背景[1−2]。

一般来说，求解双层规划非常困难，这主要包括2方面的原因。

一方面，双层规划问题是1个NP-hard问题，HANSEN等[3]证明即使是最简单的双层线性规划也是强NP-Hard问题。

VICENTE等[4]指出甚至寻找双层线性规划问题的局部最优解也是1个NP-Hard问题。

另一方面，由于上层优化问题的目标函数取决于下层优化问题的解函数，而这个解函数一般是非线性且不可微的，故双层优化问题是1个非凸优化问题。

BP算法的多核并行研究及其在枣无损检测的应用黄磊;王凡;吴素萍【摘要】为提高BP神经网络算法的训练速度,针对BP网络训练过程中层间数据传播,权值更新耗时大的问题进行深入分析.基于单机多核CPU系统环境,运用OpenMP并行技术,设计实现多核架构下基于OpenMP的BP并行算法.将该算法应用于基于高光谱图像技术的长枣糖度无损检测中,实验结果表明,与原串行算法相比,并行算法可以保证算法的相对误差较低,取得较好加速比,该算法在不同平台随着核数的增加,加速比也在增加,验证了其可行性、有效性和可扩展性.【期刊名称】《计算机工程与设计》【年(卷),期】2016(037)009【总页数】5页(P2502-2506)【关键词】BP神经网络;OpenMP并行;多核;并行优化;无损检测【作者】黄磊;王凡;吴素萍【作者单位】宁夏大学数学计算机学院,宁夏银川750021;宁夏大学数学计算机学院,宁夏银川750021;宁夏大学数学计算机学院,宁夏银川750021【正文语种】中文【中图分类】TP302.7传统的BP训练算法[1-3]在网络的训练过程中都是基于串行的执行过程。

针对数据量较大的问题，传统的BP训练过程比较耗时，无法满足大数据应用的需求。

并行处理技术是提高BP网络训练速度的有效方法，目前有基于集群的BP并行方法[4]，但由于编写程序复杂且成本较高，不易推广应用。

还有利用特殊硬件加速[5-8]，例如GPU加速，这类加速技术普遍是利用GPU计算能力，将训练数据传到GPU端进行计算提高训练速度。

多核CPU加速是一个较热的并行研究领域[9-11]，本文对BP算法进行了介绍，分析其耗时部分，结合该算法特点，比较不同核数和不同样本的串并算法时间及效率，分析影响该并行算法加速比的原因，通过OpenMP技术优化了BP神经网络训练过程，实现了多核CPU并行加速。

BP算法可以对枣的糖度进行无损检测[12]，但时间效率不高，可以利用多核并行加速的方法提高效率，本文将并行BP算法应用于对枣的糖度进行无损检测中，并将该算法在台式机四核机器和六核机器上进行实验，都取得了较好的加速效果。

双频激励下含分数阶非线性汽车悬架系统的混沌研究作者：常宇健孙亚婷陈恩利李韶华邢武策来源：《振动工程学报》2021年第06期摘要：研究了含分数阶非线性特性的1/4汽车悬架模型在双频激励下的混沌运动。

运用Melnikov 方法，推导出系统发生异宿混沌运动的解析必要条件，得到系统混沌边界曲面阈值，讨论了悬架系统各参数对混沌边界曲面的影响。

运用时间历程图、频谱图、相图、庞加莱截面图及最大李雅普诺夫指数进行数值验证。

研究表明，在双频激励下悬架系统存在混沌运动，且含分数阶非线性悬架系统中阻尼系数、刚度系数等各参数对混沌边界曲面阈值都有一定影响，其中分数阶项阶数和系数及线性阻尼系数对其影响较大。

关键词：非线性振动;汽车悬架;混沌运动;双频激励;分数阶中图分类号： O322;U463.33 文献标志码： A 文章编号：1004-4523（2021）06-1198-09DOI：10.16385/ki.issn.1004-4523.2021.06.011引言分数阶微积分作为重要的数学分支，于1695年德国科学家 Leibniz 和法国数学家L'Hopital 在探讨1/2阶导数时首次被提出[1]。

然而，由于缺乏应用背景支撑等多方面原因，它长期以来并没有得到较多的关注和研究。

随着20世纪70年代以来对分形和各种复杂系统的深入研究，分数阶微积分理论及其应用开始受到广泛关注，很多学者对分数阶微积分的基本特性进行研究，在基础理论方面取得了很大进展[2⁃6]。

进入21世纪以来，分数阶微积分建模方法和理论在复杂黏弹性材料力学本构关系、反常扩散、高能物理等诸多领域有了若干非常成功的应用[7⁃10]，凸显了其独特优势和不可替代性，所以研究含分数阶微积分方程中的典型力学特性和分数阶参数对动力系统的影响很有意义，大量学者进行着这方面的研究[11⁃13]。

车辆悬架减振装置不仅具有迟滞非线性特性，而且多数阻尼器都具有类黏弹性本构关系，这些黏弹性材料介于弹性和阻尼特性之间，普通的整数阶理论无法准确地描述这种材料的本构关系。

２０２４年３月第３９卷第２期西安石油大学学报（自然科学版）ＪｏｕｒｎａｌｏｆＸｉ’ａｎＳｈｉｙｏｕＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ）Ｍａｒ．２０２４Ｖｏｌ．３９Ｎｏ．２收稿日期：２０２３ ０６ ０３基金项目：国家自然科学基金面上项目“基于频变信息的流体识别及流体可动性预测”（４１７７４１４２）；四川省重点研发项目“工业互联网安全与智能管理平台关键技术研究与应用”（２０２３ＹＦＧ０１１２）；四川省自然科学基金资助项目“基于超分辨感知方法的密集神经图像分割”（２０２２ＮＳＦＳＣ０９６４）第一作者：曹凯奇（１９９８ ），男，硕士，研究方向：遥感图像标注。

Ｅ ｍａｉｌ：８１９０８８３３８＠ｑｑ．ｃｏｍ通讯作者：文武（１９７９ ），男，博士，研究方向：人工智能在地球科学的应用、高性能计算。

Ｅ ｍａｉｌ：ｗｅｎｗｕ＠ｃｕｉｔ．ｅｄｕ．ｃｎＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１６７３ ０６４Ｘ．２０２４．０２．０１６中图分类号：ＴＥ１９文章编号：１６７３ ０６４Ｘ（２０２４）０２ ０１２８ １５文献标识码：Ａ基于改进ＤｅｅｐＬａｂＶ３＋的引导式道路提取方法及在震源点位优化中的应用曹凯奇１，张凌浩２，徐虹１，吴蔚３，文武１，周航１（１．成都信息工程大学计算机学院，四川成都６１０２２５；２．国网四川省电力公司电力科学研究院，四川成都６１００９４；３．中国石油集团东方地球物理勘探有限责任公司采集技术中心，河北涿州０７２７５０）摘要：为解决自动识别方法在道路提取时存在漏提、错提现象，提出一种引导式道路提取方法提高修正效率。

在ＤｅｅｐＬａｂＶ３＋原有输入通道（３通道）的基础上添加额外输入通道（第４通道），将道路的４个极点转化为二维高斯热图后作为额外通道输入网络，网络以极点作为引导信号，使网络适用于引导式道路提取任务；设计并行多分支模块，提取上下文信息，增强网络特征提取能力；融合类均衡二值交叉熵和骰子系数组成新的复合损失函数进行训练缓解正负样本不均衡问题。

蚁群算法综述控制理论与控制工程09104046 吕坤一、蚁群算法的研究背景蚂蚁是一种最古老的社会性昆虫，数以百万亿计的蚂蚁几乎占据了地球上每一片适于居住的土地，它们的个体结构和行为虽然很简单，但由这些个体所构成的蚁群却表现出高度结构化的社会组织，作为这种组织的结果表现出它们所构成的群体能完成远远超越其单只蚂蚁能力的复杂任务。

就是他们这看似简单，其实有着高度协调、分工、合作的行为，打开了仿生优化领域的新局面。

从蚁群群体寻找最短路径觅食行为受到启发，根据模拟蚂蚁的觅食、任务分配和构造墓地等群体智能行为，意大利学者M.Dorigo等人1991年提出了一种模拟自然界蚁群行为的模拟进化算法——人工蚁群算法，简称蚁群算法(Ant Colony Algorithm,ACA)。

二、蚁群算法的研究发展现状国内对蚁群算法的研究直到上世纪末才拉开序幕，目前国内学者对蚁群算法的研究主要是集中在算法的改进和应用上。

吴庆洪和张纪会等通过向基本蚁群算法中引入变异机制，充分利用2-交换法简洁高效的特点，提出了具有变异特征的蚊群算法。

吴斌和史忠植首先在蚊群算法的基础上提出了相遇算法，提高了蚂蚁一次周游的质量，然后将相遇算法与采用并行策略的分段算法相结合。

提出一种基于蚁群算法的TSP问题分段求解算法。

王颖和谢剑英通过自适应的改变算法的挥发度等系数，提出一种自适应的蚁群算法以克服陷于局部最小的缺点。

覃刚力和杨家本根据人工蚂蚁所获得的解的情况，动态地调整路径上的信息素，提出了自适应调整信息素的蚁群算法。

熊伟清和余舜杰等从改进蚂蚁路径的选择策略以及全局修正蚁群信息量入手，引入变异保持种群多样性，引入蚁群分工的思想，构成一种具有分工的自适应蚁群算法。

张徐亮、张晋斌和庄昌文等将协同机制引入基本蚁群算法中，分别构成了一种基于协同学习机制的蚁群算法和一种基于协同学习机制的增强蚊群算法。

随着人们对蚁群算法研究的不断深入，近年来M.Dorigo等人提出了蚁群优化元启发式(Ant-Colony optimization Meta Heuristic，简称ACO-MA)这一求解复杂问题的通用框架。

基础设施改善了农业技术效率吗？——基于异质性随机前沿模型周晓时;李谷成;吴清华【摘要】采用异质性随机前沿模型,测算农村电力、公路、灌溉三大基础设施对中国农业技术效率的影响及其不确定性。

研究结果表明:(1)中国农业生产技术效率仅为0.35,生产效率仍有巨大的优化空间;(2)农村三大基础设施对技术无效率都有显著缓解作用,但也增加了技术效率的不确定性,且作用效果呈现农村公路设施>农村电力设施>农村灌溉设施的排序;(3)公路设施加剧地区技术效率的不确定性,降低了东、中部技术效率,但对西部技术效率有促进作用。

农村电力设施对地区技术效率不确定性有反向作用,仅改善了中部地区的技术效率。

灌溉设施对东部技术效率的改善作用不明显,中部地区由于公共物品特性导致技术效率下降,但显著提升了西部地区技术效率。

基础设施对各地区技术效率不确定性作用方向一致,都为强化效果。

【期刊名称】《农林经济管理学报》【年(卷),期】2017(000)002【总页数】8页(P191-198)【关键词】农村基础设施;技术效率;不确定性;异质性随机前沿模型【作者】周晓时;李谷成;吴清华【作者单位】【正文语种】中文【中图分类】F2基础设施投资是吸纳就业、扩大内需、促进经济增长的重要手段。

在农业生产领域，基础设施更是重要的基础条件[1]。

截至2015年底，中国耕地有效灌溉面积建设达6 612.0万km2，约占世界总数的1/5；农村公路通车总里程378万km，基本实现建制镇或村的“村村通”。

此外，农村用电量从1999年到2014年的增长翻了近两番，达到8 884.4亿kw·h。

此外，2015年“中央一号文件”全文也有12处提到农村基础设施，农村基础设施建设成为提高农业生产能力的重要保障。

早在20世纪40年代，基础设施对经济增长的外部性效应就已引起学者们的关注[2]。

在农业经济发展领域，国内外学者也做了大量研究。

Aigner运用C-D生产函数分别研究了发达和不发达国家的农村基础设施对农业的产出效应，实证结果表明并不能拒绝“基础设施能提高农业产出”的假设[3]。

联合收获机前进速度模糊控制系统多目标遗传优化宁小波;陈进;李耀明;杨广静;吴培;陈思【摘要】针对联合收获机前进速度模糊控制系统参数设计具有主观性,导致作业性能不理想的问题,以切纵流联合收获机样机为研究对象,构建联合收获机前进速度模糊控制系统仿真模型,并建立控制性能和收获性能的优化目标函数来衡量联合收获机的作业性能,利用多目标遗传算法对模糊控制系统的隶属函数和输送槽、割台螺旋输送器和切流滚筒对前进速度的影响因子进行优化.通过对优化前后模型仿真对比和两组田间试验数据分析,表明优化后的控制系统在受外界干扰情况下控制性能得到了较好的保持,收获性能在喂入量变化不大情况下,单位平均损失率分别由1.45％和1.26％降至1.12％和1.14％,联合收获机的总体作业性能得到改善.【期刊名称】《农业机械学报》【年(卷),期】2015(046)005【总页数】7页(P68-74)【关键词】联合收获机;前进速度;模糊控制系统;多目标遗传优化【作者】宁小波;陈进;李耀明;杨广静;吴培;陈思【作者单位】江苏大学机械工程学院,镇江212013;巢湖学院电子工程与电气自动化学院,合肥238000;江苏大学机械工程学院,镇江212013;江苏大学现代农业装备与技术教育部重点实验室,镇江212013;江苏大学机械工程学院,镇江212013;江苏大学机械工程学院,镇江212013;江苏大学机械工程学院,镇江212013【正文语种】中文【中图分类】S225.31联合收获机作业过程中允许损失率和收获效率是衡量联合收获机收获质量的主要因素。

当田间作物条件如作物品种、作物密度等变化时，将直接影响到联合收获机的收获质量。

为了适应田间作物条件的变化，联合收获机必须能相应地改变其前进速度的大小，以保证收获质量。

因此，收获性能良好的联合收获机应在不超过额定喂入量和允许损失率的前提下具有最大的前进速度[1-7]。

现有联合收获机前进速度控制系统一般都采用模糊控制技术。

收稿日期:2005-06-20作者简介:吴健生(1961-),男,广东普宁人,教授,博士生导师,理学博士.E 2mail :wujiansh @.拉东变换在探地雷达资料处理中的应用吴健生,张　昊(同济大学海洋地质国家重点实验室,上海　200092)摘要:为了消除探地雷达剖面中存在的旁侧影响、“X ”形同相轴等线段形干扰,把拉东变换引入到探地雷达资料处理中.通过原理的分析和对水平线性同相轴经离散拉东变换后数据的特征深入研究,建立了水平线性同相轴的振幅大小以及波形曲线与变换结果中心条带数据之间的关系.通过对这种关系的拓展和应用,提出了雷达剖面上线段形干扰特征提取和消除改进的离散拉东变换的方法技术.理论模型实验和实际资料的处理结果都说明了方法的有效性和优越性.关键词:探地雷达;拉东变换;线段形干扰中图分类号:P 631.325 文献标识码:A 文章编号:0253-374X (2005)09-1270-04Application of Radon Transform in G roundPenetrating Rader Data ProcessingW U Jian 2sheng ,ZHA N G Hao(State K ey Laboratory of Marine G eology ,Tongji University ,Shanghai 200092,China )Abstract :In order to deal with the sideward influences ,“X ”interferences and other linear interfer 2ences ,the Radon transform can be used to process the ground penetrating radar (GPR )profile.After analysing on the discrete Radon transform ,it is found that getting linear events from the GPR profile in the Radon transform result directly is infeasible and the method must be modified.With the study on the aclinic linear events and theirs Radon tranform results ,the relationship between events character and their center strips of the transform results is set up.The improved processing method removing linear events with discrete Radon transform is brought up ,whose validity and advantage have been proved by the model testing and the field data results.Key words :ground penetrating radar (GPR );Radon transform ;linear interference 探地雷达的概念于1910年被正式提出,初期应用范围仅限于对电磁波吸收很弱的冰层.随着电子技术的发展,以及现代数据处理技术的应用,20世纪70年代后,探地雷达的应用从冰层、盐矿等弱耗介质扩展到土层、煤层、岩层等有耗介质.现在,探地雷达的应用范围已经涵盖了考古、矿产资源勘探、岩土勘查、无损检测及工程建筑物结构调查等诸多领域,并开发了各种专用的探地雷达[1].但是随着探地雷达应用范围的不断扩展,应用环境的不断复杂,干扰因素也越来越多,造成剖面中的干扰信息呈现多样化的趋势,出现了多种新的干扰类型.图1就是一个例子:剖面中两条同相轴相互交叉,呈“X ”形分第33卷第9期2005年9月同济大学学报(自然科学版)JOURNAL OF TON G J I UN IVERSITY (NATURAL SCIENCE )Vol.33No.9　Sep.2005布.这两条同相轴并不是真实电性结构的反映,而只是一种干扰信息.由于这种线段形干扰能量往往比较强,以至于淹没了剖面中的有效信息,所以在进行解释之前必须将其从剖面中移除,以使其背后的有效信息突出出来.二维滤波(F2K滤波)[2]可以被用来处理这种具有明显倾角的线段形干扰同相轴,但是基于方法本身的特点,二维滤波在去除剖面中线段形干扰同相轴的同时,也对剖面中那些与干扰同相轴具有同样倾角的有效信号同相轴造成了伤害.有时候,这种伤害是人们需要竭力避免的,使用拉东变换进行数据处理就是实现这一目标的途径之一.图1　“X”形干扰Fig.1　“X”interference1　拉东变换的原理拉东变换(或称经典Radon变换)是由奥地利数学家J.Radon于1917年提出来的.作为积分几何学的基石,它为一大类图像重构(层析成像)问题提供了一个统一的数学基础,已被广泛应用于物理、医学、天文、分子生物、材料科学、核磁共振、无损检测、地球物理等方面.在二维平面中,函数f(x,y)的拉东变换的定义为R(r,θ)=∫y∫x f(x,y)δ(r-x cosθ-y sinθ)d x d y 式中:r是原点到直线L(r,θ)的距离,r=x cosθ+ y sinθ;θ为原点到直线的垂线与x轴的夹角(如图2),0≤θ≤π;δ为狄拉克函数.从这个定义出发,拉东变换的实质是沿直线簇积分,如图2中所示直线上各点的能量经过拉东变换,将累加在拉东变换域中的点(r,θ)上.拉东变换的逆变换可以根据投影数据重建图像.根据投影定理,可以得到拉东变换的逆变换定义为f(x,y)=14π2∫∞0∫∞-∞R^(ω,θ)・exp{iω(x cosθ+y sinθ)}|ω|dωdθ式中:R^(ω,θ)是R(r,θ)关于r的傅利叶变换结果[3].图2　拉东变换Fig.2　R adon transform 实际应用中拉东变换的定义更被拓展为沿曲线簇积分,被称为广义拉东变换,如地震数据处理中的抛物拉东变换和双曲拉东变换都是广义的拉东变换在地球物理方面应用的实例.2　方法实现由于拉东变换能将二维数据变换到线参数的域中,数据中的线性特征在变换域中会表现为对应于相关线参数的峰值,所以可以设想利用其将探地雷达剖面中的线段形干扰同相轴移除掉.一个基本的思路便是将原始剖面经拉东变换映射到r2θ域中,然后将线段形干扰在r2θ域中的能量聚焦点移除,再逆变换回时间空间域就可以达到在不伤害其他有效信息的同时,把目标同相轴从剖面中分离的目的.虽然从数学意义上来说,拉东变换和其逆变换都是严格的,f(x,y)和R(r,θ)是一一对应的,但是由于在实际情况下,无论是函数f(x,y),还是拉东正、反变换的计算方法,都得以离散的形式出现.要将拉东变换应用于实践,就必须先解决离散化带来的两个问题.首先是拉东变换聚焦不准的问题.从拉东变换的定义来讲,直线r=x cosθ+y sinθ上各点的能量将聚焦在拉东变换域中的点(r,θ)上.但在数值计算中,数据本身是离散的,连续的积分变成了离散的累加.其结果造成直线上的能量实际是分布在了以点(r,θ)为中心的一个“X”形区域上,要想把它从拉东变换域中移除而不伤害其他的有效信息就变得比较困难.其次是拉东正、反变换造成的平均效应问题.即使对拉东变换的结果不进行任何的改变,由拉东反变换所得到的结果与原始数据仍然存在着差异.这1721　第9期吴健生,等:拉东变换在探地雷达资料处理中的应用 种差异变化表现为细节特征的丢失以及同向轴振幅的平均化,降低了探地雷达剖面的分辨率.为了解决这两个问题,这里引入振幅均匀的假设:认为所要处理的同相轴各道之间拥有均匀的振幅,各道波形上的差异是因为随机背景数据与同相轴数据叠加造成的.在这个假设之下,可以直接建立线段形同相轴振幅、长度与拉东变换结果中“X ”形区域核心数据之间的对应关系.由此计算出干扰同相轴数据并从雷达剖面中将其移去.把从拉东变换域中移去能量焦点转换为在时间-空间域中直接消除干扰同相轴.方法的基本流程如图3所示.首先通过拉东变换将原始剖面变换到拉东变换域,根据目标同相轴在该域中形成的“X ”形区域的核心数据,提取出干扰同相轴的信息并生成只含有干扰信息的干扰剖面,然后将干扰剖面从原始剖面中减去,就达到了消除干扰同相轴的目标.图3　方法流程图Fig.3　Flow chart of the method 这种方法相对于原来的处理思路,有着明显的优点.它降低了干扰提取的难度,提高了干扰提取的精度.由于不使用拉东反变换,提高了计算速度,避免了对细节数据的破坏.还可对原始数据实现分块处理,在提高数据处理灵活性的同时,将处理的副作用限定在一定范围内,便于进一步的处理.这种方法在振幅均匀的前提假设下并不失其现实意义:旁侧影响、“X ”形杂波等线段形干扰等非电性结构产生的同相轴,拥有着极为一致的波形,叠加于有效信息之上,只有将其从剖面上移除了,被其掩盖的有效信息才可以显现出来.下面就是使用这种方法对模型数据和实际资料进行处理后得到的结果.2.1　模型剖面处理结果图4所示的实验使用了包含有两条水平同相轴和两条倾斜同相轴的模型剖面,根据这种方法的前提假设,它们都拥有着均匀的振幅.首先进行的是不含有随机噪声的实验(图4a ),对于这个模型原始剖面分别作了两种处理:去除中间的水平同相轴和去除倾斜同相轴,并在每个剖面的下方列出了其在拉东变换域中的响应剖面.可以看到,这种情况下,目标同向轴被非常干净地移除,同时没有造成其他有效信息的破坏,实验取得了很好的效果.然后在这个剖面中添加50%水平的随机噪声作为背景,仍然进行上述两种处理(图4b ).由于随机的背景数据累加值对于所要提取的响应特征的影响非常微弱,与第一个实验一样,这个实验仍然取得了令人满意的效果,不仅目标同向轴被从剖面中准确地移除,作为背景的随机噪声并没有遭到严重破坏.图4　模型实验结果Fig.4　Processing result of model GPR prof ile2721 同济大学学报(自然科学版)第33卷　2.2　实际资料处理结果实际资料与模型剖面还是存在着一定差异的,在使用上述方法进行处理之前,必须进行一些预处理,以使实际资料能够符合处理方法的应用前提.虽然实际资料中的旁侧影响、“X ”形杂波等线段形干扰往往是由非电性结构产生,有着相似的波形,但是由于衰减效应的存在,这些同相轴在振幅上并不均匀,必须对其进行振幅的补偿和均衡,这在大部分的探地雷达常规处理软件中都可以实现.实际资料中由非电性结构产生的旁侧影响、“X ”形杂波等线段形干扰的能量与有效信号差异比较大的情况也时有发生,处理时不可避免地会出现能量的二次分配问题.但是由于本方法自身的特点,能量的二次分配区域被限制在一定的范围内,从现有资料来看,大部分处理的情况都处于可以接受的范围之内.图5a 所示的是在对地下溶洞的勘测过程中获得的一个雷达剖面,在图中圈出的位置有一个比较明显的溶洞响应.剖面中出现的“X ”形干扰掩盖了有效的信息,造成了对溶洞范围信息判断的困难.为了得到准确的勘测结果,必须将“X ”形干扰从剖面中移除.由于考虑到剖面中存在有与“X ”形干扰同倾角的绕射波,使用二维滤波势必对这部分绕图5　“X ”干扰实际资料处理结果Fig.5　Processing result of “X ”interference in Field Data射波信息造成破坏,不利于后期的处理和解释,所以使用拉东变换方法对这个剖面进行了处理,处理结果如图5b 所示.相对于原始剖面,在图5b 所示的剖面中可以清楚地勾勒出溶洞的具体范围.原来被淹没掉的洞顶反射同相轴也清晰地显现了出来,溶洞的左右边界位置也基本可以确定.整个剖面的质量得到了有效的提高,为进一步的处理与解释奠定了良好的基础.3　结论理论分析和模型实验表明,采用拉东变换处理方法可以消除探地雷达剖面上线段形干扰.为了取得好的处理效果,重要的一方面是对数据进行振幅均衡化等预处理.实际资料处理获得的良好结果说明该方法已能应用于生产实际.处理过程中不可避免会产生能量二次分配的问题,从试验结果看,由此造成的影响不是十分明显,处理结果是可以接受的.当干扰与有效信号的能量差异悬殊时,造成的影响可能是明显的,这时应该考虑补偿处理.参考文献:[1]　李大心.探地雷达方法与应用[M ].北京:地质出版社,1994. L I Da 2xin.Ground penetrating radar (GPR )methods and applica 2tion[M ].Beijing :G eology Press ,1994.[2]　黄　伟,李大心,唐庆兵.二维滤波在探地雷达图像处理中的应用研究[J ].工程勘察,2002,(4):66-69. HUAN G Wei ,L I Da 2xin ,TAN G Qing 2bing.Application researchof two 2dimension filtering in the GPR figure processing [J ].G eotechnical Investigation &Surveying ,2002,(4):66-69.[3]　李新祥.Radon 变换的计算及其地球物理应用[J ].计算物理,1992,9(4):643-644. L I Xin 2xiang.The computation of radon transform and its applica 2tion in geophysics[J ].Chinese Journal of Computational Physics ,1992,9(4):643-644.(编辑:王东静)3721　第9期吴健生,等:拉东变换在探地雷达资料处理中的应用。

专利名称：推荐系统中基于矩阵分解的并行随机梯度下降算法专利类型：发明专利
发明人：顾宁,龚志霖,李东胜,卢暾,张鹏
申请号：CN201911061727.X
申请日：20191101
公开号：CN111125620A
公开日：
20200508
专利内容由知识产权出版社提供
摘要：本发明属于推荐技术领域，具体为推荐系统中基于矩阵分解的并行随机梯度下降算法。

本发明根据用户历史评分数据对未评分数据进行预测，采用混合交替更新的方式使其在高度并行的情况下依然保持良好的准确性；通过递归地将评分矩阵分成2×2的子矩阵，先并行处理左上角和右下角子矩阵，再并行处理右上角和左下角的子矩阵，避免了训练数据导致的参数向量依赖问题；在更新过程中固定一个参数向量求解另一个参数向量，解除了计算时的参数向量之间的依赖关系，降低了并行造成的精度损失。

本发明通过引入混合交替更新的方式，解决了并行随机梯度下降算法在矩阵分解场景下参数向量更新时依赖的问题，并具有良好的准确性和扩展性。

申请人：复旦大学
地址：200433 上海市杨浦区邯郸路220号
国籍：CN
代理机构：上海正旦专利代理有限公司
更多信息请下载全文后查看。

用于低功耗的体域网加速度数据压缩感知设计吴建宁;徐海东;王珏【期刊名称】《中国生物医学工程学报》【年(卷),期】2015(034)006【摘要】为有效降低体域网加速度数据远程获取系统功耗,提出一种用于低功耗的体域网加速度数据压缩感知处理框架.首先基于优化的稀疏二进制测量矩阵,线性投影压缩体域网传感节点的加速度数据,降低相应节点压缩算法的复杂性和数据传输量;在此基础上,基于块稀疏贝叶斯学习模型,构建非稀疏加速度数据压缩感知重构算法,实现低功耗远程获取加速度数据.实验采用USC-HAD数据库的加速度数据,评估所提方法的有效性.结果表明,当优化稀疏二进制测量矩阵中每列非零元素个数为6、压缩率为50％时,能够获得与传统优化高斯随机矩阵、伯努利随机矩阵相同的压缩重构误差(约0.004 5);与一些传统的压缩感知重构算法相比,所提出的重构算法提高信噪比约17 dB,显著改善重构性能,可有效实现低功耗远程获取加速度数据.该方法有助于传感节点硬件简化设计,改善加速度数据重构性能,为构建低功耗体域网人体活动远程监测系统提供新的思路和方法.【总页数】9页(P677-685)【作者】吴建宁;徐海东;王珏【作者单位】福建师范大学数学与计算机科学学院,福州350007;福建师范大学数学与计算机科学学院,福州350007;西安交通大学生物医学信息工程教育部重点实验室,西安710049【正文语种】中文【中图分类】TN98;TP391【相关文献】1.应用于无线体域网2.4 GHz超低功耗唤醒接收机的设计 [J], 骆丽;吴凤姣2.一种用于MEMS加速度传感器的低功耗低噪声全差分电路 [J], 张航;金湘亮;杨柳3.基于压缩感知的低功耗高效率CMOS图像传感器设计 [J], 赵士彬;姚素英;徐江涛4.面向心电信号的低功耗压缩感知电路设计 [J], 黄翔;潘天文;魏朋博;孙益洲;虞致国;顾晓峰5.一种用于海洋大数据的低功耗数据采集器设计 [J], 陈作聪因版权原因，仅展示原文概要，查看原文内容请购买。

基于精英区域学习的动态差分进化算法彭虎;吴志健;周新宇;邓长寿【摘要】DE算法简单高效,但对复杂问题也存在收敛效率较低的问题,为提高DE 算法的全局勘探能力和收敛精度,提出了一种新的精英区域学习动态差分进化算法,算法首先将历史精英保存在精英池中,然后采用正弦函数对精英池中的精英进行区域学习,最后利用动态DE模式有效提高收敛的速度,并从理论上证明了算法的收敛性.通过对包括单峰函数、多峰函数和偏移函数的20个基准测试函数的仿真实验和分析,验证了新算法的有效性和适用性,其能在保持较高的收敛速度的同时也能保持较好的收敛精度,经与多种知名的DE算法在统计学上的分析比较,证明了该算法是一种具有竞争力的新算法.【期刊名称】《电子学报》【年(卷),期】2014(042)008【总页数】9页(P1522-1530)【关键词】差分进化;精英池;精英区域学习;动态差分进化【作者】彭虎;吴志健;周新宇;邓长寿【作者单位】武汉大学软件工程国家重点实验室,湖北武汉430072;武汉大学计算机学院,湖北武汉430072;武汉大学软件工程国家重点实验室,湖北武汉430072;武汉大学计算机学院,湖北武汉430072;武汉大学软件工程国家重点实验室,湖北武汉430072;武汉大学计算机学院,湖北武汉430072;九江学院信息科学与技术学院,江西九江332005【正文语种】中文【中图分类】TP181 引言差分进化算法(Differential Evolution，DE)简单、高效且容易实现，自Storn[1]提出之后受到广泛关注，并长时间成为进化算法研究中的一个热点.DE已成功应用到如工业设计、工程优化和机器学习等多个领域并取得很好的效果[2].国内外很多学者对DE算法进行了大量的改进[2]，算法的改进可分为三类，一是对差分变异策略进行研究[3]，提出新的变异策略或组合变异策略，其中Wang[4]提出了一种经典的对变异策略和控制参数进行随机组合的CoDE；二是研究DE的差分变异策略和控制参数对问题的适应性，提出了各种自适应算法，Qin[5] 提出一种自适应DE算法SaDE，算法根据历史经验自适应选择成功率较高的变异策略和参数，张晓伟[6]提出了一种免缩放因子F的差分进化算法DEF，此类算法还有JADE[7]，jDE[8]；三是研究高效的区域搜索策略，搞高DE算法的收敛能力，Rahnamayan[9]提出了反向差分进化算法ODE，在评价当前向量的同时也评价其反向向量，Wang[10]对反向问题一般化提出了GODE.针对学习对象的选取问题，近年来基于精英信息的群智能算法陆续被提出，周新宇[11]提出了基于精英的反向粒子群优化算法，Takahama[12]提出了基于可行解精英集的差分进化算法用于求解约束优化问题.他们利用精英所携带的丰富信息，有效提高了算法的收敛速度和精度，但也存在易于陷入局部极值的问题.为进一步拓展向量学习的区域，提高算法的收敛精度和收敛速度，本文提出了一种新的面向精英的区域学习动态差分进化算法(Elite Local Learning Dynamic Differential Evolution,ELDDE)，算法首先采用精英池策略，池中保存有算法的历史最优向量，然后采用精英区域学习策略(Elite Local Learning，ELL)，利用正弦函数对DE算法在迭代过程中产生的历史精英进行学习，学习的区间为从当前向量到其反向向量的整个搜索区域，从而更好的利用整个学习区域的信息，提高算法的收敛精度；接着算法采用了动态DE模式(Dynamic DE,DDE)，在计算出每一个试验向量后立即与当前向量进行比较并对当前向量进行更新，提高算法的收敛速度.实验证明ELDDE算法简单高效、鲁棒性强，不仅对普通的单峰和多峰问题表现出非常强的收敛能力，而且对偏移的优化问题收敛效果也较其它算法要好.2 标准DE作为一种基于随机搜索的群智能算法，DE首先根据预设的种群大小和问题规模随机生成包含N个D维向量Xi=(xi,1,xi,2,…,xi,D)的种群，然后迭代进行DE的三个基本操作：差分变异、交叉和选择，直到达到预设的停止条件，下面分别对标准DE算法[1]的三个基本操作进行介绍.2.1 差分变异差分变异是DE最主要的操作，也是DE差异进化思想的体现，其根据当前向量Xi,G，在种群中随机选择几个向量进行差分操作并产生一个差分向量Vi,G，最常见的差分变异策略有以下五种：(1)DE/rand/1Vi,G=Xi1,G+F·(Xi2,G-Xi3,G)(1)(2)DE/best/1Vi,G=Xbest,G+F·(Xi1,G-Xi2,G)(2)(3)DE/current-to-best/1Vi,G=Xi1,G+F·(Xbest,G-Xi,G)+F·(Xi1,G-Xi2,G)(3)(4)DE/rand/2Vi,G=Xi1,G+F·(Xi2,G-Xi3,G)+F·(Xi4,G-Xi5,G)(4)(5)DE/best/2Vi,G=Xbest,G+F·(Xi1,G-Xi2,G)+F·(Xi3,G-Xi4,G)(5)其中i表示当前向量的下标，G表示第G次迭代，i1，i2，i3，i4，i5分别表示从当前种群中随机选择的5个不同的用于差分操作向量的下标，Xbest,G表示当前种群中的最优向量，F为缩放因子.除了上述常用的五种，还有学者提出的很多不同的差分变异策略，可以参考文献[1,3].2.2 交叉操作交叉操作主要是根据交叉概率CR对当前向量和差分向量进行重组，产生一个试验向量，如公式(6)所示，其中jrand是随机生成的介于1到D之间的整数.如果生成的随机数小于CR或是当前指示器j等于jrand则当前向量的第j维使用差分向量的值，否则用原值.(6)2.3 选择操作当前向量种群所对应的试验向量全部产生后，两个向量群对应位置的向量根据适应度函数值进行优劣比较，获胜的进入下一代向量群进行新的迭代.3 精英区域学习的动态差分进化3.1 精英区域学习策略ELL反向学习策略是近年来兴起了的一个研究热点[9,10]，Rahnamayan[9]将反向学习策略用于DE中并证明了其有效性，其主要方法为评估当前向量的同时也评估向量在搜索空间相反位置的反向向量.Wang[10]进一步分析了反向学习的效果，提出了反向学习一般化处理的方法，如图1所示，反向向量可在当前向量的搜索区域所对应的反向搜索区域[L,U]内取值,用动态搜索边界取代了固定搜索边界，保存了搜索经验，然而如图1所示，反向搜索过程中搜索的只是一个很小的区域，忽略掉了从当前向量X到反向向量X°的全搜索区域[X,X°].如图1所示，如果当前最优向量在几何中心[c,c,…,c]，反向向量不断靠近的同时，全搜索区域中的大部分候选向量也在不断向最优向量靠近，那么将区域搜索的范围由反向搜索区域扩大到从当前向量到反向向量的全搜索区域，将能搜索到更多的更靠近最优向量的可行向量.为此，引入三角函数用于全区域搜索，由于正弦函数sin和余弦函数cos在定义域[-π,π]的值域为[-1,1]，反正弦函数arcsin在定义域[-1,1]的值域为[-π/2,π/2]，sin和cos的取值与全区域搜索吻合，arcsin的取值将搜索区域放大了1.57倍，分析发现它们都适合作为ELL策略的学习函数，算法以sin函数作为首选的学习函数.正弦函数y=sin(α),α∈[-π,π],y∈[-1,1]，它的取值服从均匀分布，在整个区域搜索范围内所有候选解的机会均等.下面给出区域学习变异解的定义.定义1 区域学习变异解，设X为D维空间中的一个可行解，X=(x1,x2,…,xD)，在搜索区域从X到X°，通过三角函数进行变异后，对应的区域学习变异解X*=(x1*,x2*,…,xD*)可定义为：X*=sin(α)·X+r·(U+L),α∈[-π,π](7)其中，r为介于0和1之间的一个随机数，U和L为当前种群搜索区域的上下界. 为了进行区域学习，学习对象的选取是关键，靠近实际最优解的向量能为区域学习提供丰富的信息，而对那些远离实际最优解的向量进行学习可能降低算法的收敛速度，为此我们的学习存在两种方案：方案A，对当前种群中的普通向量进行学习.方案B，对当前种群中的精英即最优解进行学习.方案A的优点是能保持种群的多样性，缺点是对种群中那些偏离最优解的向量的学习将导致收敛精度和速度的下降.方案B的优点是离实际最优解最近，包含的有效信息量大，缺点是当前最优解如果是局部极值，对它的学习将导致种群多样性的丧失，并容易陷入收敛停滞.为了平衡两种方案，提出了精英池的概念，将历史最优解推入精英池中，算法对池中的向量进行学习，通过历史精英来保持学习的多样性，如果当前精英是局部极值，算法也可以通过对其它历史精英的学习来逃离局部极值点.这样既保证了学习的质量和效率，也可避免因对单一向量学习而陷入局部极值.图2给出了针对二维Ackley函数的搜索状态图，其中小圆圈和黑色方框分别表示普通个体和精英个体，图2(a)中给出了向量群的初始状态，图2(b)、(c)、(d)中分别给出了第5、10、15次迭代后的状态，其中包括30个普通个体，5个历史精英.分析可以发现随着搜索进程的推进，普通个体逐渐向最优解靠近，历史精英有效分布于搜索空间中但比普通个体更靠近最优解，在保持了种群多样性的同时能有效引导普通个体向最优解收敛.下面给出精英区域学习变异解的定义.定义2 精英区域学习变异解，设Xe为当前迭代计算的精英解，Xe=(x1e,x2e,…,xDe)，通过三角函数进行变异后，对应的三解函数变异解Xe*=(x1e*,x2e*,…,xDe*)可定义为：Xe*=sin(α)·Xe+r·(U+L),α∈[-π,π](8)3.2 动态DE区域学习过程是对选定的向量进行局部寻优，而寻优时所耗费的迭代次数，必将在一定程度上减缓算法的收敛进程.动态DE可以有效的克服这一问题，加快算法的收敛速度.标准DE算法的一个主要特征是算法在差分变异和交叉操作执行完后会产生一个和原向量群相同规模的试验向量群，原向量群和试验向量群中对应位置的向量通过适应度函数值进行一对一的比较，如果试验向量优于原向量，那么试验向量将在原向量群中取代对应位置的原向量.然而这种方案存在一个延缓收敛速度的问题，当前某个向量，如果优于原向量，但这个新的优质向量不能立即参与到其它向量的演化过程中，必需等到下一次迭代开始才能参与其中.相对于标准DE算法，动态DE模式[13]减去了试验向量群这一中间环节，每个向量根据差分变异和交叉操作产生新的向量后，立即与原向量进行比较.如果新向量优于原向量，则立即取代原向量更新到向量群中.DDE加速了算法的收敛过程，任何新产生的优质向量能立即参与到其它向量的更新过程，不会出现迟滞的现象.ELDDE算法采用这一模式来加速算法的收敛进程.3.3 ELDDE算法算法1描述了ELDDE，它和标准DE的框架基本相似，但主要有3个不同之处，在第(6)步，如果产生的随机数小于学习概率LP，则从精英池中选择一个精英进行区域学习，否则根据DE/rand/1执行标准的差分变异和交叉.在第(12)至(17)步，根据DDE模式，在每一个向量产生试验向量后，立即判断优劣并进行更新.在第(19)至(21)步，对精英池进行更新.算法1 ELDDE算法Input:NP:population size,LP:mutation probability(1)Randomly initialize population P(2)Evaluate the objective function value(3)FEs=NP(4)While FEs < MaxFEs(5) For i=1:NP(6) If rand(0,1)<LP(7) Execute ELL strategy according to Eq.(8)(8) Else(9) Execute the DE strategy DE/rand/1 and crossover according to Eq.(1) and Eq.(6)(10) End if(11) Evaluate the trial vector Ui,G(12) If f(Ui,G)≤f(Xi,G)(13) Xi,G+1=Ui,G(14) If f(Ui,G)≤f(Xbest,G)(15) Xbest,G+1=Ui,G(16) End if(17) End if(18) End for(19) If f(Xbest,G)≤f(Xelite,G)(20) Update the elite pool(21) End if(22)End whileOutput:Global optimum3.4 算法收敛性分析Zaharie[14]对收缩因子F添加了一些限定条件，从而证明了DE算法能以概率1收敛，贺毅朝[15]通过分析DE的差分算子和选择算子，用随机压缩映射原理证明了DE是渐近收敛的.本文在这些收敛性分析的成果上，对ELDDE算法的收敛性进行分析.引理1 设S为解空间，Ψ:Ω×S→S为DE形成的随机压缩算子，则Ψ是具有唯一性的随机不动点，即DE是渐近收敛的.证明：见参考文献[15]，略.根据引理1可知DE算法具有渐近收敛性，ELDDE算法是在DE算法的基础上增加了ELL策略，其试验向量的产生分为两种情况，一是通过DE的差分变异和交叉操作产生的，二是对历史精英进行区域学习产生的，依据DE的渐近收敛性可以证明ELL策略产生的向量也将渐近收敛到一个全局最优解，于是得到ELDDE的渐近收敛性定理如下.定理1 DE算法具有渐近收敛性，则ELDDE算法也具有渐近收敛性.证明：假设DE算法收敛到全局最优解Xgopt，则对于第t次迭代的个体X(t)有：(9)当前种群搜索区域的边界满足：(10)那么对于ELL策略产生的变异解Xe*则有：(11)分析上述推理结果，可知精英区域学习的结果将收敛到(sin(α)+2·r)·Xgopt，那么ELDDE算法中的所有向量不管是差分进化的个体，还是ELL策略产生的个体都是渐近收敛的.所以ELDDE算法也具有渐近收敛性.3.5 算法复杂度分析根据算法1中各步骤分析ELDDE的时间复杂度，其中种群规模为NP，问题维数为D，迭代次数为T.第(1)步种群初始化和第(2)步初始适应度函数评价分别为O(NP·D)，第(7)步ELL学习为O(D)，第(9)步DE差异变异和交叉操作为O(D)，第(11)步适应度函数评价和第(12)至(17)步向量更新为O(D)，则从第(5)到第(18)步的每一次迭代计算为O(NP·D).第(19)至(21)步中如果精英池规模与种群规模同为NP，将当前精英推入池的顶端，其它历史精英后移所需时间复杂度为O(NP·D)，则从第(4)到(22)步总的时间复杂度为O(T·NP·D).综上所述，略去低阶项后ELDDE 算法总的时间复杂度为O(T·NP·D)，仅与NP、D和T相关.ELDDE算法与标准DE 算法的时间复杂度一致，对算法的改进没有增加过多的计算开销.4 仿真实验与分析4.1 测试函数为了验证ELDDE算法的有效性、正确性和适用性，选择了20个标准测试函数进行实验分析.其中f1～ f7为单峰函数[16]，f8～ f13为多峰函数[16]，f14～ f20为偏移函数[17]，各函数如表1所示.ELDDE算法中，参数NP=30，F=0.5，CR=0.5，区域学习概率LP=0.1,其它各参与比较算法的参数与原文献相同，最大函数评价次数FEs=200000，各算法独立运行25次.为了更好的分析ELDDE的收敛速度、收敛强度和收敛精度等性能，将ELL策略构建在标准DE之上形成ELDE，比较分析动态DE模式对算法收敛速度的贡献.将ELL减去精英池策略形成ELDDE-NEP，比较分析精英池策略对提高种群多样性以逃离局部极值的贡献.ELDDE算法与DE[1]，GODE[10]，ELDE，ELDDE-NEP的平均最优值和方差在表2中，为了公正客观的评价ELDDE算法的性能，采用Wilcoxon秩和检验方法对实验结果进行统计分析，显著性水平为0.05，在表的底部，符号“-”，“+”，“≈”分别表示劣于、优于和相当于ELDDE的结果.表3为ELDDE与知名的DE算法CoDE[4]，SADE[5]，JADE[7]，jDE[8]的实验和统计结果.图3描述了各算法的收敛曲线，画图所用数据为各算法独立运行25次的第15次计算结果，受篇幅限制，仅从单峰函数、多峰函数和偏移函数中各选择了2个有代表性的函数.表1 基准测试函数TypeFunctionNamef(X∗)Initial RangeUnimodalFunctionsf1Sphere0[-100,100]f2Schwefel2.220[-10,10]f3Schwefel1.20[-100,100]f4Schwefel2.210[-100,100]f5Rosenbrock0[-30,30]f6Step0[-100,100]f7Quartic with Noise0[-1.28,1.28]MultimodalFunctionsf8Schwefel2.26-12569.5[-500,500]f9Rastrigin0[-5.12,5.12]f10Ackley0[-32,32]f11Griewank0[-600,600]f12Penalized10[-50,50]f13Penalized20[-50,50]ShiftFunctionsf14Shift Sphere0[-100,100]f15ShiftSchwefel1.20[-100,100]f16Shift Schwefel1.2 With noise0[-100,100]f17Shift Griewank0[-600,600]f18Shift Ackley0[-32,32]f19Shift Penalized10[-50,50]f20Shift Penalized20[-50,50]表2 DE，GODE，ELDE，ELDDE-NEP，ELDDE算法的平均值、标准差和Wilcoxon秩和检验结果DE平均值±方差GODE平均值±方差ELDE平均值±方差ELDDE-NEP平均值±方差ELDDE平均值±方差f19.66E-37±2.80E-36-1.16E-39±1.18E-39-0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00f21.57E-20±9.86E-21-5.25E-21±2.59E-21-0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00f31.21E+03±6.17E+02-4.26E+03±1.11E+03-0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00f49.20E-02±3.11E-01-2.66E-02±1.67E-02-0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00f52.21E+01±3.77E-01≈2.32E+01±3.69E-01-2.30E+01±3.66E-01-2.30E+01±2.86E-01-2.23E+01±3.88E-01f60.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E +00±0.00E+00≈0.00E+00±0.00E+00f75.92E-03±1.49E-03-5.94E-03±2.28E-03-1.92E-04±1.25E-04≈6.46E-05±3.69E-05+1.51E-04±1.10E-04f8-5.35E+03±3.80E+02--5.08E+03±3.50E+02--9.56E+03±2.28E+03--1.13E+04±4.09E+02--1.25E+04±9.98E+01f91.54E+02±2.35E+01-1.34E+02±2.08E+01-0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00f106.25E-15±1.52E-15-6.25E-15±1.52E-15-0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00f117.89E-04±2.76E-03≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E+00±0.00E+00≈0.00E +00±0.00E+00f124.15E-03±2.03E-02≈6.54E-21±7.31E-21-1.31E-24±1.17E-24-1.58E-32±2.53E-34≈1.57E-32±5.47E-48f131.35E-32±5.47E-48≈1.42E-20±9.62E-21-3.89E-03±1.91E-02-8.87E-01±8.00E-01-1.35E-32±5.47E-48f140.00E+00±0.00E+00≈1.19E-20±1.31E-20-3.34E-22±3.40E-22-0.00E+00±0.00E+00≈0.00E+00±0.00E+00f151.34E+03±6.27E+02-3.65E+03±1.48E+03-3.04E+00±2.06E+00-2.63E-04±1.96E-04+4.32E-01±3.19E-01f161.58E+03±1.20E+03-4.05E+03±1.93E+03-5.04E+00±3.07E+00-4.54E-01±1.39E+00-4.53E-01±2.86E-01f177.89E-04±2.67E-03≈2.96E-04±1.45E-03-5.92E-04±2.01E-03≈3.16E-03±3.91E-03-0.00E+00±0.00E+00f186.39E-15±1.42E-15-5.59E-11±2.81E-11-1.31E-11±4.35E-12-6.33E+00±2.62E-01-4.97E-15±1.74E-15f191.58E-32±2.58E-34≈6.57E-21±8.15E-21-8.40E-25±7.18E-25-1.58E-32±2.53E-34≈1.57E-32±6.32E-35f201.67E-32±1.55E-32≈5.85E-20±7.52E-20-4.39E-04±2.15E-03-4.25E+00±7.23E+00-1.35E-32±5.47E-48-1118107+0002≈921011表3 CoDE，SaDE，JADE，jDE，ELDDE算法的平均值、标准差和Wilcoxon秩和检验结果CoDE平均值+方差SaDE平均值+方差JADE平均值+方差jDE平均值+方差ELDDE平均值+方差f16.42E-43±1.90E-42-1.79E-96±8.76E-96-5.79E-97±2.83E-96-9.80E-130±3.25E-129-0.00E+00±0.00E+00f24.44E-23±5.44E-23-5.41E-71±1.81E-70-7.89E-53±2.60E-52-9.60E-81±4.25E-80-0.00E+00±0.00E+00f38.15E-10±1.00E-09-4.80E-03±7.22E-03-4.29E-37±1.22E-36-5.12E-07±7.70E-07-0.00E+00±0.00E+00f43.24E-10±2.53E-10-4.77E-02±1.60E-01-2.26E-11±4.80E-11-1.74E+01±5.62E+00-0.00E+00±0.00E+00f55.33E-02±7.97E-02+3.18E+01±2.72E+01≈4.15E+00±1.71E+01+1.50E+00±1.83E+00+2.23E +01±3.88E-01f60.00E+00±0.00E+00≈0.00E+00±0.00E+00≈3.20E-01±8.35E-01-8.00E-02±2.71E-01≈0.00E+00±0.00E+00f74.02E-03±1.52E-03-7.07E-03±3.72E-03-2.44E-03±1.19E-03-3.44E-03±2.12E-03-1.51E-04±1.10E-04f8-1.26E+04±1.82E-12+-1.25E+04±9.48E+01≈-1.22E+04±1.94E+02--1.25E+04±6.77E+01≈-1.25E+04±9.98E+01f93.98E-02±1.95E-01≈9.15E-01±8.40E-01-0.00E+00±0.00E+00≈7.96E-02±2.70E-01≈0.00E+00±0.00E+00f103.55E-15±0.00E+00-9.77E-01±7.96E-01-1.44E-01±3.97E-01-6.11E-15±1.60E-15-0.00E+00±0.00E+00f117.89E-04±2.67E-03≈2.20E-02±1.76E-02-2.27E-03±4.40E-03-1.97E-03±4.06E-03-0.00E+00±0.00E+00f121.57E-32±5.47E-48≈1.38E-01±3.51E-01-4.56E-02±1.41E-01≈8.29E-03±2.81E-02-1.57E-32±5.47E-48f131.35E-32±5.47E-48≈1.28E-01±4.33E-01-4.39E-04±2.15E-03≈4.39E-03±1.94E-02-1.35E-32±5.47E-48f140.00E+00±0.00E+00≈2.96E-32±6.39E-32-0.00E+00±0.00E+00≈2.96E-32±5.92E-32-0.00E+00±0.00E+00f156.72E-10±1.37E-09+2.40E-03±3.74E-03+1.21E-30±6.59E-31+1.74E-07±2.70E-07+4.32E-01±3.19E-01f162.82E-08±4.68E-08+4.12E+01±6.94E+01-1.52E+02±2.89E+02-2.75E+01±1.09E+02≈4.53E-01±2.86E-01f170.00E+00±0.00E+00≈1.18E-02±2.36E-02-5.61E-03±8.65E-03-2.76E-03±4.64E-03-0.00E+00±0.00E+00f185.55E-15±0.00E+00-7.57E-01±7.09E-01-8.35E-02±2.85E-01≈7.25E-15±3.09E-15-4.97E-15±1.74E-15f191.57E-32±5.47E-48≈4.15E-03±2.03E-02≈1.57E-32±5.47E-48≈3.32E-02±1.05E-01-1.57E-32±6.32E-35f201.35E-32±5.47E-48≈1.61E-01±7.08E-01-8.79E-04±2.98E-03≈7.41E-32±2.09E-31-1.35E-32±5.47E-48-7151114+4122≈94744.2 实验结果比较分析对表2和表3分析可发现，ELDDE算法的收敛能力较强，在f1，f2，f3，f4，f6，f9，f10，f11，f14，f17共10个函数上的优势明显，可以很快并稳定的收敛到最优解0.ELDDE算法在收敛精度和收敛能力方面，与各算法相比占有较大优势.在表2中标准DE算法在f3，f8，f9，f15，f16出现了停滞，而ELDDE则在f3，f9收敛到了最优解，f8，f15，f16则接近最优解.对于一般化的反向搜索算法GODE，ELDDE占有全面的优势，且收敛的精度方面除f5，f6，f11之外都大于多个数量级，说明将学习范围从反向区域扩大到全区域的重要意义.相对于在标准DE上增加了ELL策略的ELDE，分析可发现ELDE对于各测试函数具有较强的收敛能力，但在相同的函数评价次数的情况下，它的收敛精度要弱于ELDDE，说明DDE模式提高了收敛的速度.对于在ELDDE上去掉精英池策略的ELDDE-NEP，可发现它的收敛能力也较强，但对于部分函数如f13，f17，f18，f20则存在收敛停滞的现象，说明仅仅对当前精英进行学习对于多峰问题和偏移问题容易陷入了局部极值，这证明了精英池对保持种群多样性方面的贡献，对于历史精英的不断学习有助于算法及时跳出局部极值.ELDDE-NEP在f7和f15上的收敛效果好于ELDDE，因为f7是单峰问题，f15是单峰的偏移问题，ELDDE-NEP对当前精英进行学习是一种贪婪的学习策略，其对此类问题的收敛速度比ELDDE要快.从表3底部的Wilcoxon秩和检验的统计结果可以看出，ELDDE算法相对于近几年出现的在国际上知名的DE算法具有明显的优势，对于单峰函数f1～f7，ELDDE除f5和f7外都收敛到最优解0，但对函数f5ELDDE要弱于CoDE，JADE，jDE.对于多峰函数f8～f13，ELDDE与各算法相当，但ELDDE对于f8，f9，f10收敛到了最优解0.对于偏移函数f14～f20，ELDDE在f14和f17收敛到了最优解，f18，f19，f20都优于或相当于各算法，f15要劣于各算法，f16要劣于CoDE.从图3可以看出ELDDE算法相对于其它算法具有较强的收敛能力，在f1，f2，f9上能快速的收敛到最优解0，在f8，f19，f20上与其它算法的收敛曲线吻合.表4给出了ELDDE和各算法的Friedman检验排名，ELDDE排在第一，从统计学上说明了ELDDE算法的优势.综合以上实验分析可以说明ELDDE算法具有较快的收敛速度、较强的收敛精度和较好的函数适用性，有效提高了对复杂问题的收敛效率.表4 各算法的Friedman检验排名算法SaDEGODEjDEJADECoDEELDDE排名4.904.553.683.602.301.984.3 精英学习的可行性分析表5给出了在区域学习的DDE算法框架下对精英个体和普通个体分别进行学习的实验结果，为了全面的比较两者的性能，分别记录了函数评价次数达到20万次和10万次时的平均值.对表5分析可发现，精英学习的收敛速度和精度要优于普通学习，特别是复杂的偏移问题.对于单峰问题f1～f7和多峰问题f8～f13，精英学习和普通学习的精度基本一致，在f5和f7上稍有差异，在f13上精英学习的效果好于普通学习，但对比函数评价次数达到10万次时的结果，可发现精英学习的收敛速度要更快，能在较少的函数评价次数达到更高的精度.对于带偏移的问题f14～f20，精英学习在收敛速度和精度两方面都要好于普通学习.说明精英池策略在解决复杂问题时，对保持学习对象的多样性方面发挥了重要作用，能让算法及时跳出局部极值，实验结果证明了精英学习以及精英池策略的可行性和有效性.表5 精英学习与普通学习的实验结果FESf1f2f3f4f5f6f7f8f9f102E5精英0.00E+000.00E+000.00E+000.00E+002.23E+010.00E+001.51E-04-1.25E+040.00E+000.00E+00普通0.00E+000.00E+000.00E+000.00E+002.24E+010.00E+007.92E-05-1.25E+040.00E+000.00E+001E5精英0.00E+004.41E-1800.00E+009.94E-1812.47E+010.00E+003.44E-04-1.25E+040.00E+000.00E+00普通1.98E-2353.71E-1224.07E-1741.30E-1022.58E+010.00E+003.32E-04-1.08E+040.00E+000.00E+00FESf11f12f13f14f15f16f17f18f19f202E5精英0.00E+001.57E-321.35E-320.00E+004.32E-014.53E-010.00E+004.97E-151.57E-321.35E-32普通0.00E+001.57E-324.39E-047.89E-331.58E+012.43E+011.78E-035.26E-151.57E-321.35E-321E5精英0.00E+001.57E-321.35E-320.00E+001.28E+011.37E+010.00E+006.25E-151.57E-321.35E-32普通0.00E+001.25E-304.39E-044.38E-282.32E+022.84E+021.78E-032.19E-148.99E-313.00E-284.4 DDE的有效性分析为了测试DDE模式对算法收敛速度的影响，在表7中给出了ELDE和ELDDE达到如表6所示的精度所用的25次独立实验所得的平均迭代次数及加速比.如表2所示，因为ELDDE的收敛精度比ELDE高，表6所用的精度以ELDE能达到的精度为基准进行设定.对表7分析可发现，ELDDE和ELDE对单峰函数的平均迭代次数基本相同，但在多峰函数和偏移函数的加速比较为明显，特别是在f12，f13，f14，f17，f18，f19，f20都超过了四倍，显示了DDE模式在ELL算法框架下提高了对复杂问题求解的收敛速度，证明了DDE在ELDDE算法中的适用性和正确性.表6 函数预设精度函数f1f2f3f4f5f6f7f8f9f10精度00001E+201E-3-1E+400函数f11f12f13f14f15f16f17f18f19f20精度01E-201E-21E-201E+11E+11E-31E-101E-201E-3表7 ELDDE与ELDE达到预设精度的平均迭代次数及加速比f1f2f3f4f5f6f7f8f9f10ELDDE2665.965420.42741.645498.5617.222.681477.92 1024.88131.84286.52ELDE2749.245449.962803.845481.6417.9623.881773.0 42298.76152.68292.68加速比1.031.011.021.001.041.051.202.241.161.02f11f12f13f14f15f16f17f18f19f20E LDDE151.321345.64230.921508.363529.843513.96338.521471.881349.9234 6.12ELDE165.765511.04961.86183.484893.045296.721484.6461315456.441439.8加速比1.104.104.174.101.391.514.394.174.044.165 结论本文提出了一种新的面向精英进行区域学习的动态差分进化算法ELDDE，在ELDDE算法中，DDE模式有效提高了收敛速度，精英池策略有效保持了学习对象的多样性，通过正弦函数对历史精英进行区域学习增强了算法的收敛精度，实验数据和统计分析证明了ELDDE算法较强的收敛能力以及各参数的适用性.后续工作是将ELL策略推广到其它的群智能算法中并用于解决工程优化等实际问题.参考文献【相关文献】[1]Storn R,Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.[2]Das S,Suganthan P N.Differential evolution:A survey of the state-of-the-art[J].IEEE Transactions on Evolutionary Computation,2011,15(1):4-31.[3]Mezura-Montes E,Velázquez-Reyes J,et al.A comparative study of differential evolution variants for global optimization[A].Proc of the 8th Annual Conference on Genetic and Evolutionary Computation[C].Seattle:ACM,2006.485-492.[4]Wang Y,Cai Z,et al.Differential evolution with composite trial vector generation strategies and control parameters[J].IEEE Transactions on EvolutionaryComputation,2011,15(1):55-66.[5]Qin A K,Huang V L,et al.Differential evolution algorithm with strategy adaptation for global numerical optimization[J].IEEE Transactions on EvolutionaryComputation,2009,13(2):398-417.[6]张晓伟,刘三阳.免比例因子F的差分进化算法[J].电子学报,2009,36(6):1318-1323.Zhang Xiao-wei,Liu San-yang.Differentialevolution without the scale factor F[J].Acta Electronica Sinica.2009,36(6):1318-1323.(in Chinese)[7]Zhang J,Sanderson A C.JADE:adaptive differential evolution with optional external archive[J].IEEE Transactions on Evolutionary Computation,2009,13(5):945-958.[8]Brest J,Greiner S,et al.Self-adapting control parameters in differential evolution:Acomparative study on numerical benchmark problems[J].IEEE Transactions on Evolutionary Computation,2006,10(6):646-657.[9]Rahnamayan S,Tizhoosh H R,et al.Opposition-based differential evolution[J].IEEE Transactions on Evolutionary Computation,2008,12(1):64-79.[10]Wang H,Wu Z,et al.Enhanced opposition-based differential evolution for solving high-dimensional continuous optimization problems[J].Soft Computing,2011,15(11):2127-2140.[11]周新宇,吴志健,等.一种精英反向学习的粒子群优化算法[J].电子学报,2013,41(8):1647-1652. Zhou Xin-yu,Ww Zhi-jian.Elite opposition based particle swarm optimization[J].Acta Electronica Sinica.2013,41(8):1318-1323.(in Chinese)[12]Takahama T,Sakai S.Constrained optimization by the ε c onstrained differential evolution with gradient-based mutation and feasible elites[A].Proc of IEEE Congress on Evolutionary Computation[C].Vancouver :IEEE,2006.1-8.[13]Tagawa K.A statistical study of the differential evolution based on continuous generation model[A].Proc of IEEE Congress on EvolutionaryComputation[C].Trondheim:IEEE,2009.2614-2621.[14]Zaharie D.Critical values for the control parameters of differential evolution algorithms[A].Proc of Mendel 2002,8th International Conference on Soft Computing [C].Brno:Faculty of Mechanical Engineering BUT,2002.62-67.[15]贺毅朝,王熙照,等.差分演化的收敛性分析与算法改进[J].软件学报,2010,21(5):875-885.He Yi-chao,Wang Xi-zhao.Convergent analysis and algorithmic improvement of differential evolution[J].Journal of Software,2010,21(5):875-885.(in Chinese)[16]Yao X,Liu Y,et al.Evolutionary programming made faster[J].IEEE Transactions on Evolutionary Computation,1999,3(2):82-102.[17]Wang H,Wu Z,et al.Space transformation search:a new evolutionary technique[A].Proc of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation[C].New York:ACM,2009.537-544.。

基于改进遗传算法的QoS移动网格任务调度张丽;吴楠;曲攀【摘要】移动网格环境具有高度的动态性,任意时刻都可能发生资源的变化,任务调度因此变得复杂,提出了一种面向服务质量(QoS)的移动网格任务调度策略.建立资源和任务模型,定义任务优先级,将任务分成若干子集,子集内调度采用改进遗传算法,选取时延和跨度为QoS指标,编码和遗传操作上体现资源对任务QoS的匹配调度,使最优解尽力满足任务QoS;同一资源上分配的任务,按优先级顺序执行.仿真结果表明,调度算法可以较好地满足用户的QoS,调度跨度也较优.【期刊名称】《河南理工大学学报（自然科学版）》【年(卷),期】2014(033)005【总页数】5页(P635-639)【关键词】移动网格;任务调度;QoS;最优跨度;遗传算法【作者】张丽;吴楠;曲攀【作者单位】河南理工大学计算机科学与技术学院,河南焦作454000;河南理工大学万方科技学院,河南焦作454000;河南理工大学计算机科学与技术学院,河南焦作454000【正文语种】中文【中图分类】TP393移动网格是大规模资源共享网络[1-2]，作为一种整合异构资源的系统，在动态、多制度的虚拟组织中协调各种资源共享，需要有灵活的面向服务质量(Quality ofService，QoS)的资源管理策略和任务调度算法[3].QoS本质是为了提高系统性能，移动网格资源的异构性和任务QoS的多样性，使得资源与任务的匹配变得复杂.所以移动网格服务质量设计实现的目标应该既能够支持移动网格不同类型的应用，同时也兼顾较高的资源利用率；如何寻找最满足任务QoS的资源执行任务，成为移动网格QoS任务调度的难点.已有网格任务调度研究中，经典的Min-Min算法选择最小完成时间的任务和相应资源进行匹配，算法最大缺点是引起资源的负载严重不均衡，影响资源利用率[4]；移动网格独立任务调度算法MGDS-SA算法采用分批调度思想，采用模拟退火算法得到任务分配方案，但没有考虑到移动设备的能量信息[5]；改进PSO算法改进粒子群算法，提出离散编码方式，改进遗传算子和变异算子，但未考虑到用户的QoS；自适应QoS调度算法使用基准测试和曲线拟合估计作业长度，综合作业长度和用户QoS需求制定调度算法，提高了资源的利用率，但不适用于移动网格环境[6].移动网格QoS任务调度问题的实质，是按照一定的策略将任务与最满足任务QoS 需求的资源进行匹配，同时要达到调度系统的目标.在已有资源聚类工作的基础上[7]，提出一种移动网格面向QoS的独立任务调度算法(MQoS-GA算法)，利用资源性能信息，根据任务优先级，采用改进遗传算法完成任务调度，在满足用户QoS约束条件下，优化调度的时间跨度，达到调度目标.1.1 资源及任务模型移动网格资源集合R={R1,R2,…,Rn}，资源Ri的性能属性记为RCAP，RCAP={RSER,RCOM,RLOA,RLOC}，其中，RSER 为资源服务能力，RCOM为资源通信性能，RLOA为资源负载能力，RLOC为资源所处网络位置.RCAP反映了资源可提供的计算能力、存储能力等.移动网格独立任务集合T={T1，T2，…,Tm}，每个任务Ti都有相应的QoS约束Qi.根据移动网格特性，主要考虑时延和跨度，即任务集合T={T1，T2，…,Tm}内任务等待执行时间和完成时间；任务Ti的完成时间上限用Di表示.调度开始时，独立任务集合T={T1，T2，…,Tm}和资源集合R={R1,R2,…,Rn}，根据资源的性能参数[7]和任务信息，估算得到任务的执行时间EXT[extij]m×n，元素extij表示任务Ti在资源Rj上的估计执行时间.1.2 相关定义定义1 任务平均执行时间是任务Ti在j个资源上执行时间的均值定义2 任务等待执行时间WATij：是任务Ti分配到资源Rj上的时延，WATij=任务调度时间+资源查找时间.定义3 任务完成时间ECTij：由任务等待时间和执行时间组成，ECTij=extij+WATij.所有任务的完成时间即为系统跨度.定义4 任务优先级PRi：决定任务调度时的顺序，即式中：α,β∈[0,1]，且α+β=1；extij为任务Ti在资源rj上的估计执行时间；表示执行时间方差，反映任务在不同资源上执行时间的差异性[5].1.3 问题描述根据任务的优先级，独立任务集合T降序分为若干子集，依序调度每个子集.调度结果既表示任务在资源上的分配情况，又表示在该资源上任务的执行顺序.假设资源集合R={R1,R2,…,Rn}，任务之间是独立的，任务集合T={T1，T2，…,Tm}，按优先级降序分为k个子集V1，V2，…,Vk,k 值的选取不是随意的，如果取太小，则子集调度周期较长，对资源的动态适应性不够灵敏；但如果过大，至少要保证每个调度周期内所有资源被利用，不能有空闲.假设m个任务已按照优先级由高到低的顺序排序，为PR(v1)≥PR(v1)≥…PR(vn)，划分得到任务子集V1，V2，…,Vk；前k-1个子集内的任务数量为[m/k]，最后一个子集的任务数量是m-[m/k](k-1)，则有[m/k]≥n，即子集数量大于资源数量，保证每次调度时至少每个资源上都分配任务.从第一个任务开始执行，到最后一个任务完成结束时间为系统跨度.设调度跨度为Mi，子集 Vi调度开始时刻为t(vi)，资源Rj完成所有任务的时间为tij，调度问题可描述为式(2)表示任务调度的目标是跨度最小；式(3)表示任务子集之间的关系；式(4)表示任务子集的执行顺序.子集划分之后，即根据特定的算法s调度各个子集，假设子集调度资源集合R={R1,R2,…,Rnj}，任务集合T={T1，T2，…,Tmj}，子集调度跨度为Mi(s)，任务Ti在资源Rj上开始执行时间为t(vjp)，子集调度问题描述为式中:s和S为子集调度方案和子集调度空间，式(5)为子集的调度目标是跨度最优；式(6)为任务的完成时间要小于等于任务截止期限的上限，体现任务QoS对任务完成时间的约束；式(7)为任务在同一资源上执行的优先级关系.格任务调度算法MQoS-GA移动网格任务调度是为了实现任务与资源的匹配，且使资源与任务的匹配满足用户对任务的QoS要求，使用较少的资源获得较高的收益，所以从本质上说移动网格计算任务调度算法是一个优化算法，属于NP完全问题[8].根据已有工作[7]，首先将移出网格区域的节点和能量低于全部能量30%的节点舍弃；然后依据网格资源的性能属性RCAP的服务能力、通信性能、负载能力和网络位置4个参数，选用算术平均最小法[9]定义资源相似性，资源X1和X2之间相似度公式为X12=；选取适当的截集水平，对移动网格资源进行聚类分簇，使得同一簇中的资源相似度高，簇间资源相似度低.算法假设资源短期内是静态的，即在遗传操作进行中不会出现资源的故障；任务之间相互独立，没有依赖性；执行算法时，将任务分配到资源后，对每个资源上的任务按照优先级顺序执行.在第k次调度期间，若有新的任务请求，则进入下一个任务子集，等待调度；如果有新的资源加入，则将资源与可用资源进行相似度分析，分配到相应簇中.如果有任务断开连接，则其分配的资源执行下一个任务；若有资源离开系统，则该资源上的正在执行的任务取消执行，进入下一个任务子集等待调度.2.1 染色体编码和初始种群遗传算法的基因包括基因座locus和等位基因allele.本文采用任务与资源相对应的间接编码方式，每个基因位置的编号代表任务Ti，基因位的数值代表任务占用资源编号Ri.本文对染色体编码采用浮点编码.首先根据任务优先级，染色体编码顺序按照任务的优先级降序排列；其次根据资源聚类结果得出资源综合性能，对优先级高的任务与综合性能最好的资源匹配，资源匹配串的长度即子任务的个数.mati表示染色体，代表任务与资源的合理匹配；定义染色体合法性的充分必要条件是：染色体编码上与任务匹配的资源必须要能够满足任务的最低QoS需求，所有集合Mat={mat1,mat2,…,mati}即为染色体种群.2.2 适应度函数为避免同一染色体被多次选择，影响种群多样性，采用双适应度函数约束种群的进化.个体适应度函数定义为个体浓度pd定义为式中：d=群体中相同个数体数目q/群体总数p，由此得到个体被选中的概率pf=fi/(pd×p).要使系统跨度最优，不仅要使单个任务完成时间最小，而且同时也要关注任务平均完成时间，避免因小任务完成而大任务耗费时间引起跨度增大，因此个体适应度用任务平均执行时间的倒数表示.适应度越大，被选择概率越大；个体浓度表示某个染色体在遗传进化中被选择的概率，个体浓度越大，被选择的可能性越小，对算法收敛起到抑制作用，避免了过早收敛.2.3 遗传操作——交叉、变异和选择(1)选择.本文采用两两对比的选择方法，即每次从种群中随机选取两个个体加以比较，适应度值大的个体被选出，若两个个体的适应值一样，则随机选取其中一个.(2)交叉.为了尽量保证染色体合法性，本文对任务串和资源串分别采取交叉算子：对两个子任务串随机选取一个分割点分成两部分，两个串的分割点是一样的，将后面的任务重新进行排列，目的是保证染色体的合法性.对资源串也随机选取一个分割点，分成两部分，将后面部分的资源重新排列.(3)变异.为保证任务调度的有效性，本文中变异基因不是随机选择的，而是选择能使该任务执行时间最短的资源，同时要满足任务的最小QoS要求，然后再将任务迁移过去，防止因某个任务迁移后，执行时间增加而造成的种群退化，也保证了变异后的新个体中，资源满足 .为了保证交叉产生个体的有效性，即资源能否保证任务QoS，需要采用作业状态检测算法Job-Check恢复调度方案的有效性[3].具体检测如下.输入：交叉后产生的新种群Mat.输出：有效新个体.扫描新个体，对每一任务被分配的次数While mati∈Mat if ni>1 then保留染色体适应度函数最高的，作为对Ti的调度，删除其余调度else if ni=0 then选择综合性能最好的资源Rjif 作业Ti分配到Rj可以满足其最小QoS需求then将Ti分配到Rj的作业队列中else 将Ti与Rj编码继续进行下一轮遗传操作End ifEnd ifEnd while如此之后，得到新一代染色体，根据初始种群N对染色体通过交叉、变异产生新的N个个体，将两代染色体组成2N的临时种群，适应度靠前的N个个体，认为是较为优良的个体，将其保存起来，计算终止条件，作为最优解，或者进行下一轮遗传操作.3.1 遗传算法的收敛性分析遗传算法的收敛性通常是指遗传算法所生成的迭代种群收敛到某一稳定状态，或其适应度值函数的最大值随迭代趋于优化问题的最优值.令p(t)为遗传算法在第t代的群体，Ft=f(Pt)为第t代群体的适应度值，F*为最优解集f(Pn)对应的最大适应度值函数，那么，|F*|是有限的，且第n代以后的群体适应度值都会达到最大适应度值F*.定理1 若对于任务集T中每个任务，资源集R存在一个在所有QoS属性上都是最优的资源，那么T必存在最优解.证明对T中每个任务Ti，若存在一个在所有QoS属性上都最优的资源Ri，此时假设资源Ri与任务Ti编码的染色体适应度值为F*，那么，F*一定是遗传算法的最优解.若F*不是最优解，那么此时应该有适应度值为F*的染色体为最优解，那么F*染色体的资源在某一QoS属性上要优于F*染色体上的资源，这与条件矛盾.因此，任务集T一定存在最优解.定理2 遗传算法的运行过程是一齐次有限Markov链，且具有全局收敛性.证明由算法的迭进化过程可以看出，t+1时刻的种群P(t+1)只与t时刻的种群P(t)有关，而与种群P(1)，P(2)，…，P(t-1)无关，即遗传算法的运行过程满足Markov性.由算法的整个进化过程可以看出，交叉算子和变异算子不随时间发生变化，即遗传算法满足时间齐次性.同时，遗传算法的种群集合是有限的，因此，遗传算法的运行过程是一齐次有限Markov链.由于遗传算法每一个种群集合Pi都是齐次有限Markov链的一个状态，且以概率1收敛，遗传算法的时间复杂度与资源规模n、任务个数m和迭代次数t有关，所以算法的时间复杂度为o(nmt).3.2 仿真实验与对比选用网格仿真工具Gridsim对所提出算法进行仿真，与经典的Min-min算法作对比，主要考察调度跨度Makespan和任务等待执行时间，独立任务数量100～600，资源数100.如图1所示，随着任务数量的增加，MQoS-GA的时间跨度的增加远低于Min-min，这是由于MQoS-GA算法根据任务的优先级综合考虑资源性能和任务大小，使任务调度分配更合理，从而使得系统的时间跨度较优.MQoS-GA划分任务子集进行调度，调度期间若发生资源的移动性，任务可以进入下一个子集等待调度或者执行下一个任务，因此对整体的任务调度影响较小.Min-Min算法主要针对固定资源，在移动网格动态环境下运行Min-Min算法时，首先运行Min-Min算法得到调度结果，在任务运行过程中，如果一个资源发生变化(加入或退出)，则对所有未完成任务重新运行Min-Min算法，当有多个资源动态发生变化时，则需要多次运行该算法.Min-Min算法后期可能会出现大任务的执行引起调度跨度时间长，图2所示为任务调度算法分配任务的执行时间，可以看出，虽然由于资源性能的预处理和遗传算子的生成占用了一定的时间，但是MQoS-GA算法的执行时间增加的并不大，较好地达到了目标.图3表示不同截止期限下资源利用率的比较.最低期限增加对资源利用率的影响显而易见，因为截止期限越大，就会有越多的资源可以在截止期限前完成任务，越大的截止期限带来越高的资源利用率.当截止期限D=400，MQoS-GA的资源利用率比Min-Min提高了19%，当截至期限一样时，MQoS-GA的资源利用率比Min-Min略高一些.可见在固定的截止期限下，MQoS-GA的用户可以根据用户其他的QoS需求来提高系统的效用性，从而提高了资源的利用率.本文针对移动网格资源数量庞大、异构性、高度动态性等特点，给面向QoS任务调度带来的不便，提出基于改进遗传算法的移动网格QoS任务调度策略.在已有研究对资源模糊聚类的分簇基础上，定义任务的优先级，在任务QoS约束下，对调度问题形式化描述，以最小跨度为调度目标，以任务完成时间限制和优先级为约束条件，采用改进遗传算法，遗传算子的选取以QoS约束为条件.仿真结果表明，算法在满足用户的QoS的条件下使系统整体时间跨度优化，因此在使用户的效益得到最大化满足方面有进一步发展的空间，能使移动网格资源得到更加充分合理的利用.E-mail：*******************【相关文献】[1] 杜丽娟,鞠宏军.移动网格环境下可靠任务调度研究[J].计算机工程与应用,2012,48(20):142-145.[2] TOMAS, LUIS, OSTBERG, et al. An adaptable in-advance and fairshare meta-scheduling architecture to improve grid qos[C]// Proceedings 2011 12th IEEE/ACM International Conference on Grid Computing, Grid.[s.n.],2011: 220-221.[3] 蒲汛,何为,卢显良.基于改进遗传算法的多QoS约束网格任务调度[J].电子科技大学学报,2010.39(4):54-60.[4] FREUND R F. CHEERILY M, ALMBRUSIUS S, et al. Scheduling resources in multi-user, heterogeneous, computing environment with SmarNet[C]//Pruc the 7th IEEEHeterugeneous Computing Workshop(HCW'98). Florida, USA：[s.n.],1998:184-199.[5] 杜丽娟,余镇危.基于Overlay Network的移动网格及其关键技术研究[D].北京：中国矿业大学，2012.[6] ANG,TAN FONG, LING. Teck Chaw.Adaptive QoS scheduling in a service-oriented grid environment[J].Turkish Journal of Electrical Engineering and Computer Sciences,2012.20(3): 413-424.[7] ZHANG LI, QU PAN. Mobile Grid Resources Clustering Algorithm Based on Fuzzy Theory[C]// 2012 International Conference on Electrical Information and Mechatronics.[s.n.],2012.[8] FANGPENG DONG, SELIM G AKL. Scheduling algorithms for grid computing: state of the art and open problems[D].Kingston:Queen S University,2006.[9] 秦涛,刘朝斌.基于最早完成时间的网格任务调度算法[D].大连：大连海事大学，2010.。

第22卷第6期强激光与粒子束Vo l.22,No.6 2010年6月H IGH POWER LASER AND PART ICLE BEAM S Jun.,2010 文章编号: 1001-4322(2010)06-1206-05自适应光学系统随机并行梯度下降算法*马慧敏, 张鹏飞, 张京会, 范承玉, 王英俭(中国科学院安徽光学精密机械研究所大气成分与光学重点实验室,合肥230031) 摘 要: 随机并行梯度下降(SPG D)算法可以对系统性能指标直接优化来校正畸变波前。

对基于SPG D算法的61单元自适应光学系统进行仿真模拟,分析了对不同初始静态畸变波前的校正能力,并比较了不同性能指标情况下的算法增益系数、扰动幅度值的选取及校正情况。

仿真结果表明:算法收敛速度很大程度上依赖于增益系数和扰动幅度值,对畸变较大的波前,随机扰动幅度在0.50~0.85范围内,性能指标采用焦斑平均半径比采用斯特列尔比取得的校正效果好。

关键词: 自适应光学; 随机并行梯度下降算法; 数值仿真; 波前畸变中图分类号: T P273.2 文献标志码: A doi:10.3788/H PL P B20102206.1206传统的自适应光学系统是利用波前传感器探测畸变波前信息,再控制波前校正器补偿像差。

随着该技术的发展以及应用领域的扩展,传统的自适应光学系统由于波前探测困难而表现出一定的局限性。

近几年来,利用优化算法直接优化系统性能指标的无波前自适应光学控制技术,越来越受到自适应光学领域的重视。

1997年,M. A.Vo rontsov 等人[1-2]基于SPSA 算法和随机逼近理论提出了SPGD 算法,此后SPGD 算法经过多次改进和完善,针对不同单元数、不同校正器类型、高分辨力波前校正等方面也进行了数值模拟和实验研究,验证了随机并行梯度下降算法对波前畸变的校正能力。

国内对基于该算法的自适应光学技术的研究目前处于起步阶段,中国科学院成都光电研究所的杨慧珍[3-4]、国防科学技术大学的靳冬欢[5]分别对以32单元和37单元变形镜作为校正器的基于SPGD 算法的自适应光学系统做了部分研究。

基于Zernike模式的自适应光学系统随机并行梯度下降算法杨慧珍;李新阳
【期刊名称】《强激光与粒子束》
【年(卷),期】2009(21)5
【摘要】控制算法的收敛速度一定程度上限制了无波前探测自适应光学技术在实时波前畸变校正中的应用.从理论分析角度提出将模式法和区域法结合起来以提高算法收敛速度,并以61单元变形镜为校正器,建立基于随机并行梯度下降算法自适应光学系统仿真模型.结果表明:达到同样的校正效果时,采用组合优化的算法收敛速度要明显优于基于区域法的收敛速度,从而验证了理论分析的合理性.
【总页数】4页(P645-648)
【作者】杨慧珍;李新阳
【作者单位】淮海工学院,控制工程技术研究所,江苏,连云港,222005;中国科学院,自适应光学重点实验室,成都,610209
【正文语种】中文
【中图分类】TP273.2
【相关文献】
1.基于随机并行梯度下降算法的光束相干合成技术 [J], 潘旭东;贺喜;雍松林;张生帅;田俊林
2.自适应光学系统随机并行梯度下降算法 [J], 马慧敏;张鹏飞;张京会;范承玉;王英俭
3.基于随机并行梯度下降算法的InSAR相位解缠方法 [J], 杨新锋;宋长斌;刘克成
4.随机并行梯度下降算法性能与变形镜排布规律的关系研究 [J], 陈惠颖;王卫兵;王挺峰;郭劲
5.基于Zernike模式的随机并行梯度下降算法的收敛速率 [J], 王卫兵;赵帅;郭劲;王挺峰
因版权原因，仅展示原文概要，查看原文内容请购买。

基于Keystone-FRFT的机动弱目标检测算法郭云飞;周森山;赵尚宇【摘要】针对机动弱目标检测中出现的距离走动和多普勒频率走动问题，在分析回波信号走动的基础上，提出一种基于楔形变换和分数阶傅里叶变换的弱目标检测算法。

算法使用楔形变换补偿距离走动，利用分数阶傅里叶变换补偿多普勒频率走动，在低信噪比情况下能有效地检测机动弱目标。

仿真分析表明算法有效。

%For the problem of range migration and Doppler frequency migration in maneuvering weak target detection, on the basis of echo signal analysis , a maneuvering weak target detection algorithm based on Keystone transform and fractional Fourier transform ( FRFT) is proposed.In this method, Keystone transform is used to correct the range migration , and FRFT is used for phase compensation .It is ideal for maneuvering target detection under low signal to noise ratio(SNR) condition, simulation results demonstrate the validity of this method .【期刊名称】《杭州电子科技大学学报》【年(卷),期】2015(000)001【总页数】4页(P97-100)【关键词】距离走动;多普勒频率走动;楔形变换;分数阶傅里叶变换【作者】郭云飞;周森山;赵尚宇【作者单位】杭州电子科技大学自动化学院，浙江杭州310018;杭州电子科技大学自动化学院，浙江杭州310018;杭州电子科技大学自动化学院，浙江杭州310018【正文语种】中文【中图分类】TN957.51微弱目标信号检测中，常采用相参积累的方法加大回波信号能量，提高雷达对微弱目标的检测能力。