蛙跳算法的研究及应用

陕西师范大学毕业论文II陕西师范大学本科生毕业论文摘 要随机蛙跳算法(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 inheritance 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 searching 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目 录第一章 绪论11.1选题意义及研究背景11.2国内外研究现状21.3 论文研究的内容41.4 论文章节安排4第二章 蛙跳算法的基本理论52.1 蛙跳算法概述52.2 蛙跳算法原理52.2.1 蛙跳算法的基本原理描述52.2.2 蛙跳算法的步骤52.2.3 算法流程图72.3蛙跳算法的组成要素92.3.1 蛙群( Population)92.3.2族群(Memeplex)92.3.3 子族群（Sub-memeplex）92.3.4 蛙跳算法的参数10第三章 蛙跳算法在函数优化问题上的应用113.1 测试函数113.2 仿真测试11第四章 蛙跳算法在0-1背包问题上的应用164.1背包问题数学模型164.2蛙跳算法求解0-1背包问题174.2.1 青蛙的表示174.2.2子族群的构造：174.2.3青蛙个体的构造策略：174.2.4 算法步骤184.3 仿真实验18第五章 总结215.1 本文的主要工作215.2展望21【参考文献】22致 谢233第一章 绪论1.1选题意义及研究背景当科技在进步的同时，工程实践中遇到的问题也越来越多，面临的困难也越来越大，使用传统的计算方法会出现诸多弊端，由于在实际工程中问题的规模较大且建模困难，寻找一种适合于求解大规模问题的并行算法已成为有关学科的主要研究目标1 ,于是一系列具有启发式特征及并行高效性能的智能优化算法产生了。这些算法思想多来自于大自然的生物或人类智慧，有些受生物群体行为的启发，有些模拟生物的身体机能和生理构造，有些模仿生物界的进化过程，有些利用人的思维和记忆过程，最终实现在可接受的时间内找到令人满意的解。1975年，被称作是遗传算法奠基人Holland教授2 收到自然生物种群进化机制的启发正式提出了遗传算法（Genetic Algorithms，GA），算法中群进化依据优胜劣汰、适者生存的原理进行选择、交叉和变异操作，产生更适应环境的种群，直至寻得近似最优解。对于很多函数优化问题，组合优化问题，它都能够成功求解，传统计算方法无法解决的NP难问题，它也能有让人满意的效果，于是被大量推广。随即，1977年的禁忌搜索(Tabu Search，TS)、1983年的模拟退火（Simulated Annealing,SA）算法被相继提出，这些算法为解决经典的NP完全问题或是一些新的复杂问题提供了新的思路和方法。 20世纪90年代左右，受自然界中群居生活的动物、昆虫的启发，以粒子群算法（Partial Swarm Optimization，PSO）、蚁群算法（Ant Colony Optimization，ACO）等为代表的群智能算法出现了，它是人工智能的一个重要的分支，作为新兴的演化计算方法已经受到越来越多的国内外研究人员的关注。群体智能体现在由大量简单的个体所组成的群体，能够完成复杂个体的任务，并且其性能上更具优势，靠的是个体间的合作与竞争来指导优化搜索。模拟自然界中生物群体行为来构造随机的优化算法是它的基本思想，相互协作和作用是其重要的因素。2000年一种新的群智能算法蛙跳算法（Shuffled Frog Leaping Algorithm,SFLA）产生了，它是由两位美国学者Eusuff和Lansey3提出的，最初应用于分布系统设计优化问题，并成功求解。它原理清晰、简单易理解、优化参数少、求解问题能力优越。SFLA的执行过程模拟了一群青蛙（解）在一片湿地上（解空间）中跳动觅食的行为。（如图（1.1）所示）： 图1.1 基本随机蛙跳算法基本思想示意图每一只青蛙在觅食行为中被看作元或思想的载体，每只青蛙可以与其他青蛙交流思想并且可以通过传递信息的方式来改进其他蛙的元信息，这些信息可以通过诸如模仿等行为在蛙脑中行进传递。在算法执行初期，一群蛙被分为多个族群，不同的族群被认为是具有不同思想的青蛙的集合。族群中的蛙按照一定的元进化策略，采用类似粒子群算法的进化方法，在解空间中进行局部深度搜索及内部思想交流。这一过程不断重复演进，直到预先定义的收敛性条件得到满足为止。全局性的信息交换和内部思想交流机制的结合，使得算法具有避免过早陷入局部极值点的能力，从而指引算法搜索过程向着全局最优点的方向进行搜索。本课题主要对经典SFLA算法进行研究和编程实现，分析其工作原理与应用。1.2国内外研究现状算法的提出时间不长，无论在理论还是实践方面都处于起步阶段。在学者们的不断努力下，近年来这种算法不断得到完善和广泛的工程应用，如函数优化、地下水管网优化设计、齿轮问题、旅行商问题、下料问题等，进一步证明它在解决优化问题上的优越性。然而，与其他的智能优化算法一样，SFLA同样存在易收敛到局部最优、在求解部分函数优化问题时效果不够理想的缺陷。根据没有免费的午餐(no free lunch, NFL)定理：从解决实际问题的角度出发，融合不同类型的优化算法，充分发挥它们各自的优势是解决问题的必然发展趋势。为提高算法性能，又有学者利用青蛙间的吸引与排斥机制对算法的更新策略作了适当的修正。函数仿真结果表明，改进后的SFLA克服了基本SFLA收敛缓慢、易陷入局部最优以及求解质量不高的缺点，验证了算法的可行性和有效性。最初，2003年，Eusuff和Lansey在研究资源网络优化时，将随机蛙跳算法实验性地应用在了求解水资源网络的管径选择和管网扩张问题中。在原文中，他们将表示管径类型的一串整数值构成解向量，将随机蛙跳算法作为优化工具，并用EPANET检验了整个过程的约束性。通过与类似文献的比较，作者有力地展示了随机蛙跳算法在解决这一类问题上的优越性，并给出了解决此类问题时的相关参数设置情况。接着，2005年，Elbeltagi4等人对随机蛙跳算法、遗传算法、粒子群优化算法 、蚁群算法及元算法进行了比较，详细描述了各种算法，给出了各个算法的简单实现过程的伪码及合理化的参数组合。采用F8和F10这两个具有连续变量的函数，评价了随机蛙跳算法的计算性能, 结果显示随机蛙跳算法在F10函数的求解方面性能不够理想，在F8函数的求解上性能优于遗传算法，与粒子群优化算法的性能相近。2007年，李英海5等对蛙跳算法的局部搜索部分进行改进，引进一个局部更新阈值，使在阈值的范围内的个体进行更新，否则保持原位置不变。新算法限定了个体变异的空间位置，是算法不易陷入局部极值点，达到快速求解的目的。2009年为了保持种群多样性，赵鹏军6等通过引进高斯变异算子算法改变了算法的优化策略，当种群最优与局部最优解影响的最差个体没有进化时，对其进行一定的干扰，使其更新。随后，他和刘三阳7利用电荷的吸引和排斥原理对蛙跳算法的更新策略进行改进，取得了很好的效果。2010年李英海等为了解决多目标优化问题，对算法的全局搜索部分进行改进，利用小生境技术提高算法性能。2011年吕丽霞7等针对蛙跳算法在迭代后期收敛速度变慢的现象，引入混沌优化机制，取代随机搜索，对当前群体中的最差个体实施混沌搜索，并替换群体中的部分个体，改善算法极值点的能力，增强了算法的全局寻优能力。 这些改进都从某些方面优化了基本的蛙跳算法，如避免陷入局部最优或者提高收敛速度，但像无免费午餐定理（NFL）8中指出，不存在某一种优化算法，在各个方面都比其他算法性能好，所以以上的各种改进算法各有所长。目前，改进后的SFLA已经在许多领域得到了应用，譬如水资源网络优化问题、连续优化问题、成品油管网优化问题、离散优化问题、聚类问题9、双准则带缓冲区的流水车间调度问题、TSP问题10、0-1背包问题11以及多变量PID控制器参数调节问题12等。在短短的几年内，SFLA引起了学术界的广泛关注，成为了国际优化计算领域的研究热点之一，亦逐渐成为解决各种优化问题的热门工具。1.3 论文研究的内容论文研究的内容主要由以下几个方面：(1) 介绍蛙跳算法的基础，分析其原理和流程。(2) 用蛙跳算法求解函数极值。(3) 用蛙跳算法求解0-1背包问题。1.4 论文章节安排论文的结构与章节安排如下:第一章 绪论。介绍了论文研究目的和意义，分析了目前国内外研究动态，并简要描述了本文主要的工作以及各章节安排。第二章 蛙跳算法的基本理论。介绍蛙跳算法的基本理论，分析其工作原理和流程并用函数进行仿