tsp问题 matlab

### 关于旅行商问题 (TSP) 的 MATLAB 实现

#### 蚁群算法求解 TSP 问题
蚁群算法作为一种启发式算法，能够有效解决 NP-hard 类型的问题，并为路径规划提供新思路。该算法模拟蚂蚁觅食行为，在寻找最短路径过程中通过信息素更新机制不断优化路径选择策略[^1]。

% 初始化参数
m = 50; % 蚂蚁数量
n = length(C); % 城市数目
Alpha = 1; Beta = 5;
Rho = 0.1; Q = 100;

D = zeros(n,n);
Eta = ones(n,n);

for i=1:n-1
    for j=i+1:n
        D(i,j)=((C(i,1)-C(j,1))^2+(C(i,2)-C(j,2))^2)^0.5;
        D(j,i)=D(i,j);
        Eta(i,j)=1/D(i,j);
        Eta(j,i)=Eta(i,j);
    end
end

Tau=zeros(n,n)+0.1;%初始化信息素浓度矩阵
Tabu=zeros(m,n);%禁忌表记录每只蚂蚁走过的城市序号
Route_best=zeros(iter_max,n);%各代最佳路线
Length_best=zeros(iter_max,1);%各代最佳路径长度

#### 混合粒子群与遗传算法(GA-PSO)求解 TSP 问题
混合粒子群算法 GA-PSO 结合了遗传算法和粒子群优化的特点，提高了求解效率和精度。此方法利用遗传操作如交叉变异来增强全局搜索能力的同时也保留了局部最优位置的记忆特性[^2]。

function [gbestpos, gbestval]=ga_pso_tsp(cities)
N=size(cities,1); % Number of cities
popsize=50;       % Population size
maxiter=1000;     % Maximum number of iterations
...
% Initialize population and velocities randomly
positions=randperm(N,popsize)';
velocities=repmat([1:N], popsize, 1);
...

for iter=1:maxiter
    ...
    % Update personal best positions
    pbestvals=min(pbestvals,min(fitness));
    [~,idx]=min(fitness);
    if fitness(idx)<pbestvals(idx)
        pbestpos(:,idx)=positions(:,idx);
        pbestvals(idx)=fitness(idx);
    end
    
    % Perform crossover & mutation operations from Genetic Algorithm here
    ...

    % Evaluate new solutions after applying genetic operators
    ...
    
    % Update global best position based on current iteration's results
    ...
end

#### 使用 PSO 粒子群算法求解 TSP 问题
对于采用纯 PSO 方法处理 TSP 来说，则更侧重于速度向量的调整规则以指导个体朝着更好的方向移动。下面给出了一段简化版的 PSO-TSP 编程实例[^3]：

CityNum = 30; % City count
MaxIter = 1000; % Max iteration times
PopulationSize = 50; % Particle swarm size

Position = randi([1, CityNum], PopulationSize, CityNum);
Velocity = round(rand(PopulationSize, CityNum)*CityNum);

for Iteration = 1 : MaxIter
    FitnessValue = CalculateFitness(Position);
    PBestIndex = find(FitnessValue == min(FitnessValue), 1);
    GBestPos = Position(PBestIndex,:);
    
    Velocity = w * Velocity + c1*rand().*(PBest - Position) + c2*rand().*(GBestPos - Position);
    Position = mod(round(Position + Velocity), CityNum) + 1;
end