基于贪婪更新和自适应扰动的自然计算策略.pdf

，信息通信基于贪婪更新和自适应扰动的自然计算策略胡建暄，马宁，黄鑫宇（哈尔滨师范大学计算机科学与信息工程学院，黑龙江哈尔滨15 0 0 2 5）摘要：自然计算因其参数少好实现等优点而被广泛应用，但是这些算法存在着寻优精度较低和易陷入局部最优解的问题，为更有效的提高算法性能,提出一种基于贪婪更新和自适应扰动的自然计算策略(Greedy-renewaland Self-adaptionDisturb,简称GSD),该方法具备普适性，适用于所有启发式寻优算法。首先使用Faure序列化初始化种群,提高初始解的质量,其次在个体位置更新后，比对更新前后个体的适应度值，如果适应度提高则保留此次更新操作,反之放弃此次更新,最后设计自适应扰动因子，随迭代次数增加调整对个体的扰动几率，提高算法后期的种群多样性。将该策略应用于粒子群算法和遗传算法中，利用经典测试函数验证性能。实验结果表明，贪婪更新和自适应扰动策略改进的算法较其他对比算法表现出了更好的寻优能力，具有普适性。关键词：自然计算；贪婪更新；自适应扰动中图分类号：TP301文献标识码：AA natural computing strategy based on greedy renewal and adaptive disturbanceHU Jianxaun,MA Ning,HUANG Xinyu(Harbin Normal University School of Computer Science and Information Engineering,Heilongjiang Harbin 150025,China)Abstract:Natural computing is widely used because of its advantages such as few parameters and easy implementation,but these algo-rithms have problems of low optimization accuracy and easy to fall into the local optimal solution.In order to improve the algorithm per-formance more effectively,This paper proposes a natural computing strategy based on Greedy renewal and Self-adaption Disturb(GSD),which is universal and suitable for all heuristic optimization algorithms.Firstly,Faure serialization was used to initialize the population toimprove the quality of the initial solution.Secondly,after the update of the individual position,the fitness values of the individuals beforeand after the update were compared.If the fitness was improved,the update operation would be retained;otherwise,the update would beabandoned.Improve the population diversity of the late algorithm.This strategy is applied to particle swarm optimization and genetic al-gorithm,and the performance is verified by classical test function.The experimental results show that the greedy update algorithm and theadaptive perturbation algorithm have better optimization ability than other comparison algorithms and have universality.Key words:Natural computation,Greedy renewal,Adaptive disturbance1引言自然计算（natural computation）是指研究自然界中蕴藏的收稿日期：2 0 2 3-0 2-0 3基金项目：黑龙江省自然科学基金项目（LH2021F037)；黑龙江省高等教育教学改革项目（SJGY20200368；哈尔滨市科技局科技创新人才研究专项项目（2 0 17 RAQXJ050）；哈尔滨师范大学博士科研启动基金项目(XKB201901)；哈尔滨师范大学计算机学院科研项目（JKYKYY202006)；哈尔滨师范大学研究生培养质量提升工程项目（HSDYJSJG2019006）。作者简介：胡建喧（1995-），男，黑龙江鹤岗人，研究生，硕士，主要研究方向为：自然计算；马宁（198 1-），男，黑龙江哈尔滨人，博士，副教授，主要研究方向为：自然计算；黄鑫宇（2 0 0 0-)，女，黑龙江七台河人，研究生，主要研究方向为：自然计算。+.+表1实验数据本文滤波算法误差统计参考文献：滤波后数据滤波结果参考数据地面点数非地面点数地面点数45325非地面点数3962滤波后结果49287表2 实验数据渐进三角网滤波算法误差统计滤波后数据滤波结果参考数据地面点数非地面点数参考点数误差类型误差率地面点数44596非地面点数5212滤波后结果498083结语文章根据机载Lidar点云数据的特点，对渐进三角网滤波算法提出了改进，提高了提取地面点云的准确率，很大程度上提高了滤波算法的精度，改善了滤波后的效果，为下一步针对地面点云提取特定点云打下了坚实的基础。2023年第0 5 期(总第 2 45 期)文章编号：2 0 96-97 5 9(2 0 2 3)0 5-0 0 90-0 4计算能力以及受到自然界启发而出现的计算方法的研究领域，主要涵盖以下三个方面：自然启发的计算、自然仿真或模拟、利1张小红.机载激光扫描测高数据滤波及地物提取 D.武汉：一参考点数误差类型误差率236047685第I类误差4.95%100403104365第I类误差3.80%102763152050308947685第I类误差6.48%99153104365第I类误差4.99%102242152050武汉大学,2 0 0 2.2 甘桂琴.机载LiDAR点云数据滤波方法研究 D.中南大学,2 0 12.3 Zhang Yibin,Sui Lichun,Qu Jia,et al.Filtering of Airborne总误差4.16%总误差5.46%LiDAR Data Based on Mathematical Morphology FilteringAlgorithmJ.Bulletin of Surveying and Mapping.4 Vosselman G.Slope based filtering of laser altimetry dataJ.International Achives of Photogrammetry and RemoteSensing,2000,33(B3):935-942.5苏伟,孙中平,赵冬玲，等.多级移动曲面拟合LIDAR数据滤波算法 J.遥感学报,2 0 0 9,13(0 5):8 2 7-8 39.6 AXELSSON P.DEM Generation from Laser Scanner DataUsing Adaptive TIN ModelsC/Proceeding of InternationalArchives of the Photogrammetry,Remote Sensing and SpatialInformation Sciences.Amsterdam:s.n.,2000:110-117.7隋立春,张熠斌,张硕,等.基于渐进三角网的机载LiDAR点云数据滤波 J.武汉大学学报(信息科学版),2 0 11,36(10):115 9-116 3.90Changjiang Information&Communications用自然物质计算。在模拟自然界自然现象而产生的方法中，常见的主要分为粒子群算法（ParticleSwarmOptimization，简称PSO)和遗传算法（Genetic Algorithm，简称GA)两类，这两类算法通过仿真个体种群的自然特性，采用不同的变换规则对解空间进行探索以求得最优解。基于PSO又产生了模拟动物种群的优化算法，如蜻蜓算法，鲸鱼算法等。诸多研究团队在自然算法优化中投入了很多心力并做出了很多出色的贡献，目前有大量的优化算法被用于塑料工艺,材料切割，软件测试，图像分割 5 等方面。这些优化算法具备着参数少好实现等优点，但是都存在收敛精度不足以及容易陷入局部最优解的问题。为提高自然计算的寻优性能，国内外学者都对不同算法进行了研究改进。Sun等人以概率混合改进鲸鱼算法和综合交错算法，提高鲸鱼算法的全局寻优能力,Liu等人 7 提出了种群再分配和收敛自适应加权策略，根据概率将当前个体替换为最优个体，有效加快算法收敛速度。Xia等人8 使用动态变换概率和种群重构机制改进了蝴蝶算法，通过淘汰适应度较差个体的方式增强了全局寻优能力。Wang等人 提出了自适应惯性权重、动态螺旋搜索和广义对立学习5 种策略对鲸鱼算法进行改进，对个体从初始化到位置更新操作都做了相应调整，提高了收敛速度和精度。Sun等人 o在鲸鱼算法中引入了二次插值概念，即在n维空间中中找三个代理获得曲线最小值点替换当前个体，按比例对个体更换，增强了每次迭代解的质量。Deepika等人 提出用差分进化方法改进灰狼算法，有效平衡头狼和狼群的关系。上述算法在改造对应算法时表现出了优异的性能，但是都针对某一种算法,对算法的公式进行修改，耦合性较强，因此本文提出一种基于贪婪更新和自适应扰动的自然计算策略（Greedy renewal and Self-adaptionDis-turb，G SD)，不依赖与原算法更新方式，以切片的方式融合进算法，提高算法收敛性能。通过多个单峰多峰的测试函数验证，表明该算法在提升算法收敛性能上表现优秀，且可融合进不同算法中，具备普适性。2 GSD策略描述2.1Faure序列初始化在各类依靠种群对解空间进行搜索的自然计算算法中，初始解的质量能很大程度上影响算法的迭代寻优性能，一个较好的初始解可以大大加快算法前期收敛速度，而初始解的质量主要与种群初始个体位置的数量和分布情况有关，初始个体分布越均匀则称其质量越好。100806040200-20-40-6080100-100-80-6040-20。20406080100图1Faure初始化种群与随机初始化种群分布对比图一般启发式自然计算算法中，初始解的点是通过伪随机方式生成，在迭代过程中会浪费一些迭代次数对解空间进行91胡建暄等：基于贪婪更新和自适应扰动的自然计算策略探索，从而影响了算法收敛速度。为了使初始个体在解空间中分布的更均匀和规律，本文通过Faure序列对个体初始解点进行完善优化，从而达到提高初始解的目的。Faure序列是混沌序列的一种，是一种随机性更强的序列,核心思想是以不小于维度m的最小素数b为基，对解空间进行切分处理，从而使初始个体能不重复且均匀的分布在解空间中。图1中将使用Faure初始化的种群标记为蓝色点，将原生初始化种群标记为红色点，从图中可以看到深色点在空间分布中更加均匀，分布更广，对解空间的覆盖更全面，因此初始解的质量更高。2.2贪更新目前对算法迭代结果的评价方式通常是在当前迭代完成后使用适应度函数评价比较的方式，即在全维度的个体值都更新后，整组解带入函数求取适应度值，这种方式简单易实现，但存在着忽略更优解的可能性。在个体随机更新时，可能存在某个维度上探索到更优解，但是在全维度评价时优秀解被去差异化，个体进化被忽视，导致浪费了迭代次数，收敛速度变慢。贪婪算法在个体的角度对算法寻优能力进行提升，即考虑当前解更优秀的可能性，在每次个体更新后，都立即对解进行评价，如果更好则保留，反之放弃。因此本文采用贪婪算法策略对个体进行更新，能够有效发掘迭代过程中优秀解的信息，保留个体精英解。该策略的流程如下，在对个体值进行原算法的更新操作之后，立即与其他维度解组成一组新解，将该新解带入目标函数中求得评价，如果该新解有更好的评价值则保留该解，继续迭代过程，反之采用原解代替此次更新，并继续进行下一个个体迭代操作。持续这种对全维度的个体值贪保留操作，直至迭代完成。采用贪婪更新策略，使得在同一次迭代过程中，不同维度的精英个体得以保留，充分挖掘每次迭代的寻优能力，节约因算法导致个体随机跳动导致浪费的迭代次数，降低了多维度间相互干扰的概率，大幅提高算法局部寻优的能力。2.3自适应扰动在算法迭代过程中可能存在局部最优点及其范围占据解空间较大的可能，此时因为个体移动步长较短，不易跳出局部最优解范围，尤其在算法迭代后期，种群个体值都围绕在局部最优解附近，个体很难跳出局部最优解范围。为增加后期种群多样性，提高种群跳出局部最优能力，避免算法早熟，同时为了平衡算法前后期全局寻优和局部寻优能力，使扰动力度呈现出前期小后期大的状态，提出一种自适应扰动策略，该策略根据选代数的变化，计算扰动因子对算法个体值进行随机偏移，扰动具体公式如下：5=S max*cos(Max_iter-iter)/Max_iter)*)：(1)X,=X,+5*X,(2)：式中：是非线性自适应扰动因子，max是最大扰动因子，Max_iter是最大选代次数，iter为当前代次数，X是当前个体值，X是扰动后的个体值。该式为凹函数，随选代次数非线性减小。前期扰动力度大，提高全局寻优性能，迭代次数越大扰动力度越小，但仍保持一定扰动力度，可以较好的平衡算法前后期的寻优能力。3实验结果与分析本文实验将GSD策略应用于标准粒子群算法和遗传算法中，通过结合得到GSDPSO和GSDGA，通过一些标准测试Changjiang Information&Communications函数对改进算法进行测试，验证算法的寻优性能。表一中给出了这些函数的表达式，搜索空间，维度，理论极值和峰值数。其中F1-F4为单峰函数，只有唯一最优点，能够有效的测试算法的局部开发能力，F5-F6是多峰函数，含有多个局部最优解，在迭代过程中很容易陷入局部最优解中，因此是验证算法跳出局部最优解的有效手段。3.1参数设置为保证算法结果公平性，将算法的初始参数设置如下：粒子群类算法的学习因子c1=c2=2,惯性权重由0.9至0.4线性函数名称SphereSchwefel2.22Schwefel 1.2Schwefel 2.21GeneralizedRastriginGeneralizedGriewank胡建喧等：基于贪婪更新和自适应扰动的自然计算策略递减；遗传算法类算法变异因子mutation_rate=0.1，父母个体数 parent_number为10。上述算法的种群规模 N=100,维度D为10 0 维，最大迭代次数MaxIter-1000。3.2实验结果与分析将标准基础算法与结合了GSD的改进算法在维度d=50时对测试函数F1-F6执行了10 0 次，将平均适应度值和方差记录在表2 中，加粗部分标注除了更接近最优解的实验结果，收敛精度图如图2 所示，横坐标为迭代次数，纵坐标标识适应度收敛精度（以十为底的对数）。表1测试函数参数设置表达式difi(x)-Zxdimdimf2(x)-Zx:/+I1Ix:li-1dimfs(x)=一f4(x)=maxi/x,l1i30)30fs(x)=Zx?-10cos(2;+10)1130fo(x)4000i1搜索空间-100,100-10,10i=1230cosX维度理论极值峰值1000010000100,1001000-100,1001000-5.12,5.12 1000600,6001000i1单峰单峰0单峰0单峰0多峰0多峰表2 PSO,GA及改进算法的实验对比结果平均结果与标准方差函数PSO均值3.624e+1F1方差均值F2方差均值F3方差均值F4方差均值F5方差均值F6方差0-5-101520-25-30-35-40GSDPSO9.512e-273.624e+14.961e-288.892e+24.624e-134.624e+29.226e-1414.5268.629e-47.2314.831e-42.4839.599e-91.8994.783e-95.750e+12.597e-21.523e+14.803e-3241.23072.351010-10-20100200300400500 600选代次数GA2.662e+24.292e+24.572e+12.903e+16.267e+28.211e+19.4927.3621.512e+25.41e+1224.55112.6220-60700100200 300800 9001000GSDGA00005.251E-739.512e-74000000500 600700 80090010000400选代次数-800100200 3004005006007008009001000收做精度92Changjiang Information&Communications胡建喧等：基于贪婪更新和自适应扰动的自然计算策略00-5-1020-400100200300400500600D7008009001000选代次数一PSO GSDPSO GA GSDGA图2 PSO,GA及其改进算法的收敛图从图2 中可以看到GSD算法能有效提高了算法的收敛性能，不仅在单峰函数中表现出了大幅提高收敛精度的能力，同时在多峰函数中表现出了优秀的跳出局部最优的能力，并在迭代后期，收敛精度仍未归于平缓，表示仍具备进一步提高收敛精度的能力。对于PSO算法而言，由进化曲线可知，结合了GSD策略后,因为此时自适应扰动策略的作用，前中期存在一个较大的偏移概率和偏移概率，所以能有效提高全局寻优能力，在收敛精度的表现为收敛精度得到提升，同时因为贪婪算法的作用，有效保证了算法的迭代有效性，更充分的利用了更新值，因此收敛精度得到大幅提高。而对于GA算法，GSDGA表现出了更好的寻优能力，在多个函数中表现出了远超改进PSO的收敛速度和收敛精度，首先基于原生算法评估,PSO算法是对个体值随机偏移以搜寻解空间的算法，而GA算法则是将解抽象为染色体，采用选择操作、交叉操作和变异操作改变个体值，在选择操作中被选出的适应度较高的小种群称为精英个体群，在交叉操作中，在精英个体群中以一定概率对随机两个染色体进行配对，使其各自携带的一部分基因组进行交换。对于GSD策略中的个体贪婪更新操作来说，选择更优解杂交出来的后代个体适应度更好的可能性更高，因此能更好的加快算法的寻优速度，同时结合了自适应扰动后，更解决了GA算法后期种群多样性不高的问题。在单峰函数中,GSDGA以较快的速度收敛并且在保持高精度的局部最优解过程中寻得函数最优解，大幅节省迭代次数。在多峰函数中GSDGA加强了GA算法擅长的全局寻优能力。尤其是F6函数，原GA函数因其易陷入局部最优的问题，导致收敛能力相当有限，在算法前期中期走势即归于平缓，无法提高收敛精度，而GSDGA能在前中期将算法收敛至理论极值点，大大提高了收敛速度，同时节省了迭代次数。4结语本文提出一种普适性的基于贪婪更新和自适应扰动的自然计算策略以解决目前自然计算中存在的通用问题，提高算法全局寻优和局部寻优能力，并具备跳出局部最优陷阱的能力，通过大量的理论分析和实验结果表明，结合本策略后的算法不仅在单峰函数中有优秀的收敛精度和收敛速度表现，同时在多峰函数中能有效提高种群多样性，避免种群陷入局部最优陷阱中的同时仍具备较好的局部寻优能力。选取了包括单峰和多峰的多个测试函数来比对原算法和改进算法寻优性能，证明GSD策略的普适性和有效性。实验结果表明该策略在有效提高原算法特性的同时，收敛速度和收敛精度得到进一步提升。93-10-15201002200300400500600700选代次数参考文献：1 de Castro L N.Fundamentals of natural computing:an over-viewJ.Physics of Life Reviews,2007,4(1):1-36.2 Tang Xuefeng,Wang Zhizhou,Deng Lei,Wang Xinyun,LongJinchuan,Jiang Xin,Jin Junsong,Xia Juchen.A Review ofthe Intelligent Optimization and Decision in Plastic FormingJ.Materials,2022,15(19).3 Saberian Mohammad,Ghoddosian Ali,Ghasemi Ghale-bahman Ahmad.Computational intelligent optimization ap-proach based on Particle Swarm Optimization and ExtendedFinite Element Method for high-cycle fatigue life extensionJ.Journal of the Brazilian Society of Mechanical Sciencesand Engineering,2023,45(2),1-32.4 党向盈，李金凤.融合智能优化的软件测试用例生成方法J.软件工程,2 0 2 2,2 5(12):5 9-6 2.5 Dhruv Bhawna,Mittal Neetu,Modi Megha.Artificial intelligenceoptimized image segmentation techniques for renal cyst detection.3.Journal of medical engineering&technology,2022,PP,1-9.6Sun Guanglei,Shang Youlin,Zhang Roxin.An Efficient and Ro-bust Improved Whale Optimization Algorithm for Large ScaleGlobal Optimization ProblemsJ.Electronics,2022,11(9),1-20.7 Liu Jianxun,Shi Jinfei,Hao Fei,Dai Min.A reinforced explo-ration mechanism whale optimization algorithm for continu-ous optimization problemsJ.Mathematics and Computersin Simulation,2022,201.23-488 Xia Qingyu,Ding Yuanming,Zhang Ran,Liu Minti,ZhangHuiting,Dong Xiaoqi.Blind Source Separation Based onDouble-Mutant Butterfly Optimization AlgorithmJ.Sen-sors,2022,22(11),3979-3992.9 Wang Zichen,Dou Zhenhai,Dong Jun,Si Shuqian,WangChen,Liu Lianxin.Optimal Dispatching of Regional Intercon-nection Multi-Microgrids Based on Multi-Strategy Impro-ved Whale Optimization AlgorithmJ.IEEJ Transactions onElectrical and Electronic Engineering,2022,17(6)766-779.10 Yongjun Sun,Xilu Wang,Yahuan Chen,Zujun Liu.A modifiedwhale optimization algorithm for large-scale global optimizationproblemsJ.Expert Systems With Applications,2018,114.563-577.11 Deepika D,Balaji N.Effective heart disease prediction with Grey-wolfwith Firefly algorithm-differential evolution(GF-DE)for feature selec-tion and weighted ANN classification.J.Computer methods in bio-mechanics and biomedical engineering,2022,25(12),1-20.-15-20-2580090010001002003004005006007008009001000选代次数