当前位置: 灰狼 >> 灰狼的习性 >> TSP问题基于灰狼算法求解多旅行商问
1简介
旅行商问题是一个典型的组合优化问题,该问题假设一位旅行商需访问n个城市,城市之间的间距是固定的,旅行商从一指定的城市出发,且不重复的访问剩余城市,最后回到起始城市,在所有的回路中求出最短路径。TSP问题应用非常广泛,例如绘制基因组图谱、望远镜、X射线、操控工业机械、安排生产作业任务等。TSP问题是著名的NP完全问题,求解TSP问题有精确算法和启发式算法两种。精确算法能保证在指数级次数中找到最好结果,但其本身非常复杂,且对计算机要求较高;启发式算法普遍简单,运行时间短,例如模拟退火算法、遗传算法、局部搜索算法等,但易陷入局部最优。灰狼优化算法是年由Mirjalili等人提出的启发式智能算法。该算法模拟自然界灰狼等级制度和狼群搜索猎物过程,利用灰狼种群内部等级制度,实现对目标猎物函数的优化过程
。该算法具有优良的收敛稳定性与较强的全局探索能力。
2部分代码%%根据城市数目、旅行商数目以及起(终)点城市编码出灰狼个体
%输入n:城市数目
%输入m:旅行商数目
%输入start:起(终)点城市
%输出individual:灰狼个体
functionindividual=encode(n,m,start)
%%生成灰狼个体的第一部分
part1=randperm(n);%对城市进行随机排序
part1(part1==start)=[];%将起(终)点城市从part1中删除
%%生成灰狼个体的第二部分
part2=zeros(1,m);%初始化每个旅行商访问城市数目(不包括start)
ifm==1
part2=n-1;
else
fori=1:m
ifi==1
right=n-1-(m-1);%最大取值
part2(i)=randi([1,right],1,1);
elseifi==m
part2(i)=n-1-sum(part2(1:(i-1)));
else
right=n-1-(m-i)-sum(part2(1:(i-1)));%最大取值
part2(i)=randi([1,right],1,1);
end
end
end
%%将两部分进行合并,生成最终灰狼个体
individual=[part1,part2];%将两段合并
end
3仿真结果4参考文献[1]高珊,and孟亮."贪婪随机自适应灰狼优化算法求解TSP问题."现代电子技术42.14():6.
部分理论引用网络文献,若有侵权联系博主删除。
天天Matlab