蚁群系统算法

蚁群系统算法（通用7篇）

蚁群系统算法 篇1

随着高速率通信需求的快速增长, 正交频分多址技术 (Orthogonal Frequency Division Multiple Access, OFDMA) 已经成为下一代无线通信系统中具有前景的技术之一。因为载波是正交的, 系统能够通过信道增益将载波自适应地分配给用户。能够有效利用多用户的多样性来增强系统性能。另外, 其可避免由多径效应引起的符号间干扰。所以, OFDMA成为了无线通信的关键技术。

OFDMA系统中, 资源分配问题是分配载波、比特率和功率给不同用户。根据不同的优化目的, OFDMA系统的资源分配问题分为两类[1]: (1) 边际问题。目标是根据每个用户的数据速率和误码率最小化总传输功率。 (2) 速率自适应。目标是根据基站总传输功率的制约最大化系统容量, 文中介绍了边际问题的问题规划, 从而结合蚁群算法实现呼叫接纳控制。

1 系统模型和问题规划

本文考虑到的OFDMA系统模型如图1所示。假设系统中有N个载波和K个用户。用户k的一个OFDM码元的数据速率是Rk (k=1, 2, …, K) 。假设, 基站通过反馈信道获得及时、完整的为了所有下行链路传输的信道信息。另外, 假设在传输过程中所有载波不变。

为了描述优化问题, 定义了如下的概念:σk, n为载波分配指示;σk, n=1表示第n个载波分配给了第k个用户, 否则, σk, n=0;hk, n为第k个用户载波n的信道增益;pk, n为分配给第k个用户的第n个载波的传输功率;ck, n为每个码元中, 第k个用户的第n个载波能够传输的比特数。

pk, n与ck, n的关系可以表示为

其中, fk (ck, n) 表示可靠地接受每个码元ck, n个比特的单位信道增益所需的接收功率。

通过文献[1], 可以将非线性规划问题转化为整数规划问题。定义xk, n, c为指示变量;xk, n, c表示第n个载波分配给了第k个用户且能被第n个载波传输的比特数是c;pk, n, c表示为了传输c比特数据, 分配给第k个用户的第n个载波的传输功率

其中, ck, n∈{1, 2, …, C}是一组代表每个载波的调制方法的非负整数值。对于每个用户来说, f (ck, n) ∈{fk (1) , fk (2) , …, fk (C) }

在这个整数规划问题中有K×N×C个整数变量和K个约束条件。通过解决这个整数规划问题, 可以得到最佳结果。但计算的复杂度会随着变量和约束条件指数增长。

2 蚁群算法

2.1 蚁群算法介绍

蚁群算法, 又称蚂蚁算法, 是一种用于在图中寻找优化路径的机率型算法。各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后, 其会向环境释放一种挥发性分泌物———信息素 (该物质随着时间的推移会逐渐挥发消失, 信息素浓度的大小表征路径的远近) 来实现, 吸引其他的蚂蚁过来, 这样越来越多的蚂蚁会找到食物。有些蚂蚁并没有象其它蚂蚁一样总重复同样的路, 他们会另辟蹊径, 如果另开辟的道路比原来的道路更短, 那么, 渐渐地, 更多的蚂蚁会被吸引到这条较短的路上来。最后, 经过一段时间运行, 可能会出现一条最短的路径被大多数蚂蚁重复着。蚁群算法最初被用于解决旅行商问题 (Traveling Salesman Problem, TSP) , 近来被用于解决不同种类的组合最优化。

为应用蚁群算法, 建立二分图G= (V, U, E) , V是一组载波, 对于每个载波n, vnc={vn1, …, vnc}, vnc表示能够被第n个载波传输的比特数是c。U是一组用户, u∈{u1, …, uK}。E是一组边界, E={eck, n|k=1, …, K;n=1, …, N;c=1, …, C}, 如果第n个载波分配给第k个用户且第n个载波传输的比特数是c, 边界eck, n是vnc与uk之间的边界。图中的一组边界代表了分配方案。解决边际问题与找到图中最小消耗路径相一致。

2.2 步骤

(1) 初始。m个蚂蚁随机地选择一组用户, 然后设置信息素追踪τck, n和试探信息ηck, n。信息素追踪τck, n代表分配载波n给用户k和能够被第n个载波传输的比特数是c的期望。在本文中, 定义τck, n=τ0+Δτ, τ0是边际上的初始信息素追踪, Δτ定义如下

试探信息ηck, n刺激蚁群用较低消耗选择载波。ηck, n定义为

(2) 每个蚂蚁基于可能决策选择一个未被占用的载波。可能性定义如下

式中, α和β是决定信息素追踪和试探信息重要性的两个参数;Tabuk是蚂蚁k的踏步表, 它是没有被蚂蚁k选择的一组载波。

(3) 满足用户需求之后, 蚂蚁k随机选择下一个用户且重复步骤 (2) 。

(4) 所有蚂蚁完成他们的步骤之后, 能够发现种选择且更新信息素追踪。为使蚂蚁忘记不好的选择, 在最初所有信息素追踪都会减少。然后找到最好路径的蚂蚁在路径上放置信息素。在每个循环结束, 信息素追踪更新如下

式中, 参数ρ代表信息素追踪的消散值;Δτck, n表示找到最好路径的蚂蚁在它的路径上放置信息素。Δτck, n定义如下

式中, Lgb表示目前蚁群发现的全面最佳选择;Q是在一个循环中信息素放置的个数, 它能够加强信息素追踪的作用。

3 接纳控制实现

在本文中, 假设系统提供的总的传输功率为P, 则CAC策略有如下规则:

(1) 在切换呼叫和新呼叫同时到达时, 优先为切换呼叫分配载波, 同时提供切换呼叫所需的传输功率。通过本文提出的算法预先计算所有呼叫所需的最小PT, 若PT≤P, 则同时接纳切换呼叫和新呼叫。若PT>P, 则新呼叫被阻塞;若阻塞新呼叫后, PT>P, 则切换呼叫同样被阻塞。

(2) 在切换呼叫或新呼叫不同时到达时, 计算所需最小PT。若PT≤P则接纳所有呼叫;否则阻塞呼叫, 若x个新呼叫同时到达, 则根据递减规则, 依次计算阻塞第l至第l-d个时的PT, 直到找出满足条件PT≤P的d, 此时阻塞了d个呼叫。x个切换呼叫同时到达的接纳控制规则与个新呼叫同时到达的接纳控制规则相同。

结合规则 (1) 和 (2) , 对需要接入呼叫进行接纳控制, 以此达到资源的有效合理利用。

4 仿真实现

假设OFDMA系统的参数如下:系统总带宽为1 MHz, AWAG的功率谱密度为-80 d B/Hz, 系统的信道是由6个独立的瑞利多径组成的频率选择信道, 载波数目N=64, 用户的数目K, c∈{0, 1, …, 6}, 用户的数据率R1=R2=…RK=20 bit/symbol, pe=10-4。蚁群算法的参数设置如下:α=1, β=2, ρ=0.1, Q=50, m=30, τ0=0.01。

从图中可以看出, 在用户数量不同时, 此算法的收敛性能不同, 用户数越多收敛越慢。且在用户数量增加时, 通过蚁群算法能够找到的最小所需传输功率在不断增加。通过对传输功率的门限值进行设定, 能够对切换呼叫和新呼叫进行有效地接纳控制, 实现资源的分配。

5 结束语

本文提出的算法是蚁群算法在资源分配上的利用, 其应用范围广泛, 在求解最佳值方面具有较大优势。因此, 利用蚁群算法实现资源的分配, 简单方便, 且易实现。在接纳控制中, 有效地实现了新呼叫和切换呼叫的接纳控制。但在用户不断增多时算法的运算复杂度增加, 会导致算法需要的时间增加。从实际角度出发本算法不适用于用户过多的情况。

参考文献

[1]Zhang Xin, Ye Wu, Feng Suili, et al.Adaptive resource allocation for OFDMA system based on ant colony algorithmnan[C].Nanjing:ICISE, 2009.

[2]WONG I C, Evans B L.Optimal downlink OFDMA resource allocation with linear complexity to maximize ergodic rates[J].IEEE Transactions on Wireless Communications, 2008, 7 (3) :962-971.

[3]Kivanc D, Li G, Liu H.Computationally efficient bandwidth allocation and power control for OFDMA[J].IEEE Transactions on Wireless Communications, 2003, 2 (6) :1150-1158.

[4]Shen Z, Andrews J G, Evans B L.Adaptive resource allocation in multiuser OFDM systems with proportional rate constraints[J].IEEE Transactions on Wireless Communications, 2005, 4 (6) :2726-2737.

[5]Kim I, Lee H L, Kim B, et al.On the use of linear programming for dynamic subchannel and bit allocation in multiuser OFDM[C].San Antonio, TX:IEEE Global Telecommunications Conference, 2001.

[6]Ergen M, Coleri S, Varaiya P.Qo S aware adaptive resource allocation techniques for fair scheduling in OFDMA based broadband wireless access systems[J].IEEE Transactions on Broadcast, 2003, 49 (4) :362-370.

[7]Tolli A, Hakalin P, Holma H.Performance evaluation of common radio resource management (CRRM) [C].IEEE International Conference of Communication, 2002:3429-3433.

[8]Tolli A, Hakalin P.Adaptive load balancing betweenmultiple cell layers[C].IEEE 56th Vehicular Technology Conference, 2002:1691-1695.

[9]周坡, 曹志刚.基于网络效用的OFDM卫星移动通信系统呼叫接纳控制[J].宇航学报, 2012, 33 (5) :628-634.

蚁群系统算法 篇2

高炉的冶炼过程是非常复杂的工艺, 影响高炉顺行的因素非常多。根据炉内状况和对各种参数的判断, 进而更改高炉的操控方式也是一个复杂的过程。为此, 工程人员尝试引入数学模型来解决这个问题。工程技术人员参考了众多工程资料, 决定用蚁群算法实现对高炉重要指标的概率搜索, 从而对高炉冶炼过程进行指导。

1 蚁群算法

与大多数基于梯度的应用优化算法不同, 蚁群算法依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数, 但是与梯度方法及传统的演化算法相比, 其优点还是显著的:无集中控制约束, 不会因个别个体的故障影响整个问题的求解, 确保了系统具备更强的鲁棒性;以非直接的信息交流方式确保了系统的扩展性;对问题定义的连续性无特殊要求;算法实现过程便于优化。

2 数学原理

在函数优化问题中, 假定优化函数为:

转移概率准则:设m个人工蚂蚁, 刚开始时位于区间[a, b]的m等分处, 蚂蚁的转移概率定义为:

其中, Pij表示蚂蚁从位置i转移到位置j的概率;τj为蚂蚁j的邻域吸引强度;ηij定义为Fi (x) -Fj (x) , 即目标函数差异值;参数α, β∈[1, 8], 该范围的取值是一个经验值。强度更新方程:

式中, △τj反映第j只蚂蚁在本次循环中吸引强度的增加;Q为正常数, 其范围为0~5000, Lj表示本次循环中F (x) 的增量, 定义为F (x+r) -F (x) ;0≤ρ≤1, 体现强度的持久性;t表示本次循环的时刻, t+1为下一时刻。于是, 函数F (x) 的寻优就借助m个蚂蚁的不断移动来进行:当ηij≥0时, 蚂蚁i按概率Pij从其邻域i移至蚂蚁j的邻域;当ηij≤0时, 蚂蚁i做邻域搜索 (搜索半径或步长为r) , 即每个蚂蚁要么转移至其他蚂蚁处, 要么进行邻域搜索。

这种寻优方式相当于一群蚂蚁对定义区间[a, b]做穷尽的搜索, 逐渐收敛到问题的全局最优解。

3 针对高炉参数的变异过程

将Xk化为影响高炉布料的一个参数 (如煤气利用率) , k从i变成j, 再变为n的过程, Xk的值在其整个取值域内发生改变, 如[23.6, 44.8], 在此变异过程中, 舍去比Xi劣的解, 保存比Xi优的解。程序完成设定的变异次数后, 就能有效地搜寻到较Xi优化的解Xp, 再采用蚁群算法在Xp的邻域内进行寻优。经此变异后, 可以跳出局部极小的区域, 使得解的质量得到提高。利用蚁群算法的变异过程如图1所示。

对影响下料的17个主要参数, 炉顶压力、顶温、α角度、冷风流量等进行变异过程分析, 并用MATLAB软件对算法进行实现。

部分代码如下:

根据此算法, 各炉况下倾动角度a的推演如图2所示。

如图2所示, 在矿石反复布料的情况下, 透指等工艺状态更稳定, 达到理想效果, 与用MATLAB仿真的结果相同。

4 结语

根据蚁群算法的推演, 得到结论:在布料方面, 倾动角度在较固定的区域内[a, b], 均匀布料会获得比较好的炉体运行状态。该例中, a=36.8, b=48.5。

另外, 对影响炉况运行的其它参数也进行了模拟运算, 这对工艺参数修改有非常显著的指导意义。

摘要：介绍蚁群算法原理, 结合高炉系统的工艺, 对高炉的重要参数进行变异, 实现对高炉炉况顺行的指导。

关键词：数学模型,蚁群算法,高炉,MATLAB仿真

参考文献

[1]余艾冰, 杜鹤桂.高炉无钟炉顶中炉料运动的理论解析[J].东北工学院学报, 1986, (4) :71-78

[2]朱清天.高炉料流轨迹的数学模型[J].北京科技大学学报, 2007, 29 (9) :932-936

蚁群系统算法 篇3

关键词：项目调度,资源受限,多模式,蚁群系统算法

0 引 言

资源约束项目调度问题RCPSP(Resource-Constrained Project Scheduling Problem)一般以找出工期最短(或耗费最小)的调度方案为优化目标,项目由一系列相互关联的活动组成,调度决策需要同时满足项目活动之间的时序约束和资源约束,以使管理目标最优[1]。多模式资源约束项目调度问题MRCPSP(Multi-mode Resource Constrained Project Scheduling Problem)是传统RCPSP的扩展,其考虑项目中每个活动都有多种可供选择的执行模式,每种执行模式对应一定的工期和资源需求,在调度时能够动态地选择活动执行模式及其属性。相对于单模式调度问题[2],MRCPSP在资源约束条件下,不仅要选择项目中各活动的执行模式,还要确定活动的开工期,是一类带有复杂非线性特征NP-难问题,精确类算法很难求解。随着智能算法的不断发展,其在项目管理领域的应用也越来越多。针对该问题,文献[3]提出基于二维编码方式的混合遗传算法对MRCPSP问题进行求解;文献[4]采用差分演化算法求解MRCPSP,取得了不错的效果;文献[5]运用改进蚁群算法求解MRCPSP,采用规则池管理和使用大量优先级规则,提升了算法的通用性和性能。

蚁群优化算法是文献[6]于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种新型的基于种群的启发式仿生进化算法,具有全局搜索、快速收敛等特点。由于它特有的构建性策略,特别适合于项目调度问题的求解。文献[7]已经验证,蚁群优化算法是求解传统以最短工期为目标的RCPSP的性能最优的算法之一。本文提出一种性能最优的蚁群优化算法之一的蚁群系统(Ant Colony System,ACS)算法[8]来实现MRCPSP的优化,采用基于活动执行模式的一维实数编码方案,把活动网络图转换为构建图,蚂蚁在构建图上在资源约束和时序约束下按一定规则游走来确定调度生成方案,定义新的信息素表示和启发式,得出一种用于优化MRCPSP的蚁群系统算法,最后用实验结果验证算法的正确性与有效性。

1 问题描述及模型

MRCPSP是研究在工程项目活动网络图的基础上,满足资源和活动时序等约束来安排各活动的执行模式和开始时间,以使项目工期最短的调度方法,其实质是寻求各个活动执行模式和开工时间的最佳组合。本文采用AOA(activity-on-arrow)有向活动网络图表示整个项目活动,如图1所示。其中结点代表事件,箭线代表活动,方向代表时序约束。

基于AOA图建立MRCPSP模型时作如下假设:

(1) 每种活动均有多种执行模式可供选择,每种执行模式对应不同的工期和资源需求。

(2) 每个活动只能选择其中一种执行模式执行,而且一旦执行就不能被中断和更改执行模式直至完成;

(3) 活动具有时序约束和资源约束;

(4) 资源均为可更新资源,每个活动所需资源量均小于资源的最大供应量;

(5) 对事件和活动进行编号时,确保事件按时序约束非严格递增,即事件j的所有紧前事件编号必须小于j,后继事件编号必须大于j;

(6) 为方便描述问题引入虚事件0和N+1(只有一种执行模式,不占用资源且执行时间为0),代表整个项目的开始和结束。Fm+1为结束事件(N+1)对应的唯一活动(M+1)的最早开始时间,即项目总工期。

设项目包含N个事件M个活动,从事件i到事件j的一项活动记为(i,j),r${}_{ijv}^k$为活动(i,j)用模式k执行时单位工期所需资源v的数量,d${}_{ij}^k$为工期。所有活动共享V种可更新资源,其中第v种资源的供应量为Rv。P(j)为事件j的紧前事件集合,S(j)为事件j的后继事件集合。优化目标是在满足资源约束和时序约束前提下,通过确定合理的活动执行顺序、相应的执行模式以及活动的开始时间,使项目的工期最短。其数学模型为:

minf(x)=Fm+1 (1)

s.t.${\displaystyle \sum _{(i,j)\in SA{}_t}{\displaystyle \sum _{k=1}^{{\rm K}{}_{ij}}r}}{}_{ijv}^{k}X{}_{ij}^k\le R{}_v(v=1,2,\cdots ,V$;t=1,2,…,TN) (2)

${\displaystyle \sum _{k=1}^{{\rm K}{}_{ij}}X}{}_{ij}^k=1((i,j)\in A)$ (3)

${\displaystyle \sum _{\begin{array}{l}t=E{\rm T}{}_{ij}\\ i\in {\rm P}(j)\end{array}}^{L{\rm T}{}_{ij}}t}Y{}_{ijv}^t\le {\displaystyle \sum _{\begin{array}{l}t=E{\rm T}{}_{jl}\\ l\in S(j)\end{array}}^{L{\rm T}{}_{jl}}(}tY{}_{jl}^t-{\displaystyle \sum _{k=1}^{{\rm K}{}_{jl}}d}{}_{jl}^{k}X{}_{jl}^k)(j=1,2,\cdots ,{\rm N})$ (4)

${\displaystyle \sum _{t=E{\rm T}{}_{ij}}^{L{\rm T}{}_{ij}}Y}{}_{ij}^t=1$ (5)

式(1)表示最小化项目工期;式(2)表示资源约束,SAt表示在时期t时正在进行的活动集合;式(3)表示活动仅能用一种模式执行(X${}_{ij}^k$=1时,活动以模式k执行,否则为0);式(4)表示时序约束,表达的是任意事件j的前趋活动(i,j)必须在事件j的后继活动(j,l)开始之前完成;式(5)定义了活动的时间窗约束,即活动(i,j)必须在其时间窗[ETij,LTij]内完成(如果活动(i,j)在时间窗[ETij,LTij]中的一个时点t上被完成,则Y${}_{ij}^t$=1,否则为0)。

2 求解MRCPSP模型的蚁群算法设计

在MRCPSP模型中使用蚁群系统算法,需要把问题表示的AOA网络图转换为蚂蚁路径构建图,得出问题的解的构建方法,并重新定义信息素和启发式信息的表示。

2.1 构建图

对所有活动(i,j)∈A的所有执行模式进行编号并将其变成构建图的结点,如图2所示。

假设图1中每个活动均有两种执行模式,即通常模式(N)和通过增加资源缩短工期的压缩模式(C)。则活动1的两种执行模式分别对应结点m1和m2,活动2的两种执行模式分别对应m3 和m4,活动3的两种执行模式分别对应m5 和m6,活动4的两种执行模式分别对应m7 和m8 ,m0和m9分别对应项目的开始和结束。通过编号得到构建图的结点集MODE={m1,m2,…,m|MODE|}。其中|MODE|是所有真实模式的总数目,mode0和mode|MODE|+1是哑模式,分表代表项目的开始和结束。

MODE中模式在两个方向上完全连接的有向边为信息素和启发式信息的载体,在边(mi, mj)上的信息素含量记为τij,在此边上的启发式信息记为ηij。

2.2 解的构建

蚂蚁从初始模式m0出发,寻找一条遍历所有活动一次且仅一次,最终到达结束模式m|MODE|+1的合法路径。

(1) 蚂蚁把开始模式m0添加到解序列中,初始化当前时间,并把所有初始事件的直接后继活动所有模式添加到候选集中。

(2) 蚂蚁根据信息素和启发式信息,从候选集中选出下一个可行模式添加到解序列中,根据当前时间、满足时序约束时间以及满足资源约束时间确定此模式的最快可开始时间(取三者最大值),将其设置为该模式实际执行时间。同时将当前时间设置为该模式的最快可开始时间,以保证模式序列开始执行时间的非严格递增性。

(3) 蚂蚁更新当前所占用的资源集合并更新候选集:

① 判断所选择的模式Si所属活动,把所有同属于该活动的模式从候选集中删除。

② 如果Si所在活动属于事件j的紧前活动,并且执行Si后所有事件j的直接紧前活动都已经被选择执行,那么事件j被激活,其直接后继活动的所有模式都被加入到候选集中;转(2)直到候选集为空。

2.3 算法流程

(1) 初始化

将蚁群置于开始模式m0处并初始化信息素。由于MRCPSP问题的优化目标是工期,项目总工期的长短是衡量一个项目调度方案质量优劣的标准。本文以项目总工期作为信息素的表达对象,信息素按式(6)进行初始化,其中,T0为由初始调度得到的项目总工期。

$\tau {}_{ij}=\tau {}_0=\frac{1}{{\rm T}{}_0}$ (6)

(2) 生成调度

蚂蚁在构建图的每次迭代过程中,各蚂蚁在各结点间信息素的引导下,按照一定的转移规则选择可行的活动模式并记下该模式所在的结点,同时将其放入模式列表中,直至生成一个时序可行的活动模式列表S=(S0,S1,…,SM+1),其中,S0= m0,SM+1= m|MODE|+1,即项目的开始和结束;对于l=1,2,…, M,Sl对应于按时间序列第l项发生的一种执行模式。每一种活动只对应于S中的一种模式,且必须满足AOA网络给定的时序约束。通过串行进度生成机制对所得模式列表进行解码,从而得到问题的一个解,即一种可行调度方案,最后根据得到项目工期评价各调度方案的优劣。

其中,某只蚂蚁当前位于模式mi时,选择下一可行的活动模式Sk时按转移规则式(7)和式(8)进行:

$S{}_k=\{\begin{array}{l}\text{a}\text{r}\text{g}\text{m}\text{a}\text{x}{}_{m{}_j\in \text{候}\text{选}\text{集}}\{[\tau {}_{ij}]\cdot [(\eta {}_{ij}){}^{\beta }]\}\text{如}\text{果}q\le q{}_0\\ \text{轮}\text{盘}\text{赌}\text{选}\text{择}\text{否}\text{则}\end{array}(7)$

${\rm P}(m{}_j)=\{\begin{array}{l}\frac{\tau {}_{ij}\cdot (\eta {}_{ij}){}^{\beta }}{{\displaystyle \sum _{m{}_l\in \text{候}\text{选}\text{集}}\tau }{}_{il}\cdot (\eta {}_{il}){}^{\beta }}\text{如}\text{果}m{}_j\in \text{候}\text{选}\text{集}\\ 0\text{否}\text{则}\end{array}(8)$

算法生成一个随机数q∈[0,1]并与参数q0相比较,如果q≤q0则选择函数直接返回候选集中具有最大信息素与启发式信息的β次幂的乘积值的模式mj,否则执行轮盘赌选择,如式(7)所示。也就是说,选中候选集中某种模式的概率与该模式的信息素与启发式信息的β次幂的乘积的值的大小成正比,如式(8)所示。其中,ηij为用于评价蚂蚁从Si向Sj移动的路径启发信息,β是一个表示启发式信息权重的参数。本文通过最大资源需求量优先启发式规则来确定ηij,若mj的资源总需求量为${\displaystyle \sum _{m{}_j\in \text{候}\text{选}\text{集}}r}{}_{m{}_{j}v}$,则t时刻蚂蚁在结点Si处的启发信息如式(9)所示,这样能够使最多资源需求的候选模式被更多的蚂蚁选择。

$\eta {}_{ij}(t)=\frac{{\displaystyle \sum _{m{}_j\in \text{候}\text{选}\text{信}}r}{}_{m{}_{j}v}}{{\displaystyle \sum _{v=1}^{V}R}{}_v}$ (9)

(3) 信息素更新

在所有蚂蚁完成一次循环后,对信息素进行更新。本文ACS采用两种信息素更新方式:在局部信息素更新中,每当蚂蚁从模式mi移动到mj,信息素更新规则将被立刻调用,如式(10)所示:

τij←(1-ρ)·τij+ρ·τ0 (10)

其中,ρ∈[0,1]是一个参数。由于τ0是信息素的初始值,相对较小。对于信息素含量高,经常被蚂蚁使用的边来说,局部信息素更新的作用在于减少该边上的信息素,使后来的蚂蚁能够尝试选择更多不同的边,从而增加了算法的搜索多样性。

全局信息素更新规则仅在每次迭代完成之后才执行。当所有蚂蚁都构建出它们的解并计算出其项目工期之后,全局信息素更新规则将对算法执行以来所发现的最优解S′上的所有边释放较大量的信息素,如式(11)所示:

τij←(1-α)·τij+α·T(S′) (11)

其中,mi和mj是在解S′模式序列上的两个相邻模式。全局信息素更新增大了蚂蚁对最优解上的模式的选择偏向性,从而使算法向最优解收敛。

3 实例验证与分析

本文采用一个包含10事件14活动的项目实例来验证ACS算法在解决该类问题上的可行性和有效性,项目活动网络图如图3所示。该项目需要三种可更新资源R1、R2 和R3,单位工期限量分别为8、16和20,除虚事件对应活动外,项目中每个活动均有两种可执行模式:通常模式(N)和通过增加资源缩短工期的压缩模式(C),不同执行模式下各活动的工期(T)及所需资源如表1所示。

利用本文提出的ACS算法对上述模型进行求解,算法参数设置:蚂蚁数目m=10,启发式信息权重 β=1,式(7)中的q0=0.5,局部信息素更新参数ρ=0.1,以及全局信息素更新参数α=0.1,算法迭代次数为30。运行结果为:项目最短工期31天,平均工期为32天,最佳调度方案如表2所示。

(1) 由表2可知:ACS算法能有效求解多模式资源约束调度问题,对项目各活动的执行模式和开工日期做出合理调度,以使整个项目工期最短。

(2) 运用遗传算法求解该实例,运行30次,其平均工期为34天,说明了ACS算法在求解MRCPSP问题上的高效性。

(3) 将ACS与简单遗传算法(GA)两种方法应用于一个包含20个事件、36个活动的项目上测试,两种方法均运行100次,结果如表3所示。说明对于较大规模的算例,ACS同样表现了良好的全局收敛性能。

4 结 语

本文把ACS算法应用到MRCPSP的求解中,详细分析了问题的模型,给出算法的设计思想、详细方法,通过实验用ACS算法对MRCPSP问题进行解答,数值实验结果证明了算法的正确性和有效性。特别是本文提出的算法无需结合其他优化技术,简洁高效,其基于活动执行模式的一维实数编码方案,相对于其它文献[2,3,4,5]的二维编码,更为简单实用,有利于蚁群算法在项目管理领域的进一步推广和应用。

参考文献

[1]Valls V,Ballestin F,Quintanilla S.Justification and RCPSP:A tech-nique that pays[J].European Journal of Operational Research,2005,165(2):375-386.

[2]陈旺,李波,史彦军,等.求解RCPSP问题的带分布估计的差异演化算法[J].计算机工程与应用,2011,47(4):1-4.

[3]王为新,李原,张开富.基于遗传算法的多模式资源受限项目调度问题研究[J].计算机应用研究,2007(1):70-74.

[4]Damak N,Jarboui B,Siarry P,et al.Differential evolution for solving multi-mode resource-constrained project scheduling problems[J].Computers&Operations Research,2009,36(9):2653-2659.

[5]彭武良.一种求解多模式资源受限项目调度问题的蚁群算法[J].信息系统学报,2009,3(1):1-10.

[6]Colomi A,Dorigo M,Maniezzo V.Distributed Optimization by Ant Colonies[C]//The First European conference on Artificial Lift.France:Elsevier,1991:134-142.

[7]Merkle D,Middendorf D,Schmeck H.Ant colony optimization for re-source-constrained project scheduling[J].IEEE Transactions on Evo-lutionary Computation,2002,6(4):333-346.

蚁群系统算法 篇4

1 蚁群算法

蚁群算法主要是模拟蚂蚁寻找食物的行为而产生的。蚂蚁在外出觅食的时候会沿路散播一些信息素用于标记路线。一旦有一只蚂蚁在出发地点和目标地点之间走出了最短路径, 那么它会比其他蚂蚁更早返回。因此, 会有更多的蚂蚁开始按照这只蚂蚁散播的信息素选择这条最短路径, 最短路径上积累的信息素也会随之增加。同时, 其他路径上由于蚂蚁越来越少, 信息素也会不断减少, 这条路径会逐渐被放弃。因此, 蚁群算法具有很高的效率。

1.1 前提假设

(1) 把用户视为一个单元, 作为蚂蚁K (=1, 2, …m) 。

(2) 把职位作为“食物”, 即项目Ic。

(3) 在用户K和职位Ic之间存在一个空间, 其中有类Ii (i=0, 1, 2…m, m∈N) , 将用户的浏览行为记录下来, 结合数据便可以计算该类的评分。

由表1可知, 蚂蚁寻找最优路径巢穴出发蚂蚁信息素觅食路径食物;用户寻找目标职位登录系统用户项目评分浏览路径目标职位。

1.2 关于蚁群算法应用的描述

描述1:用有向图G= (U, E) 来表示招聘网站, 其中U是网站URL的集合, E是有向边的集合。一个招聘职位可以看成一个项目, 对应相应的URL界面。所以, 存在一个项目集I与网站的集合相对应, 且他们之间的关系可以用G= (I, E) 来表示。在图中, 网站对应的项目为Ii, 则可以用D (Ii, Ij) 来表示图中Ii和Ij之间的最短路径。

描述2:假设I是人职匹配推荐系统中职位项目的集合, 其总数为m, m∈N, W是用户已经浏览过的职位网页的集合。如果存在w W, 对于任何v∈w, 它们的前i位都相同, 而i+1位有m-1种浏览项目, 则称在i位上有m-1种不同的选择, 定义用户从项目i到下一项目j的转移概率。

描述3:如果职位项目Ii较长时间未被k用户访问, 说明k用户已经发生了偏好转移。因此, 该职位项目Ii应该被放弃, 设下一次t+1可选则项目为Ij (j=1, 2….m) , 用户k选择项目为Ic。

项目得分因子一般地, 项目j与项目i的距离D (Ii, Ij) 越大, 项目j得分越高。

2 职位推荐过程

通常所知的推荐系统都有三个步骤:第一, 数据清洗;第二, 数据挖掘;第三, 信息推荐。

首先, 系统需要从用户的浏览日志中获得数据, 然后通过数据清洗, 去除无用信息, 提炼出可供挖掘的有效数据。其次, 可以按照上文推导公式构建评分矩阵, 从而进行数据挖掘。矩阵以项目类Ii为行, Ij为列构造项目得分矩阵。表示t时刻计算得出的从项目i到项目j的评分。最后, 需要将用户进行分类, 依据数据挖掘的结果, 可以得到用户的偏好浏览路径。在某一类用户的矩阵中可以找到用户概率最大的一个职位推荐给他, 并且还能根据用户的动态信息重新调整项目的评分。

3 结语

蚁群算法是一种比较新的算法, 本文将该算法和偏好浏览路径相结合, 讨论了项目集的评分, 最优职位的产生问题, 并能一定程度上解决实际问题, 同时验证了该算法在推荐过程中尤其独特的优势。

参考文献

[1]肖人彬, 陶振武.群集智能研究进展[J].管理科学学报, 2007 (3) .

[2]姚建明.MC模式下供应链动态调度的蚁群寻优分析[J].管理科学学报, 2007 (3) .

蚁群系统算法 篇5

车辆导航系统中的最短路径搜索问题可以归结为图论中的最短路径问题,解决该问题的经典算法是Dijkstra算法,该算法采用贪心策略,即每一步都选择与源节点构成局部路径距离最短的节点作为当前扩展节点来形成当前局部最短路径,进而得到全局的最短路径。是一种静态的局部最优算法。该算法简单、易于实现,然而把该算法应用在求车辆导航系统中的最短路径搜索问题却存在如下的局限性:首先,因为需要反复遍历所有节点,在网络节点和路径较多的情况下,搜索效率就会大大降低,有时甚至找不到最短路径,再者,对于路径权值随时间动态变化的动态网络,如反映路径堵塞和畅通信息的实时交通系统网络就不适用。

蚁群算法是由意大利学者Dorigo M[1]等人于1991年从自然界蚂蚁群体觅食行为得到启发,提出的一种模拟蚂蚁行为的模拟进化算法——人工蚁群算法,简称蚁群算法。这种算法具有分布计算、信息正反馈和启发式搜索的特征,算法具有模拟生物界群体觅食的能力,并且能够在实际的路径搜索过程中对外界的影响做出动态的响应,因而在交通最优路径选择中具有极大的可能性和适应性。

然而使用传统蚁群算法求最短路径问题却存在搜索速度慢,易于陷入局部最优解等缺陷,在此针对交通网络最短路径问题的特点,在传统蚁群算法中引入搜索方向机制和搜索热区机制提高算法搜索性能。通过计算机进行仿真实验,实验结果较满意。

1 基本蚁群算法简介

自然界中的蚂蚁的特点是个体行为极其简单,而群体行为却相当复杂。一群蚂蚁通过相互协作很容易找到从蚁穴到食物源的最短路径(最优路径),之所以可以做到这一点,是因为蚂蚁个体之间是通过在其所经过的路径上留下一种可称之为信息素的物质进行信息传递,蚂蚁就是根据路径上信息素的浓度指导自己对前进方向的选择。蚁穴到食物源之间的路径越短,则单位时间内蚂蚁往返的次数越多,相应地该路径上的信息素的浓度也越高,反过来路径上信息素的浓度越高,后来的蚂蚁选择该路径的概率就越大。信息素浓度最大的路径就是最短路径(最优路径)。

将m只蚂蚁随机放在n个节点,所有路径(i,j)上的信息素置初值τij(0)=C(C为常数),然后蚂蚁k(1,2,…,m)在t时刻按照转移概率p${}_{ij}^k$(t)选择下一个节点。其中τ${}_{ij}^{\alpha }$(t)表示边(i,j)在t时刻的信息素浓度,η${}_{ij}^{\beta }$(t)表示边(i,j)在t时刻的启发信息。

$p{}_{ij}^k(t)=\{\begin{array}{cc}\frac{\tau {}_{ij}^{\alpha }(t)\eta {}_{ij}^{\beta }(t)}{{\displaystyle \sum _{s\in \text{a}\text{l}\text{l}\text{o}\text{w}\text{e}\text{d}{}_k}\tau }{}_{is}^{\alpha }(t)\eta {}_{is}^{\beta }(t)},& j\in \text{a}\text{l}\text{l}\text{o}\text{w}\text{e}\text{d}{}_k\\ 0‚& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}(1)$

启发信息因子设为:

$\eta {}_{ij}(t)=1/d{}_{ij}(2)$

式中:dij表示节点i到节点j之间的距离;参数α,β分别表示信息素浓度和启发信息的重要性;allowedk={0,1,…,n-1}表示蚂蚁k下一步允许选择的节点(访问过的节点不允许选择)。经过n个时刻,所有蚂蚁完成一次循环,各路径上的信息素根据下式调整:

$\tau {}_{ij}(t+n)=(1-\rho )\tau {}_{ij}(t)+\text{Δ}\tau {}_{ij}(t)(3)$

式中:1-ρ表示信息素残留因子,ρ∈(0,1);

$\text{Δ}\tau {}_{ij}(t,t+n)={\displaystyle \sum _{k=1}^m\text{Δ}}\tau {}_{ij}^k(t,t+n)(4)$

式(4)表示所有经过边(i,j)的蚂蚁撒下的信息素。

根据信息素更新策略的不同,Dorigo M提出了三种不同的基本蚁群算法模型,其中Ant-Cycle模型在求解最短路径时性能最好,具体模型如下:

$\begin{array}{l}\text{Δ}\tau {}_{ij}^k(t)=\\ \{\begin{array}{l}Q/L{}_k‚\text{如}\text{果}\text{蚂}\text{蚁}k\text{在}\text{本}\text{次}\text{循}\text{环}\text{中}\text{经}\text{过}(i,j)\\ 0‚\text{否}\text{则}\end{array}(5)\end{array}$

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

2 改进的蚁群算法

针对交通系统中最短路径问题的特点,对蚁群算法进行改进,引入搜索方向机制和搜索热区机制来提高对最短路径的搜索效率,具体改进措施如下:

2.1 引入搜索方向机制

蚁群算法的启发信息,即式(2)中,dij表示为可选边的长度,dij越短则该边被选中的概率就越大。但在求解最短路径问题时,路径启发信息仍然用式(2)表示则并没有考虑到由源节点到目的节点的方向性问题,从而造成算法的搜索速度下降和易于陷入局部最优解。由此对启发信息因子修改如下:

$\eta {}_{ij}^{}(t)=1/d{}_{jo}(6)$

式中:djo表示节点j到节点o的距离。这样距离目标节点近的节点被选中的概率就比较高,从而可以提高了蚁群算法的搜索性能。

2.2 引入搜索热区机制

搜索热区是指由源节点和目标节点为对角节点所组成的矩形区域,在实际求最短路径问题时,求得的最优轨迹节点的位置,其落在由源节点和目标节点为对角节点所形成的搜索热区的概率往往要大大高于落在非搜索热区内的概率。因此在蚁群算法中引入搜索热区的概念后不但使得搜索的速度大大提高,而且不易搜索陷入局部最优解。引入搜索热区机制后转移概率p${}_{ij}^k$(t)如式(7)所示。

$p{}_{ij}^k(t)=\{\begin{array}{l}\frac{\tau {}_{ij}^{\alpha }(t)\eta {}_{ij}^{\beta }(t)\phi {}_{ij}(t)}{{\displaystyle \sum _{s\in \text{a}\text{l}\text{l}\text{o}\text{w}\text{e}\text{d}{}_k}\tau }{}_{is}^{\alpha }(t)\eta {}_{is}^{\beta }(t)},j\in \text{a}\text{l}\text{l}\text{o}\text{w}\text{e}\text{d}{}_k\\ 0‚\text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\end{array}(7)$

式中:φ${}_{ij}^{}$(t)表示在t时刻根据边(i,j)是否在搜索热区中而取不同的值,其他参数意义不变。

$\phi {}_{ij}(t)=\{\begin{array}{l}A,\text{边}(i,j)\text{在}\text{搜}\text{索}\text{热}\text{区}\text{内}\\ B‚\text{边}(i,j)\text{不}\text{在}\text{搜}\text{索}\text{热}\text{区}\text{内}\end{array}(8)$

式中:通常情况下A应取大于1的数;B取小于1的数。

3 使用改进的蚁群算法求最短路径问题的实现

求图中任意源点到目标点最短路径问题的改进蚁群算法具体实现步骤如下:

(1) 将m只蚂蚁放在源点;

(2) 所有路径(i,j)上的信息素置初值τij(0)=C(C为常数),当前最短距离初始化为一个极大值;

(3) 然后蚂蚁k(1,2,…,m)在t时刻按照的转移概率式(7)选择下一个节点。其中ηij(t),φij(t)如式(6),式(8)所示。当所选节点是终点时,则该只蚂蚁结束搜索,此时,如果该蚂蚁走过的路径长度小于当前最短距离,则当前最短距离用该蚂蚁走过的路径长度取代。

(4) 经过n个时刻,所有蚂蚁完成一次循环,即结束一次迭代过程,各路径上的信息素根据式(3)～式(5)调整。

(5) 重复步骤(1)～(4),直到预期的迭代次数为止,即得到由源点到目标点的最短路径。

4 实验仿真

4.1 求交通网络两点间的最短路径问题仿真

实验的硬件平台是赛扬1.8 G的PC机,256 MB内存,操作系统是Windows 2000 Server。开发工具是VC 6.0。数据采用沈阳电子地图,以交叉路口作为节点。

相邻两节点之间的距离为权值,如果两节点不是直线,则测量出实际长度作为两点间的权值,节点经、纬度如表1所示。

蚁群算法中各参数设置如下:蚂蚁数为5,信息素初始值τij(0)=20,路径信息释放率ρ=0.1,参数α=0.3,β=5,A=4,B=0.999 9,蚂蚁携带信息素总量Q=1 000,迭代次数为100。则路口2到路口50之间的路径长度为3.128 730 km,经过的路口依次为2,1,12,20,21,22,18,26,35,43,44,47,49,50。结果如图1所示。

4.2 传统蚁群算法和改进的蚁群算法在求解最短路径问题时的对比

以点60为目标节点,以其他节点为源点,各参数设置同上。使用基本蚁群算法和改进蚁群算法来分别求源点到目标点搜索到最短路径所需的迭代次数,结果如表2所示。

由表2可知,传统蚁群算法的平均迭代次数为71.06,改进蚁群算法平均迭代次数为55.82,较传统蚁群算法有了明显的提高。

5 结 语

这里采用改进的蚁群算法对交通系统最短路径问题进行研究,为解决该问题提供了一个新的思路,从仿真结果可以看出,该方法取得较好的效果,与传统的蚁群算法相比,搜索速度有了明显的提高,该实验主要针对路径权值为正的静态交通网络为进行求解,对于权值随时间变化的动态网络仍然适用。

摘要：求解交通路网中两点间的最短路径是智能交通系统中的一个重要功能,为了更为准确快速地找到最优解,这里分析Dijkstra算法处理动态车辆路径问题中的缺陷,提出一种改进的蚁群算法,即在基本蚁群算法中引入搜索方向和搜索热区机制提高算法的搜索性能。通过建立改进蚁群算法模型,用VC 6.0开发工具,以实际交通地图为例,求解交通网络两点间最短距离;并与基本蚁群算法进行对比。仿真实验表明,传统蚁群算法的平均迭代次数为71.06,改进蚁群算法平均迭代次数为55.82,比传统蚁群算法有了明显的提高。该方法能有效解决交通系统最短路径问题,具有一定的实际意义和参考价值和实际意义。

关键词：蚁群算法,最短路径,信息素,智能交通系统

参考文献

[1]Colorni A,Dorigo M,Maniezzo V.The Ant System:Optimi-zation by a Colony of Cooperating Agents[J].IEEE Trans.on Systems,1996,26(1):1-13.

[2]Colorni A,Dorigo M,Maniezzo V,et al.Distributed Optimiza-tion by Ant Colonies[A].Proceedings of ECAL91(European-Conference on Artificial Life)[C].Paris,1991:134-142.

[3]吴斌,史忠植.一种基于蚁群算法的TSP问题分段求解算法[J].计算机学报,2001,24(12):1 328-1 333.

[4]申春,彭秀增,罗凡,等.基于方向启发因子的蚁群算法[J].计算机科学,2006,33(8):175-176.

[5]张志民,张小娟,李明华,等.一种引入奖励与惩罚机制的蚁群算法[J].计算机仿真,2006,23(7):161-163.

[6]张曦煌,李彦中,李岩.基于加速寻径收敛的改进型蚁群算法[J].计算机工程与应用,2007,43(24):75-77.

[7]张毅,梁艳春.基于选路优化的改进蚁群算法[J].计算机工程与应用,2007,43(2):60-63.

蚁群系统算法 篇6

随着现代信息技术的发展,网络中的信息资源也越加丰富,如何在其中依据用户需求快速而准确地找到目标信息资源,即已成为目前亟待解决的研究问题。

蚁群算法是一种群智能算法,具体是由意大利学者DORIGO[1,2]等人通过研究自然界中蚁群寻找食物、并发现路径的过程而形成的一种进化算法。目前,蚁群算法主要用于解决常见的复杂组合优化问题,比如:TSP问题(Traveling Salesman Problem)、路径规划问题(Vehicle Routing Problem)等。算法表现出了多样性、正反馈和具有强大全局搜索能力等特点,但是,蚁群算法也同样存在着计算开销数值偏高、而且容易陷入局部最优等不足。

基于此,为提高蚁群算法的效率和搜索能力,本文设计提出一种基于改进蚁群的路径搜索算法,该算法在混合信息素更新策略,自适应挥发因子等方面研究生成改进,并设置了先行蚂蚁和后行蚂蚁,运用于网络知识路由问题中,有效地避免了蚁群搜索陷入局部最优,加快了收敛速度,同时也提高了搜索效率。仿真实验验证了改进算法的有效性和优越性。

1 语义Web与知识路由的概念

语义Web由Berners-Lee于2001年首次公布推出[3],其基本思想是提供基于机器可处理的语义元数据,并进行自动化的信息访问,协助人们在Web上发现知识、处理事务。而知识路由[4]的形成则来自语义Web,重点是协同运用用户的请求、网络信息相关性及语义信息,通过搜索准确快速地发现用户需要的目标知识。

2 蚁群算法描述

蚁群算法是在离散状态下,将算法中的解抽象成初始状态到目标状态的转移序列,其最优解就是转移序列中的最优值。蚁群中的每只蚂蚁可利用其路径上的信息素强度执行状态转移,一次搜索结束后,将即时更新信息素强度,由此群体就完成一次搜索;然后不断循环,蚂蚁间也将继续展开交流和协作,最后,得到强度最大的路径就是最优转移序列,即算法最优解。

蚁群算法的数学模型如下[5]:

首先,设蚂蚁数量为m,蚂蚁个体k在运动时的移动方向取决于各路径上的信息量浓度;Tabuk为蚂蚁k已走过的所有城市集合,且可以随着蚂蚁运动而动态调整;城市i和城市j之间的距离为ηij(t);t时刻ij路径上的信息素浓度为τij(t);α为信息启发式因子,反映了路径上的信息重要性,其值越大,蚂蚁间的协作性越强;β为期望启发式因子;allowedk为蚂蚁k所经过的集合。算法开始时,m只蚂蚁被随机地放置在平面中,各路径上的初始信息素浓度是一致的。那么在t时刻,蚂蚁k从城市i转移到城市j的概率pij(t)为:

为了避免蚂蚁运动过程中在路上残留过多的信息素而使启发信息被淹没,当每只蚂蚁遍历完成后,需要对残留信息进行信息素更新处理。由于更新策略不同,DORIGO为此提出了“蚁周模型”(Ant-Cycle)、“蚁量模型”(Ant-Quantity)及“蚁密模型”(Ant-Density)等3种模型。具体实现可分做如下描述:

1)蚁周模型

其中,Q为常数,Lk为t时刻蚂蚁k经过路径的长度。

2)蚁量模型

3)蚁密模型

3 基于改进蚁群的网络知识路由算法

3.1 基本蚁群算法的改进方法

基本蚁群算法在网络知识路由算法的求解过程中,具有收敛于局部最小值及收敛速度慢等缺陷,由此则直接降低了网络资源的搜索能力。为了提高算法的搜索能力和速度,本文设计的改进策略的功能优势要点可详述如下。

3.1.1 混合信息素更新策略

由于蚁周模型采用蚂蚁完成一个循环后再更新路径中信息素,是一种整体概念,而蚁量模型及蚁密模型是局部信息,因此,在研究中通常采用性能更优的“蚁周模型”进行更新,但是3个模型都具有各自合理的一面,也具有独特的优势,如果单纯只用某个模型来求解信息素更新,并非最佳策略,因此本文试图将3种模型混合使用,这样就使得在搜索过程中,对信息素更新时,既考虑了局部和整体的信息,又提高了算法的收敛性,同时也更加深入与全面。另外,为了避免算法出现停滞和扩散,研究中设定了信息素浓度最高值为τmax,最低值为τmin,大于最高值和小于最低值的浓度都将舍弃掉,保证了信息素浓度的稳定,使得各条路径上的浓度值不会相差太大,从而消除了随机搜索值带来的干扰。

3.1.2 自适应挥发因子

信息素挥发因子ρ对算法的全局搜索能力和速度有着重要的影响。如果ρ过小,随机搜索减弱,全局搜索能力提高,但是算法却易陷入某个局部最优点;反之,如果ρ较大,算法正反馈减弱,但算法全局搜索能力和收敛速度均将随之而降低。因此,采用自适应的方法来设置ρ值,数学公式可表示为:

其中,ρmax为最大值,这样可以提高算法全局搜索能力,找到最优解。

3.1.3 蚂蚁类型设置

在网络中为每个节点生成2种蚂蚁,即先行蚂蚁和后行蚂蚁。算法初期,由先行蚂蚁对网络中路径进行搜索,并记录走过的路径,到达目标节点后原路返回;后行蚂蚁则依据前述记录展开搜索,如果此时网络结构发生变化,后行蚂蚁将实时修改先行蚂蚁的路径记录和信息素,并对自身路径实施调整,最终找到最优路径。此方法通过先行蚂蚁和后行蚂蚁的协力合作,能在网络发生变化时,实时、完整、快速地找到网络路径,因而方法的适应性将会更强。

3.2 算法求解的过程分析

依据上文对算法的基本说明,对蚁群算法实现网络知识路由的具体求解过程可作如下描述:

1)初始化各项参数值,所有节点的路由表都获得有统一的可达节点的分布初始化。并设置节点间各条路径的初始信息素及循环次数,给每个节点分配先行蚂蚁和后行蚂蚁。

2)算法开始,先行蚂蚁按照状态转移公式选择下一个节点,并计算路径的代价,后行蚂蚁则根据该结果更新信息素,同时也实现路径修改;当所有的蚂蚁完成本次循环,进行全局信息素更新,找到全局最优解。

3)继续循环,循环暂停后,比较此次和前次的最优值,保留更优值,继续下一次循环。

4)直到循环次数大于设定值,停止循环,得到算法最优解,算法结束。

4 实验仿真及分析

在本次仿真实验中,研究采用MATLAB来构建模拟实验,通过对蚁群算法中的参数进行分析,设计得出实验程序。为了测试算法的有效性及优越性,分别进行了2次实验,实验一测试了本文改进算法的资源搜索能力,实验二通过对比分析基本蚁群算法和本文改进算法的实验结果,从而验证了本文算法的优越性。

4.1 实验一

为测试改进蚁群算法的有效性,在实验中,定制生成了一内含20个节点的虚拟社区,随机初始化20个节点的坐标值,具体数值分别为:节点1(603,1 171)、节点2(992,76)、节点3(1 281,187)、节点4(1 023,1 550)、节点5(984,1 442)、节点6(400,450)、节点7(802,393)、节点8(188,1 079)、节点9(285,980)、节点10(405,1 216)、节点11(560,218)、节点12(207,200)、节点13(1 372,578)、节点14(278,1 433)、节点15(663,1 224)、节点16(1 428,365)、节点17(1 297,1 214)、节点18(1 087,1 383)、节点19(46,712)和节点20(1 013,983)。

实验中,给出蚁群算法的系统参数设置如下[5]:α=1,β=5,信息素衰减因子ρ=0.7,蚂蚁数m=20,循环次数n=20,初始信息素设为1。20个网格资源节点的初始分布如图1所示。

通过仿真实验,找到了近似最优的路径,实验结果如图2所示。由图2可知,本文提出的改进蚁群算法具有良好的适应性和实用性,表明这是一种有效的改进算法。

4.2 实验二

在本次实验中,研究选取了基本蚁群算法和本文改进算法,并把2类算法发现的资源数的时间以及成功率进行了对比呈现,得出结果如图3、图4所示。在此,还对其结果给出了详细的分析,说明了本文改进算法的有效性和优越性。

4.2.1 算法的可靠性分析

在图3中,随着时间的推移,基本蚁群算法及本文改进算法发现资源数量都逐渐增加,并且通过对比可以看到,本文改进算法比基本蚁群算法能更快、且更早地到达最优搜索数量,反映出更快的进化速度,因此本文算法具有更优性能。究其原因在于本文算法采用了混合信息素更新策略,自适应挥发因子等改进方法,并设置了先行蚂蚁和后行蚂蚁,不仅资源搜索效率得到了提高,而且节约了搜索时间,加快了算法的收敛速度。

4.2.2 算法的优越性分析

从图4中可以看出,本文的改进算法比基本蚁群算法的资源发现成功率更高。具体分析可知,在本文的改进算法中,由于在蚁群搜索过程中采用了混合信息素更新策略,使得资源查找效率更高,也更准确;并且本文改进算法提高了全局搜索能力,能快速找到全局最优解,因此,本文算法在整体上提高了资源搜索的准确率,同时又保证了资源发现准确性,成功率也随即大大增加,而算法的优越性也就更为显著。

5 结束语

本文针对网络知识路由系统中资源搜索存在的问题,对基本蚁群算法开展了研究改进,提出了混合信息素更新策略,自适应挥发因子等改进方法,设置了先行蚂蚁和后行蚂蚁,有效地改善了基本算法存在收敛速度慢等缺陷。仿真实验说明本文的改进算法能快速、有效、准确地搜索到网络资源,是一种性能上更加优越的实用算法。

参考文献

[1]DORIGO M,VITTORIO M,ALBERTO C.The ant system:Optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):1-13.

[2]DORIGO M,GAMBARDELLA L M.Ant colony system:A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[3]Berners-Lee T,Connolly D,Swick R R.Web Architecture:Describing and Exchanging Data[EB/OL].[1999-06-07].http://www.w3.org/1999/04/Web Data.html.

[4]李英杰,王莉,余雪丽.本体驱动的知晓内容和上下文的知识路由研究[J].计算机工程与应用,2006(22):150-154.

蚁群算法概述 篇7

1、蚁群算法的基本原理

在自然界真实的蚁群觅食过程中, 蚁群在没有视觉的情况下通过个体之间交换信息素, 能够在较短的时间内找到食物和蚁巢之间的最短路径。生物学家的研究已经表明, 一只蚂蚁的记忆和智能是非常有限的, 但是, 由于蚂蚁之间可以通过一些信息素进行协同作用, 实现蚂蚁之间的信息交流和传递, 可以共同做出令人惊讶的行为。

为了阐述蚁群算法的机理[2], 下面以蚂蚁搜索食物的过程为例, 分析蚂蚁是如何通过上述的信息交流和传递的协同作用, 最终找到从蚁穴到食物源的最短路径的。

图1.1中, A为蚁穴, E为食物源, 从A到E有两条路径可走, ABE是长路径, ACE是短路径。蚂蚁走过一条线路以后, 在其路径上会留下信息素气味, 后来的蚂蚁就是根据留在各路径上的这种气味的强度选择应该移动的方向。图1.1 (a) 表示起始时的情况, 假定蚁穴中有4只蚂蚁, 分别用1, 2, 3, 4表示。开始时蚁穴中蚂蚁1, 2向食物源E移动, 由于线路ABE和ACE均没有蚂蚁通过, 在这两条路径上都没有原始的信息素气味, 因此蚂蚁1和2选择这两条线路的机会均等。假设蚂蚁1选择ABE线路, 蚂蚁2选择ACE线路, 并且假定各个蚂蚁行走的速度相同, 当蚂蚁2到达食物源E时, 蚂蚁1还在途中, 如图1.1 (b) 所示。蚂蚁2到达食物源以后就返回, 这时从B点返回也有两条线路的选择, 而哪一条线路上的信息素气味重, 就选择哪一条。因为蚂蚁1还在途中, 没有到达终点, 即此时在EBA线路上靠近B端处, 蚂蚁1还没有留下信息素气味, 所以蚂蚁2返回蚁穴的路径只有一个选择, 就是由原路返回。当蚂蚁2返回到A端时, 蚂蚁3开始出发, 蚂蚁3的线路选择将必定是ACE, 因这时ACE线路上信息素的气味比ABE线路上重 (ACE路径上已有蚂蚁两次通过) , 如图1.1 (c) 所示。当蚂蚁1到达食物源B点时, 由于同样的理由, 蚂蚁1所选择的返回线路必将是ECA, 如图1.1 (d) 所示。如此继续下去, 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象:沿路径ACE移动的蚂蚁越多, 则后来者选择该路径的概率就越大, 这正是蚁穴到食物源的最短路径。蚂蚁个体之间就是通过这种信息的交流达到最佳食物搜索的目的[3]。

在自然界中, 蚁群的这种寻找路径的过程表现为正反馈的过程, 与人工蚁群的寻优算法极为一致。如果我们将在优化求解中那些只具备简单功能的单元看作"蚂蚁", 那么上述寻找路径的过程可以用于解释人工蚂蚁的寻优过程。[4]

由以上分析可知, 人工蚁群和自然界蚁群的相似之处在于:两者优先选择的都是含"信息素"浓度较大的路径;人工蚁群和自然界蚁群的区别在于:

(1) 人工蚂蚁具有记忆或智能功能, 它能够记忆已经访问过的节点。

(2) 人工蚂蚁具有一定的视觉, 人工蚁群在选择下一条路径的时候, 并不是完全盲目的, 而是按一定的算法规律有意识得寻找最短路径。

(3) 人工蚂蚁的生活环境是时域离散的。

2、蚁群算法的特点

从蚁群算法的原理不难看出, 蚁群的觅食行为实际上是一种分布式的协同优化机制。单只蚂蚁虽然能够找到从蚁巢到食物源的一条路径, 但找到最短路径的可能性极小, 只有当多只蚂蚁组成蚁群时, 其集体行为才表现出蚂蚁的智能 (发现最短路径的能力) 。在寻找最短路径的过程中, 蚁群使用了一种间接的通信方式, 即通过向所经过的路径上释放一定量的外激素, 其它蚂蚁通过感知这种物质的强弱来选择下一条要走的路。

在蚁群的觅食行为中, 另一个重要的方面是自催化机制和解的隐式评估。自催化机制实际上是一种正反馈机制, 解的隐式评估指蚁群将先走完较短的路径。自催化机制和解的隐式评估相结合, 极大地提高了问题的求解效率。即对于越短的路径, 蚂蚁将越早走完, 从而使更多的蚂蚁将会选择该路径。当然在使用自催化机制时, 要努力避免早熟现象。在蚁群算法中, 使用外激素蒸发和随机状态转移来弥补自催化机制的缺陷。蚁群算法的主要特点概括如下:

(1) 采用分布式控制, 不存在中心控制。

(2) 每个个体只能感知局部的信息, 不能直接使用全局信息。

(3) 个体可改变环境, 并通过环境来进行间接通讯。

(4) 具有自组织性, 即群体的复杂行为是通过个体的交互过程中突现出来的。

(5) 是一类概率型的全局搜索方法, 这种非确定性使算法能够有更多的机会求得全局最优解。

(6) 其优化过程不依赖于优化问题本身的严格数学性质, 诸如连续性、可导性, 及目标函数和约束函数的精确数学描述。

(7) 是一类基于多主体的智能算法, 各主体间通过相互协作来更好的适应环境。

(8) 具有潜在的并行性, 其搜索过程不是从一点出发, 而是同时从多个点同时进行。这种分布式多智能体的协作过程是异步并发进行的, 分布并行模式将大大提高整个算法的运行效率和快速反应能力。

3、蚁群算法的应用

对蚁群算法的应用研究一直非常活跃。由于蚁群算法不依赖于问题的具体领域, 所以在很多学科有广泛的应用。

(l) 组合优化

继M.Dorigo首先将蚁群算法应用于TSP问题之后, V Maniezzo[5]等人将蚁群算法应用于QAP。最近几年, Gambardella[6], Taillard[7]和Stutzle[8]也发表了一些用蚁群算法求解QAP问题的文章。目前, ACO己是求解QAP问题最有效的算法之一。A Colomi[9]等人首先将蚁群算法应用于车间作业调度问题 (Jobshop Scheduling Problem, 简称JSP) 。Costa和Herz[10]提出增强的蚁群算法, 并将其应用于分配类型的问题。该算法在求解图的作色问题时, 得到了完全可以和其它启发式算法相媲美的结果。

(2) 通讯领域

蚁群算法在通讯网络领域 (特别是解决网络路由问题) 方面的应用研究受到越来越多学者的关注。由于网络中信息的分布式性、动态性、随机性和异步性与蚁群算法一非常相似, 如利用局部信息发现解, 间接的通讯方式和随机状态的转换。Di Caro和Dorigo己在相关的文献中将蚁群算法应用于网络路由问题, 并称这种算法为Ant Net[11]。

(3) 大规模集成电路的线网布局

在大规模集成电路的线网布局中, 需要根据电路和工艺的要求完成芯片上单元或功能模块的布局, 然后实现它们之间的互连。此问题可看作是寻找一个网格平面上两端点之间绕过障碍的最短路径问题。线网上的每个Agent根据启发策略, 像蚂蚁一样在开关盒网格上爬行, 所经之处便设置一条金属线, 历经一个线网的所有引脚之后, 线网便布通了[12]。应用蚁群算法, 可以找到成本最低、最合理的线网布局, 而且由于其本身的并行性, 比较适合于解决此类问题。

(4) 函数优化

虽然蚁群算法在离散空间的寻优能力十分突出, 但是对于连续空间的优化也是蚁群算法应用的领域之一, 也是评价蚁群算法性能的主要方法[13,14]。

此外, 蚁群算法在计算机领域、机器人设计与控制领域、数据挖掘、系统辨识、化工领域等方面也有广泛应用。特别需要指出的是:由于蚁群算法在求解复杂组合优化问题方面具有并行化、正反馈、鲁棒性强等先天优越性, 所以在解决一些组合优化问题时所取得的结果无论是在解的质量上, 还是在收敛速度上都要优于或至少等效于模拟退火以及其它一些启发式算法[2]。

摘要：本世纪50年代中期创立了仿生学, 人们从生物进化的机理中受到启发, 提出了许多用于解决复杂优化问题的新方法, 如遗传算法、蚁群算法、进化规划、进化策略等。研究成果已经显示出这些算法在求解复杂优化问题 (特别是离散优化问题) 方面的具有很强的优越性。本文将对蚁群算法做详细的介绍。