Question

遗传算法解决TSP问题

Answer 1

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

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

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

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

遗传算法基本思路：

流程图：

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

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

运行结果：

python源码： https://github.com/wangjiosw/GA-TSP

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

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