遗传算法最短路径matlab代码

以下是遗传算法求解最短路径的 MATLAB 代码：

% 遗传算法求解最短路径
% 输入参数：邻接矩阵G，起点s，终点t，种群大小popsize，迭代次数maxgen
% 输出参数：最短路径path，最短距离dist

function [path, dist] = GA_shortest_path(G, s, t, popsize, maxgen)
    n = size(G, 1);
    pc = 0.8; % 交叉概率
    pm = 0.05; % 变异概率
    len = 2 * n - 1; % 染色体长度
    pop = zeros(popsize, len); % 种群初始化
    pop(:, 1) = s;
    pop(:, len) = t;
    for i = 1 : popsize
        path = randperm(n - 2) + 1;
        pop(i, 2 : end - 1) = path;
    end
    bestfit = inf; % 初始最优解
    for i = 1 : maxgen
        fit = zeros(popsize, 1);
        for j = 1 : popsize
            path = pop(j, :);
            dist = 0;
            for k = 1 : len - 1
                dist = dist + G(path(k), path(k + 1));
            end
            fit(j) = dist;
            if dist < bestfit % 更新最优解
                bestfit = dist;
                bestpath = path;
            end
        end
        % 选择操作
        [fit, idx] = sort(fit);
        pop = pop(idx, :);
        newpop = zeros(popsize, len);
        for j = 1 : popsize
            parent1 = pop(ceil(rand * popsize), :);
            parent2 = pop(ceil(rand * popsize), :);
            % 交叉操作
            if rand < pc
                pos = ceil(rand * (len - 2)) + 1;
                child = [parent1(1 : pos), parent2(pos + 1 : end)];
                % 变异操作
                if rand < pm
                    pos = ceil(rand * (len - 2)) + 1;
                    child(pos) = randperm(n - 2) + 1;
                end
            else
                child = parent1;
            end
            newpop(j, :) = child;
        end
        pop = newpop;
    end
    path = bestpath;
    dist = bestfit;
end

其中，邻接矩阵 G 的第 i 行第 j 列表示从节点 i 到节点 j 的边权重。s 和 t 分别为起点和终点，popsize 和 maxgen 分别为种群大小和迭代次数。最终输出最短路径 path 和最短距离 dist。