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