失眠网 > 【TSP问题】基于灰狼算法求解旅行商问题matlab源码

【TSP问题】基于灰狼算法求解旅行商问题matlab源码

时间：2022-12-17 05:31:10

1 算法介绍

1.1 TSP介绍

“旅行商问题”(Traveling Salesman Problem,TSP)可简单描述为：一位销售商从n个城市中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能路径中求出路径长度最短的一条。

旅行商的路线可以看作是对n城市所设计的一个环形，或者是对一列n个城市的排列。由于对n个城市所有可能的遍历数目可达(n-1)!个，因此解决这个问题需要O(n!)的计算时间。而由美国密执根大学的Holland教授发展起来的遗传算法，是一种求解问题的高效并行全局搜索方法，能够解决复杂的全局优化问题，解决TSP问题也成为遗传算法界的一个目标。

1.2 灰狼算法求解tsp模型

灰狼算法(greywolfoptimizer,gwo)是澳大利亚学者seyedalimirjalili于根据灰狼种群的习性提出的一种元启发式算法。该算法根据灰狼喜欢群居的特性引入了社会统治阶层。在种群中，将其分为四个阶层：α狼(负责对种群发出命令的优势狼，即领头狼)；β狼(辅助头狼做出决策等活动的优势狼)；δ狼(侦察、站岗、狩猎和看护幼崽等相关活动是这种狼的主要活动，是服从于前两种狼的优势狼。)；ω狼(服从于前三种优势狼，是位于统治阶级中最底端的狼)。算法利用根据灰狼种群在搜寻、围捕猎物的行为构建算法的数学描述公式，通过迭代获取最优解。通过基准函数的仿真结果表明，灰狼算法能够比遗传算法、粒子群算法等更快更好地完成最优解的搜寻。虽然灰狼算法在连续空间表现出了较好地应用效果，但是应对tsp问题时，在离散空间下的表现不是十分满意。因此，需要对传统的灰狼算进行改进，来更有效地处理tsp问题。

2 部分代码

clc;clear;%% TSP问题设置% 产生问题模型model = CreateModel('Oliver30.txt'); % 城市分布图figure(1);plot(model.x, model.y, 'ms', 'LineWidth', 2, 'MarkerEdgeColor', 'k', 'MarkerFaceColor', 'g')legend('城市位置')title('城市分布图', 'fontsize', 12)xlabel('km', 'fontsize', 12)ylabel('km', 'fontsize', 12)grid on% 适应度函数句柄Fun = @(tour) TourLength(tour, model); % TSP参数M = model.n; % 城市个数 % GWO参数N = 50; % 灰狼个数Max_iter = 1000;% 最大迭代次数lb = -10; % Lower Boundub = 10; % Upper Bounddim = M; % 维数% 初始化alpha, beta, and delta_posAlpha_pos = zeros(1,dim);Alpha_score = inf; Beta_pos = zeros(1,dim);Beta_score = inf; Delta_pos = zeros(1,dim);Delta_score = inf; % 初始化种群位置Positions = rand(N, dim).*(ub-lb)+lb;Length_best = zeros(1, Max_iter);Length_ave = zeros(1, Max_iter);l = 1; % 迭代计数器%% 迭代寻优while l < Max_iter+1for i = 1:N% 边界处理Flag4ub = Positions(i, :) > ub;Flag4lb = Positions(i, :) < lb;Positions(i, :) = (Positions(i, :).*(~(Flag4ub+Flag4lb)))+ub.*Flag4ub+lb.*Flag4lb; % 按行升序排列产生城市序列[~, sol] = sort(Positions, 2); % 计算目标函数值(即路径距离)fitness = Fun(sol(i, :));Length_ave(l) = Length_ave(l)+fitness;% 更新Alpha, Beta, and Deltaif fitness < Alpha_score Alpha_score = fitness; Alpha_pos = Positions(i, :);endif fitness > Alpha_score && fitness < Beta_score Beta_score = fitness; Beta_pos = Positions(i, :);endif fitness > Alpha_score && fitness > Beta_score && fitness < Delta_score Delta_score = fitness; Delta_pos = Positions(i, :);endenda = 2-l*((2)/Max_iter); % a从2线性减到0% 更新所有个体位置for i = 1:Nfor j = 1:dim r1 = rand(); % r1 is a random number in [0,1]r2 = rand(); % r2 is a random number in [0,1]A1 = 2*a*r1-a; % Equation (3.3)C1 = 2*r2; % Equation (3.4)D_alpha = abs(C1*Alpha_pos(j)-Positions(i, j)); % Equation (3.5)-part 1X1 = Alpha_pos(j)-A1*D_alpha; % Equation (3.6)-part 1r1 = rand();r2 = rand();A2 = 2*a*r1-a; % Equation (3.3)C2 = 2*r2;% Equation (3.4)D_beta = abs(C2*Beta_pos(j)-Positions(i, j)); % Equation (3.5)-part 2X2 = Beta_pos(j)-A2*D_beta; % Equation (3.6)-part 2 r1 = rand();r2 = rand(); A3 = 2*a*r1-a; % Equation (3.3)C3 = 2*r2; % Equation (3.4)D_delta = abs(C3*Delta_pos(j)-Positions(i, j)); % Equation (3.5)-part 3X3 = Delta_pos(j)-A3*D_delta; % Equation (3.5)-part 3 Positions(i, j) = (X1+X2+X3)/3; % Equation (3.7)endend Length_best(l) = Alpha_score; % 最短距离Length_ave(l) = Length_ave(l)/dim; % 平均距离disp(['Iteration ' num2str(l) ': Best Fitness = ' num2str(Alpha_score)]);l = l + 1;[~, BestSol] = sort(Alpha_pos);figure(2);PlotSolution(BestSol, model, Alpha_score);pause(0.01); end%% 进化曲线figure(3);t = 1:Max_iter;plot(t, Length_best, 'r', t, Length_ave, 'b--', 'LineWidth', 2);xlabel('Iteration');ylabel('Best Cost');legend('最短距离','平均距离')xlabel('迭代次数')ylabel('距离')title('各代最短距离与平均距离对比')