蚁群分析

关键词： 算法 运行 性能

蚁群分析（精选十篇）

蚁群分析 篇1

关键词：蚁群系统,运行时间分布,解的性能分布

1 TSP问题

TSP问题是组合优化中经典的问题, 指一位商人, 从家乡出发, 希望能找到一条最短的路径, 途经给定城市集合中所有的城市, 最后返回家乡, 每个城市都被访问一次且仅一次。

2 蚁群系统

蚁群系统ACS (Ant Colony System) 是求解TSP问题诸多算法中取得较好性能的一种启发式算法, 由意大利学者M.Dorigo等人在90年代首先提出, 其算法描述如下:

1) 初始时刻, m只蚂蚁被分别放置到随机选择出来的城市中。

2) 蚂蚁k (k=1, 2, …, m) 按照一个称为伪随机比例规则选择下一步要转移的城市, 在t时刻, 位于城市i的蚂蚁k选择城市j的规则由如下式子给出:

其中q是分布在区间[0, 1]中的一个随机变量, q0是一个参数, J是根据式 (2) 给出的概率分布产生出来的一个随机变量。

其中, τij为边 (i, j) 的信息素量, ηij为从城市i转移到城市j的启发式信息, α和β是两个参数, allowedk为蚂蚁k下一步允许访问的城市的集合。

3) 蚂蚁每经过一条边 (i, j) , 调用下式进行局部信息素更新:

τij← (1-ξ) τij+ξτ0 (3)

其中ξ满足0<ξ<1, τ0是信息素的初始值。

4) 经过n个时刻, 所有的蚂蚁都完成了一次周游。走过最短路径的蚂蚁根据如下式子进行全局信息素的更新:

τij← (1-ρ) τij+ρΔτ${}_{ij}^{bs}$∀ (i, j) ∈Tbs (4)

其中ρ为信息素蒸发率, Δτ${}_{ij}^{bs}$=1/Cbs。

5) 当蚂蚁周游次数达到设定值时算法结束, 输出最优解。

ACS算法求解TSP的性能如何?是否一定找到全局最优解呢?也就是说, 如果有足够的运行时间, 是否能保证算法找到一个最优解的概率会任意地接近1 (值收敛) Gutjahr于2000年提出了第一个关于蚁群算法的收敛性证明[1]。Gutjahr将蚁群算法的行为简化为在一幅代表所求问题的有向图上的行走过程, 进而从有向图论的角度对一种改进蚁群算法— 基于图的蚂蚁系统 (GBAS) 的收敛性进行了理论分析, 证明了在一些合理的假设条件下, GBAS能以一定的概率收敛到所求问题的最优解。但Gutjahr在文献[1]中并没有给出GBAS的实验结果, 因此不能从实验角度验证算法的性能。

本文通过实验从运行时间分布及解的性能分布两个方面研究ACS算法求解TSP的性能问题。ACS算法的源代码来自www.aco-metaheuristic.org/aco-code/, 采用ANSI C开发, 运行环境为一台P4 2.8GHz的PC机, 编译工具为基于Windows XP的C-free 2.0。

3 算法运行时间分布分析

3.1 运行时间分布定义

算法的运行时间分布RTD (Running Time Distribution) 是指算法的运行时间与在这个时间内得到全局最优解 (或与全局最优解在一定误差范围内的解) 的概率之间的对应关系。具体来说RTD分布图上的一个数据点 (t, Fe (t) ) 是指在运行时间t内得到与全局最优解误差小于等于e%的解的概率为Fe (t) 。

对算法运行时间分布的研究意义在于找到算法的运行规律, 是否运行时间足够长就能找到最优解的概率接近1

3.2 实验统计结果

为了获得ACS算法求解TSP问题的运行时间分布, 本文对TSPLIB中的实例lin318.tsp、pcb442.tsp进行了分析。对每一个实例, 运行100 次独立的ACS算法, 每一次运行的时间根据实例规模的大小而设置或是得到全局最优解。对于每一次运行, 记录得到全局最优解时的CPU运行时间;对于规模较大的实例, 如果在规定的运行时间内都未能获得最优解, 就取一个与最优解相差e%的近似阈值, 当得到的解小于等于这个阈值的时候就跳出循环同时记录当前的CPU运行时间。这样就得到了一组ACS算法运行时间的数据, 然后根据文献[2]中的运行时间分布计算式 (5) 得到算法求解TSP问题的RTD分布。

Fe (t) =|{j|rt (j) ≤t and f (xj) ≤e%×opt}|/k (5)

在式 (5) 中rt (j) 表示第j次独立运行ACS算法所用的时间, f (xj) 表示第j次运行得到的TSP实例的解, opt表示TSP实例的全局最优解。k为算法的运行次数, 本文中k=100。

lin318.tsp每次运行60秒, 运行时间分布如图1所示, pcb442.tsp每次运行1000秒, 运行时间分布如图2所示。

3.3 实验统计结果分析

蚁群算法的工作过程是随机搜索过程, 算法能否找到最优解是人们关心的一个问题。从图1可以看出, 对于小规模的TSP实例, ACS算法在很短时间内就找到最优解。对于lin318.tsp, 算法运行60秒后以很高的概率 (接近1) 找到最优解。从图2可以看出, 对于中大规模的TSP实例来说, 找到最优解的运行时间就比较长, 如对于pcb442.tsp, 算法运行1000秒找到最优解的概率为0.31, 但从时间运行分布图看出, 算法找到最优解的概率是随着运行时间的增加而增大的, 因此, 可以得出这样的结论:只要有足够的运行时间, 算法找到最优解的概率会任意地接近1, 也就是算法一定会收敛, 但无法估计收敛的速度, 找到最优解的计算时间仍然是未知的。

4 算法解的性能分布分析

通过ACS算法运行时间分布的分析可以知道, 只要运行时间足够, 算法一定会找到一个最优解, 但找到最优解的计算时间是未知的。有时候想得到与最优解距离在某个范围的解, 可以通过分析算法解的性能分布, 设置合适的运行时间就可以以很高的概率得到满足要求的解。因此, 分析算法在不同的运行时间下得到解的性能分布是不同于RTD的另一重要特性。通过分析算法解的性能的分布, 对求解TSP问题有一定的指导意义。

4.1 解的性能分布定义

解的性能分布SPD (Solution Performance Distribution) 用于表示ACS算法求解TSP问题在不同的运行时间下得到的解的分布情况。 SPD是指在固定的时间阈值内, 算法得到的解同全局最优解之间的距离的相对差D (xj) (式 (6) ) 和得到这个距离的概率Ft (w) (式 (7) ) 之间的对应关系。具体来说SPD分布图上的一个数据点 (w, Ft (w) ) 是指在时间阈值t内算法得到与全局最优解距离相对差小于等于w的解的概率为Ft (w) 。

D (xj) =f (xj) /opt-1 (6)

在式 (6) 中f (xj) 表示第j次运行得到的TSP实例的解, opt表示TSP实例的全局最优解。

Ft (w) =|{j|rt (j) ≤t and D (xj) ≤w}|/k (7)

在式 (7) 中, rt (j) 表示第j次独立运行ACS算法所用的时间, t为时间阈值, w为算法得到的解同全局最优解之间的距离的相对差, k为算法的运行次数。

4.2 实验统计结果

为了获得ACS算法求解TSP问题解的性能分布, 本文对TSPLIB中的实例lin318.tsp、pcb442.tsp进行了分析。对每一个实例, 运行100次。对于每一次运行, 记录在时间阈值t得到的解的性能。这样对每一个实例根据算法运行的不同的时间阈值t就得到了不同的几组解的数据, 每一组数据表示了算法在不同的时间阈值t的运行情况。然后根据每一组的数据由式 (7) 得到解的性能分布。

Lin318.tsp设置时间阈值t=10秒、30秒、60秒各运行100次 (k=100) , 得出解的性能分布图如图3所示。Pcb442.tsp设置时间阈值t=10秒、60秒、300秒、1000秒各运行100次, 得出解的性能分布图如图4所示。

4.3 实验统计结果分析

根据图3、图4中的统计结果, 可以得到如下结论:

1) 算法获得最优解的概率随着运行时间的增加而增大, 但找到最优解的时间是未知的。

对于规模较小的TSP实例 (城市规模在400以下) , 设置较小的运行时间就可以以较高的概率获得最优解。如对于lin318.tsp, 设运行时间t=10秒时, 获得最优解的概率为0.16, 当设t=30秒时, 获得最优解的概率为0.78, 设t=60秒时, 获得最优解的概率为0.85。

对于规模较大的TSP实例 (城市规模在400以上) , 需要设置较大的运行时间才能获得最优解。如对于pcb442.tsp, 设置t=10和t=60秒时, 都没能找到最优解。设置t=300秒时, 获得最优解的概率为0.03, 设置t=1000秒时, 获得最优解的概率为0.31。

2) 算法可以通过重启策略获得与最优解距离在一定范围内的解。

以pcb442.tsp为例, 如果得到与最优解距离在0.5%内的解就满足需求, 则通过设置运行时间t=60秒就能以较高的概率 (0.92) 得到这样的解。 如果运行超过60秒还没有得到满足需求的解, 则可以通过重新启动算法, 而不需要一直运行下去, 从而缩短运行时间同时增大获得最优解的概率。

3) 算法的执行效果是分阶段的, 运行前期改进解的性能速度较快, 但后期速度明显减慢。

例如pcb442.tsp , 运行t=60秒就能以较高的概率得到与最优解距离在0.5%范围内的解, 但如果想以较高的概率得到距离在0.25%范围内的解, 则需设置运行时间至少为t=1000秒, 也就是说算法在刚开始的一些循环中改进解的性能的速度是很快的, 但是在60～1000秒这么长的时间中改进的速度明显减慢。

5 结束语

本文通过实验得出了ACS算法求解TSP的运行时间分布 (RTD) 和解的性能分布 (SPD) 。通过对RTD和SPD的分析, 得出了算法找到最优解的概率是随着运行时间的增加而增大的结论, 算法的执行效果是分阶段的, 运行前期改进解的性能速度较快, 但后期速度明显减慢。如果想获得与最优解距离在一定范围内的解, 可以通过重新启动算法, 而不需要一直运行下去, 从而可以在工程运用中缩短运行时间同时增大获得最优解的概率, 这对TSP问题的实际应用具有一定的指导意义。

今后的工作是尝试能否从大量的实验中通过统计分析找到RTD和SPD的理论分布, 建立理论模型, 从理论上分析算法的行为和性能。

参考文献

[1]Gutjahr WJ.Agraph-based ant aystem and its convergence[J].FutureGeneration Computer System, 2000, 16 (8) :873- 888.

[2]Stuzle T, Hoos H.Analyzing the run-time behavior of iterated localsearch for the TSP[J].In:Hansen P., Ribeiro C.eds.Essays and Sur-veys on Metaheuristics Boston, USA:Kluwer Academic Publishers, 2002:589- 612.

[3]Dorigo M, Gambardella L M.Ant colonies for the traveling salesmanproblem[J].BioSystems, 1997 (43) :73 -81.

[4]邹鹏, 周智, 江贺, 陈国良, 顾钧。求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析[J].计算机学报, 2006, 29 (1) :92- 99.

蚁群算法 篇2

蚁群算法是一种仿生类非线性优化算法,具有并行性、正反馈性和全局极小搜索能力强等特点.蚁群算法的机理是:生物界中的蚂蚁在搜寻食物源时,能在其走过的路径上释放一种蚂蚁特有的分泌物信息素,使得一定范围内的其他蚂蚁能够觉察并影响其行为.当某些路径上走过的蚂蚁越来越多时,留下的这种信息素轨迹也越多,以至信息素强度增大,使后来蚂蚁选择该路径的.概率也越高,从而更增加了该路径的信息素强度.为了将起源于离散网络路径优化的原始蚁群算法思想用于连续函数优化的地球物理反演问题,必须对有关实施细节进行改造和修正,本文基于网格划分策略的连续域蚁群算法实现了连续域大地电磁蚁群算法.通过选择蚂蚁数、信息素挥发系数等参数,利用三层K型模型和四层HA型模型进行数值试验,结果表明,蚁群算法可以稳定收敛,反演结果接近理论模型.

作 者：王书明 刘玉兰 王家映 Wang Shuming Liu Yulan Wang Jiaying 作者单位：王书明,Wang Shuming(中国地质大学,地球物理与空间信息学院,武汉,430074;University,of,Utah,Salt,Lake,City,84112,U.S.A)

刘玉兰,Liu Yulan(东方地球物理勘探有限责任公司,涿州,072751)

王家映,Wang Jiaying(中国地质大学,地球物理与空间信息学院,武汉,430074)

蚁群分析 篇3

【关键词】TSP问题；蚁群算法；遗传算法；仿真分析

目前，关于蚁群算法在TSP问题中的应用及改进已经相对成熟，文献[1]通过引入模糊集合的概念提出改进路径更新效果的蚁群算法（FACO），该方法通过模糊评价充分合理利用信息素，能有效提高求得最优解的几率，是一种有效的改进算法。文献[2]通过在最大最小蚁群算法基础上，通过遗传算法特点对蚁群算法参数设置进行优化，有效提高算法求解信息素的速度。文献[3]通过提出相遇策略以及分组并列运行方式改进蚁群算法以及在二维和三维环境进行建模仿真，验证了蚁群改进算法的可靠和有效性。文献[4]通过提出扩大局部搜索空间策略和信息素更新机制提出蚁群自适应优化算法求解TSP问题的方法，提高算法收敛速度和精度。同时探讨了将混沌扰动引入信息素更新的求解过程，可以用更优解取代当前最优值。

1、基本蚁群算法TSP仿真分析及改进

基本蚁群算法求解TSP问题的实质在于引入蚂蚁行走的思想求解最优路径问题，蚂蚁随机挑选路径并产生信息素，信息素越大代表路径长度越短从而反馈引导蚂蚁选择路径最短的路线，蚁群算法有比较好的自组织性，通过整体反馈寻优可以应用于很多实际组合优化问题。

对于蚁群算法的流程，首先应该明确蚁群算法公式及符号定义

在蚁群算法描述之前，引入如下变量记号：m：蚁群中的蚂蚁数量；

β：启发信息影响程度的表达因子，相当于能见度；

ρ：信息素挥发系数，ρ<1；

dij：边（i，j）代表城市距离；

ηij：边（i，j）的启发因子，取ηij=I/dij，这个值固定，一般不随蚂蚁系统而改变；

τij：边（i，j）的信息素值表示；

Pkij（t）：在t时刻蚂蚁k从城市i转移到城市j的概率，i为当前蚂蚁所在的城市，j为蚂蚁尚未访问过的城市；

其中，蚂蚁系统使用随机比例规则进行状态转移，用公式（1-1）表示：

（1-1）

allowedK：在本次循环中蚂蚁k未曾访问的城市集合；

tabuK：蚂蚁k的禁忌表，记录蚂蚁己经访问的城市而禁止再走这些城市。

城市i和城市j之间路径的信息素量，经过n个时刻，信息素调整如公式（1-2）所示：

（1-2）

其中信息素调整原则我们采用蚁周（ant-cycle system）模型，利用的是蚂蚁的全局信息素调整方式，效果最为优越，蚁周模型中：

其中Q：表示蚂蚁释放在所经过路径上（一个过程或一次迭代）的信息素总量，为正常数；

Lk：表示第k只蚂蚁在当前迭代中所经过的路径长度；

△τijk：表示蚂蚁k释放在路径（i，j）上的信息素；△τij：表示所有蚂蚁释放在路径（i，j）上的信息素总和。

本文进行如下蚁群算法TSP仿真实现，选取参数信息素启发因子 a=1，路径启发因子β=2，局部信息素挥发系数ρ1=0.2，全局信息素挥发系数ρ2=0.1，蚂蚁数量为m=100，最大迭代次数NCmax=500实际仿真结果如下：

同时我们输出蚁群个体适应度最优随着迭代次数的变化曲线，在迭代50次以后适应度值达到相对稳定状态，表示路径选择基本稳定在小范围波动，从而达到输出路径的效果[5]。验证了蚁群算法的有效性。

同时可以对基本蚁群算法作出改进，即采用最大最小蚂蚁系统对将信息素在每条路径上的值限定于[τmin，τmax]范围内，如若超出范围则被强制置为上限或下限。这样可以有效控制路径上的信息素差值多大导致的算法过早收敛，同时有利于蚁群的集中搜索[6]。仿真结果如图3：

2、结论

利用蚁群算法对TSP问题的求解，验证了蚁群算法在路径规划问题中的有效性，同时对蚁群算法的参数设置对仿真结果的影响进行探讨，蚁群算法的参数较多，如何设置需要根据对算法具体要求合理配置。综上分析，蚁群算法在求解TSP问题时具有比较强的速度优势，而遗传算法具有比较高的可靠性和独立性，因此我们通过以上仿真分析的结论，可以为进一步的融合算法深入研究打好基础。

参考文献

[1]江迎春.改进的蚁群算法在TSP问题上的应用[D].中南民族大学，2009.

[2]冯月华.基于遗传算法的蚁群算法参数优化研究[J].贵阳学院学报：自然科学版，2014，（1）.

[3]马金财.基于蚁群算法的机器人路径规划问题研究[D].昆明理工大学，2014.

[4]王胜训.蚁群算法的改进及TSP仿真研究[D].西安电子科技大学，2014.

蚁群分析 篇4

意大利学者M. Dorigo等人从蚂蚁觅食行为中受到启发,于1991 年首次提出了蚁群算法。常见的蚁群算法模型有AS( ant system) 模型、ACS ( ant colony system) 模型、MMAS ( max-min ant system) 模型等[1]。目前蚁群算法已成功应用于多种优化问题,如车辆路径[2]、资源调配[3]、机器人路径规划[4,5]等。

虽然这种自适应人工智能技术在组合优化中应用较广泛,求解连续空间优化问题的蚁群算法尚缺乏理论基础,它将搜索周期模拟成个体的进化或觅食过程,将个体对环境的适应能力作为目标函数,总体上将个体的觅食过程或优胜劣汰过程抽象成用较好可行解取代较差可行解的迭代过程。目前主要有两种途径: 一是将连续空间离散化[6],从而使连续问题转化为离散问题,但该方法能否适用于高维优化问题还有待研究; 二是与其他算法融合[7,8,9],引入进化机制或某种算子弥补在连续域的适用缺陷,但收敛速度较慢。尤其应用于连续函数优化的蚁群算法其收敛性问题还需要探讨。因此,如何应用蚁群算法高效率实现连续空间优化问题求解将是一个很有意义的研究课题。

许多学者提出了用于求解连续空间优化问题的蚁群算法。文献[10]提出了一种基于密集非递阶的连续交互式蚁群算法,该算法通过信息素交流和直接通信的融合来指导蚂蚁寻优,却带来了收敛速度慢、评价代价高等缺点; 文献[11]提出TCACS并比较了多组测试函数的解精度,但仅仅引入了动态调整禁忌表; 文献[12]提出了MTACO( Modified Touring Ant Colony Optimization) 算法。以上这些研究取得了一定的成果,但如何提高全局搜索能力,提高收敛速度仍是有待解决的问题。在国内,大多是从仿真角度进行分析,没有对算法的收敛性进行分析。文献[13]将量子计算与蚁群算法相融合,提出一种连续量子蚁群算法。文献[14]提出了一种全新的由侦察蚁和觅食蚁协作搜索的快速连续蚁群算法。本文针对函数优化问题中的信息素分布方法、解的表示进行了研究,提出了一种蚁群分层搜索算法,相比传统算法中的信息素区间分布,本文基于分层结点的分布更合理。给出了算法的收敛性分析,仿真实验说明了本文算法全局搜索能力强,解的精度高且求解速度快。

1基于分层搜索的蚁群算法求解连续空间问题

设计连续空间蚁群算法,需要定义信息素分布函数、状态转移规则以及信息素更新策略。搜索空间本质上的连续性使得分布于路径上的信息素被区间淹没,蚁群分层搜索算法ACHSA( Ant Colony Hierarchical Search Algorithm) 是将连续域中的结点分成有等级的层,信息素也是依层结点进行分布,利用蚁群优化框架进行结点搜索。这些蚂蚁在其寄居点周围以分布函数的形式留存信息素,蚂蚁智能体根据这些结点上的信息素强度确定该结点的吸引力,从而选取其最终的转移结点。当蚁群搜索完各层后,根据当前解的函数值更新各层结点上的信息素强度。对于定义域E上的函数优化问题,要求解的精度为小数点后位,设计层结点。把E上的全体整数作为层结点,中间层上结点依次代表解的十分位,百分位,…,各层有10 个结点,依次编码为数字0 ~ 9。在一个搜索周期中,让蚂群往层数更大的结点上转移,而不能向层数减小的结点转移,随着层数的递增,蚁群的转移步长就会越来越小。这样通过层后形成的通路就代表一个解,并且开始进入下一个搜索周期,蚂蚁智能体根据各结点周围的信息素强度及路径的启发信息选择下一层结点。

1. 1 信息素分布函数

蚂蚁Ar到达第i层中代表十进制数j的结点时,会以分布函数( 1) 在以该结点为对称中心、长为的区间上释放信息素,信息素分布函数定义如下[15]:

其中: xr表示个体在解空间上的位置,f( xr) 是目标函数值,kr是形状尺度系数。本文中Ar留存在某结点周围的信息素强度用定积分式表示:

此值应该与时间t无关的。

1. 2 状态转移规则

我们采用确定性计算和随机性选择相结合的策略,蚂蚁Ar( r = 1,2,…,m) 选择第i层结点j的概率为:

其中q是区间( 0,1) 上的随机数,参数q0用来调节蚁群的探索能力( exploration) 和挖掘能力( exploitation) 的相对强弱,q0越大,蚁群的挖掘能力越强,反之,探索能力越强。

其中,prij( t) 表示第t次搜索时蚂蚁Ar转移到第i层结点j的状态转移概率。allowedi为10 × 10 矩阵是选择第i层结点的允许集合,τi,j( t) 为第t次搜索时第i层结点j上的信息素强度。以m ×( d + 1) 矩阵list记录蚁群当前走过的结点,用于求解xr( r = 1,2,…,m) 。

1. 3 信息素更新策略

1. 3. 1 局部更新

为避免残留信息素过多导致淹没启发信息,蚂蚁Ar每到达一个结点后,会释放信息素,在第i层结点j上释放的信息素强度用表示; 同时要蒸发,这样蚁群寻访新结点的机会增大,来挖掘未被蚁群达到的潜在解,选取系数kr保证老结点周围的信息素强度减小。假设在第t步转移中有s只蚂蚁经过该路径,记作都要留下相当的信息素,留在路径上的信息素总和为:

1. 3. 2 全局更新

当所有蚂蚁完成一次循环之后,会自适应地调整各结点上的信息素分布,来启发蚁群探索解的改进方向。将路径记录表映射到优化问题的解空间,计算对应点的函数值并选取最优值。所有结点周围残留信息素强度以 ρ2倍的速率蒸发掉,只有本次循环中最优路径的信息素得到补偿。

式中,Q是一个正常数,第n + 1 次循环中最优函数值f( n + 1) 对应路径 Γr*。

至此,蚁群返回L0层,根据上一周期中路径上信息素残留按照状态转移规则开始寻找下一层结点,如此循环,直到满足终止准则[16]:

参数取值 ε1= ε2= 10-4。

1. 4 算法描述

2 算法收敛性分析

本节在转移路径向量列的马氏性基础上证明函数最小值序列是非负下鞅,并从鞅过程的停止定理证明算法以概率1 收敛。

引理1 最优函数值序列{ f( n) ,n = 1,2,…} 是非负下鞅。

证明蚂蚁Ar的本次转移与蚁群在前一个搜索周期到达的状态有关,由信息素局部更新规则,第t + 1 步转移概率由前一步结点周围残留的信息素强度决定,决定了蚁群在n + 1 个循环中各步转移后的状态,即f( n + 1) 只与 Γ1( n) ,Γ2( n) ,…,Γm( n) 有关。

式中 Γ1( n) ,Γ2( n) ,…,Γm( n) 是第n个周期中蚁群的搜索通路,υjk是蚂蚁Ar所在结点位置,为避免信息素不断蒸发,而算法在某几个循环中还未改进解,信息素强度设置一个下限 τmin。

定理1最优函数值序列{ f( n) ,n = 1,2,…} 以概率1收敛。

证明蚁群首次发现最优解时即满足算法终止准则,迭代次数T是最优路径 Γ*( 1) ,Γ*( 2) ,…,Γ*( T) 的函数,T是关于下鞅{ f( n) ,n = 1,2,…} 的停时。

对于下鞅序列{ f( n) }n≥1,有Ef( n) ≤ Ef( T) ,n < T,记第T次搜索时由 υik转移到 υjk为( T-1)eikjk,

得到,由文献[17] 下鞅{ f( n) }n≥1以概率1 收敛于f( T) 。

3 仿真实验

为验证ACHSA的有效性,本文采用Matlab8. 2 实现了上述算法,用于求解典型函数式( 10) 、式( 11) ( 程序中把最小化问题变换为求最大值) 。对每个算例连续寻优50 次,记录每次所得最优解fopt,计算各项优化性能指标: 平均值、鲁棒性、优化成功率% ,其中fo*pt为测试函数的已知理论最优解,记录每次运行时间,采用平均时间衡量算法的时间性能。

两个算例中相同参数的设置如表1 所示,形状系数kr在信息素局部更新中有利于增加解的多样性。主要结果如表2 所示,两算例都可达到理论最优值,实验结果优于文献[18]中给出的最优值及鲁棒性,min g = 1. 3652,R = 3. 24% 。

本文算法求解式( 10) 的收敛曲线及找到的最优解位置分别如图1、图2 所示,最优解位置用* 号标识。算法的全局搜索性能较好,并且在150 代以内收敛。求解式( 11) 的收敛曲线及找到的最优解位置分别如图3、图4 所示,最优解位置用* 号标识,对比文献[18]中的收敛曲线,本文算法求解精度更高,收敛性能稍好。

4 结语

针对连续域优化问题,本文提出ACHSA,用分层结点模拟连续域中自变量的每位,以结点为对称中心的分布函数来表示信息素,并经过局部更新、全局更新合理地实现了迭代搜索过程,最终找到最优解。最后证明了最优函数值序列是非负下鞅并且算法以概率1 收敛,给出了算法参数的取值,仿真对比说明了本文算法的有效性,并且改善了传统蚁群算法的全局搜索性能。

摘要：针对蚁群算法容易陷入局部最优的问题,提出一种新的解决连续空间优化的蚁群分层搜索算法。该算法将蚁群搜索空间逐层分割,用信息素分布函数给出了基于分层结点的信息素分布方法。定义了适用于连续域的信息素局部更新、全局更新、状态转移规则,其中局部更新算子能够通过选取合适的参数来增加解的多样性。实验结果表明,相比传统算法,该算法全局搜索能力强,求解精度更高。该算法能达到连续域问题的理论最优值,通过下鞅的停时理论证明了算法以概率1收敛。

蚁群分析 篇5

在螞蚁、蜂等社会性昆虫的群体内，经常存在20%至30%的个体几乎不参加劳动。这种情形显然会降低短期的生产效率，但即便人为使一个蚁群只剩劳动的蚂蚁或只剩“懒汉”，过不了多久，蚁群中的“人手”分配就又会回到原有比例，这种现象一直是一个谜。

北海道大学研究生院副教授长谷川英祐率领的研究小组对两个蚁群进行了计算机模拟并比较。两个蚁群一个中存在不劳动的成员，另一个中所有的成员都劳动。

研究人员发现，在不存在疲劳的情况下，两个蚁群的存在时间没有差别，但如果存在疲劳，则有一部分蚂蚁不劳动的群体反而能长期延续。这是由于，当原来劳动的蚂蚁疲劳休息时，原来不劳动的蚂蚁就会开始劳动，从而确保整个蚁群一直有充足的劳动力，蚁群也因此能够长期延续。

这显示，社会性昆虫群体内长期存在不劳动的个体，看似降低了效率，实际上对于群体的长期延续是不可或缺的。

长谷川英祐表示，不仅是社会性昆虫，包括人类在内，过度追求短期效率有时反而会使组织遭受重大损失。因此在组织运营时，基于长期延续的观点来考虑问题非常重要。

（曹吉珍荐自新华网）

责编：我不是雨果

蚁群分析 篇6

聚类分析是根据“物以类聚,人以群分”这一现象[2],根据不同对象之间的差异和特定的准则做模式分类,而抽象发展起来的一种数学分析方法,是统计学的一个分支,也是无导师监督的机器学习方法,属于NP难问题。聚类分析是一种典型的组合优化问题。用蚁群算法解决聚类问题,可将数据库中的数据划分成具有一定意义的子类,使得不同子类中的数据尽可能不同,而同一子类中的数据尽可能相似。

1 聚类问题蚁群算法的基本思想

在基于蚁群算法的聚类分析中,将数据视为具有不同属性的蚂蚁,聚类中心看作是蚂蚁所要寻找的“食物源”。所以,数据聚类过程就看作是蚂蚁寻找食物源的过程。设X={Xi|X1=(xi1,xi2,…,xim)}是待进行聚类分析的数据集合。令:

dij表示Xi到Xj之间的加权欧氏距离,其中P为权因子,可以根据各分量在聚类中的贡献不同而设定。设r为聚类半径,ε为统计误差,τij(0)=0是t时刻数据Xi到数据Xi,路径上残留的信息量,设τij(0)=0,即在初始时刻各条路径上的信息量相等且为0。路径ij上的信息量由下式给出:

Xi是否归并到Xj由下式给出:

其中S={Xs|dsj≤r,s=1,2,…,j,j+1,…N},若pij(t)≥p0,则Xi归并到Xj邻域。

令Cj={Xk|dkj≤r,k=1,2,…,J},Cj表示所有归并到Xj邻域的数据集合。根据下式求出理想的聚类中心:

其中:Xk∈Cj。

2 相关信息和公式

根据蚁群算法的鲁棒性[5],结合动态K-均值聚类算法集,即避免了K-均值事先确定分类个数以及模板的初值的缺陷,又得出合理归类的最短路径。

2.1 欧氏距离

任一样本i可以看成是m维空间中的一个点,用向量Xi=(x1i,x2i,…xm)表示,任两个样品Xi与Xj之间的欧氏距离[3]为:

2.2 相关概率

对于样本库中的各个样品向量,令平均矩为定义xi与xj两向量的相关概率为:其中n+={xki与xkj取相同号的个数}

n-={xki与xkj取相反号的个数}。

2.3 K-均值算法

K-均值算法的步骤如下:

(1)任选K个初始聚类中心Z1,Z2……Zk。

(2)逐个将样本集{X}中各个样本按最小距离原则分配给个聚类中心的某一个Zj。

(3)计算新的聚类中zj(j=l,2,□,K),即,其中Nj为第j个聚类域Sj包含的个数。

(4)若Zj≠Zj(j=l,2,□,K),转步(2);否则算法收敛,计算结束。

2.4 路径中各路段上信息素增量的自适应调整

在基本蚁群算法的信息素增量分配中,对同一路径的不同路段分配相同大小的信息素增量,而路段影响蚁群向最佳路径搜索的作用显然不同。因此,合理的策略应为:(1)对于较好的路段,分配较大的信息素增量;(2)对较差路段分配较小的信息素增量。这样既可以保留上次搜索得到的有效信息,在较好区域进一步进行更精细的搜索,加快算法的收敛;又可以保证大范围搜索的有效性,使算法能找到全局最佳路径。具体方法为:设路段(i,j)在第t个搜索周期中在各搜索路径上出现的总次数为k(0≤k≤n),则路段(i,j)上的信息素增量[4]为:

3 改进蚁群算法的动态K-均值聚类算法流程

该算法流程如下:

(1)设样本集为:X={Xi,i=1,2,…,n},在样本空间中,计算样本间的欧式距离,把距离从小到大排列,距离较大和较小的样本交叉选取K个样本作为初始聚类点,用(C1,C2,…Cj)表示,K为初始聚类点个数,K

(2)建立K个蚂蚁种群:M1,M2,…,Mk确定每个种群蚂蚁的个数L(n/k≤L≤n)。

(3)对所有蚂蚁走过的路径采用均匀分配信息素增量的方法,所有路段上的信息素进行初始化,确定τi,j(t)=1/M(M为路段总数)。

(4)种群M1,M2,…,Mk分别以聚类中心Z1p,Z2p,…,Zkp为出发点,在整个样本空间并行进行蚁群搜索T个周期(2≤T≤5)。

(5)取种群Mj。在T周期末搜索到的最好路径所包含的样本点Ii,预归入类Cj。计算相关概率pij,如果pij>0.9,则把样本点Ii归入该类Cj,否则自成一新类,聚类个数class-number增加一个。

(6)一个类有新样本点Ii增加,按K均值算法计算新的聚类中心,返回step2,如有新类产生,增加蚂蚁种群,返回step3。计算J(p)。

(7)在第一次归类基础上,结合初始类群,根据以上原则进行再次归类。直至把所有样本归入不同的类中,|J(p)-J(p-1)|<ε(给定精度ε>0),则算法终止。

4 结束语

蚁群算法是一种基于种群的进化算法,易于并行实现,也易于与其他方法相结合,具有较强的鲁棒形。基于蚁群算法的动态K-均值算法,综合蚁群算法和K-均值算法的长处,使得算法能够动态的分类,不限制在固定的类上,从而更加健壮。随着不断深入研究将会出现更多令人惊喜的成果,将两者的最新结论结合起来应用于实际问题将是研究的重要方向。

参考文献

[1]Dorigo M,Maniezzo V,Colorni A.Ant system:Optimization by a colony of cooperative Agents[J].IEEE Transactions on Systems,Man,and Cybernetics,1996,26.

[2]Jiawei Han,Micheline Kamber.Data mining:concepts and tech-niques[M].北京:高等教育出版社,2000.

[3]张白妮.动态的聚类算法在图像检索中的应用[J].计算机工程与设计,2004(10).

蚁群分析 篇7

关键词：蚁群算法,碾压混凝土坝

碾压混凝土坝是将常态混凝土坝和填筑土石坝的优点集中于一体的坝型, 是近几十年来常见的一种新坝型。它综合了混凝土坝和土石坝施工的特点, 有节约水泥用量、简化施工工艺、施工速度快和工程造价低等许多优点, 因此发展的速度比较快。这种新型的筑坝技术已经从试验阶段发展到了实际的应用阶段, 并被各国广泛采用。

由于碾压混凝土坝不同于一般混凝土坝的施工方式, 以及由此产生的结构复杂性, 使得碾压混凝土坝的结构模型难以确定, 坝体的计算参数难以得到, 这就使得在计算时难以与工程实际相吻合。大坝的计算参数通过正分析直接计算有一定的难度, 计算的过程也十分复杂。

1 蚁群算法在碾压混凝土坝参数反演中应用

蚁群算法在参数反演中, 需要将待反演的参数进行离散化处理, 从而对参数进行反分析优化[1,2]。碾压混凝土坝参数反演的模型如下:将待反演的n个参数比作n个城市, 假设系统中有m只蚂蚁, 第i个反演参数用第i个城市来代表;用ki来表示从第i个城市到第i+1个城市之间的路径数, 表示第i个反演参数的取值可能在ki个不同的子区间;用τij (t) 记录第i城市的第j条路径上在t时刻的信息量;每只蚂蚁都要从第1个城市出发, 最后到达最后一个城市。在从第i个城市到第i+1个城市时, 需要按照一定的策略选择;算法的目的是找到一条最短的路径, 这样一条路径是不重复的贯穿了每个城市;最后, 可以求到使得所求目标函数值最小的一组反演参数。

碾压混凝土坝参数基于蚁群算法反演的具体步骤如下:

1) 对反演参数进行离散化处理:将待反演的参数i的取值区间进行ki等份, 因此, 待反演参数的取值区间被离散化成了有限个数的离散子区间, 待反演参数的组合一共有 种情况, 即有A条路径到达终点, 其中n为待反演参数的个数。

2) 参数反演的初始化过程:让m只蚂蚁随机选择一条路径到达终点, 即选择一组待反演的参数, 目标函数值由所选择的这m组反演参数计算获得。然后, 主要是对各条路径 (即反演参数的子区间上) 的信息量τij (t) 进行计算, 前提是先由初始的各个参数计算出其所对应的子区间。所选子区间信息量τij (t) 可以由式1) 计算得出, 碾压混凝土坝参数反演的目标是找到使目标函数获得最小值的一组参数。则可以, 目标函数值的大小来确定衡量一条路径的长短。目标函数的值越小, 信息量越大, 路径的长度越短;反之, 信息量越小。

在某次循环中, 蚂蚁k选择路径的长度Lk表示为:

3) 待反演参数的循环迭代过程:令t=t+1, 根据蚂蚁上次在子区间留下的信息量, 计算上次循环中所有蚂蚁在待反演参数选择子区间的概率, 让m只蚂蚁重新回到第一个城市。进行循环迭代, 当到达终点时, 计算目标函数的值, 对各子区间的信息量τij (t) 进行更新。

当m只蚂蚁得到m个解后, 本文利用选择路径的总长度Lk作为评估解的优劣程度, 重复迭代过程, 直到满足精度的一定要求或者迭代达到一定的步骤时, 目标函数值的循环结束。

2 工程实例

某水电站大坝为整体式碾压混凝土重力坝, 坝顶高程为185m, 坝顶长度为176m。最大坝高为68m, 坝顶宽为8m。溢流坝布置在河道中部, 两岸是挡水的坝段。

上游坝面处于直立状态, 下游坝坡为1∶0.65。水库设计的坝前正常库水位为143.00m, 校核洪水位144.17m。

结合某碾压混凝土大坝的实际情况, 利用坝顶位移测点2006年1月1日到2008年12月31日的位移测值, 作为反演分析时的资料系列。然后, 根据水平位移测点的测值, 建立了水平位移的统计模型, :分离出不同时刻的组成一个变形值序列, 然后以该变形序列作为目标值进行反演。

各待反演参数取值范围如下:

根据上述待反演参数进行离散化处理:将Ev1、El1在15.0~35.0内, 平均分成20等份, 每等份为1000MPa;Ev2、El2在15.0~95.0GPa内, 平均分成80等份, 每等份为1000MPa;ηv2、ηl2在106~108GPa·s内平均分成40等份, 每等份2.5GPa·s。其他参数根据经验设定:蚁群规模N=50, 常数Q=60, 系数ρ=0.7, 最大的迭代次数是800次。将所有的参数带入改进的蚁群算法进行反演优化分析。

经过反演分析, 最后得出:

将碾压混凝土坝粘弹性参数的反演结果作为已知值, 利用反演结果带入计算时间段的测点变形, 所计算的结果与实际的测值进行比较, 分析反演结果的好坏。

3 结论

经过表中实测值与计算值的比较分析可以得出, 实测值与计算的结果还是比较接近的, 这说明了参数反演结果比较可靠。

参考文献

[1]杨剑峰.蚁群算法及其应用研究[D].浙江大学博士论文, 2007.

蚁群分析 篇8

关键词：数据挖掘,网状图,蚁群算法

一、引言

购物篮,指的是超级市场内供顾客购买商品时所使用的篮子或小推车,当顾客付款时这些购物篮内的商品被营业人员通过收款机一一登记结算并记录。市场购物篮分析就是通过这些购物篮子所显示的信息来研究顾客的购买行为。消费者的购物篮里隐含着重要且十分有价值的信息,通过对这些信息的研究与分析,我们就可以获得有关消费者的一些资料,如他们的购买习惯、产品偏好、品牌忠诚度等。

在本文中,我们利用购物篮分析技术对通过“会员卡”制度所获得的顾客数据进行最佳路线设计分析,从而帮助零售商做出选择性销售和安排货架中商品的摆放方式,从而促进销售量。我们将通过以下两个阶段来对案例进行分析研究:(1)构建揭示所购买商品之间频繁集关系的网状图。(2)使用蚁群算法进行最佳购物路线的分析设计。

二、网状图与蚁群算法

在零售业中,网状图可以发现顾客购物的频繁程度,而蚁群算法则可以根据顾客的购物流量进行商品最佳摆放,从而提高顾客购物的效率和流量。网状图由节点和节点连线组成。每个节点对应一个分类型变量,连线代表两个分类型变量不同类别值的组合。

1. 网状图

网状图是一种生动和直观地展示两个或多个分类型变量(尤其适合多分类型变量)相关特征的图形。图形由节点和节点连线组成。

在购物篮分析中,网状图可以反映商品购买的频繁程度。这可以用频繁模式来表示。

频繁模式是频繁地出现在数据集中的模式。频繁模式挖掘就是搜索给定数据集中反复出现的联系。而频繁地同时出现在交易数据集中的商品的集合就是频繁项集。频繁项集导致发现大型事务或关系数据集中项之间有趣的关联或相关性。因此,挖掘关联规则的问题可以归结为挖掘频繁项集。

2. 蚁群算法

蚁群算法(ant colony optimization,ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的概率型算法。它是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法,由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚁群算法的原理是:蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递,蚂蚁在运动过程中能够感知这种物质,并以此指导自己的运动方向,因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。

基本的ACO模型由下面3个公式描述[1]:

式(1)、式(2)和式(3)中:m为蚂蚁个数;n为迭代次数;i为蚂蚁所在位置;j为蚂蚁可以到达的位置;Λ为蚂蚁可以到达位置的集合;ηij为启发性信息,这里为由i到j的路径的能见度,即ηij=1/dij;Lk为目标函数,这里为两点间欧氏(Euclidean)距离;τij为由i到j的路径的信息素强度;Δτkij为蚂蚁k由i到j的路径上留下的信息素数量;α为路径权;β为启发性信息的权;ρ为路径上信息素数量的蒸发系数;Q为信息素质量系数;pkij为蚂蚁k从位置i移动到位置j的转移概率。

三、实例分析

在这里,我们用SPSS Clementine12.0自身所带的数据文件BASKETS1n.txt进行商品最佳摆放的数据挖掘分析。其中,数据表中的每一条记录表示一个“购物篮”,也就是说记录了某位客户某次的购物情况。数据集中共包含了18个字段,1000条记录,各字段说明如表1所示。

首先,借助于Web图,恰当地设计Link size varies con tinuously和图下方的滑块,可显示出强弱不同的连接线。如图1所示。

为了得到更准确的数据,可点击Show web output sum mary and controls按钮,则可显示出详细的数据表格。我们再对数据进行处理,则可产生以下对称矩阵的数据表格。如表2所示。

将以上数据输入Matlab程序中,使用蚁群算法,则运行可得到如下结果:

最短距离:0.26379

最短路径:3 9 2 5 7 6 4 10 1 8 11 3

程序执行时间:1.047秒

相应的购物最优化路径和算法收敛轨迹分别如图2所示:

由图2分析可知,这里的11个节点表示11种商品,节点与节点之间的距离越短,表示商品被联带购买的频繁度越大,商品之间的关联性就越强。从图3中可以看出节点7、6和4之间的距离较短,这说明beer、frozenmeal和cannedveg这三种商品频繁购买的频率较大,可以摆放在一起;同样的,节点8和11之间的距离也较短,这说明confectionery和wine这两种商品频繁购买的频率较大,也可以摆放在一起;而节点3和9之间的距离虽然没有前面两种组合的距离短,但也是人们日常的营养品和偏好品,故dairy和softdrink也可以摆放在一起。

此外,在商品货架的摆放上,可以将dairy和softdrink这两种商品,以及把beer、frozenmeal和cannedveg这三种商品摆放在超市的入口处和出口处,这可以方便那些需要快速购买的顾客,因为dairy和softdrink这两种商品的消费者主要针对于儿童和青年,而beer、frozenmeal和cannedveg这三种商品的消费者主要是针对于男性和工作节奏快,工作时间长的上班族,因为他们没有太多的时间和精力进行饮食制作过程的前期工作处理(如食品的清洗)。

最后,我们再改进图1的网状图,恰当地设计Link size varies continuously和图下方的滑块,可显示出强弱不同的连接线。如图3所示。我们可以看到,有三组商品组合所属的客户群特别明显,它们分别是:(1)购买beer、frozenmeal和cannedveg组合的客户群;(2)购买confectionery和wine组合的客户群;(3)购买fish和fruitveg组合的客户群。其中,购买fish和fruitveg组合的客户群在蚁群算法的购物最优化路径中的节点相距较远,这说明这类客户群注重健康饮食和生活品质,他们更愿意花费一定的时间和精力在商品的精挑细选上,从而提高自己的生活质量。

四、小结

在零售业领域,商品摆放的位置对产品关联销售会产生很大的影响的,为了更方便地让顾客找到其需要的产品,设计出商品摆放的最佳位置,以方便顾客购买其需要的商品,使用蚁群算法进行商品摆放路线的设计无疑是一种较好的方法。当然,我们会发现不少的这样规则:人流比较大的两个相隔货架之间的商品关联性比较大,而在进行关联分析的时候,客户更希望能从其他不相隔的货架之间找出更好的关联销售机会,这对我们后期的分析研究也提出了新的挑战。

参考文献

[1]吴庆洪,张颖,马宗民.蚁群算法综述[J].微计算机信息,2011,(27)3.

[2]薛薇,陈欢歌.基于Clementine的数据挖掘[J].2012,(2).

[3]龚勇龙.基于关联规则的多样化推荐技术应用研究[D].暨南大学,2012.9.

蚁群算法及其应用研究 篇9

关键词：蚁群算法,优化问题,应用研究

1 蚁群算法的基本原理

真实的蚂蚁有能力在没有任何可见提示下找出从蚁穴到食物源的最短路径, 并能随环境的变化而变化搜索出新的路径, 产生新的选择, 蚁群算法也是通过模拟真实蚁群的这一特征进行工作的。

1.1 蚂蚁的觅食行为

像蚂蚁这类群居昆虫, 虽然没有视觉, 却能找到从蚁穴到食物源的最短路径。单只蚂蚁的行为及其简单, 在蚁群觅食的过程中释放信息素, 通过对路径上信息素强度的感知来选择所要行进的方向, 并传递信息。当遇到新的障碍物时, 信息素轨迹会被障碍物暂时性阻断, 蚂蚁会随机地选择下一步的方向, 重新构建起新的连续的信息素路径。随着时间的推移, 选择短路径的蚂蚁越来越多, 留下的信息素浓度也会加强, 从而使后继的蚂蚁以较大的概率选择短路径。他们这种自催化过程形成的信息正反馈机制使得他们可以找到新的最短路径。

1.2 蚁群算法的基本原理

蚁群算法是受到真实蚁群集体行为的启发而得到的新型优化算法, 人工蚂蚁和真实蚂蚁存在异同。人工蚂蚁和真蚂蚁的蚂蚁一样, 是一群相互合作的个体并且他们有着共同的任务, 他们都是通过使用信息素进行间接通讯, 而且人工蚂蚁利用了真实蚂蚁觅食行为中的自催化机制。但人工蚁群也存在真蚂蚁所不具有的一些特性, 蚁群这种记忆并非存储于蚂蚁个体, 而是分布在路径上。人工蚂蚁实质上是由一个离散状态到另一个离散状态的跃迁。信息素的释放时间是根据不同情况而改变的。为了提高系统总体上的性能, 蚁群被赋予了其他的功能, 如局部优化、原路返回等。

蚁群算法最初是应用在对称的旅行商问题, 下面对求解旅行商问题进行简单的说明。

旅行商问题就是指给定n个城市, 并给出两两城市间的距离, 要求确定一条经过各城市最短的路径。蚂蚁根据城市的距离和连接边上信息素浓度为变量的概率函数选择下一城市。为了满足问题的约束条件, 在完成一次循环前, 不允许蚂蚁选择已经访问过的城市, 需要由禁忌表控制。完成循环后, 路径上都会留下浓度不同的信息素, 我们可以通过对信息素浓度的强度, 选择出最短路径。

算法的基本流程图如图1所示。

初始时刻, 各条路径上的信息素量相等, 设τij (0) =C (C为常数) 。蚂蚁k (1, 2, …m) 在运动过程中根据各条路径上的信息素决定转移方向。蚂蚁系统所使用的状态转移规则被称为随机比例规则, 它给出了位于城市i的蚂蚁k选择移动到城市j的概率。在t时刻, 蚂蚁k在城市i选择城市j的转移概率Pkij (t) 为:

其中τij表示为边 (i, j) 上的信息素轨迹强度;ηij表示为边 (i, j) 的能见度, 反映由城市i转移到城市j的启发程度, 这个量在蚂蚁系统的运行过程中不改变。蚁群算法中只有那些属于最短路径上的边的信息素才被得到增强。这种规则和伪随机比例规则的使用都是为了让算法的寻优过程更具有指导性, 最短路径的寻找始终是在当前找到的最短路径的附近进行。在所有的蚂蚁遍历完n个城市之后, 各路径上信息素量根据式 (2) 进行更新。

△τij (t, t+1) 表示第k只蚂蚁在时刻 (t, t+1) 留在 (i, j) 上的信息素的量, 它的值根据蚂蚁表现的优劣程度而定。路径越短, 信息素释放的就越多。根据具体算法的不同, 表达式也可以不同, 要根据具体问题选择不同的表达形式。蚁密和蚁量系统模型仅在于的不同。在蚁密系统模型中, 一只蚂蚁在经过路径 (i, j) 上释放的信息素量为每单位长度Q, 在蚁量模型中, 蚂蚁在经过路径上释放的信息素量为每单位长度Q/dij。而在蚁周模型中, 与上述两种模型的△τkij表达式不同, △τkij (t, t+n) 表示更新蚂蚁k所走的路径, (t, t+n) 表示蚂蚁经过n步完成一次循环, 具体的更新值由式 (3) 所示:

蚂蚁k在本次循环中经过路径 (i, j) 否则在蚁密和蚁量系统中, 蚂蚁建立方案的同时释放信息素, 是局部的更新。而在蚁周系统中, 是在蚂蚁已经完全建立了轨迹后再释放信息素, 是利用了整体的信息。根据一系列标准测试问题上运行的实验表明, 蚁周算法的性能优于其他两种算法。因此, 蚁周算法模型往往被称为蚂蚁系统, 另外两种模型不被使用。

2 改进的蚁群优化算法

近年来, 蚁群优化算法研究主要集中在改善蚁群算法的性能方面。改进的方法主要是在搜索控制的具体方面不同, 但这些算法都是基于蚂蚁找出最优解来指导蚂蚁搜索的过程。

(1) 带精英策略的蚂蚁系统 (Ant System with elitist strategy) 是最早的改进蚂蚁系统。在这个系统中, 为了使到目前所找出的最优解在下一循环中对蚂蚁更有吸引力, 在每次循环之后给予最优解以额外的信息素量, 这样的解被称为全局最优解, 找出这个解的蚂蚁被称为精英蚂蚁。但是该系统存在缺点, 若在进化过程中, 解的总质量提高了, 解元素之间的差异减小了, 将导致选择概率的差异也随之减小, 使得搜索过程不会集中到所找出的最优解附近, 阻止了对更优解的进一步搜索。

(2) 基于优化排序的蚂蚁系统 (Rank-Based Bersion of Ant System) :将遗传算法中排序的概念扩展应用到蚂蚁系统中, 当每只蚂蚁都生成一条路径后, 蚂蚁按路径长度排序, 蚂蚁对激素轨迹量更新的贡献根据该蚂蚁的排名进行加权。只考虑w只最好的蚂蚁, 而且要以有效避免上述的某些局部极优路径被很多蚂蚁过分重视的情况发生。

(3) 最大—最小蚂蚁系统 (Max-Min Ant System) 与蚁群系统相似, 为了充分利用循环最优解和到目前为止找出的最优解, 在每次循环之后, 只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁, 也可能是找出从实验开始以来最优解的蚂蚁。而在蚂蚁系统中, 对所有蚂蚁走过的路径都进行信息素更新。为了避免搜索的停滞, 把每个解的元素上的信息素轨迹量的值域范围限制在[Min, Max]区间内。在蚂蚁系统中的信息素轨迹量不被限制, 使得一些路径上的轨迹量远高于其他边, 蚂蚁都沿着同条路径移动, 组织了进一步搜索更优解的行为。

(4) 最优-最差蚂蚁系统 (Best-Worst Ant System) 。该算法在蚁群算法的基础上进一步增强了搜索过程的指导性, 使得蚂蚁的搜索更集中于当前所找出的最好路径的领域内。蚁群算法的任务就是引导问题的解向着全局最优的方向不断进化。该算法的思想就是对最优解进行更大限度的增强, 而对最差解进行削弱, 使得属于最优路径的边与属于最差路径的边之间的信息量差异进一步增大, 从而使蚂蚁的搜索行为更集中于最优解的附近。

蚁群算法还可以与其他智能优化算法相融合, 取长补短, 改进和完善算法的性能。目前蚁群算法可以与遗传算法、粒子群算法等进行融合, 更有效的解决一些问题。

3 蚁群算法在优化问题中的应用

蚁群算法最初被用经典的组合优化问题, 随着研究的深入, 应用范围不断扩大, 现在应用到静态组合优化问题、动态组合优化问题、连续空间优化问题、以及其他领域。下面分别介绍了在不同领域中的应用:

3.1 在静态组合优化中的应用

蚁群算法最先应用于旅行商问题 (TSP) 问题, 它是组合优化中研究最多的NP问题之一, 该问题主要是在n个城市中, 必须访问每个城市且每个城市只能访问一次, 最后回到起始城市, 寻找最短路径。目前, 求解TSP问题的方法有很多, 穷举搜索法、最近邻算法、插入算法等, 也有其他优化算法, 例如:模拟退火算法、遗传算法、神经网络算法、禁忌算法等。许多研究表明, 应用群算优化算法求解TSP问题要优于其他的方法。

二次分配问题 (QAP) 指的是分配n个设备给n个地点使得分配代价最小。事实上, QAP问题是一般化的TSP问题。

车间任务调度问题 (JSP) 指的是一组M台机器和一组T个任务, 任务有一组制定的将在这些机器上执行的操作序列组成。

还有许多问题, 像车辆路线问题 (VRP) 、图着色问题 (GCP) 、有序排列问题 (SOP) 、最短的公共父序列问题 (SCS) 等。

3.2 在动态组合优化中的应用

在动态组合优化问题中, 问题的解是随时间而变化的。蚁群算法在解决动态组合优化问题中主要是通信网络。在国际上Schoonderwerd等人首先将蚁群算法应用于路由问题, White等人将蚁群算法运用在单对单点和单对多点的有向连接的网络路由中, 而Dicarogy等人基于蚁群算法设计了自适应的路由算法。在国内, 开展了基于蚁群算法的Qo S路由调度方法的研究。

4 结束语

蚁群算法问世至今已有十多年的时间, 其理论和应用都有了很大的进步, 蚁群算法从最初求解旅行商问题开始, 已经逐步发展为一个优化工具, 并且较为成功地应用到科学和工程中的多个领域。众多研究已经证明, 蚁群算法具有很强的发现较好解的能力, 因为该算法不仅利用了正反馈原理, 而且是一种本质并行的算法, 不同个体之间不断进行信息交流和传递, 从而能够相互协作。蚁群算法相对于各种比较成熟的计算智能方法来说, 它的数学离了基础相对薄弱, 缺乏具备普遍意义的理论性分析。算法中涉及的各种参数设置也没有确切的理论依据, 通常都是通过经验来确定。因此, 蚁群算法还有许多问题需要解决, 它的应用也有待进一步的发掘。

蚁群算法还有许多要研究的地方, 主要是: (1) 进一步的研究算法收敛性的分析, 得出更强的收敛性证明并得出收敛速度将会加速算法的发展; (2) 蚁群算法的理论性分析和参数的设置; (3) 蚁群算法的应用领域的扩展, 应用较多的是静态组合优化问题, 改进并将其应用于动态组合优化问题和连续优化问题是值得探索的。

参考文献

[1]DORIGO M, GAMBARDELLA L M.Ant colony system:a coopera-tive learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation, 1997 (1) .

[2]DORIGO M, MANIEZZO V, COLORNI A.Ant system:optimization by a colon of cooperating agents.IEEE Transactions on Systems, Man and Cybernetics, PartB, 1996 (1) .

[3]COLORM A, DORIGO M, MANIEZZO V.Distributed optimization by ant colonies[C].Proc of the First European conf.On Artificial Life, Paris, France Elsevier Publishing, 1991.

[4]李士勇.蚁群优化算法及其应用研究进展[J].计算机测量与控制, 2003 (12) .

[5]温文波, 杜维.蚁群算法综述[J].石油化工自动化, 2002 (1) .

[6]姜长园.蚁群算法的理论及应用[J].计算机时代, 2004 (6) .

基于元胞蚁群算法的网络生存性研究 篇10

摘 要：针对通信网络因链路失效而产生的网络拥塞问题，基于元胞蚁群算法提出了一种新的网络生存性评价方法SACA（Survivability Algorithm based on Cellular Ant）。该方法首先给出了网络生存性定义，并且通过元胞蚁群算法设计了生存性算法流程，以此获得网络剩余数据传输量。同时，利用NS2和MATLAB进行仿真实验，结果表明，相比于其它算法，SACA算法具有出较好的适应性。

关键词：生存性；剩余能量；失效；元胞蚁群

中图分类号：G642 文献标识码：B 文章编号：1002-7661（2014）09-285-02

目前，如何提高网络安全性成为网络的研究重点和研究热点。网络生存性已经成为影响其性能的关键问题[1]。网络生存性主要是指网络在遭遇外部攻击或自身故障等异常情况下，仍然能够及时维持可接受的业务质量的能力。为了有效评价并解决这一问题，国内外学者开展大量研究工作。2000年，Albert等[2]首先研究了不同度分布下复杂网络的有效性。Paolo Crucitti等[3]利用度和介概念提出了关键节点和链路评估模型，并讨论了不同状态下的网络生存能力。但是这些优化思想并没有从网络模型和网络状态进行深入分析，所以对于从本质上解决网络抗毁性的作用有限。皇甫伟等[4]定义了网络生存性指标，并基于灾害条件对具有SDH自愈环拓扑结构的网络生存性进行了定量分析。包学才等[5]针对全连通网络定义了不相交路径抗毁性评估模型，研究了全连通网络节点间不相交路径数的比重，从而能够定量计算通信网络的抗毁性。Wang Jianwei等[6]提出了基于局部负荷分配策略的级联失效模型，并且发现在某些条件下攻击低度节点对网络的破坏程度反而大于高度的节点。

针对上述问题，本文首先给出了网络生存性定义，并且利用元胞蚁群算法来计算剩余数据传输量[7-8]，进而获得当前网络生存性。同时通过NS2和MATAB进行仿真实验，深入研究了影响该方法的关键因素。

1、网络生存性定义

假设存在网络G（V， W， F）中，V代表节点集合（V=[1， 2， …， n]），W代表链路权重集合，F表示网络中任意两点之间的流量集合，假设网络中各节点位置具有随机性，并且节点的性质相同（如数据转发能力，缓冲大小等），这里将各节点出现失效的情况归纳为对应链路出现失效，同时假设各链路出现失效的概率相等。令网络中存在n段链路，正常情况下整个网络数据传输量为f，有k条链路失效时网络剩余流量为f（k）。那么，网络生存性则可以定义为：

（1）

其中：

（2）

在上述定义中，关键在于求解网络剩余流量f（k）。本文结合元胞自动机和蚁群智能算法对f（k）进行研究，将定义的元胞演化规则替换变异和交叉操作，以达到快速收敛的目的，同时降低了算法的运算量。

2、元胞蚁群算法

元胞自动机是一种时间和空间离散、可扩散的、状态有限的多维系统，普遍应用于非线性科学领域。

本文采用Moore型元胞结构，如图1所示，在下一时刻蚂蚁按照概率p选择周围8个元胞和自身中的最优状态进行转移：

（3）

其中，ξ和ζ为非负常数，λi为蚂蚁i为中心r为半径的邻域内的单位面积内的节点分布，Δλ表示两相临邻域内的节点分布差，yi为每个蚂蚁对应的状态函数，Δyij=yi-yj，并且状态函数yi为定义为：

（4）

同时这里定义如下元胞演化规则：

（a） 选择任意一个元胞i，通过计算临域内各yi值，记录其中最优值yopt=yi。

（b） 在临域半径r内任意选取元胞i和j，并计算相应的yi和yj；如果yi

这里利用元胞蚁群给出上述数学模型的求解算法（Botnet Detecting algorithm based on Cellular Ant，BDCA）：

1、在开始时刻T，初始化网络拓扑结构，网络剩余数据传输量f（k）、元胞蚁群规模为M，并确定元胞蚁群的转移概率p和搜索区域半径r，最大迭代阈值MAX；

2、确定蚂蚁的搜索区域及搜索中心位置Oi：

（13）

其中，xmax和xmin为搜索区域上下边界，rand（）产生（0， 1）之间的随机数；

3、在Oi为中心、r为搜索半径的区域内，蚂蚁i搜索是否存在比当前状态函数yi更优的元胞；如果存在则按照概率p进行移动，如果移动成功，则丢弃当前中心区域Oi，重新计算当前蚂蚁i的目标函数值，以及当前最优解，同时更新方程修改轨迹强度；

4、重复上述步骤（3），完成所有蚂蚁的更新操作；

5、令T=T+1，跳转到步骤（2）继续执行，直至Δλ趋于0或者跌代次数超过阈值MAX时停止；

6、输出当前的最优解，即为稳定状态下最优的网络剩余数据传输量f（k）；

算法结束。

本文针对网络生存性提出了一种新的刻画方法SACA。该方法首先根据网络剩余数据传输能力给出了网络生存性指标，通过定义元胞演化规则并结合蚁群算法，将网络节点集合看作蚁群，使得在网络失效的情况下能够快速收敛，从而获得全局最优。最后，本文将提出的SACA算法与SAICSA 算法、ASATS算法进行仿真实验，结果发现该算法具有较好的适应性。同时在今后的研究中，可以考虑联系网络有效性和抗毁性进行动态建模，以此形成较为完善的评价体系结构。

参考文献：

[1] Lazarou G Y， Baca Julie， Frostv S， Evans J B. Describing network traffic using the index of variability[J]. IEEE /ACM Transactions on Networking， 2009， 17 （5）： 1672-1683.

[2] Albert R， Jeong H， Barabasi A L. Error and attack tolerance of complex networks [J]. Nature， 2000， 406： 378-382.

[3] Crucitti P， Latora V， Marchiori M， Rapisarda A. Error and attack tolerance of complex networks [J]. Physica A， 2004， 340（1）： 388-394.

[4] 皇甫伟， 容鹏， 曾烈光. SDH 自愈环生存性定量分析[J]. 电子学报， 2001， 29（11）： 1558-1560.

[5] 包学才， 戴伏生， 韩卫占. 基于拓扑的不相交路径抗毁性评估方法[J]. 系统工程与电子技术， 2012， 34（1）： 168-174.

[6] Wang Jianwei， Rong Lili. Cascade-based attack vulnerability on the US power grid[J]. Safety Science， 2009， 47（10）： 1332-1336.

[7] 曹春红，王利民，赵大哲. 基于离散元胞蚂蚁算法的几何约束求解技术研究[J].电子学报，2011，38（5）：1127.