文档介绍：蚂蚁算法总结
摘要：蚂蚁算法是一种新的随机优化算法，它利用人工蚂蚁在其途经路上释放信息素寻优，体现了正反馈、分布式、多agent协同性和并行性等特点。目前，蚂蚁算法已从著名的旅行商问题和二次分配问题渗透到其它问题领域工件排序、车辆调3)它是一种分布式的优化方法，不仅适合目前的串行计算机，而且适合未来的并行计算机；(4) 可用于求解单目标优化问题，而且可用于求解多目标优化问题；(5)它是一种启发式算法，计算复杂性为0(NC • m • n)，其中NC为迭代次数，m为蚂蚁数目，n 为节点数目。
三、蚂蚁算法的求解步骤
首先规定一些符号的含义：
m-蚂蚁个数
n-结点个数
-边弧(i,j)的局部启发因子，一般取丄,d表示路径(i,j)的长度
ij d ij
ij
T -边弧(i,j)的信息素轨迹强度
ij
Atk -蚂蚁k于弧(i,j)上留下的单位长度轨迹信息素数量
ij
pk-蚂蚁k在结点i的转移概率，j是尚未访问的结点
ij
a -信息素轨迹的相对重要性(a $0)
B -边弧局部启发因子的相对重要性(B$0)
p -信息素轨迹的持久性(OW p W1), 1- p可理解为轨迹衰减度
Q-体现蚂蚁所留轨迹数量的一个常数
U-可行结点集合
Nk为第k只蚂蚁在第i结点出发下一步的可行结点集
i
T(K)-一个列表，用于记录第k只蚂蚁到目前为止已经访问的城市
以经典的旅行商问题为例，蚂蚁算法求解一般步骤如下：
第一步：初始化，NC u 0 (NC为搜索次数)，各t、AT等初始化；将m只 ij ij
蚂蚁置于 n 个结点上；
第二步：将各蚂蚁的初始出发点置于当前解集中；对每一只蚂蚁k(k=1,…, m),按概率P选择至下一个结点j上；将结点j置于当前解集中；
第三步：计算各蚂蚁的目标函数值Lk (k=1,…，m)；记录当前最好的值；第四步：按更新方程修改信息数轨迹强度；
第五步：对各边弧(i,j),置At = 0, NC u NC + I ；
ij
第六步：若搜索次数NC小于预定搜索次数，且无退化行为(即找到的都是相同的解),则转至第二步；
第七步：输入目前最好的解。
四、蚂蚁算法研究进展蚂蚁算法的研究集中在理论和应用研究两个方面。
(一)蚂蚁算法的应用研究
蚂蚁算法是一种鲁棒算法,把它在 TSP 问题中的经典原型经过少量改动就可以在很多情况下应用。例如：几乎不用对蚂蚁算法作任何改动就可以解决非对称 TSP问题(ATSP)；在TSP蚂蚁算法的基础上对T (t)的定义稍作改动，用最长加 k
工时间代替tk，就可以解决车间调度问题(JSP)。蚂蚁算法在解决其他如二次分配(QAP)、交通运输分配、作业排序、图形着色等问题上均有出色的表现。AS算法的传统应用主要集中在离散优化领域。近年来，蚂蚁算法的应用范围已经扩大到连续问题的求解： Bilchev 和 Parmee 等把蚂蚁算法的应用引人工程设计领域； WangLei 和 wuQidi 用 AS 算法求解线性系统优化问题和一维函数最值问题； ChenLing和Shengjie等利用AS算法求解非线性规划问题也是很有意义的尝试。
(二)蚂蚁算法的理论研究
1．Ant—Q 算法
首先出现的改进是