毕业论文普通遗传算法与佳点集遗传算法的研究

《毕业论文普通遗传算法与佳点集遗传算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、目录摘要1关键词1引言11遗传算法概论11．1遗传算法的历史和研究现状11．2遗传算法的基本原理31．2．1遗传算法基本概念31．2．2遗传算法基本原理31．2．3遗传算法的特点32普通遗传算法42．1普通遗传遗传算法思想42．2普通遗传算法的遗传操作42．2．1选择（selection）操作42．2．2交叉(crossover)操作42．2．3变异(mutation)操作54遗传算法在TSP问题上的应用84．1TSP问题概述84．2遗传算法求解TSP问题84．2．1编码与解码84．2．2初始化种群

2、94．2．3适应度函数94．2．4选择算子104．2．5交叉算子104．2．6变异算子154．2．7停止准则155TSP问题的实验结果及分析155．1普通遗传算法与佳点集遗传算法的比较与分析155．1．1最优解分析155．1．2算法收敛速度分析175．1．3算法运行时间分析18总结18致谢18参考文献19ABSTRACT19KEYWORDS1917遗传算法在TSP问题上的应用摘要：遗传算法(GA)模拟自然进化机制，在搜索优化问题全局或全局附近的最优解上具有较好的鲁棒性、内在的并行性和较优越的稳定性，

3、因而在诸如组合优化、图像处理等方面有着广泛的应用。但是传统的遗传算法性能很大程度上依赖于相关参数的取值与算子的作用方式，佳点集遗传算法利用数论中的佳点集理论和方法，来改进普通遗传算法中的各相关算子，以期克服普通遗传算法收敛速度慢，易陷入局部最优的弱点。本文在分析普通遗传算法和佳点集遗传算法机理上，利用JAVA语言实现了佳点集算法演示系统，通过选取不同的遗传算子来对标准TSP的数据集中的大量数据进行了对比分析和验证。我们的实验结果表明对于较大规模的TSP组合问题佳点集的优势是非常明显的。关键词：Tsp

4、问题；普通遗传算法；佳点集遗传算法；单切点交叉算子；双切点交叉算子；循环交叉算子；佳点集交叉算子；引言遗传算法GeneticAlgorithm（GA）是由美国密歇根大学的JohnH.Holland教授及其学生于20世纪60年代末到70年代初提出的。它是以达尔文的自然进化论“适者生存、优胜劣汰”和孟德尔遗传变异理论为基础，模拟生物进化过程。它具有大范围快速全局搜索能力，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求的最优解。正是遗传算法的诸多特点，使得它在求解组合优化、机器

5、学习、并行处理等问题上得到了广泛的应用。普通遗传算法是通过模拟染色体群的选择、交叉和变异等操作，不断迭代，最终收敛到高适应度值的染色体，从而求得问题的最优解。但是随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，普通遗传算法的收敛速度慢、易陷入局部最优的缺点就暴露了。而佳点集遗传算法正是通过佳点集的方法改进交叉算子，加快算法收敛到全局最优解的速度，降低发生早熟的概率，提高整个算法的计算效率。1遗传算法概论1．1遗传算法的历史和研究现状早在1967年Bagley和Rosenberg就提出了生物遗传算

6、法(GA)的初步思想，1975年由美国Michigan大学的JohnHolland的出色工作奠定了遗传学算法的理论基础，遗传变异和优胜劣汰现象的优化搜索算法付诸了实际应用，这也标志着遗传算法的诞生。到了80年代初期，Holland的一些学生的毕业论文中对遗传算法的应用以及在应用中遇到的问题进行了研究，其中有Delong(1975)对GA的各种策略的性能和机理进行了大量的细致分析与实验。与此同时Holland还给出了一个自适应的规则学习系统，并于1980年成功地实现了这一学习系统，Holland及其学

7、生的研究成果使得人们开始看到了GA的应用价值。1981年Betake的博士论文中提出了用Walsh函数来研究遗传算法的方法，Alberta大学的Brindle在其博士论文中开始对选择策略进行了研究，这一时期的研究回答了GA算法的到底有何意义，有何价值。也正是他们的研究使得更多的人把目光投向了遗传算法，1985年召开了第一届GA国际会议，至此以后每两年召开一次。80年代中期，遗传算法广泛的应用于许多的应用领域，如TSP问题、调度问题、机器学习、模式分类问题，囚徒困境问题以及多关节机械手轨迹规划问题。1

8、989年D.J.Goldberg总结了遗传算法的主要成果，全面论述了遗传学的基本原理极其应用，奠定了现代GA的科学基础。17进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不仅它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已