遗传算法.doc

遗传算法
页数 20 字数 13479
【摘 要】遗传算法呈现出的是一种通用的算法框架，该框架不依赖与问题的种类。本文利用遗传算法与传统方法求解旅行商问题，进而利用算例进行遗传算法与传统算法的比较。几个算例中，遗传算法求得的结果都比传统算法要好。由几个例子可以看出，遗传算法是一类具有较强鲁棒性的优化算法，特别是对于一些大型，复杂非线性系统，它更表现出了比其他传统优化算法更加独特和优越的性能。

【关键词】 遗传算法,旅行商问题,组合优化


目录

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春.