改进的遗传混合蚁群算法在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所示。

[初始化参数，根据优化解生成信息素初始分布，将m只蚂蚁置于n个结点][计算每只蚂蚁移动到下一结点的概率，根据选择概率移动每只蚂蚁到下一结点][根据式⑶～式⑸局部更新每条路径上的信息量][问题][定义目标函数和适应值函数][随机生成一组实数编码][递归迭代][根据适应函数选择X，Y][对X，Y进行交叉计算][根据适应值函数进行逆转变异][生成若干组优化解][根据式⑶⑷⑹全局更新每条路径上的信息量][输出最优解][递归迭代]

图1遗传混合蚁群算法流程图

3 混合算法的改进

在基本遗传混合蚁群算法的基础上，本文给出了一种改进的遗传混合蚁群算法，这种改进后的混合算法通过改进遗传算法中交叉算子和采用自适应ρ值的方法增强算法寻找全局最优解的能力和加快算法的收敛速度。

3.1 交叉计算的改进[8]

Davis提出的顺序交叉方法是先进行普通的双点交叉，再进行维持原有相对访问顺序的巡回路线修改。这种算法和蚁群算法融合后可以提高算法的搜索空间，有助于提高算法的全局性，但是这种交叉具有随机性，算法整体收敛速度不快。本文算法采用保留每代进化中最优的两个解的公共解，采用单点交叉后再维持原有相对访问顺序的巡回路线修改，具体做法是：

设在n个城市的TSP问题中，TSP的一个解可表示为一个循环排列C=（C1，C2，…，Cn，Cl），定义任意两个解Ci，Cj的交集Aij=Ci∩Cj，其中Aij表示Ci，Cj中排列相同的且子集中元素数目大于2的子集。对于第t代进化中选取最优解Ct1=（…，Ca，…，Cb，…，Cc，…，Cd，…）和次优解Ct2=（…，Cc…，Cd…，Ca，…，Cb），则（Ca，…，Cb）和（Cc，…，Cd）就是Ct1∩Ct2的两个子集At1t2。在做交叉组合前保留交集，记=Ct1-At1t2，=Ct2-At1t2对，的元素进行中心单点交叉重组，将父体交叉点前元素不变的复制到后代New2中，同时把Ct2加到New2中，同样也将父体交叉点前元素不变地复制到后代New1中，同时把Ct1加到New1中；在New1、New2中删除与交叉段相同的元素得到新一代的New1、New2。

3.2 ρ取值的改进

当问题规模比较大时，一方面由于在信息量更新公式中采用了信息素挥发系数1-ρ，使得那些从未被搜索到路径上的信息量会逐渐减少到0——该路径将不被搜索，这就降低了算法的全局搜索能力；另一方面，当信息素含量ρ值过大时，随着解的信息量增大，以前搜索过的解被选择的可能性过大，也会影响到算法的全局搜索能力，为此应减小ρ值，从而提高全局搜索能力，但这样又会降低算法的收敛速度。针对上述问题，本文采用自适应地改变ρ值[9]的方法，具体做法是：初始时刻取ρ=0.999；当算法在一定的循环次数内取得的最优值没有明显改变时，ρ值减为：

其中ρmin为ρ的最小值，这样可以防止ρ过小而降低算法的收敛速度；rand（）为是随机函数。这种自适应改变ρ值的方法保证了在一定的搜索速度下有效地提高混合算法的全局搜索能力。

4 实验结果与分析

为了验证混合算法的有效性，通过对TSPLIB中Oliver30问题进行仿真研究，平均运行20次作为仿真结果。实验中采用的各项参数是：α=1，β=5，Q=150，蚂蚁数目m=10，设置最大循环次数250次。实验结果数据如表1所示。

表1三种算法最优解、平均解和进化代数

[[问题＼&算法＼&平均值＼&最优值＼&平均进化代数＼&Oliver30＼&基本ACA＼&437.09＼&423.73＼&121＼&GAAA＼&433.54＼&423.73＼&101＼&改进的GAAA＼&430.95＼&423.73＼&54＼&]]

从表1中的实验数据可以看出，本文算法的全局性和收敛性相对有所提高。本文通过融入遗传算法，引入交叉算子扩大算法的搜索空间，同时在交叉运算中保留解中公共最优路径加快了算法的收敛速度，并采用自适应改变ρ值的方法提高了算法的全局搜索能力。通过对TSP问题的仿真表明本文算法是一种有效的改进算法。

参考文献：

[1] Lin S，Kernighan B W.An effective heuristic algorithm for the

traveling salesman problem[J]. Operational Research，1971.19：486-515

[2] Michalewicz Z. How to solve it—modern heuristics[M].Berlin

Heidelberg：Springer-Verlag，2000.

[3] Zhan Shi- chang， Xu Jie， Wu Jun. The optimal selection on the

parameters of the ant colony algorithm[J].Bulletin of Science and Technology，2003.19（5）：381-386

[4] Chen H， Flann N S.Parallel simulated annealing and genetic

algo-rithms： a space of hybrid methods[M]//Parallel Problem Solving from Nature 3.[S.l.]：Springer-Verlag，1994：428-438

[5] Lee S， oLson D.A gradient algorithms for chance constrained

non-linear programming[J].European Journal of Operational Research，1977.11（1）：343-369

[6] Mahfoud S W， Goldgerg D E.A genetic algorithm for parallel

sim-ulated annealing[M]//Parallel Problem Solving from Nature 2， North Holland，1992：301-310

[7] Bilchev G， Parmee I C.Adaptive searching strategies for heavily

constrained design spaces[C]//Proceedings of 22nd International Conference on Computer Aided Design'95， Yelta： Ukraine，1995：230-235

[8] 刘立东，蔡淮.融入遗传算法的混合蚁群算法[J].计算机工程与设计，

2008.29（5）：1248-1252

[9] 曹文梁，康岚兰.基于遗传算法的混合蚁群算法及其在TSP中的应用

研究[J].制造业自动化，2011.33（1）：91-93