摘要: 遗传算法 (Genetic Algorithm, GA)是一种全新的全局优化搜索算法，它的基本思想就是模拟生物进化的过程。遗传算法它具有不受搜索空间的限制，不要求在所求的解具有连续性、提供了一种求解复杂系统优化问题的通用框架、不依赖于问题的具体领域，对问... 展开 遗传算法 (Genetic Algorithm, GA)是一种全新的全局优化搜索算法，它的基本思想就是模拟生物进化的过程。遗传算法它具有不受搜索空间的限制，不要求在所求的解具有连续性、提供了一种求解复杂系统优化问题的通用框架、不依赖于问题的具体领域，对问题的种类有很强的鲁棒性、遗传算法具有并行性，这些特性就决定了遗传算法在许多领域的广泛的运用。实践证明，遗传算法对于组合优化中的NP完全问题的求解非常有效。 组合优化 (CombinatoriAlOptimization,CO)主要研究的是那些含有有限个可行解的问题，它在工程设计中有着广泛的应用。这其中一个重要而且很普遍的应用领域就是考虑如何有效的利用稀缺的资源来提高其生产力。比较典型的工程设计问题包括了背包问题、装箱问题、旅行商问题、车辆路径问题、机器调度排序与平衡问题、制造元设计问题、设备定位与布局等。虽然从理论上来说，这些问题的最优解都可以通过简单的枚举得到，但是在实际操作中通常情况下都不能实现。因为对于这种实际设计中的问题来说，它们的可行解的数量可能特别的巨大，因此组合优化中最具有挑战性问题之一就是如何有效地解决这些组合爆炸。而解决这一困难问题一种很有效的方法就是采用遗传算法。 本文研究的就是基于遗传算法的组合最优化问题。主要研究的是对标准遗传算法的改进算法并通过这些改进的遗传算法算法用于解决组合优化问题。特别给出了两个比较经典的组合优化问题—旅行商问题(Traveling Salesman Problem,TSP)、车辆路径问题(Routing Vehicle Problems，VRP)的解决方案。本文的主要工作包括以下几个方面： (1)首先概括地介绍了遗传算法的一些基本原理，包括遗传算法的历史、定义、应用、特点和标准遗传算法的遗传操作。还在总结前人的基础上，研究了遗传算法的一些常见的改进算法。 (2)为了克服标准遗传算法在交叉概率和变异概率固定不变所带来的局限性，本文对标准遗传算法的每一步遗传操作都进行了优化，特别是在在交叉操作中采用“部分匹配”的方法，在变异操作中引用了“多项式的变异”的方法，并将这种方法应用于求解TSP问题，及对全国32个城市求解最佳路径，试验结果表明了这种改进的遗传算法具有很好的收敛性并且得到了最优解。 (3)为了克服遗传算法在局部搜索能力方面的不足，本文还是对遗传算法的每一步遗传操作都进行了优化，特别是将局部搜索能力很强的爬山算法与基本遗传算法相互结合，从而形成了混合的遗传算法，并将其应用到求解车辆路径问题(VRP)。试验结果证明了VRP问题的混合遗传算法的搜索能力提高了，因此种群演化也较容易地产生最优解。 收起