遗传算法解决TSP问题MATLAB实现（详细）

文章目录

问题定义：巡回旅行商问题

给定一组n个城市和俩俩之间的直达距离，寻找一条闭合的旅程，使得每个城市刚好经过一次且总的旅行距离最短。

TSP问题也称为货郎担问题，是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年，由美国兰德公司推动，TSP成为近代组合优化领域的典型难题。

TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法，模拟退火方法以及遗传算法方法等。

TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的搜索空间中寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题，是很自然的想法。

基本遗传算法可定义为一个8元组：

（SGA）=（C，E，P0，M，Φ，Г，Ψ，Τ）
C ——个体的编码方法，SGA使用固定长度二进制符号串编码方法；
E ——个体的适应度评价函数；
P0——初始群体；
M ——群体大小，一般取20—100；
Ф——选择算子，SGA使用比例算子；
Г——交叉算子，SGA使用单点交叉算子；
Ψ——变异算子，SGA使用基本位变异算子；
Т——算法终止条件，一般终止进化代数为100—500；
问题的表示
- 对于一个实际的待优化问题，首先需要将其表示为适合于遗传算法操作的形式。用遗传算法解决TSP，一个旅程很自然的表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用。
- 路径表示是表示旅程对应的基因编码的最自然，最简单的表示方法。它在编码，解码，存储过程中相对容易理解和实现。例如：旅程（5-1-7-8-9-4-6-2-3）可以直接表示为（5 1 7 8 9 4 6 2 3）
产生初始种群

一是完全随机产生，它适合于对问题的解无任何先验知识的情况。随机性较强，因而也较公正

二是某些先验知识可转变为必须满足的一组要求，然后在满足这些要求的解中在随机地选取样本。这样选择初始种群可使遗传算法更快的达到最优解。种群有一定的目标性和代表性，但取例不如完全随机的广泛，而且先验知识是否可靠也是一个问题

适应度函数

遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。TSP的目标是路径总长度为最短，路径总长度的倒数就可以为TSP的适应度函数：

选择

一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制，令Σfi表示群体的适应度值之总和，fi表示种群中第i个染色体的适应度值，它产生后代的能力正好为其适应度值所占份额fi／Σfi。

交叉

基于路径表示的编码方法，要求一个个体的染色体编码中不允许有重复的基因码，也就是说要满足任意一个城市必须而且只能访问一次的约束。基本遗传算法的交叉操作生成的个体一般不能满足这一约束条件。

部分匹配交叉操作要求随机选取两个交叉点，以便确定一个匹配段，根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体。

变异

遗传算法解决TSP 问题基于二进值编码的变异操作不能适用，不能够由简单的变量的翻转来实现

在TSP问题中个体的编码是一批城市的序列，随机的在这个序列抽取两个城市，然后交换他们的位置。这样就实现了个体编码的变异，算法如下：

产生两个0到1之间的随机实数；
将这两个随机实数转化为0到n（城市数）-1之间的随机整数；
将这两个随机整数指代的城市进行交换；

流程图

代码

主函数代码：

clear;
clc;
tStart = tic; % 算法计时器

%%%%%%%%%%%%自定义参数%%%%%%%%%%%%%
[cityNum,cities] = Read('dsj1000.tsp');
cities = cities';
%cityNum = 100;
maxGEN = 1000;
popSize = 100; % 遗传算法种群大小
crossoverProbabilty = 0.9; %交叉概率
mutationProbabilty = 0.1; %变异概率
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

gbest = Inf;
% 随机生成城市位置
%cities = rand(2,cityNum) * 100;%100是最远距离

% 计算上述生成的城市距离
distances = calculateDistance(cities);

% 生成种群，每个个体代表一个路径
pop = zeros(popSize, cityNum);
for i=1:popSize
    pop(i,:) = randperm(cityNum); 
end
offspring = zeros(popSize,cityNum);
%保存每代的最小路劲便于画图
minPathes = zeros(maxGEN,1);

% GA算法
for  gen=1:maxGEN

    % 计算适应度的值，即路径总距离
    [fval, sumDistance, minPath, maxPath] = fitness(distances, pop);

    % 轮盘赌选择
    tournamentSize=4; %设置大小
    for k=1:popSize
        % 选择父代进行交叉
        tourPopDistances=zeros( tournamentSize,1);
        for i=1:tournamentSize
            randomRow = randi(popSize);
            tourPopDistances(i,1) = sumDistance(randomRow,1);
        end

        % 选择最好的，即距离最小的
        parent1  = min(tourPopDistances);
        [parent1X,parent1Y] = find(sumDistance==parent1,1, 'first');
        parent1Path = pop(parent1X(1,1),:);


        for i=1:tournamentSize
            randomRow = randi(popSize);
            tourPopDistances(i,1) = sumDistance(randomRow,1);
        end
        parent2  = min(tourPopDistances);
        [parent2X,parent2Y] = find(sumDistance==parent2,1, 'first');
        parent2Path = pop(parent2X(1,1),:);

        subPath = crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉
        subPath = mutate(subPath, mutationProbabilty);%变异

        offspring(k,:) = subPath(1,:);
        
        minPathes(gen,1) = minPath; 
    end
    fprintf('代数:%d   最短路径:%.2fKM \n', gen,minPath);
    % 更新
    pop = offspring;
    % 画出当前状态下的最短路径
    if minPath < gbest
        gbest = minPath;
        paint(cities, pop, gbest, sumDistance,gen);
    end
end
figure 
plot(minPathes, 'MarkerFaceColor', 'red','LineWidth',1);
title('收敛曲线图（每一代的最短路径）');
set(gca,'ytick',500:100:5000); 
ylabel('路径长度');
xlabel('迭代次数');
grid on
tEnd = toc(tStart);
fprintf('时间:%d 分  %f 秒.\n', floor(tEnd/60), rem(tEnd,60));

clear;

clc;

tStart = tic; % 算法计时器

%%%%%%%%%%%%自定义参数%%%%%%%%%%%%%

[cityNum,cities] = Read('dsj1000.tsp');

cities = cities';

%cityNum = 100;

maxGEN = 1000;

popSize = 100; % 遗传算法种群大小

crossoverProbabilty = 0.9; %交叉概率

mutationProbabilty = 0.1; %变异概率

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

gbest = Inf;

% 随机生成城市位置

%cities = rand(2,cityNum) * 100;%100是最远距离

% 计算上述生成的城市距离

distances = calculateDistance(cities);

% 生成种群，每个个体代表一个路径

pop = zeros(popSize, cityNum);

for i=1:popSize

pop(i,:) = randperm(cityNum);

end

offspring = zeros(popSize,cityNum);

%保存每代的最小路劲便于画图

minPathes = zeros(maxGEN,1);

% GA算法

for gen=1:maxGEN

% 计算适应度的值，即路径总距离

[fval, sumDistance, minPath, maxPath] = fitness(distances, pop);

% 轮盘赌选择

tournamentSize=4; %设置大小

for k=1:popSize

% 选择父代进行交叉

tourPopDistances=zeros( tournamentSize,1);

for i=1:tournamentSize

randomRow = randi(popSize);

tourPopDistances(i,1) = sumDistance(randomRow,1);

end

% 选择最好的，即距离最小的

parent1 = min(tourPopDistances);

[parent1X,parent1Y] = find(sumDistance==parent1,1, 'first');

parent1Path = pop(parent1X(1,1),:);

for i=1:tournamentSize

randomRow = randi(popSize);

tourPopDistances(i,1) = sumDistance(randomRow,1);

end

parent2 = min(tourPopDistances);

[parent2X,parent2Y] = find(sumDistance==parent2,1, 'first');

parent2Path = pop(parent2X(1,1),:);

subPath = crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉

subPath = mutate(subPath, mutationProbabilty);%变异

offspring(k,:) = subPath(1,:);

minPathes(gen,1) = minPath;

end

fprintf('代数:%d 最短路径:%.2fKM \n', gen,minPath);

% 更新

pop = offspring;

% 画出当前状态下的最短路径

if minPath < gbest

gbest = minPath;

paint(cities, pop, gbest, sumDistance,gen);

end

figure

plot(minPathes, 'MarkerFaceColor', 'red','LineWidth',1);

title('收敛曲线图（每一代的最短路径）');

set(gca,'ytick',500:100:5000);

ylabel('路径长度');

xlabel('迭代次数');

grid on

tEnd = toc(tStart);

fprintf('时间:%d 分 %f 秒.\n', floor(tEnd/60), rem(tEnd,60));

calculateDistance.m

function [ distances ] = calculateDistance( city )
%计算距离
    [~, col] = size(city);
    distances = zeros(col);
    for i=1:col
        for j=1:col
            distances(i,j)= distances(i,j)+ sqrt( (city(1,i)-city(1,j))^2 + (city(2,i)-city(2,j))^2  );           
        end
    end
end

function [ distances ] = calculateDistance( city )

%计算距离

[~, col] = size(city);

distances = zeros(col);

for i=1:col

for j=1:col

distances(i,j)= distances(i,j)+ sqrt( (city(1,i)-city(1,j))^2 + (city(2,i)-city(2,j))^2 );

end

crossover.m

function [childPath] = crossover(parent1Path, parent2Path, prob)
% 交叉
    random = rand();
    if prob >= random
        [l, length] = size(parent1Path);
        childPath = zeros(l,length);
        setSize = floor(length/2) -1;
        offset = randi(setSize);
        for i=offset:setSize+offset-1
            childPath(1,i) = parent1Path(1,i);
        end
        iterator = i+1;
        j = iterator;
        while any(childPath == 0)
            if j > length
                j = 1;
            end

            if iterator > length
                iterator = 1;
            end
            if ~any(childPath == parent2Path(1,j))
                childPath(1,iterator) = parent2Path(1,j);
               iterator = iterator + 1;
            end
            j = j + 1;
        end
    else
        childPath = parent1Path;
    end
end

function [childPath] = crossover(parent1Path, parent2Path, prob)

% 交叉

random = rand();

if prob >= random

[l, length] = size(parent1Path);

childPath = zeros(l,length);

setSize = floor(length/2) -1;

offset = randi(setSize);

for i=offset:setSize+offset-1

childPath(1,i) = parent1Path(1,i);

end

iterator = i+1;

j = iterator;

while any(childPath == 0)

if j > length

j = 1;

end

if iterator > length

iterator = 1;

end

if ~any(childPath == parent2Path(1,j))

childPath(1,iterator) = parent2Path(1,j);

iterator = iterator + 1;

end

j = j + 1;

end

else

childPath = parent1Path;

end

fitness.m

function [ fitnessvar, sumDistances,minPath, maxPath ] = fitness( distances, pop )
% 计算整个种群的适应度值
    [popSize, col] = size(pop);
    sumDistances = zeros(popSize,1);
    fitnessvar = zeros(popSize,1);
    for i=1:popSize
       for j=1:col-1
          sumDistances(i) = sumDistances(i) + distances(pop(i,j),pop(i,j+1));
       end 
    end
    minPath = min(sumDistances);
    maxPath = max(sumDistances);
    for i=1:length(sumDistances)
        fitnessvar(i,1)=(maxPath - sumDistances(i,1)+0.000001) / (maxPath-minPath+0.00000001);
    end
end

function [ fitnessvar, sumDistances,minPath, maxPath ] = fitness( distances, pop )

% 计算整个种群的适应度值

[popSize, col] = size(pop);

sumDistances = zeros(popSize,1);

fitnessvar = zeros(popSize,1);

for i=1:popSize

for j=1:col-1

sumDistances(i) = sumDistances(i) + distances(pop(i,j),pop(i,j+1));

end

minPath = min(sumDistances);

maxPath = max(sumDistances);

for i=1:length(sumDistances)

fitnessvar(i,1)=(maxPath - sumDistances(i,1)+0.000001) / (maxPath-minPath+0.00000001);

end

mutate.m

function [ mutatedPath ] = mutate( path, prob )
%对指定的路径利用指定的概率进行更新
    random = rand();
    if random <= prob
        [l,length] = size(path);
        index1 = randi(length);
        index2 = randi(length);
        %交换
        temp = path(l,index1);
        path(l,index1) = path(l,index2);
        path(l,index2)=temp;
    end
        mutatedPath = path; 
end

function [ mutatedPath ] = mutate( path, prob )

%对指定的路径利用指定的概率进行更新

random = rand();

if random <= prob

[l,length] = size(path);

index1 = randi(length);

index2 = randi(length);

%交换

temp = path(l,index1);

path(l,index1) = path(l,index2);

path(l,index2)=temp;

end

mutatedPath = path;

end

paint.m

function [ output_args ] = paint( cities, pop, minPath, totalDistances,gen)
    gNumber=gen;
    [~, length] = size(cities);
    xDots = cities(1,:);
    yDots = cities(2,:);
    %figure(1);
    title('GA TSP');
    plot(xDots,yDots, 'p', 'MarkerSize', 14, 'MarkerFaceColor', 'blue');
    xlabel('经度');
    ylabel('纬度');
    axis equal
    hold on
    [minPathX,~] = find(totalDistances==minPath,1, 'first');
    bestPopPath = pop(minPathX, :);
    bestX = zeros(1,length);
    bestY = zeros(1,length);
    for j=1:length
       bestX(1,j) = cities(1,bestPopPath(1,j));
       bestY(1,j) = cities(2,bestPopPath(1,j));
    end
    title('GA TSP');
    plot(bestX(1,:),bestY(1,:), 'red', 'LineWidth', 1.25);
    legend('城市', '路径');
    axis equal
    grid on
    %text(5,0,sprintf('迭代次数: %d 总路径长度: %.2f',gNumber, minPath),'FontSize',10);
    drawnow
    hold off
end

function [ output_args ] = paint( cities, pop, minPath, totalDistances,gen)

gNumber=gen;

[~, length] = size(cities);

xDots = cities(1,:);

yDots = cities(2,:);

%figure(1);

title('GA TSP');

plot(xDots,yDots, 'p', 'MarkerSize', 14, 'MarkerFaceColor', 'blue');

xlabel('经度');

ylabel('纬度');

axis equal

hold on

[minPathX,~] = find(totalDistances==minPath,1, 'first');

bestPopPath = pop(minPathX, :);

bestX = zeros(1,length);

bestY = zeros(1,length);

for j=1:length

bestX(1,j) = cities(1,bestPopPath(1,j));

bestY(1,j) = cities(2,bestPopPath(1,j));

end

title('GA TSP');

plot(bestX(1,:),bestY(1,:), 'red', 'LineWidth', 1.25);

legend('城市', '路径');

axis equal

grid on

%text(5,0,sprintf('迭代次数: %d 总路径长度: %.2f',gNumber, minPath),'FontSize',10);

drawnow

hold off

end

Read.m

function [n_citys,city_position] = Read(filename)
fid = fopen(filename,'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;
            end
            location=[location;A(2:3)'];
        end
    end
    tline = fgetl(fid); 
    if strcmp(tline,'EOF')
        break;
    end
end
[m,n]=size(location);
n_citys = m;
city_position=location;
fclose(fid);
end

function [n_citys,city_position] = Read(filename)

fid = fopen(filename,'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;

end

location=[location;A(2:3)'];

end

tline = fgetl(fid);

if strcmp(tline,'EOF')

break;

end

[m,n]=size(location);

n_citys = m;

city_position=location;

fclose(fid);

end

结果

测试数据：

初始状态：

最终状态：

收敛曲线图：

可以看到，当城市数量适中时，迭代500次最短路径长度有收敛的趋势。

当城市数目较多时

迭代500次，仍然不收敛，可能的问题是陷入了局部最优解。

总结与观点

难点是交叉算法的设计，由于TSP问题和一般的NP问题不一样，每个个体的每个维度具有唯一性，因此在交叉的时候要注意不能有重复的值。本次实验采用的是部分匹配交叉，先从第一个父代选出一个偏移量，从偏移量后的部分点加入到子代，接下来从第二个父代选择第一代没有选择的部分点移到子代中。
当城市数量较多时，大于50个城市，迭代多次，GA仍然不收敛，可能的问题是陷入了局部最优解，因此对GA算法进行改进怡跳出局部最优解，可以采用类似于PSO或者蚁群算法的思想。

数据集下载

https://github.com/xyjigsaw/Dataset

# Matlab

144 评论

yly

2022-06-07 / 16:48 回复

文章很好！帮大忙啦！谢谢
彼岸花开

2022-03-26 / 10:16 回复

这个用的是顺序交叉不是部分匹配交叉兄弟
- xyjisaw
  
  2022-03-26 / 10:20 回复
  
  好的，谢谢提醒
liuguangxv liu

2021-05-17 / 10:07 回复

fitness函数里面distances()里面索引不能是0啊，但pop(i,j)就是用zeros生成的，老报错
- lgx
  
  2021-05-17 / 10:28 回复
  
  我把i写成1了…….
zzzzz

2021-05-06 / 16:50 回复

是Read哦，是楼主自己写的函数，不是matlab自带的read
郭风

2021-03-23 / 16:46 回复

rt没有建立吧
张欣

2021-01-18 / 16:18 回复

能加你个微信吗楼主
GP

2020-12-20 / 15:51 回复

楼主请问你的模型是怎么建的在学习这个问题代码编出来了但是模型不太会建可以分享一下吗
王笑梅

2020-11-19 / 20:22 回复

想问楼主这句报错read(‘dsj1000.tsp’);，我需要装那个文件
- 郭风
  
  2021-03-23 / 16:35 回复
  
  我也没弄明白，请问你弄好了吗？
- 青
  
  2023-05-26 / 15:57 回复
  
  解决了嘛
  - xyjisaw
    
    2023-05-26 / 16:26 回复
    
    这个文件在这里下载即可：https://github.com/xyjigsaw/Dataset/tree/master/TSPLIB
你好

2020-11-18 / 17:19 回复

楼主我想请教一下，想从一个确定的城市开始最后回到这个城市该怎么还，能提供一下思路吗，我是把pop第一列和最后一列卡死，但好像交叉里面还要还？
刘

2020-11-18 / 10:27 回复

怎样固定起点，并最后还回到起点，改过pop之后，老是报错，是咋回事？
你好

2020-11-17 / 17:45 回复

楼主那个城市直接的距离是直线距离吗？
- xyjisaw
  
  2020-11-18 / 14:24 回复
  
  显然是的
刘小龙

2020-11-10 / 19:01 回复

错误使用 randi
第一个输入必须为正标量整数值 IMAX，或者为两个整数值 [IMIN IMAX] (IMIN 小于或等于 IMAX)。

出错 crossover (line 9)
offset = randi(setSize);

出错 zx (line 50)
subPath = crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉
这个问题怎么解决啊
- 刘小龙
  
  2020-11-10 / 19:21 回复
  
  已解决
  - 肖杰
    
    2021-04-21 / 20:31 回复
    
    哥们咋解决的
  - 唐李
    
    2022-05-20 / 13:45 回复
    
    铁你咋解决的啊
haorui

2020-11-10 / 16:17 回复

fitnessvar(i,1)=(maxPath – sumDistances(i,1)+0.000001) / (maxPath-minPath+0.00000001);
这里为什么要+0.000001啊😁
- xyjisaw
  
  2020-11-10 / 16:50 回复
  
  防止除数为0
glo

2020-09-30 / 13:21 回复

交叉概率和变异概率是怎么得来的呀
- xyjisaw
  
  2020-09-30 / 19:41 回复
  
  看论文啊
glo

2020-09-30 / 11:53 回复

run这个要多久呀
- xyjisaw
  
  2020-09-30 / 12:18 回复
  
  这个与种群大小和维度有关，在多项式时间内。
李梓歆

2020-09-01 / 01:41 回复

[cityNum,cities] = Read(‘dsj1000.tsp’);
这句怎么报错呀 2018a不能用吗
- xyjisaw
  
  2020-09-01 / 11:13 回复
  
  需要这个文件
  - 节点部署
    
    2020-09-09 / 17:01 回复
    
    大佬你好，请问一下怎么添加这个文件呀
    - xyjisaw
      
      2020-09-09 / 17:02 回复
      
      下载完了放到工程目录中https://github.com/xyjigsaw/Dataset
  - 周辉
    
    2020-12-30 / 23:56 回复
    
    大佬，麻烦问一下需要哪个文件
任盈盈

2020-08-30 / 10:55 回复

为什么适应度计算的时候不是用总路径长度的倒数，是为了标准化一下吗？
- xyjisaw
  
  2020-08-30 / 11:01 回复
  
  这里是标准化。
  适应度可以自己定义。
  - 任盈盈
    
    2020-08-31 / 10:58 回复
    
    感觉这个选择和网上看的轮盘赌选择算法不太一样，这个是分两次随机的从种群中选择四个染色体作候选，然后选这几个中的最好的作为父代，来交叉产生下一个子代，感觉有点像变化后的贪心，轮盘赌的话不是应该根据累计的概率选吗
    - xyjisaw
      
      2020-08-31 / 11:25 回复
      
      对这里不是标准的
杨小珑

2020-08-21 / 20:39 回复

无法定义具有重复名称 “paint” 的函数。
请问这是什么错误
- xyjisaw
  
  2020-08-21 / 21:39 回复
  
  可能是一个项目下有两个paint函数
Dimples

2020-08-04 / 11:52 回复

请问一下，就是嗯我是刚接触MATLAB的，感觉这个题跟我碰到的是差不多的给出来了30个点的经纬度从第一个点出发每个点都要遍历回到原点求最短路径不太会改
何畅

2020-07-29 / 22:39 回复

请问一下多旅行商问题可以基于此代码进行修改么
- xyjisaw
  
  2020-08-02 / 15:05 回复
  
  可以
王土土

2020-07-21 / 23:10 回复

您好，想请教一下TSP改VRP的方法，要改哪一部分？谢谢
- xyjisaw
  
  2020-07-22 / 08:26 回复
  
  抱歉不太懂VRP
哇哈哈

2020-07-03 / 19:57 回复

up请问怎么固定一个终点让其余随机点走完最后都往终点走，还有就是你的这个是随机起点跟终点吗
- xyjisaw
  
  2020-07-03 / 20:34 回复
  
  这个代码可以随机起点也可以读取文件。如果要固定终点可以将编码的最后一位写死。
RUIN

2020-06-27 / 13:54 回复

TSP问题不是要求最后结果是闭合路径么，大神你的这个程序能不能针对这个问题稍微调整一下啊
- xyjisaw
  
  2020-06-27 / 17:11 回复
  
  这个不是原则问题，在目标函数那里，如果要求总距离最后加上起点到终点的距离即可，或者在编码时增加一位。
  - RUIN
    
    2020-06-27 / 17:29 回复
    
    目标函数那里我理解了，请问paint函数应该怎么改呢？
    - xyjisaw
      
      2020-06-27 / 17:42 回复
      
      抱歉这个我记不大清楚了，你看一下在连线处的代码。
      - RUIN
        
        2020-06-27 / 18:17 回复
        
        谢谢大神了，我最后找到起始点和终点，然后用line函数直接连起来了，简单粗暴
        
        xyjisaw
        
        2020-06-27 / 20:55 回复
        
        强
        
        Ddiao
        
        2020-07-21 / 23:51 回复
        
        请问一下在哪里改的
哇哈哈

2020-06-22 / 18:49 回复

错误使用 fgets
文件标识符无效。使用 fopen 生成有效的文件标识符。

出错 fgetl (line 32)
[tline,lt] = fgets(fid);

出错 Read (line 5)
tline = fgetl(fid);

出错 main (line 5)
[cityNum,cities] = Read(‘dsj1000.tsp’);
新手不知道咋弄
- xyjisaw
  
  2020-06-22 / 20:36 回复
  
  matlab版本越新越好，我的没有问题。
- 1
  
  2022-05-20 / 10:05 回复
  
  你解决了吗，我出现了跟你一样的情况
闫森

2020-06-22 / 11:23 回复

未定义函数或变量 ‘Read，这是什么原因啊
- xyjisaw
  
  2020-06-22 / 12:12 回复
  
  所有代码要单独用文件保存起来，放在一个文件夹中调用。
安丘

2020-06-16 / 17:14 回复

我用了你的代码为啥他把所有城市全画出来了，我是新手小白，想问下你哪个请输入城市数量50怎么来的
- xyjisaw
  
  2020-06-16 / 23:17 回复
  
  把最前面几行的注释去掉即可
vanilla

2020-06-14 / 11:17 回复

这个代码里面除了种群数量和迭代次数需要自己设置一下以外，别的代码还需要改吗？我的运行结果收敛不到最优值唉
- xyjisaw
  
  2020-06-15 / 10:13 回复
  
  GA算法确实不一定能收敛到最优值，可以试试其他演化计算方法
MJ

2020-05-24 / 14:41 回复

我用了你的代码为啥他把所有城市全画出来了，我是新手小白，想问下你哪个请输入城市数量50怎么来的
- MJ
  
  2020-05-24 / 14:45 回复
  
  不用了很感谢你的注释，看到你的注释了，很棒的代码
  - xyjisaw
    
    2020-05-24 / 16:19 回复
    
    😃
    - 肥仔
      
      2020-06-22 / 16:31 回复
      
      你好，我最近在写这方面的论文，可以留个联系方式，请教一下吗
      - xyjisaw
        
        2020-06-22 / 18:14 回复
        
        网站首页关注公众号留言即可。
苏

2020-05-23 / 19:51 回复

错误使用 randi
第一个输入必须为正标量整数值 IMAX，或者为两个整数值 [IMIN IMAX] (IMIN 小于或等于 IMAX)。

出错 crossover (line 11)
offset = randi(setSize);

请问这是什么问题啊
- xyjisaw
  
  2020-05-23 / 22:11 回复
  
  可能是matlab版本问题,另外请检查一下setSize的值
唐拓

2020-05-21 / 22:20 回复

出错 fgetl (line 32)
[tline,lt] = fgets(fid);

出错 Read (line 5)
tline = fgetl(fid);

请问一下为什么会出现这两个错误啊
- xyjisaw
  
  2020-05-21 / 22:29 回复
  
  可能是matlab版本问题，请升级到最新版
  - 唐拓
    
    2020-06-04 / 16:26 回复
    
    我用的是2018a请问你用的是哪个版本？
Honzh

2020-05-05 / 12:39 回复

请问输入城市个数怎么弄，求解，如何修改默认读取1000个城市的数量。
- xyjisaw
  
  2020-05-05 / 14:44 回复
  
  去掉[cityNum,cities] = Read(‘dsj1000.tsp’);，然后把下面的注释的代码还原，就不使用dsj1000这个文件，直接随机生成城市（个数）
龙岩

2020-04-18 / 12:17 回复

运行后显示：未定义函数或变量 ‘filename’，怎么办啊大佬
- xyjisaw
  
  2020-04-18 / 13:42 回复
  
  需要有dsj1000.tsp这个文件。
Runmpleteazer

2020-03-26 / 09:57 回复

请问如何选择从某一城市出发？
- xyjisaw
  
  2020-03-26 / 18:15 回复
  
  编码方式指定某一维度
  - taiheng
    
    2020-03-28 / 15:28 回复
    
    博主，关于这个选择某一城市出发是否有详细的编码，谢谢
    - xyjisaw
      
      2020-03-28 / 15:36 回复
      
      代码中pop的第一位应该是出发城市
      - chenzhihan
        
        2020-04-25 / 14:37 回复
        
        博主能再详细一点么
        pop = zeros(popSize, cityNum);
        for i=1:popSize
        pop(i,:) = randperm(cityNum);
        end
        是生成的这个pop阵中第一行第一列的数改为1么我改了之后一直失败
        
        xyjisaw
        
        2020-04-26 / 08:42 回复
        
        不是这样的，pop矩阵不能动。
cass

2020-03-25 / 21:49 回复

在这一句有什么作用？轮盘选择参数为4有什么作用？
for i=1:length(sumDistances)
fitnessvar(i,1)=(maxPath – sumDistances(i,1)+0.000001) / (maxPath-minPath+0.00000001);
end
感谢楼主的答复
- xyjisaw
  
  2020-03-26 / 18:16 回复
  
  计算适应度值，选择最好的一个路径。
  - cass
    
    2020-03-27 / 20:54 回复
    
    q1;可是计算适应度的公式=（单个个体路径/总路径）的倒数，你这个是最大路径与单个个体的差/最大路径和最小路劲之差呀
    q2:% 轮盘赌选择
    tournamentSize=4; %设置大小
    for k=1:popSize
    % 选择父代进行交叉
    tourPopDistances=zeros( tournamentSize,1);
    for i=1:tournamentSize
    randomRow = randi(popSize);
    tourPopDistances(i,1) = sumDistance(randomRow,1); 这个轮盘选择只是单纯的随机选择，没有按照适应度或者路劲距离来选择呀？
    - xyjisaw
      
      2020-03-27 / 21:33 回复
      
      你说的没错，适应度函数被我改了，轮盘赌的选择方式你可以自己加上。
xly

2020-03-25 / 11:40 回复

请问TSP数据集的最优解，是像您这样不回到固定城市，还是回到特定城市的？哪里有说明吗？
谢谢
- xyjisaw
  
  2020-03-25 / 11:50 回复
  
  都行，看你怎么编码了，如果要回到最后的城市编码修改下就好。
  - xly
    
    2020-03-25 / 12:30 回复
    
    那数据集里给的最优解是不是回到起点的城市的？
里昂同学

2020-02-06 / 11:15 回复

非常感谢！！！
今日新闻

2020-02-03 / 01:43 回复

文章不错支持一下，非常喜欢
一个逗比

2019-12-27 / 19:45 回复

这个两点之间的距离公式用的不是经纬度的计算公式吧，地球是圆的，不能直接根号下x²+y²。怪不得最后最优距离比已有最优解还短0.0，能解决一下吗
- 一个逗比
  
  2019-12-27 / 19:56 回复
  
  我错了，这个是2D欧几里得距离，公式没错，打扰了..
- 一个逗比
  
  2019-12-27 / 20:17 回复
  
  CEIL_2D不是2D欧几里得距离，这是个啥？距离公式是根号下x²+y²？还有其他几种坐标格式GEO，EUC_2D，ATT都是什么意思？我翻墙去https://docs.google.com/file/d/0B4zUGKjaO9uERU1RZDNuRkg3TW8/edit看看原论文0.0
匿名

2019-12-12 / 16:23 回复

请问算法怎么改成求带权一张有向图的最短路径？
- 匿名
  
  2019-12-12 / 16:24 回复
  
  打错了，请问算法怎么改成求一张带权有向图的最短路径？
  - xyjisaw
    
    2019-12-12 / 17:09 回复
    
    可以考虑不使用遗传算法，试试迪杰斯特拉
匿名

2019-11-27 / 12:31 回复

出错 crossover (line 9)
offset = randi(setSize);

出错 main (line 62)
subPath = crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉

请问这是哪里出错了
- 匿名
  
  2019-11-27 / 13:37 回复
  
  已经解决了，不好意思打扰了
  - 弟弟
    
    2019-12-02 / 20:50 回复
    
    怎么弄？不太会改。。
    - xyjisaw
      
      2019-12-04 / 17:13 回复
      
      Ctrl C, Ctrl V
      - 匿名
        
        2019-12-11 / 15:15 回复
        
        我想问一下这个问题是怎么改的，我调不出来
        
        xyjisaw
        
        2019-12-11 / 15:19 回复
        
        检查一下MATLAB版本有没有更新到最新版，我这里可以跑
        
        匿名
        
        2019-12-11 / 16:31 回复
        
        17版的，因为没有你的那个文件，所以我把文件换成了我的excel表格文档
        
        匿名
        
        2019-12-12 / 21:50 回复
        
        2019a也运行不了，请问大佬解决
      - 匿名
        
        2019-12-11 / 19:54 回复
        
        A = [1 2];
        您好我想问一下，这个是中间少了什么吗，有没有少逗号
        
        xyjisaw
        
        2019-12-11 / 20:44 回复
        
        都可以
  - 阿飞
    
    2020-05-04 / 12:28 回复
    
    老哥，怎么解决的啊，急！！
- Symcal
  
  2020-03-08 / 19:24 回复
  
  我遇到了同样的问题，2019b版本的，请问您是怎么解决的呢
  - Symcal
    
    2020-03-08 / 20:12 回复
    
    明白了，是数据集没处理好，代码和版本没问题
    - yuanyi
      
      2020-04-26 / 17:48 回复
      
      你好我也是同样问题，要怎么调整呢
匿名

2019-11-27 / 01:13 回复

dsj1000.tsp没了是吗？
- xyjisaw
  
  2019-11-28 / 18:59 回复
  
  tsplib上面找
  - xyjisaw
    
    2020-03-09 / 09:16 回复
    
    数据集位置：https://github.com/xyjigsaw/Dataset
匿名

2019-11-26 / 18:48 回复

提示：错误使用 Read
输出参数太多。
匿名

2019-11-23 / 17:03 回复

请问输入城市个数怎么弄，求解
匿名

2019-09-24 / 11:01 回复

请问那个数据集怎样放进去呢？刚学，不太会
- xyjisaw
  
  2019-09-24 / 15:26 回复
  
  你好，请参考 http://www.omegaxyz.com/2019/06/26/divide-dataset/
匿名

2019-06-04 / 16:40 回复

你好，请问一下，我在阅读你的代码的时候发先你在主函数中虽然产生了适应度值的计算，但是后面并没有用到适应度去选择父母路径，fval这个参数没有被使用。
- xyjisaw
  
  2019-06-04 / 22:26 回复
  
  嗯嗯，是这样的，你可以在我的框架上优化一下，我是直接通过距离选的
林松

2019-05-20 / 12:21 回复

请问下怎样改程序使输出的城市首尾坐标连接起来？
- xyjisaw
  
  2019-05-20 / 12:37 回复
  
  paint.m里面
  plot(bestX(1,:),bestY(1,:), 'red', 'LineWidth', 1.25);
  
  在best里面把起点坐标加到最后（再写一遍）
  - 林松
    
    2019-05-20 / 17:13 回复
    
    还是不太明白怎么改，，，
    - 鸡蛋面不吃鸡蛋
      
      2019-09-17 / 12:39 回复
      
      MbestX=[bestX(1,:) bestX(1,1)];
      MbestY=[bestY(1,:) bestY(1,1)];
      plot(MbestX(1,:),MbestY(1,:), ‘red’, ‘LineWidth’, 1.25);
yyyyes

2019-05-16 / 23:35 回复

您好，感谢您的分享。我试着运行了一下代码，发现cityNum在读取数据集时就被设置为了1000，请问应该如何修改成自己想要的城市数量呢？（因为对matlab不太熟悉，可能问的有点傻，请多见谅）
- xyjisaw
  
  2019-05-17 / 12:36 回复
  
  把cityNum改了就好啊
  - yyyyes
    
    2019-05-17 / 12:52 回复
    
    不好意思，我确实不太懂应该怎样修改cityNum…我看见您注释里有写直接赋值为100，但是运行了下貌似不可以这样改，能否指点一下我？
    - xyjisaw
      
      2019-05-17 / 13:32 回复
      
      18行上面的覆盖掉
      clear; clc; tStart = tic; % 算法计时器
      %%%%%%%%%%%%自定义参数%%%%%%%%%%%%% cityNum = 100; maxGEN = 1000; popSize = 100; % 遗传算法种群大小 crossoverProbabilty = 0.9; %交叉概率 mutationProbabilty = 0.1; %变异概率 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      gbest = Inf; 随机生成城市位置 cities = rand(2,cityNum) * 100;%100是最远距离
      - yyyyes
        
        2019-05-17 / 13:47 回复
        
        明白了，谢谢您！
匿名

2019-04-28 / 20:09 回复

crossover.m
function [childPath] = crossover(parent1Path, parent2Path, prob)c
最后多了一个c
- xyjisaw
  
  2019-04-28 / 21:13 回复
  
  ok谢谢啦，已改正
  - 匿名
    
    2019-04-28 / 22:38 回复
    
    但是没有在命令窗口没出现填写迭代次数填写
    哈哈，你很优秀啦，不介意我说这么多吧
匿名

2019-04-27 / 22:19 回复

main.m中 matlab2016
% 计算上述生成的城市距离
distance = calculateDistance(cities);
是不是少了代码
- xyjisaw
  
  2019-04-28 / 08:28 回复
  
  少了啥，请指教
  - 匿名
    
    2019-04-28 / 13:47 回复
    
    运行的时候，2016版本的，时常报错，具体原因还在找，可能原因之一是版本
匿名

2019-04-21 / 13:52 回复

(‘dsj1000.tsp’) 在哪下载
- xyjisaw
  
  2019-04-21 / 19:50 回复
  
  你找找我的关于TSP的文章，里面有个网址可以下载。
  - 匿名
    
    2019-05-09 / 21:20 回复
    
    博主能发一下dsj1000.tsp嘛，没有找到
    - xyjisaw
      
      2019-05-10 / 08:35 回复
      
      http://www.omegaxyz.com/2018/12/03/tsplib-matlab/?hilite=%27TSP%27
      
      这个文章末尾有数据集下载方式
      - xyjisaw
        
        2020-03-09 / 09:17 回复
        
        数据集已经上传到 https://github.com/xyjigsaw/Dataset
- 匿名
  
  2019-05-09 / 21:21 回复
  
  请问你找到了吗？
  - xyjisaw
    
    2019-05-10 / 08:34 回复
    
    http://www.omegaxyz.com/2018/12/03/tsplib-matlab/?hilite=%27TSP%27
    
    这个文章末尾有数据集下载方式
    - xyjisaw
      
      2020-03-09 / 09:17 回复
      
      数据集已经上传到 https://github.com/xyjigsaw/Dataset

遗传算法解决TSP问题MATLAB实现（详细）

文章目录

问题定义：巡回旅行商问题

流程图

代码

结果

总结与观点

数据集下载

大模型中的RepE表征工程

大模型也是一种优化器（LLM as Optimizer）

全栈开发与快速部署Demo

学术idea自动发现与生成

自回归语言模型（language model）Python实现

粉丝期待的三体电影宇宙（近四十部电影与电视剧集）

基于历史对比学习的时序知识图谱推理

泰拉瑞亚Terriaria快速部署Linux服务器

iPad生产力指南——编程

DeepScience：学术趋势预测与分析

144 评论

留下评论取消回复

文章目录

问题定义：巡回旅行商问题

流程图

代码

结果

总结与观点

数据集下载

相关文章

144 评论