遗传算法解决旅行商问题（TSP）

遗传算法与生物进化学说

1885年年，达尔文用自然选择来解释物种的起源和生物的进化，达尔文的自然选择学说包括三个方面：

遗传
变异
生存斗争和适者生存

上世纪20年代，一些学者用统计生物学和种群遗传学重新解释达尔文自然选择理论，形成现代综合进化论，种群遗传学认为：

在一定地域中一个物种的全体成员构成一个种群
生物的进化是种群的进化，每一代个体基因型的改变会影响种群基因库的组成，而种群基因库组成的变化就是这一种群的进化

遗传算法中与生物学相关的概念和术语与优化问题中的描述的关系：

个体：解
种群：解集/解空间
适应度：评价/目标/寻优函数
选择、交叉、变异：产生新解的方法

遗传算法的计算机实现

上世纪60年代中期，Holland提出位串编码技术。
这种技术适用于变异和交叉操作，而且强调将交叉作为主要的遗传操作。
Holland将该算法用于自然和人工系统的自适应行为研究中，在1975出版了开创性著作“Adaptation in Natural and Artifical System”。
之后，他将算法应用到优化以及学习中，并将其命名为遗传算法（简称GA）。

遗传算法基本思路：

计算开始时，随机初始化一定数目的个体，并计算每个个体的适应度值，产生第一代（初始种群）。
如果不满足优化准则，开始新一代的计算：
1. 按照适应度值选择个体，产生下一代；
2. 父代按一定概率进行交叉操作，产生子代；
3. 所有的子代按一定概率变异，形成新的一代；
4. 计算新子代的适应度值。
这一过程循环执行，直到满足优化准则为止。

流程图：

遗传算法解决TSP问题

背景

旅行商

旅行商问题，即 TSP 问题（Traveling Salesman Problem）是数学领域中著名问题之一。假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP 问题是一个组合优化问题。该问题可以被证明具有 NPC 计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

遗传算法

遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。

思路

编码

最常用策略：路径编码
直接采用城市在路径中的位置来构造用于优化的状态。
例：九城市TSP问题，路径：5-4-1-7-9-8-6-2-3
路径编码：(5 4 1 7 9 8 6 2 3)

交叉

变异

遗传算法解决TSP问题编程实现

MATLAB实现

修改Read(‘***.tsp’)读取你想要的数据集，如上图读取的是100个城市的数据集。

dsj100.tsp

NAME : dsj100
COMMENT : Clustered random problem (Johnson)
TYPE : TSP
DIMENSION : 100
EDGE_WEIGHT_TYPE : CEIL_2D
NODE_COORD_SECTION
 1 981036 508139
 2 534120 -42453
 3 577878 -43732
 4 532890 -96645
 5 205322 215891
 6 225923 197950
 7 69842 667632
 8 391965 1054524
 9 310065 -10714
 10 247401 754523
 11 217951 218350
 12 443097 54051
 13 47342 630935
 14 317515 713679
 15 301816 1021772
 16 950864 332234
 17 276433 725657
 18 921801 410349
 19 555508 67090
 20 409959 379409
 21 968097 540588
 22 40089 721860
 23 702011 527050
 24 726191 326684
 25 990428 196959
 26 381890 1003805
 27 409527 1056227
 28 675609 496310
 29 971071 188552
 30 932494 818793
 31 936083 384774
 32 835076 517826
 33 120444 663239
 34 648516 395774
 35 402323 126508
 36 307839 57178
 37 397333 987582
 38 314281 949219
 39 105042 667806
 40 1006036 468020
 41 473356 311656
 42 970499 257334
 43 919732 458332
 44 1033956 436231
 45 934265 314744
 46 239142 55856
 47 720304 525053
 48 480764 1058084
 49 970063 396578
 50 543132 334794
 51 755587 491352
 52 975653 745618
 53 272842 58331
 54 537123 165900
 55 519742 129315
 56 35924 947451
 57 1064442 490895
 58 489393 117496
 59 631320 277543
 60 261674 961159
 61 534617 58056
 62 691689 512673
 63 182654 715277
 64 945838 459916
 65 627821 -838
 66 1022110 283893
 67 458725 143747
 68 273755 -10984
 69 293760 805861
 70 466598 160110
 71 906179 264649
 72 712619 535794
 73 240847 212619
 74 993782 930601
 75 322034 925655
 76 954600 443790
 77 995817 521789
 78 267943 -26353
 79 674673 332544
 80 978160 748015
 81 353466 1077036
 82 371788 950118
 83 779223 446051
 84 525136 311620
 85 1026402 609181
 86 619524 -3330
 87 644232 440581
 88 198821 272321
 89 280990 298348
 90 475893 278934
 91 291897 964145
 92 476091 102274
 93 34538 935151
 94 985493 331624
 95 25533 991767
 96 1029016 248202
 97 1041034 983317
 98 922880 836157
 99 754748 378532
 100 193676 209011
EOF

输入TSP(pop,cp,mp,mg)上图注释说明了各参数的代表意义，注意概率<=1。

TSP(50,0.8,0.2,100)

TSP(80,0.8,0.2,100)

TSP(50,0.5,0.2,100)

TSP(50,0.8,0.5,100)

TSP(50,0.8,0.2,200)

Python实现

输入：

10城市坐标为：
(41, 94)；(37, 84)；(54, 67)；(25, 62)；(7, 64)； (2, 99)；(68, 58)；(71, 44)；(54, 62)； (83, 69)

运行结果：

遗传算法的特点

GA是一种通用的优化算法，它的优点有：

编码技术和遗传操作比较简单；
优化不受限制性条件的约束；
隐含并行性和全局解空间搜索;

随着计算机技术的发展，GA愈来愈得到人们的重视，并在机器学习、模式识别、图像处理、神经网络、优化控制、组合优化、VLSI设计、遗传学等领域得到了成功应用。

源代码

Gitee代码仓库：

GitHub

abyss-yjy/GA-TSP