高志娥　薛艳锋　兰静

摘要摘要：蚁群优化算法——蚂蚁系统（Ant System，AS）是Dorigo M在20世纪90年代最早提出的一种新型生物智能算法，Dorigo M将蚁群优化算法应用于解决经典的旅行商问题（TSP），取得了较好的应用效果。采用混合型蚁群算法进行优化求解，探讨其实现TSP问题的求解流程，以更好地指导实际问题解决。

关键词关键词：蚁群优化算法；混合型蚁群算法；TSP问题

DOIDOI：10.11907/rjdk.1431040

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2015）004007302

0引言

TSP是一个典型的NP完全问题，没有确定的算法能够在多项式时间内得到问题的解。因此，如何解决旅行商问题，具有很重要的实际应用意义与价值。

TSP问题：假设有n个城市，每一个城市看作一个点，城市的实际距离转化为点的距离，如何寻找一条遍历所有城市且每个城市只被访问一次的路径，并保证总路径距离最短。

其数学描述如下：

其中，K是V的全部非空子集，|K|是集合K中包含图G的全部顶点的个数。

1蚁群算法基本原理

蚁群算法是一种新型的模拟生物习性的智能进化算法。蚁群算法又简称ACO算法，蚁群在搜索食物源过程中，总是表现出极好的寻优路线，使得路程最短。蚁群算法模仿蚁群这一寻优能力特性，解决了很多离散系统优化问题。蚁群算法现已广泛应用于调度问题、旅行商问题（TSP问题）、指派问题、函数优化问题等，均取得了较好的应用效果[1]。

单只蚂蚁的行为比较简易，随机地在搜索区域内寻找食物，但由这样的单只蚂蚁组成的蚁群群体，则可以表现出极其复杂、信息共享的寻优能力，究其原因主要是因为蚂蚁个体之间的信息传递，称之为信息素（pheromone）。……