蚁群优化算法

蚁群优化算法目录 [隐藏] 比较1 2蚁群算法的提出： 人工蚂蚁与真实蚂蚁的异同o o     3 4 5 6 72.1 2.2相同点比较 不同点比较蚁群算法的流程图 基本蚁群算法的实现步骤 蚁群算法的 matlab 源程序 蚁群算法仿真结果 版权声明[编辑]蚁群算法的提出：人类认识事物的能力来源于与自然界的相互作用，自然界一直是人类创造力 的源泉。 自然界有许多自适应的优化现象不断地给人以启示，生物和自然中的生 态系 统可以利用自身的演化来让许多在人类看来高度复杂的优化问题得到几乎完美 的解决。近些年来，一些与经典的数学问题思想不同的，试图通过模拟自然生态 系统 来求解复杂优化问题的仿生学算法相继出现，如蚁群算法、遗传算法、粒子群算 法等。 这些算法大大丰富了现在优化技术，也为那些传统最优化技术难以处理的 组 合优化问题提供了切实可行的解决方案。 生物学家通过对蚂蚁的长期的观察发现，每只蚂蚁的智能并不高，看起来没 有集中的指挥，但它们却能协同工作，集中事物，建起坚固漂亮的蚁穴并抚养后 代， 依靠群体能力发挥出超出个体的智能。 蚁群算法是最新发展的一种模拟昆虫王国 中蚂蚁群体智能行为的仿生优化算法，它具有较强的鲁棒性、优良的分布式计算 机 制、易于与其他方法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，国 内外的相关研究还处于实验阶段， 但是目前人们对蚁群算法的研究已经由当初单 一 的旅行商问题(TSP)领域渗透到了多个应用领域，由解决一维静态优化问题发展 到解决多维动态组合优化问题， 由离散域范围内的研究逐渐扩展到了连续域范围 内的

研究，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。[编辑]人工蚂蚁与真实蚂蚁的异同比较[编辑]相同点比较蚁群算法是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的，其很多 观点都来源于真实蚁群， 因此算法中所定义的人工蚂蚁与真实蚂蚁存在如下共同 点。 （1）都存在一个群体中个体相互交流通信的机制 人工蚂蚁和真实蚂蚁都存在一种改变当前所处环境的机制：真实蚂蚁在经过 的路径上留下信息素， 人工蚂蚁改变在其所经路径上存储的数字信息，该信息就 是算 法中所定义的信息量， 它记录了蚂蚁当前解和历史解的性能状态，而且可被其他 后继人工蚂蚁读写。蚁群的这种交流方式改变了当前蚂蚁所经路径周围的环境， 同 时也以函数的形式改变了整个蚁群所存储的历史信息。通常，在蚁群算法中有一 个挥发机制，它像真实的信息量挥发一样随着时间的推移来改变路径上的信息 量。 挥发机制使得人工蚂蚁和真实蚂蚁可以逐渐地忘却历史遗留信息， 这样可使蚂蚁 在选择路径时不局限于以前蚂蚁所存留的“经验”。 （2）都要完成一个相同的任务 人工蚂蚁和真实蚂蚁都要完成一个相同的任务，即寻找一条从源节点（巢穴） 到目的节点（食物源）的最短路径。人工蚂蚁和真实蚂蚁都不具有跳跃性，只能 在 相邻节点之间一步步移动， 直至遍历完所有城市。为了能在多次寻路过程中找到 最短路径，则应该记录当前的移动序列。 （3）利用当前信息进行路径选择的随机选择策略 人工蚂蚁和真实蚂蚁从某一节点到下一节点的移动都是利用概率选择策略实 现的， 概率选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信 息。 因此，人工蚂蚁和真实蚂蚁所使用的选择策略在时间和空间上都是局部的。[编辑]不同点比较在从真实蚁群行为获得启发而构造蚁群算法的过程中，人工蚂蚁还具备了真 实蚂蚁所不具备的一些特性： （1）人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个 状态的转换； （2）人工蚂蚁具有一个记忆其本身过去行为的内在状态； （3）人工蚂蚁存在于一个与时间无关联的环境中；

（4）人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发。例如有的问 题中人工蚂蚁在产生一个解后改变信息量，但无论哪种方法，信息量的更新并不 是随 时都可以进行的； （5）为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局 部优化、回退等，这些行为在真实蚂蚁中是不存在的。在很多具体应用中，人工 蚂蚁 可在局部优化过程中相互交换信息， 还有一些改进蚁群算法中的人工蚂蚁可实现 简单预测。[编辑]蚁群算法的流程图

[编辑]基本蚁群算法的实现步骤

以 TSP 为例，基本蚁群算法的具体实现步骤如下： （1）参数初始化。令时间 t=0 和循环次数 τ=0，设置最大循环次数 Nc=0，将 m 只蚂蚁置于 n 个元素（城市）上，令有向图上每条边（i，j）的初始化信息量 τij(t) = const，其中 const 表示常数，且初始时刻 Δτij(0) = 0 。（2）循环次数。（3）蚂蚁的禁忌表索引号 k=1。 （4）蚂蚁数目 。 （5）蚂蚁个体根据状态转移概率公式计算的概率选择元素（城市）j 并前进， 。其中， 表示在 t 时刻蚂蚁 k 由元素（城市）i 转移到元素（城市）j 的状态转 移概率。 allowedk = C − tabuk 表示蚂蚁 k 下一步允许选择的城市。 α 为启发式因 子， 表示轨迹的相对重要性， 反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所 起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁 经过的路径，蚂蚁之间的协作性越强。β 为期望启发式因子，表示能见度的相对 重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重 视程度，其值越大，则该状态转移概率越接近于贪心规则；ηij(t) 为启发函数， 表达式为 。式中，dij 表示相邻两个城市之间的距离。（6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素（城市），并把该 元素（城市）移动到该蚂蚁个体的禁忌表中。 （7） 若集合 C 中元素（城市）未遍历完，即 k

[编辑]蚁群算法的matlab 源程序1.蚁群算法主程序：main.m%function [bestroute,routelength]=Ant clc clear tic % 读入城市间距离矩阵数据文件 CooCity = load( 'CooCity.txt' ) ;% 城市网络图坐标数据文件，txt 形式给 出 NC=length(CooCity); % 城市个数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCit y(j,3))^2); end end MAXIT=10;%最大循环次数 Citystart=[]; % 起点城市编号 tau=ones(NC,NC); % 初始时刻各边上的信息痕迹为 1 rho=0.5; % 挥发系数 alpha=1; % 残留信息相对重要度 beta=5; % 预见值的相对重要度 Q=10; % 蚁环常数 NumAnt=20; % 蚂蚁数量 routelength=inf; % 用来记录当前找到的最优路径长度 for n=1:MAXIT for k=1:NumAnt %考查第 K 只蚂蚁 deltatau=zeros(NC,NC); % 第 K 只蚂蚁移动前各边上的信息增量为 零 %[routek,lengthk]=path(distance,tau,alpha,beta,[]); % 不靠率起始点 [routek,lengthk]=path(distance,tau,alpha,beta,Citystart); 始点 if lengthk

deltatau(routek(i),routek(i+1))=deltatau(routek(i),routek(i+1))+Q/len gthk; % 信息素更新 end %deltatau(routek(NC),1)=deltatau(routek(NC),1)+Q/lengthk; % end length_n(n)=routelength; % 记录路径收敛 tau=(1-rho).*tau; % 信息素挥发 end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% costtime=toc; subplot(1,2,1),plot([CooCity(bestroute,2)],[CooCity(bestroute,3)],'-* ') subplot(1,2,2),plot([1:MAXIT],length_n,'-*') [routelength,costtime]2.蚁群算法寻找路径程序：path.m% 某只蚂蚁找到的某条路径 routek,lengthk function [routek,lengthk]=path(distance,tau,alpha,beta,Citystart) [m,n]=size(distance); if isempty(Citystart) % 如果不确定起点 p=fix(m*rand)+1; % 随机方式初始化起点，均匀概率 else p=Citystart; % 外部给定确定起点 end lengthk=0; % 初始路径长度设为 0 routek=[p]; % 蚂蚁路径点序列，即该蚂蚁已经过的城市集合，路径初 始起点 for i=1:m-1 np=routek(end); % 蚂蚁路径城市序号，依次经过的城市编号 np_sum=0; % 路由长度初始为 0 for j=1:m if inroute(j,routek) % 判断城市节点 j 是否属于 tabuk，即 是否已经过 continue; else % j 为还未经过的点，对 ada=1/distance(np,j); % 预见度 np_sum=np_sum+tau(np,j)^alpha*ada^beta; % 路由表： 信息痕 迹、预见度 end end cp=zeros(1,m); % 转移概率，基于路径长度及路由表

for j=1:m if inroute(j,routek) continue; else ada=1/distance(np,j); % 预见度 cp(j)=tau(np,j)^alpha*ada^beta/np_sum; 率 end% np 到 j 的转移概end NextCity=nextcitychoose2(cp); % 根据转移概率确定下一个城市, % 直观地，取转移概率最大值方向方法，决策结果稳定且收敛快 routek=[routek,NextCity]; % 更新路径 lengthk=lengthk+distance(np,NextCity); % 更新路径长度 end[编辑]蚁群算法仿真结果

其中左边是蚂蚁行走的最短路径，右边是最短路径的值的收敛情况。

蚁群优化算法目录 [隐藏] 比较1 2蚁群算法的提出： 人工蚂蚁与真实蚂蚁的异同o o     3 4 5 6 72.1 2.2相同点比较 不同点比较蚁群算法的流程图 基本蚁群算法的实现步骤 蚁群算法的 matlab 源程序 蚁群算法仿真结果 版权声明[编辑]蚁群算法的提出：人类认识事物的能力来源于与自然界的相互作用，自然界一直是人类创造力 的源泉。 自然界有许多自适应的优化现象不断地给人以启示，生物和自然中的生 态系 统可以利用自身的演化来让许多在人类看来高度复杂的优化问题得到几乎完美 的解决。近些年来，一些与经典的数学问题思想不同的，试图通过模拟自然生态 系统 来求解复杂优化问题的仿生学算法相继出现，如蚁群算法、遗传算法、粒子群算 法等。 这些算法大大丰富了现在优化技术，也为那些传统最优化技术难以处理的 组 合优化问题提供了切实可行的解决方案。 生物学家通过对蚂蚁的长期的观察发现，每只蚂蚁的智能并不高，看起来没 有集中的指挥，但它们却能协同工作，集中事物，建起坚固漂亮的蚁穴并抚养后 代， 依靠群体能力发挥出超出个体的智能。 蚁群算法是最新发展的一种模拟昆虫王国 中蚂蚁群体智能行为的仿生优化算法，它具有较强的鲁棒性、优良的分布式计算 机 制、易于与其他方法相结合等优点。尽管蚁群算法的严格理论基础尚未奠定，国 内外的相关研究还处于实验阶段， 但是目前人们对蚁群算法的研究已经由当初单 一 的旅行商问题(TSP)领域渗透到了多个应用领域，由解决一维静态优化问题发展 到解决多维动态组合优化问题， 由离散域范围内的研究逐渐扩展到了连续域范围 内的

研究，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。[编辑]人工蚂蚁与真实蚂蚁的异同比较[编辑]相同点比较蚁群算法是从自然界中真实蚂蚁觅食的群体行为得到启发而提出的，其很多 观点都来源于真实蚁群， 因此算法中所定义的人工蚂蚁与真实蚂蚁存在如下共同 点。 （1）都存在一个群体中个体相互交流通信的机制 人工蚂蚁和真实蚂蚁都存在一种改变当前所处环境的机制：真实蚂蚁在经过 的路径上留下信息素， 人工蚂蚁改变在其所经路径上存储的数字信息，该信息就 是算 法中所定义的信息量， 它记录了蚂蚁当前解和历史解的性能状态，而且可被其他 后继人工蚂蚁读写。蚁群的这种交流方式改变了当前蚂蚁所经路径周围的环境， 同 时也以函数的形式改变了整个蚁群所存储的历史信息。通常，在蚁群算法中有一 个挥发机制，它像真实的信息量挥发一样随着时间的推移来改变路径上的信息 量。 挥发机制使得人工蚂蚁和真实蚂蚁可以逐渐地忘却历史遗留信息， 这样可使蚂蚁 在选择路径时不局限于以前蚂蚁所存留的“经验”。 （2）都要完成一个相同的任务 人工蚂蚁和真实蚂蚁都要完成一个相同的任务，即寻找一条从源节点（巢穴） 到目的节点（食物源）的最短路径。人工蚂蚁和真实蚂蚁都不具有跳跃性，只能 在 相邻节点之间一步步移动， 直至遍历完所有城市。为了能在多次寻路过程中找到 最短路径，则应该记录当前的移动序列。 （3）利用当前信息进行路径选择的随机选择策略 人工蚂蚁和真实蚂蚁从某一节点到下一节点的移动都是利用概率选择策略实 现的， 概率选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信 息。 因此，人工蚂蚁和真实蚂蚁所使用的选择策略在时间和空间上都是局部的。[编辑]不同点比较在从真实蚁群行为获得启发而构造蚁群算法的过程中，人工蚂蚁还具备了真 实蚂蚁所不具备的一些特性： （1）人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个 状态的转换； （2）人工蚂蚁具有一个记忆其本身过去行为的内在状态； （3）人工蚂蚁存在于一个与时间无关联的环境中；

（4）人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发。例如有的问 题中人工蚂蚁在产生一个解后改变信息量，但无论哪种方法，信息量的更新并不 是随 时都可以进行的； （5）为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局 部优化、回退等，这些行为在真实蚂蚁中是不存在的。在很多具体应用中，人工 蚂蚁 可在局部优化过程中相互交换信息， 还有一些改进蚁群算法中的人工蚂蚁可实现 简单预测。[编辑]蚁群算法的流程图

[编辑]基本蚁群算法的实现步骤

以 TSP 为例，基本蚁群算法的具体实现步骤如下： （1）参数初始化。令时间 t=0 和循环次数 τ=0，设置最大循环次数 Nc=0，将 m 只蚂蚁置于 n 个元素（城市）上，令有向图上每条边（i，j）的初始化信息量 τij(t) = const，其中 const 表示常数，且初始时刻 Δτij(0) = 0 。（2）循环次数。（3）蚂蚁的禁忌表索引号 k=1。 （4）蚂蚁数目 。 （5）蚂蚁个体根据状态转移概率公式计算的概率选择元素（城市）j 并前进， 。其中， 表示在 t 时刻蚂蚁 k 由元素（城市）i 转移到元素（城市）j 的状态转 移概率。 allowedk = C − tabuk 表示蚂蚁 k 下一步允许选择的城市。 α 为启发式因 子， 表示轨迹的相对重要性， 反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所 起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁 经过的路径，蚂蚁之间的协作性越强。β 为期望启发式因子，表示能见度的相对 重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重 视程度，其值越大，则该状态转移概率越接近于贪心规则；ηij(t) 为启发函数， 表达式为 。式中，dij 表示相邻两个城市之间的距离。（6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素（城市），并把该 元素（城市）移动到该蚂蚁个体的禁忌表中。 （7） 若集合 C 中元素（城市）未遍历完，即 k

[编辑]蚁群算法的matlab 源程序1.蚁群算法主程序：main.m%function [bestroute,routelength]=Ant clc clear tic % 读入城市间距离矩阵数据文件 CooCity = load( 'CooCity.txt' ) ;% 城市网络图坐标数据文件，txt 形式给 出 NC=length(CooCity); % 城市个数 for i=1:NC % 计算各城市间的距离 for j=1:NC distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCit y(j,3))^2); end end MAXIT=10;%最大循环次数 Citystart=[]; % 起点城市编号 tau=ones(NC,NC); % 初始时刻各边上的信息痕迹为 1 rho=0.5; % 挥发系数 alpha=1; % 残留信息相对重要度 beta=5; % 预见值的相对重要度 Q=10; % 蚁环常数 NumAnt=20; % 蚂蚁数量 routelength=inf; % 用来记录当前找到的最优路径长度 for n=1:MAXIT for k=1:NumAnt %考查第 K 只蚂蚁 deltatau=zeros(NC,NC); % 第 K 只蚂蚁移动前各边上的信息增量为 零 %[routek,lengthk]=path(distance,tau,alpha,beta,[]); % 不靠率起始点 [routek,lengthk]=path(distance,tau,alpha,beta,Citystart); 始点 if lengthk

deltatau(routek(i),routek(i+1))=deltatau(routek(i),routek(i+1))+Q/len gthk; % 信息素更新 end %deltatau(routek(NC),1)=deltatau(routek(NC),1)+Q/lengthk; % end length_n(n)=routelength; % 记录路径收敛 tau=(1-rho).*tau; % 信息素挥发 end %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% costtime=toc; subplot(1,2,1),plot([CooCity(bestroute,2)],[CooCity(bestroute,3)],'-* ') subplot(1,2,2),plot([1:MAXIT],length_n,'-*') [routelength,costtime]2.蚁群算法寻找路径程序：path.m% 某只蚂蚁找到的某条路径 routek,lengthk function [routek,lengthk]=path(distance,tau,alpha,beta,Citystart) [m,n]=size(distance); if isempty(Citystart) % 如果不确定起点 p=fix(m*rand)+1; % 随机方式初始化起点，均匀概率 else p=Citystart; % 外部给定确定起点 end lengthk=0; % 初始路径长度设为 0 routek=[p]; % 蚂蚁路径点序列，即该蚂蚁已经过的城市集合，路径初 始起点 for i=1:m-1 np=routek(end); % 蚂蚁路径城市序号，依次经过的城市编号 np_sum=0; % 路由长度初始为 0 for j=1:m if inroute(j,routek) % 判断城市节点 j 是否属于 tabuk，即 是否已经过 continue; else % j 为还未经过的点，对 ada=1/distance(np,j); % 预见度 np_sum=np_sum+tau(np,j)^alpha*ada^beta; % 路由表： 信息痕 迹、预见度 end end cp=zeros(1,m); % 转移概率，基于路径长度及路由表

for j=1:m if inroute(j,routek) continue; else ada=1/distance(np,j); % 预见度 cp(j)=tau(np,j)^alpha*ada^beta/np_sum; 率 end% np 到 j 的转移概end NextCity=nextcitychoose2(cp); % 根据转移概率确定下一个城市, % 直观地，取转移概率最大值方向方法，决策结果稳定且收敛快 routek=[routek,NextCity]; % 更新路径 lengthk=lengthk+distance(np,NextCity); % 更新路径长度 end[编辑]蚁群算法仿真结果

其中左边是蚂蚁行走的最短路径，右边是最短路径的值的收敛情况。