基于蚁群算法的TSP问题研究

意大利学者Marco Dorigo, VManiezzo等人, 在观察蚂蚁觅食习性时发现, 蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现蚂蚁的这种群体协作是通过一种叫做信息素 (pheromone) 的化学物质进行通讯和协调的。蚂蚁在行走过程中会在经过的路径上散发化学物质信息素, 其它的蚂蚁会受信息素的吸引, 在随机行走过程中趋向信息素较高的路径, 整个蚁群通过这种信息素相互协作, 形成正反馈, 多个路径上的蚂蚁逐渐聚集到最短的那条路径上来。

由于蚂蚁寻找最短路径的习性与旅行商问题 (Traveling Salesman Problem, TSP) [1]有很大的相似性, 因此Dorigo首先将蚁群算法应用到求解该问题, 取得了不错的效果, 验证了蚁群算法是一种有效的优化工具。随着研究的深入, 蚁群算法应用到更多的领域, 为其问题的求解提供了新的方法。

1 TSP问题简述

旅行商问题 (TSP问题) 是组合优化的著名难题。它具有广泛的应用背景, 如计算机网络、电气布线、加工排序、通信调度等。业已经证明TSP问题是NP-C[2]难题, 鉴于其重要的工程与理论价值, TSP常作为算法性能研究的典型算例。TSP的最简单形象描述是:给定n个城市, 有一个旅行商从某一城市出发, 访问各城市一次且仅有一次后再回到原出发城市, 要求找出一条最短的巡回路径。TSP分为对称TSP和非对称TSP两大类, 若两城市往返距离相同, 则为对称TSP, 否则为非对称TSP。本文研究的是对称的TSP。

2 蚁群算法介绍

2.1 基本蚁群算法的原理

自然界中, 蚂蚁的食物源总是随机散布于蚁巢周围。只要仔细观察就可以发现, 经过一段时间后, 蚂蚁总能找到一条从蚁巢到食物源的最短路径。蚂蚁个体只有很简单的能力, 并且没有视觉, 却能在复杂的环境中找到最短路径, 生物学家研究发现, 这是蚂蚁群体协同工作的结果, 蚂蚁在其经过的路上留下一定数量的称为外激素的物质 (信息素) , 其它蚂蚁能检测到这些信息素, 一条路上的信息素越多, 其他蚂蚁将以越高的概率跟随这条路径, 从而这条路径上的信息素会被加强, 引导越来越多的蚂蚁跟随这条路径。

2.2 基本蚁群算法的模型

平面上n个城市的旅行商问题 (TSP) 就是找一个环游, 使得经过每个城市一次且仅一次, 并且路径长度最短。为了描述方便, 下面引进一些记号令 () ib t表示t时刻在城市i的蚂蚁的个数是蚂蚁的总数, ijd表示城市i和城市j之间的距离, () ijτt表示t时刻在边 (i, j) 信息素的多少。

初始时刻, 各条边上的信息素相等, 设τij (0) =c (c为常数) , 把m只蚂蚁按一定规则分布在各城市。在t时刻m只蚂蚁各自选择t+l时刻要去的城市 (选择策略) , 直到t+n时刻时m只蚂蚁各自完成一个环游, 再根据各自环游的长度在其经过的边上留下一定数量的信息素。原则是越短环游留下越多的信息素, 同时, 各边上的信息素也蒸发掉一部分。信息素更新结束后, 开始下一轮迭代。在t时刻, 位于城市i的蚂蚁k以概率pkij (t) 选择下一个要去的城市j:

其中ηij表示由城市i转移到城市j的期望程度, 可根据具体问题具体确定, 这里ηij=1/dij。τij (t) 是在t时刻时边 (i, j) 上的信息素的数量, α, β是参数, 表示两者的重要程度。allowedk={0, 1, 2, n-1) -tabuk表示蚂蚁k下一步允许选择的城市, tabuk用来记录蚂蚁k到目前为止走过的城市, 集合tabuk随着进化过程作动态调整, 经过n个时刻, m只蚂蚁各自完成一个环游, 根据下式更新各边上的信息素:

其中

其中∆τij (t) 是第k只蚂蚁在边 (i, j) 上留下的信息素的数量, 按下式计算:

其中Q是一个常数, 是一个影响算法收敛的参数, kL是蚂蚁k的环游长度。ρ是一个常数, 0

在ant-density模型中,

3 算法实现及TSP问题求解

3.1 Scilab简介

本算法实现选用软件是Scilab-4.0。Scilab (Scientific Laboratory) 是以法国国立信息与自动化研究院 (INRIA) 的科学家为主共同开发的“开放源码”式科学计算软件。

Scilab[3]是一个科学计算软件, 它主要有两个功能:数值计算和计算结果可视化。Scilab数据类型丰富, 可以很方便地实现各种矩阵运算Scilab也能处理比数字矩阵复杂得多的对象。Scilab具有功能丰富的图形显示能力, 可完成各种常规形式的计算结果可视化功能。

3.2 基本蚁群算法的实现步骤

以TSP为目标, 基本蚁群算法的具体实现步骤如下。

(1) 参数初始化。令时间t=0和循环次数Nc=0, 设置最大循环次数Ncmax, 将m蚂蚁置于n个元素 (城市) 上, 令有向图上每条边 (i, j) 的初始化信息量τij (t) =const, 其中const表示常数, 且初始时刻∆τij (0) =0。

(2) 循环次数Nc←Nc+1。

(3) 蚂蚁的禁忌表索引号k=1。

(4) 蚂蚁数目k←k+1。

(5) 蚂蚁个体概据本文第三章状态转移概率公式 (1) 计算的概率选择元素 (城市) j前进, j∈{C-tabuk}。

(6) 修改禁忌表指针, 即选择好之后将蚂蚁移动到新的元素 (城市) , 并把该元素 (城市) 移动到该蚂蚁个体的禁忌表中。

(7) 若集合C中的元素 (城市) 未遍历完, 即k

(8) 根据公式 (2) 和公式 (3) 更新每条路径上的信息量。

(9) 若满足结束条件, 即如果循环次数Nc Ncmax, 则循环结束并输出程序计算结果, 否则清空禁忌表并跳转到第 (2) 步。

3.3 程序界面设计

为了提高程序的通用性和易用性, 在程序实现的的过程中为程序设计了图形界面进行封装。如图1主界面设计编辑框接受算法运行所需参数的输入, 按钮Display Setting设置程序结果显示, Load Data按钮用来通过文本导入TSP问题的城市数据。所有参数设置完成后, 设置Run按钮开始运行程序, 运行结束后输出结果 (如图2) 。

4 研究展望

本文研究了基本蚁群算法的原理, 分析了TSP的应用领域, 以及解决TSP的方法。然后建立了蚂蚁算法的模型, 给出算法实现流程, 并实现了采用蚂蚁算法解决TSP问题。本文实现的是基本的蚁群算法, 以后可以对蚁群算法的优化问题进行研究。同时, 蚁群算法的应用是十分广泛的, 可以根据自身高校的工作环境, 研究蚁群算法在解决排课问题方面的应用。

摘要：蚁群算法是一种新型的优化算法, 于20世纪90年代提出, 最早成功应用于解决旅行商问题。研究表明, 蚁群算法有着极强的鲁棒性发现较好解的能力。本文介绍了蚁群算法原理和TSP问题, 通过Scilab编程实现了用蚁群算法解决旅行商问题。

关键词：蚁群算法,旅行商问题,Scilab,组合优化

参考文献

[1] Dorigo M, Gambardella L M.Ant colony systern:A cooperative learning approach to the traveling salesman problem[J].IEEE Trans Evolutionary Computation, 1997, 1 (1) :53～66.

[2] 陈志平, 徐宗本.计算机数学[M].北京:科学出版社, 2001.

[3] 胡包钢.SCILAB教程[M].清华大学出版社, 2003, 1:209.

[4] 段海滨, 蚁群算法原理及其应用[M].科学出版社, 2005, 12:29～34.