改进的遗传混合蚁群算法在TSP问题中的应用

摘 要： 为了提高基本蚁群算法的收敛性能和全局求解能力，对基本蚁群算法进行了改进，提出了一种改进的遗传混合蚁群算法。在每代进化中保留最优解和次优解的公共解集后引入遗传操作中的交叉算子进行运算，并采用自适应改变信息素挥发系数的方法，加快了算法收敛速度，提高了解的全局性。通过对 TSP 问题的仿真运算表明，改进的遗传混合蚁群算法在收敛速度和解的全局性上都有较大的改善。

关键词： 蚁群算法； 遗传算法； 交叉算子； 自适应； TSP

中图分类号：TP391 文献标志码：B 文章编号：1006-8228（2012）11-31-02

Application of improved genetic hybrid ant colony algorithm in TSP

Xu Deming

（Huizhou University， Huizhou， Guangdong 516007， China）

Abstract： To improve the efficiency of convergence and the global ability of basic ACA， a novel hybrid algorithm is proposed， which is an improved combination of GA and ACA. Cross operator is calculated after reserving the intersection of the best solution and the second best solution in every evolution， and the adaptive change pheromone volatile coefficient is affected. Convergence speed is accelerated and the global ability of the algorithm is improved. The simulations for TSP problem show that the improved algorithm has better convergence efficiency and global ability.

Key words： ant colony algorithm（ACA）； genetic algorithm（GA）； cross operator； the adaptive change； TSP

0 引言

旅行商问题（Traveling Salesman Problem，TSP）又称货郎担问题，是一个著名的组合优化问题，也是一个典型的、易于描述却难于处理的NP完全问题[1]。由于该问题的实际模型在路径、网络、分配、基因测序和机器人控制等方面有着广泛的应用[2]，故长期以来一直吸引着许多领域的研究人员对其算法改进的关注。

蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、分布式计算和贪婪启发式搜索的特点。由于蚁群算法容易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步搜索，不利于发现更好的解，而且蚁群中多个个体的运动是随机的，当群体规模较大或网络结构较为复杂时，要找出一条较好的路径需要较长的搜索时间。

遗传算法因其具有良好的鲁棒性、可并行性与全局优化性而在求解组合最优化问题时获得了广泛的应用。但是，在实际应用中，遗传算法早熟收敛等缺陷没有从根本上消除，因此，通常存在计算量大的问题，从而导致定位速度慢。

遗传算法和蚁群算法都是受生物进化论的启发而提出来的仿生算法，两种算法都应用于求解组合优化问题上，并取得了一定的成果。本文在基本蚁群算法的基础上，给出一种改进的遗传混合蚁群算法，这种改进后的混合算法利用遗传算法中交叉与变异的优点，通过引入交叉算子增强蚁群算法寻找全局最优解的能力和加快算法的收敛速度，并采用自适应改变ρ值的方法提高了算法的全局搜索能力。仿真实验表明，改进后的新算法能在保证一定的收敛速度的基础上改进算法的全局收敛性。

1 基本蚁群算法原理（基本ACA）

蚂蚁从某一地点出发，按照状态转移规则选择下一路径，该规则也被称为“随机比率规则”。蚂蚁选择路径的转移概率为：

⑴

式⑴中τij（t）为t时刻路径（i，j）上的信息量；蚂蚁在运动过程中用禁忌表tabuk来记录蚂蚁k走过的城市；allowedk={c-tabuk}表示蚂蚁k下一步允许选择的城市；α为信息启发式因子，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用；β为期望启发式因子，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度。ηij（t）为启发函数，其表达式如下：

⑵

式⑵中dij表示相邻两个城市之间的距离。对蚂蚁k而言，dij越小，则ηij（t）越大，也就越大。每只蚂蚁走完一步或者完成一次循环，要对残留的信息进行更新处理，每次迭代完成后，各路径上的信息素都需要进行更新，其公式如下：

⑶

⑷

式⑶中ρ表示信息素挥发系数，1-ρ表示信息素的残留因子；式⑷中表示第k只蚂蚁在本次循环中留在路径（i，j）上的信息量，其计算方法按照Ant-Cycle模型如下：

⑸

Q表示信息素强度，它在一定程度上影响算法的收敛速度；Lk表示第k只蚂蚁在本次循环中所走过的路径的总长度。

当所有蚂蚁遍历完一次后，要对残留信息进行全局更新处理，其表达式同式⑶、式⑷，只是的表达式有所不同，在全局更新中只更新本次循环最小路径L上的信息量，如下：

⑹

2 遗传算法与蚁群算法融合（GAAA）

根据遗传算法和蚁群算法两者在某个集成算法中所处的地位和优势不同，大体可以划分为两个大类算法：一类是以蚁群算法为主体的混合蚁群算法，如文献[3]利用遗传算法GA寻找ACS中ρ、α、β的最优组合；另一类是以遗传算法为主体的混合遗传算法如参考文献[4-7]。本文基本思路是：算法前过程采用遗传算法，充分利用遗传算法的快速性、随机性、全局收敛性，其结果是产生有关问题的初始信息素分布；算法后过程采用蚁群算法，在有一定初始信息素分布的情况下，充分利用蚂蚁算法并行性、正反馈性、求精解效率高等特点。其总体框架如图1所示。