【路径规划-TSP问题】基于蚁群算法求解旅行商问题含Matlab代码

简介: 【路径规划-TSP问题】基于蚁群算法求解旅行商问题含Matlab代码

✅作者简介:热爱科研的Matlab仿真开发者,修心和技术同步精进,matlab项目合作可私信。

🍎个人主页:Matlab科研工作室

🍊个人信条:格物致知。

更多Matlab仿真内容点击👇

智能优化算法  神经网络预测雷达通信 无线传感器

信号处理图像处理路径规划元胞自动机无人机

⛄ 内容介绍

旅行商问题,即TSP问题(Trav01ingSalegmanProblem)是数学领域中著名问题之一,这是一个NP难题也是一个著名的组合优化问题.它广泛地应用于电力系统故障诊断,国防武器一目标分配(weapon—targetassignment)问题等领域.蚁群算法是模仿蚂蚁在寻找食物过程中的行为而形成的一种寻找优化路径的机率型模拟进化算法,经研究表明该算法具有许多优良的性质,具有一定的有效性和应用价值.根据蚂蚁寻找食物的行为和旅行商活动的相似性,利用蚁群算法可以求解旅行商问题,从而找到最短路径,实现最优解.

⛄ 部分代码

%蚁群算法求解TSP问题的matlab程序

clear all

close all

clc

% 程序运行计时开始

t0 = clock;

%初始化蚁群

C=[

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

];                %%31个省会坐标

Nc_max=100;%最大循环次数,即算法迭代的次数,亦即蚂蚁出动的拨数(每拨蚂蚁的数量当然都是m)

alpha=1;%蚂蚁在运动过程中所积累信息(即信息素)在蚂蚁选择路径时的相对重要程度,alpha过大时,算法迭代到一定代数后将出现停

beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度

rho=0.2;%0<rho<1,表示路径上信息素的衰减系数(亦称挥发系数、蒸发系数),1-rho表示信息素的持久性系数

Q=100;%蚂蚁释放的信息素量,对本算法的性能影响不大

m=192;%蚁群中蚂蚁的数量,当m接近或等于城市个数n时,本算法可以在最少的迭代次数内找到最优解

%变量初始化

n=size(C,1);%表示TSP问题的规模,亦即城市的数量

D=ones(n,n);%表示城市完全地图的赋权邻接矩阵,记录城市之间的距离

for i=1:n

   for j=1:n

       if i<j

           D(i,j)=sqrt((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2);

       end

    D(j,i)=D(i,j);

   end

end

eta=1./D;%启发式因子,这里设为城市之间距离的倒数

max_ph=1000;

min_ph=0;

pheromone=max_ph.*ones(n,n);%信息素矩阵

tabu_list=zeros(m,n);%禁忌表,记录蚂蚁已经走过的城市,蚂蚁在本次循环中不能再经过这些城市。当本次循环结束后,禁忌表被用来

repeat=0;

scale=1;

Nc=0;%循环次数计数器

routh_best=zeros(Nc_max,n);%各次循环的最短路径

length_best=ones(Nc_max,1);%各次循环最短路径的长度

length_average=ones(Nc_max,1);%各次循环所有路径的平均长度


while Nc<Nc_max


   %将m只蚂蚁放在n个城市上

   rand_position=[];

   for i=1:ceil(m/n)

       rand_position=[rand_position,randperm(n)];

   end

   tabu_list(:,1)=(rand_position(1:m))';%将蚂蚁放在城市上之后的禁忌表,第i行表示第i只蚂蚁,第i行第一列元素表示第i只蚂蚁


   %m只蚂蚁按概率函数选择下一座城市,在本次循环中完成各自的周游

   for j=2:n

       for i=1:m

           city_visited=tabu_list(i,1:(j-1));%已访问的城市

           city_remained=zeros(1,(n-j+1));%待访问的城市

           probability=city_remained;%待访问城市的访问概率

           cr=1;

           for k=1:n%for循环用于求待访问的城市。比如如果城市个数是5,而已访问的城市city_visited=[2 4],则经过此for循环后

               if length(find(city_visited==k))==0

                   city_remained(cr)=k;

                   cr=cr+1;

               end

           end


           %状态转移规则****************************************

           q0=0.5;

           if rand>q0

               for k=1:length(city_remained)

                   probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;

                   position=find(probability==max(probability));

                   to_visit=city_remained(position(1));

               end

           else

               for k=1:length(city_remained)

                   probability(k)=(pheromone(city_visited(end),city_remained(k)))^alpha*(eta(city_visited(end),city_remained(k)))^beta;

               end

               probability=probability/sum(probability);

               pcum=cumsum(probability);

               select=find(pcum>=rand);

               to_visit=city_remained(select(1));

           end

           tabu_list(i,j)=to_visit;

           %**************************************************************

           

       end

   end

   if Nc>0

       tabu_list(1,:)=routh_best(Nc,:);%将上一代的最优路径(最优解)保留下来,保证上一代中的最适应个体的信息不会丢失

   end

   %记录本次循环的最佳路线

   total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度

   for i=1:m

       r=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径

       for j=1:(n-1)

           total_length(i)=total_length(i)+D(r(j),r(j+1));%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度

       end

       total_length(i)=total_length(i)+D(r(1),r(n));%最终得到第i只蚂蚁在本次循环中所走过的路径长度

   end

   length_best(Nc+1)=min(total_length); %把m只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度

   position1=find(total_length==length_best(Nc+1));%找到最短路径的位置,即最短路径是第几只蚂蚁或哪几只蚂蚁走出来的

   routh_best(Nc+1,:)=tabu_list(position1(1),:);%把第一个走出最短路径的蚂蚁在本次循环中所走的路径作为本次循环中的最优路径

   length_average(Nc+1)=mean(total_length);%计算本次循环中m只蚂蚁所走路径的平均长度


     f_best=length_best(1)

if f_best>length_best(Nc+1)

f_best=length_best(Nc+1)

end


   %更新信息素

   delta_pheromone=zeros(n,n);

 

 for j=1:n-1

     


     delta_pheromone(tabu_list(position(1),j),tabu_list(position(1),j+1))=delta_pheromone(tabu_list(position(1),j),tabu_list(position(1),j+1))+1/log(length_best(Nc+1));

     delta_pheromone(tabu_list(position(1),n),tabu_list(position(1),1))=delta_pheromone(tabu_list(position(1),n),tabu_list(position(1),1))+1/log(length_best(Nc+1));



      if mod(Nc,5)==0

         delta_pheromone(tabu_list(position(1),j),tabu_list(position(1),j+1))=delta_pheromone(tabu_list(position(1),j),tabu_list(position(1),j+1))+1/log(f_best);

         delta_pheromone(tabu_list(position(1),n),tabu_list(position(1),1))=delta_pheromone(tabu_list(position(1),n),tabu_list(position(1),1))+1/log(f_best);

      end


  end%至此把m只蚂蚁在本次循环中在所有路径上释放的信息素已经累加上去

%t=sigmf(Nc,[-0.01 Nc_max/2])

   pheromone=0.6.*pheromone+delta_pheromone;

max_ph=max(pheromone(1,:));

min_ph=max_ph/(2*n);

for i=1:n

        for j=1:n

if(pheromone(i,j)>max_ph)

pheromone(i,j)=max_ph;

end

if(pheromone(i,j)<min_ph)

pheromone(i,j)=min_ph;

end

end

end

    tabu_list=zeros(m,n);

    Nc=Nc+1

end


%输出结果,绘制图形

position=find(length_best==min(length_best));

shortest_path=routh_best(position(1),:)

shortest_length=length_best(position(1))

%绘制最短路径

figure(1)

set(gcf,'Name','Ant Colony Optimization——Figure of shortest_path','Color','r')

N=length(shortest_path);

scatter(C(:,1),C(:,2),10,'filled');

hold on

plot([C(shortest_path(1),1),C(shortest_path(N),1)],[C(shortest_path(1),2),C(shortest_path(N),2)])

set(gca,'Color','g')

hold on

for i=2:N

   plot([C(shortest_path(i-1),1),C(shortest_path(i),1)],[C(shortest_path(i-1),2),C(shortest_path(i),2)])

   hold on

end

%绘制每次循环最短路径长度和平均路径长度

figure(2)

set(gcf,'Name','Ant Colony Optimization——Figure of length_best and length_average','Color','r')

plot(length_best,'r')

set(gca,'Color','g')

hold on

plot(length_average,'k')

⛄ 运行结果

⛄ 参考文献

[1]徐义豪. 基于蚁群算法求解旅行商问题[J]. 电子技术与软件工程, 2013(17):2.

❤️ 关注我领取海量matlab电子书和数学建模资料
❤️部分理论引用网络文献,若有侵权联系博主删除


相关文章
|
7天前
|
存储 算法 调度
【复现】【遗传算法】考虑储能和可再生能源消纳责任制的售电公司购售电策略(Python代码实现)
【复现】【遗传算法】考虑储能和可再生能源消纳责任制的售电公司购售电策略(Python代码实现)
102 26
|
7天前
|
存储 编解码 算法
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
【多光谱滤波器阵列设计的最优球体填充】使用MSFA设计方法进行各种重建算法时,图像质量可以提高至多2 dB,并在光谱相似性方面实现了显著提升(Matlab代码实现)
|
4天前
|
机器学习/深度学习 人工智能 搜索推荐
从零构建短视频推荐系统:双塔算法架构解析与代码实现
短视频推荐看似“读心”,实则依赖双塔推荐系统:用户塔与物品塔分别将行为与内容编码为向量,通过相似度匹配实现精准推送。本文解析其架构原理、技术实现与工程挑战,揭秘抖音等平台如何用AI抓住你的注意力。
103 6
从零构建短视频推荐系统:双塔算法架构解析与代码实现
|
7天前
|
机器学习/深度学习 传感器 算法
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
【高创新】基于优化的自适应差分导纳算法的改进最大功率点跟踪研究(Matlab代码实现)
83 14
|
7天前
|
机器学习/深度学习 运维 算法
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
【微电网多目标优化调度】多目标学习者行为优化算法MOLPB求解微电网多目标优化调度研究(Matlab代码实现)
|
9天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
8天前
|
传感器 机器学习/深度学习 算法
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
【UASNs、AUV】无人机自主水下传感网络中遗传算法的路径规划问题研究(Matlab代码实现)
|
10天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。
110 15
|
12天前
|
机器学习/深度学习 传感器 算法
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
基于全局路径的无人地面车辆的横向避让路径规划研究[蚂蚁算法求解](Matlab代码实现)
|
10天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于WOA鲸鱼优化的XGBoost序列预测算法matlab仿真
基于WOA优化XGBoost的序列预测算法,利用鲸鱼优化算法自动寻优超参数,提升预测精度。结合MATLAB实现,适用于金融、气象等领域,具有较强非线性拟合能力,实验结果表明该方法显著优于传统模型。(238字)

热门文章

最新文章