人工鱼群法在组合优化问题的研究毕业

学生毕业设计（论文）课题名称人工鱼群法在组合优化问题的研究姓名何少武学号0909401-17院系数学与计算科学学院专业数学与应用数学指导教师林仁讲师2013年4月23日※※※※※※※※※※※※※※※※※※※※※※※※2013届学生毕业设计(论文)材料（四）湖南城市学院本科毕业设计（论文）诚信声明本人郑重声明：所呈交的本科毕业设计（论文），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本设计（论文）不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。本科毕业设计（论文）作者签名：二○年月日目录摘要...........................................................1关键词.........................................................1Abstract......................................................1Keywords......................................................11绪论.............................................................21.1课题背景及意义................................................21.2课题的研究现状...............................................22解决组合优化问题的几种智能算法.................................32.1遗传算法....................................................32.2蚁群算法.....................................................42.3粒子群算法..................................................52.4几种智能算法特点.............................................62.5小结.......................................................73基本人工鱼群算法................................................73.1人工鱼群算法模型.............................................73.2算法描述.....................................................83.3算法全局收敛性...............................................113.4各参数对收敛性能的影响分析.，.................................123.5应用.........................................................123.6小结.........................................................124总结和展望......................................................14参考文献.......................................................14致谢............................................................15人工鱼群算法在组合优化问题的研究何少武摘要：组合优化问题在现实生活中有着很广泛的应用，并且有很强的工程代表性，但最优化解很困难，目前对组合优化问题的求解主要以启发式算法为主。人工鱼群算法是一种新的群智能优化算法，其原理简单，收敛速度快，求解精度高。近年来得到广泛关注和应用。人工鱼群算法的觅食行为是算法全局收敛的基础，聚群行为和追尾行为更加增强了算法的全局收敛性。蚁群算法决旅行商问题存在收敛速度慢，而且参数的设定对算法的性能影响很大，而人工鱼群算经过实例证明具有优于蚁群算法的收敛速度。关键字:人工鱼群算法;组合优化问题;群聚行为；蚁群算法ArtificialfishalgorithmincombinatorialoptimizationproblemHeshaowuAbstract：Combinatorialoptimizationproblemhasaverywiderangeofapplicationsinreallife,andhasastrongengineeringrepresentative,butbesttoresolvetheverydifficult,solvingcombinatorialoptimizationproblemsmainlyheuristicalgorithm.Artificialfishswarmalgorithmisanewswarmintelligenceoptimizationalgorithm,theprincipleissimple,fastconvergenceandhighaccuracy.Inrecentyearshasbeenwidespreadconcernandapplications.Thefeedinglineoftheartificialfishswarmalgorithmisaglobalconvergenceonthebasisofthebehaviorofclustersandrear-endbehaviorandmoretoenhancetheglobalconvergenceofthealgorithm.Antcolonyalgorithmdecisiontravelingsalesmanproblemsofslowconvergenceandparametersettingsaffecttheperformanceofthealgorithm,artificialfishschooloperatorthroughexamplesprovebetterthantheantcolonyalgorithmconvergencerate.Keywords:artificialfishswarmalgorithm;combinatorialoptimizationproblems;flockingbehavior;geneticalgorithms1绪论1.1课题背景及意义优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题。组合优化，又称离散优化问题，是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学中一个经典且重要的分支，随着计算机科学、管理科学、现代化生产技术等的日益发展，这类问题与日俱增，受到诸多学者的高度重视。典型的组合优化问题有旅行商问题、背包问题、车间作业调度问题、装箱问题、图着色问题、聚类问题等。这些问题描述简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。目前常见的启发式算法有遗传算法、模拟退火算法、禁忌搜索算法、人工鱼群算法、蚁群算法、粒子群算法等。人工鱼群算法是我国学者在2002年提出的一种新的群智能算法。得到国内外学者的广泛关注，目前处于研究改进阶段。人工鱼群算法已经成为交叉学科中一个非常活跃的研究问题。人工鱼群算法对目标函数的性质要求不高，对初值要不高，对参数设定的要求不高，具备全局优化能力，能够快速跳出局部极值点。具有并行性，简单性，全局性，快速性。1.2课题的研究现状优化问题是生产过程中广泛存在的一个问题，经过优化处理后，生产过程系统会降低能量消耗、提高生产效率。为提供解决优化领域的问题的有效方法，智能搜索算法综合了生物学、计算机和人工智能等各个科学领域的知识，随着各个科学的发展，也是逐渐深入的。人工鱼群算法是一种新型的智能优化算法，目前用人工鱼群算法解决组合优化问题还是一个比较新的领域。人工鱼群算法（AFSA）是浙江大学的李晓磊、钱积新等人提出的，2002年李晓磊在其博士论文中对人工鱼群算法进行了系统的介绍。与其他群集智能算法相比，人工鱼群算法既有相同点又有自己的特点和相异之处。对TSP问题，优化专家们提出各种不同启发式算法，以得到该问题的近似优化算法。这些不同算法的共同目的是尽量提高其解的精度。各类启发式算法是目前比较理想的算法，适用于不同规模和时间要求的TSP问题，他们都可以得到局部最优解或全局最优解。近年连来有很多的国内外学者在研究遗传算法，粒子群算法解决TSP问题。并且取得了一定的成效。JSP问题的研究广泛吸收遗传算法，粒子群算法，人工神经网络，模拟退火算法的精髓。解决TSP问题主要有三步:JSP仿生，创建JSP遗传算法所需要的材料，包括JSP染色体以及个体群组;JSP遗传进化创造JSP遗传算法所需要的遗传算子，包括选择，交叉，变异，组合算子，同时设定遗传进化参数;JSP仿真，以JSP的实际需求为依据，定义JSP遗传算法所需要的JSP个体适应度，并设计JSP个体适应度的求解方法。2解决组合优化问题的几种智能算法2.1遗传算法遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（geneticoperators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。与传统的优化算法相比，遗传算法具有以下特点:(1)遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。(2)遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。(3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。(4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基