蚁算法简介及matlab源代码
1 蚁算法原理
⾃1991年由意⼤利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁觅⾷⾏为提出了⼀种基于种的模拟进化算法——蚁优化。该算法的出现引起了学者们的极⼤关注，蚁算法的特点：
① 其原理是⼀种正反馈机制或称增强型学习系统; 它通过【最优路径上蚂蚁数量的增加→信息素强度增加→后来蚂蚁选择概率增⼤→最优路径上蚂蚁数量更⼤增加】达到最终收敛于最优路径上L
② 它是⼀种通⽤型随机优化⽅法, 它吸收了蚂蚁的⾏为特(内在搜索机制) , 它是使⽤⼈⼯蚂蚁仿真(也称蚂蚁系统) 来求解问题L但⼈⼯蚂蚁决不是对实际蚂蚁的⼀种简单模拟, 它融进了⼈类的智能L⼈⼯蚂蚁有⼀定的记忆; ⼈⼯蚂蚁不完全是瞎的; ⼈⼯蚂蚁⽣活的时空是离散的L
③ 它是⼀种分布式的优化⽅法, 不仅适合⽬前的串⾏计算机, ⽽且适合未来的并⾏计算机L
④ 它是⼀种全局优化的⽅法, 不仅可⽤于求解单⽬标优化问题, ⽽且可⽤于求解多⽬标优化问题L
⑤ 它是⼀种启发式算法, 计算复杂性为o (Nc*n2*m) , 其中Nc 是迭代次数, m 是蚂蚁数⽬, n 是⽬的节点数⽬L
蚁发现最短路径的原理和机制[1]
下⾯⽤图 1解释蚁发现最短路径的原理和机制。
如图 1(a)所⽰，在蚁巢和⾷物源之间有两条道路 Nest-A-B-D-Food 和Nest-A-C-D-Food，其长度分别为 4 和 6。单位时间内蚂蚁可移动⼀个单位长度的距离。开始时所有路径上都没有外激素。
如图 1(b)，在 t=0 时刻，20 只蚂蚁从蚁巢出发移动到 A。由于路径上没有外激素，它们以相同概率选择左侧或右侧道路，因此平均有 10 只蚂蚁⾛左侧，另外 10 只⾛右侧。
如图 1(c)，在 t=4 时刻，第⼀组先到达⾷物源的蚂蚁将折回。
如图 1(d)，在 t=5 时刻，两组蚂蚁将在 D 点相遇。此时 BD 上的外激素数量与 CD 上的相同，因此返回的 10 只蚂蚁中有 5 只选择BD ⽽另 5 只选择 CD。
如图 1(e)，在 t=8 时刻，前 5 个蚂蚁将返回巢⽳，⽽在 AC、CD 和 AB 上各有 5 个蚂蚁。
如图 1(f)，在 t=9 时刻，前 5 个蚂蚁⼜回到 A 并且再次⾯对往左还是往右的选择。这时，AB 上的轨迹数是 20 ⽽ AC 上是 15，因此将有较为多数的蚂蚁选择往右，从⽽增强了 AB 上外激素的量。随着该过程的继续，两条道路上外激素数量的差距将越来越⼤，直⾄绝⼤多数蚂蚁都选择了最短的路径。正是由于⼀条道路要⽐另⼀条道路短，因此，在相同的时间间隔内，短的路线会有更多的机会被选择。
根据仿⽣学家的研究结果，蚂蚁凭借路径寻优的能⼒能够到蚁巢与⾷物之间的最短路径，其原理在于：蚂蚁在所经过的路径上留下⼀种挥发性分泌物(pheromone，以下称为信息素)，信息素随着时间的推移会逐渐挥发消失.蚂蚁在觅⾷过程中能够感知这种物质的存在及其强度，并以此来指导⾃⼰的运动⽅向，倾向于朝着这种物质强度⾼的⽅向移动，即选择该路径的概率与当时这条路径上该物质的强度成正⽐.信息素强度越⾼的路径，选择它的蚂蚁就越多，则在该路径上留下的信息素的强度就更⼤,⽽强度⼤的信息素⼜吸引更多的蚂蚁，从⽽形成⼀种正反馈.通过这种正反馈，蚂蚁最终可以发现最佳路径，导致⼤部分的蚂蚁都会⾛此路径.
以求解ｎ个城市的ＴＳＰ旅⾏商问题为例说明ＡＣＡ模型.
设蚁中蚂蚁的数量为ｍ,ｄij (ｉ,ｊ=1,2,…,ｎ)表⽰城市ｉ和城市ｊ之间的距离,ｂi(ｔ)表⽰ｔ时刻位于城市ｉ的蚂蚁的个数，则有 表⽰ｔ时刻在城市ｉ,ｊ连线上残留的信息量.初始时刻，各条路径上信息量相等，设τｉｊ(0)=Ｃ(Ｃ为常数).蚂蚁ｋ(ｋ=1,2,…,ｍ)在运动过程中，根据各条路径上的信息量决定转移⽅向. 表⽰在ｔ时刻蚂蚁ｋ由城市ｉ转移到城市ｊ的概率.
（1）
残留信息的重要程度;β——启发信息的重要程度;tabuk——记录蚂蚁ｋ当前所⾛过的城市，称为记忆列表,ｋ=1,2,…,ｍ，集合tabuk随着进化过程作动态调整.经过ｎ个时刻，所有蚂蚁都完成了⼀次遍历.此
时，计算每⼀只蚂蚁所⾛过的路径Ｌｋ，并保存最短路径Ｌｍｉｎ=ｍｉｎ{Ｌｋ︱ｋ=1,2,…,ｍ}.在蚂蚁完成⼀次循环以后，各路径上的信息量进⾏如下调整
τｉｊ(ｔ+1)=(1-ρ)τｉｊ(ｔ)+Δτｉｊ    (2)
式中ρ∈(0,1)，表⽰信息素τｉｊ(ｔ)随时间的推移⽽衰减的程度.所以1-ρ为信息素残留因⼦，开始时Δτｉｊ（0）=0，
信息素增量Δτｉｊ可表⽰            (3)
式中Δτｋｉｊ为蚂蚁ｋ在本次循环中在城市ｉ和ｊ之间留下的信息量，它的计算公式根据具体问题⽽定.Dorigo曾给出Δτｋｉｊ3种不同的模型，分别称为Ant-Cycle模型、Ant-Quantity模型、Ant-Density模型，它们的区别就在于信息素的更新机制，即其差别在于Δτｋｉｊ
在Ant-Cycle模型中：
（4） 式中，Q表⽰信息素强度，它在⼀定程度上影响算法的收敛速度；Lk表⽰第K只蚂蚁在本次循环中所奏路径的总长度。
在Ant-Quantity模型中：
（5） 式中，Q表⽰信息素强度，它在⼀定程度上影响算法的收敛速度；dij表⽰第K只蚂蚁在t和t+1之间经过的（ i, j ）
在Ant-Density模型中：
（6） 区别：式(5)式(6)中利⽤的是局部信息，即蚂蚁完成⼀步后更新路径上的信息素；⽽式(4)中利⽤的是整体信息，即蚂蚁完成⼀个循环后所有路径上的信息素。经过⼤量试验总结研究，采⽤式(4)性能较好，所以 Ant-Cycle模型是最优的。
以上说明了信息素残留因⼦1-ρ、信息启发式因⼦α、期望启发式因⼦β、信息素强度Q、蚂蚁数⽬M等都是⾮常重要的参数，其选区⽅式和选区原则直接影响到蚁算法的全局收敛性和求解效率。我们学习到这种“三步⾛”[2]选择蚁算法最优组合参数的有效⽅法：
（1） 确定蚂蚁数⽬M，根据 城市规模 / 蚂蚁数⽬ ≈1.5的选择策略来确定蚂蚁的总数⽬。
（2） 参数粗调，即调整数值范围较⼤的信息启发式因⼦α、期望启发式因⼦β、信息素强度Q等参数，已得到较理想的解。
（3） 参数微调，即调整数值范围较⼩的信息素残留因⼦1-ρ。
2 ⽬前蚁算法的应⽤
虽然对蚁算法的研究时间不长, 但是初步研究已显⽰出它在求解复杂优化问题⽅⾯具有很⼤的优势, 特别是1998 年在⽐利时布鲁塞尔专门召开了第⼀届蚂蚁优化国际研讨会后, 现在每两年召开⼀次这样的蚂蚁优化国际研讨会。这标志着蚁算法的研究已经得到了国际上的⼴泛⽀持，使得这种新兴的智能进化仿⽣算法展现出了勃勃⽣机[3]。
以蚁算法为代表的体智能已成为当今分布式⼈⼯智能研究的⼀个热点，许多源于蜂和蚁模型设计的算法已越来越多地被⽤于企业的运转模式的研究。美国五⾓⼤楼正在资助关于体智能系统的研究⼯作--体战略(SWARM STRATEGY)，它的⼀个实战⽤途是通过运⽤成的空中⽆⼈驾驶飞⾏器和地⾯车辆来转移敌⼈的注意⼒，让⾃⼰的军队在敌⼈后⽅不被察觉地安全⾏进。英国电信公司和美国世界通信公司以电⼦蚂蚁为基础，对新的电信⽹络管理⽅法进⾏了试验。体智能还被应⽤于⼯⼚⽣产计划的制定和运输部门的后勤管理。美国太平洋西南航空公司采⽤了⼀种直接源于蚂蚁⾏为研究成果的运输管理软件，结果每年⾄少节约了1000万美元费⽤开⽀。英国联合利华公司已率先利⽤体智能技术改善其⼀家⽛膏⼚的运转状况。美国通⽤汽车公司，法国液⽓公司，荷兰公路交通部和美国⼀些移民事务机构也都采⽤这种技术来改善其运转的机能。⼜如美国MCIWorld公司⼀直研究⼈⼯蚂蚁，并⽤于管理公司的电话⽹，对⽤户记账收费等⼯作。另外，还设计“⼈⼯蚂蚁”打算⽤于因特⽹的路由管理。鉴于体智能⼴阔的应⽤前景，美国和欧洲联盟均于近⼏年开始出资资助基于体智能模拟的相关研究项⽬, 关在⼀些院校开设体智能的相关课程.⽜津⼤学出版社1999年版的E.Bonabeau
国内源代码网站
和M.Dorigo等⼈编写的专著《体智能：从⾃然到⼈⼯系统》(Swarm Intelligence:From Natural to Artificial System)，以及2001年出版的J.Kennedy和R.Eberhart编著的《体智能》(Swarm Intelligence)进⼀步扩⼤了体智能的影响.IEEE进化计算会刊也于2002年8⽉出版了蚁优化算特刊。国内也有研究者⽤蚂蚁算法求解全国144个城市的最短回路问题，求得的解同其它⽅法求到得解⼀样精确，这说明蚂蚁算法不但是求解组合优化问题的可⾏⽅法，⽽且是⼀种很有竞争⼒的算法。国家⾃然科学基⾦"⼗五"期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了体智能领域的进化,⾃适应与现场认知主题[4]。⽽且从1999年开始，⼏乎每年都会有⼏项相关项⽬获得资助。蚁算法是⼀种新型的模拟进化算法，其在数据挖掘中的应⽤正逐步引起⼈们的关注。⽬前，⼈⼯蚁在知识发现的过程中主要⽤于发掘聚类模型和分类模型。
2．1蚁算法在数据挖掘中的应⽤
聚类是将⼀组对象分成若⼲个体，每个体构成⼀个簇，使得簇内的对象尽可能具有最⼤的相似性，不同簇之间的对象尽可能有最⼤的相异性。⽬前，聚类⽅法主要有K均值法，模糊聚类、神经⽹络聚类、基于遗传算法的聚类、⼩波变换聚类以及将这些算法有效结合⽽形成的改进⽅法。随着蚁算法研究的兴起，⼈们发现在某些⽅⾯采⽤蚁模型进⾏聚类更加接近实际的聚类问题。将蚁算法⽤于聚类分析，灵感源于蚂蚁堆积他们的⼫体和分类他们的幼体。基于蚁算法的聚类⽅法从原理上可分为两种：⼀种是基于蚁堆形成原理来实现数据聚类，另⼀种是运⽤蚂蚁觅⾷的原理，利⽤信息来实
现聚类分析。
⽽数据是数据挖掘的另⼀个重要主题，它是在数据库对象集合中寻属性，并根据分类模式将其划分为不同类别的过程。分类过程利⽤历史数据记录⾃动推导出对给定数据的分类树。分类器构造⽅法有统计学⽅法、机器学习法、神经⽹络、决策树等。从知识发现的观点来看，分类规则的表达⽅式形如if<；条件>then<；类>规则前件（if 部分）包含⼀组条件集合，⼀般由逻辑连接符连接；规则结论（then部分）定义了样本的预测类，这些样本的预测属性满⾜规则前件所定义的所有条件[5]。将蚁算法引⼊分类规则的发现，是利⽤蚁觅⾷原理在数据库中进⾏搜索，对随机产⽣的⼀组规则进⾏选择优化，直到数据库能被该组规则覆盖，从⽽挖掘出隐含在数据库中的规则，建⽴最优的分类模型。蚁算法搜索的初始条件为发现规则的集合为空，且训练集包含所有的训练样本。蚂蚁搜索⼀次要完成规则⽣成、规则剪枝、信息素更新三个任务。⼀次搜索⽣成⼀条规则，并且将这条规则加⼊发现规则集合，同时将该条规则所覆盖的训练样本从训练集中删除。如果未覆盖训练样本的数⽬⼤于⽤户定义的阈值，即最⼤未覆盖样本数，就反复执⾏上述过程，最终算法将得到⼀组最优分类规则集合[5]。
最早在这⼀领域开展⼯作的是Deneubourg 等[6]，他们根据数据对象与其周围对象的相似性，让蚂蚁随机地移动、拾起或放下数据对象，以达到聚类数据的⽬的，这个基本模型已成功地应⽤于机器⼈领域。Lumer 等⾸先改进此算法，提出了LF算法。Wu 等、Ramos等、Yang等[7]从不同⾓度对LF算法进⾏了改进，在⽤蚁算法进⾏聚类分析⽅⾯取得了⼀定成效。近⼏年，学者在这⽅⾯的研究从来没
有间断过，也取得了⼀定的研究成果。
2．2 结论
不过，将蚁算法运⽤于数据发掘还存在⼀些问题，需要进⼀步研究：
（1）如何将现实的挖掘任务转换成蚁求解的问题空间，并⽤适当的⽅式表达。如何定义“⼈⼯蚂蚁”以及蚂蚁间的⾮直接通信⽅式（如路径上的信息素、对象的分布状态等）的选择。
（2）如何建⽴正反馈机制，定义启发函数，递增地进⾏问题求解，并且使得到的解与问题定义中现实世界的情况相对应。
（3）基于蚁的算法要初始化⼤量的参数，这些参数的选择会对算法的性能产⽣较⼤的影响，但其选取的⽅法和原则⽬前尚⽆理论上的依据，只能通过多次实验调优，因此参数的最佳设置原则还有待进⼀步研究。
（4）蚁算法的搜索时间较长，如何将蚁算法与遗传算法、免疫算法等优化算法相结合，改善和提⾼算法性能，以适应海量数据库的知识发现。
所以如何在数据挖掘中运⽤蚁算法快速、⾼效地获得⾼质量的知识越来越受到⼈们的关注，逐渐成为近期的研究热点[5]。
以下是解放军信息⼯程⼤学⼀个⽼师编的matlab程序，请尊重原作者劳动，引⽤时请注明出处。
我经过修改增加了注释，已经运⾏过，⽆误，
function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACATSP(C,NC_max,m,Alpha,Beta,Rho,Q)
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个城市的坐标，n×2的矩阵
%% NC_max 最⼤迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因⼦重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================
%%第⼀步：变量初始化
n=size(C,1);%n表⽰问题的规模（城市个数）
D=zeros(n,n);%D表⽰完全图的赋权邻接矩阵
for i=1:n
for j=1:n
if i~=j
D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
else
D(i,j)=eps;      %i=j时不计算，应该为0，但后⾯的启发因⼦要取倒数，⽤eps（浮点相对精度）表⽰end
D(j,i)=D(i,j);  %对称矩阵
end
end
Eta=1./D;          %Eta为启发因⼦，这⾥设为距离的倒数
Tau=ones(n,n);    %Tau为信息素矩阵
Tabu=zeros(m,n);  %存储并记录路径的⽣成
NC=1;              %迭代计数器，记录迭代次数
R_best=zeros(NC_max,n);      %各代最佳路线
L_best=inf.*ones(NC_max,1);  %各代最佳路线的长度
L_ave=zeros(NC_max,1);        %各代路线的平均长度
while NC<=NC_max        %停⽌条件之⼀：达到最⼤迭代次数，停⽌
%%第⼆步：将m只蚂蚁放到n个城市上
Randpos=[];  %随即存取
for i=1:(ceil(m/n))
Randpos=[Randpos,randperm(n)];
end
Tabu(:,1)=(Randpos(1,1:m))';    %此句不太理解？
%%第三步：m只蚂蚁按概率函数选择下⼀座城市，完成各⾃的周游
for j=2:n    %所在城市不计算
for i=1:m
visited=Tabu(i,1:(j-1)); %记录已访问的城市，避免重复访问
J=zeros(1,(n-j+1));      %待访问的城市
P=J;                      %待访问城市的选择概率分布
Jc=1;
for k=1:n
if length(find(visited==k))==0  %开始时置0
J(Jc)=k;
Jc=Jc+1;                        %访问的城市个数⾃加1
end
end
%下⾯计算待选城市的概率分布
for k=1:length(J)
P(k)=(Tau(visited(end),J(k))^Alpha)*(Eta(visited(end),J(k))^Beta); end
P=P/(sum(P));
%按概率原则选取下⼀个城市
Pcum=cumsum(P);    %cumsum，元素累加即求和
Select=find(Pcum>=rand); %若计算的概率⼤于原来的就选择这条路线to_visit=J(Select(1));
Tabu(i,j)=to_visit;
end
end
if NC>=2
Tabu(1,:)=R_best(NC-1,:);
end
%%第四步：记录本次迭代最佳路线
L=zeros(m,1);    %开始距离为0，m*1的列向量
for i=1:m
R=Tabu(i,:);
for j=1:(n-1)
L(i)=L(i)+D(R(j),R(j+1));    %原距离加上第j个城市到第j+1个城市的距离end
L(i)=L(i)+D(R(1),R(n));      %⼀轮下来后⾛过的距离
end
L_best(NC)=min(L);          %最佳距离取最⼩
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:); %此轮迭代后的最佳路线
L_ave(NC)=mean(L);          %此轮迭代后的平均距离

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。