本文非原创，而是节选自微信公众号AmazingRobot +的文章：《解决最优路径问题的算法》
遗传算法の解决最优路径问题
旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。
— Edited By Hugo
1、遗传算法与生物进化学说：
遗传算法(Genetic Algorithm)遵循『适者生存』、『优胜劣汰』的原则，是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
遗传算法模拟一个人工种群的进化过程，通过选择(Selection)、交叉(Crossover)以及变异(Mutation)等机制，在每次迭代中都保留一组候选个体，重复此过程，种群经过若干代进化后，理想情况下其适应度达到《近似最优》的状态。
自从遗传算法被提出以来，其得到了广泛的应用，特别是在函数优化、生产调度、模式识别、神经网络、自适应控制等领域，遗传算法发挥了很大的作用，提高了一些问题求解的效率。
2、遗传算法是一类模拟自然界遗传进化规律的仿生学算法，它不是一个具体的算法，而是一个算法簇。遗传算法是演化算法的一个分支，由于遗传算法的整体搜索策略和优化计算是不依赖梯度信息，所以它的应用比较广泛。我们本次实验同样用到了遗传算法（用C#编写）来解决TSP问题。
如上图所示：有这么多的点集，通过遗传算法求解可得到优化后的路径。
3、遗传算法基本思路：
计算开始时，随机初始化一定数目的个体，并计算每个个体的适应度值，产生第一代（初始种群）。
如果不满足优化准则，开始新一代的计算：按照适应度值选择个体，产生下一代；父代按一定概率进行交叉操作，产生子代；所有的子代按一定概率变异，形成新的一代。计算新子代的适应度值。这一过程循环执行，直到满足优化准则为止。
4、工程源码请下载：
https://download.csdn.net/download/libaineu2004/12839484
5、C++开源项目
（1）TSP
https://github.com/ShiSanChuan/GeneticAlgorithm 《MATLAB智能算法30个案例分析（2版）》，第4章，基于遗传算法的TSP算法
https://github.com/marcoscastro/tsp_genetic
https://github.com/hsusin123/Genetic-algorithm
https://github.com/wdsrocha/genetic-algorithm-tsp
https://github.com/zawadzki-dawid/GeneticAlgorithmTSP
https://github.com/GiovanniSorice/TSPGeneticAlgorithm
（2）No TSP
https://github.com/olmallet81/GALGO-2.0
https://github.com/Arash-codedev/openGA
https://github.com/lyle-nel/siga
https://github.com/indjev99/Evolving-Snakes
---
参考文献
微信公众号： AmazingRobot +
