使用DWA算法与蚁群算法求解TSP问题的MATLAB代码

以下是使用DWA算法与蚁群算法求解TSP问题的MATLAB代码：

% DWA算法求解TSP问题
% 蚁群算法求解TSP问题
clc;clear;close all;

%% 生成城市坐标
n = 50; % 城市数量
x = rand(1,n)*10;
y = rand(1,n)*10;
plot(x,y,'o');
hold on;

%% DWA算法求解TSP问题
% 初始化参数
N = 1000; % 迭代次数
alpha = 0.95; % 降温系数
T0 = 100; % 初始温度
T = T0; % 当前温度
L = zeros(1,N); % 保存每次迭代的路径长度
bestL = inf; % 最佳路径长度
bestPath = []; % 最佳路径
path = randperm(n); % 初始路径
for i = 1:N
    % 交换两个城市位置
    a = randi(n);
    b = randi(n);
    while a == b
        b = randi(n);
    end
    newPath = path;
    newPath([a b]) = newPath([b a]);
    % 计算路径长度
    newL = 0;
    for j = 1:n-1
        newL = newL + sqrt((x(newPath(j+1))-x(newPath(j)))^2 + (y(newPath(j+1))-y(newPath(j)))^2);
    end
    newL = newL + sqrt((x(newPath(1))-x(newPath(n)))^2 + (y(newPath(1))-y(newPath(n)))^2);
    deltaL = newL - L(i);
    % 判断是否接受新解
    if deltaL < 0 || exp(-deltaL/T) > rand()
        path = newPath;
        L(i+1) = newL;
        if newL < bestL
            bestL = newL;
            bestPath = newPath;
        end
    else
        L(i+1) = L(i);
    end
    % 降温
    T = alpha*T;
end
% 绘制最佳路径
plot(x(bestPath),y(bestPath),'r-');
title(sprintf('DWA算法求解TSP问题,路径长度=%f',bestL));

%% 蚁群算法求解TSP问题
% 初始化参数
m = 50; % 蚂蚁数量
alpha = 1; % 信息素重要程度因子
beta = 5; % 启发函数重要程度因子
rho = 0.1; % 信息素挥发因子
Q = 1; % 常系数
eta = 1./sqrt((repmat(x,n,1)-repmat(x',1,n)).^2 + (repmat(y,n,1)-repmat(y',1,n)).^2); % 启发函数
tau = ones(n,n); % 信息素矩阵
L = zeros(1,N); % 保存每次迭代的路径长度
bestL = inf; % 最佳路径长度
bestPath = []; % 最佳路径
for i = 1:N
    % 蚂蚁寻找路径
    path = zeros(m,n);
    for j = 1:m
        unvisited = 1:n;
        current = unvisited(randi(n));
        unvisited(unvisited==current) = [];
        path(j,1) = current;
        for k = 2:n
            p = tau(current,unvisited).^alpha .* eta(current,unvisited).^beta;
            p = p/sum(p);
            current = unvisited(find(rand()<cumsum(p),1));
            unvisited(unvisited==current) = [];
            path(j,k) = current;
        end
        % 计算路径长度
        L(j) = 0;
        for k = 1:n-1
            L(j) = L(j) + sqrt((x(path(j,k+1))-x(path(j,k)))^2 + (y(path(j,k+1))-y(path(j,k)))^2);
        end
        L(j) = L(j) + sqrt((x(path(j,1))-x(path(j,n)))^2 + (y(path(j,1))-y(path(j,n)))^2);
        % 更新最佳路径
        if L(j) < bestL
            bestL = L(j);
            bestPath = path(j,:);
        end
    end
    % 更新信息素
    deltaTau = zeros(n,n);
    for j = 1:m
        for k = 1:n-1
            deltaTau(path(j,k),path(j,k+1)) = deltaTau(path(j,k),path(j,k+1)) + Q/L(j);
        end
        deltaTau(path(j,n),path(j,1)) = deltaTau(path(j,n),path(j,1)) + Q/L(j);
    end
    tau = (1-rho)*tau + deltaTau;
end
% 绘制最佳路径
plot(x(bestPath),y(bestPath),'g-');
title(sprintf('DWA算法与蚁群算法求解TSP问题,路径长度=%f',bestL));