论文部分内容阅读
摘要：遗传算法和蚁群算法是两种具有代表性的智能算法。在解决组合优化问题时，遗传算法具有较快的全局搜索能力，但在解决规模较大的TSP问题时存在一定缺陷，不能取得全局最优解。相反蚁群算搜索速度相对较慢，但有着较高的准确性，对于大规模问题有较好的效果。本文改进了两种算法，将蚁群算法与遗传算法融化起来。首先借助遗传算法的快速搜索能力，快速接近最优解，通过求解结果为蚁群算法设置初始信息量，再借助蚁群算法进行最终结果的求解，得到最优解。经过计算机仿真发现，在一定情况下，新的改进算法对TSP问题的求解能力有一定提高。
关键词：蚁群算法；遗传算法；TSP
中图分类号：TP18
遗传算法在1969年被美国学者提出，后来经过一系列改进总结成一类模拟自然界遗传基因进化的算法1。遗传算法的理论源于达尔文的进化论，模拟生物进化的过程来求解极值问题。遗传算法适合求解各种问题同时具有并行性。因此，遗传算法广泛应用于计算机科学，人工智能，模式识别，机械自动化控制等各种领域。遗传算法的缺点主要是局部搜索能力差，收敛慢。因此如何提高遗传算法的局部搜索能力成为了遗传算法研究的重点。
蚁群算法是由意大利学者M.Dorigo提出，模拟自然界中蚂蚁觅食的过程。经过众多学者多年来的研究和改进，能够较好的解决组合优化问题。蚁群算法的原理是一种正反馈机制，通过信息素的分泌和挥发使问题的解最终收敛。蚁群算法同样具有分布式并行计算的优势，可以求解单目标和多目标优化问题。研究证明，对于较大规模的问题，蚁群算法能够较好的使解收敛于最优解。当然，蚁群算法的缺点也很明显，初期搜索速度较慢。
结合遗传算法和蚁群算法的优势，学者们考虑将两者融合起来，形成对特定问题更加有效的算法。有些学者提出通过遗传算法调整蚁群算法的参数，以达到优化算法的思路。另一种融合思路是借鉴遗传算法速度较快的搜索速度在前期使用遗传算法进行搜索，然后通过蚁群算法找到最优解。本文就是在这一框架的基础上提出的。
1算法
遗传算法具有较快的搜索能力，但是在面对规模较大的问题的时候，往往只能够接近最优解而很难取得。而对于蚁群算法，其优势在于能够较准确的找到最优解，但是初始状态的正反馈信息匮乏使得搜索速度较慢。
本文将两种算法融化，利用遗传算法计算初始信息素分布，然后在此基础上进行蚁群算法，求解问题。
算法定义如下：设对于N个城市的旅行商问题， 表示城市之间的联通关系。其中V表示城市的集合，W表示任意两个城市之间的距离的集合。我们用 序号为i的城市， 表示 和 间的距离。
针对TSP问题，我们在遗传算法的编码上采用十进制的编码方式，用一串十进制数字表示基因。其中每一个基因片段表示一个城市，基因片段的顺序决定了TSP问题中旅行商所走的顺序。设系统中的基因数为 ，我们定义 为系统中第i个基因，其中 。基因的长度为N， 表示第j个基因片段， j (1)
设第i个基因的适应度为 ，则有：
(2)
下面给出选择操作，交叉操作和变异操作：
选择操作是对于当前代次的基因，选择 个基因加入繁殖池进行繁殖，选择的概率依据 。
(3)
交叉操作是从繁殖池中选出 对基因，进行基因交叉。具体的操作如下：
父代1：12|3456
父代2：65|4321
交叉之后得到：
子代1：12|4365
子代2：65|3412
子代1和子代2分别选取父代1和父代2的前半部分，然后将父代2和父代1的后半部分中重复的部分剔除，再与前半部拼接而成。将生成的子代基因最为新一代的基因。
变异操作是指将新一代中的部分基因进行变异以增加种群的多样性。具体的操作是随机选择两个基因片段进行位置交换。下面我们介绍蚁群算法部分：
我们将M个蚂蚁放置在系统中，每一只蚂蚁将在当前代次选择一个路径遍历所有城市，其中每一步的选择依赖于路径上的信息素。设 为蚂蚁k下一步从城市i到城市j的概率，则有：
(4)
和 分别表示信息因子和启发因子， 表示t时刻城市i到城市j之间的信息素。 表示k已经访问的城市集合。信息素的更新规则如下：
(5)
(6)
(7)
表示算法的启发函数， 。 表示挥发程度， 。
我们设 为总时间， 和 分别为蚁群算法和遗传算法的时间。则有：
(8)
设 表示第k个基因所对应路径上的边的集合。对于已经通过遗传算法求出的解，我们通过下面的公式对其进行信息素的分布：
(9)
算法的整体流程如下：
1.初始化 个基因。
2.计算适应度。
3.进行选择操作。
4.进行交叉操作。
5.计算适应度进行变异操作。
6.如果 ， 跳转到2，否则到7。
7.用遗传算法得到的解初始化信息素。
8.初始化M个蚂蚁分布与N个城市。
9.蚂蚁根据适应度和启发信息移动。
10.更新信息素。
11.如果 ， 跳转到9，否则到12。12.在得到的路径中选取最优的作为问题的解。
2结论
本文中我们通过对遗传算法和蚁群算法进行改进、融化。得到了一种GAACS算法的框架。该算法发挥了遗传算法的快速搜索能力和蚁群算法的精确搜索能力，提高了算法整体解决TSP问题的效果，从计算机仿真的结果可以看出，GAACS算法能够求解出最优解，同时可以节省一定的计算时间。
当然对于GAACS中一些具体的参数设定，以及两种算法的融合方式，还有待进一步的探讨。该算法依然具有较大的提升空间，这些工作我们将在后续的研究中进行。
参考文献：
[1]HOLLAND JH. Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan Press,1975.
[2]DeJONG K A. The analysis of the behavior of a class of genetic adap-tive systems[D].Ann Arbor: University of Michigan,1975.
关键词：蚁群算法；遗传算法；TSP
中图分类号：TP18
遗传算法在1969年被美国学者提出，后来经过一系列改进总结成一类模拟自然界遗传基因进化的算法1。遗传算法的理论源于达尔文的进化论，模拟生物进化的过程来求解极值问题。遗传算法适合求解各种问题同时具有并行性。因此，遗传算法广泛应用于计算机科学，人工智能，模式识别，机械自动化控制等各种领域。遗传算法的缺点主要是局部搜索能力差，收敛慢。因此如何提高遗传算法的局部搜索能力成为了遗传算法研究的重点。
蚁群算法是由意大利学者M.Dorigo提出，模拟自然界中蚂蚁觅食的过程。经过众多学者多年来的研究和改进，能够较好的解决组合优化问题。蚁群算法的原理是一种正反馈机制，通过信息素的分泌和挥发使问题的解最终收敛。蚁群算法同样具有分布式并行计算的优势，可以求解单目标和多目标优化问题。研究证明，对于较大规模的问题，蚁群算法能够较好的使解收敛于最优解。当然，蚁群算法的缺点也很明显，初期搜索速度较慢。
结合遗传算法和蚁群算法的优势，学者们考虑将两者融合起来，形成对特定问题更加有效的算法。有些学者提出通过遗传算法调整蚁群算法的参数，以达到优化算法的思路。另一种融合思路是借鉴遗传算法速度较快的搜索速度在前期使用遗传算法进行搜索，然后通过蚁群算法找到最优解。本文就是在这一框架的基础上提出的。
1算法
遗传算法具有较快的搜索能力，但是在面对规模较大的问题的时候，往往只能够接近最优解而很难取得。而对于蚁群算法，其优势在于能够较准确的找到最优解，但是初始状态的正反馈信息匮乏使得搜索速度较慢。
本文将两种算法融化，利用遗传算法计算初始信息素分布，然后在此基础上进行蚁群算法，求解问题。
算法定义如下：设对于N个城市的旅行商问题， 表示城市之间的联通关系。其中V表示城市的集合，W表示任意两个城市之间的距离的集合。我们用 序号为i的城市， 表示 和 间的距离。
针对TSP问题，我们在遗传算法的编码上采用十进制的编码方式，用一串十进制数字表示基因。其中每一个基因片段表示一个城市，基因片段的顺序决定了TSP问题中旅行商所走的顺序。设系统中的基因数为 ，我们定义 为系统中第i个基因，其中 。基因的长度为N， 表示第j个基因片段， j
设第i个基因的适应度为 ，则有：
(2)
下面给出选择操作，交叉操作和变异操作：
选择操作是对于当前代次的基因，选择 个基因加入繁殖池进行繁殖，选择的概率依据 。
(3)
交叉操作是从繁殖池中选出 对基因，进行基因交叉。具体的操作如下：
父代1：12|3456
父代2：65|4321
交叉之后得到：
子代1：12|4365
子代2：65|3412
子代1和子代2分别选取父代1和父代2的前半部分，然后将父代2和父代1的后半部分中重复的部分剔除，再与前半部拼接而成。将生成的子代基因最为新一代的基因。
变异操作是指将新一代中的部分基因进行变异以增加种群的多样性。具体的操作是随机选择两个基因片段进行位置交换。下面我们介绍蚁群算法部分：
我们将M个蚂蚁放置在系统中，每一只蚂蚁将在当前代次选择一个路径遍历所有城市，其中每一步的选择依赖于路径上的信息素。设 为蚂蚁k下一步从城市i到城市j的概率，则有：
(4)
和 分别表示信息因子和启发因子， 表示t时刻城市i到城市j之间的信息素。 表示k已经访问的城市集合。信息素的更新规则如下：
(5)
(6)
(7)
表示算法的启发函数， 。 表示挥发程度， 。
我们设 为总时间， 和 分别为蚁群算法和遗传算法的时间。则有：
(8)
设 表示第k个基因所对应路径上的边的集合。对于已经通过遗传算法求出的解，我们通过下面的公式对其进行信息素的分布：
(9)
算法的整体流程如下：
1.初始化 个基因。
2.计算适应度。
3.进行选择操作。
4.进行交叉操作。
5.计算适应度进行变异操作。
6.如果 ， 跳转到2，否则到7。
7.用遗传算法得到的解初始化信息素。
8.初始化M个蚂蚁分布与N个城市。
9.蚂蚁根据适应度和启发信息移动。
10.更新信息素。
11.如果 ， 跳转到9，否则到12。12.在得到的路径中选取最优的作为问题的解。
2结论
本文中我们通过对遗传算法和蚁群算法进行改进、融化。得到了一种GAACS算法的框架。该算法发挥了遗传算法的快速搜索能力和蚁群算法的精确搜索能力，提高了算法整体解决TSP问题的效果，从计算机仿真的结果可以看出，GAACS算法能够求解出最优解，同时可以节省一定的计算时间。
当然对于GAACS中一些具体的参数设定，以及两种算法的融合方式，还有待进一步的探讨。该算法依然具有较大的提升空间，这些工作我们将在后续的研究中进行。
参考文献：
[1]HOLLAND JH. Adaptation in natural and artificial systems[M].Ann Arbor:University of Michigan Press,1975.
[2]DeJONG K A. The analysis of the behavior of a class of genetic adap-tive systems[D].Ann Arbor: University of Michigan,1975.