蛙跳算法的研究及应用.docx

蛙跳算法的研究及应用.docx摘要随机蛙跳算法(ShuffledFrogLeapingAlgorithm,SFLA)是进化计算领域中一种新兴、有效的亚启发式种群算法,它的基本思想来源于文化基因传承,其显著特点是具有局部搜索与全局信息混合的协同搜索策略,寻优能力强,易于编程实现,由Eusuff和Lansey于2003年正式提出,近几年来逐渐受到学术界和工程优化领域的关注。本文从蛙跳算法的基本概念开始,分析算法的工作过程总结其基本原理与算法流程,然后对其关键参数进行说明并采用测试函数测试,最后将蛙跳算法应用于解决0-1背包问题,并与相关文献的结果进行对比,验证了算法解决此类问题的可行性。关键词:蛙跳算法,函数优化,背包问题ABSTRACTShuffledFrogLeapingAlgorithm(SFLA)isanemergingeffectivesub-,,thispaperdescribestheconceptofSFLA,,wedrawtheflowsheet,,:ShuffledLeapingFrogAlgorithm,Functionoptimization,Knapsackproblem目录第一章绪论 3L1选题意义及研究背景 4笫二章蛙跳算法的基本理论 9蛙群(Population) 9族群(Memeplex) 9子族群(Sub-memeplex) 10第三章蛙跳算法在函数优化问题上的应用 11第四章蛙跳算法在0・1背包问题上的应用 164」背包问题数学模型 ・1背包问题 : 17423青蛙个体的构造策略: 18第五章总结 215」木文的主要工作 21【参考文献】 22致谢 ,工程实践中遇到的问题也越來越多,面临的困难也越來越大,使用传统的计算方法会出现诸多弊端,由于在实际工程中问题的规模较大且建模困难,寻找i种适合于求解大规模问题的并行算法已成为冇关学科的主要研究目标⑴,于是一系列具有启发式特征及并行高效性能的智能优化算法产生To这些算法思想多来白于大白然的生物或人类智慧,有些受生物群体行为的启发,冇些模拟生物的身体机能和生理构造,冇些模仿生物界的进化过程,冇些利用人的思维和记忆过程,最终实现在可接受的时间内找到令人满意的解。1975年,被称作是遗传算法奠基人Holland教授⑵收到门然生物种群进化机制的启发正式提出了遗传算法(icAlgorithms,GA),算法中群进化依据优胜劣汰、适者生存的原理进行选择、交叉和变异操作,产生更适应坏境的种群,直至寻得近似最优解。对于很多函数优化问题,组合优化问题,它都能够成功求解,传统计算方法无法解决的NP难问题,它也能有让人满意的效果,于是被大量推广。随即,1977年的禁忌搜索(TabuSearch,TS)>1983年的模拟退火(SimulatedAnnealingsA)算法被相继提出,这些算法为解决经典的NP完全问题或是一些新的复杂问题提供了新的思路和方法。20世纪90年代左右,受自然界中群居生活的动物、昆虫的启发,以粒子群算法(PartialSwarmOptimization,PSO)^