遗传蚁群算法求解TSP问题的MATLAB代码实现

以下是遗传蚁群算法求解TSP问题的MATLAB代码实现：

% TSP问题求解的遗传蚁群算法
% 算法步骤：
% 1. 初始化群体
% 2. 计算每个个体的适应度
% 3. 选择父代个体
% 4. 交叉操作
% 5. 变异操作
% 6. 计算新个体的适应度
% 7. 选择生存个体
% 8. 满足终止条件则输出结果，否则回到2

clear;
clc;

% TSP问题的数据
x = [0 4 2 5 6 1 3]; % 城市的x坐标
y = [0 1 5 2 4 7 6]; % 城市的y坐标
n = length(x); % 城市数量

% 遗传算法的参数
popSize = 50; % 种群大小
crossRate = 0.8; % 交叉概率
mutateRate = 0.02; % 变异概率
maxGen = 100; % 最大迭代次数

% 初始化群体
pop = zeros(popSize, n);
for i = 1:popSize
    pop(i,:) = randperm(n); % 随机生成一条路径
end

% 计算适应度
fit = zeros(popSize, 1);
for i = 1:popSize
    fit(i) = tspLength(pop(i,:), x, y); % 计算路径长度
end

% 迭代
for gen = 1:maxGen
    % 选择父代个体
    parent = zeros(popSize, n);
    for i = 1:popSize
        % 轮盘赌选择
        idx1 = roulette(fit);
        idx2 = roulette(fit);
        parent(i,:) = pop(idx1,:); % 选择父代
        if rand < crossRate % 以交叉概率交叉
            parent(i,:) = crossover(parent(i,:), pop(idx2,:)); % 交叉
        end
        if rand < mutateRate % 以变异概率变异
            parent(i,:) = mutate(parent(i,:)); % 变异
        end
    end
    
    % 计算新个体的适应度
    child = zeros(popSize, n);
    for i = 1:popSize
        child(i,:) = parent(i,:);
        fitChild = tspLength(child(i,:), x, y);
        if fitChild < fit(i) % 如果新个体更优，则替换
            fit(i) = fitChild;
            pop(i,:) = child(i,:);
        end
    end
    
    % 输出结果
    [~, idx] = min(fit);
    bestPath = pop(idx,:);
    bestLength = fit(idx);
    fprintf('第%d代：最短路径长度为%.2f\n', gen, bestLength);
end

% 绘制最优路径
figure;
plot(x(bestPath), y(bestPath), 'r-o');
title(sprintf('最短路径长度为%.2f', bestLength));

% 计算路径长度
function len = tspLength(path, x, y)
    len = 0;
    n = length(path);
    for i = 1:n-1
        len = len + sqrt((x(path(i+1))-x(path(i)))^2 + (y(path(i+1))-y(path(i)))^2);
    end
    len = len + sqrt((x(path(1))-x(path(n)))^2 + (y(path(1))-y(path(n)))^2);
end

% 轮盘赌选择
function idx = roulette(fit)
    popSize = length(fit);
    p = fit./sum(fit); % 计算选择概率
    r = rand;
    for i = 1:popSize
        r = r - p(i);
        if r <= 0
            idx = i;
            break;
        end
    end
end

% 交叉操作
function child = crossover(parent1, parent2)
    n = length(parent1);
    child = zeros(1, n);
    % 随机选择一段基因
    idx1 = randi(n-1);
    idx2 = randi(n-idx1) + idx1;
    % 复制父代1的这段基因
    child(idx1:idx2) = parent1(idx1:idx2);
    % 填充剩余的基因
    j = 1;
    for i = 1:n
        if j == idx1
            j = idx2 + 1;
        end
        if ~ismember(parent2(i), child)
            child(j) = parent2(i);
            j = j + 1;
        end
    end
end

% 变异操作
function child = mutate(parent)
    n = length(parent);
    child = parent;
    % 随机选择两个位置
    idx1 = randi(n);
    idx2 = randi(n);
    % 交换这两个位置的基因
    temp = child(idx1);
    child(idx1) = child(idx2);
    child(idx2) = temp;
end

其中，`tspLength`函数用于计算路径长度，`roulette`函数用于轮盘赌选择父代个体，`crossover`函数用于交叉操作，`mutate`函数用于变异操作。在主函数中，先初始化群体，然后迭代直到满足最大迭代次数，每次迭代都选择父代个体、进行交叉和变异操作，计算新个体的适应度，最后输出最优路径及其长度。