本文主要的研究内容是进化计算的算法在路径优化问题上的应用。其中本文主要涉及的进化计算的算法有遗传算法（Genetic Algorithm）和粒子群优化算法(Particle Swarm Optimization)。而本文所讨论的路径优化问题主要指旅行商问题（Traveling Salesman Problem）和车辆路由问题（Vehicle Routing Problem）。进化计算通常有以下四个领域：遗传算法(Genetic Algorithm, GA),进化策略(Evolution Strategies, ES), 进化规划（Evolutionary Programming, EP）,还有遗传规划(Genetic Programming, GP)。近年来，又出现了粒子群优化算法(Particle Swarm Optimization), 还有拟子算法( memetic algorithm)，这些算法虽然不是进化计算的经典分支，但是最近几年它们的发展也非常迅速，而且在很多领域中取得了很好的应用，因此成为进化计算框架中重要的组成部分。 遗传算法是进化计算领域中研究最充分，应用最广泛的领域。遗传算法（Genetic Algorithm，简称GA）最早由Holland于1975年提出，该方法以一个随机染色体种群开始进化，适应度高的染色体被选择进行交叉和变异操作，产生的子代与父代不同，但从父代继承了某些遗传因素，当某一特定代产生或进化收敛时过程停止。粒子群优化算法是近几年来发展比较快的进化计算算法。粒子群优化算（Particle Swarm Optimization，简称PSO）首先由Kennedy和Eberhart于1995年提出，是一种基于迭代的进化计算的算法。粒子群优化算法主要借鉴了两个主要方面的领域：一是人工生命方面，它从鸟群和鱼群觅食得到灵感，特别是群集理论(Swarm Theory)。另一方面，同进化计算，特别是遗传算法和进化规划有着紧密的联系。算法中，一定数量的粒子构成了粒子群。在每一次迭代中，所有的粒子在N维空间中“移动”以搜索全局最优解。粒子的速度和位置由特定的更新公式确定。每个粒子在搜索空间的过程中，受到了三个方面因素的影响，一方面是粒子当前的速度，另一方面是粒子过去搜索到的历史最好纪录，还有一方面是整个群中搜索到的全局最好纪录。旅行商问题的形象化描述是指一个商人想要到n个城市推销商品，希望选择一条道路，使得经过所有城市一次且仅一次，最后回到起点。我们的目标是帮助这个商人找到最短的路径。旅行商问题简称TSP（Traveling salesman problem）。TSP以图论的形式描述为：在图G=(V,E)中，V是点（城市）的集合，E是边的集合，E={(i, j)|i,j∈V}。点i与j的欧氏距离为dij，设dij=dji。目标是找到一个长度最小的闭合回路，使得访问每个点一次且仅一次，这条闭合回路也称作哈密顿回路。粒子群优化算法已经成功地应用于求解连续域问题，但是对于离散域问题特别是路由问题的求解研究还很少。本文提出了一种改进的粒子群优化算法，用于求解旅行商问题。采用模糊矩阵来表示粒子的位置和速度，并重新定义其更新公式，最后对TSPLIB中的具体算例进行测试，实验结果表明该算法能够得到较好的结果。 <WP=43>模糊离散PSO算法对于中小规模的TSP问题效果较好，但是随着问题规模的扩大，算法的空间复杂性将会有很大增加。基于上述考虑，我们提出了一种快速的粒子群优化算法。算法使用连续的PSO算法在笛卡尔空间下的超立方体中搜索，然后使用特殊的空间转换方式将TSP问题的离散排列空间与超立方体空间建立映射关系，在算法中还引入了2-opt局部搜索的技术以增强算法的搜索能力，并利用了耗散PSO算法的思想引入混乱算子避免粒子陷入局部最小。最后针对TSPLIB中的四个问题进行了测试，实验表明算法具有快速和求解质量高的特点。车辆路由问题（Vehicle Routing Problem，VRP）[4]最早由Dantzig于1959年提出，是运筹学中的热点研究问题，其原型是旅行商问题（Traveling Salesman Problem, TSP）[5]。所谓VRP是对一系列特定位置和需求量的客户点，调用一定数量的车辆，从中心仓库出发，选择最优的行车路线，使车辆有序地访问各客户点，在满足特定的约束条件（如客户的需求量，车辆载重限制）下，使得货物尽快达到客户点并且运输总费用最低。车辆路由问题是比TSP问题更加复杂，并且更具实用价值的NP-hard问题，可以认为TSP问题是VRP问题的一个特例。带时间窗约束的车辆路由问题（Vehicle Routing Problem with time windows, VRPTW）中给定了各客户点的需求量和允许服务的时间范围，要求分派的车辆从仓库出发并回到仓库的一组行车路线，各车辆不能超载，并使总费用最少。VRPTW是在实际的物流配送决策中经常遇到，是典型的带约束的组合优化问题。由于GA的内在并行性特别适合大规模启发式搜索问题，并首先在TSP问题中得到成功的应用，近年来尝试用GA求解VRPTW又成为新的研究热点。本文提出一种改进的遗传算法，用于求解带时间窗的车辆路由问题。在标准遗传算法的基础上，提出新的三父本选择策略和IHX交叉算子，同时对启发函数进行改进，同时考虑距离、时间窗和能力限制约束，并综合应用于求解VRPTW的100个客户点的Solomon标准算例中，实验结果表明其有效性。