遗传算法tsp matlab代码

以下是一个简单的遗传算法解决TSP问题的Matlab代码：

% TSP问题的遗传算法
clear all;
close all;

% 城市坐标
cities = [0.5, 0.5;
          0.9, 0.1;
          0.1, 0.9;
          0.9, 0.9;
          0.2, 0.2;
          0.4, 0.6;
          0.6, 0.4;
          0.8, 0.2;
          0.2, 0.8;
          0.6, 0.6];

% 参数设置
popSize = 50; % 种群大小
numGen = 200; % 迭代次数
mutProb = 0.05; % 变异概率
eliteCount = 2; % 精英个数
numCities = size(cities, 1); % 城市数
distMat = squareform(pdist(cities)); % 距离矩阵

% 初始化种群
pop = zeros(popSize, numCities);
for i = 1:popSize
    pop(i,:) = randperm(numCities);
end

% 迭代
for g = 1:numGen
    % 计算适应度
    fitness = zeros(popSize, 1);
    for i = 1:popSize
        fitness(i) = 1 / sum(distMat(pop(i,:), [1:end, 1]));
    end
    
    % 选择精英
    [sortedFitness, idx] = sort(fitness, 'descend');
    elite = pop(idx(1:eliteCount), :);
    
    % 选择父代
    parents = zeros(popSize - eliteCount, numCities);
    for i = 1:popSize - eliteCount
        % 轮盘赌选择
        prob = fitness / sum(fitness);
        probSum = cumsum(prob);
        r = rand();
        for j = 1:popSize
            if r <= probSum(j)
                parents(i,:) = pop(j,:);
                break;
            end
        end
    end
    
    % 交叉
    offspring = zeros(size(parents));
    for i = 1:size(parents, 1)
        % 随机选择两个父代
        idx = randperm(size(parents, 1), 2);
        parent1 = parents(idx(1), :);
        parent2 = parents(idx(2), :);
        
        % 交叉点
        k = randi(numCities - 2) + 1;
        
        % 交叉操作
        offspring(i, :) = [parent1(1:k), parent2(~ismember(parent2, parent1(1:k)))];
    end
    
    % 变异
    for i = 1:size(offspring, 1)
        if rand() < mutProb
            % 选择两个变异点
            idx = randperm(numCities, 2);
            % 交换变异点
            offspring(i, idx) = offspring(i, [idx(2), idx(1)]);
        end
    end
    
    % 合并种群
    pop = [elite; offspring];
end

% 计算最优解
[sortedFitness, idx] = sort(fitness, 'descend');
bestPath = pop(idx(1),:);
bestDist = sum(distMat(bestPath, [1:end, 1]));

% 绘图
figure;
plot(cities(:,1), cities(:,2), 'ko', 'MarkerSize', 10, 'LineWidth', 2);
hold on;
plot([cities(bestPath, 1); cities(bestPath(1), 1)], [cities(bestPath, 2); cities(bestPath(1), 2)], 'r-', 'LineWidth', 2);
hold off;
axis([0 1 0 1]);
axis square;
title(sprintf('最短路径长度: %.4f', bestDist));

这个代码的主要思路是：

1. 初始化种群，每个个体是城市的排列；
2. 计算每个个体的适应度，适应度定义为路径长度的倒数；
3. 选择精英，即适应度最高的个体；
4. 选择父代，采用轮盘赌选择；
5. 交叉操作，随机选择两个父代，选取一个交叉点，将父代的一部分拼接成子代；
6. 变异操作，有一定的概率随机选择两个变异点，交换他们的位置；
7. 合并种群，将精英和子代合并作为下一代种群；
8. 重复步骤2-7，直到达到迭代次数。

最终得到的最优路径如下图所示：