蚁群遗传算法对于tsp问题应用

《蚁群遗传算法对于tsp问题应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、蚁群遗传算法对于TSP问题应用摘要：遗传算法和蚁群算法是两种具有代表性的智能算法。在解决组合优化问题时，遗传算法具有较快的全局搜索能力，但在解决规模较大的TSP问题时存在一定缺陷，不能取得全局最优解。相反蚁群算搜索速度相对较慢，但有着较高的准确性，对于大规模问题有较好的效果。本文改进了两种算法，将蚁群算法与遗传算法融化起来。首先借助遗传算法的快速搜索能力，快速接近最优解，通过求解结果为蚁群算法设置初始信息量，再借助蚁群算法进行最终结果的求解，得到最优解。经过计算机仿真发现，在一定情况下，新的改进算法

2、对TSP问题的求解能力有一定提高。关键词：蚁群算法；遗传算法；TSP中图分类号：TP18遗传算法在1969年被美国学者提出，后来经过一系列改进总结成一类模拟自然界遗传基因进化的算法lo遗传算法的理论源于达尔文的进化论，模拟生物进化的过程来求解极值问题。遗传算法适合求解各种问题同时具有并行性。因此，遗传算法广泛应用于计算机科学，人工智能，模式识别,机械自动化控制等各种领域。遗传算法的缺点主要是局部搜索能力差，收敛慢。因此如何提高遗传算法的局部搜索能力成为了遗传算法研究的重点。蚁群算法是由意大利学者M.

3、Dorigo提出，模拟自然界中蚂蚁觅食的过程。经过众多学者多年来的研究和改进，能够较好的解决组合优化问题。蚁群算法的原理是一种正反馈机制，通过信息素的分泌和挥发使问题的解最终收敛。蚁群算法同样具有分布式并行计算的优势，可以求解单目标和多目标优化问题。研究证明，对于较大规模的问题，蚁群算法能够较好的使解收敛于最优解。当然，蚁群算法的缺点也很明显，初期搜索速度较慢。结合遗传算法和蚁群算法的优势，学者们考虑将两者融合起来，形成对特定问题更加有效的算法。有些学者提出通过遗传算法调整蚁群算法的参数，以达到优化

4、算法的思路。另一种融合思路是借鉴遗传算法速度较快的搜索速度在前期使用遗传算法进行搜索，然后通过蚁群算法找到最优解。本文就是在这一框架的基础上提出的。1算法遗传算法具有较快的搜索能力，但是在面对规模较大的问题的时候，往往只能够接近最优解而很难取得。而对于蚁群算法，其优势在于能够较准确的找到最优解，但是初始状态的正反馈信息匮乏使得搜索速度较慢。本文将两种算法融化，利用遗传算法计算初始信息素分布，然后在此基础上进行蚁群算法，求解问题。算法定义如下：设对于N个城市的旅行商问题，表示城市之间的联通关系。其中V

5、表示城市的集合，W表示任意两个城市之间的距离的集合。我们用序号为i的城市，表示和间的距离。针对TSP问题，我们在遗传算法的编码上采用十进制的编码方式，用一串十进制数字表示基因。其中每一个基因片段表示一个城市，基因片段的顺序决定了TSP问题中旅行商所走的顺序。设系统中的基因数为，我们定义为系统中第i个基因，其中。基因的长度为N,表示第j个基因片段,J