《工人鱼群法在组合优化问题的研究--本科毕业设计》由会员分享，可在线阅读，更多相关《工人鱼群法在组合优化问题的研究--本科毕业设计（20页珍藏版）》请在金锄头文库上搜索。
1、 2013届学生毕业设计(论文)材料（四）学 生 毕 业 设 计（论 文）课题名称 人工鱼群法在组合优化问题的研究姓 名何少武学 号0909401-17院 系数学与计算科学学院专 业数学与应用数学指导教师林仁 讲师2013年4月23 日湖南城市学院本科毕业设计（论文）诚信声明本人郑重声明：所呈交的本科毕业设计（论文），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本设计（论文）不含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 本
2、科毕业设计（论文）作者签名： 二 年 月 日 目录 摘要. .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参
3、考文献. . . .14致谢. .15II人工鱼群算法在组合优化问题的研究何少武摘 要：组合优化问题在现实生活中有着很广泛的应用，并且有很强的工程代表性，但最优化解很困难，目前对组合优化问题的求解主要以启发式算法为主。人工鱼群算法是一种新的群智能优化算法，其原理简单，收敛速度快，求解精度高。近年来得到广泛关注和应用。人工鱼群算法的觅食行为是算法全局收敛的基础，聚群行为和追尾行为更加增强了算法的全局收敛性。蚁群算法决旅行商问题存在收敛速度慢，而且参数的设定对算法的性能影响很大，而人工鱼群算经过实例证明具有优于蚁群算法的收敛速度。关键字:人工鱼群算法;组合优化问题;群聚行为；蚁群算法Artific
4、ial fish algorithm in combinatorial optimization problemHe shao wuAbstract：Combinatorial optimization problem has a very wide range of applications in real life, and has a strong engineering representative, but best to resolve the very difficult, solving combinatorial optimization problems mainly he
5、uristic algorithm. Artificial fish swarm algorithm is a new swarm intelligence optimization algorithm, the principle is simple, fast convergence and high accuracy. In recent years has been widespread concern and applications.The feeding line of the artificial fish swarm algorithm is a global converg
6、ence on the basis of the behavior of clusters and rear-end behavior and more to enhance the global convergence of the algorithm. Ant colony algorithm decision traveling salesman problems of slow convergence and parameter settings affect the performance of the algorithm, artificial fish school operat
7、or through examples prove better than the ant colony algorithm convergence rate. Keywords: artificial fish swarm algorithm; combinatorial optimization problems; flocking behavior;genetic algorithms1 绪论1.1课题背景及意义优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题。组合优化，又称离散优化问题，是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学中一
8、个经典且重要的分支，随着计算机科学、管理科学、现代化生产技术等的日益发展，这类问题与日俱增，受到诸多学者的高度重视。典型的组合优化问题有旅行商问题、背包问题、车间作业调度问题、装箱问题、图着色问题、聚类问题等。这些问题描述简单，并且有很强的工程代表性，但最优化求解很困难，其主要原因是求解这些问题的算法需要极长的运行时间与极大的存储空间，以致根本不可能在现有计算机上实现，即所谓的“组合爆炸”。目前常见的启发式算法有遗传算法、模拟退火算法、禁忌搜索算法、人工鱼群算法、蚁群算法、粒子群算法等。人工鱼群算法是我国学者在2002年提出的一种新的群智能算法。得到国内外学者的广泛关注，目前处于研究改进阶段。
9、人工鱼群算法已经成为交叉学科中一个非常活跃的研究问题。人工鱼群算法对目标函数的性质要求不高，对初值要不高，对参数设定的要求不高，具备全局优化能力，能够快速跳出局部极值点。具有并行性，简单性，全局性，快速性。1.2课题的研究现状优化问题是生产过程中广泛存在的一个问题，经过优化处理后，生产过程系统会降低能量消耗、提高生产效率。为提供解决优化领域的问题的有效方法，智能搜索算法综合了生物学、计算机和人工智能等各个科学领域的知识，随着各个科学的发展，也是逐渐深入的。人工鱼群算法是一种新型的智能优化算法，目前用人工鱼群算法解决组合优化问题还是一个比较新的领域。人工鱼群算法（AFSA）是浙江大学的李晓磊、钱
10、积新等人提出的，2002年李晓磊在其博士论文中对人工鱼群算法进行了系统的介绍。与其他群集智能算法相比，人工鱼群算法既有相同点又有自己的特点和相异之处。对TSP问题，优化专家们提出各种不同启发式算法，以得到该问题的近似优化算法。这些不同算法的共同目的是尽量提高其解的精度。各类启发式算法是目前比较理想的算法，适用于不同规模和时间要求的TSP问题，他们都可以得到局部最优解或全局最优解。近年连来有很多的国内外学者在研究遗传算法，粒子群算法解决TSP问题。并且取得了一定的成效。JSP问题的研究广泛吸收遗传算法，粒子群算法，人工神经网络，模拟退火算法的精髓。解决TSP问题主要有三步:JSP仿生，创建JSP
11、遗传算法所需要的材料，包括JSP染色体以及个体群组;JSP遗传进化创造JSP遗传算法所需要的遗传算子，包括选择，交叉，变异，组合算子，同时设定遗传进化参数;JSP仿真，以JSP的实际需求为依据，定义JSP遗传算法所需要的JSP个体适应度，并设计JSP个体适应度的求解方法。2解决组合优化问题的几种智能算法2.1遗传算法遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（
