求解CVRP的改进混合蛙跳算法研究

改进的蛙跳算法在库存匹配中的研究曾伟渊【摘要】针对生产订单库存匹配问题,提出一种改进的混洗蛙跳算法(SF-LA)进行求解.采用随机分组策略,平衡各子群的寻优能力,保持种群多样性;打破最差蛙只向最优蛙学习的模式,引入Minkowski距离,使最差蛙借助更多同伴信息选择进化方向,增强种群适应性;针对最优蛙进化机会少,引入精英策略和变异思想更新其位置,避免陷入局部极小,加快收敛速度.仿真实验表明所建立模型的正确性和改进后算法的有效性.【期刊名称】《哈尔滨师范大学自然科学学报》【年(卷),期】2015(031)004【总页数】4页(P54-57)【关键词】生产订单;库存匹配;蛙跳算法;Minkowski距离【作者】曾伟渊【作者单位】厦门软件职业技术学院【正文语种】中文【中图分类】TP30 引言当前库存匹配问题主要集中在钢铁等流程行业，在钢铁、石化等流程行业的生产经营主要面临两方面的问题:一方面要在复杂的工艺条件下实现生产的连续性，第二客户对最终产品在规格、种类、数量和交货期上的各种要求需要满足［1］.与钢铁、石化等行业类似，在磁性材料生产管理过程中，为了实现非订单库存产品的有效利用，需要将其与客户下达的生产订单进行匹配.针对钢铁企业生产过程中订单与库存之间的匹配问题Trumbo等人对其做了重要的贡献，他们主要针对工艺路线和生产组织等特殊的约束条件的库存匹配问题进行研究，并提出了解决方法［2］.库存匹配问题可以与多背包问题(MKP)进行类比，均属于被证明为NP难的组合优化问题［3－4］.针对基本混洗蛙跳算法(SFLA)收敛速度慢、优化精度低且易于陷入局部最优的问题，对其进行多项改进.采用随机分组策略，平衡各子群的寻优能力，保持种群多样性;打破最差蛙只向最优蛙学习的模式，引入Minkowski距离，使最差蛙借助更多同伴信息选择进化方向，增强种群适应性;针对最优蛙进化机会少，引入精英策略和变异思想更新其位置，避免陷入局部极小，加快收敛速度，最后选取合适的目标函数，将改进前后混洗蛙跳算法(ISFLA)用于冷轧液压伺服位置(APC)系统的PID参数整定，并将整定结果进行西门子PLC实验验证，结果表明改进后算法的有效性和高效性.1 库存匹配问题描述库存匹配的流程图如图1所示.人工库存匹配工作量大，库存匹配时间长，生产订单拖期严重，同时，选取的最终匹配结果，不一定是最优的或近似最优的.因此该文采用改进的蛙跳算法进行库存匹配问题的研究的.2 库存匹配数学模型针对库存匹配问题，首先给出了参数与变量的符号定义.i:订单序号;l:库存微粉编号;IS:生产订单集合;LS:库存微粉集合;ai:计划员给定的生产订单i库存匹配的优先级系数;di:订单i的交货日期;gi:生产订单i的牌号编码;bl:库存微粉l的桶号;rl:库存微粉l是否为预留微粉，若rl=1，则为预留微粉;否则，非预留微粉;Ωi:满足生产订单i要求的库存微粉集合，;Ωi⊆LS:Ψl库存微粉l能够匹配的生产订单集合，φl⊆IS;ωi:实际匹配生产订单i库存微粉集合，ωi⊆Ωi;xl(i):若库存微粉l被匹配给生产订单i，则为1;否则为0;Wl(i):若库存微粉l被匹配给生产订单i的重量.图1 库存匹配流程图(2)目标函数和约束目标函数(1)最大化库存匹配的微粉重量;目标函数(2)最大化匹配出的微粉的入库时间;目标函数(3)最大化匹配出的微粉的氧含量;目标函数(4)最小化匹配出的微粉的平均粒度.约束(5)库存微粉的牌号与生产订单的牌号属于同一性能序列且不低于订单要求;约束(6)一个生产订单最多与三个库存编号的微粉匹配;约束(7)与一个生产订单匹配的多个微粉的入库时间偏差不超过30 d;约束(8)生产订单匹配的库存粉重不能超过生产订单的需求量.3 改进的蛙跳算法3.1 基本混洗蛙跳算法存在的问题(1)对于基本的混洗蛙跳算法，有序的分组方法使得越靠前的子种群，其平均适应度值越高，全局最优解往往存在于这样的分组里，因此，即使每一组每代更新最差蛙，也是这样的分组得到新的全局最优解的概率最大，寻优能力强于其他分组，这为整个种群容易陷入局部极值埋下了隐患.(2)根据基本的混洗蛙跳算法，最差蛙可能的新位置被限制在当前位置和最优蛙位置的线性区域，最差蛙永远跳不出最优蛙.即使当最差蛙的新位置无法得到改善而产生随机解，然而并不能保证随机解一定会更优.结果，这种蛙跳规则限制了本组进化的搜索空间.同时，最差蛙仅仅被最优蛙影响，并没有做到个体间充分的思想交流，降低了种群的适应性.除此之外，最优蛙在跳跃过程中很少有机会进化，这造成算法的学习机制不充分，种群多样性减少，从而导致早熟收敛［7］.3.2 随机分组策略为解决基本混洗蛙跳算法的第一个缺陷，从改进全局搜索方式的角度出发该文提出了对青蛙进行随机分组的策略.随机分组策略的主要思想是:首先，按照适应度值由大到小将N只青蛙进行排序;其次，将整个种群划分成n个独立的子种群;第三，实现每个子种群包含解的个数是m个，并且在算法迭代过程中，前n个解需要随机进入不同的n个子种群，同时实现每个解只能进入一个子种群，依此类推，直到所有解分配完毕.采用上述的随机分组策略，使得各个子种群通过不断的更新以得到新的全局最优解的机会均等.该策略强化了子种群的寻优能力，实现了种群的多样性，避免了蛙跳算法陷入局部最优［5］.3.3 最差蛙改进策略考虑原算法各子群中最差蛙的进化仅仅利用到最优蛙的信息，于是在此基础上引入Minkowski距离，使其不仅仅向最优蛙学习，而且向该子群中其他个体学习，使得最差蛙能充分利用所得到的信息来判断向哪个方向进化，而不是局限在和最优蛙的单一的直线方向上，从而加快进化速度，并且当该系统突发扰动时，由于集体的力量，使得适应能力提高，鲁棒性增强.最差蛙位置更新公式如式(9)所示.其中，Xi表示子种群中的第i只青蛙，S(i)表示子种群中最差蛙受第i只青蛙影响后得到的实际步长，c1表示同一种群中最差青蛙和另外随机选取的一只青蛙的学习因子，取值范围是(0，1)之间的随机数.c2表示整个种群的全局最优蛙与该种群中的最差蛙的学习因子，其中范围为(0，1)之间的随机数.M(Xi，Xw)表示Minkowski距离，即子种群中的最差解与第i个解之间的实际距离.3.4 次优蛙改进策略在基本混洗蛙跳算法中，最优蛙几乎不进化，大量仿真实验证实最优蛙的地位一般会被保持很多代，造成算法寻优速度慢，易出现早熟收敛，不能真正寻到目标函数的最小值.该文借鉴精英策略，保留每个种群中的最优蛙，以防最优蛙向较坏方向变异后造成没有全局最优解的局面，出现解的退化现象.因此次优蛙的改进策略如下:首先，选择每个子种群中的次优蛙在小概率事件时出现变异;其次，让其以自身所在的位置为中心，以到该种群中最优蛙的距离作为最大半径进行全方位的搜索，若适应度值无变化，则需要在种群中最优蛙邻域范围内产生一个新解，方式是采用随机的方法［6，8］.其中，次优蛙的变异公式如式(11)所示.其中，Xg'为每组次优蛙变异完后的候选解，rmax为自身到本组最优蛙之间的最大半径，θ为(0，360°)之间的随机数.4 仿真研究为了实现对算法的有效性的进一步验证，将该文提出的改进蛙跳算法与人工库存匹配的排序搜索(largest first fit，LFF)规则进行比较，具体比较结果如下.根据上文提出的LFF算法对应的规则以及两种算法实际执行过程中的策略，将其与该文提出的改进蛙跳算法进行了对比实验，实验结果见表1.针对磁性材料实际现场的中等规模问题，以计算时间、“以好充次”的比例和最终匹配的生产订单总重量等三个作为评价指标的具体数值实验结果.表1 100桶微粉20个生产订单的仿真结果算法计算时间/s“以好充次”比例/%匹配生产订单总重量/t改进的蛙跳算法＜1 10 2.34 LFF规则+策略A ＜1 25 images/BZ_173_1817_2059_1819_2061.png2.56 LFF规则+策略B ＜1 0 2.12 通过上面的仿真实验可以得到以下的比较结果:(1)与“LFF规则+策略A”的算法相比，该文提出的改进蛙跳算法虽然在匹配生产订单总重量方面略差，但是在库存微粉“以好充次”的比例方面有着非常大的优势，说明了算法的有效性.(2)与“LFF规则+策略B”的算法相比，该文提出的改进蛙跳算法仅仅用少量的库存微粉“以好充次”为代价，便获得了在匹配生产订单总重量方面非常好的效果，说明了算法的有效性.(3)在计算时间方面，该文提出的改进蛙跳算法较LFF规则的算法略高.但是根据该实验的仿真结果，该文提出算法的计算时间也在可接受的范围内，算法的效率是完全满足实际现场要求的.5 结束语该文从基本混洗蛙跳算法的原理出发分析了其存在的问题，进而有针对性地提出了相关的改进策略;使得该文提出的混洗蛙跳算法能以更加接近生产实际的方式实现磁性材料库存匹配问题的求解.通过该文仿真结果可以看出，改进后的混洗蛙跳算法优化精度高、收敛速度快、适应性和鲁棒性强，并有效克服了原算法早熟、易陷入局部最优的缺陷，并且可以在较短的时间内解决较大规模的生产订单库存匹配问题，并获得完全满足实际现场要求的可行解.参考文献［1］Rajagopalan S.Make to order or make to stock:Model and application ［J］.Management Science，2002，48(2):241–256.［2］Tnunbo M，Kalagnanam J，Lee H.IBM Research Report:A Solution Architecture for Inventory Application Problems in the SteelIndustry.Unpublished Results，1998.［3］Pisinger D.An Exact Algorithm for Large Multiple Knapsack Problems.European Journal of Operational Research，1999，114(3):528–541.［4］Martello S，Toth P.Knapsack Problems:Algorithms and Computer Implementations.Wiley，Chichester U K，1990.［5］Pan Q K，Wang L，Gao L，et al.An effective shuffled frogleaping algorithm for lot－streaming flow shop scheduling problem［J］.Int J of Advanced Manufacturing Technology，2011，52(5/6/7/8):699－713. ［6］Rahimi－Vahed A，Mirzaei AH.A hybrid multi－objective shuffled frog－leaping algorithm for a mixed－model assembly line sequencing puters and Industrial Engineering，2007，53(4):642–66. ［7］王介生，高宪文.基于改进混合蛙跳算法的电渣重熔过程多变量 PID控制器设计［J］.控制与决策，2011，26(11):1731－1734.［8］Huynh T H.A modified shuffled frog leaping algorithm for optimal tuning of multivariable PID controllers［C］.IEEE Int Conf on Industrial Technology.Perth:IEEE Press，2008.1–6.。

基于精英策略改进的混合蛙跳算法
江泽昌;刘天羽;吴星;王义东
【期刊名称】《上海电机学院学报》
【年(卷),期】2018(021)001
【摘要】针对蛙跳算法(SFLA)在后期收敛速度慢和易于陷入局部收敛的问题,研究一种改进的混合SFLA.采用精英策略对局部子群的最差青蛙进行更新,使其既向最优青蛙学习,也向周围其他较好的青蛙学习;引入Minkowski距离使全局最优青蛙向局部最优青蛙和局部进化较好的青蛙学习,提高了全局最优青蛙的质量;利用柯西变异分子避免算法陷入局部最优.选取典型测试函数进行仿真实验验证,结果表明,改进后算法是有效的且高效的.对改进后的SFLA进行收敛性分析.
【总页数】6页(P14-19)
【作者】江泽昌;刘天羽;吴星;王义东
【作者单位】上海电机学院电气学院,上海201306;上海电机学院电气学院,上海201306;上海电机学院电气学院,上海201306;上海电机学院电气学院,上海201306
【正文语种】中文
【中图分类】TP18
【相关文献】
1.基于阈值选择策略的改进混合蛙跳算法在电网规划中的应用 [J], 王茜;张粒子;舒隽;王楠
2.基于改进混合蛙跳算法的网格任务调度策略 [J], 欧阳;孙元姝
3.一种基于阈值选择策略的改进混合蛙跳算法 [J], 李英海;周建中;杨俊杰;刘力
4.基于精英保留策略与爆炸算子的改进遗传算法 [J], 罗凤鸣;吕方林;侯宗琰
5.基于改进精英策略的PCA-NSGAⅡ的高维目标调度优化 [J], 刘琼;熊书平;湛梦梦
因版权原因，仅展示原文概要，查看原文内容请购买。

基于自适应变异因子策略的混合蛙跳算法赵付青;陈自豪【摘要】由于基本混合蛙跳算法在对问题的优化求解中存在着收敛速度慢、优化精度低且容易陷入局部最优等问题,因此提出了一种新的混合蛙跳算法.对基本混合蛙跳算法的组内更新策略进行重新设计,引入自适应变异因子来控制青蛙的移动步长;在算法中将改进的粒子群优化算法有机地嵌入其中,这样算法在搜索过程中就增加了发现新解的概率,维持了种群的多样性,从而使算法不易陷入局部最优.通过对标准函数进行优化测试,结果证明其具有良好的优化性能.【期刊名称】《甘肃科学学报》【年(卷),期】2016(028)001【总页数】6页(P6-11)【关键词】混合蛙跳算法;自适应变异因子;移动步长;粒子群优化算法【作者】赵付青;陈自豪【作者单位】兰州理工大学计算机与通信学院,甘肃兰州 730050;西北工业大学现代设计与集制造技术教育部重点实验室,陕西西安710072;兰州理工大学计算机与通信学院,甘肃兰州 730050【正文语种】中文【中图分类】TP391混合蛙跳算法(SFLA,shuffled frog leaping algorithm)是2003年由Eusuff和Lansey提出的一种基于群体智能的生物进化算法[1]。

它具有参数少、概念简单、计算速度快、全局寻优能力强及易于实现等特点。

目前该算法在改进和应用方面都得到了相应提高,并且利用它解决了许多实际优化问题,如函数优化、水资源网络分配问题、成品油管网优化设计、车间调度问题、旅行商问题等[2-4]。

然而它还是存在着许多缺点,如收敛速度较慢、优化精度相对低、易陷入局部最优等,尤其在解决高维函数问题时,这些缺点表现的更明显,从而算法的效率非常低。

因此改进基本混合蛙跳算法,提高算法性能就变得非常急切。

目前,研究者们用不同的方法对算法的各个过程进行改进。

文献[5-10]中介绍了国内和国外学者们对基本混合算法进行的改进,确实提高了算法的优化性能。

改进蛙跳算法的约束处理方法
王金阳;郭承军;黄曼娜
【期刊名称】《仲恺农业工程学院学报》
【年(卷),期】2017(030)001
【摘要】提出了一种用于求解有约束优化问题的混合蛙跳算法.蛙跳算法结合E-差分进化算法(E-differential evolution algorithm,E-DE),可使算法在进化过程中充分利用种群中不可行解的信息.在进化初始阶段,可行域边界上拥有较优目标函数的不可行解进入种群,随着进化代数增加,种群约束允许放松程度不断减小,使得种群中不可行解数量减少,直到种群约束允许放松程度为0,此时种群完全由可行解组成.改进后的蛙跳算法能够提高收敛速度和精度.13个标准Benchmark函数仿真试验的结果表明,改进后的蛙跳算法寻优精度高,鲁棒性强,是一种有效的求解有约束优化问题的算法.
【总页数】5页(P48-52)
【作者】王金阳;郭承军;黄曼娜
【作者单位】广东工业大学应用数学学院,广东广州 510520;广东工业大学应用数学学院,广东广州 510520;广东工业大学应用数学学院,广东广州 510520【正文语种】中文
【中图分类】J653
【相关文献】
1.求解约束优化问题的自适应免疫混合蛙跳算法 [J], 潘学
2.新型蛙跳算法求解总能耗约束FJSP [J], YANG Dongjing;LEI Deming
3.基于改进的免疫克隆蛙跳算法的多约束QoS路由优化研究 [J], 卢毅; 徐梦颖; 周杰
4.求解约束优化问题的元胞混洗蛙跳算法及应用 [J], 张强;姜慧清;王颖;郭玉洁
5.基于改进混合蛙跳算法的多约束车辆路径优化 [J], 鲁建厦;翟文倩;李嘉丰;易文超;汤洪涛
因版权原因，仅展示原文概要，查看原文内容请购买。

【word】求解多背包问题的混合蛙跳算法求解多背包问题的混合蛙跳算法总第263期2011年第9期计算机与数字工程Computer&DigitalEngineeringVo1.39No.913求解多背包问题的混合蛙跳算法马竹根”舒少华.(怀化学院计算机科学与技术系”怀化418008)(中方县职业中等专业学校怀化418000)摘要针对多背包问题,提出一种改进的离散混合蛙跳算法.算法中对青蛙个体采用十进制整数编码方式,应用遗传算法中的交叉操作来对个体进行更新,扩展了传统混合蛙跳算法模型.将改进的算法用于多背包问题求解,仿真实验表明了所提算法的有效性.关键词混合蛙跳算法;多背包问题;组合优化;交叉算子中图分类号TP301.6ShuffledFrogLeapingAlgorithmforSolvingMultipleKnapsackProblemMaZhugenShuShaohua.(DepartmentofComputerScienceandTechnology,HuaihuaUniversity”,Huaihu a418008)(SpecializedSchoolofZhongfangCountryVocationalSencondarf,Huaihua4180 08)AbstractADiscreteShuffledFrogLeapingAlgorithmisproposedtosolvetheMul tipleKnapsackProblem.Thealgo—rithmadoptsintegercodedschemeandanewmethodofindividualproductionbycr ossoveroperationtOextendthetraditionalmodelofShuffledFrogLeapingAlgorithm.Theexperimentalresultsshowthatth eproposedalgorithmiseffectiveandef—fient.KeyWordsshuffledfrogleapingalgorithm(SFLA),multipleknapsackproblem(M KP),combinatorialoptimization,crossoveroperationClassNumberTP301.61引言多背包问题(MultipleKnapsackProblem,MKP)是一个经典的组合优化问题,在现实生活中有着广泛的应用,如资源分配,投资决策,货物装载等均可建模为多背包问题.因此,多背包问题的求解一直以来是人们关注的一个研究热点,目前已经提出了如精确算法[1],动态规划法[2],启发式算法[引,遗传算法[,蚁群算法[引,人工鱼群算法[.]等多种求解方法.由于精确求解的时间复杂度大,所以精确算法仅能适用于小规模的MKP.基于生物进化和仿生的遗传算法,蚁群算法,人工鱼群算法等,由于具有自组织性,鲁棒性好,易于获得全局解等特点,在求解大规模组合优化问题中应用越来越广泛.混合蛙跳算法[](ShuffledFrogLeapingA1一gorithm,以下简称SFIA)是一种新型仿生群体智能优化算法,它结合了基于基因进化的模因演算法(MemeticAlgorithm,MA)和基于群体行为的粒子群算法(ParticleSwarmOptimization,PSO)两者的优hE,具有概念简单,参数少,计算速度快,全局寻优能力强,易于实现的特点,在资源分配,车间作业流程安排,旅行商问题[,0-1背包问题[1n]等工程实际问题中得到有效的应用.文献Elo]和文献[11]都是采用二进制编码对标准的0—1背包问题进行求解.本文针对多维背包问题,采用十进*收稿日期:2011年3月15日,修回日期:2011年4月28日作者简介:马竹根,男,讲师,研究方向:人工智能,软件工程. 马竹根等:求解多背包问题的混合蛙跳算法第39卷制整数编码方式,应用遗传算法中的交叉操作对个体进行更新,提出一种求解多维背包问题的离散混合蛙跳算法,在具体实例上的实验结果表明该算法对解决多维背包问题是行之有效的.2多背包问题数学模型多背包问题是指在一个物品集合N一{1,2,…,n}中选出一个子集分别装入m个背包中,在不超出每个包的限制容量6,的条件下,使选出的全部物品的总价值最大,其中?M,M一{1,2,…, m}.背包问题可形式化地描述为[6]:Max?CiX(1)f2aijzbiJ一1,2,…,m(2)满足.{?Nlz?{0,1}i一1,2,…,(3)其中:C表示物品i的价值a表示物品i放人背包所占的容量.式(2)表示背包约束,由于具有m个约束,多背包问题又被称为多维背包问题.在多背包问题中,除了确定每个物体是否装入背包外, 还需要确定它将装入哪个背包.显然对于多背包问题的优化会比背包问题复杂得多,它是一个NP一完全问题.3混合蛙跳算法混合蛙跳算法是模拟青蛙觅食过程中信息共享和交流的特点而提出的一种仿生算法.在SF—LA中,种群(解集)由一群具有相同结构的青蛙组成,每只青蛙代表一个解.种群被分成多个族群, 不同的族群被认为是具有不同思想和行为方式的青蛙的集合,不同的族群之间能够相互影响.在每个族群内以更新最差蛙为策略,按照预先定义的局部更新迭代次数进行更新,当所有族群内最差蛙完成局部更新后,各个族群间进行思想交流实现族群间的混合,重新产生新的族群.局部搜索和混合过程一直持续到满足收敛条件或达到最大迭代次数为止.具体来说,SFLA可分成以下步骤:1)初始化种群:随机生成P只青蛙组成初始种群,第i只青蛙表示问题的解为X===(,.27 …,),其中s为解空间的维数,即变量的个数.2)划分族群:将所有青蛙按照它们的适应值降序排列,然后将整个种群分成m个族群,每个族群包含n只蛙,要求满足P=mXn.在迭代过程中第一只蛙分人第一个族群,第二只蛙分人第二个族群,一直分配下去,直到第m只蛙分人第rn个族群.然后第+1只蛙分人第一个族群,第m+2只蛙分入第二个族群,依此类推,直到所有青蛙分配完毕. 3)族群进化:在每个族群中,用和X分别表示该族群中适应值最好和最差的青蛙,用X表示整个种群中最好的青蛙.然后对每个族群进行局部深度搜索,即对每个族群中的最差蛙按下式进行更新操作:D===rand()*(X一)(4)新的位置Xne-u2~一X(当前位置)+D,(DD三三=一D)(5)式中rand()是0,l之间的随机数,D表示青蛙所允许改变位置的最大值.如果这个过程能够产生一个较好解,那么就用新位置青蛙取代最差蛙; 如果没有改进,则用X代替X重复执行式(4)和式(5);如果仍没有改进,则在可行域中随机产生一个新解取代原来最差青蛙X.重复这种更新操作,直到达到设定的局部搜索迭代次数.4)混合:当所有族群的局部搜索完成后,将所有族群内的青蛙重新混合并排序,重复执行第2步和第3步直到满足终止条件,输出全局最优解.4离散混合蛙跳算法求解多背包问题在蛙跳算法中,相关参数大部分属于连续实数域,因此蛙跳算法主要适用于求解连续空间域的优化问题,难于直接处理离散的组合优化问题.在分析传统蛙跳算法优化机理的基础上,本文采用了整数编码方式和新的个体更新策略,提出一种解决多背包问题的离散蛙跳算法.4.1蛙体结构的编码和解性能评价设计蛙跳算法首先要建立个体矢量与问题域之间的映射关系.在蛙跳算法中,一只青蛙对应所求问题的一个解.设有n个物品m个背包,将n个物品按顺序组成一向量X一(z,35z,…,)表示青蛙个体,其中.?{0,1,…,n},i一1,2,…,n.===表示将第i个物品放人第m个背包,.27一0表示第i个物品不放入任何背包.例如,X===(2,3,1,0, 0,0,2,3,3,2,0,1,0,1,1)表示15个物品中,第3, 12,14,l5个物品放人第1个背包,第1,7,10个物品放人第2个背包,第2,8,9个物品放人第3个背包,第4,5,6,11,13个物品不放入任何背包.另外,以背包价值F(x)作为衡量个体X性能指标,F(x)一CiJC,其中各分量含义同式(1).iEN显然F(X)的值越大,表示解的性能越好.。

求解TSP的改进混合蛙跳算法
骆剑平;李霞
【期刊名称】《深圳大学学报（理工版）》
【年(卷),期】2010(027)002
【摘要】重新定义表示青蛙移动距离和位置的数据结构及运算符意义,提出混合蛙跳算法(shuffled frog leaping algorithm,SFLA)求解旅行商问题(traveling salesman problem,TSP)基于交换序的实现方法.把具有极强局部搜索能力的幂律极值动力学优化(power law extremal optimization,T-EO)融合于SFLA,并针对TSP对T-EO过程进行设计和改进.改进后的T-EO采用新颖的组元适应度计算方法,通过定义边置换增益能量,结合模拟退火控制过程,并采取幂律定律用概率的方式选取2-opt置换产生邻域解.为避免每个族群最优解的趋同性,提出最优样本差异控制策略.通过求解TSPLIB数据库中的实例,证明该改进算法有效.
【总页数】7页(P173-179)
【作者】骆剑平;李霞
【作者单位】深圳大学信息工程学院,深圳,518060;深圳大学信息工程学院,深圳,518060
【正文语种】中文
【中图分类】TP181;TP183
【相关文献】
1.改进的连续Hopfield网络求解组合优化问题——以TSP求解为例 [J], 邱树伟
2.混合蛙跳算法求解TSP问题 [J], 王园嫒;司畅
3.求解TSP问题的改进混合蛙跳算法 [J], 张敬敏;马丽;李媛媛
4.混合蛙跳算法改进及其对旅行商问题的求解 [J], 李俊
5.混合蛙跳算法改进及其对旅行商问题的求解 [J], 李俊
因版权原因，仅展示原文概要，查看原文内容请购买。

混合蛙跳算法基本原理
嘿，朋友们！今天咱们来聊聊超有意思的混合蛙跳算法的基本原理！
你想想啊，就好比一群青蛙在一个大大的池塘里蹦跶（这就像算法中各种可能的解）。

它们有的蹦得远，有的蹦得近，但是它们都在努力寻找最好的位置。

混合蛙跳算法呢，就是让这些青蛙们分成小组（可以类比为不同的解集群）。

每个小组里的青蛙们会一起交流，互相学习，然后各自根据学到的东西蹦一蹦（调整解）。

比如说，有一只青蛙发现旁边那只蹦得挺不错，它就会跟人家学学，也试着往那个方向多蹦一点。

然后呢，各个小组之间还会交换信息（这就像是不同解集群之间的交互）！哎呀，这多棒啊！这样就可以让大家都能知道其他小组找到的好地方，都朝着更好的方向去努力。

就好像一群小伙伴一起玩游戏，互相分享经验，然后一起进步！
那这个算法到底有啥用呢？这么说吧，假如你要规划一条最优的物流路线，那它就能帮你找到最合适的那条路，能省好多时间和成本呢！这不就像你找路的时候有人给你指了一条明路一样吗？
再比如，在设计一个复杂的系统时，它能让你快速找到最佳的参数组合。

这不就相当于有个超级聪明的助手帮你把一切都安排得妥妥当当嘛！
我觉得混合蛙跳算法真的太神奇了，就像给我们打开了一扇通往高效解决问题的大门。

它让我们能在各种复杂的情况下都能找到最好的办法，难道不是很了不起吗？朋友们，你们说呢！
观点结论：混合蛙跳算法是一种非常有创意和实用的算法，能帮助我们高效地解决各种问题，具有很大的价值和潜力。

基于改进混合蛙跳算法的在轨服务飞行器任务分配
孔凡光;何建华;唐奎
【期刊名称】《计算机测量与控制》
【年(卷),期】2013(21)4
【摘要】针对飞行器在轨服务任务分配问题,提出了一种基于改进混合蛙跳算法的任务分配方法；以飞行器服务优先级、能量消耗等指标为准则建立在轨服务任务分配数学模型；在改进的混合蛙跳算法中,为提高算法工作效率,采用特殊的青蛙粒子更新方式,为提高算法搜索深度,将自适应差分扰动机制引入算法局部搜索中,为避免族群最优解的趋同性,采用幂律定律选择变异单元对族群最优个体进行变异操作,最后通过Matlab对不同规模的任务分配进行仿真,证明该方法能够快速有效地给出合理的目标分配方案.
【总页数】4页(P1035-1038)
【作者】孔凡光;何建华;唐奎
【作者单位】西北工业大学电子信息学院,西安 710129;西北工业大学电子信息学院,西安 710129;西北工业大学电子信息学院,西安 710129
【正文语种】中文
【中图分类】TP18;V27
【相关文献】
1.基于改进层次分析法的在轨服务飞行器机动策略评估 [J], 李岩;蔡远文;辛朝军
2.基于离散粒子群算法的多飞行器在轨服务任务分配 [J], 张琪新;孙富春;许斌;刘
华平
3.基于离散粒子群算法的航天器在轨服务任务分配问题研究 [J], 张琪新;孙富春;叶文;闵海波
4.基于混合蛙跳算法的异地分布式协同开发的任务分配优化 [J], 周聪;姜继娇;殷茗
5.基于改进混合蛙跳算法的多约束车辆路径优化 [J], 鲁建厦;翟文倩;李嘉丰;易文超;汤洪涛
因版权原因，仅展示原文概要，查看原文内容请购买。

混合蛙跳算法自适应参数调整改进策略肖莹莹;林廷宇;李伯虎;侯宝存;施国强【期刊名称】《系统工程与电子技术》【年(卷),期】2016(038)008【摘要】针对基本混合蛙跳算法(shuffled frog leaping algorithm,SFL)在求解高维复杂问题时的不足,本文提出一种自适应参数调整的改进策略.首先,利用变公比数列分析了SFL更新轨迹的收敛性;在此基础上,利用系统稳定性分析方法,提出在SFL 更新公式中基于比例系数和适应度标准差来自适应调整更新的方法.最后,基于3组共8个标准测试函数将本文改进SFL与基本SFL和4个改进型粒子群优化算法(particle swarm optimization,PSO)作对比,验证了本文改进策略对各类复杂函数的高效性;同时,对比了改进SFL与基本SFL和wPSO在求解高维问题时的性能,验证了改进SFL对高维问题求解的有效性.【总页数】12页(P1939-1950)【作者】肖莹莹;林廷宇;李伯虎;侯宝存;施国强【作者单位】北京市复杂产品先进制造系统工程技术研究中心,北京仿真中心,北京100854;复杂产品智能制造系统技术国家重点实验室,北京电子工程总体研究所,北京100854;北京市复杂产品先进制造系统工程技术研究中心,北京仿真中心,北京100854;复杂产品智能制造系统技术国家重点实验室,北京电子工程总体研究所,北京100854;复杂产品智能制造系统技术国家重点实验室,北京电子工程总体研究所,北京100854;航天系统仿真重点实验室,北京仿真中心,北京100854;北京市复杂产品先进制造系统工程技术研究中心,北京仿真中心,北京100854;复杂产品智能制造系统技术国家重点实验室,北京电子工程总体研究所,北京100854;航天系统仿真重点实验室,北京仿真中心,北京100854;北京市复杂产品先进制造系统工程技术研究中心,北京仿真中心,北京100854;复杂产品智能制造系统技术国家重点实验室,北京电子工程总体研究所,北京100854;航天系统仿真重点实验室,北京仿真中心,北京100854【正文语种】中文【中图分类】TP391【相关文献】1.无线局域网 EDCA 机制的一种自适应参数调整改进算法 [J], 朱智平;万福2.基于自适应参数调整的航空电源车电力稳定控制方法 [J], 马建忠3.基于自适应参数调整的航空电源车电力稳定控制方法 [J], 马建忠4.应用遗传算法的认知无线电自适应参数调整 [J], 赵知劲;郑仕链;邢国际;尚俊娜5.模糊自适应参数调整的改进遗传算法 [J], 罗梅;贾志娟因版权原因，仅展示原文概要，查看原文内容请购买。

基于改进混合蛙跳算法的贴片机贴装顺序优化
朱光宇;林蔚清
【期刊名称】《中国工程机械学报》
【年(卷),期】2008(006)004
【摘要】元器件贴装顺序是影响贴片机工作效率的关键因素之一.针对拱架型贴片机,在建立贴装顺序数学模型基础上,采用改进混合蛙跳算法对贴装顺序进行优化,按照三角概率分布选择可能被改进蛙的策略,完成对基本混合蛙跳算法的改进.最后以3块PCB为例进行实验,实验结果表明,算法可以有效解决元件贴装顺序问题,并具有比基因遗传算法更高的准确性及效率.
【总页数】5页(P428-432)
【作者】朱光宇;林蔚清
【作者单位】福州大学,机械工程及自动化学院,福建,福州,350002;福州大学,机械工程及自动化学院,福建,福州,350002
【正文语种】中文
【中图分类】TP391.73
【相关文献】
1.基于MMAS的贴片机元件贴装顺序优化 [J], 徐丽莉;刘文杰;严震宇;吴秉羲
2.应用于贴片机贴装顺序优化的遗传算法的比较和改进 [J], 罗爱玲;龙绪明
3.基于改进蚁群算法的垂直旋转式贴片机贴装顺序优化 [J], 付永忠;潘云峰
4.基于蚁群–混合蛙跳算法的贴片机贴装顺序优化 [J], 陈铁梅;罗家祥;胡跃明
5.基于RLS的用于贴片机贴装顺序优化的禁忌搜索算法 [J], 罗家祥;罗树浩;吴忻生
因版权原因，仅展示原文概要，查看原文内容请购买。

蛙跳算法的改进及应用
叶晶晶;郭承军;冯国明
【期刊名称】《数学学习与研究：教研版》
【年(卷),期】2016(000)001
【摘要】通过对传统的蛙跳算法分析得出其收敛速度有待提升,并且较易出现局部最优的情况,通过改进得到新的算法,并将新算法结合实际问题进行应用,并取得了好的效果.
【总页数】1页(P68-68)
【作者】叶晶晶;郭承军;冯国明
【作者单位】广东工业大学应用数学学院,广东广州510520
【正文语种】中文
【中图分类】TP301.6
【相关文献】
1.改进的混合蛙跳算法及其在多阈值图像分割中的应用
2.一种改进的混合蛙跳算法及其在变压器设计中的应用
3.改进型蛙跳萤火虫算法及其在CRN频谱分配中的应用
4.改进型蛙跳萤火虫算法及其在CRN频谱分配中的应用
5.改进混合蛙跳算法在马斯京根模型参数优化中的应用
因版权原因，仅展示原文概要，查看原文内容请购买。

蛙跳算法-详解目录• 1 什么是蛙跳算法• 2 蛙跳算法的原理• 3 蛙跳原理的特点• 4 蛙跳原理的数学模型什么是蛙跳算法蛙跳算法是一种全新的启发式群体进化算法，具有高效的计算性能和优良的全局搜索能力。

对混合蛙跳算法的基本原理进行了阐述，针对算法局部更新策略引起的更新操作前后个体空间位置变化较大，降低收敛速度这一问题，提出了一种基于阈值选择策略的改进蛙跳算法。

通过不满足阈值条件的个体分量不予更新的策略，减小了个体空间差异，从而改善了算法的性能。

数值实验证明了该改进算法的有效性，并对改进算法的阈值参数进行了率定。

蛙跳算法的原理蛙跳算法的思想是：在一片湿地中生活着一群青蛙。

湿地内离散的分布着许多石头，青蛙通过寻找不同的石头进行跳跃去找到食物较多的地方。

每只青蛙个体之间通过文化的交流实现信息的交换。

每只青蛙都具有自己的文化。

每只青蛙的文化被定义为问题的一个解。

湿地的整个青蛙群体被分为不同的子群体，每个子群体有着自己的文化，执行局部搜索策略。

在子群体中的每个个体有着自己的文化，并且影响着其他个体，也受其他个体的影响，并随着子群体的进化而进化。

当子群体进化到一定阶段以后，各个子群体之间再进行思想的交流（全局信息交换）实现子群体间的混合运算，一直到所设置的条件满足为止。

蛙跳原理的特点蛙跳原理是由Eusuff和Lansey为解决组合优化问题于2003年最先提出。

作为一种新型的仿生物学智能优化算法，SFLA 结合了基于模因（meme）进化的模因演算法（MA，memeticalgorithm）和基于群体行为的粒子群算法（PSO,particle swarm optimization）2 种群智能优化算法的优点。

该算法具有概念简单，调整的参数少，计算速度快，全局搜索寻优能力强，易于实现的特点。

混合蛙跳算法主要应用于解决多目标优化问题，例如水资源分配、桥墩维修、车间作业流程安排等工程实际应用问题。

蛙跳原理的数学模型算法参数与其他优化算法一样，SFLA亦具有一些必要的计算参数，包括F：蛙群的数量；m：族群的数量；n：族群中青蛙的数量；Smax：最大允许跳动步长；Px：全局最好解；Pb：局部最好解；Pw：局部最差解；q：子族群中青蛙的数量；LS：局部元进化次数以及SF：全局思想交流次数等。

基于改进混合蛙跳算法的软测量建模方法张孙力;杨慧中【期刊名称】《南京理工大学学报（自然科学版）》【年(卷),期】2017(041)002【摘要】针对混合蛙跳算法的寻优机制在寻优过程中易陷入局部最优和收敛效果不理想的问题,该文提出一种改进的混合蛙跳算法.该算法在更新群中最差个体时同步更新最优个体.更新最差个体步长时引入上一次的移动步长并赋予动态权值.改进算法舍弃了原算法中用随机值代替最差值的做法,引入高斯变异算子对最差个体进行高斯变异,使种群进化更趋合理.将改进的混合蛙跳算法运用到模糊C均值聚类算法的聚类中心优化中,得到最优的聚类中心.利用该聚类中心对样本进行模糊C均值聚类,并用高斯过程回归对各类样本子集分别建立对应的子模型,通过加权得到系统输出.以双酚A生产过程结晶单元为例进行仿真,对装置出口处的苯酚浓度进行软测量建模,获得了较好的实验结果.%In order to solve the problem that the optimization mechanism of the shuffled frog leaping adgorithm(SFLA)is easily falling into the local optimum during the optimization process and the convergence result is unsatisfactory,an improved shuffled frog leaping algorithm(ISFLA)is proposed here.The worst individual and the best individual among subgroups are updated simultaneously.The last moving step-length with the dynamic weight is applied to update the worst individual step-length and makes the population evolution more rational after the Gaussian mutation operator is used on the worst individual instead of the original random mutation operator.The optimal clusteringresult is calculated with the application of the ISFLA in the optimization of clustering centers by using the fuzzy C-means clustering algorithm.The clustering centers are optimized by the fuzzy C-means clustering algorithm.In addition,the final result is outputted by weighted Gaussian sub-models towards different categories.A sample of the crystallization unit of a bisphenol-A production is applied to make a simulation,and the soft-sensor model of the phenol concentration is built at the exit device with a good experiment result.【总页数】8页(P173-180)【作者】张孙力;杨慧中【作者单位】江南大学教育部轻工过程先进控制重点实验室,江苏无锡 214122;江南大学教育部轻工过程先进控制重点实验室,江苏无锡 214122【正文语种】中文【中图分类】TP274【相关文献】1.基于改进BP方法的精炼炉电压和电流软测量建模 [J], 张艳芬;肖东2.一种基于改进扩张搜索聚类算法的软测量建模方法 [J], 张孙力;杨慧中3.基于混合蛙跳算法的极限学习机软测量建模 [J], 孙顺远;周乾4.基于改进的DeepESN软测量建模方法及应用 [J], 岳文琦5.基于模型迁移的磨矿过程混合蛙跳算法-小波神经网络软测量建模及重构 [J], 王介生;杨阳;孙世峰因版权原因，仅展示原文概要，查看原文内容请购买。

摘要随机蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA)是进化计算领域中一种新兴、有效的亚启发式种群算法，它的基本思想来源于文化基因传承，其显著特点是具有局部搜索与全局信息混合的协同搜索策略，寻优能力强，易于编程实现，由Eusuff 和Lansey于2003年正式提出，近几年来逐渐受到学术界和工程优化领域的关注。

本文从蛙跳算法的基本概念开始，分析算法的工作过程总结其基本原理与算法流程，然后对其关键参数进行说明并采用测试函数测试，最后将蛙跳算法应用于解决0-1背包问题，并与相关文献的结果进行对比，验证了算法解决此类问题的可行性。

关键词：蛙跳算法，函数优化，背包问题ABSTRACTShuffled Frog Leaping Algorithm (SFLA) is an emerging effective sub-heuristic in the field of evolutionary computation. Its basic idea comes from the cultural genetic inheritanee and notable feature is a collaborative search strategy that is a mixture of local search and global information. SFLA has strong local search and global search ability, so it is good at searchi ng for the best and is easy to be programmed ・ It is raised formally by Eusuff and Lansey in 2003 and become gradually popular the field of academic and optimization in recent years・Firstly, this paper describes the concept of SFLA, and summarizes its basic principle・ Then, we draw the flowsheet, describe the key parameters and verify the algorithm by use of the test function. At last, we solve problems about the application on packing bags and prove its feasibility・Key words：Shuffled Leaping Frog Algorithm, Function optimization ,Knapsack problem第一章绪论 (4)1.1选题意义及研究背景 (4)1.2国外研究现状 (5)1.3论文研究的容 (7)1.4论文章节安排 (7)第二章蛙跳算法的基本理论 (8)2.1蛙跳算法概述 (8)2.2蛙跳算法原理 (8)2.2.1蛙跳算法的基本原理描述 (8)2.2.2蛙跳算法的步骤 (8)2.2.3算法流程图 (10)2.3蛙跳算法的组成要素 (12)2. 3. 1 蛙群(Population) (12)2. 3. 2 族群(Memeplex) (12)2. 3. 3 子族群(Sub-memeplex) (12)2.3.4蛙跳算法的参数 (13)第三章蛙跳算法在函数优化问题上的应用 (14)3.1测试函数 (14)3.2仿真测试 (14)第四章蛙跳算法在0-1背包问题上的应用 (19)4.1背包问题数学模型 (19)4.2蛙跳算法求解0-1背包问题 (20)4.2. 1青蛙的表示 (20)4.2.2子族群的构造： (20)4.2.3青蛙个体的构造策略： (20)4.2.4算法步骤 (21)4.3仿真实验 (21)第五章总结 (24)5.1本文的主要工作 (24)5. 2展望 (24)【参考文献】 (25)致 (26)第一章绪论1.1选題意义及研究背景当科技在进步的同时，工程实践中遇到的问题也越来越多，面临的困难也越来越大，使用传统的计算方法会出现诸多弊端，由于在实际工程中问题的规模较大且建模困难，寻找一种适合于求解大规模问题的并行算法已成为有关学科的主要研究目标⑴，于是一系列具有启发式特征及并行高效性能的智能优化算法产生了。

模因内三角概率选择混合蛙跳算法朱光宇【期刊名称】《计算机集成制造系统》【年(卷),期】2009(015)010【摘要】为优化拱架型多头贴片机贴装顺序,建立了贴装顺序数学模型.按照三角概率分布选择多只蛙实现模因进化的策略,改进混合蛙跳算法,构建模因内三角概率选择混合蛙跳算法,解决了贴装顺序优化问题.实验表明,新算法具有比混合蛙跳算法更高的收敛率,比基因遗传算法具有更好的准确性及更高的收敛率,有效解决了贴装顺序优化问题.通过算法参数分析得出,随着蛙群个体数量的增加,算法能够得到更优解;模因组数对算法的影响小于蛙群的个体数量;对应不同蛙群的个体数量,有一个与之对应的模因组数,使算法相对稳定.%To optimize the component placement sequence of gantry surface mounting machine, a mathematical model of component sequence was established, and the triangular probability distribution shuffled frog-leaping algorithm was proposed with the strategy of selecting several frogs for meme evolution. These frogs were selected according to triangular probability distribution. The presented algorithm was used to resolve the optimization problem of component placement sequence. Experiment results indicated that the improved algorithm outperformed shuffled frog-leaping algorithm in convergence ratio and Genetic Algorithm(GA) in accuracy and convergence ratio. Known from parameter analysis that better solution could be obtained when the frog population number increased and the effect of memeplex numberwas weaker comparing to frog population number. There was a memeplex number corresponding to different frog population number which ensured the algorithm to be comparatively stable.【总页数】7页(P1979-1985)【作者】朱光宇【作者单位】福州大学,机械工程及自动化学院,福建,福州,350002【正文语种】中文【中图分类】TP391【相关文献】1.形式三角矩阵环上的广义内射模 [J], 范维丽;刘仲奎2.形式三角矩阵环上的PC-内射模 [J], 夏国利;王芳贵;蒲永燕3.基于混合蛙跳算法的概率积分模型参数反演 [J], 滕超群;王磊;魏鹏;李靖宇;江克贵;朱尚军4.基于混合蛙跳算法的概率积分模型参数反演 [J], 滕超群;王磊;魏鹏;李靖宇;江克贵;朱尚军5.模糊蕴涵算子及其构造(Ⅲ)——由三角模或余三角模构造的模糊蕴涵算子 [J], 尤飞;杨昔阳;李洪兴因版权原因，仅展示原文概要，查看原文内容请购买。