[ 论文中心|计算机应用 ]遗传算法解旅行商问题
登出时间 ： 2008-07-22 14:30:54
写稿时间 ： 2007-7
登 陆 人 ： 空空的TIAN空
下 载 ： 1
总 页 数 ： 20 Page / 字数 ： 13489
文件类型 ：
大 小 ： [ 294,912Byte
]
资料点评 ： 没有会员的点评.
关键词 ： 遗传算法 旅行商问题 组合优化 编码方法 支撑树加倍法
原文：
1．遗传算法简介
近年来 ,遗传算法 (GA)的卓越性能引起人们的关注 .对于以往难以解决的函数优化问题 ,复杂的多目标规划问题 ,工农业生产中的配管、配线问题 ,以及机器学习 ,图象识别 ,人工神经网络的权系数调整和网络构造等问题 ,GA是最有效的方法之一 .虽然GA在许多优化问题中都有成功的应用 ,但其本身也存在一些不足 .例如局部搜索能力差、存在未成熟收敛和随机漫游等现象 ,从而导致算法的收敛性能差 ,需要很长时间才能找到最优解 ,这些不足阻碍了遗传算法的推广应用 .如何改善遗传算法的搜索能力和提高算法的收敛速度 ,使其更好地应用于实际问题的解决中 ,是各国学者一直探索的一个主要课题.之后世界范围内掀起了关于遗传算法的研究与应用热潮
1．1遗传算法的发展现状
1．1．1 遗传算法简介
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法.它最早由美国密执安大学的Holland教授提出,起源于60年代对自然和人工自适应系统的研究.70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验.在一系列研究工作的基础上,80年代由Goldberg进行归纳总结,形成了遗传算法的基本框架.
1．1．2遗传算法存在的问题及相应的改进措施
自然界早已显示出了基因的强大威力 ,通过这种机制 ,一系列的具有智能、自组织、自修整的器官产生了 .人们要在科学研究中效仿这些生物器官 ,那么就必须了解基因、进化的概念 .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 Intel
点评资料 :
