蚁群算法路径优化matlab代码,蚁群算法路径规划matlab
主要介绍了一个利用PythonMatlab蚁群算法求解最短路径问题的实例，通过实例代码详细介绍，具有一定的参考价值。感兴趣的朋友可以参考一下。
00-1010 1知识点1.1蚁群算法步骤1.2蚁群算法程序2蚁群算法求解最短路径问题——Python实现2.1源代码实现2.2 ACA_TSP实现3蚁群算法求解最短路径问题——Matlab实现3.1流程图3.2代码实现3.3结果
目录
详细知识点见：智能优化算法-蚁群算法(Python实现)。
这一节我们只谈蚁群算法求解最短路径步骤及流程。。
1 知识点
设蚂蚁数为m，地点数为n，地点I和J之间的距离为Dij，在T时刻连接地点I和J的路径上的信息素浓度为Sij，在初始时刻每个地点之间的路径上的信息素浓度相等。
蚂蚁K根据各个位置之间连接路径上的信息素决定下一个目标位置。Pijk表示蚂蚁K在时间T从位置I移动的概率，概率计算公式如下：
其中，是启发式函数，表示蚂蚁从位置I移动到位置J的期望程度；是蚂蚁k要去的地方的集合，开头有n-1个元素(出发地点除外)。随着时间的推移，蚂蚁每到达下一个地方，里面的元素就会减一，直到空集，也就是说所有的地方都去过了。a为信息素重要性因子，值越大，信息素浓度在转移中的作用越大，即蚂蚁选择下一个地点附近的概率越大，为启发式函数重要性因子。
当蚂蚁释放信息素时，每个地方之间的连接路径上的信息素逐渐消失，并使用参数
显示了信息素的挥发性。因此，当所有蚂蚁完成一个循环时，每个地方之间的连接路径上的信息素浓度需要更新，即蚂蚁经过并留下信息素。公式如下：
其中，代表位置I与位置J连接路径上第k只蚂蚁释放的信息素浓度；表示位置I和J的连接路径上所有蚂蚁释放的信息素浓度的总和；q为常数，表示蚂蚁在一个周期内释放的信息素总量；Lk表示第k个蚂蚁的路径长度。一般来说，蚂蚁的路径越短，释放的信息素浓度越高，最终选择最短的路径。
1.1蚁群算法步骤
(1)参数初始化
求最短路径钱需要初始化程序的参数，如蚁群规模M、信息素重要性因子、启发式函数重要性因子、信息素发生因子、最大迭代次数ddcs_max，初始迭代值为ddcs=1。
(2)构建解空间
每只蚂蚁被随机放置在不同的起始地点，根据蚂蚁访问行为的公式计算下一个访问地点，直到所有蚂蚁都访问了所有地点。
(3)更新信息素
计算每只蚂蚁路径的总长度Lk，记录当前周期的最优路径，根据公式更新不同地点之间连接路径上的信息素浓度。
(4)判断终止
在迭代次数达到最大值之前，清除蚂蚁通过的记录，返回步骤(2)。
1.2蚁群算法程序
2 蚂蚁算法求解最短路径问题——Python实现
智能算法-蚁群算法(Python实现)
2.1 源码实现
补充知识点：scipy.spatial.distance.cdist
#========导入相关库===============
进口
umpy as np
from scipy import spatial
import pandas as pd
import matplotlib.pyplot as plt
from sko.ACA import ACA_TSP
num_points = 25
points_coordinate = np.random.rand(num_points, 2) # 生成点的坐标
distance_matrix = spatial.distance.cdist(points_coordinate, points_coordinate, metric=euclidean)#函数用于计算两个输入集合的距离
def cal_total_distance(routine):
num_points, = routine.shape
return sum([distance_matrix[routine[i % num_points], routine[(i + 1) % num_points]] for i in range(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 代码实现
下表为一些坐标点，找出最短路线：
%蚁群算法寻找最短路径程序%% 清空环境变量
clear
clc
%% 导入数据，导入方式，看个人习惯
zuobiao=[1304 2312
3639 1315
4177 2244
3712 1399
3488 1535
3326 1556
3238 1229
4196 1004
4312 790
4386 570
3007 1970
2562 1756
2788 1491
2381 1676
1332 695
3715 1678
3918 2179
4061 2370
3780 2212
3676 2578
4029 2838
4263 2931
3429 1908
3507 2367
3394 2643
3439 3201
2935 3240
3140 3550
2545 2357
2778 2826
2370 2975];
%% 计算城市间相互距离
n = size(zuobiao,1);%城市个数
jl = zeros(n,n);%首先求得各个坐标点的距离，这里是矩阵初始化
for i = 1:n
for j = 1:n
if i ~= j %~=是不等于的意思，zuobiao矩阵中每行都有个坐标，坐标相减用i和j区分不同的坐标点，然后求两点距离
jl(i,j) = sqrt(sum((zuobiao(i,:) - zuobiao(j,:)).^2));
%上式运算如a=[2,2;1,1]=>a(1,:)-a(2,:)=>ans =1 1，然后1?+1?=2，最后开根号
else
jl(i,j) = 1e-4;%相等的点相减准确说是等于0的，这里设置成了一个很小的数，是为了避免后面程序运算出错
end
end
end
%% 初始化参数
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); % 各代路径的平均长度
%% 迭代寻找最佳路径
while ddcs <= ddcs_max%在ddcs小于ddcs_max前，一直循环
%% 随机产生各个蚂蚁的起点
start = zeros(m,1);
for i = 1:m
temp = randperm(n);%功能是随机打乱一个数字序列,也就是现将坐标点排号再打乱，相当于将蚂蚁随机分布在各个地点
start(i) = temp(1);
end
ljjl(:,1) = start;
%% 构建解空间
zuobiao_index = 1:n;
% 逐个蚂蚁路径选择
for i = 1:m
% 逐个地点路径选择
for j = 2:n
yfw = ljjl(i,1:(j - 1)); % 已访问的地点集合(禁忌表)
allow_index = ~ismember(zuobiao_index,yfw);%ismember用于判断矩阵某个元素是否存在，用法详见后文函数讲解
allow = zuobiao_index(allow_index); % 待访问的城市集合
P = allow;
% 计算城市间转移概率
for k = 1:length(allow)
P(k) = xxsjz(yfw(end),allow(k))^a * qfhs(yfw(end),allow(k))^b;%见文中公式
end
P = P/sum(P);
% 选择下一个访问城市
Plj = cumsum(P); %cumsum函数用于累加，具体用法详见后文函数讲解
yidong_index = find(Plj >= rand);
yidong = allow(yidong_index(1));
ljjl(i,j) = yidong;
end
end
% 计算各个蚂蚁的路径距离
L = zeros(m,1);
for i = 1:m
Lujin = ljjl(i,:);
for j = 1:(n - 1)
L(i) = L(i) + jl(Lujin(j),Lujin(j + 1));
end
L(i) = L(i) + jl(Lujin(n),Lujin(1));
end
% 计算最短路径距离及平均距离
if ddcs == 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);
if L_best(ddcs) == min_L
Lujin_best(ddcs,:) = ljjl(min_index,:);
else
Lujin_best(ddcs,:) = Lujin_best((ddcs-1),:);
end
end
%% 更新信息素
S = zeros(n,n);
% 逐个蚂蚁计算
for i = 1:m
% 逐个城市计算
for j = 1:(n - 1)
S(ljjl(i,j),ljjl(i,j+1)) = S(ljjl(i,j),ljjl(i,j+1)) + Q/L(i);
end
S(ljjl(i,n),ljjl(i,1)) = S(ljjl(i,n),ljjl(i,1)) + Q/L(i);
end
xxsjz = (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_Lujin Shortest_Lujin(1)])]);
%% 绘图
figure(1)
plot([zuobiao(Shortest_Lujin,1);zuobiao(Shortest_Lujin(1),1)],...
[zuobiao(Shortest_Lujin,2);zuobiao(Shortest_Lujin(1),2)],o-);
grid on
for i = 1:size(zuobiao,1)
text(zuobiao(i,1),zuobiao(i,2),[ num2str(i)]);
end
text(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 结果
到此这篇关于Python&Matlab实现蚂蚁群算法求解最短路径问题的示例的文章就介绍到这了,更多相关Python&Matlab蚂蚁群最短路径内容请搜索盛行IT软件开发工作室以前的文章或继续浏览下面的相关文章希望大家以后多多支持盛行IT软件开发工作室！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。