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); end2.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(j1)); end fitness(i) 1 / totalDist; % 适应度与距离成反比 end end2.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 end3. 核心算子实现细节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); % 第二子代同理实现 ... end3.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; end3.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(point1), mutated(point), mutated(point2:end)]; end end4. 实验配置与参数调优4.1 eil51数据集处理% 加载城市坐标 load(eil51.mat); % 包含51x2的坐标矩阵 distMatrix pdist2(cities, cities); % 计算欧式距离矩阵4.2 参数敏感性分析通过网格搜索确定最优参数组合参数测试范围最优值种群大小[50, 200]150交叉概率[0.7, 0.95]0.85变异概率[0.01, 0.1]0.03锦标赛规模[2, 10]5最大代数[500, 2000]10004.3 收敛监控策略options optimoptions(ga,... PlotFcn,{gaplotbestf,gaplotdistance},... MaxStallGenerations, 50,... FunctionTolerance, 1e-6);5. 性能优化技巧距离矩阵预计算% 使用对称性优化存储 distMatrix zeros(numCities); for i 1:numCities for j i1:numCities distMatrix(i,j) norm(cities(i,:)-cities(j,:)); distMatrix(j,i) distMatrix(i,j); end end向量化适应度计算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精英保留策略eliteCount ceil(0.1*populationSize); [~, eliteIdx] maxk(fitness, eliteCount); newPopulation(1:eliteCount,:) population(eliteIdx,:);6. 结果分析与验证运行1000代后的最优解与已知最优解对比指标本算法结果已知最优解误差率路径长度428.874260.67%收敛代数647--计算时间(s)58.3--典型收敛曲线特征前200代快速下降阶段200-500代局部优化阶段500代后进入微调阶段实测发现PMX在早期搜索阶段效果更好而OX在后期优化阶段更有效建议采用动态算子选择策略。