遗传算法解决TSP问题(c++实现)

admin1

遗传算法简介
  遗传算法(Genetic Algorithms，简称 GA)是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法，它是模拟自然界中的生命进化机制，在人工系统中实现特定目标的优化。遗传算法的实质是通过群体搜索技术，根据适者生存的原则逐代进化，最终得到最优解或准最优解。它必须做以下操作:初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对，通过随机交叉其染色体的基因并随机变异某些染色体的基因后生成下一代群体，按此方法使群体逐代进化，直到满足进化终止条件。其实现方法如下：

1.根据具体问题确定可行解域，确定一种编码方法，能用数值串或字符串表示 可行解域的每一解。
2.对每一解应有一个度量好坏的依据，它用一函数表示，叫做适应度函数。
3.确定进化参数群体规模M，交叉概率pcpc、变异概率pmpm、进化终止条件。

  表2列出了生物遗传概念在遗传算法中的对应关系：



遗传算法求解TSP问题
  问题：给定平面上20个点的名称与坐标，两个点之间的距离为它们的欧几里得距离。求一条路径，刚好经过每个点1次，使其路径长度最短。

  参数设定如下：

种群大小：M=50
最大代数：G=1000
交叉率：pc=1pc=1,交叉率为1能保证种群的充分进化
变异率：pm=0.1pm=0.1,一般而言，变异发生的可能性较小
  在该问题中，每一条路径就是所谓的染色体（解的编码），每条路径的长度就是该个体的适应性（路径长度越短，适应性越强）。交叉操作就是选择两条路径，取一个分界点k，将两条路径分别以分界点k分成前后两段，并且将两条路径重新组合得到新的两条路径。这里的交叉操作蕴含了变异操作，但是能够让子代继承父代的优良特性。变异操作也是实现群体多样性的一种手段，也是全局寻优的保证，具体实现为，按照给定的变异率，对选定的变异的个体，随机的选取三个整数u

遗传算法c++实现
  写了一整个下午加晚上，终于搞出来了。。仅供参考。下面是c++实现的遗传算法解决TSP问题的代码：