声振论坛 › 展示 ›基础理论 › 查看内容

路径优化的Floyd,dijkstra,A*算法的matlab代码

2012-10-24 15:27| 发布者: aspen| 查看: 5165| 评论: 0|原作者: assist|来自: 振动论坛

摘要: 路径优化的Floyd,dijkstra,A*算法的matlab代码

本人自己写的蚁群算法。完全能够实现功能，就是收敛速度感觉有点慢。

% function [R_best,L_best,L_ave,Shortest_Route,Shortest_Length]=ACO(C,D,s,e,NC_max,m,Alpha,Beta,Rho,Q)
% function [Shortest_Route,Shortest_Length]=ACOR(C,D,s,e,NC_max,m,Alpha,Beta,Rho,Q)
%%=========================================================================
%% ACO.m
%% Ant Colony Optimization Algorithm for Road Select Problem
%% LiLixin,ShenYang Insitute of Aeronautical engineering ,ShenYang,China
%% Email:myassist@163.com
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个城市的坐标，n×2的矩阵
%% D 道路连通加权矩阵
%% s 起点
%% e 终点
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳路线
%% L_best 各代最佳路线的长度
%%=========================================================================
%
clc
clear
% 设置初始参数如下：
m=10;Alpha=1;Beta=5;Rho=0.1;NC_max=100;Q=100;
%设定起始点
s=1;e=50;
% 31城市坐标为：
C=[601.6 971.7
988.8 482.6
54.4 549.6
95.4 868
529.1 429.5
982 350.5
654.3 23.2
738.1 372
538.9 593.7
560.1 850.3
229.2 805.9
411.2 710
83.2 706.2
937.4 800.5
11.9 994.4
694.1 809.1
795.4 758.8
338.9 148.1
955.8 643.8
345.7 726.2
550.3 349.6
183.7 935.1
640 544
854.6 842.4
199.3 547.9
434.1 921.4
405.5 624.2
272.3 998.1
772 24.4
385.2 327.4
320.3 410.4
890 90
810 580
180 80
185 300
950 200
850 258.6
50 450
150 402
345 900
450 800
621 700
564.3 180
80.5 280
750 950
450 500
300 50
900 530
300 520
152 189.6
];
D=[0 0 0 0 0 0 0 0 0 76.92 0 0 0 0 0 230.95 0 0 0 0 0 0 0 0 0 76.894 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 157.34 0 0 0 0 0
0 0 0 0 0 140.78 0 325.12 0 0 0 0 0 0 0 0 0 0 155.71 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.913 0 0
0 0 0 0 0 0 0 0 0 0 0 0 74.247 0 0 0 0 0 0 0 0 0 0 0 55.603 0 0 0 0 0 0 0 0 0 0 0 0 76.921 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 147.8 0 76.551 0 76.908 0 0 0 0 0 0 79.548 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 84.189 0 0 0 0 0 0 0 0 166.74 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.915 0 0 0 0
0 140.78 0 0 0 0 0 211.43 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.91 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 205.65 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.91 0 0 0 0 0 0 0 0 0 0 0 0 0 76.901 0 0 0 156.87 0 0 0
0 325.12 0 0 0 211.43 205.65 0 0 0 0 0 0 0 0 0 0 0 0 0 79.979 0 258.19 0 0 0 0 0 0 0 0 0 0 0 0 0 73.841 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 76.898 0 0 0 0 0 0 0 0 0 0 79.382 0 0 0 75.438 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
76.92 0 0 0 0 0 0 0 0 0 0 0 0 0 0 80.01 0 0 0 0 0 0 0 0 0 79.064 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.919 0 0 0 0 0 0 0 0 0
0 0 0 147.8 0 0 0 0 0 0 0 0 147.14 0 0 0 0 0 0 163.89 0 60.464 0 0 0 0 0 151.26 0 0 0 0 0 0 0 0 0 0 0 76.852 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 76.898 0 0 0 0 0 0 0 0 0 0 76.922 0 0 0 0 0 0 81.004 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 74.247 76.551 0 0 0 0 0 0 147.14 0 0 0 0 0 0 0 0 0 0 0 0 0 155.58 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 79.124 0 79.49 0 0 0 0 76.899 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 76.908 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.889 0 0 0 0 0 76.886 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
230.95 0 0 0 0 0 0 0 0 80.01 0 0 0 0 0 0 78.141 0 0 0 0 0 0 154.69 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 157.07 0 0 161.07 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 79.124 0 78.141 0 0 76.92 0 0 0 0 0 0 0 0 0 0 0 0 0 78.001 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 128.28 0 0 0 62.948 0 0 0 0 0 0 0 0 154.95 0 0 0 80.368 0 0 0
0 155.71 0 0 0 0 0 0 0 0 0 0 0 79.49 0 0 76.92 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.89 0 0
0 0 0 0 0 0 0 0 0 0 163.89 76.922 0 0 0 0 0 0 0 0 0 0 0 0 163.74 0 76.919 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 84.189 0 0 79.979 0 0 0 0 0 0 0 0 0 0 0 0 0 0 152.52 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 77.57 0 0 0 0 0 0 0
0 0 0 79.548 0 0 0 0 0 0 60.464 0 0 0 76.889 0 0 0 0 0 0 0 0 0 0 0 0 76.892 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 258.19 79.382 0 0 0 0 0 0 0 0 0 0 0 152.52 0 0 0 0 0 0 0 0 0 0 0 161.33 0 0 0 0 0 0 0 0 157.1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 76.899 0 154.69 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 62.691 0 0 0 0 0
0 0 55.603 0 0 0 0 0 0 0 0 0 155.58 0 0 0 0 0 0 163.74 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 79.451 0 0 0 0 0 0 0 0 0 79.409 0
76.894 0 0 0 0 0 0 0 0 79.064 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 77.742 0 0 0 0 0 0 0 0 0 0 0 76.928 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 75.438 0 0 81.004 0 0 0 0 0 0 0 76.919 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 151.26 0 0 0 76.886 0 0 0 0 0 0 76.892 0 0 0 77.742 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 76.91 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.913 0 0 0 0 78.324 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 166.74 0 0 0 0 0 0 0 0 0 0 0 0 128.28 0 0 0 0 0 0 0 0 0 0 0 0 79.988 0 0 0 157.22 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 79.988 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.911 0 0 76.918 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.913 0 0 0 0 0 0 76.921 76.907 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 78.001 0 0 0 0 0 161.33 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.914 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 62.948 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.916 0 0 76.923
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 157.22 0 0 0 0 0 0 0 0 80.495 0 0 0 0 76.92 0 0 0 0 0 76.926
0 0 0 0 0 76.91 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.921 0 0 0 0 76.888 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 73.841 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 78.324 0 0 76.907 0 0 0 76.888 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 76.921 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.92 0 0 0 0 76.908 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 79.451 0 0 0 0 0 0 0 0 0 80.495 0 0 76.92 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 76.852 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.928 0 0 0 0 0 0 0 0 0 0 0 0 0 0 77.96 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 76.919 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 77.96 0 76.893 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 157.07 0 0 0 0 0 0 157.1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.893 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 76.901 0 0 0 0 0 0 0 0 0 0 154.95 0 0 77.57 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.92 0 0 76.908 0 0 0 0 0 0 0 0 0 0 0 76.921
157.34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 161.07 0 0 0 0 0 0 0 62.691 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 76.915 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.911 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.912 0
0 0 0 0 0 0 156.87 0 0 0 0 0 0 0 0 0 0 80.368 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.916 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 76.913 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.89 0 0 0 0 0 0 0 0 0 0 0 0 0 76.914 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 79.409 0 0 0 0 0 76.918 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.912 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 76.923 76.926 0 0 0 0 0 0 0 0 76.921 0 0 0 0 0 0
];
%%第一步：变量初始化
n=size(C,1);%n表示问题的规模（城市个数）
gplot(D , C);%画无向图
hold on
XX=C';
plot(XX(1 , :) , XX(2 , :) , 'k+', 'markersize' , 5) %画十字架
for i=1:n
text(C(i,1)+5,C(i,2),int2str(i)); %加标号
end
for i=1:n
for j=1:n
if D(i,j)==0
D(i,j)=inf;
end
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);%各代最佳路线的长度
lastmin=inf; %上代最小路径
thesameNum=0; %终止算法条件之一
while NC<=NC_max%停止条件之一：达到最大迭代次数
%%第二步：将m只蚂蚁放到n个城市上
Randpos=ones(1,m)*s;
Tabu(:,1)=(Randpos(1,1:m))';
%%第三步：m只蚂蚁按概率函数选择相通的下一座城市，直到到达目的地
for i=1:m
%按概率原则选取下一个城市
%只有当达到最后的节点等于终点时候才结束
j=2;
to_visit=s;
while to_visit~=e
visited=Tabu(i,1:(j-1));%已访问的城市
% 得到矩阵中最后一个不为0的数 ,即蚂蚁爬到的最后节点
col=size(visited,2);
lastvisited=visited(end);
J=[];%待访问的城市，随机分布
P=J;%待访问城市的选择概率分布
Jc=1;
JJ=randperm(n);%随机分布
for k=1:n
flag=bHaveNum(visited,JJ(k));
if flag~=1
if D(lastvisited,JJ(k))~=inf
J(Jc)=JJ(k);
Jc=Jc+1;
end
end
end
if length(J) ==0
break;
end
%下面计算待选城市的概率分布
for k=1:length(J)
P(k)=(Tau(lastvisited,J(k))^Alpha)*(Eta(lastvisited,J(k))^Beta);
end
P=P/(sum(P));
Pcum=cumsum(P);
Select=find(Pcum>=rand);
kk=randperm(length(Select));
to_visit=J(Select(kk(1)));
Tabu(i,j)=to_visit;
j=j+1;
end
end
%%第四步：记录本次迭代最佳路线
L=zeros(m,1);
for i=1:m
R=Tabu(i,:);
F=thelastNum(R);
if R(F)==e
for j=1:(n-1)
if R(j+1)~=0
L(i)=L(i)+D(R(j),R(j+1));
end
end
else
L(i)=inf;
end
end
if lastmin~=min(L)
thesameNum=0;
else
thesameNum=thesameNum+1;
end
if (thesameNum >0.2*NC_max)
break;
end
L_best(NC)=min(L);
pos=find(L==L_best(NC));
R_best(NC,:)=Tabu(pos(1),:);
NC=NC+1;
%%第五步：更新信息素
Delta_Tau=zeros(n,n);
for i=1:m
for j=1:(n-1)
if Tabu(i,j+1)~=0
Delta_Tau(Tabu(i,j),Tabu(i,j+1))=Delta_Tau(Tabu(i,j),Tabu(i,j+1))+Q/L(i);
end
end
end
Tau=(1-Rho).*Tau+Delta_Tau;
%%第六步：禁忌表清零
Tabu=zeros(m,n);
end
%%第七步：输出结果
Pos=find(L_best==min(L_best));
Shortest_Route=R_best(Pos(1),:);
Shortest_Length=L_best(Pos(1));
F=thelastNum(Shortest_Route);
Shortest_Route=Shortest_Route(1:F);
plot(XX(1 , Shortest_Route') , XX(2 , Shortest_Route') , 'g' , 'linewidth' , 1) %画结果路径
hold off

复制代码

本文内容由 assist 提供

1 2 345 / 5 页下一页

收藏分享邀请

账号		自动登录	找回密码
密码			我要加入

路径优化的Floyd,dijkstra,A*算法的matlab代码

最新评论

相关分类

下级分类