混合蛙跳算法流程步骤图

基于混合蛙跳算法的SPECT-B超甲状腺图像配准郑伟;孟繁婧;田华;郝冬梅;吴颂红【摘要】为了降低甲状腺肿瘤的误诊率和漏诊率,提出将甲状腺肿瘤的SPECT图像和B超图像进行多模异机融合,提供涵盖功能信息和结构信息的融合后图像,为手术规划和放射治疗提供依据.配准是融合的前提,针对2种成像模式的不同特点,采用阈值方法和图割方法提取轮廓并填充为二值图像,建立仿射变换模型对待配准图像进行变换,将混合蛙跳算法引入基于特征的配准过程中,将局部区域的二值图像的互信息量作为适应度函数以获取水平平移量、垂直平移量和旋转角度的全局最优解.实验表明,该算法具有参数少、配准精度高、鲁棒性强等特点,为2种模式图像的融合奠定了基础.【期刊名称】《河北大学学报（自然科学版）》【年(卷),期】2013(033)003【总页数】7页(P305-311)【关键词】甲状腺肿瘤;SPECT图像;B超图像;特征配准;混合蛙跳算法【作者】郑伟;孟繁婧;田华;郝冬梅;吴颂红【作者单位】河北大学电子信息工程学院,河北保定071002;河北大学电子信息工程学院,河北保定071002;河北大学电子信息工程学院,河北保定071002;河北大学附属医院功能检查科,河北保定071002;河北大学附属医院功能检查科,河北保定071002【正文语种】中文【中图分类】TN911世界权威组织统计显示，甲状腺癌在2010年已跃居女性恶性肿瘤的第6位.目前，针对甲状腺肿瘤的影像检查分为功能成像（SPECT，PET等）和解剖结构成像（B 超，CT，MRI等）2类，单一检测方式的诊断准确率较低.图像融合技术能够将来自不同模式的图像中的信息结合起来，为外科手术的规划和放射治疗计划的设计提供依据.美国通用电气公司生产的SPECT／CT融合设备，将SPECT的功能图像CT 图像的准确定位相结合，确定肿瘤的位置和大小.但CT放射性会削弱人体抗菌能力，而且对于小于2cm的甲状腺肿瘤，B超检查检出率可高达67%，检出率明显高于CT，而且B超无放射性损伤.根据临床实际需求，提出了将甲状腺B超图像和SPECT图像进行融合处理，克服单模医学图像信息单一、表征局限的缺点，提供涵盖功能信息和结构信息的图像，提高对甲状腺肿瘤良、恶性判断的准确率.图像配准是融合的基础，医学图像配准就是指将来自不同模式的医学图像，通过空间变换使一幅医学图像与另一幅医学图像上的对应点或对应轮廓达到空间上的一致，或至少是所有具有诊断意义的点及手术感兴趣的点都达到匹配.因研究对象，研究目的不同，配准的方法也多种多样，常用的图像配准方法有基于灰度的方法、变换域法和基于特征的方法.现有的SPECT／CT融合设备为同机配准，采用的是衰减校正质量控制配准方法［1］.文献［2］提出基于人工免疫系统模型算法的点对点的配准算法，证明其性能的优越性和高精度性；文献［3］对人脑的CT和MR采用一种新的非均匀采样的方法提高了互信息的精确度；文献［4］则对人脑的MR和CT图像提出了一种改进式同步扰动随机算法对配准的过程进行了优化；文献［5］采用大变形微分同胚尺度映射算法进行配准，高斯－牛顿策略则实现了更快的收敛速度；文献［6］提出了基于稳健点集的随机全局优化配准；文献［7］提出了一种改进的人工鱼群算法和powell算法结合完成了在低分辨率下的图像配准；文献［8］首先把点集匹配问题转化为解空间为仿射参数空间下的目标函数优化问题，然后运用粒子群算法对相应的变换参数进行搜索，获得问题最优解；文献［9］提出基于边缘保护多尺度空间配准以及自动获取非线性扩散模型中平滑参数入的方法来提高配准的精度和速度，避免局部极值.B超图像和SPECT图像成像原理不同，同一器官表现出来的图像特征差异较大，基于灰度的方法和变换域法不适用，而基于特征的方法适合用于有明显特征的图像，B超图像和SPECT图像轮廓特征明显，适合用该方法.从原始的B超图像（如图1a所示）中可以看到甲状腺的两叶、肿瘤、颊部、气管，其周围的神经、血管和甲状软骨等.SPECT对于一些凉结节和冷结节不显像，亦无法显示气管或病灶的解剖细节，图像中只能观察到甲状腺区和其上方的放射线减淡区，即为凉结节（如图1b所示）.医学图像配准中所需的特征点通常为具有一定意义的点，而非纯粹几何意义上的点，河北大学附属医院专家在采集图像过程中，通过对肿瘤的触摸，标记出凉结节的位置（如图1c所示）.对比2种模式的图像，2幅图像都能显示的解剖部位为甲状腺和肿瘤，是具有临床诊断意义的区域，可采用基于特征的配准方法，将甲状腺的蝴蝶形轮廓特征和肿瘤的圆形轮廓特征结合起来作为配准的依据.采用基于特征的B超图像和SPECT图像的配准主要包括特征轮廓的提取，相似度测度，仿射变换模型的确定以及参数的优化.B超图像灰度对比度低、亮度分布不均匀，本文采用基于活动轮廓模型的图割算法［10］得到了所需区域的分割图（如图2a所示）.SPECT图像可显示的甲状腺和肿瘤的边界较为模糊，没有一个可以视觉可观的边界，于是以肿瘤上标记点为界限（如图2b所示），分割出实验所需的甲状腺和肿瘤的整体轮廓（如图2c所示）.由图2a可知，B超分割的轮廓线不圆滑，图2c所示的SPECT分割轮廓线较圆滑，且轮廓线不能达到完全对齐，于是不能采用基于轮廓线的配准，而由于两图像轮廓的区域内像素差异大，亦会造成误配准，于是我们将分割出的轮廓填充，以甲状腺和肿瘤的轮廓区域的二值图像分别作为参考图像和待配准图像.填充后的结果如图2d和图2e所示.相似性测度是用来度量图像间相似性的一种准则，本文以甲状腺和肿瘤轮廓区域二值图像的平均互信息作为配准测度.若A代表参考图像，B代表待配准图像，它们之间的平均互信息I（A；B）为其中，H（A）和H（B）分别是图像A和图像B的熵，H（AB）是它们的联合熵，都可由A和B的联合直方图hAB求出，见式（2）式中，A（i，j）和B（i，j）分别表示2幅图像相同位置的坐标点，n［A（i，j），B（i，j）］表示同一灰度级出现的次数.对上式两边除以全部灰度值出现的次数和n，即可得到归一化的联合直方图函数p（A，B）为则B超图像和SPECT图像轮廓区域二值图像的互信息为待配准B超图像是三维甲状腺图像的断层图像，由于甲状腺内部无相对运动，可以把甲状腺近似的看做刚体运动，以SPECT图像中医生标出的肿瘤大小为基准同比例缩放，并把图像均裁至208＊208，使待配准的图像经过预处理后具有相同的空间比例.设待配准图像未旋转时中心坐标为（a，b），旋转后的中心坐标为（c，d），若对图像进行水平平移Δx个像素，垂直平移Δy个像素，并以图像中心为基点旋转θ弧度，旋转后新图像左上角为原点，则SPECT图像和B超图像的仿射变换模型为B超图像和SPECT图像的配准问题就是寻求参数Δx，Δy，θ的解，代入仿射变换模型T，使互信息MI（T）最大，即可得2种模式图像的配准结果.多参数优化问题成为决定配准精度的核心因素，优化策略的选取尤为重要.混合蛙跳算法（shufled frog leaping algorithm，SFLA）是2003年由Eusuf和Lansey提出的一种基于群体智能的后启发式计算技术［11］.它结合了基于模因进化的模因演算法（MA，memeticalgorithm）和基于群体行为的粒子群算法（PSO，particle swarm optimization）2种群智能优化算法的优点，模拟青蛙群体寻找食物时，按族群分类进行思想传递的过程，关键是全局搜索策略和局部深度搜索策略的完美结合使得最后的解能够跳出局部极值点，向着全局最优的方向进行搜索，具有概念简单、调整的参数少、计算速度快、全局搜索寻优能力强，易于实现等特点.首先，随机生成U只青蛙组成初始群体，nDim表示变量的个数即解空间的维数，因需要寻优的参数为Δx，Δy，θ，所以nDim＝3.第i只青蛙可以表示成U（i）＝（U1i，U2i，U3i）.然后，把U1i，U2i，U31代入放射变换模型对待配准图像进行变换，再计算参考图像和变换后待配准图像的最大互信息，即为每只青蛙的适应度，用fUi表示，并将种群内青蛙个体按适应度降序排列，并记录全局最佳解Ug，即为U1.将整个青蛙群体分成m个族群，根据式（6）的分组方式每个族群包含n只青蛙，并满足关系U＝m×n.对每个子族群进行局部深度搜索，即对k循环进行更新操作，根据混合蛙跳规则［12］（如图3所示）青蛙的位置进行更新，Ds表示移动的距离，U′w表示更新后的青蛙，更新策略为其中，rand（）表示0和1之间的随机数，同时更新的距离Ds必须在可行域内.其中，Ub表示子群中的最佳解，Uw代表子群中的最差解.更新后，如果得到的解U′w优于原来的解Uw，则令U′w＝Uw.如果没有改进，则用全局最优解Ug取代原来的解Uw重复执行更新策略.如果仍然没有改进，则随机产生一个新的解Urandom取代原来的解Uw.当所有子群内部更新完成后，对子群的青蛙重新混合并排序进行分组和对子群的内部搜索，如此反复直到收敛到最优解或达到最大进化代数为止.在选定了混合蛙跳的优化方法后，有5个参数需要调整和确定［13］：子种群的个数、每个子群蛙的个数、每个子种群中的进化迭代次数、允许每只青蛙移动的最大距离、允许整个种群进化的代数次数.根据多次实验确定的参数可知，子群的个数和每个子群蛙的个数要选择合适的大小，子群蛙的个数太小就会丧失局部搜索的优点，还要保证初始种群的容量，容量越大，则能够找到全局最优的概率越大，经实验测试，选用4＊5青蛙群体.子群的进化迭代次数太小不益于子种群信息交流，太大则容易陷入局部最优，经实验测得迭代次数5至8最恰当.允许青蛙改变的距离Dmax控制的是算法进行全局搜索的能力，所以Dmax太小，则会降低全局搜索的能力，使算法容易陷入局部最优值，如果Dmax过大，则容易使算法错过最优解，经实验测试，20至34最适合.一般来说，当循环进化到一定次数后，代表最好解的青蛙的适应值就不再改变了，算法即可以此为条件停止了.图4横坐标代表进化迭代的次数，纵坐标代表全局最好青蛙的适应值，可以看出，在45代的时候适应值就不再改变了，并基本保持稳定，设定迭代次数为45即可.实验环境为Matlab7.1，Dell，CPU2.53GB，内存2GB.采用的所有数据来源于河北大学附属医院，SPECT图像采自GE Infina Hawkeye 4SPECT－CT单光子发射断层仪，B超图像采自Voluson E8三维彩色超声诊断仪，这2幅图像均按每4mm一断层，同一时期取至同一病人甲状腺的同一层面.为了验证本方法的有效性，先以2幅SPECT图像为例，一幅为参考图像，另一幅图像是人为改变水平平移量为10个像素，垂直平移量为20个像素，旋转角度为10个角度的待配准图像.利用本方法配准前后的数据如表1所示.由表1数据可以看到，基于轮廓特征点最大互信息的图像配准方法误差可以保证在3个像素内，可以达到很好的配准效果，配准精度较高，且有较好的稳定性. 在调至相同迭代次数的条件下，再与其他算法的配准效果加以比较，结果如图5所示.第1行分别表示配准前，粒子群算法（PSO），蚁群算法（Ant Colony），本文算法配准后的轮廓叠加图，第2行为对应的最后融合结果.比较3幅结果图，可以明显看出，粒子群算法和蚁群算法并未达到甲状腺和肿瘤位置的对齐，而本文算法具有较好的配准效果，混合蛙跳算法可以基本达到甲状腺和肿瘤的对齐，能够满足临床基本诊断需要.对这3种算法的配准时间和配准精度进行了比较，结果如表2所示.由表2数据也可证明虽然粒子群算法时间较快，但配准精度不高，且实验结果具有随机性；蚁群算法配准精度比粒子群算法精度高，但优化时间长.本文算法比蚁群算法有更高的配准精度，比粒子群算法有更快的配准速度.提出了一种基于混合蛙跳算法的甲状腺SPECT－B超图像配准方法，通过多次实验证明，该方法对甲状腺的SPECT图像和B超图像配准有较好的效果，不仅能够有效地防止配准结果陷入局部最优当中，还有很强的鲁棒性，能够为甲状腺的SPECT图像和B超图像的融合提供满足要求的配准图像，对甲状腺肿瘤的临床诊断具有较高的参考价值.【相关文献】［1］ SUH J W，KWON O K，SCHEINOST D，et al.CT－PET weighted image fusion for separately scanned whole body rat［J］.Med Phys，2012，39（1）：533－542.［2］ DELIBASIS K K，ASVESTAS P A，MATSOPOULOS G K.Automatic point correspondence using an artificial immune system optimization technique for medical image registration［J］.Computerized Medical Imaging and Graphics，2011，35（1）：31－41.［3］ FREIMAN M，WERMAN M，JOSKOWICZ L A.curvelet－based patient－specific prior for accurate multi－modal brain image rigid registration［J］.Medical Image Analysis，2011，15（1）：125－132.［4］ KHADER M，HAMZA A B.An information－theoretic method for multimodality medical image registration［J］.Expert Systems with Applications，2012，39（5）：5548－5556.［5］ ASHBURNER J，FRISTON K J.Diffeomorphic registration using geodesic shooting and Gauss－Newton optimization［J］.NeuroImage，2011，55（3）：954－967.［6］ PAPAZOV C，BURSCHKA D.Stochastic global optimization for robust point set registration［J］.Computer Vision and Image Understanding，2011，115（12）：1598－1609.［7］赵海峰，姚丽莎，罗斌，等.改进的人工鱼群算法和Powell法结合的医学图像配准［J］.西安交通大学报，2011，45（4）：46－52.ZHAO Haifeng，YAO Lisha，LUO Bin，et al.Registration of multi－resolution medical images using a modified artificial fish－swarm algorithm combined with Powell's Method ［J］.Journal of Xi'an Jiaotong University，2011，45（4）：46－52.［8］谭志国，鲁敏，任戈，等.匹配与姿态估计的粒子群优化算法［J］.中国图象图形学报，2011，16（4）：640－646.TAN Zhiguo，LU Min，REN Ge，et al.Particle swarm optimization based pose and correspondence estimation［J］.Journal of Image and Graphics，2011，16（4）：640－646.［9］李登旺，王洪君，尹勇，等.基于边缘保护多尺度空间的医学图像配准方法［J］.模式识别与人工智能，2011，24（1）：117－122.LI Dengwang，WANG Hongjun，YIN Yong，et al.Multiscale registration based on edge－preserved scale space for medical Images［J］.Pattern Recognition and Artificial Intelligence，2011，24（1）：117－122.［10］ XU Ning，AHUJA N，BANSAL R.Object segmentation using graph cuts based active contours［J］.Computer Vision and Image Understanding，2007，107（3）：210－224.［11］ EUSUFF M M，LANSEY K E.Optimization of water distribution network design using the shuffled frog leaping algo rithm［J］.Journal of Water Resources Planning and Management，2003，129（3）：210－225.［12］崔文华，刘晓冰，王伟，等.混合蛙跳算法研究综述［J］.控制与决策，2012，27（4）：481－486，493.CUI Wenhua，LIU Xiaobing WANG Wei，et al.Survey on shuffled frog leaping algorithm ［J］.Control and Decision，2012，27（4）：481－486，493.［13］ ELBELTAGI E，HEGAZY T，GRIERSON parison among five evolutionary－based optimization algorithm［J］.Advanced Engineering Informaties，2001，19（1）：43－53.。

基于邻域搜索的穴盘苗移钵路径优化蛙跳算法徐守江;罗竹青【摘要】在农业钵苗培育环节中常出现漏栽或钵苗不健康的情况,补种作业利用钵苗移栽机器人末端执行器从原点出发,从移栽穴盘中选取健康钵苗逐一补种到目的穴盘中,最后回到出发点的过程.本文基于混合蛙跳算法提出了一套解决补种作业过程中自动移钵问题的模型算法,较好解决了末端执行器在补种作业中的路径优化问题.针对自动移钵问题的特殊性,蛙跳算法模型融入了邻域搜索策略、交换因子、交换序和交叉操作等思想,算法简单且稳定性好.本算法有效解决了自动移钵路径的优化问题,移钵路径长度得到了大幅度的优化,提高了移栽效率.%In the cultivation of agricultural seedlings,there are often cases of missing or unhealthy seedling.The replan-ting operation refers to the use of end-effecters from the origin,and the selection of the seedlings from the transplanting tray to the goal tray,and finally back to the starting point.In this paper, a new method is developed for optimization of seedling transplanting path based on the hybrid frog leaping algorithm.The frog leaping algorithm model is integrated with the neighborhood search strategy, exchanging factor, exchanging order and crossover operation.The algorithm is simple and stable.The algorithm effectively solves the optimization problem of automatic seedling transplanting,and the length of the path is greatly optimized and the transplanting efficiency is improved.【期刊名称】《农机化研究》【年(卷),期】2018(040)011【总页数】5页(P208-212)【关键词】混合蛙跳算法;穴盘苗;移钵路径;邻域搜索【作者】徐守江;罗竹青【作者单位】江苏食品药品职业技术学院信息工程学院,江苏淮安 223003;江苏食品药品职业技术学院校企合作办公室,江苏淮安 223003【正文语种】中文【中图分类】S223.9;S240 引言在穴盘苗培育过程中，常出现穴盘内育苗不成功的情况，主要是由于漏栽和钵苗发育不正常引起，成苗率在90%左右[1]。

一种新的改进的混合蛙跳算法赵鹏军;邵泽军【期刊名称】《计算机工程与应用》【年(卷),期】2012(48)8【摘要】针对混合蛙跳算法在优化过程中受初始值影响较大且容易陷入局部最优的缺陷,提出了一个改进的混合蛙跳算法,该算法利用基于对立学习的策略产生初始种群,提高了产生解的质量；在进化过程中,将差分进化有机地嵌入其中,维持了种群的多样性.数值结果表明,改进的混合蛙跳算法对复杂函数优化问题具有较强的求解能力.%To overcome the drawbacks of local optima and instability involved in Shuffled Frog Leaping Algorithm(SFLA), an improved SFLA is proposed. The proposed algorithm employs Opposition Based Learning (OBL) to generate the initial population, which can obtain better initial candidate solutions. During the course of evolvement, the Differential Evolution (DE) is embedded in SFLA organically to maintain the population diversity. Numerical results show that the proposed SFLA has a better capability to solve complex functions than other algorithms.【总页数】3页(P48-50)【作者】赵鹏军;邵泽军【作者单位】商洛学院数学与计算科学系,陕西商洛726000;北京化工大学北方学院,河北三河065201【正文语种】中文【中图分类】TP18【相关文献】1.一种改进的混合蛙跳算法 [J], 施秋红2.一种改进的混合蛙跳算法 [J], 赵红星;常小刚3.一种改进的混合蛙跳算法及其在变压器设计中的应用 [J], 杜江;袁中华4.一种改进的混合蛙跳算法及其在水浴牵伸控制中的应用 [J], 肖纯材;郝矿荣;丁永生5.一种基于二分法查找的改进混合蛙跳算法 [J], 王晓彬;邹海荣因版权原因，仅展示原文概要，查看原文内容请购买。

《智能算法及应用技术》结课综述Name: MoonlightranEmail: randolphingwp@目录1. 随机蛙跳（SFLA）算法 (1)1.1 SFLA理论基础 (1)1.2 SFLA 的基本原理 (3)1.3 SFLA 的基本概念 (4)1.4 SFLA 的参数设置 (4)1.5 SFLA 的运算流程 (5)1.6 SFLA函数优化中实例 (10)1.7 粒子群算法（PSO）函数优化 (14)2. 多目标优化算法(NSGA—II) (19)2.1多目标优化问题描述 (19)2.2 基本概念 (19)2.3 非支配排序算法(NSGA) (20)2.4 带精英策略的非支配排序遗传算法(NSGA—II) (22)2.5 NSGA-II函数优化实例 (27)单目标和多目标优化算法介绍——随机蛙跳算法和带精英策略的非支配排序算法通常的优化问题可以分为单目标优化问题和多目标优化问题。

针对这两类问题，分别介绍随机蛙跳算法（SFLA）和带精英策略的非支配排序算法（NSGA—II），并且给出这两类算法在函数优化中的应用实例。

1.随机蛙跳（SFLA）算法随机蛙跳算法是由Kevin Lanes和Mustafa Eusuff于2003 年共同提出，该算法结合了基于遗传特性的模因算法和基于行为的粒子群算法的优点，适合解决各类组合优化问题。

混合蛙跳算法具有设置参数少、简单易于理解、鲁棒性强等特点，已在语音情感识别、作业车间调度、复杂函数优化问题求解等领域得到成功应用。

1.1 SFLA理论基础SFLA 是一种群体仿生类启发式进化计算方法，该算法将模因算法和粒子群优化算法的思想相结合，并经过适度扩展，因而兼具二者的优点。

作为SFLA 的理论基础，模因算法和粒子群优化算法有必要进行简要介绍。

1.1.1模因算法Moscato受Dawkin提出的meme概念的启示，于1989年首次提出了模因算法。

该算法源于文化进化理论中的隐喻思想，结合了全体成员参与搜索的思想和有选择性的特定个体搜索的机制，可以通过启发式搜索解决优化问题。

2009年7月Journal on Communications July 2009 第30卷第7期通信学报V ol.30No.7改进混合蛙跳算法求解旅行商问题罗雪晖，杨烨，李霞（深圳大学信息工程学院，广东深圳 518060）摘 要：以旅行商问题（TSP）为例，引入调整序思想设计了局部搜索策略，同时在全局信息交换过程中加入变异操作，提出一种改进混合蛙跳算法求解TSP问题。

实验结果表明，与遗传算法和粒子群优化算法相比较，改进混合蛙跳算法在求解TSP问题上具有更好的搜索性能和顽健性。

关键词：混合蛙跳算法；旅行商问题；局部搜索；全局信息交换中图分类号：TP18 文献标识码：A 文章编号：1000-436X(2009)07-0130-06Modified shuffled frog-leaping algorithm tosolve traveling salesman problemLUO Xue-hui, YANG Ye, LI Xia（College of Information Engineering, Shenzhen University, Shenzhen 518060，China）Abstract: Modified shuffled frog-leaping algorithm to solve TSP was proposed, which presented the concept of adjustment sequence to design the strategy of local searching, and added the mutation operation in the global exchange of information. Experimental results indicate that, compared with genetic algorithm and particle swarm optimization algorithm, the proposed algorithm has more powerful search capability and more strong robustness in solving TSP.Key words: shuffled frog-leaping algorithm; traveling salesman problem; local search; global information exchange1引言混合蛙跳算法是2000年由Muzaffar Eusuff和Kevin Lansey提出的一种基于群智能的亚启发式计算优化算法，用于解决离散组合优化问题[1]。

对较好和较差个体双向更新的混合蛙跳算法庞凯立;梁昔明【摘要】针对基本蛙跳算法在处理复杂函数优化问题时求解精度低且易陷入局部最优的缺点,将共轭梯度法引入基本蛙跳算法,对排名靠前的p个模因组中的精英个体和排名靠后的q个模因组中的落后个体同时使用共轭梯度法进行更新,一方面增强对较差青蛙的指导能力,另一方面使最差的青蛙直接更新,提高了算法的收敛精度.所得混合蛙跳算法有效结合了基本蛙跳算法较强的全局搜索能力和共轭梯度法快速精确的局部搜索能力.将所得的混合蛙跳算法与其他智能优化算法进行对比,数值试验结果表明,无论从收敛精度还是进化代数而言,所得混合蛙跳算法较其他算法均有较大的改进,具有更高的收敛精度,能有效避免陷入局部最优,且优化结果更加稳定.【期刊名称】《北京建筑大学学报》【年(卷),期】2016(032)004【总页数】6页(P52-57)【关键词】混合蛙跳算法;共轭梯度法;数值试验;适应度函数【作者】庞凯立;梁昔明【作者单位】北京建筑大学理学院,北京100044【正文语种】中文【中图分类】TP301.6基本蛙跳算法[1]是一种新的基于群体智能的启发式算法，该算法是在2003年由Eusuff和Lansey受青蛙进食行为的启发进行建模和仿真研究的结果，该算法结合了粒子群算法和模因算法两者的优点，具有结构简单、收敛速度快和全局寻优能力强等特点.基本蛙跳算法与其他群体迭代算法一样，虽然具有较强的全局搜索能力，但是易陷入局部最优，且收敛精度不高. 为此，学者们进行了深入的研究，提出了一些改进算法，也都取得了不错的效果. 文献[2]对子群中每只青蛙个体引入了随机扰动，并让子群内每只青蛙个体都参与产生新个体，充分利用每只青蛙个体的信息，增加了种群多样性. 文献[3]引入全局共享因子和局部共享因子，由于共享因子随着迭代次数的增加而增大，使得在局部搜索初期，较小的共享因子初值能减弱最优个体对最差个体的指导，避免了青蛙个体更新步长过大而跳过局部最优；在进化后期，共享因子增大，增强了最优个体对最差个体的指导，使得个体跳过局部最优实现全局收敛，该算法动态改变最优个体对最差个体的指导能力，使得青蛙个体更容易跳出局部最优实现全局收敛. 文献[4]基于量子理论提出一种量子混合蛙跳算法，该算法采用量子位的Bloch球面坐标编码个体，利用量子位在Bloch球面上绕轴旋转的方法更新个体，通过自适应混沌旋转角度算子提高子群内部局部搜索能力，采用Hadamard门实现个体变异避免早熟，有效扩展了空间的搜索范围. 文献[5]定义了新的粒子分类标准，将所有青蛙按此标准进行分类，青蛙个体在迭代过程中根据自身状态动态调整惯性权重，并以停滞代数判断是否对最优个体进行优化，避免了陷入局部最优.以上文献中的改进算法都较好地改善了基本SFLA算法，在克服种群陷入局部最优缺陷的基础上增加了种群多样性. 考虑到传统优化算法—共轭梯度法具有较强的局部搜索能力，而现代智能优化算法—基本蛙跳算法收敛精度不高，寻找一种方法将蛙跳算法与共轭梯度法结合起来从而凸显各自的优点显得尤为重要，且历来很少有学者将传统优化方法与基本蛙跳算法结合起来研究. 本文提出的对较好和较差个体进行更新的混合蛙跳算法(SFLA_HH)，充分利用了SFLA算法和共轭梯度法两者的优点，弥补了两者的不足，将SFLA_HH算法与其他智能优化算法进行对比，对五个测试问题的试验结果表明，SFLA_HH算法收敛精度更高.对无约束连续优化问题：若x*∈Rd满足：则称x*为f(x)在全空间Rd上的全局最小点或整体极小点.1.1 SFLA原理SFLA算法将每个个体看做池塘中的一只青蛙[6]，搜索区间即为整个池塘. SFLA算法首先在寻优区间内随机初始化一组向量来组成青蛙的初始种群[7]P={X1,X2,…,Xi,…,XF}(i=1,2,…,F)，第i只青蛙为Xi=(xi1,xi2,…,xid)，每一只青蛙代表一个待选解，xij为第i只青蛙第j维的分量. 对于每个青蛙个体，计算适应度函数值fit(Xi)，本文中适应度函数取为目标函数，然后将所有青蛙个体按照它们的适应度值进行升序排列，并分别放入m个模因组中. 设Mk为第k个模因组青蛙的集合(k=1,2,…,m)，表达式如下：式中，n为每个模因组中的青蛙的个数.种群中适应度函数值最小的青蛙用Xg表示，用和分别表示第k个模因组Mk中适应度函数值最小和最大的青蛙，通过每个模因组Mk中的跳跃前进和位置调整进而影响整个族群的前进位置调整公式如下：青蛙移动的距离向量：更新最差青蛙位置：式中，rand()是0～1之间的随机数，Smax是青蛙跳跃每个分量上允许的最大值，Smin是青蛙跳跃每个分量上允许的最小值. 青蛙在跳跃前进时，如果经(5)更新后的的适应度值比小，用代替；否则用Xg取替重新进行更新操作位置更新公式如下：如果经过式(5)、式(7)计算后仍然产生不了适应度函数值更小的青蛙，那么就随机化一个新向量代替至此完成一次局部迭代，重复局部迭代L次. 当所有模因组都完成局部迭代L次后，判断是否达到全局搜索次数G次，若没有，则将所有F只青蛙重新混合、排序、分组，再按照上述局部搜索步骤重复搜索，直至符合终止条件. 一般情况下，当算法达到了预定的全局迭代次数时，算法终止并输出最优解，全局最优解即为Xg.1.2 共轭梯度法共轭梯度法[8]是由Hestenes和Stiefel( 1952)提出来的，是一种介于最速下降法和牛顿法之间的经典非线性无约束优化算法，它的基本思想是根据迭代点处的负梯度方向构造出一组共轭方向，再沿着这组方向搜索目标函数极值，共轭梯度法的机制保证了所得到的这组共轭方向就是函数值的下降方向. 共轭梯度法最大的优势在于同时解决了最速下降法收敛慢和牛顿法对目标函数要求较高且计算量大的不足，具有较好的局部搜索能力，是求解大型非线性无约束最优化问题的有效算法之一，其求解流程如下：步骤1 选取初始点X0，给定精度eps，计算初始搜索方向步骤2 若‖‖≤eps，输出X0并停止迭代；否则，令k=0，转步骤3；步骤3 求tk使得步骤4 令Xk+1=Xk+tkPk；步骤5 计算若‖‖≤eps，输出Xk+1并停止迭代；否则转步骤6；步骤6 计算共轭方向Pk+1，令k=k+1并转步骤3.考虑到基本蛙跳算法中精英个体更新效率较低、较差个体更新效果不明显等缺陷导致的进化后期易陷入局部最优这一缺点，本文提出在基本蛙跳算法中引入共轭梯度法，对前p个模因组中的精英个体和后q个模因组中的落后个体直接进行更新，一方面增强了对较差个体的指导能力，另一方面提高了最差个体的更新效率. SFLA_HH算法首先对种群和参数进行初始化，各青蛙的初始位置在给定搜索区间内随机生成；然后计算每只青蛙的适应度函数值，对函数值进行升值排序. 本文中适应度函数取为目标函数，故函数值越小代表点的位置越好，由此得到Xg；然后将排完序后的青蛙按照式(3)划分模因组，找到每个模因组中的Xb和Xw，对模因组中的前p组和后q组与共轭梯度法进行结合，具体更新规则为：前p组以Xb为初始点，即X0=Xb，初始搜索方向P0取为-g(Xb)，根据X1=X0+tP0对Xb进行更新，其中步长t根据：求解. 如果X1满足给定的精度要求，则跳出共轭梯度法循环，否则，按下式：进行下一点的迭代，重复计算直至达到给定的精度要求或次数，更新Xb，再按照式(4)、式(5)指导更新Xw；将排列在中间的的(m-p-q)个模因组按照式(5)、式(7)进行更新；将排列在最后的q个模因组与共轭梯度法结合，以Xw为初始点，初始搜索方向P0取为-g(Xw)，再按照上面的式(8)、式(9)、式(10)对Xw进行更新. 从整体效率来考虑，可以适当放低共轭梯度法的精度要求[9]，并且同时使用精度和循环代数一起作为判断共轭梯度法停止的条件. 当所有模因组的局部更新操作都完成后，判断是否达到全局搜索次数，若满足，则输出当前最好解，即为全局最优解；否则，将全部青蛙混合，重复进行下一轮搜索. SFLA_HH算法流程如下：步骤1 随机初始化F只青蛙，最大蛙跳步长为Smax，模因组数为m，每个模因组中的青蛙数为n，局部迭代次数为L，整体迭代次数为G；步骤2 计算所有青蛙适应度函数值；步骤3 将青蛙按照适应度函数值从小到大排序，适应度函数值最小的青蛙记为Xg；步骤4 青蛙种群根据分组规则按照(3)式划分为m个模因组；分别记下每个模因组中的Xb和Xw；步骤5 对前p个模因组结合共轭梯度法，以模因组中Xb为初始点进行循环迭代r 次或达到精度要求，更新Xb，再按照式(4)、式(5)指导更新Xw；对中间的(m-p-q)个模因组按照式(5)、式(7)进行局部搜索L次，更新Xw；对剩余的q个模因组以Xw为初始点行进行循环迭代r次或达到精度要求，更新Xw；步骤6 当局部搜索全部完成后，判断是否达到全局混合迭代次数G，若满足，则输出当前最好解，即为全局最优解；否则，将全部青蛙混合，返回步骤3进行下一轮搜索.因为共轭梯度法对于一个n元正定二次目标函数最多n次就可以寻得最优解，可见共轭梯度法的寻优效率之高. 由于共轭梯度法的运算涉及到梯度计算，运算过程中调用共轭梯度法的次数越多，耗时越久，在本文中共轭梯度法的运算次数与两个因素有关，一是结合共轭梯度法的组数，二是共轭梯度法的内部终止迭代次数r.为了整体寻优速度，本试验调用共轭梯度法的次数不宜太多，故只选取前两组和后两组，即p=q=2.共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题，因此混合蛙跳算法SFLA_HH对较高维数的函数优化具有较大的优势.为验证混合蛙跳算法SFLA_HH的寻优效果和稳定性，将SFLA_HH算法与基本SFLA算法在不同维度下进行试验. 为了进一步验证文中所提出的混合蛙跳算法的优越性，将SFLA_HH与SFLA、文献[2]中提出的内嵌扰动变异的混合蛙跳算法(DVSFLA)、文献[10]中提出的自适应粒子群优化算法(APSO)以及文献[11]中提出的强化学习的人工蜂群算法(GABC)分别在30维时固定全局迭代次数情况下进行对比分析. 又将SFLA_HH与文献[5]中基于新搜索策略的混合蛙跳算法(NSSFLA)在固定精度情况下进行对比分析. 三种情况对比均使用表1中5个典型的无约束优化问题进行数值试验，各问题的目标函数表达式、搜索范围和理论最优值如表1所示[12]，其中D为问题的维度.函数f1为Sphere单峰函数，全局最小点是(0,0,…,0)；函数f2为Rastrigin函数，函数f3为Griewank函数，函数f4为Ackley函数，都是多峰函数，有很多局部极小点，全局最小点是(0,0,…,0)；函数f5为Rosenbrock函数，是非凸的病态函数，在极小值附近有陡峭的峡谷，用SFLA求解时很容易陷入局部极值，它的全局最小点是(1,1,…,1). 为了进一步比较各种算法的性能，并减少偶然性的影响，本文采用Matlab R2014b试验平台进行数值试验，并对每个测试问题进行30次独立试验，取试验所得的平均最优值、标准差进行对比. 其中，平均最优值为30次试验中每次求得的全局最优解相加除以30；标准差即为30次试验中全局最优解的标准差.本文所选取的试验参数如下，其余对比算法参数设置见对应文献：青蛙个体数F=200;族群数m=20;族群内青蛙个数n=10;局部循环迭代次数L=10;全局循环迭代次数G=200;青蛙最大移动步长设置规则根据文献[13]，即：Smax=可行域的界×45%；p=2；q=2；r=5；eps=1e-2.表2为将SFLA_HH算法与基本SFLA算法在不同维度下进行试验的结果对比. 由表2中对比结果可以看出，在不同试验维度下，无论是解的质量还是算法的稳定性，SFLA_HH算法较SFLA算法均有较大提高. 对于五个测试问题，SFLA算法均未找到最优解，且随着维数增高，SFLA寻优效果也越来越差，而SFLA_HH算法都找到了最优解，并且解的精度在维数变化较大的情况下保持一定的稳定性. 对于问题f1，f2，f3，SFLA_HH算法在三种维度下都找到了理论最优解，SFLA求解精度较差，且未找到最优解；对于问题f4，f5，SFLA_HH算法也都找到了最优解，SFLA算法求解效果较差，且未找到最优解.表3为30维时SFLA_HH与其他现代智能优化算法在固定全局迭代次数情况下结果对比.表4为SFLA_HH与基本蛙跳算法及文献[5]中NSSFLA算法在固定精度情况下结果对比.从表3对比结果中可以看出，SFLA_HH算法与其他算法相比有明显的优势，对于五个测试问题都找到了最优解，其中对于f1，f2，f3都找到了理论最优解；SFLA 算法对于所有的问题均未找到最优解；DVSFLA只对f1找到了最优解；APSO和GABC对于f1，f2和f4均找到了最优解，但求解精度都不如SFLA_HH，可见SFLA_HH的寻优精度之高.从表4可以看出，SFLA对于所有问题都没能达到指定的精度，NSSFLA和SFLA_HH都达到了指定精度；对于f2，NSSFLA和SFLA_HH进化代数没有太大差异；对于f3，SFLA_HH比NSSFLA效果略差；但对于f1和f5，SFLA_HH只需一次就可以达到指定精度，比NSSFLA所需次数少，对于f4，NSSFLA最少需要17次才可以达到指定精度，而SFLA_HH最少只需11次就可以达到指定精度，且平均次数也比NSSFLA少.综上，SFLA_HH收敛精度和平均进化代数均优于基本蛙跳算法和其他几种智能优化算法.共轭梯度法是经典无约束优化算法，由于采用梯度信息，因此可以较快的收敛到函数极小值；基本蛙跳算法在搜索区间广泛随机采点，然后从各点出发，依据青蛙觅食原理搜寻全局最小点，因而具有较好的全局搜索能力. 本文所提出的SFLA_HH算法正是结合了两者的优点，对于排列在前面位置较好的模因组和后面位置较差的模因组均引入共轭梯度法，不仅加强了对最差青蛙个体的指导能力，更提高了最差青蛙的更新效率，进而提高了算法的收敛精度. 改进算法无论从收敛精度、进化代数还是稳定性方面都有较大的优越性，但仍存在一些问题，由于共轭梯度法每次循环都需要计算梯度信息，故对于有些复杂问题，或者非凸问题无法很好地解决，这也是需要改进的地方.【相关文献】[1] 崔文华，刘晓冰，王伟,等.混合蛙跳算法研究综述[J]. 控制与决策，2012，4(3)：481-486[2] 季骏，戴月明，吴定会.内嵌扰动变异的混合蛙跳算法[J].计算机工程与应用，2015，51(12)：27-30[3] 刘立群，王联国，韩俊英,等.基于全局共享因子的混合蛙跳算法[J].计算机工程，2013，39(10)：162-166[4] 张强，李盼池.量子混合蛙跳算法求解连续空间优化问题[J].吉林大学学报：理学版，2013，51(3)：471-477[5] 赵芳，张桂珠.基于新搜索策略的混合蛙跳算法[J].计算机应用与软件，2015，32(8)：224-228[6] 杨淑莹，张桦.群体智能与仿生计算—Matlab技术实现[M].北京：电子工业出版社，2012：167-176[7] 马鲁，陈国初，王海群.蛙跳算法及其在函数优化中的应用[J].上海电机学院学报，2014，17(2)：68-75[8] 孙文瑜，徐成贤，朱德通.最优化方法[M].北京：高等教育出版社，2010：125-137[9] 梁昔明，李德生.嵌入共轭梯度法的混合粒子群优化算法[J].小型微型计算机系统，2014，35(4)：835-839[10] Zhan Zhihui, Zhang Jun, Li Yun, et al. Adaptive particle swarm optimization[J]. IEEE Transactions on Systems Man, and Cybernetics—Part B: Cybernetics, 2009,39(6): 1362-1381[11] Zhu Guopu, KWONG S. Gbest-guided artificial bee colony algorithm for numerical function optimization[J]. Applied Mathematics and Computation, 2010, 217(7): 3166-3173 [12] Meng Jia-na, Lin Hong-fei. Transfer learning based on graph ranking[C]∥Proc. Of the 9th International Conference on Fuzzy Systems and Knowledge Discovery. [S.1.]: IEEE Press, 2012[13] Eusuff M, Lansey K, Pasha F. Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization [J]. Engineering Optimization, 2006, 38(2): 129-154。

融合多策略改进麻雀搜索算法目录一、内容概要 (2)1.1 研究背景 (3)1.2 研究目的与意义 (3)1.3 国内外研究现状 (4)1.4 主要内容与结构安排 (6)二、麻雀搜索算法概述 (7)2.1 麻雀搜索算法的原理 (7)2.2 麻雀搜索算法的优缺点分析 (9)2.3 麻雀搜索算法的应用场景 (10)三、多策略改进方法 (11)3.1 基于个体多样性策略的改进 (11)3.1.1 多目标优化策略 (12)3.1.2 粒子多样性策略 (13)3.2 基于个体行为优化策略的改进 (15)3.2.1 精英蚂蚁系统(EMAS) (16)3.2.2 最大最小蚂蚁系统(MMAS) (17)3.2.3 差分蚂蚁系统(DAS) (18)3.3 基于全局搜索策略的改进 (20)3.3.1 粒子网络(GS) (21)3.3.2 粒子群优化(PSO) (22)3.3.3 混合蛙跳算法(SFLA) (23)四、融合多策略的麻雀搜索算法设计 (24)4.1 算法总体框架设计 (25)4.2 关键参数设置与调整策略 (26)4.3 算法实现步骤及流程图 (28)五、实验设计与结果分析 (29)5.1 实验环境与参数设置 (31)5.2 对比算法选择与基准函数 (32)5.3 实验结果与性能分析 (33)5.4 结果讨论与分析 (34)六、结论与展望 (35)6.1 研究成果总结 (36)6.2 研究不足与局限性分析 (37)6.3 后续研究方向与展望 (38)一、内容概要随着科技的不断进步和优化问题的日益复杂化，传统的优化算法已经难以满足各种应用场景的需求。

在这种背景下，麻雀搜索算法（Sparrow Search Algorithm, SSA）作为一种新兴的群智能优化算法，受到了广泛关注。

SSA在某些方面仍存在局限性，如收敛速度较慢、易陷入局部最优等。

为了克服这些问题，本文提出了一种融合多策略改进的麻雀搜索算法（IMSSA）。

第５１卷第３期　２０１３年５月　吉林大学学报（理学版）　

Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉｌｉｎ　Ｕｎｉｖｅｒｓｉ｝ｙ（Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　ＶｏＩ＿５１　Ｎｏ．３　

Ｍａｖ　２Ｏ１３　

ｄｏｉ：１０．７６９４／ｊｄｘｂｌｘｂ２Ｏ１３０３２６　

量子混合蛙跳算法求解连续空间优化问题　张强，李盼池　（东北石油大学计算机与信息技术学院，黑龙江大庆１６３３１８）　

摘要：基于量子理论提出一种量子混合蛙跳算法，该算法采用量子位的Ｂｌｏｃｈ球面坐标编　个体，利用量子位在Ｂｌｏｃｈ球面上绕轴旋转的方法更新个体，通过自适应混沌旋转角度算　提高子群内部局部搜索能力，采用Ｈａｄａｍａｒｄ门实现个体变异避免早熟，有效扩展了解空　的搜索范围．实验结果表明，该方法优于普通的混合蛙跳算法、粒子群算法和遗传算法，　有较高的优化能力和效率，更适合高维复杂函数的优化．　关键词：量子计算；混合蛙跳算法ｌ连续空间优化；仿真　中图分类号：ＴＰ３０１。６　文献标志码：Ａ　文章编号：１６７１—５４８９（２０１３）０３—０４７１－０７　’　

Ｑｕａｎｔｕｍ　Ｓｈｕｆｆｌｅｄ　Ｆｒｏｇ　Ｌｅａｐｉｎｇ　Ａ　Ｃｏｎｔｉｎｕｏｕｓ　Ｓｐａｃｅ　Ｏｐｔｉｍｉｚａｔｉｏｎ　ｌｇｏｒｉｔｈｍ　ｆｏｒ　

Ｐｒｏｂｌｅｍｓ　

ＺＨＡＮＧ　Ｑｉａｎｇ，ＬＩ　Ｐａｎ—ｃｈｉ　（Ｓｃｈｏｏｌ　ｏｆ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｅｃｈｎｏｌｏｇｙ，Ｎｏｒｔｈｅａｓｔ　Ｐｅｔｒｏｌｅｕｍ　Ｕｎｉｖｅｒｓｉｔｙ，Ｄａｑｉｎｇ　１６３３１８，　ＨｅｉｌｏｎｇＪ　ｉａｎｇ　Ｐｒｏｖｉｎｃｅ，Ｃｈｉｎａ）　、　

Ａｂｓｔｒａｃｔ：Ａ　ｑｕａｎｔｕｍ　ｓｈｕｆｆｌｅｄ　ｆｒｏｇ　ｌｅａｐｉｎｇ　ａｌｇｏｒｉｔｈｍ　ｗａｓ　ｐｒｏｐｏｓｅｄ　ｗｈｉｃｈ　ｃｏｍｂｉｎｅｓ　ｗｉｔｈ　ｔｈｅ　ｑｕａｎｔｕｍ　ｔｈｅｏｒｙ．Ｉｎ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ，ｔｈｅ　ｉｎｄｉｖｉｄｕａｌｓ　ａｒｅ　ｅｘｐｒｅｓｓｅｄ　ｗｉｔｈ　Ｂｌｏｃｈ　ｓｐｈｅｒｉｃａｌ　ｃｏｏｒｄｉｎａｔｅｓ　ｏｆ　ａ　ｕｂｉｔｓ，ｔｈｅ　ｉｎｄｉｖｉｄｕａｌ　ｕｐｄａｔｅ　ｉｓ　ｒｅａｌｉｚｅｄ　ｗｉｔｈ　ｔｈｅ　ｒｏｔａｔｉｏｎ　ｏｆ　ｑｕｈｉｔｓ　ｉｎ　Ｂｌｏｃｈ　ｓｐｈｅｒｅ，ａｎｄ　ｔｈｅ　ｌｏｃａｌ　ｓｅａｒｃｈ　ｃａｐａｂｉｌｉｔｉｅｓ　ｗｉｔｈｉｎ　ｔｈｅ　ｓｕｂｇｒｏｕｐ　ｉｓ　ｉｍｐｒｏｖｅｄ　ｗｉｔｈ　ａｄａｐｔｉｖｅ　ｃｈａｏｔｉｃ　ｒｏｔａｔｉｏｎ　ａｎｇｌｅ　ｏｐｅｒａｔｏｒ．Ｔｈｅｎ，ｔｏ　

多种运输方式的4PL多到多网络设计模型与算法李锐;孙福明【摘要】针对第四方物流(4PL)承担多个供需点对之间物流配送任务的情况,考虑实际中第三方物流(3PL)运输供应商具有多种运输方式,研究多种运输方式的4PL多到多网络设计问题.建立问题的优化模型,在选择3PL运输供应商的同时确定运输方式,并在满足配送时间约束下最小化总的物流成本.根据问题模型,设计混合蛙跳算法(SFLA)对问题进行求解.最后,通过仿真实验来验证模型的合理性,并测试SFLA的性能.实验结果表明模型能够合理描述问题,并且SFLA能够对问题进行有效求解.【期刊名称】《计算机工程与应用》【年(卷),期】2018(054)018【总页数】6页(P229-234)【关键词】第四方物流;多到多网络设计;多运输方式;混合蛙跳算【作者】李锐;孙福明【作者单位】辽宁工业大学电子与信息工程学院,辽宁锦州 121001;辽宁工业大学电子与信息工程学院,辽宁锦州 121001【正文语种】中文【中图分类】TP291 引言物流业务外包已经成为许多企业提高自身的核心竞争力的有效途径。

随着经济全球化的发展，往往需要多个物流公司合作才能完成一项物流任务。

由于能够整合不同的第三方物流（3PL）资源，依靠其信息方面的优势，解决单独靠一家3PL不能完成的任务，第四方物流[1]（4PL）开始得到关注。

在运作过程中，4PL需要根据需求设计合理的物流网络来提供有效的物流服务。

现实中，很多情况需要承担多个确定的供需点对之间的配送任务，即多到多的配送任务。

目前，4PL网络设计问题已经得到一定的研究[2-4]。

然而，这些研究都是考虑4PL承担某种产品的配送或回收任务。

此外，3PL运输供应商可能提供多种运输方式供选择，所以在4PL网络设计过程中需要同时考虑选择3PL运输商及运输方式。

可见，研究多种运输方式的4PL多到多网络设计问题具有现实意义。

目前，国内外学者已经对考虑多种运输方式的物流及运输相关问题进行了研究。