問題展現(xiàn)

假設(shè)有一個(gè)旅行商人要拜訪全國 31 個(gè)省會城市，他需要選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪一次，而且最后要回到原來出發(fā)的城市。路徑的選擇要求是：所選路徑的路程為所有路徑之中的最小值。
全國 31 個(gè)省會城市的坐標(biāo)為 [1304 2312; 3639 1315; 4177 2244; 3712 1399; 3488 1535; 3326 1556; 3238 1229; 4196 1004; 4312 790; 4386 570; 3007 1970; 2562 1756; 2788 1491; 2381 1676; 1332 695; 3715 1678; 3918 2179; 4061 2370; 3780 2212; 3676 2578; 4029 2838; 4263 2931; 3429 1908; 3507 2367; 3394 2643; 3439 3201; 2935 3240; 3140 3550; 2545 2357; 2778 2826; 2370 2975]。

解決代碼

代碼1

clc; close all; clear

% 設(shè)置初始化參數(shù)

NC_max=200; % 最大迭代次數(shù)
m=50; % 螞蟻個(gè)數(shù)
Alpha=1; % 表征信息素重要程度的參數(shù)
Beta=5; % 表征啟發(fā)式因子重要程度的參數(shù)
Rho=0.1;% 信息素蒸發(fā)系數(shù)
Q=100;% 信息素增加強(qiáng)度系數(shù)
% n個(gè)城市的坐標(biāo)，n×2的矩陣
Citys = [1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...
    3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...
    2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...
    3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...
    3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...
    2370 2975];


%% 第1步：變量初始化
n = size(Citys, 1); % n表示問題的規(guī)模（城市個(gè)數(shù)）
D = distanceMatrix(Citys); % D表示完全圖的賦權(quán)鄰接矩陣
Eta = 1 ./ D; % Eta為啟發(fā)因子，這里設(shè)為距離的倒數(shù)
Tau = ones(n, n); % Tau為信息素矩陣
Tabu = zeros(m, n); % 存儲并記錄路徑的生成
NC = 1; % 迭代計(jì)數(shù)器，記錄迭代次數(shù)
R_best = zeros(NC_max, n); % 各代最佳路線
L_best = inf .* ones(NC_max, 1); % 各代最佳路線的長度
L_ave = zeros(NC_max, 1); % 各代路線的平均長度

while NC <= NC_max % 停止條件之一：達(dá)到最大迭代次數(shù)，停止
    %% 第2步：將m只螞蟻放到n個(gè)城市上
    Randpos = []; % 隨機(jī)存取
    for i = 1:(ceil(m / n))
        Randpos = [Randpos, randperm(n)];
    end
    Tabu(:, 1) = (Randpos(1, 1:m))';

    %% 第3步：m只螞蟻按概率函數(shù)選擇下一座城市，完成各自的周游
    for j=2:n % 所在城市不計(jì)算
        for i=1:m
            visited=Tabu(i,1:(j-1)); % 記錄已訪問的城市，避免重復(fù)訪問
            J = 1:n; % 待訪問的城市
            J(ismember(J, visited)) = []; % 刪除已訪問城市

            % 計(jì)算待選城市的概率分布
            P = (Tau(visited(end), J).^Alpha) .* (Eta(visited(end), J).^Beta);
            % visited(end)表示螞蟻現(xiàn)在所在城市編號，J(k)表示下一步要訪問的城市編號
            P=P/(sum(P)); % 把各個(gè)路徑概率統(tǒng)一到和為1

            % 按概率原則選取下一個(gè)城市
            Pcum=cumsum(P); % cumsum，元素累加即求和
            % 螞蟻要選擇的下一個(gè)城市不是按最大概率，就是要用到輪盤法則，不然影響全局收縮能力，所以用累積函數(shù)
            Select=find(Pcum>=rand); % 若計(jì)算的概率大于原來的就選擇這條路線
            to_visit=J(Select(1));
            Tabu(i,j)=to_visit; % 提取這些城市的編號到to_visit中
        end
    end

    % 將當(dāng)前最佳路徑加入到下一次迭代
    if NC >= 2
        Tabu(1,:) = R_best(NC-1,:);
    end

    %% 第4步：記錄本次迭代最佳路線
    L = zeros(m, 1); % 開始距離為0，m*1的列向量
    for i = 1:m
        R = Tabu(i, :);
        for j = 1:(n - 1)
            L(i) = L(i) + D(R(j), R(j + 1)); % 原距離加上第j個(gè)城市到第j+1個(gè)城市的距離
        end
        L(i) = L(i) + D(R(1), R(n)); % 一輪下來后走過的距離
    end
    L_best(NC) = min(L); % 最佳距離取最小
    pos = find(L == L_best(NC));
    R_best(NC, :) = Tabu(pos(1), :); % 此輪迭代后的最佳路線
    % 找到路徑最短的那條螞蟻所在的城市先后順序
    % pos(1)中1表示萬一有長度一樣的兩條螞蟻，那就選第一個(gè)
    L_ave(NC) = mean(L); % 此輪迭代后的平均距離
    NC = NC + 1; % 迭代繼續(xù)

    %% 第5步：更新信息素
    Delta_Tau = zeros(n, n); % 開始時(shí)信息素為n*n的0矩陣
    for i = 1:m
        R = Tabu(i, [1:n, 1]);
        indices = sub2ind(size(Delta_Tau), R(1:end-1), R(2:end));
        Delta_Tau(indices) = Delta_Tau(indices) + Q ./ L(i);
    end % 此次循環(huán)在路徑（i，j）上的信息素增量
    Tau = (1 - Rho) .* Tau + Delta_Tau;

    %% 第6步：禁忌表清零
    Tabu = zeros(m, n); % 直到最大迭代次數(shù)
end

%% 第7步：輸出結(jié)果
Pos = find(L_best == min(L_best));
Shortest_Route = R_best(Pos(1), :);
Shortest_Length = L_best(Pos(1));
displayResults(Citys, Shortest_Route, Shortest_Length, L_best, L_ave)
disp(['最短距離:' num2str(Shortest_Length)]);
disp(['最短路徑:' num2str([Shortest_Route Shortest_Route(1)])]);


%% 函數(shù)部分
function D = distanceMatrix(C)
n = size(C, 1);
D = zeros(n, n);
for i = 1:n
    for j = 1:n
        if i ~= j
            D(i, j) = norm(C(i, :) - C(j, :));
        else
            D(i, j) = eps;
        end
        D(j, i) = D(i, j);
    end
end
end

function displayResults(Citys, Shortest_Route, Shortest_Length, L_best, L_ave)
figure(1)
N = length(Shortest_Route);
scatter(Citys(:, 1), Citys(:, 2));
hold on;
R = [Shortest_Route, Shortest_Route(1)];
for ii = 1:N
    plot(Citys(R(ii:ii+1), 1), Citys(R(ii:ii+1), 2),'o-', 'LineWidth',1.5);
    hold on;
end
text(Citys(Shortest_Route(1), 1), Citys(Shortest_Route(1), 2), '   起點(diǎn)');
text(Citys(Shortest_Route(end), 1), Citys(Shortest_Route(end), 2), '   終點(diǎn)');
xlabel('城市位置橫坐標(biāo)');
ylabel('城市位置縱坐標(biāo)');
title('蟻群算法優(yōu)化旅行商問題');
grid on;

figure(2)
plot(1:length(L_best), L_best(1:end), 'b', 'LineWidth',1.5);
hold on;
plot(1:length(L_ave), L_ave(1:end), 'r', 'LineWidth',1.5);
legend('最短距離', '平均距離');
xlabel('迭代次數(shù)');
ylabel('距離');
title('平均距離和最短距離');
end

輸出結(jié)果

最短距離:15609.4771
最短路徑:15  14  12  13  11  23  16   5   6   7   2   4   8   9  10   3  18  17  19  24  25  20  21  22  26  28  27  30  31  29   1  15

代碼2

clc; close all; clear

% Initialize the parameters
num_ants = 50; % Number of ants
num_iterations = 200; % Number of iterations
alpha = 1; % Importance of pheromone
beta = 5; % Importance of heuristic information
rho = 0.1; % Evaporation rate of pheromone
coordinates = [1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...
    3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...
    2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...
    3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...
    3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...
    2370 2975];

% Calculate distance matrix
n = size(coordinates, 1);
dist_matrix = zeros(n);

% error statement!!!
% start_city_custom = input(sprintf('Enter the starting city index (1 to %d): ', n));
% start_city = start_city_custom;

for i = 1:n
    for j = i+1:n
        dist_matrix(i, j) = norm(coordinates(i, :) - coordinates(j, :));
        dist_matrix(j, i) = dist_matrix(i, j);
    end
end

% Initialize the pheromone matrix
pheromone = ones(n, n);

% Start the iterations
best_distance = inf;
best_path = [];

for i = 1:num_iterations
    paths = zeros(num_ants, n + 1);
    path_lengths = zeros(num_ants, 1);

    % For each ant
    for j = 1:num_ants
        start_city = randi(n);
        paths(j, 1) = start_city;

        for step = 2:n
            current_city = paths(j, step - 1);
            not_visited = setdiff(1:n, paths(j, 1:step - 1));
            prob = (pheromone(current_city, not_visited) .^ alpha) .* ((1 ./ dist_matrix(current_city, not_visited)) .^ beta);
            probabilities = prob / sum(prob);
            next_city = not_visited(randsample(length(not_visited), 1, true, probabilities));
            paths(j, step) = next_city;
        end

        paths(j, n + 1) = paths(j, 1);
        path_lengths(j) = sum(dist_matrix(sub2ind(size(dist_matrix), paths(j, 1:n), paths(j, 2:n + 1))));

        if path_lengths(j) < best_distance
            best_distance = path_lengths(j);
            best_path = paths(j, :);
        end
    end

    % Update the pheromone matrix
    pheromone = (1 - rho) * pheromone;
    for j = 1:num_ants
        for step = 1:n
            pheromone(paths(j, step), paths(j, step + 1)) = ...
                pheromone(paths(j, step), paths(j, step + 1)) + 1 / path_lengths(j);
        end
    end
end

% Print the best path
num_cities = size(coordinates, 1);
fprintf('Optimal path:\n');
for j = 1:num_cities
    fprintf('%d -> ', best_path(j));
end
fprintf('%d\n', best_path(1));
fprintf('Optimal distance: %f\n', best_distance);

% {
% start_city=randi(n)用于為每只螞蟻隨機(jī)選擇起始城市。
% n 代表城市數(shù)，randi(n) 生成1到n（含）之間的隨機(jī)整數(shù)。
% 螞蟻從不同的城市開始，這增加了探索解決方案的多樣性，有助于防止算法陷入局部最優(yōu)。
% }

輸出結(jié)果

Optimal path:
14 -> 12 -> 13 -> 11 -> 23 -> 16 -> 5 -> 6 -> 7 -> 2 -> 4 -> 8 -> 9 -> 10 -> 3 -> 18 -> 17 -> 19 -> 24 -> 25 -> 20 -> 21 -> 22 -> 26 -> 28 -> 27 -> 30 -> 31 -> 29 -> 1 -> 15 -> 14
Optimal distance: 15609.477144

代碼3

clc; close all; clear

% Coordinates of 31 provincial capital cities in China
coords = [1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...
    3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...
    2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...
    3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...
    3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...
    2370 2975];

% Calculate distance matrix
n = size(coords, 1);
dist_matrix = zeros(n);

for i = 1:n
    for j = i+1:n
        dist_matrix(i, j) = norm(coords(i, :) - coords(j, :));
        dist_matrix(j, i) = dist_matrix(i, j);
    end
end

% Initialize ACO parameters
n_ants = 50;
n_iterations = 200;
alpha = 1;
beta = 5;
rho = 0.1;
Q = 100;

% ACO algorithm
[best_path, best_dist, avg_dists, best_dists] = ACO(dist_matrix, n_ants, n_iterations, alpha, beta, rho, Q);

% Display the optimal path and its distance
disp("Optimal path:");
optimal_path_str = join(string(best_path), "->"); 
disp(optimal_path_str); 
disp("Optimal distance:");
% disp(best_dist);
fprintf('%.6f\n', best_dist);


% Plot the cities and the optimal path
figure;
plot(coords(:, 1), coords(:, 2), 'o');
hold on;
plot(coords(best_path, 1), coords(best_path, 2), '-');
title('Cities and the Optimal Path');
xlabel('X Coordinate');
ylabel('Y Coordinate');
grid on;

% Annotate city numbers
for i = 1:n
    text(coords(i, 1), coords(i, 2), num2str(i), 'HorizontalAlignment', 'left', 'VerticalAlignment', 'bottom');
end

% Plot the convergence curves
figure;
plot(1:n_iterations, best_dists, 'b-', 1:n_iterations, avg_dists, 'r-');
title('Convergence Curves');
xlabel('Number of Iterations');
ylabel('Path Distance');
legend('Best Path', 'Average Path');
grid on;

% ACO function
function [best_path, best_dist, avg_dists, best_dists] =...
    ACO(dist_matrix, n_ants, n_iterations, alpha, beta, rho, Q)
n = size(dist_matrix, 1);
best_path = zeros(1, n + 1);
best_dist = Inf;
avg_dists = zeros(1, n_iterations);
best_dists = zeros(1, n_iterations);

pheromone_matrix = ones(n, n);
visibility_matrix = 1 ./ dist_matrix;

for iter = 1:n_iterations
    paths = zeros(n_ants, n + 1);
    path_lengths = zeros(n_ants, 1);

    for ant = 1:n_ants
        start_city = randi(n);
        paths(ant, 1) = start_city;
        for step = 2:n
            current_city = paths(ant, step - 1);
            not_visited = setdiff(1:n, paths(ant, 1:step - 1));
            prob = (pheromone_matrix(current_city, not_visited) .^ alpha) .*...
                (visibility_matrix(current_city, not_visited) .^ beta);
            next_city = not_visited(randsample(length(not_visited), 1, true, prob / sum(prob)));

            paths(ant, step) = next_city;
        end

        paths(ant, n + 1) = paths(ant, 1);
        path_lengths(ant) = sum(dist_matrix(sub2ind(size(dist_matrix), paths(ant, 1:n), paths(ant, 2:n + 1))));

        if path_lengths(ant) < best_dist
            best_dist = path_lengths(ant);
            best_path = paths(ant, :);
        end
    end

    % Update pheromone matrix
    pheromone_matrix = (1 - rho) * pheromone_matrix;
    for ant = 1:n_ants
        for step = 1:n
            pheromone_matrix(paths(ant, step), paths(ant, step + 1)) = ...
                pheromone_matrix(paths(ant, step), paths(ant, step + 1)) + Q / path_lengths(ant);
        end
    end

    % Calculate average path length and record the best distance
    avg_dists(iter) = mean(path_lengths);
    best_dists(iter) = best_dist;
end
end

輸出結(jié)果

Optimal path:
15->14->12->13->11->23->16->5->6->7->2->4->8->9->10->3->18->17->19->24->25->20->21->22->26->28->27->30->31->29->1->15
Optimal distance:
15609.477144

文章來源地址http://www.zghlxwxcb.cn/news/detail-414257.html

到了這里，關(guān)于Matlab蟻群算法求解旅行商問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！