首页 > 法律常识

蚁优化算法原理及Matlab编程实现

更新时间:2024-11-07 06:37:57 阅读：评论：0

2022年8月1日发
(作者：环保工程专业承包叁级)

蚁优化算法原理及Matlab编程实现

蚁算法的提出：

人类认识事物的能力来源于与自然界的相互作用，自然界一直是人类创造力

的源泉。自然界有许多自适应的优化现象不断地给人以启示，生物和自然中的生

态系

统可以利用自身的演化来让许多在人类看来高度复杂的优化问题得到几乎完美

的解决。近些年来，一些与经典的数学问题思想不同的，试图通过模拟自然生态

系统

来求解复杂优化问题的仿生学算法相继出现，如蚁算法、遗传算法、粒子算

法等。这些算法大大丰富了现在优化技术，也为那些传统最优化技术难以处理的

组

合优化问题提供了切实可行的解决方案。

生物学家通过对蚂蚁的长期的观察发现，每只蚂蚁的智能并不高，看起来没

有集中的指挥，但它们却能协同工作，集中事物，建起坚固漂亮的蚁穴并抚养后

代，

依靠体能力发挥出超出个体的智能。蚁算法是最新发展的一种模拟昆虫王国

中蚂蚁体智能行为的仿生优化算法，它具有较强的鲁棒性、优良的分布式计算

机

制、易于与其他方法相结合等优点。尽管蚁算法的严格理论基础尚未奠定，国

内外的相关研究还处于实验阶段，但是目前人们对蚁算法的研究已经由当初单

一

的旅行商问题(TSP)领域渗透到了多个应用领域，由解决一维静态优化问题发展

到解决多维动态组合优化问题，由离散域范围内的研究逐渐扩展到了连续域范围

内的

研究，从而使这种新兴的仿生优化算法展现出勃勃生机和广阔的发展前景。

人工蚂蚁与真实蚂蚁的异同比较

相同点比较

蚁算法是从自然界中真实蚂蚁觅食的体行为得到启发而提出的，其很多

观点都来源于真实蚁，因此算法中所定义的人工蚂蚁与真实蚂蚁存在如下共同

点。

（1）都存在一个体中个体相互交流通信的机制

人工蚂蚁和真实蚂蚁都存在一种改变当前所处环境的机制：真实蚂蚁在经过

的路径上留下信息素，人工蚂蚁改变在其所经路径上存储的数字信息，该信息就

是算

法中所定义的信息量，它记录了蚂蚁当前解和历史解的性能状态，而且可被其他

后继人工蚂蚁读写。蚁的这种交流方式改变了当前蚂蚁所经路径周围的环境，

同

时也以函数的形式改变了整个蚁所存储的历史信息。通常，在蚁算法中有一

个挥发机制，它像真实的信息量挥发一样随着时间的推移来改变路径上的信息

量。

挥发机制使得人工蚂蚁和真实蚂蚁可以逐渐地忘却历史遗留信息，这样可使蚂蚁

在选择路径时不局限于以前蚂蚁所存留的“经验”。

（2）都要完成一个相同的任务

人工蚂蚁和真实蚂蚁都要完成一个相同的任务，即寻一条从源节点（巢穴）

到目的节点（食物源）的最短路径。人工蚂蚁和真实蚂蚁都不具有跳跃性，只能

在

相邻节点之间一步步移动，直至遍历完所有城市。为了能在多次寻路过程中到

最短路径，则应该记录当前的移动序列。

（3）利用当前信息进行路径选择的随机选择策略

人工蚂蚁和真实蚂蚁从某一节点到下一节点的移动都是利用概率选择策略实

现的，概率选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信

息。

因此，人工蚂蚁和真实蚂蚁所使用的选择策略在时间和空间上都是局部的。

不同点比较

在从真实蚁行为获得启发而构造蚁算法的过程中，人工蚂蚁还具备了真

实蚂蚁所不具备的一些特性：

（1）人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个

状态的转换；

（2）人工蚂蚁具有一个记忆其本身过去行为的内在状态；

（3）人工蚂蚁存在于一个与时间无关联的环境中；

（4）人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发。例如有的问

题中人工蚂蚁在产生一个解后改变信息量，但无论哪种方法，信息量的更新并不

是随

时都可以进行的；

（5）为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局

部优化、回退等，这些行为在真实蚂蚁中是不存在的。在很多具体应用中，人工

蚂蚁

可在局部优化过程中相互交换信息，还有一些改进蚁算法中的人工蚂蚁可实现

简单预测。

蚁算法的流程图

基本蚁算法的实现步骤

以TSP为例，基本蚁算法的具体实现步骤如下：

（1）参数初始化。令时间t=0和循环次数τ=0，设置最大循环次数

=0，将m

只蚂蚁置于n个元素（城市）上，令有向图上每条边

（i，j）的初始化信息量τ

(t)=const，其中const表示常数，且初始时刻Δτ

(0)=0。

（2）循环次数。

（3）蚂蚁的禁忌表索引号k=1。

（4）蚂蚁数目。

（5）蚂蚁个体根据状态转移概率公式计算的概率选择元素（城市）j并前进，

。

其中，表示在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转

移概率。allowed

=C−tabu

表示蚂蚁k下一步允许选择的城市。α为启发式因

子，

表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所

起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁

经过的路径，蚂蚁之间的协作性越强。β为期望启发式因子，表示能见度的相对

重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重

视程度，其值越大，则该状态转移概率越接近于贪心规则；η

(t)为启发函数，

表达式为。式中，d

表示相邻两个城市之间的距离。

（6）修改禁忌表指针，即选择好之后将蚂蚁移动到新的元素（城市），并把该

元素（城市）移动到该蚂蚁个体的禁忌表中。

（7）若集合C中元素（城市）未遍历完，即k

执行第（8）步。

（8）根据公式更新每条路径上的信息量：

(t+n)=(1−ρ)*τ

(t)+Δτ

(t)

（9）若满足结束条件，即如果循环次数，则循环结束并输出程序计算结果，

否则清空禁忌表并跳转到第（2）步。

]蚁算法的matlab源程序

1.蚁算法主程序：main.m

%function[bestroute,routelength]=Ant

clc

clear

tic

%读入城市间距离矩阵数据文件

CooCity=load('');%城市网络图坐标数据文件，txt形式给

出

C=length(CooCity);%城市个数

fori=1:C%计算各城市间的距离

forj=1:C

distance(i,j)=sqrt((CooCity(i,2)-CooCity(j,2))^2+(CooCity(i,3)-CooCit

y(j,3))^2);

end

MAXIT=10;%最大循环次数

Citystart=[];%起点城市编号

tau=ones(C,C);%初始时刻各边上的信息痕迹为1

rho=0.5;%挥发系数

alpha=1;%残留信息相对重要度

beta=5;%预见值的相对重要度

Q=10;%蚁环常数

umAnt=20;%蚂蚁数量

routelength=inf;%用来记录当前到的最优路径长度

forn=1:MAXIT

fork=1:umAnt%考查第K只蚂蚁

deltatau=zeros(C,C);%第K只蚂蚁移动前各边上的信息增量为

零

%[routek,lengthk]=path(distance,tau,alpha,beta,[]);%

不靠率起始点

[routek,lengthk]=path(distance,tau,alpha,beta,Citystart);%指定起

始点

iflengthk

:::routelength=lengthk;

:::bestroute=routek;

end

fori=1:C-1%第K只蚂蚁在路径上释放的信息量

deltatau(routek(i),routek(i+1))=deltatau(routek(i),routek(i+1))+Q/len

gthk;%信息素更新

end

%deltatau(routek(C),1)=deltatau(routek(C),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);

ifisempty(Citystart)%如果不确定起点

p=fix(m*rand)+1;%随机方式初始化起点，均匀概率

else

p=Citystart;%外部给定确定起点

end

lengthk=0;%初始路径长度设为0

routek=[p];%蚂蚁路径点序列，即该蚂蚁已经过的城市集合，路径初

始起点

fori=1:m-1

np=routek(end);%蚂蚁路径城市序号，依次经过的城市编号

np_sum=0;%路由长度初始为0

forj=1:m

ifinroute(j,routek)%判断城市节点j是否属于tabuk，即

是否已经过

continue;

else%j为还未经过的点，对

ada=1/distance(np,j);%预见度

np_sum=np_sum+tau(np,j)^alpha*ada^beta;%路由表：信息痕

迹、预见度

end

cp=zeros(1,m);%转移概率，基于路径长度及路由表

forj=1:m

ifinroute(j,routek)

continue;

留言与评论（共有 0 条评论）