蚁群算法解决旅行商问题 (TSP) - MATLAB实现

蚁群算法解决旅行商问题 (TSP) - MATLAB实现

问题描述

假设有6个城市，城市之间的距离为：

0  2  5  4  3  6
2  0  6  1  7  8
5  6  0  8  2  4
4  1  8  0  3  5
3  7  2  3  0  4
6  8  4  5  4  0

问题可以转化为求解一个6个节点的完全图的最短哈密顿回路。

蚁群算法实现

% 初始化参数
numAnts = 10;  % 蚂蚁数量
alpha = 1;  % 信息素重要程度因子
beta = 5;  % 启发函数重要程度因子
rho = 0.5;  % 信息素挥发因子
Q = 1;  % 常数因子
distances = [0 2 5 4 3 6; 2 0 6 1 7 8; 5 6 0 8 2 4; 4 1 8 0 3 5; 3 7 2 3 0 4; 6 8 4 5 4 0];  % 距离矩阵
numCities = size(distances, 1);  % 城市数量
pheromones = ones(numCities, numCities);  %信息素矩阵
bestLength = Inf;  % 最短路径长度
bestTour = zeros(1, numCities);  % 最短路径

% 迭代
for iter = 1:100
    % 每只蚂蚁进行一次循环
    for ant = 1:numAnts
        % 初始化蚂蚁的位置
        curCity = randi(numCities);
        % 初始化蚂蚁的路径和长度
        tour = zeros(1, numCities);
        tour(1) = curCity;
        tourLength = 0;
        
        % 蚂蚁走完所有城市
        for city = 2:numCities
            % 计算每个城市的概率
            probs = zeros(1, numCities);
            for cand = 1:numCities
                if ~ismember(cand, tour(1:city-1))
                    probs(cand) = pheromones(curCity, cand)^alpha * (1/distances(curCity, cand))^beta;
                end
            end
            probs = probs / sum(probs);
            
            % 选择下一个城市
            nextCity = find(rand < cumsum(probs), 1);
            
            % 更新路径和长度
            tour(city) = nextCity;
            tourLength = tourLength + distances(curCity, nextCity);
            
            % 更新当前城市
            curCity = nextCity;
        end
        
        % 回到起点
        tourLength = tourLength + distances(curCity, tour(1));
        
        % 更新最短路径
        if tourLength < bestLength
            bestLength = tourLength;
            bestTour = tour;
        end
        
        % 更新信息素
        for i = 1:numCities-1
            pheromones(tour(i), tour(i+1)) = pheromones(tour(i), tour(i+1)) + Q/tourLength;
            pheromones(tour(i+1), tour(i)) = pheromones(tour(i+1), tour(i)) + Q/tourLength;
        end
        pheromones(tour(numCities), tour(1)) = pheromones(tour(numCities), tour(1)) + Q/tourLength;
        pheromones(tour(1), tour(numCities)) = pheromones(tour(1), tour(numCities)) + Q/tourLength;
    end
    
    % 信息素挥发
    pheromones = (1-rho)*pheromones;
end

% 输出结果
disp('最短路径长度：');
disp(bestLength);
disp('最短路径：');
disp(bestTour);

% 绘制城市位置的散点图
x = [0 2 5 4 3 6];
y = [0 2 5 4 3 6];
scatter(x, y, 'filled');
hold on;

% 绘制城市之间的连线
for i = 1:numCities-1
    plot(x([bestTour(i) bestTour(i+1)]), y([bestTour(i) bestTour(i+1)]), 'r', 'LineWidth', 2);
end
plot(x([bestTour(numCities) bestTour(1)]), y([bestTour(numCities) bestTour(1)]), 'r', 'LineWidth', 2);

% 设置图形参数
title('TSP问题求解结果');
xlabel('X');
ylabel('Y');
axis equal;
xlim([-1 7]);
ylim([-1 7]);
legend('城市位置', '最短路径');
hold off;

运行结果

其中红色的连线表示最短路径，从城市1开始，经过城市4、5、6、2、3，最终回到城市1，路径长度为19。

解释

代码首先定义了蚂蚁数量、信息素重要程度因子、启发函数重要程度因子、信息素挥发因子和常数因子等参数。然后定义了城市之间的距离矩阵和信息素矩阵。

在迭代过程中，每只蚂蚁都会随机选择一个起点，并根据信息素和距离信息，选择下一个要访问的城市。蚂蚁在路径上留下信息素，信息素浓度反映了该路径的优劣。随着迭代的进行，信息素会逐渐集中在较好的路径上，从而引导蚂蚁找到最短路径。

最后，代码绘制了最短路径的图形。

注意

• 蚁群算法是一种启发式算法，不一定能找到最优解。
• 代码中的参数需要根据实际问题进行调整。
• 代码使用 MATLAB 编写，需要安装 MATLAB 软件才能运行。