混合型蚁群算法及其应用

高志娥　薛艳锋　兰静

摘要摘要：蚁群优化算法——蚂蚁系统（Ant System，AS）是Dorigo M在20世纪90年代最早提出的一种新型生物智能算法，Dorigo M将蚁群优化算法应用于解决经典的旅行商问题（TSP），取得了较好的应用效果。采用混合型蚁群算法进行优化求解，探讨其实现TSP问题的求解流程，以更好地指导实际问题解决。

关键词关键词：蚁群优化算法；混合型蚁群算法；TSP问题

DOIDOI：10.11907/rjdk.1431040

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2015）004007302

0引言

TSP是一个典型的NP完全问题，没有确定的算法能够在多项式时间内得到问题的解。因此，如何解决旅行商问题，具有很重要的实际应用意义与价值。

TSP问题：假设有n个城市，每一个城市看作一个点，城市的实际距离转化为点的距离，如何寻找一条遍历所有城市且每个城市只被访问一次的路径，并保证总路径距离最短。

其数学描述如下：

其中，K是V的全部非空子集，|K|是集合K中包含图G的全部顶点的个数。

1蚁群算法基本原理

蚁群算法是一种新型的模拟生物习性的智能进化算法。蚁群算法又简称ACO算法，蚁群在搜索食物源过程中，总是表现出极好的寻优路线，使得路程最短。蚁群算法模仿蚁群这一寻优能力特性，解决了很多离散系统优化问题。蚁群算法现已广泛应用于调度问题、旅行商问题（TSP问题）、指派问题、函数优化问题等，均取得了较好的应用效果[1]。

单只蚂蚁的行为比较简易，随机地在搜索区域内寻找食物，但由这样的单只蚂蚁组成的蚁群群体，则可以表现出极其复杂、信息共享的寻优能力，究其原因主要是因为蚂蚁个体之间的信息传递，称之为信息素（pheromone）。蚂蚁在寻找食物过程中，能够在它所通过的路径（位置）上留下信息素，并以此指导自己的运动方向，也可以给其它蚂蚁提供参考作用[2]，且蚂蚁特性是倾向于朝着信息素浓度高（向着食物源）的方向移动。

蚁群算法是一种随机生物智能搜索算法，与其它生物智能算法一样，通过初始化很多组可行解，然后通过迭代寻优，即生物进化功能，来寻求最优解。蚂蚁的特性具体有以下3个方面：

（1）若一只蚂蚁搜索过某条路径，它在下次搜索时，就不会选择该条路径，映射到蚁群算法上，则需要建立禁忌列表模拟蚂蚁的记忆功能。

（2）利用信息素实现个体之间的信息共享。

（3）蚂蚁的群集活动。通过一只蚂蚁的运动很难到达食物源（花费时间可能很长，且容易陷入局部最优），但整个蚁群进行搜索效果则完全不同。蚁群这种行为足以让蚂蚁更加快速地找到食物，且能找到食物最好、最多的位置，也就避免了陷入局部最优等缺陷[3]。

2基于混合型蚁群算法的TSP求解

蚁群算法ACO利用信息素进行信息互享，而粒子群优化算法（又称PSO算法）利用当前个体的位置信息、当前迭代前的个体极值与全局极值这3个信息，通过速度更新，达到个体的位置更新，从而实现问题的优化求解。实验研究表明，简单的蚁群算法也容易出现早熟以及陷入局部最优解等情况，且蚁群算法求解收敛速度不是很快，因此采用蚁群算法和粒子群算法的混合算法，可达到算法的互补，从而提高算法的收敛速度以及避免求解个体陷入局部最优等[4]。

根据蚁群算法和粒子群算法的混合算法，蚂蚁按照蚁群算法完成一次遍历后，再让蚂蚁根据粒子群算法中的个体最优极值和全局最优极值进行蚂蚁的位置调整，则蚁群算法和粒子群算法的混合算法应用于旅行商问题的具体求解流程如下：

（1）nc←0；（nc为迭代次数），进行蚁群算法的参数初始化操作，产生大量的可行路径（例如50条路径），即可行解，从这50个可行路径中选择较好的路径——旅行距离和最短，使蚂蚁在这些初始路径上留下信息素。

（2）根据蚂蚁当前位置计算适应度值（各路径的长度叠加和，满足旅行商求解条件）ltsp0，计算当前适应值个体最优极值，当前位置为个体极值位置，根据各个粒子的个体极值，找出全局极值和全局极值位置。

（3）将各蚂蚁的初始出发点置于当前解集中，对每只蚂蚁k（k=1，2，3，…，m），按照概率pkij移至下一顶点j，并将顶点j置于当前解集。

（4）进入主循环，对每只蚂蚁进行位置更新，第j只蚂蚁路径C0（f）与gcbest交叉得到C1（f），C1（f）与pcbest交叉、变异到C1（f），根据当前位置计算路径长度ltsp1，如果新的适应度值更优，则接受新的可行解值；否则拒绝，第j个粒子路径C1（f）仍为C0（f），重新找到各只蚂蚁的个体极值ptbest和极值位置pcbest，以及找出全局极值gtbest和全局极值位置gcbest。

（5）计算各蚂蚁的路径长度Lk（k=1，2，3…，m），记录当前的最好解。

（6）按蚂蚁位置更新方程修改轨迹强度。

（7）对各边弧（i，j），置Δτij←0，nc←nc+1。

（8）输出目前最好解。

选取下列对象进行混合型蚁群算法的TSP问题分析，该地图信息如图1所示，包括30个城市，各城市之间的位置关系确定。选取轨迹相对重要性α=1.5，能见度相对重要性β=2，蚂蚁数量m=30，轨迹持久性ρ=0.9，针对图1所示城市位置关系，进行混合型蚁群算法寻优求解，得到相应的结果如图2所示。

由图2可知，该混合型蚁群算法具有快速收敛、不易陷入局部最优的特点，避免了蚂蚁个体局部早熟等现象发生，因此混合型蚁群算法较之于简单的蚁群算法具有较好的应用价值[5]。

3结语

蚁群算法是一种用来在图中寻找优化路径的机率型

算法。该算法是一种新型的模拟进化算法，蚁群在搜索食物源的过程中，总是表现出极好的寻优路线，蚁群算法模仿蚁群这一寻优能力特性，解决了很多离散系统优化问题。而在蚁群算法和粒子群算法的混合算法中，蚂蚁根据粒子群算法中的个体最优极值和全局最优极值进行蚂蚁的位置调整，使蚂蚁具有“粒子”的特性，从而达到算法的互补，可提高算法的收敛速度以及避免求解个体陷入局部最优等。

参考文献参考文献：

[1]曹振新，朱云龙.混流轿车总装配线上物料配送的研究与实践[J].计算机集成制造系统，2006，12（6）：289291.

[2]张文诺.基于Petri网的汽车生产物流流程仿真优化研究[D].吉林：吉林大学，2007.

[3]王旭，张芳珍，李文川.汽车混流装配线物料动态配送研究[J].电子技术应用，2010，36（9）：4349.

[4]钱芳，扈静，葛茂根，等.面向机械产品装配过程的物料配送方法研究[J].机械工程师，2011（5）：3437.

[5]朱哲，薛善良，王珉，等.航天产品装配物料配送系统的研究[J].中国制造业信息化，2012，41（15）：912.

责任编辑（责任编辑：黄健）