一、获取代码方式
获取代码方式1：
通过订阅紫极神光博客付费专栏，凭支付凭证，私信博主，可获得此代码。
获取代码方式2：
完整代码已上传我的资源：【TSP】基于matlab遗传算法求解中国35省会城市旅行商问题【含Matlab源码 1222期】
备注：
订阅紫极神光博客付费专栏，可免费获得1份代码（有效期为订阅日起，三天内有效）；
二、TSP简介
旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
TSP的数学模型
三、遗传算法简介
1 引言
2 遗传算法理论
2.1 遗传算法的生物学基础
2.2 遗传算法的理论基础
2.3 遗传算法的基本概念
2.4 标准的遗传算法
2.5 遗传算法的特点
2.6 遗传算法的改进方向
3 遗传算法流程
4 关键参数说明
四、部分源代码
clear;clc;tStart = tic; % 算法计时器%************************初始化参数变量*******************************[Num,Txt,Raw]=xlsread('provincial_ capital_coordinate12.xlsx'); %经纬度数据% cities = Num(:,5:6);cities=cities';[~,cityNum]=size(cities);maxGEN = 500;popSize = 300; % 遗传算法种群大小crossoverProbabilty = 0.95; %交叉概率mutationProbabilty = 0.33; %变异概率%********初始化种群***********% 计算上述生成的各个城市之间的距离断distances = calculateDistance(cities);% 生成种群，每个个体代表一个路径gbest = Inf;%行：Inf 无穷大parentPop = zeros(popSize, cityNum);% 随机打乱种群for i=1:popSizeparentPop(i,2:cityNum-1) = randperm(cityNum-2); %randperm功能是随机打乱一个数字序列，将1-cityNum数字序列随机打乱for a=2:cityNum-1parentPop(i,a)=parentPop(i,a)+1;endparentPop(i,1)=1;parentPop(i,cityNum)=cityNum;end% 定义子代种群childPop = zeros(popSize,cityNum);%定义每代的最小路径minPathes = zeros(maxGEN,1);%****************************%**********************************************************************%*********************GA算法选择交叉变异执行过程************************for genNum=1:maxGEN% 计算适应度的值，即路径总距离[fitnessValue, sumDistance, minPath, maxPath] = fitness(distances, parentPop);tournamentSize=4; %设置大小for k=1:popSize%% 以下为联赛选择法% 随机选择父代tourPopDistances=zeros( tournamentSize,1);for i=1:tournamentSizerandomRow = randi(popSize);%行：返回一个介于1到popSize的伪随机整数tourPopDistances(i,1) = sumDistance(randomRow,1);end% 选择最好的，即距离最小的parent1 = min(tourPopDistances);[parent1X,parent1Y] = find(sumDistance==parent1,1, 'first');%选出随机的4个中最短距离种群序号parent1Path = parentPop(parent1X(1,1),:);%%选出随机的4个中最短距离种群路径for i=1:tournamentSizerandomRow = randi(popSize);tourPopDistances(i,1) = sumDistance(randomRow,1);endparent2 = min(tourPopDistances);[parent2X,parent2Y] = find(sumDistance==parent2,1, 'first');parent2Path = parentPop(parent2X(1,1),:);%% 以上为联赛选择法function [childPath] = crossover(parent1Path, parent2Path, prob)% 交叉random = rand();if prob >= random %行：随机生成一个01之前的数，和概率值比较，相当于一个轮盘赌的选择，来执行概率选择执行操作[l, length] = size(parent1Path);childPath = zeros(l,length);setSize = floor(length/2) -1;%行：floor 朝负无穷大方向取整offset = randi(setSize);%行：随机 产生1-setSize之间的整数parent1OXstart=offset; %行：0X交叉，父代1遗传给子代的片段起点parent1OXend=setSize+offset-1; %行：0X交叉，父代1遗传给子代的片段终点for i=parent1OXstart:parent1OXendchildPath(1,i) = parent1Path(1,i);endchildPath(1,1) = parent1Path(1,1);%行：将路径的起点和终点直接赋给子代，因为起点和终点不变childPath(1,length) = parent1Path(1,length);%行：parent2依顺序放入子代位坐标parent2Point=2;for x=2:length-1if childPath(1,x)==0for y=parent2Point:length-1if ~any(childPath == parent2Path(1,y))%行：如果子代路径相应元素不等于父代元素childPath(1,x)=parent2Path(1,y);parent2Point=y+1;break;endendendendelsechildPath = parent1Path;endendfunction [ bestPopPath ] = paint( cities, pop, minPath, totalDistances,gen)gNumber=gen;[~, length] = size(cities);xDots = cities(1,:);yDots = cities(2,:);%figure(1);%行：先画城市的固定坐标plot(xDots,yDots, 'p', 'MarkerSize', 10, 'MarkerFaceColor', 'green');xlabel('经度');ylabel('纬度');axis equal[num,txt,raw]=xlsread('provincial_ capital_coordinate12.xlsx'); %经纬度数据% text(xDots(1)+0.2,yDots(1)+0.2,txt(1+1,2),'FontSize',9.5,'Color','red','FontWeight','Bold') ; %先画起点，突出起点for i=2:length-1text(xDots(i)+0.2,yDots(i)+0.2,txt(i+1,2),'FontSize',8,'Color','blue','FontWeight','Bold') ; %加上0.01使标号和点不重合，可以自己调整endfunction [n_citys,city_position] = Read(filename)fid = fopen(filename,'rt');%行：“rt”以文本方式读出location=[];A = [1 2];tline = fgetl(fid);%行：从文件中读取一行数据，并去掉行末的换行符。 while ischar(tline)if(strcmp(tline,'NODE_COORD_SECTION'))while ~isempty(A)A=fscanf(fid,'%f',[3,1]);if isempty(A)break;endlocation=[location;A(2:3)'];endendtline = fgetl(fid); if strcmp(tline,'EOF')break;end
五、运行结果
六、matlab版本及参考文献
1 matlab版本
a
2 参考文献
[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）[M].电子工业出版社，.
[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社，.
