遗传算法解决tsp问题 matlab代码

遗传算法是一种基于生物进化原理的优化算法，它通过模拟自然选择、交叉、变异等操作，不断迭代寻找最优解。而TSP问题是一种经典的组合优化问题，即给定若干个城市和它们之间的距离，求解访问所有城市的最短路径。

遗传算法可以被用来解决TSP问题，其具体步骤如下：
1. 将每个城市看做遗传算法中的一个基因，构建初始种群。
2. 通过计算每个个体的适应度（即路径长度），按照适应度大小进行选择、交叉、变异等操作，生成新的种群。
3. 迭代执行第2步，直到达到设定的终止条件为止（如达到最大迭代次数或满足一定的收敛条件）。
4. 选取最优解作为TSP问题的解。

以下是MATLAB代码的一个简单实现：

% TSP问题数据，包括城市坐标和距离矩阵
N = 10; % 城市数量
x = rand(1,N)*10; % 坐标范围[0,10]
y = rand(1,N)*10;
D = zeros(N,N); % 距离矩阵
for i=1:N
    for j=i+1:N
        D(i,j) = sqrt((x(i)-x(j))^2 + (y(i)-y(j))^2);
        D(j,i) = D(i,j);
    end
end

% 遗传算法参数设置
popSize = 50; % 种群大小
maxGen = 100; % 最大迭代次数
pc = 0.8; % 交叉概率
pm = 0.1; % 变异概率

% 初始化种群，每个个体表示一个城市序列
pop = zeros(popSize,N);
for i=1:popSize
    pop(i,:) = randperm(N);
end

% 迭代执行遗传算法
bestFit = inf;
for gen=1:maxGen
    % 计算每个个体的适应度（即路径长度）
    fits = zeros(1,popSize);
    for i=1:popSize
        fits(i) = sum(D(pop(i,:),circshift(pop(i,:),[0,-1])));
    end
    
    % 记录最优解
    [minFit,minIdx] = min(fits);
    if minFit < bestFit
        bestFit = minFit;
        bestInd = pop(minIdx,:);
    end
    
    % 选择、交叉、变异生成新种群
    newPop = zeros(size(pop));
    for i=1:2:popSize-1
        % 轮盘赌选择两个个体
        p1 = rouletteWheelSelection(fits);
        p2 = rouletteWheelSelection(fits);
        
        % 交叉
        if rand() < pc
            [c1,c2] = crossover(pop(p1,:),pop(p2,:));
        else
            c1 = pop(p1,:);
            c2 = pop(p2,:);
        end
        
        % 变异
        if rand() < pm
            c1 = mutation(c1);
        end
        if rand() < pm
            c2 = mutation(c2);
        end
        
        % 加入新种群中
        newPop(i,:) = c1;
        newPop(i+1,:) = c2;
    end
    
    % 更新种群
    pop = newPop;
end

% 输出结果
disp('最短路径长度为：');
disp(bestFit);
disp('最优路径为：');
disp(bestInd);

% 轮盘赌选择函数
function idx = rouletteWheelSelection(fits)
    % 计算适应度总和
    totalFit = sum(fits);
    
    % 计算每个个体被选中的概率
    probs = fits / totalFit;
    
    % 根据概率进行选择
    r = rand();
    accProb = 0;
    for i=1:length(probs)
        accProb = accProb + probs(i);
        if r <= accProb
            idx = i;
            break;
        end
    end
end

% 交叉函数，采用部分匹配交叉（PMX）
function [c1,c2] = crossover(p1,p2)
    n = length(p1);
    
    % 随机选取交叉区间
    pt1 = randi(n-1);
    pt2 = randi([pt1+1,n]);
    
    % 将p2中与p1交叉区间重复的元素删除
    c2 = p2;
    for i=pt1:pt2
        idx = find(c2 == p1(i));
        if idx ~= i
            c2(idx) = c2(i);
            c2(i) = p1(i);
        end
    end
    
    % 将p1中交叉区间未出现的元素插入到c2中对应位置
    c1 = p1;
    for i=pt1:pt2
        idx = find(c1 == c2(i));
        if idx ~= i
            while any(c1(pt1:pt2) == c2(idx))
                idx = find(c1 == c2(idx));
            end
            c1(idx) = c1(i);
            c1(i) = c2(i);
        end
    end
end

% 变异函数，采用两点变异
function c = mutation(p)
    n = length(p);
    
    % 随机选取两个位置进行变异
    pt1 = randi(n);
    pt2 = randi(n);
    
    % 交换两个位置上的基因
    tmp = p(pt1);
    p(pt1) = p(pt2);
    p(pt2) = tmp;
    
    c = p;
end