遗传算法求解TSP问题的MATLAB代码

以下是基于遗传算法的TSP问题的MATLAB代码：

% TSP问题遗传算法求解
clc
clear
close all

% 参数设置
numOfCities = 10;  % 城市数量
numOfIndividuals = 50;  % 种群规模
numOfGenerations = 500;  % 迭代次数
mutationProb = 0.01;  % 变异概率
crossoverProb = 0.8;  % 交叉概率

% 生成城市坐标
x = randi([0, 100], 1, numOfCities); % 生成0-100的随机整数
y = randi([0, 100], 1, numOfCities);
cities = [x; y]';

% 计算距离矩阵
distanceMatrix = pdist2(cities, cities);

% 初始化种群
population = zeros(numOfIndividuals, numOfCities);
for i = 1:numOfIndividuals
    population(i,:) = randperm(numOfCities);
end

% 迭代
for i = 1:numOfGenerations
    % 计算适应度
    fitness = zeros(1, numOfIndividuals);
    for j = 1:numOfIndividuals
        fitness(j) = calculateFitness(population(j,:), distanceMatrix);
    end
    
    % 选择
    [parents, ~] = selection(population, fitness);
    
    % 交叉
    offspring = crossover(parents, crossoverProb);
    
    % 变异
    offspring = mutation(offspring, mutationProb);
    
    % 合并父代和子代
    population = [parents; offspring];
    
    % 精英选择
    [~, idx] = sort(fitness, 'descend');
    population(1,:) = parents(idx(1),:);
end

% 最优路径
[~, idx] = max(fitness);
bestPath = population(idx,:);
bestDistance = calculateDistance(bestPath, distanceMatrix);

% 画图
figure;
plot(cities(:,1), cities(:,2), 'bo');
hold on;
plot([cities(bestPath,1); cities(bestPath(1),1)], [cities(bestPath,2); cities(bestPath(1),2)], 'r');
title(sprintf('TSP Problem with Genetic Algorithm (Distance = %.2f)', bestDistance));

% 计算适应度
function fitness = calculateFitness(individual, distanceMatrix)
    fitness = 1 / calculateDistance(individual, distanceMatrix);
end

% 计算路径距离
function distance = calculateDistance(path, distanceMatrix)
    distance = 0;
    for i = 1:length(path)-1
        distance = distance + distanceMatrix(path(i), path(i+1));
    end
    distance = distance + distanceMatrix(path(end), path(1));
end

% 轮盘赌选择
function [parents, indices] = selection(population, fitness)
    indices = zeros(1, 2);
    parents = zeros(2, length(population(1,:)));
    for i = 1:2
        temp = randperm(length(fitness));
        tempFitness = fitness(temp);
        cumFitness = cumsum(tempFitness / sum(tempFitness));
        r = rand();
        for j = 1:length(cumFitness)
            if r <= cumFitness(j)
                indices(i) = temp(j);
                parents(i,:) = population(indices(i),:);
                break;
            end
        end
    end
end

% 交叉
function offspring = crossover(parents, crossoverProb)
    offspring = zeros(size(parents));
    for i = 1:length(parents(:,1))
        if rand() < crossoverProb
            % 随机选择交叉位置
            cutPos = sort(randperm(length(parents(i,:)), 2));
            offspring(i, cutPos(1):cutPos(2)) = parents(i, cutPos(1):cutPos(2));
        else
            offspring(i,:) = parents(i,:);
        end
    end
end

% 变异
function offspring = mutation(population, mutationProb)
    offspring = zeros(size(population));
    for i = 1:length(population(:,1))
        if rand() < mutationProb
            % 随机选择变异位置
            swapPos = randperm(length(population(i,:)), 2);
            offspring(i,:) = swap(population(i,:), swapPos(1), swapPos(2));
        else
            offspring(i,:) = population(i,:);
        end
    end
end

% 交换位置
function newIndividual = swap(individual, pos1, pos2)
    newIndividual = individual;
    temp = newIndividual(pos1);
    newIndividual(pos1) = newIndividual(pos2);
    newIndividual(pos2) = temp;
end

运行该代码，将生成10个随机坐标的城市，使用遗传算法求解TSP问题，并绘制最优路径。