✅作者简介：热爱科研的Matlab仿真开发者，修心和技术同步精进，matlab项目合作可私信。
🍎个人主页：Matlab科研工作室
🍊个人信条：格物致知。
更多Matlab仿真内容点击👇
⛄ 内容介绍
旅行商问题（TSP）是运筹学、数学优化和理论计算领域的经典算法问题。推销员必须绕过最短路线，绕过一定数量的地方，返回起点。精确算法和启发式算法都用于解决 TSP。
设计用于获得具有阶乘复杂性的精确解的精确算法被归类为 NP-Complete。启发式方法的解决方案都基于优化问题。这些算法的复杂性低于精确算法。因此，它可以在更少的时间和空间内给出解决方案，并用于近似解足以解决问题的情况，特别是在很难获得精确解的情况下。
本论文的首要目的是强调每种 TSP 方法的要求、局限性和能力，以指导科学家和研究人员根据他们的特定需求选择最合适的方法。它对最有效和广泛使用的 TSP 方法进行了全面调查，通过研究它们的方法来阐明它们的主要区别，以发现它们的优缺点。
蚁群优化 (ACO) 考虑了一种启发式方法，它具有很强的达到最优 TSP 解决方案的能力。它源于蚂蚁在自然界中的自然行为——基于分析真实的蚂蚁在群体中寻找和储存食物的思考。本论文的第二个目的是提出一种新的混合算法来解决TSP。它将由 ACO 和 Neighbor Joining (NJ) 组成的结构称为 (NACO)。新算法集中关注所有可能影响解的准则并将其应用到TSP中，与原蚁群算法相比，解得到很多改进，特别是在减少计算量和时间上.
此外，本文还介绍了并行NACO作为高性能TSP的高效并行程序。建议在单独的执行线程中并行运行蚂蚁，以受益于每个蚂蚁的独立操作，并通过使用多核系统实现并行算法。拟议的程序由 MATLAB® R2017a（版本 9.2）编写，并在配备 8GB RAM 和英特尔酷睿 i7-8565U CPU、64 位 Windows 操作系统的惠普计算机上实施。获得的结果表明，相对于 NACO，复杂度降低到 O(n^2 (n-ω))。至于 PNACO，复杂度从 O(n(n⁄p)(n-ω)) 降低，此外加速度高达 10。
⛄ 部分代码
%%PNACO
%%New hybrid methods to solve the model of traveling salesman problem based-on meta-heuristic method
%% A thesis Submitted to the College of Education for Pure Sciences,
%% Tikrit University as a Partial Fulfillment of Requirements for the Degree
%% of Master of Sciences in Mathematics
%% By (Warif B.B. Yahia)&(Dr Mohammed W. Al-Neama)&(Dr. Ghassan E. Arif)
%% 2020 A.D = 1441 A.H
%% The main idea of the NACO method is to reduce the distance matrix generated
%by the cities which the salesman must to visits. Where the NACO try to merge the
%cities by building a phylogenetic tree and then generating a new matrix called
%LEAF1 which represent the first stage of the joined leaves.When the salesman
%reach any city within this matrix,he will move directly to the next
%corresponding city without doing any computations.
%% Start with ACO
clc;
clear;
close all;
profile on
for s=2:2
%% Read the Dataset
D_Set=CreateD_Set('5.txt');
% D_Set=D_Set1;
% % load('D_Set.mat');
% D_Set1=D_Set;
CostFunction=@(tour) L_Tour(tour,D_Set);
no_Var=D_Set.n;
%% The Parameters
Iteration=1; % No. of Iterations
no_ant=1; % Population Size (No. of Ants)
Q=100;
%t0=1;
t0=10*Q/(no_Var*mean(D_Set.D(:))); % Initial Phromone
alpha=1; % Phromone Exponential Weight
beta=5; % Heuristic Exponential Weight
rate=0.7; % Evaporation Rate
%% Initialization
eta=1./D_Set.D; % Heuristic Information Matrix
t=t0*ones(no_Var,no_Var); % Phromone Matrix
BC=zeros(Iteration,1); % Array to Hold Best Cost Values
% Empty Ant
empty_ant.Tour=[];
empty_ant.Cost=[];
% Ant Colony Matrix
ant=repmat(empty_ant,no_ant,1);
% Best Ant
BS.Cost=inf;
% the Level_one of NJ
Leaf=Leaf_1(D_Set.D);
% Runtime
T_1 = cputime;
%% NEW_ACO Main Program
for it=1:Iteration
for k=1:no_ant % Move Ants
Leaf1=Leaf;
ant(k).Tour=randi([1 no_Var]); %% {choose a random non visited city}
city=ant(k).Tour;
for l =2:no_Var
ant_tour=ant(k).Tour(end);
profile viewer
% filename = 'resuls.xlsx';
% A = {Time,num2str(BC(it)),no_Var,Iteration};
% sheet = 1;
% xlRange = 'A22';
% xlswrite(filename,A,sheet,xlRange)
%filename = 'resuls.xlsx';
%A = {Time,num2str(BC(it)),no_Var,Iteration};
%sheet = 1;
%cell_num = sprintf('A%s',num2str(s));
%xlRange = cell_num;
%xlswrite(filename,A,sheet,xlRange)
end
%%% Results4
figure;
plot(BC,'LineWidth',2);
xlabel('Iteration');
ylabel('Best Cost');
grid on;
% saveas(gcf,'It_BC_48_N_1.png');
% filename = 'resuls.xlsx';
% A = {'Time(s)','Best Cost','no Cities','no it'};
% sheet = 2;
% xlRange = 'A1';
% xlswrite(filename,A,sheet,xlRange)
⛄ 运行结果
⛄ 参考文献
"A HYBRID OPTIMIZATION ALGORITHM OF ANT COLONY SEARCH AND NEIGHBOUR-JOINING METHOD TO SOLVE THE TRAVELLING SALESMAN PROBLEM", Advanced Mathematical Models & Applications Vol.5, No.1, 2020, pp.95-110
