1简介

旅行商问题是一个典型的组合优化问题，该问题假设一位旅行商需访问n个城市，城市之间的间距是固定的，旅行商从一指定的城市出发，且不重复的访问剩余城市，最后回到起始城市，在所有的回路中求出最短路径。TSP问题应用非常广泛，例如绘制基因组图谱、望远镜、X射线、操控工业机械、安排生产作业任务等。TSP问题是著名的NP完全问题，求解TSP问题有精确算法和启发式算法两种。精确算法能保证在指数级次数中找到最好结果，但其本身非常复杂，且对计算机要求较高；启发式算法普遍简单，运行时间短，例如模拟退火算法、遗传算法、局部搜索算法等，但易陷入局部最优。灰狼优化算法是年由Mirjalili等人提出的启发式智能算法。该算法模拟自然界灰狼等级制度和狼群搜索猎物过程，利用灰狼种群内部等级制度，实现对目标猎物函数的优化过程

。该算法具有优良的收敛稳定性与较强的全局探索能力。

%%根据城市数目、旅行商数目以及起（终）点城市编码出灰狼个体

%输入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

[1]高珊,and孟亮."贪婪随机自适应灰狼优化算法求解TSP问题."现代电子技术42.14():6.

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

转载请注明:http://www.aideyishus.com/lkyy/130.html