VC无变异多重交叉遗传算法对旅行商问题的优化实现.doc

VC++067-无变异多重交叉遗传算法对旅行商问题的优化实现 摘 要：旅行商问题（Traveling Saleman Problem，TSP）是组合优化领域中的一个典型问题，涉及求多个变量函数的最小值。尽管问题陈述简单，但求解却非常困难，并且已经被科学家证明为NP完全问题。但该问题确实广泛存在诸多领域中，且是诸多领域内出现的多种复杂问题的集中概括和简化形式。快速、有效地解决旅行商问题有着较高的理论意义和高度的实际应用价值，这也是本文提出的用改进遗传算法求解旅行商问题的目的。 本文根据旅行商问题的特点和当前研究情况，选用遗传算法来对它进行求解。论文首先介绍了旅行商问题，已经对应遗传算法的原理及基本实现技术，并着重阐述了遗传算法的特性，再具体地针对传统遗传算法进行相应的改进。传统遗传算法在求解旅行商问题时通常采用城市次序编码法和边编码法。本文采用了传统方法，可以容易判断个体的合法性和计算其适应度。在遗传算法的求解过程中，本文的算法采用无变异，二重交叉以上的算法进行求解，经过试验结果证实，此方法求解的全局最优解几率较高。 关键字：TSP，改进遗传算法，无变异，多重交叉 ? 目录 摘要 3 1 TSP问题 4 1.1旅行商问题介绍 4 1.2 NP难题 5 1.3 TSP问题几种常见解法介绍 5 1.4 TSP问题的研究目的和意义 7 2遗传算法 7 2.1遗传算法简介 7 2.2 遗传算法原理 8 2.3 算法描述和运行步骤 8 2.4 参数 9 2.5 特点 9 2.6 变量 10 2.7 适用的问题 11 2.8 发展历史 11 2.9 应用领域 11 3 遗传算法与TSP问题的求解 12 3.1选择算子 12 3.2 交叉算子 13 3.3 变异算子介绍 17 3.4 仿真和结果 17 3.5 小结 18 参考文献 19 ? ? 以下是部分界面图，如图片不清，请直接点击图片，如需要看更详细的资料，请直接联系客服！ ? ??????????????????????????? 图1（双击并最大化图片，可看清晰图片） ? ? ????????????????????????? 图2（双击并最大化图片，可看清晰图片） ? ? ????????????????????????????????? 图3（双击并最大化图片，可看清晰图片） -