MATLAB遗传算法求解旅行商问题(TSP)实战

1. 项目背景与问题定义

旅行商问题（TSP）是组合优化领域最经典的NP难问题之一，其目标是找到访问所有城市并返回起点的最短路径。当城市规模超过30个时，精确算法已难以在合理时间内求解。遗传算法（GA）作为一种启发式搜索方法，通过模拟自然选择机制，在TSP求解中展现出独特优势。

MATLAB的全局优化工具箱提供了完整的遗传算法实现框架，但实际应用中需要针对TSP特性进行专门设计。本项目基于eil51标准数据集（包含51个城市坐标），实现了包含PMX、OX等交叉算子和多种变异算子的完整遗传算法解决方案。

关键挑战：TSP的解空间随城市数量呈阶乘级增长，eil51问题的解空间规模达51!≈1.55×10⁶⁶，传统算法完全无法处理。

2. 算法设计与实现

2.1 染色体编码方案

采用路径表示法（Permutation Encoding），染色体直接表示城市访问顺序。例如对于5个城市，[3 1 4 2 5]表示访问顺序为3→1→4→2→5→3。

% 初始化种群示例 numCities = 51; populationSize = 100; initialPopulation = zeros(populationSize, numCities); for i = 1:populationSize initialPopulation(i,:) = randperm(numCities); end

2.2 适应度函数设计

适应度值与路径长度成反比，采用标准化处理避免数值溢出：

function fitness = calculateFitness(population, distMatrix) [popSize, numCities] = size(population); fitness = zeros(popSize,1); for i = 1:popSize path = population(i,:); totalDist = distMatrix(path(end), path(1)); % 回到起点 for j = 1:numCities-1 totalDist = totalDist + distMatrix(path(j), path(j+1)); end fitness(i) = 1 / totalDist; % 适应度与距离成反比 end end

2.3 选择算子实现

采用锦标赛选择（Tournament Selection），平衡选择压力与多样性：

function parents = tournamentSelection(population, fitness, tournamentSize) [popSize, numCities] = size(population); parents = zeros(popSize, numCities); for i = 1:popSize candidates = randperm(popSize, tournamentSize); [~, bestIdx] = max(fitness(candidates)); parents(i,:) = population(candidates(bestIdx),:); end end

3. 核心算子实现细节

3.1 PMX交叉算子

部分匹配交叉（PMX）通过映射段保持路径有效性：

function offspring = pmxCrossover(parent1, parent2) numCities = length(parent1); offspring = zeros(2, numCities); % 随机选择交叉段 points = sort(randperm(numCities, 2)); startPoint = points(1); endPoint = points(2); % 第一子代 offspring(1, startPoint:endPoint) = parent1(startPoint:endPoint); for i = startPoint:endPoint if ~ismember(parent2(i), offspring(1, startPoint:endPoint)) current = parent2(i); while true pos = find(parent1 == current); if pos < startPoint || pos > endPoint offspring(1, pos) = parent2(i); break; end current = parent2(pos); end end end offspring(1, isnumber(offspring(1,:))==0) = parent2(isnumber(offspring(1,:))==0); % 第二子代（同理实现） ... end

3.2 OX交叉算子

顺序交叉（OX）保留父代1的片段，按父代2顺序填充剩余：

function offspring = oxCrossover(parent1, parent2) numCities = length(parent1); points = sort(randperm(numCities, 2)); % 创建子代框架 child = zeros(1, numCities); child(points(1):points(2)) = parent1(points(1):points(2)); % 从父代2填充剩余位置 ptr = mod(points(2), numCities) + 1; for gene = [parent2(points(2)+1:end), parent2(1:points(2))] if ~ismember(gene, child) child(ptr) = gene; ptr = mod(ptr, numCities) + 1; end end offspring = child; end

3.3 变异算子组合

实现三种变异策略的动态组合：

function mutated = mutate(individual, mutationRate) if rand > mutationRate return; end mutationType = randi(3); switch mutationType case 1 % 交换变异 points = randperm(length(individual), 2); mutated = individual; mutated(points) = mutated(fliplr(points)); case 2 % 倒位变异 points = sort(randperm(length(individual), 2)); mutated = individual; mutated(points(1):points(2)) = fliplr(mutated(points(1):points(2))); case 3 % 滑动变异 point = randi(length(individual)); mutated = individual; mutated = [mutated(1:point-1), mutated(point+1), mutated(point), mutated(point+2:end)]; end end

4. 实验配置与参数调优

4.1 eil51数据集处理

% 加载城市坐标 load('eil51.mat'); % 包含51x2的坐标矩阵 distMatrix = pdist2(cities, cities); % 计算欧式距离矩阵

4.2 参数敏感性分析

通过网格搜索确定最优参数组合：

4.3 收敛监控策略

options = optimoptions('ga',... 'PlotFcn',{@gaplotbestf,@gaplotdistance},... 'MaxStallGenerations', 50,... 'FunctionTolerance', 1e-6);

5. 性能优化技巧

1. 距离矩阵预计算：

% 使用对称性优化存储 distMatrix = zeros(numCities); for i = 1:numCities for j = i+1:numCities distMatrix(i,j) = norm(cities(i,:)-cities(j,:)); distMatrix(j,i) = distMatrix(i,j); end end

2. 向量化适应度计算：

function fitness = fastFitness(population, distMatrix) shiftedPop = circshift(population, -1, 2); indices = sub2ind(size(distMatrix), population, shiftedPop); totalDist = sum(distMatrix(indices), 2); fitness = 1 ./ totalDist; end

3. 精英保留策略：

eliteCount = ceil(0.1*populationSize); [~, eliteIdx] = maxk(fitness, eliteCount); newPopulation(1:eliteCount,:) = population(eliteIdx,:);

6. 结果分析与验证

运行1000代后的最优解与已知最优解对比：

典型收敛曲线特征：

• 前200代快速下降阶段
• 200-500代局部优化阶段
• 500代后进入微调阶段

实测发现PMX在早期搜索阶段效果更好，而OX在后期优化阶段更有效，建议采用动态算子选择策略。