1．遗传算法简介
近年来 ,遗传算法 (GA)的卓越性能引起人们的关注 .对于以往难以解决的函数优化问题 ,复杂的多目标规划问题 ,工农业生产中的配管、配线问题 ,以及机器学习 ,图象识别 ,人工神经网络的权系数调整和网络构造等问题 ,GA是最有效的方法之一 .虽然GA在许多优化问题中都有成功的应用 ,但其本身也存在一些不足 .例如局部搜索能力差、存在未成熟收敛和随机漫游等现象 ,从而导致算法的收敛性能差 ,需要很长时间才能找到最优解 ,这些不足阻碍了遗传算法的推广应用 .如何改善遗传算法的搜索能力和提高算法的收敛速度 ,使其更好地应用于实际问题的解决中 ,是各国学者一直探索的一个主要课题.之后世界范围内掀起了关于遗传算法的研究与应用热潮
...........

1．遗传算法简介 3
1．1遗传算法的发展现状 3
1．1．1 遗传算法简介 3
1．1．2遗传算法存在的问题及相应的改进措施 3
1．1．3　遗传算法的发展动向 (GA' s developmen-tal trends) 6
1．1．4　结论 8
1．2 遗传算法的特点 8
1．3 遗传算法的应用 9
2．遗传算法的算法描述 9
3.旅行商问题的描述与建模 10
3．1 搜索空间与NP难题 10
3．2 旅行商问题(Travelling Salesman Problem,简称TSP)描述 11
4.解旅行商问题的遗传算法 11
4．1 编码方法 11
4．2 交叉算子设计 12
4．3 变异算子设计 13
5.旅行商问题的具有上确界的解法 13
5．1 支撑树加倍法 13
6.算例 15
6．1算例1 15
6．2 算例2 17
6．3 算例3 18
7.结论 19
8．致谢 19
【参考文献】 19

1．陈国良 , 王煦法 , 庄镇泉 , 等. 遗传算法及其应用 [M]. 北京 : 人民邮电出版社 , 1996.
2．赵赫 , 杜端甫. 遗传算法求解旅行推销员问题时算子的设计与选择 [J ]. 系统工程理论与实践 , 1998 ,18 (2) : 62265.
3．克胜 , 邵华 , 曹先彬 , 等. 基于免疫算法的 TSP 问题求解 [A]. 1999 中国智能自动化学术会议论文集 (下册) [ C]. 北京 : 清华大学出版社 , 1999. 116821174.
4．张延华 , 许阳明. 高技术计算环境 ———Matlab 使用指南 [M]. 北京 : 科学技术文献出版社 , 1998.
5．靳蕃, 范俊波, 谭永东编著. 神经网络与神经计算机: 原理、应用. 成都: 西南交通大学出版社, 1991春.
6．遗传算法之发展与全局优化: [硕士学位论文 ]. 成都: 西南交通大学大学, 1995
7．遗传算法原理及应用。周明，孙树栋编著，国防工业出版社。
8．Kenneth A Dejong. Genetic Algorithm s: A 25 Year Perspective. Computational Intelligence: Imitating Life.WCC I- IEEE World Congress on Computational Intelligence, 1994
9．David B Fogel. Applying evolutionary programming to selected T SP. Cyber. Sys. , 1993; 24
10．Wilson G V , Pawley G S. O n the stability of the T SP algorithm of hopfield and tank. B io l. Cybern.1988; 58
11．Brian J. Ritzel, J. Wayland Eheart, and S. Ranjithan. Using genetic algorithms to solve a multiple objective groundwater pollution containment problem. Water Resources Research, 30(5):1589-1603, may 1994
12．A. Charnes and W. W. Cooper. Management Models and Industrial Applications of Linear Programming, volume 1. John Wiley, New York, 1961.
13．Y. Ijiri. Management Goals and Accounting for Control. North-Holland, Amsterdan, 1965.
14．L. Duckstein. Multiobjective Optimization in Structural Design: The Model Choice Problem. In E. Atrek, R. H. Gallagher, K. M. Ragsdell, and O. C. Zienkiewicz, editors, New Directions in Optimum Structural Design, pages 459-481. John Wiley and Sons, 1984.
15．Y. Y. Haimes, W. Hall, and H. Freedman. Multi-Objective Optimization in Water Resources Systems: The Surrogate Trade-Off Method. Elsevier, Amsterdam, 1975.
16．J. P. Ignizio. Goal Programming and Extensions. Heath, Lexington, Massachusetts, 1976.
17．Carlos Artemio Coello Coello. An Empirical Study of Evolutionary Techniques for Multiobjective Optimization in Engineering Design. PhD thesis, Department of Computer Science, Tulane University, New Orleans, LA, apr 1996.
18．Manuel Valenzuela-Rendon and Eduardo Uresti-Charre. A Non-Generational Genetic Algorithm for Multiobjective Optimization. In Thomas B.ack, editor, Proceedings of the Seventh International Conference on Genetic Algorithms, pages 658{665, San Mateo, Cal..

遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法.它最早由美国密执安大学的Holland教授提出,起源于60年代对自然和人工自适应系统的研究.70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验.在一系列研究工作的基础上,80年代由Goldberg进行归纳总结,形成了遗传算法的基本框架.