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

关键词:遗传算法;组合优化;旅行商问题;车辆路径问题

II
安徽大学2010年硕士学位论文 Abstract
Abstract
ic algorithm is a new global optimization search algorithm, its basic idea is
to simulate the biological evolution process. ic algorithm search space it has not
restrictions, are not required to seek the solution in the continuity, providing a
complex system optimization problems for solving mon framework, the
problem does not depend on the specific areas of the problem types have a strong
robustness, ic algorithm has parallelism, these features will determine the
ic algorithm in many areas of extensive use. Practice has proved that ic
algorithms binatorial optimization of plete problem sol