【路径规划-TSP问题】基于粒子群结合蚁群算法求解旅行商问题附matlab代码(最优路径规划)

1 内容介绍

一种基于粒子群优化的蚁群算法求解TSP问题的方法.该方法在求解TSP问题时,利用粒子群优化的思想,对蚁群算法的参数取值进行优化并选择.在粒子群算法中,将蚁群算法的5个参数(q,α,β,ρ,m)看作粒子群算法中的一个粒子,经反复调用蚁群算法计算并更新后,可以优化蚁群算法的性能,使参数通过粒子自适应选取,而不再依靠人工经验选取.这种基于粒子群优化的蚁群算法将计算出的5个参数组合反馈回蚁群算法后,对解决TSP问题有优异的效果.

旅行商问题（TravelingSalesmanProblem）是一个典型的组合优化问题，旅行商问题描述如下：给定n个城市及两两城市之间的距离，求一条经过各城市一次且仅一次的最逗路线。其图论描述为：

TSP问题的求最优化解是很困难的。对于有着n个城市的TSP问题，存在着（n-1）!/2条可能的路径。随着城市数目n的增长，可能路径的数目以n的指数倍增加，如果使用穷举法搜索，需要考虑所以的可能情况，并两两比较，找出最优解，那么可搜索的路径及其距离之和的计算量将正比于n!/2，算法的复杂度呈指数增长，人们把这类问题称为“NP完全问题”。由于TSP具有实际应用价值，例如：城市管道铺设优化、物流等行业中的车辆调度优化、制造业中的切割路径优化以及电力系统配电网络重构等现实生活中的很多优化问题都可以归结为TSP模型来求解，目前TSP应用的一个重要方面就是无人飞机的航路设计问题，即事先针对敌方防御区内的威胁部署和目标的分布情况，对无人作战飞机的飞行航路进行整体规划设计，可以综合减小被敌方发现和反击的可能性、降低耗油量，从而显著提高UCAV执行对地攻击（或侦察）任务的成功率。目前求解

2 部分代码

% 交叉策略C，cross_tsp_c

function cnew=cross_tsp_c(c1,c2,n)

j1=ceil(n*rand);

j2=ceil(n*rand);

j3=min(j1,j2);

j4=max(j1,j2);

clear c3

c3=c2(j3:j4);

j5=ceil(n*rand);

k=1;

for i=1:j5-1

if(isempty(find(c3==c1(i))));

cnew(k)=c1(i);

k=k+1;

end

end

cnew(k:k+j4-j3)=c3;

k=k+j4-j3+1;

for i=j5:n

if(isempty(find(c3==c1(i))))

cnew(k)=c1(i);

k=k+1;

end

end

3 运行结果

4 参考文献

[1]尹晓峰, 刘春煌. 基于MATLAB的混合型蚁群算法求解旅行商问题[J]. 铁路计算机应用, 2005, 14(9):4.

[2]廖勇, 赵萌轩. 一种基于粒子群优化的蚁群算法求解TSP问题的方法:, CN108921354A[P]. 2018.

部分理论引用网络文献，若有侵权联系博主删除。