基于遗传算法的TSP问题求解(C)
TSP问题：
TSP(Travelling salesman problem): 译作“旅行商问题”， 一个商人由于业务的需要，要到n个城市，每个城市之间都有一条路径和其他所有的城市相连。现在要求从一个城市出发，穿越所有其他所有的城市，再回到出发的城市。 出于成本的考虑，要求商人走的路径的长短最短。问能否找到这样的一条路径？
这是个经典的NP-complete问题。 时间复杂度为θ(n!)。 随着城市的数量规模增大，在有限的时间内得不到问题的最优解。 我们只能退而求其次，在有限的时间内(或可接受的时间内)找到一个近似最优解，而且这个近似最优解和最优解的误差我们也是可以接受的。 出于这样的考虑，为求解这类问题的启发式，元启发式算法，演化算法营运而生。
随着研究的深入，TSP问题已经演化成好多版本。本文的C程序对于对称和非对称的版本都适用。
遗传算法：
遗传算法(Genetic Algorithm)，也称进化算法，是依据生物进化的过程而提出的一种启发式算法，由美国的J.Holland于1975年首次提出。其主要特点是依据生物进化中的“优胜劣汰”或者“竞争”法作为问题的解的选择依据。 直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术之一
遗传算法的基本原理：
首先根据问题产生多个初始可行解()，然后从初始解中选择诺干优异的个体(问题的解)进行各种操作(交叉，变异)用以产生新的后代。再从新的后代中选择优异的个体进行相应的操作产生它们的后代，如此不断循环，直到迭代的次数达到了预先设定的值或者多次迭代以后产生的最优异的个体(最优解)的质量并没有明显的提高，就可以停止迭代，这时的最优个体(最优解)最为问题的解。
从上面的原理我们可以知晓该算法主要涉及的步骤如图 1所示：
编码
在解实现初始化之前，如何表示一个解即编码是一个很重要的问题。 一般的编码方式有:
基于二进制编码: 作为遗传算法传统的编码方式。对于TSP问题，经过交叉后可能得不到可行解，需要修补操作。
基于矩阵的编码: 需要更多的额外空间，而且随着种群规模的增加，存储空间剧增和前期处理工作任务很庞大。后续操作也比较复杂。
基于邻近的编码: 采用链表的方式存储,但是变异,交叉操作复杂
基于格雷码方法：传统二进制编码的一种改进，容易实现交叉，变异操作，但是对于该问题不是最优的
基于符号编码：对于TSP问题，我们直接使用路径来表示一个染色体。即使用一个整数数组，数组长度为TSP城市的数量，数组中存储各个城市编号，从下标为0开始逐个遍历数组元素形成的一个序列即为路径(对于要回到原点的要求，为了方便表示，在这里不作考虑，只是在计算路径长度的时候会添加相应的长度)。
形成初始解
采用随机的方式产生诺干个(种群规模)的序列，即产生符合城市编号的随机数存储在数组中，数组中的元素包含所有的城市编号，而且没有重复的编码。数组的个数为种群规模。
选择
在形成一定数量的可行解（染色体）后，需要对这些父代的染色体进行筛选。根据生物遗传的基因的优胜劣汰原则，在筛选染色体的我们也会秉承精英保留原则，使得优异的基因有更多的机会得到遗传。
适应度函数： 这里我们选择路径长度的倒数来作为解的适应度
在这个问题中，我们选择“轮盘赌”算法来筛选染色体。
基本原理：计算每个染色体(路径)的长度的倒数，再得到所有路径倒数之和，用每条路径的倒数除以所有所有路径倒数之和即为这条路径被选中的概率(路径越短，概率越高)。
交叉
这里我们选择交替位置交叉法（Alternating Position Crossover，APX）来对一对染色体进行交叉操作，其基本原理如下图所示