Python和Matlab怎么实现蚂蚁群算法求解最短路径(matlab,python,开发技术)

1 知识点

我们这一节知识点只讲蚁群算法求解最短路径步骤及流程。

1.1蚁群算法步骤

设蚂蚁的数量为m，地点的数量为n，地点i与地点j之间相距Dij，t时刻地点i与地点j连接的路径上的信息素浓度为Sij,初始时刻每个地点间路径上的信息素浓度相等。

蚂蚁k根据各个地点间连接路径上的信息素决定下一个目标地点，Pijk表示t时刻蚂蚁k从地点i转移的概率，概率计算公式如下：

上式中，为启发函数，，表示蚂蚁从地点i转移到地点j的期望程度；为蚂蚁k即将访问地点的集合，开始时中有n-1个元素（除出发地点），随时间的推移，蚂蚁每到达下一个地点，中的元素便减少一个，直至空集，即表示所有地点均访问完毕；a为信息素重要程度因子，值越大，表明信息素的浓度在转移中起到的作用越大，也就是说蚂蚁选择距离近的下一个地点的概率更大，β为启发函数重要程度因子。

蚂蚁在释放信息素的同时，每个地点间连接路径上的信息素逐渐消失，用参数

表示信息素的挥发程度。因此，当所有蚂蚁完成一次循环后，每个地点间连接路径上的信息素浓度需更新，也就是有蚂蚁路过并且留下信息素，有公式表示为：

其中，表示第k只蚂蚁在地点i与j连接路径上释放的信息素浓度；表示所有蚂蚁在地点i与j连接路径上释放的信息素浓度之和；Q为常数，表示蚂蚁循环一次所释放的信息素总量；Lk表示第k只蚂蚁经过路径的长度，总的来说，蚂蚁经过的路径越短，释放的信息素浓度越高，最终选出最短路径。

1.2蚁群算法程序

(1)参数初始化

在寻最短路钱，需对程序各个参数进行初始化，蚁群规模m、信息素重要程度因子α、启发函数重要程度因子β、信息素会发因子、最大迭代次数ddcs_max，初始迭代值为ddcs=1。

(2)构建解空间

将每只蚂蚁随机放置在不同的出发地点，对蚂蚁访问行为按照公式计算下一个访问的地点，直到所有蚂蚁访问完所有地点。

(3)更新信息素

计算每只蚂蚁经过的路径总长Lk,记录当前循环中的最优路径，同时根据公式对各个地点间连接路径上的信息素浓度进行更新。

(4)判断终止

迭代次数达到最大值前，清空蚂蚁经过的记录，并返回步骤(2)。

2 蚂蚁算法求解最短路径问题——Python实现

2.1 源码实现

智能优化算法—蚁群算法（Python实现）

2.2 ACA_TSP实现

补充知识点：scipy.spatial.distance.cdist

#============导入相关库=================importnumpyasnpfromscipyimportspatialimportpandasaspdimportmatplotlib.pyplotaspltfromsko.ACAimportACA_TSPnum_points=25points_coordinate=np.random.rand(num_points,2)#生成点的坐标distance_matrix=spatial.distance.cdist(points_coordinate,points_coordinate,metric='euclidean')#函数用于计算两个输入集合的距离defcal_total_distance(routine):num_points,=routine.shapereturnsum([distance_matrix[routine[i%num_points],routine[(i+1)%num_points]]foriinrange(num_points)])#=============ACA_TSP解决==================================aca=ACA_TSP(func=cal_total_distance,n_dim=num_points,size_pop=50,max_iter=200,distance_matrix=distance_matrix)best_x,best_y=aca.run()#=============可视化=======================fig,ax=plt.subplots(1,2)best_points_=np.concatenate([best_x,[best_x[0]]])best_points_coordinate=points_coordinate[best_points_,:]ax[0].plot(best_points_coordinate[:,0],best_points_coordinate[:,1],'o-r')pd.DataFrame(aca.y_best_history).cummin().plot(ax=ax[1])plt.show()

3蚂蚁算法求解最短路径问题——Matlab实现

3.1 流程图

3.2 代码实现

下表为一些坐标点，找出最短路线：

%蚁群算法寻找最短路径程序%%清空环境变量clearclc%%导入数据，导入方式，看个人习惯zuobiao=[13042312363913154177224437121399348815353326155632381229419610044312790438657030071970256217562788149123811676133269537151678391821794061237037802212367625784029283842632931342919083507236733942643343932012935324031403550254523572778282623702975];%%计算城市间相互距离n=size(zuobiao,1);%城市个数jl=zeros(n,n);%首先求得各个坐标点的距离，这里是矩阵初始化fori=1:nforj=1:nifi~=j%~=是不等于的意思，zuobiao矩阵中每行都有个坐标，坐标相减用i和j区分不同的坐标点，然后求两点距离jl(i,j)=sqrt(sum((zuobiao(i,:)-zuobiao(j,:)).^2));%上式运算如a=[2,2;1,1]=>a(1,:)-a(2,:)=>ans=11，然后1?+1?=2，最后开根号elsejl(i,j)=1e-4;%相等的点相减准确说是等于0的，这里设置成了一个很小的数，是为了避免后面程序运算出错endendend%%初始化参数m=50;%蚂蚁数量，视情况而定，坐标点多的话可以适当增加蚂蚁数量a=1;%信息素重要程度因子b=5;%启发函数重要程度因子r=0.1;%信息素挥发因子Q=1;%常数qfhs=1./jl;%启发函数,将jl矩阵中每个元素转化为倒数xxsjz=ones(n,n);%信息素矩阵初始化ljjl=zeros(m,n);%路径记录表矩阵初始化ddcs=1;%迭代次数初值ddcs_max=200;%最大迭代次数Lujin_best=zeros(ddcs_max,n);%各代最佳路径L_best=zeros(ddcs_max,1);%各代最佳路径的长度L_ave=zeros(ddcs_max,1);%各代路径的平均长度%%迭代寻找最佳路径whileddcs<=ddcs_max%在ddcs小于ddcs_max前，一直循环%%随机产生各个蚂蚁的起点start=zeros(m,1);fori=1:mtemp=randperm(n);%功能是随机打乱一个数字序列,也就是现将坐标点排号再打乱，相当于将蚂蚁随机分布在各个地点start(i)=temp(1);endljjl(:,1)=start;%%构建解空间zuobiao_index=1:n;%逐个蚂蚁路径选择fori=1:m%逐个地点路径选择forj=2:nyfw=ljjl(i,1:(j-1));%已访问的地点集合(禁忌表)allow_index=~ismember(zuobiao_index,yfw);%ismember用于判断矩阵某个元素是否存在，用法详见后文函数讲解allow=zuobiao_index(allow_index);%待访问的城市集合P=allow;%计算城市间转移概率fork=1:length(allow)P(k)=xxsjz(yfw(end),allow(k))^a*qfhs(yfw(end),allow(k))^b;%见文中公式endP=P/sum(P);%选择下一个访问城市Plj=cumsum(P);%cumsum函数用于累加，具体用法详见后文函数讲解yidong_index=find(Plj>=rand);yidong=allow(yidong_index(1));ljjl(i,j)=yidong;endend%计算各个蚂蚁的路径距离L=zeros(m,1);fori=1:mLujin=ljjl(i,:);forj=1:(n-1)L(i)=L(i)+jl(Lujin(j),Lujin(j+1));endL(i)=L(i)+jl(Lujin(n),Lujin(1));end%计算最短路径距离及平均距离ifddcs==1[min_L,min_index]=min(L);L_best(ddcs)=min_L;L_ave(ddcs)=mean(L);Lujin_best(ddcs,:)=ljjl(min_index,:);else[min_L,min_index]=min(L);L_best(ddcs)=min(L_best(ddcs-1),min_L);L_ave(ddcs)=mean(L);ifL_best(ddcs)==min_LLujin_best(ddcs,:)=ljjl(min_index,:);elseLujin_best(ddcs,:)=Lujin_best((ddcs-1),:);endend%%更新信息素S=zeros(n,n);%逐个蚂蚁计算fori=1:m%逐个城市计算forj=1:(n-1)S(ljjl(i,j),ljjl(i,j+1))=S(ljjl(i,j),ljjl(i,j+1))+Q/L(i);endS(ljjl(i,n),ljjl(i,1))=S(ljjl(i,n),ljjl(i,1))+Q/L(i);endxxsjz=(1-r)*xxsjz+S;%迭代次数加1，清空路径记录表ddcs=ddcs+1;ljjl=zeros(m,n);end%%结果显示[Shortest_L,index]=min(L_best);Shortest_Lujin=Lujin_best(index,:);disp(['最短距离:'num2str(Shortest_L)]);disp(['最短路径:'num2str([Shortest_LujinShortest_Lujin(1)])]);%%绘图figure(1)plot([zuobiao(Shortest_Lujin,1);zuobiao(Shortest_Lujin(1),1)],...[zuobiao(Shortest_Lujin,2);zuobiao(Shortest_Lujin(1),2)],'o-');gridonfori=1:size(zuobiao,1)text(zuobiao(i,1),zuobiao(i,2),[''num2str(i)]);endtext(zuobiao(Shortest_Lujin(1),1),zuobiao(Shortest_Lujin(1),2),'起点');text(zuobiao(Shortest_Lujin(end),1),zuobiao(Shortest_Lujin(end),2),'终点');xlabel('城市位置横坐标')ylabel('城市位置纵坐标')title(['蚁群算法优化路径(最短距离:'num2str(Shortest_L)')'])figure(2)plot(1:ddcs_max,L_best,'b',1:ddcs_max,L_ave,'r')legend('最短距离','平均距离')xlabel('迭代次数')ylabel('距离')title('各代最短距离与平均距离对比')

3.3 结果