遗传算法解决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问题中个体的编码是一批城市的序列,随机的在这个序列抽取两个城市,然后交换他们的位置。这样就实现了个体编码的变异,算法如下:

  1. 产生两个0到1之间的随机实数;
  2. 将这两个随机实数转化为0到n(城市数)-1之间的随机整数;
  3. 将这两个随机整数指代的城市进行交换;

流程图

代码

主函数代码:

calculateDistance.m

crossover.m

fitness.m

mutate.m

paint.m

Read.m

结果

测试数据:

初始状态:

最终状态:

收敛曲线图:

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

当城市数目较多时

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

总结与观点

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

数据集下载

https://github.com/xyjigsaw/Dataset

140 评论

  1. fitness函数里面distances()里面索引不能是0啊,但pop(i,j)就是用zeros生成的,老报错

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

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

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

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

    出错 zx (line 50)
    subPath = crossover(parent1Path, parent2Path, crossoverProbabilty);%交叉
    这个问题怎么解决啊

  5. fitnessvar(i,1)=(maxPath – sumDistances(i,1)+0.000001) / (maxPath-minPath+0.00000001);
    这里为什么要+0.000001啊😁

      • 感觉这个选择和网上看的轮盘赌选择算法不太一样,这个是分两次随机的从种群中选择四个染色体作候选,然后选这几个中的最好的作为父代,来交叉产生下一个子代,感觉有点像变化后的贪心,轮盘赌的话不是应该根据累计的概率选吗

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

  7. up请问怎么固定一个终点让其余随机点走完最后都往终点走,还有就是你的这个是随机起点跟终点吗

    • 这个代码可以随机起点也可以读取文件。如果要固定终点可以将编码的最后一位写死。

  8. TSP问题不是要求最后结果是闭合路径么,大神你的这个程序能不能针对这个问题稍微调整一下啊

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

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

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

    出错 main (line 5)
    [cityNum,cities] = Read(‘dsj1000.tsp’);
    新手不知道咋弄

  10. 我用了你的代码为啥他把所有城市全画出来了,我是新手小白,想问下你哪个请输入城市数量50怎么来的

  11. 这个代码里面除了种群数量和迭代次数需要自己设置一下以外,别的代码还需要改吗?我的运行结果收敛不到最优值唉

  12. 我用了你的代码为啥他把所有城市全画出来了,我是新手小白,想问下你哪个请输入城市数量50怎么来的

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

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

    请问这是什么问题啊

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

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

    请问一下为什么会出现这两个错误啊

    • 去掉[cityNum,cities] = Read(‘dsj1000.tsp’);, 然后把下面的注释的代码还原,就不使用dsj1000这个文件,直接随机生成城市(个数)

  15. 在这一句有什么作用?轮盘选择参数为4有什么作用?
    for i=1:length(sumDistances)
    fitnessvar(i,1)=(maxPath – sumDistances(i,1)+0.000001) / (maxPath-minPath+0.00000001);
    end
    感谢楼主的答复

      • 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); 这个轮盘选择只是单纯的随机选择,没有按照适应度或者路劲距离来选择呀?

  16. 请问TSP数据集的最优解,是像您这样不回到固定城市,还是回到特定城市的?哪里有说明吗?
    谢谢

  17. 这个两点之间的距离公式用的不是经纬度的计算公式吧,地球是圆的,不能直接根号下x²+y²。怪不得最后最优距离比已有最优解还短0.0,能解决一下吗

    • CEIL_2D不是2D欧几里得距离,这是个啥?距离公式是根号下x²+y²?还有其他几种坐标格式GEO,EUC_2D,ATT都是什么意思?我翻墙去https://docs.google.com/file/d/0B4zUGKjaO9uERU1RZDNuRkg3TW8/edit看看原论文0.0

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

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

    请问这是哪里出错了

  19. 你好,请问一下,我在阅读你的代码的时候发先你在主函数中虽然产生了适应度值的计算,但是后面并没有用到适应度去选择父母路径,fval这个参数没有被使用。

  20. 您好,感谢您的分享。我试着运行了一下代码,发现cityNum在读取数据集时就被设置为了1000,请问应该如何修改成自己想要的城市数量呢?(因为对matlab不太熟悉,可能问的有点傻,请多见谅)

      • 不好意思,我确实不太懂应该怎样修改cityNum…我看见您注释里有写直接赋值为100,但是运行了下貌似不可以这样改,能否指点一下我?

        • 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是最远距离

  21. main.m中 matlab2016
    % 计算上述生成的城市距离
    distance = calculateDistance(cities);
    是不是少了代码

留下评论