详情

原文传递车辆路径问题的改进遗传算法

论文题名：	车辆路径问题的改进遗传算法
关键词：	遗传算法;车辆路径问题;早熟收敛;双种群;交叉算子
摘要：	在计算机飞速发展的今天，车辆路径问题(Vehicle Routing Problems，简称VRP)一直以来是众多计算机学者研究的焦点。如何针对车辆路径问题的特点，构造运算简单、性能优异的启发式算法，对物流系统及许多可以转化为车辆路径问题的组合优化问题都有十分重要的意义。因此，本文针对传统遗传算法求解车辆路径问题所存在的不足，将《作物育种学》中的理论分别应用于目前遗传算法求解车辆路径问题的两种最典型的算法：即广泛使用的单种群遗传算法和寻优效率较高的双种群遗传算法，并通过仿真实验验证了本文所设计的算法的性能。本文研究内容及成果如下： ①针对传统遗传算法在求解车辆路径问题中存在的“早熟收敛”、易陷入局部极值点等不足，本文提出了将作物育种学中的差异性原理应用于遗传算法求解车辆路径问题的算法设计中的改进思路。我们将该原理应用到单种群遗传算法交叉前的父染色体选择过程，以及双种群遗传算法的种群交叉过程，通过模拟自然界中的进化规律来提高遗传算法的优化性能。 ②基于上述改进思路，本文设计了一种改进的单种群遗传算法。该算法通过采用新的父染色体选择策略以及新的交叉算子，能够保证一对适应值有一定差异的染色体进行交叉，使产生的后代性状分离。这样就可以增加种群中个体的多样性，扩展解的搜索空间，避免过早陷入局部最优，在优化性能的提高方面取得更好的效果。 ③基于上述改进思路，本文还设计了一种改进的双种群遗传算法。该算法采用了一种新的种群交叉策略，主要是针对种群间互换染色体这一步骤，对传统的双种群遗传算法做了改进。同时还提出了一种新的染色体交叉与变异策略，让两个种群使用不同的交叉和变异算子，以及不同的交叉和变异概率。通过新的种群交叉策略的引入和新的染色体交叉与变异策略的引入，改进后的算法能更有效地模拟现实物种进化过程，以保证种群内物种多样性，有利于整个种群的进化。 ④采用广泛使用的标准测试数据，对本文提出的单种群遗传算法和双种群遗传算法与传统遗传算法作了较为充分的实验测试和对比分析。实验结果表明，文中的方法能更为有效的求得车辆路径问题的优化解，克服传统遗传算法求解车辆路径问题中“早熟收敛”和易陷入局部极值的不足。上述研究成果，在基于遗传算法求解车辆路径问题领域中具有较好的学术参考价值，对物流系统的开发有很好的应用价值。
作者：	曾凡超
专业：	计算机软件与理论
导师：	朱征宇
授予学位：	硕士
授予学位单位：	重庆大学
学位年度：	2007
正文语种：	中文