【原创】用遗传算法解决旅行商问题(附源代码)

来源：互联网   发布日期：2011-08-30 20:15:15   浏览：16794次  

　　最近心血来潮，重新拾起大学毕业设计时研究过的遗传算法。去年做毕业设计时还觉得遗传算法是一种多么神秘的算法，但是今天看来，遗传算法也就和冒泡排序算法差不多，都是通用的算法，只不过遗传算法实现起来稍微复杂一点而已。
　　我曾经被遗传算法的名字所疑惑，还以为遗传算法会改变程序的形态，使得程序就好像生物一样进化，过了几天去看程序已经变得连编写程序的人都认不出来了，汗！大二时的幼稚想法。
　　遗传算法其实是一种求函数极值的随机搜索算法，但它又不是毫无规则地随机搜索，而是基于一种假设：假设函数值的分布是有一定的连续性的，换句话说函数的极值出现在一个较优值附近的概率要大于出现在一个较差值附近的概率。基于这个假设，遗传算法总是以较大概率保留较优值所代表的搜索方向，而以较低概率保留较差值所代表的搜索方向。这并不是说不去搜索较差值的附近区域，只是搜索的概率较低而已。这个思想与模拟退火算法相似，对于能量较高的系统状态，程序仍然以一定的概率接受，只不过这个概率小于1。
　　遗传算法的局部搜索能力较强，但是很容易陷入局部极值，毕业设计的时候曾经认为只要增加变异概率就可以跳出局部极值，还美其名曰自适应，现在想想这种想法是错误的：虽然增加变异概率可以搜索到远离当前极值的点，但是新点的值往往不能和当前保留下来的较优值相提并论，因为这些较优值都是经过千百代的进化而存留下来的，于是远离当前极值的点往往在两到三代以内就被淘汰掉了。增加变异概率实际上是把遗传算法退化成了一种纯粹的随机搜索，所谓的自适应也无从谈起！
　　那么如何解决遗传算法容易陷入局部极值的问题呢？让我们来看看大自然提供的方案。六千五百万年以前，恐龙和灵长类动物并存，恐龙在地球上占绝对统治地位，如果恐龙没有灭绝灵长类动物是绝没有可能统治地球的。正是恐龙的灭绝才使灵长类动物有了充分进化的余地，事实上地球至少经历了5次物种大灭绝，每次物种灭绝都给更加高级的生物提供了充分进化的余地。所以要跳出局部极值就必须杀死当前所有的优秀个体，从而让远离当前极值的点有充分的进化余地。这就是灾变的思想。
　　下一个问题是什么时候进行灾变，换句话说什么时候局部搜索已经充分了呢？我用了一个灾变倒计数的概念：从500开始递减，每一代递减一次，如果出现了新的最优值，就从新开始计数，如果出现新最优值的时候倒计数递减次数的2.5倍已经超过500则从新的初始值开始倒数。例：初始倒数500，如果倒数到200时出现新最优值，则从(500 - 200) * 2.5 = 750开始从新倒数，下一次如果倒数到100时出现新最优值，则从(750 - 100) * 2.5 = 1625开始倒计数(这里的2.5是一个经验值，可以在全局参数设置里面调整)。也就是说倒计数的长度取决于进化的速度，进化速度越慢倒计数长度越长。如果倒计数完毕还没有新的最优值，就认为局部搜索已经充分，就发生灾变。
　　基于上诉思想我写了一个程序来计算旅行商问题。我现在终于体会到旅行商问题为什么会这么有名，有很多算法都可以解决旅行商问题，问题描述简单，评价函数也不复杂，问题的解可以

赞助本站