袁汪凰，游晓明，刘 升

1.上海工程技术大学 电子电气工程学院，上海 201600

2.上海工程技术大学 管理学院，上海 201600

1 引言

蚁群优化算法自1992年由意大利学者Dorigo提出来较优地解决了组合优化问题，引起了专家学者的重视。该算法模拟自然界蚂蚁的觅食行为，即蚂蚁从巢穴出发利用前一批次的蚂蚁释放的信息素选取到达目标点的最优路径。过去一些年中，专家学者在蚂蚁系统的基础上对蚁群算法进行了一系列的改进，从而能够更好地应用到组合优化的问题中[1-4]。在这些改进中主要有三个方向：其一是单种群蚁群算法内部机制的改进[5-7]；其二是蚁群算法与其他算法的结合[8-9]；其三是多种群机制的改进[10-14]。在蚁群算法研究过程中，一个很重要的测试算法性能的基准即是旅行商问题。在TSP（traveling salesman problem）中，旅行商从所有城市列表中选择任一城市作为出发点，不重复地访问每个城市，最后回到出发点。

自然界中的生存准则：“物竞天择，适者生存”。生物通过这种方式衍生下去。蚂蚁则是根据生存环境形成了一种具有分工性质的群体合作方式，从而提高群体的生存技能。有人根据蚂蚁的自然合作行为，提出了多种群蚁群算法。Gambardella等[10]在解决带时间窗的车辆路径问题（vehicle routing problem with time windows，VRPTW）上，提出了MACS-VRPTW（multiple ant colony system for vehicle routing problems with time windows），该算法定义了两个蚁群系统（ant colony system，ACS），其中种群ACS-VEI旨在减少车辆的使用数量，ACS-TIME旨在优化ACS-VEI找到的可行解的时间，两个种群通过信息素的更新交换信息，通过实验得出该算法从解的质量和求解时间上来看，比单种群更具有优势。……