摘 要
本次毕业设计的题目是应用遗传算法设计出一种解决巡回旅行商问题的方法，针对影响遗传算法性能的主要因素进行讨论，对不同的编码方式、遗传算子的设置情况进行比较分析，得出了对于应用遗传算法在控制参数方面的比较有意义的结论。
传统GA算法中的交*操作，是随机选取两个染色体进行单点交*(也可以多点交*、部分匹配交*、顺序交*和周期交*等等)，但是不管是采用何种交*操作，新的子代染色体某一基因位上的值都是由两个父代染色体中相应基因位值经过一定交*运算(直接交换或经算术运算等)所得到的，采用这种交*算子操作使群体经过多次迭代后群体中的个体开始出现极大的相似性，因此照此下去就会出现早期收敛现象，使得算法的收敛速度非常慢甚至只能求到问题的局部最优解。本文结合惩罚函数，提出了一种改进的遗传算法，算例结果表明了本文算法的有效性，并可应用于相当一类的约束优化问题。
在本次毕业设计中，我选用了基本遗传算法来实现优化，利用它的根据获得的信息自行组织搜索的能力，结合罚函数来获得最优解，寻找旅行商问题中的最短距离。

关键词：遗传算法；惩罚函数；基因位；约束优化问题

Abstract
Topic of this graduation design is to apply Genetic Algorithm design a solution to the traveling salesman problem, discussing the main factor that influence the Genetic Algorithm performance, carrying on comparative analysis to different code way and establishment situation of genetic operator, having drawn from it the more meaningful conclusion on control parameter of genetic algorithm.
The crossover operation in the traditional GA operating is that choose two chromosome cross only at random (also you can cross a bit, match and cross partly, cross order and cross cycle etc.), but no matter which kind of crossover operation you choose, a certain gene value of location in new sub-generation chromosome is produced by parent when crossover the corresponding gene value of location in the two chromosome (exchange directly or by arithmetic operation directly), adopting this kind of crossover operator will make individual in the population get to be similar to each other in a great degree when being iterated many times, go on like this will make the population converge in early days , and will make convergence of algorithm very slow or even only the part solution can be obtained. This text combine the punishment function, proposing a improved Genetic Algorithm, the result indicates the validity of this algorithm and can be applied to some analogous kind of restraint optimize problem.

Key words: Genetic Algorithm; Punishment function; Gene location ; Restrain and optimize the question

目 录
前 言 1
第一章 遗传算法简介 2
1.1  遗传算法的产生与发展 2
1.2  遗传算法概要 3
1.3  遗传算法的基本操作 5
1.4  遗传算法的应用 6
第二章 遗传算法的数学基础 8
2.1  模式定理 8
2.2  Walsh变换 9
2.3  非均匀Walsh模式变换 10
2.4  欺骗问题 11
2.5  系统开发环境及开发工具介绍 11
第三章 基本遗传算法 13
3.1  遗传基因型 13
3.2  适应度函数及尺度变换 15
3.3  遗传操作 17
3.4  算法设计与实现 20
第四章 系统分析与设计 22
4.1  需求分析 22
4.2  总体设计 23
4.3  详细设计 25
第五章 遗传算法在巡回旅行商问题中的应用 26
5.1  城市位置及城市间距离生成模块 26
5.2  初始种群生成模块 26
5.3  适应度统计模块 28
5.4  选择模块 28
5.5  交*和变异模块 30
5.6  逆转操作模块 32
结束语 33
致 谢 34
参考文献 35

前 言
自20世纪60年代，由美国Michigan大学的J．H．Holland教授在《Adaptation in Natural and ArtificialSystems》一书中给出了遗传算法的基本定理及数学证明以来，遗传算法越来越成为人们解决高度复杂问题的一个新思路和新方法。目前已被广泛应用于许多实际问题，如函数优化、自动控制、图象识别、机器学习、人工神经网络、分子生物学、优化调度等许多领域中的问题。
遗传算法是一种比较灵活的计算方法，主要表现在编码方式、遗传算子和控制参数的合理选取上，因为不同的编码方式、算子和参数的选取对遗传算法的优化效率具有重要的影响。本文利用遗传算法(GA)对优化参数进行寻优，并对不同编码方式、算子的遗传算法进行了比较研究。
遗传算法在应用中最关键的问题有串的编码方式、适应度函数的确定和遗传算法自身参数设定。如果种群设置太小时，则会出现难以求出最优解，而种群设置太大时，就会增加收敛时间，降低了遗传算法的优化速度。一般取种群大小为20－50。交*概率P 太小时，难以向前搜索，太大时则容易破坏高适应度值的结构。一般取P =0.25-0.8。变异概率P 太小时难以产生新的基因结构，太大又会使遗传算法成了单纯的随机搜索。一般取P =0.01-0.2。

第一章 遗传算法简介
遗传算法(Genetic Algorithms,GA)研究的历史比较短，20世纪60年代末期到70年代初期，主要由美国Michigan大学的John Holland与其同事、学生们研究形成了一个较完整的理论和方法，从试图解释自然系统中生物的复杂适应过程入手，模拟生物进化的机制来构造人工系统的模型。随后经过20余年的发展，取得了丰硕的应用成果和理论研究的进展，特别是近年来世界范围形成的进化计算热潮，计算智能已作为人工智能研究的一个重要方向，以及后来的人工生命研究兴起，使遗传算法受到广泛的关注。从1985年在美国卡耐基•梅隆大学召开的第一届国际遗传算法会议(Internet Conference on Genetic Algorithms:ICGA’85)，到1997年5月IEEE的Transactions on Evolutionary Computation 创刊，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。本章在介绍遗传算法的产生和发展历史之后，概述了遗传算法的基本理论和应用情况。
1.1  遗传算法的产生与发展
遗传算法(Genetic Algorithms)是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的

[1] [2] [3]  下一页