蚂蚁是群居性昆虫,其行为的一个重要方面就是能在巢穴和食物源之间找到一条最短路的能力。当蚂蚁在巢穴和食物源之间行走时会释放一种称之为信息素的化学物质。一些生物学家通过实验证实蚂蚁喜欢用信息素的浓度来标识路径:路径上信息素浓度越高该路径被选中的概率就越大。然而,一些生物学上的研究表明这种信息素踪迹是持久的(因蚂蚁的种类和路面类型等因素不同,信息素可以保存几小时到几个月),所以,在搜索行为中最短路径上信息素蒸发率的影响就显得不是那么重要了。即使蚂蚁已经找到一条更短的路径,它们也很难忘记信息素浓度高的那些路径。因此,如果将蚂蚁的这种行为直接转化到计算机中来设计搜索算法,那么我们设计的算法往往会迅速陷入局部极值。受蚂蚁觅食行为的启发,人们在过去的二十年中提出了很多蚁群优化算法(ACO)的变种,这些变种已经成为一种新的解决组合优化问题可行的算法。该模型的显著特征是正反馈、分布式计算和富于建设性的贪婪启发式搜索。目前,ACO算法的各种版本都是基于人工蚂蚁的相互协作和人工信息素的交流。当人工蚂蚁在图的边上游走时有两种信息来指导蚂蚁的移动:用来测量蚂蚁由一点到另一点的启发式信息和模拟真实蚂蚁释放信息素的人工信息素。虽然ACO已成功应用到很多组合优化问题中,但是它的理论研究却很滞后。到目前为止,只有少量的数学证明结果显示了该算法可以在有限的时间内获得最优解。然而,怎样确定信息素蒸发率这个关键因素在ACO算法中的影响,怎样证明算法运行时间可由指数级变为多项式级,实在是一项复杂而艰巨的工作。起源于二十世纪50年代后期的进化算法,在过去的十年得到了很大关注。我们描述了进化算法(EA)不同方法的结构和工作原理,这些方法包括遗传算法(GA),遗传规划(GP),进化策略(ES)和进化规划(EP),然后分析了算法的表达、变异算子、重组和选择机制。进化规划是进化算法的一个重要分支,它主要依靠选择操作和变异算子来搜索优化问题的解。为改进EP的性能,人们近期提出了一系列新的变异算子。与常规进化规划使用Gaussian分布不同,使用基于Cauchy分布的快速进化规划算法是一个很好的进化规划算法。一些研究表明,变异算子和选择机制的相互影响在进化规划的性能中起着重要的作用,但这种相互影响却难以琢磨。EP中的适应性参数,即步长控制,在进化进程中对目标变量的控制也起着重要的作用。然而,这种步长控制常因失控而使搜索陷入早熟。如果使用下界机制来维持步长,这会限制对目标变量进行深层次的局部开发。所以,寻求进化过程中探索和开发的平衡,这也是一项复杂而艰巨的工作。有时间窗车辆路径问题(VRPTW)是一个双目标优化问题,其目的首先是最小化所用路径集合,即车辆数,然后最小化车辆走的总路程。由于其应用的广泛性和经济上的重大价值一直受到国内外学者的广泛关注。在实践中有时间窗车辆路径问题的应用包括:学校班车路线,报纸和邮件的分发,治安巡逻或维修服务,航空和铁路时间表安排以及工业废品收集等。本文的主要工作和创新点如下:1、描述了常见的各种蚁群优化算法、进化规划算法和各种变异算子,如Gaussian变异、Cauchy变异和Lévy变异。2、分析了Lévy分布,它的两个参数分别是α和γ,0 <α< 2,γ是满足γ> 0的比例因子。参数α控制Lévy分布的形状,其尾部区域更依赖参数α。也就是说,参数α越小,尾部越长。我们根据α= 1.0,1.3,1.7,和2 .0使每个父代个体产生四个子代作为下一代好的候选解,然后在四个个体中选择一个子代。这种基于环境来选择子代的策略在某种意义上说是适应性的。3、提出一种新的最大最小蚁群算法EP和ACO的基本思想是很不同的:EP使用每一个个体的行为,其搜索策略不是期望去哪个区域,而是从局部点逃逸,但是ACO使用包含在种群中的预估信息,即蚂蚁根据路径上信息素的分布来产生新的解。本文的工作是将这两种优化方法结合起来会产生怎样的结果。基于上述观点,本文提出了基于MMAS框架的混合算法,通过利用EP和ACO的优点来解决VRPTW问题。我们用两个人工蚁群设计算法HMMAS-VRPTW来优化VRPTW:第一个蚁群最小化车辆数目,第二个蚁群最小化旅行的距离。两个蚁群通过信息素的更新来交换信息,从而相互协作。然后,使用Lévy随机分布来提高新框架的性能,Lévy随机分布可以产生介于Gaussian和Cauchy变异间的任意随机数,Gaussian变异在全局最优解的临域能找到一个解更好的解,而Cauchy变异在当前搜索点和全局最优点相对较远时会有较好的性能。通过分析有时间窗车辆路径问题和旅行商问题的区别,改进最大最小蚁群算法中状态转移策略,并增加与可用车辆相同数量的虚拟仓库,使这两个蚁群使用独立的信息素但通过分享全局最优解来协作,从而减少了算法的计算时间并避免过早收敛。一些实验结果表明算法HMMAS-VRPTW在解的质量和计算时间方面有良好的性能。