自适应蚁群优化算法

2024-05-28

自适应蚁群优化算法（共7篇）

自适应蚁群优化算法篇1

0 引言

供应链管理是对供应链商品流、物流、信息流、资金流以及合作者关系等规划、设计、运营、控制过程进行一体化的集成管理思想、方法和技术体系, 并且能够对市场的快速变化作出相应的反应。物流作为供应链管理过程的一个子过程, 可以解决生产点和消费点之间的计划编制、处理和货物存储控制等问题。实际上物流中心的货物流转控制是一个调度问题, 也是物流管理的一个核心问题, 这类问题通常都属于NP难问题。

在调度理论中, 供应链的调度问题是近几年才出现的。Shen和Norrie介绍了解决这个问题的几种方法, 但是由于这几种方法操作简单, 对于复杂的供应链优化问题具有其局限性。本文将自适应蚁群算法应用到供应链的调度中解决了这种局限性。

1 供应链调度描述及数学模型

物流过程作为供应链管理中的一个子过程一般分为五个部分, 订单到达、物件需求、物件到达、调度分派、订单交付。在物流过程中的一个关键环节就是资源分配, 即物件的调度分派问题, 如何对物流中心已有的物件进行分配, 并且使得需要按时交付的订单数目达到最优?物件的调度分配如图1所示。

本文使用自适应蚁群算法来解决这个组合优化问题。为此设物流中心有m个订单Oi (i=1, …, m) , 每份订单需要n种不同种类的物件Cj (j=1, …, n) , Oi需要Cj的数量为qij, 每份订单都要有一个到达时间ri和交付时间dr, 订单需要在货物延迟时间Lj内交付, 库存中已有的物件种类表示为Q, 每种物件的数量为qj (j=1, …, n) , 则物流调度过程的数学模型可以表示为:

minimize f (T) (Cost) (1)

Subject: $Ο_{i} \in 0 (i f Ο_{i} = \sum_{j = 1}^{n} q_{i j}) i = 1, \dots, m$ (2)

$q_{i j} \leq q_{j} \in Q i = 1 ‚ \dots ‚ m f (Τ) = \frac{1}{n_{Τ} + \frac{1}{\sum_{j = 1}^{n} | Τ_{j} |}}$ (3)

(2) 式表示已经分配好的订单, 其中订单Oi由物件类型及其所需要的数量组成, 符合条件的订单所需要的物件的数量不能超出库存物件的数量。

2 基于自适应蚁群优化的物流调度算法

蚁群算法由 M.Dorio等人首先提出, 它是一种新型的拟生态系统算法, 自适应蚁群算法是蚁群算法一种改进型算法, 解决了蚁群算法容易出现的一些问题, 如:计算时间较长, 容易出现停滞等问题。

2.1 基本蚁群算法原理

蚂蚁在觅食的过程中会在其走过的路径上留下蚂蚁特有的一种称为信息素的分泌物质, 信息素能够影响一定范围内的蚂蚁, 经过某些路径的蚂蚁越多, 信息素的浓度就越大, 后来蚂蚁选择这些路径的概率也就越大, 更加增强了这些路径上信息素的强度。蚂蚁的这些群体行为表现出了一种正反馈现象:某条路径上走过的蚂蚁越多, 后来就会有更多的蚂蚁选择这条路径。

2.2 基于自适应蚁群优化的物流调度算法实现

在物流调度问题中, 等待交付的定单由图表中的一些节点组成;物流调度过程中存在两个实体, 订单及其物件, 物流中心的调度问题实际上就是订单所需物件的分发交付过程, 物件交付给订单的过程可以使用蚁群觅食过程来模拟实现。每种类型的物件可以看作食物源, 订单可看作是蚁巢, 对应于每个蚁巢可以寻找不同数量的不同类型的食物, 不同的蚁巢也可以有相同类型的食物。解决物流调度问题最主要的一个方面就是每只蚂蚁所访问的节点的数目是不相同的 (在TSP问题中, 每只蚂蚁所访问的节点的数目是相同的) 。

假设有m只蚂蚁, n个蚁巢, 每个食物源放一只蚂蚁。蚂蚁的主要工作就是把食物C送到n个蚁巢中, 在蚂蚁将食物C搬到n个蚁巢的过程中, 蚂蚁采用自适应的伪随机比率选择准则来选取下一个蚁巢节点, 同时, 在路径上留下信息素τ, 当来自各食物源的蚂蚁所剩物件的数量为空或者是均不能满足剩余的订单需求时称为一次周游。每只蚂蚁从Ci个物件中取出qij个传送给订单, 其中i= (1, …, m) , j= (1, …, n) 。因为蚂蚁要去多个蚁巢, 所以蚂蚁根据概率公式 (6) 选择下一个蚁巢, 这里, τ (i, j) 表示物件Ci分配给订单j后留下的信息素浓度, η (i, j) 表示物件Ci分配给订单j的启发式因子, β表示启发式因子的相对强弱, 通常, η (i, j) 与订单的日期延迟有关, 我们取日期延迟的指数函数。

η (i, j) =edj (4)

其中, dj表示订单的延迟, 即实际日期与被要求的日期之间的差值。我们规定η (i, j) =1 (dj=0) 表示所需物件能够按时交付订单, η (i, j) < 1 (dj<0) 表示被延迟的订单, η (i, j) > 1 ( dj>0) 表示正在等待处理的订单。

在选择下一个订单节点之前生成q, 如果q的值小于等于q (λ (t) ) , 则根据公式 (4) , 从订单节点到所有可行的订单节点中找出τ (i, u) ·ηβ (i, u) 中延长时间最长的订单, 即为下一个要选择的订单;如果随机数q大于q (λ (t) ) , 则按公式 (6) 来选择下一个订单。

q (λ (t) ) =λ (t) /N (6)

其中, λ (t) ∈[2, N]表示第t次循环的平均节点分支数, N表示订单数。τ (i, u) 表示i与订单u之间的信息素量, η (i, u) 是启发式因子, β表示启发式因子的相对强弱。

这里Γ为禁忌表, 代表了第k只蚂蚁已经完成的订单或者是不需要物件类型Ci的订单。蚂蚁选择了要处理的订单后, 在链接物件i和订单j的路径上留下信息素, 设信息激素的蒸发系数为ρ (0<ρ<1) , 表示信息素的蒸发程度, 路径上信息素的更新按下式进行调整,

公式 (8) 表明了蚂蚁k在是否选择订单j时要根据物件Ci的数量q $_{i j}^{k}$ 是否满足订单j的数量qij需求进行选择;如果q $_{i j}^{k}$ ≥qij时, 值为μ·edj, 因为如果有物件Ci的数量能够同时满足两个订单的需求, 则需要根据订单的延迟时间dj选择将物件分配给哪个订单, 如果q $_{i j}^{k}$ ≤qij时, 物件Ci的数量不能满足订单j的需求, 则蚂蚁不能将物件Ci分配给订单j。

这里f (x) 是一个优化测试函数, 蚂蚁每完成一次游历都将结果存放在f (x) 中, 如果f (x+1) >f (x) , 则说明第x+1次游历要比第x次的优化结果要好, 此时, 信息素浓度应该增加, 否则, 信息素的浓度减少。

其中, (1-ρ) 表示信息素的消逝程度。

基于自适应蚁群优化的供应链调度算法描述如下:

3 仿真试验结果及其分析

设库存中有10种不同种类的物件, 有7份等待交付的订单, 每种不同种类的物件的数量分别为10, 每份订单所需要的物件的数量如表1所示。

τij的初值、α、β、ρ的值的变化对算法的结果, 算法运行时的稳定性等的影响很大, 因此本文分别对τij的初值, α, β, ρ的值进行多次试验, 最后结果表明, 当τij的初值为0.5, α=0.5, β=5, ρ=0.1时结果最优, 按时交付的订单为:3-7-4-2-5, 试验结果如表2所示;此时, 所交付的订单数目及其剩余的物件的数量达到了最优, 即按时交付的订单最多, 剩余的物件数量最少;算法的稳定性也比较好, 运行时间也相应减少了。

4 结束语

物流调度是供应链过程的一个关键的环节, 物件分派调度是物流调度的核心, 发挥着至关重要的作用。所涉及的调度算法能够有效地解决物流过程中物件的动态分派调度问题, 加快了物流中心物件的流通, 提高了工作效率。

参考文献

[1]Barbuceanu M, FoxM.Coordinating multiple agents in the supply chain[J].In:Proceedings of the Fifth Workshops on Enabling Technologyfor Collaborative Enterprises, WET ICE_96, IEEE Computer SocietyPress, 1996:134-141.

[2]Shen W, Norrie D H.Agent-based systems for intelligent manufactur-ing:a state-of-the-art survey[J].Knowledge and Information Systems, an International Journal, 1999, 1 (2) :129-156.

[3]Sousa J M, Palm R, Silva C, Runkler TA.Optimizing logistic processesusing a fuzzy decision making approach[J].IEEE Transactions on Sys-tems, Man, and Cybernetics Part A:Humans and Systems, 2003, 33 (2) :245-256.

[4]Colorni A, Dorigo M, Maniezzo V.Distributed optimization by ant colo-nies[A].Proc.1stEuropeanConf.Artificial Life[C].pans, France:Elsevier, 1991:134-142.

[5]胡小兵, 黄席樾, 等.一种新的自适应蚁群算法及其应用[J].计算机仿真, 2004, 21 (6) :108-109, 110-111.

[6]段海滨.蚁群算法原理及其应用.北京:科学出版社, 2005.

自适应蚁群优化算法篇2

随着机动车数量的不断攀升,随之而产生的交通拥挤与堵塞等现象越发严重,用户对车载导航系统的服务质量及性能等方面的要求不断提高。本文对蚁群算法加以改进,提出了基于蚁群算法的自适应路径导航算法,该算法不但充分地利用了蚁群算法的灵活性、稳定性、自启发性等良好特性,同时又克服了蚁群算法固有的缺陷(如收敛慢、易陷于局部最优等),而且,综合权衡了多个影响导航的主要因素的组合优化作用,求解最优路径,并获得了良好的导航效果。

通过对蚁群算法的分析与研究,对蚁群算法加以优化,提出了基于蚁群算法的自适应路径导航算法模型,并阐述了该算法选路和导航的决策原则、信息素的更新策略及道路拥塞、交通负载平衡情况的处理策略等,在理论上阐释了将蚁群算法应与导航系统中的原理与模型,丰富了导航算法的理论模型。在导航决策方面,算法采用模糊数学理论中的模糊评判的方法作为导航可行下一跳节点的理论依据,在模糊评判中充分考虑了影响导航的多个因素的综合作用,使得导航不再简单地依据最短路径这一单一因素来完成,增强了算法的寻优能力。同时,在使用各因素时,充分考虑了各个不同因素使用的量级不一致等情况,利用模糊数学领域中的隶属函数方法,将多个因素的量级统一到同一量级上来,有效地避免了因各因素量级的不同,而产生的低量级因素被掩埋现象的发生。在信息素更新策略上,算法给出了局部信息素更新、全局信息素更新以及相应的计算公式。通过对信息素的不同更新策略可以改善算法的收敛速度慢及易陷于局部最优的缺陷,在调节流量负载平衡方面,由于采用了多因素的综合评判方法,所以,优化后的蚁群算法具有很好的自适应性,能够自启发式的解决流量负载问题。

1 蚁群算法原理及模型

1992年M.Dorigo等人提出了一种新型的仿生进化算法——蚁群算法 (ant colony optimization)[1],蚁群算法源于自然界中真实蚁群行为的启发,自然界中单只蚂蚁的个体行为极为简单,然而,蚂蚁群体间却能够通过相互协作的群体行为寻找到蚁巢到食物之间的最短路径,并且能够根据路径情况的实时改变动态收索最短路径。

蚁巢为N(nest),蚂蚁的食物源为F(food),存在一条蚂蚁行走的路径(从蚁巢N至食物源F,反之亦然),见图1 (a),这条路径是蚂蚁间通过相互协作已寻找到的从蚁巢到食物源的当前最短路径。

如在蚂蚁的当前行进的路径上放置一个障碍物,将该路径截断,那么,在P2位置的蚂蚁要从N至F(或在P4的蚂蚁要从F至N)就不得不决定是向左转还是向右转,见图1(b)。蚂蚁因没有先前在2条备选路径上留下任何信息素或信息素的浓度很低,所以在P2点的蚂蚁向左转或是向右转的概率是相同的。由于路径P2P3P4比路径P2P1P4短,因此,沿P2P3P4行走的蚂蚁达到P4所需的时间要比沿着P2P1P4行走的蚂蚁所需的时间短,并蚂蚁原路往返,结果是在单位时间段内,沿着P2P3P4路径行走的蚂蚁的数量会高于沿着路径P2P1P4行走的蚂蚁的数量,每只蚂蚁都将在其所经过的路径上留下自己的信息素,这就使得在较短路径P2P3P4上的信息素数量的增长要比在长路径P2P1P4上的信息素数量的增长快。后续蚂蚁的选路受先前的蚂蚁留下的信息素的强度影响,在较短道路上的较高的信息素强度给予所有蚂蚁一个更强有力的刺激,因而在P2处的蚂蚁将向左转(在P4处的蚂蚁将向右转),后续的蚂蚁都会选择信息素强度高的路径行走,最终的结果是,所有的蚂蚁都会选择较短的路径,见图1(c)。从上面的描述可知,蚁群主要进行两项工作:根据路径上的信息素的强度来选择路径和更新所选路径上的信息素的数量。

以求解旅行商问题(traveling salesman problem, TSP)[2,3]为基准阐释蚁群算法模型。旅行商问题是一个著名的组合优化难题,其描述为:给定n座城市以及每对城市之间的欧氏距离,要求确定一条经过每座城市当且仅当仅经过1次的最短路径,其形式化定义如下:

设C={c1,c2,…,cn} 是n座城市的集合,P={ Pij | ci,cj∈C}是集合C中的元素两两连接的集合,dij (i, j=1,…,n) 是Pij的距离,G=(C, P)表示一个有向图,TSP的目标是从有向图G中找到一条长度最短的环,即一条对于C={c1, c2, …, cn}中n个城市访问且仅访问一次的最短封闭曲线。

为了定义蚁群算法模型引入如下变量:

n定义为TSP规模,即城市的总数;

m定义为蚁群中蚂蚁的总数, $m = \sum_{i = 1}^{n} b - i (t);$

bi(t)定义为t时刻位于元素i上的蚂蚁数目;

τij (t)定义为t时刻链路(i, j)上残留的信息量;

dij定义为城市i与城市j之间的欧氏距离;

ηij(t)定义为启发函数,其缺省值为ηij(t) =1/dij;

pijk(t)定义为状态转移概率,其值的大小决定了位于节点i上的蚂蚁倾向于转向下一可行节点j的程度;

α定义为信息启发式因子,用于表示信息素的相对重要性,反映了蚂蚁在行进过程中积累的信息对蚂蚁行进所起的作用,其值越大,蚂蚁越倾向于选择其它蚂蚁经过的路径,蚂蚁间的协作性就越强;

β定义为期望启发式因子,用于表示能见度的相对重要性,反映蚂蚁在行进过程中启发信息在蚂蚁选择路径过程中的受重视程度,其值越大,状态转移概率就越接近于贪心规则。

蚁群算法模型描述如下:在蚂蚁寻路的初始时刻,各条被选路径上的信息素的量是均等的,设τij (t)=常量,这意味着蚂蚁选择每条被选路径的概率是相等的。与自然界中的实际蚂蚁不同,人工蚂蚁具有一定的记忆功能,可用禁忌表TB记录蚂蚁k(0<k≤m)当前所走过的城市信息,城市集合随着禁忌表TB的变化作动态调整。随着时间的推移,路径上的信息素的强度将发生很大的变化,在寻路过程中,个体蚂蚁k将根据各条备选路径上的信息量的多少、路径的信息启发式因子、启发函数以及期望启发式因子来计算状态转移概率p。在t时刻,蚂蚁k由城市i转移到城市j的状态转移概率,由式(1)计算所得。

$p_{i j} k (t) = {\begin{cases} \frac{[τ_{i j}]^{α} \times [η_{i j}]^{β}}{\sum_{S \in a l l o w e d_{k}} [τ_{i j}]^{α} \times [η_{i j}]^{β}} \\ 0 其他 \end{cases} (1)$

式中:allowedk={C-TB}为蚂蚁k下一步被允许选择的城市;C为所有与节点i存在路径的城市集合;TB为禁忌表,表示已被蚂蚁k访问过的城市的集合;α为信息启发式因子,用于表示路径的相对重要性,α≥0;β为期望启发式因子,用于表示能见度的相对重要性,β≥0 。

对蚂蚁k,当2城市之间的距离dij越小,根据式ηij(t) =1/dij,则启发函数ηij(t)的值就越大,状态转移概率p $_{i j}^{k}$ 的值就越大。可见,该启发函数ηij(t)意味着蚂蚁从城市i转移到城市j的期望程度。

2 基于蚁群算法的导航算法

2.1 导航因素值规格化

影响导航的主要因素有:路经长度、路径宽度、通行时间和通行时间抖动等,这些因素即可单独使用,又可组合使用。在组合使用时,往往存在多个因素的因素值的量级不一致情况,如路径长度以公里作为单位,量级多为一到几十,路径宽度以米为单位,通常取值为15～40之间,而通行时间的单位是分钟,通常是几到几百分钟之间。由于不同的因素在取值上存在很大差异,通常会出现值小因素的评价作用被掩埋的情况,无法完全体现所有影响导航的因素的真实约束作用。例如,路径长度取值为10(即10 km),而通行时间取值是100(即100 min),在进行综合评判时,有时会发生100会将10淹没的现象,这将减弱或者屏蔽路径长度量值10的评判作用。因此,在进行模糊评判之前,首先要对各因素取值进行统一的规格化[4],将各因素取值统一到一致的量级上来,本算法利用隶属函数方法来解决量级统一的问题,通过使用隶属函数将各个因素的取值都映射到[0,1],缩小因素值之间的量级差距,这样各因素就具有了接近相同的评判作用,因此,可以有效地避免某些影响因素的评价作用被掩埋的情况发生。在算法中隶属函数采用梯形分布隶属函数形式,其中路径宽度隶属函数采用梯形分布的偏大型,见式(2),路径长度、通行时间、通行时间抖动隶属函数都采用梯形分布的偏小型,见式(3)。各因素的评判值均源于隶属函数值,且均为越大越优型。由于路径宽度隶属函数采用梯形分布偏大型,因此路径宽度值越大,意味着隶属函数值就越大,即隶属函数值与路径宽度值成正反馈关系,路径长度、通行时间和通行时间抖动均隶属函数采用梯形分布偏小型,所以,其值越小,隶属函数值就越大,即隶属函数值与路径长度,通行时间和通行时间抖动因素值成负反馈关系。

$\begin{array}{l} A (x) = {\begin{cases} 0 x < a \\ \frac{x - a}{b - a} a \leq x \leq b \\ 1 x > b \end{cases} (2) \\ A (x) = {\begin{cases} 1 x < a \\ \frac{b - x}{b - a} a \leq x \leq b \\ 0 x > b \end{cases} (3) \end{array}$

2.2 算法导航原则

在选路的过程中,位于节点i上的蚂蚁(将车辆视为蚂蚁),按式(1)计算每一个下一可行节点的转移概率,然后选择转移概率高的结点作为下一转向节点。

算法中利用模糊数学理论中的综合评判的方法来确定公式(1)中的ηij值,以取代缺省值1/dij(节点间距离的倒数)。ηij的值越大,表示该路径的综合评价结果越优,蚂蚁越倾向于选择该路径,从而达到一个良好的导航效果。ηij值的计算方法如下:

1) 确定因素集合U={u1,… ,u4},被评判路径的各因素构成的集合。

2) 给出最优路径的权重向量,W=(u1,u2,u3,u4)。

3)将当前可选路径的各因素的权重向量A与最优路径的权重向量W进行欧几米德贴近度计算[5];

$Ν (A, W) ≙ 1 - \frac{1}{\sqrt{n}} (\sum_{i = 1}^{n} (A (u_{i}) - W (u_{i}))^{2})^{1 / 2} (4)$

4) 将计算所得的贴近度值作为ηij值,按照择优的选路原则,确定转向的路径。

2.3 算法局部信息素更新策略

局部信息素更新是对蚂蚁所经过的当前路径进行信息素更新,对于每只蚂蚁而言,在其寻路行进的过程中会对其所经过的路径上的信息素进行更新。按式(5)对信息素进行局部更新。

$τ (i ‚ j) \leftarrow ρ \times τ (i ‚ j) + (1 - ρ) \times (k η_{i j}) (5)$

式中:ρ为信息素残留系数,为了避免信息素的无限累积,通常ρ取值为[0,1),(1-ρ)则表示在t和t+1时刻之间信息素挥发的程度,本算法通过对局部信息素进行更新,适度地改变了路径上信息素的强度,避免蚂蚁寻路陷入局部最优;k为一正实数系数;ηij为启发函数,通过对局部路径上的路径长度、路径宽度、通行时间和通行时间抖动的模糊评判来获得ηij值。

2.4 算法全局信息素更新策略

全局信息素更新是在整条线路上进行信息素更新。当所有蚂蚁均完成了从出发节点到目的节点的寻路过程之后,需要使用全局信息素更新策略对最优线路中的所有路径上的信息素浓度进行更新,以便增强最优线路上信息素的强度,使得该最优线路能够得以保留下来,以获得很好的收敛效果。按式(6)进行全局信息素更新。

$τ_{w} (i ‚ j) \leftarrow ρ \times τ_{w} (i ‚ j) + (1 - ρ) \times (k_{w} η_{w}) (6)$

式中:kw为全局系数,kw≥0,ηw为全局启发函数,利用全局的路径长度(线路中所有路径长度之和)、路径宽度(线路中所有路径宽度的最小值)、通行时间(线路中所有路径通行时间之和)、通行时间抖动(目的节点的抖动时间)来计算ηw,全局信息素更新能有效地调节最优线路上的信息素强度,提高蚁群算法的收敛速度,同时,由于采用了多因素综合评价方法,可以有效地解决或者避免道路拥塞等交通问题。对于最优线路之外的其它线路按照式(7)进行全局信息素更新。

$τ_{w} (i ‚ j) \leftarrow ρ \times τ_{w} (i ‚ j) (7)$

2.5 算法拥塞控制及负载均衡策略

在算法中,如位于某节点的车辆有2个及以上的可行下一跳节点,算法将计算得到的转移概率值较大的前2条路径保存下来,转移概率最大的路径作为主选径路,另一条路径作为可行路径(备选路径),当首选的主路径上出现负载过重的情况时,通行时间、通行时间抖动等都会随之增加,根据多因素约束算法的选路原则可知,期望启发式因子η将变小,使得主路径的转移概率随之减小,当主路径的转移概率低至与备选路径转移概率相当时,(采用两个转移概率之差的绝对值小于某一极小常量e来判定,1>e≥0),即设置2条路径具有相同的转移概率,因此,后续的流量就可以经过备选路径进行分流,达到拥塞控制、负载均衡目的,使得算法具有动态的自适应能力。

3 算法仿真实验

3.1 算法仿真结构图

路径仿真结构图,见图2,导航中所使用的评判因素为:路径长度、路径宽度、通行时间、通行时间抖动。每条路径的各因素值见表1。

3.2 模糊综合评判

根据式(2)计算路径宽度的隶属函数值[5],根据式(3)计算路径长度、通行时间和通行时间抖动的隶属函数值,结果见表 2。其中,式(2)和式(3)中 a=0,b=max(ui)。

节点1到节点2(路径R1)的权重向量为

A=(0.33,1,0.6,0.75)

节点1到节点7(路径R8)的权重向量为

B=(0.66,0.5,0.4,0.25)

位于节点1的蚂蚁(车辆)依据式(1)计算的转移概率来选择它的可行下一节点。式(1)中的启发函数值η由路径宽度、路径长度、通行时间及通行时间抖动等因素的模糊评判值确定。

在本拓扑结构中,基于最优路径的权重向量:W=(0.9,0.95,0.9,0.8),按式(4)计算,位于节点1的车辆转向节点2和节点7的启发函数η值,分别为

节点1到2:N(A,W)=0.676,对应的η=0.676

节点1到7:N(B,W)=0.25,对应的η=0.549

从结果可知,节点1到2的启发函数值(0.676)大于节点1到7的启发函数值(0.549),因此,在多因素综合评判情况下,节点1到2的路径优于节点1到7的路径,因此,位于节点1的车辆首选可行节点2作为下一跳节点。按此进行仿真实验,仿真实验中各参数的设置值[6]:α=2、β=3、ρ=0.7、Q=100、k=1、kw=1、τ0=0.1、m=10、n=10、t=0、nc=0 、ncmax=100。将所得实验结果与基本蚁群算法实验结果(仅采用路径长度作为评价因素,较短路径首选)进行对照,见表3:

3.3 算法仿真实验结果与分析

由表3可见:对于相同的路径策略,2种算法分别得出不同的路径集合,多因素评判算法的综合评判结果在导航方面优于基本蚁群算法,同时,该算法在迭代次数方面,也存在一定的优势,但多因素评判算法具有计算时间相对较长的不足之处。

4 结束语

本导航算法充分权衡了影响导航的主要因素的综合评判作用,因而能够求得一条综合评判最优的导航路径,并能够根据路径的实时情况,自适应的进行调整并获得新的最优路径,以满足用户对导航系统高服务质量的需求。

摘要：针对时常发生和不断加剧的交通拥挤、堵塞等情况,研究一种动态的、自适应的导航算法,以达到对车辆进行合理有效的路径导航和路径规划的目的。这一算法是在蚁群算法的基础之上,辅以多因素综合评判的方式,改进蚁群算法的评判标准,构建动态导航模型。以该导航模型为基础,通过仿真实验进行求解,仿真实验中将路径宽度、通行时延等随机因素考虑在内并进行综合权衡,使得动态导航的结果具有现实中的指导意义。数据实例表明,该导航算法是可行的、有效的,具有良好的导航效果,可为实际的导航系统提供有力地决策支持。

关键词：蚁群算法,模糊综合评判,导航算法

参考文献

[1]Dorigo M,Gambardella L M.Ant colonies for thetraveling salesman problem[J].Bio-system,1997,43(2):73-81.

[2]杜长海,黄席樾,杨祖元,等.改进的蚁群算法在动态路径诱导中的应用研究[J].计算机工程与应用,2008,44(27):236-239.

[3]刘桂青.改进蚁群算法在车辆路径问题中的应用[J].广西民族大学学报:自然科学版,2010,16(2):50-53.

[4]刘伟,史岚.基于蚁群算法的多参数模糊评判的路由算法[J].微计算机应用,2010,31(10):14-19.

[5]杨纶标,高英仪.模糊数学原理与应用[M].广州:华南理工大学出版社,2005.

基于自适应蚁群算法的分析和延展篇3

蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合,这种算法在构造解的过程中,利用随机选择策略,这种选择策略使得进化速度较慢,正反馈原理旨在强化性能较好的解,却容易出现停滞现象。这是造成蚁群算法的不足之处的根本原因。因而从选择策略方面进行修改,采用确定性选择和随机选择相结合的选择策略,并且在搜索过程中动态地调整作确定性选择的概率,当进化到一定代数后,进化方向已经基本确定,这时对路径上信息量作动态凋整。缩小最好和最差路径上的信息量的差距,并且适当加大随机选择的概率,以小于l对解空间的更完全搜索,从而可有效地克服基本蚁群算法的不足,此算法属于自适应算法。该算法按照下式确定蚂蚁由所在转移到下一个城市S。

其中,q∈(0,1),τ是(0,1)中均匀分布的随机数。当进化方向基本确定后,简单的放大(或缩小)方法调整每一路径上的信息量,该方法不仅能够加快收敛速度,节省搜索时间,而且能够克服停滞行为的过早出现,有利于发现更好的解,这对于求解大规模优化问题是有益的。通过标准蚁群算法的对比,学者就提出了一种自适应蚁群算法。

2 自适应的信息更新策略

蚂蚁在行进过程中常常选择信息量较大的路径,但当许多蚂蚁选中同一条路径时,该路径中的信息量就会陡然增大,从而使得多只蚂蚁集中到某一条路径上,造成一种堵塞和停滞现象,表现在使用蚁群算法解决问题时就容易导致早熟和局部收敛。为了解决这一问题,提高蚁群算法的全局收敛能力和搜索速度,许多文献提出了各种不同的更新信息量的策略,如引言中所谈到的蚁群算法,在更新信息量时:1)只要蚂蚁遍历时选择此路径就更新其路径上的信息量;2)只让最优适应度的路径上的信息量增强,而其余路径上的信息量被削减;3)基于等级变化的算法,让适应度相对较好的蚂蚁固定在若干条路径上,根据其解的优劣程度决定信息量的增加幅度。这些算法虽然各不相同,但主要都采用固定信息量增减的比例来进行信息量的更新,都忽视了解的分布特征,在一定程度上虽对蚁群算法的特性进行了一定的改进,但这一般只适合于处理较小规模的问题,为了解决较大规模的问题,这里从解的分布状态入手,提出了一种新的自适应的信息量更新策略。

当问题规模较大时,由于信息量挥发系数的存在,使那些从未被搜索过的路径上的信息量减小到接近于0,从而降低了算法在这些路径上的搜索能力,反之,当某条路径中信息量较大时,这些路径中的信息量增大,搜索过的路径再次被选择的机会就会变得较大,这也影响了算法的全局搜索能力,此时通过固定地变化挥发系数虽然可以提高全局搜索能力,但却使算法的收敛速度降低,因而提出一种自适应的改变τ值的方法,将信息素更新公式:

这里c为常数,根据解的分布情况自适应地进行信息量的更新,从而动态地调整各路径上的信息量强度,使蚂蚁既不过分集中也不过分分散,从而避免了早熟和局部收敛,提高全局搜索能力。

3 小结

自适应蚁群算法作为一种新的生物进化算法,目前还没有遗传算法、模拟退火等那样形成较系统的分析方法和坚实的数学基础,各种参数的确定也没有一定的理论指导,相信经过进一步研究,自适应蚁群算法在求解人类基因的问题中的应用前景会更广阔,将会同其他生物进化算法一样获得越来越广泛的应用和坚实的理论根据。

参考文献

[1]忻斌健,吴启迪,等.蚁群算法的研究现状及其应用[A]//中国控制与决策学术年会论文集[C],2001.

[2]张纪会,徐心和,胡勇,等.带遗忘因子的蚁群算法[J].系统仿真学报,2000(2):22-30.

[3]张纪会,徐心和,胡勇,等.一种新型的模拟进化算法:蚁群算法[J].系统工程理论与实践,1999(3):84-87.

[4]唐飞,膝弘飞,等.十进制整数编码遗传算法的模式定理[J].计算机科学,1999,12(6):54-56.

自适应蚁群优化算法篇4

在智能光网络中,动态RWA(路由与波长分配)问题的核心是控制平面为客户业务请求实时地选择合适的路由和分配波长资源。动态RWA问题的优化目标是降低网络连接的阻塞率和提高网络资源的利用率。RWA问题属于NP-C问题[1],常见的解决思路有两种:(1)分别处理路由选择问题和波长分配问题;(2)是采用分层图模型的并行计算方案。分层图模型简化了动态RWA问题的复杂性,对于解决有波长一致性限制的RWA问题较为有效[2],但缺点是扩大了网络规模,在解决大型网络问题时耗费时间较长;同时对带波长转换能力的RWA问题,优化效果不太明显[3]。而第一种方案结合启发式算法对解决此问题有较好的效果。

ACO (蚁群优化)算法是由M.Dorigo和V.Maniezzo等从蚁群的觅食行为中提炼出来的[4]。蚁群算法的本质是运用分布式并行计算和正反馈原理寻找最优解。但蚁群算法存在过早收敛、容易陷入停滞和全局搜索能力不足等缺点。信息素挥发系数ρ对算法全局收敛性和跳出局部最优解的影响较为突出。段海滨等对蚁群算法的全局收敛性进行了深入的理论研究[5],提出了对挥发系数采取阀值函数ρ(t+1)=φ·ρ(t)(式中,φ为挥发约束系数,且φ∈[0,1])的改进方法。本文针对光网络中动态RWA问题的求解,提出一种改进的ADACO(自适应蚁群优化)算法,将挥发约束系数定义为一种渐进的过程,与算法当前的迭代和算法总的迭代次数相关,使φ的值随着迭代次数的增加逐渐减小,从而获得较好的算法性能。

1基于 ADACO 算法的 RWA机制

1.1改进的 ADACO 算法

在传统的ACO算法中,全局信息素更新规则可以表示为

式中,Δτij(t,t+n)为路径(i,j)上产生的信息素增量;τij(t,t+n)为更新后路径(i,j)上的信息素浓度;τij(t)为路径(i,j)上累计的信息素;ρ为[0,1]区间的常数,为信息素的挥发系数。

在优化求解过程中,若ρ取值过大,会降低算法全局搜索能力;若ρ取值过小,会减慢算法的收敛速度,使优化结果陷入局部解。本文将ρ改为可变函数ρ(t+n),以平衡算法的全局搜索能力和收敛速度。改进后的信息素更新规则如下:

式中,φ为挥发约束系数,且φ∈[0,1]。为了避免ρ变化波动过大,将φ表示为一个渐进的过程,其函数关系为

式中,w为当前迭代步数;wmax为算法总的迭代次数。由于w≤wmax,满足φ∈[0,1],且φ(w)为单调递减函数;随着迭代步数的增加,φ(w)的值逐渐减小,调节ρ动态更新。

1.2改进的 ADACO 算法在 RWA中的应用

将改进的ADACO算法应用到RWA中,主要实现步骤如下:

(1)业务请求到达时,需要进行路由选择,按文献[6]提出的规则进行下一跳j的选择。

(2)下一跳j选择结束后,采用式(5)对链路(i,j)进行信息素局部更新:

式中,τinjew为更新后的链路的信息素;τiojld为累积的信息素;ε为[0,1]区间的常数;Δτij为链路上产生的信息素增量。

(3)待所有蚂蚁均进行完一次搜索后,运用式(2)对所建立的路径进行全局信息素更新。

(4)当迭代次数达到预设最大值时,从搜索到的路由集合中选取一条路径作为最佳路由,以路径信息素浓度最大结合路径节点数最少作为选取标准。

2仿真与性能分析

在不同网络拓扑上进行了数值仿真,分析和比较ADACO算法与传统的Dijkstra算法对网络阻塞率性能的改善,波长分配均采用FF(首次命中)算法。仿真的网络结构分别是14个节点、21条链路的NSFNET(国家科学基金会网络)和16个节点、32条链路规则对称的Mesh网络[7]。为了便于仿真,设定网络拓扑中相邻节点间采用4条链路相连接,对每一条链路的可用波长数目设定为6。算法的仿真参数设置如下:ρ的最小值ρmin =0.4,ρ0 =0.6,其他参数按文献[6]设置。仿真结果如图1所示。

(a) Mesh 网络(b) NSFNET

从图1(a)可以看出,对于规则对称的Mesh网络:相比较于Dijkstra+FF算法,本文提出的改进算法在改善网络阻塞率性能方面效果明显。特别是在业务强度较小时,采用ADACO+FF算法,网络阻塞率几乎为0;在增大业务负载的过程中,改进算法的阻塞率性能改善能力逐渐下降;当业务强度趋于网络最大承载能力时,由于网络波长资源有限,网络性能已发挥到最大,此时两种算法的网络阻塞率均趋于0.6。从图1(b)可以看出,对于NSFNET:改进算法对降低网络阻塞率也有明显的效果,仅略逊于同一算法对Mesh网络的改善效果。当业务强度较小时,改进算法对网络阻塞率性能改善明显;随着业务强度的增大,ADACO+FF算法对阻塞率性能改善能力降低,但仍优于传统的Dijkstra+FF算法;当业务强度趋近于网络最大承载能力时,受到波长一致性要求和网络资源的限制,算法对阻塞率性能的改善不太明显。与Dijkstra+FF算法相比,ADACO+FF算法在Mesh网络和NSFNET中阻塞率的改善量最大分别为0.3和0.2。

3结束语

自适应蚁群优化算法篇5

蚁群算法[1](Ant Colony Optimization,ACO)最早成功应用于解决NP难题中著名的旅行商问题(traveling salesman problem,TSP)。这是一种基于种群的启发式仿生类并行计算机制的智能进化算法。但当群体规模较大时,要找出一条较好的路径需要较长的搜索时间。另外,为了加速收敛,Ant-Q System让信息量最大的路径对每次路径的选择和信息量的更新起主要作用。由于强化了最优信息的回馈,蚁群算法当进化到一定代数后就容易因为较优解的信息素含量不断强化使得蚂蚁大量聚集于较少的几条路径上,会导致早熟、停滞现象,使得到的最优解只是局部最优的。由于蚁群算法有优良的鲁棒性,可以结合其它算法加以改进。有人就针对一类带聚类特征的TSP问题,提出了一种新型的带聚类处理的蚁群算法[2],将TSP问题分解成许多小规模的子问题(子问题数目与城市的聚类数相等),然后利用蚁群算法对每个子问题并行求解,并将所有子问题的解按一定规则合并成待求解问题的解。但通过自适应地从聚类分布的TSP城市之间的动态选择路径概率,来实现全局优化最优解方面的研究很少。

本文着重从应用蚁群算法求解TSP时,首先对城市样本空间预先进行聚类划分,然后在全局优化的实现过程中,当出现早熟、停滞的趋势时,能够比较迅速地按照样本空间的距离分布平衡情况,全局调度,跳出局部最优解,动态地调整选择路径概率,最后找到TSP问题的全局最优解方面作了一些探索性研究。

1 基本蚁群算法

设C={C1,C2,…,Cn}是n个城市的集合,L={lij|Ci,C⊂C}是集合C中元素(城市)两两连接的集合,dij(i,j=1,2,…,n)是lij的距离:

G=(C,L)是一个有向图,TSP问题的目的是从有向图G中寻出长度最短的Hamilton圈。

下面公式表示在t时刻蚂蚁k由元素(城市)i转移到元素(城市)j的转移概率:

式中,allowed={C-tabuk}表示蚂蚁k下一步允许选择的城市,α为信息启发式因子,β为期望启发式因子。

ηij(t)为

启发函数,其表达式如下:

式中,dij表示相邻两个城市之间的距离。对蚂蚁k而言,dij越小,则ηij(t)越大,转移概率也就越大。显然,该启发函数表示出了蚂蚁从元素(城市)i转移到元素(城市)j的期望程度。

算法对蚁群经过的每条路径进行一次更新,其更新公式为

其中ρ表示信息素量的挥发系数,Δτ表示本次周游中边上信息素的增量。如果最优组蚂蚁没有经过边,则Δτ为零;否则取与解的质量相关的数。

信息素更新策略有不同种类,通常采用Ant-Cycle模型作为基本模型,其表达形式如下:

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

2 K平均聚类算法

聚类分析是按不同对象之间的差异,根据特定的准则做模式分类,其应用面相当广泛。大致分"分类数目未知"和"分类数目已知"两类问题。聚类分析方法比较多,比如对于"分类数目已知"聚类算法有K-均值算法,ISODATA算法,修正的ISO.DATA算法,模拟退火算法等[2]。本文采用的K平均聚类算法又称距离平方和最小聚类法。通过聚类分析能有效地对TSP问题中的城市样本空间的全局分布情况,做出很好的区分。

K平均聚类算法具体步骤如下:

(1)假设要聚成K个类。由人为决定K个类中心Z1(1),Z2(1),…,Zk(1)。

(2)在第k次迭代中,样本集{Z}用如下方法分类:

对所有i=1,2,…,K,i≠j

若,则。

(3)令由(2)得到的Sj(K)的新的类中心为Zj(k+1),令最小。j=1,2,…,K。则中的样本数。

(4)对于所有的j=1,2,…,K,若Zj(k+1)=Zj(k),则终止。否则goto(2)。

3 改进的蚁群算法

3.1 对TSP预处理

使用K平均聚类算法对TSP问题中的城市样本空间做预处理。按城市样本的横坐标和纵坐标,在两个维度上作聚类分析。设n为TSP的城市数目规模,把这n个城市分成n1和n2距离分布差异较大的两个部分。如下图是tsp225聚类后的结果。

3.2 改进的蚁群算法原理和可行性

普通蚁群算法TSP计算时,当蚂蚁周游NC代还没有更优解时,便会陷入局部最优解。在此时,如果还是按照固有算法运算,按式(1)的转移概率判断,仍旧是在当前城市附近局部跳转,无法达到全局均衡。所以如果当连续运算到NC代还没有更优解时,我们动态让下一跳到距离此城市尽量远的随机的某一城市,同时令挥发系数ρ恢复到初始值,这样就可实现全局平衡,而且兼顾快速收敛。

跳转的策略如上图所示,当前城市在N1簇时,那么随机跳转到N2簇,反之,如果当前城市在N1簇时,那么随机跳转到N1簇。由于N1、N2簇经过了二维聚类分类,在距离上具有很好的分布均衡性。所以跳转也就具备了城市分布的全局性。

3.3 改进的蚁群算法TSP算法描述的具体步骤:

(1)参数初始化:α、β、ρ、Q、tabuk、t=0,Nc=0(Nc为迭代次数),设置最大循环次数Max(Nc)。按式(1)计算城市之间的距离。初始化各边上的信息素τij(i,j=1,2,…,n),通过实验取将m只蚂蚁置于出发城市S上。

(2)启动蚁群,按式(2)计算的概率用轮盘法随机选择下一个路径点,若此城市到其相邻城市的路径上的信息素值均为0,则回馈到上一个搜索的路径点,并将其放入tabuk。同时,当运行Nc=k代仍没有更优解,则按上面改进原理,跳出局部,随机跳转到另一簇中的一个路径点,同时令挥发系数ρ等于初始值。

(3)tabuk未满,重复(2),直到蚁群到达终点城市G。

(4)对蚁群搜索到的路径进行交叉运算,记录周游最优蚂蚁和全局最优蚂蚁的路径信息。

(5)令t=t+l;Nc=Nc+l,根据式(3)和式(4)更新各条路径上的信息素。如果产生了最短路径,则减少信息素的挥发,获得更多的启发信息。如果连续两代没有产生更好路径,则加快信息素的挥发,减少信息素的作用。将各条寻优路径上可能的残留信息素数量限制在[τmin,τmax]。[τmin]可以有效地避免算法停滞。可以避免某条路径上的信息量远大于其它路径,使所有的蚂蚁都集中到同一条路径上面,从而限制了算法的扩散。

(6)若蚁群全部收敛到一条路径或达到最大循环次数,则循环结束,输出最佳路径,否则到(2)。

4 算法实例

算例对TSPLIB的st70、TSP225、eil101、a280进行了TSP计算,初始化参数设置为:m=10,计算代数Nc=2000,α=1,β=5,ρ=0.5,Q=100,τmin=0.1,τmax=0.9。运算6次后没有更优解,则路径转移。通过改进的蚁群算法与普通蚁群算法进行对比实验,得到如下实验结果:

由表可知,本文提出的改进蚁群算法与基本蚁群算法相比,可实现快速收敛,最优解更小,全局搜索速度和优化性能均得到了明显改善。但当城市数量规模比较小时,优势并不明显,规模变大时,效果显著提高。

下面以TSP22为例,对比说明改进蚁群算法与基本蚁群算法收敛情况。

由上图可见,改进算法第431代就收敛到最优解4186.99,而普通算法要1767代才能收敛到最优解4221.74。

5 结论

本文提出了一种采用聚类理论改进基本蚁群算法的新思路,具有良好的可操作性。实例仿真证明了这种新理论对蚁群算法全局优化性能改善的可行性,可以使该算法最优解优化获得一定程度的提高,有效地克服了基本蚁群算法收敛速度慢、易限于局部最优解的缺陷。

摘要：本文提出样本空间经过K-均值聚类算法聚类加工处理后,算法通过动态地调整选择路径概率,优化TSP求解过程中解的分布均衡性,可以在加速收敛和防止早熟、停滞现象之间取得很好的平衡。这种新的算法提供了在样本空间预处理情况下,动态自适应地解决TSP问题最优解的新方法。比起普通蚁群算法,此算法对大规模数据的最优解的求解更有显著效果。

关键词：聚类,K-均值聚类算法,调整路径,蚁群算法,旅行商问题

参考文献

[1]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.

一种新的自适应蚁群算法及仿真篇6

蚁群算法(ant colony algorithm)是近年来刚刚诞生的一种随机优化方法,自问世以来表现出了强大的生命力。较之以往的启发式算法,在搜索效率和算法的时间复杂性上都取得了令人满意的效果。蚁群算法是意大利学者Dorigo等在研究组合优化问题计算机智能解决方法时的一项研究成果,主要是从蚂蚁觅食时的路径选择机制中得到启发的,通过蚂蚁之间的信息传递而达到寻优的目的。该算法已被其它领域的专家所接受,并运用到诸如TSP问题、Job-Shop排序问题、图染色问题、车辆调度问题等领域当中,均取得了较好的结。在许多方面还表现出相当好的性能。

2、蚁群算法的基本原理

2.1 蚁群行为描述

根据仿生学家长期的研究发现:蚂蚁虽没有视觉,但运动时会在路径上释放出一种特殊的分泌物一信息素(Pheromone)-寻找路径[1]。当它们碰到一个还没有走过的路口时,就随机地挑选一条路径前行,同时会释放出与路径长度有关的信息素蚂蚁走得路径越长,则释放的信息素数量越小。当后来的蚂蚁再次碰到这个路口的时候,选择信息素数量较大路径概率就会相对较大,这样形成了一个正反馈机制。最优路径上的信息素数量越来越大,而其它的路径上信息素数量却会随着时间的流逝而消减,最终整个蚁群会找出最优路径。而且蚂蚁还能够适应环境的变化,当蚁群的运动路径上突然出现障碍物时,蚂蚁亦能够很快地重新找到最优路径。可见在整个寻径过程中,虽然单个蚂蚁的选择能力有限,但是通过信息素的作用使整个蚁群的行为具有非常高的自组织性,蚂蚁之间交换着路最终通过蚁群的集体自催化行为找出最优路径[2]。

2.2 数学模型

设bi(t)表示t时刻位于元素i的蚂蚁数目,τij(t)为t时刻路径(i,j)上的信息量,n表示TSP规模,m为蚁群中蚂蚁的总数目,则是t时刻集合C中元素(城市)两两连接lij上残留信息量的集合。在初始时刻各条路径上信息量相等,并设τij (0)=const,基本蚁群算法的寻优是通过有向图g=(C,L,Γ)实现的。

蚂蚁g=(C,L,Γ)在运动过程中,根据各条路径上的信息量决定其转移方向。这里用禁忌表tabuk(k=1,2,…,m)来记录蚂蚁k当前所走过的城市,集合随着tabuk进化过程动态调整。在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。表示在t时刻蚂蚁k由元素(城市)i转移到元素(城市)j的状态转移概率[3]

式中,allowedk={C-tabuk}表示蚂蚁k下一步允许选择的城市;α为信息启发式因子,表示轨迹的相对重要性,反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用,其值越大,则该蚂蚁越倾向于选择其他蚂蚁经过的路径,蚂蚁之间协作性越强;β为期望启发式因子,表示能见度的相对重要性,反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的受重视程度,其值越大,则该状态转移概率越接近于贪心规则;ηij(t)为启发函数,其表达式如下

式中,dij表示相邻两个城市之间的距离。对蚂蚁k而言,dij越小,ηij(t)则越大,也就越大。显然,该启发函数表示蚂蚁从元素(城市) i转移到元素(城市)j的期望程度。

为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对所有n个城市的遍历(也即一个循环结束)后,要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点,在新信息不断存入大脑的同时,存储在大脑中的旧信息随着时间的推移逐渐淡化,甚至忘记。由此,t+n时刻在路径(i,j)上的信息量可按如下规则进行调整

式中,ρ表示信息素挥发系数,则1-ρ表示信息素残留因子,为了防止信息的无限积累,ρ的取值范围为:;△τij(t)表示本次循环中路径(i,j)上的信息素增量,初始时刻△τij(0)=0,表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量。

根据信息素更新策略的不同,Dorigo M提出了三种不同的基本蚁群算法模型,分别称之为Ant-Cycle模型、Ant-Ouantity模型、及Ant-Density模型,其差别在于求法的不同。

在Ant-Cycle模型中

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

在Ant-Quantity模型中

在Ant-Density模型中

区别式(2-6)和式(2-7)中利用的是局部信息,即蚂蚁完成一步后更新路径上的信息素;而式(2-5)中利用的是整体信息,即蚂蚁完成一个循环后更新所有路径上的信息素,在求解TSP时性能良好,因此通常采用式(2-5)作为蚁群算法的基本模型[4]。

3、改进的蚁群算法

3.1 改进策略

蚁群算法中信息素挥发因子ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度。基本蚁群算法的信息素挥发因子ρ是一固定值,它的大小不会因路径上信息素的多少而改变[5]。也就是说,各个路径的信息素挥发是一样的,信息素多的路径仍然保持着很高的被选择概率,这样很容易出现停滞现象,不利于算法找到更好的解。能否根据路径上信息素的大小来自动调整ρ的大小呢?基于此种考虑,本文提出了一种自适应调整信息素挥发因子的蚁群算法改进策略,旨在通过自适应的改变信息素挥发因子ρ来提高算法的全局性。

假设信息素挥发因子ρ的初始值ρ0=0.1,蚁群算法求得的最优值在N次循环内没有改进时,ρ按下式作自适应调整

式中,ρij表示的是城市i与城市j之间路径的信息素挥发因子;Taumin为城市的信息素矩阵Tau中的最小值(不包括主对角线);Tauij为城市i与城市j之间的信息素的大小;e-1为调节ρij大小的系数。

3.2 改进算法的伪代码

Begin

初始化

While(不满足算法终止条件);{For (ak=1;ak

将m只蚂蚁随机放置于初始城市上For (i=1;i

{For (ak=1;ak

蚂蚁ak以概率选择下一城市}

求出最佳结果

将最佳结果赋予蚂蚁m

If最佳解=N个循环以前的最佳解

4、仿真实例

这里采用实际的城市距离Western Sahara29Cities为例进行仿真。表5-1为基本蚁群算法在不同组合参数下的实验结果,而表5-2为改进算法在不同组合参数下的实验结果。迭代次数均为1000次,蚂蚁数目为城市数29,改进算法中N取50。

由表5-1和表5-2结果可见,改进蚁群算法在不同参数下所得到的最差结果小于基本蚁群算法的最优结果,实现了算法的改进。图4-1和图4-2分别给出了基本蚁群算法和改进后的蚁群算法的最好解的进化曲线。

5、结束语

本文针对蚁群算法的收敛速度慢、易陷入局部最优等缺点,提出了一种新的自适应调整信息素挥发因子的改进算法,TSP实例仿真结果证明,改进后的算法明显优于基本的蚁群算法,不管是在收敛速度还是在跳出局部最优的能力上,都有了明显的提高。

摘要：蚁群算法是一种崭新的仿生模拟进化算法,该算法在许多领域已经得到应用。本文在阐述蚁群算法概念和基本原理的基础上,提出一种新的自适应调整信息素挥发因子的改进算法,以克服其收敛速度慢、易陷入局部最优等缺点,并给出了伪代码,最后将基本的蚁群算法与本文改进后的蚁群算法进行了仿真实验,仿真结果表明,改进后的蚁群算法具有优良的全局优化性能,效果明显。

关键词：蚁群算法,自适应,仿真

参考文献

[1]Colorni A,Dorigo M,Maniezzo V,etal. Distributed optimization by ant colonies.Proceedings of the 1st European Conference on Artificial Life,1991, 134-142

[2]Dorigo M,Maniezzo V,Colorni A.The ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems,Man,and Cybernetics-Part B,1996,26(1):29-41

[3]段海滨编.蚁群算法原理及其应用[M].北京:科学出版社,2005.

[4]李士勇.蚁群算法及其应用【M】.哈尔滨:哈尔滨工业大学出版社,2004.

自适应蚁群优化算法篇7

关键词：自适应,遗传算法,蚁群算法,配电网,重构

0 引言

配电网具有闭环设计、开环运行的特点,根据负荷的不同情况调整配电系统中的开关的开合状态,称之为配电网重构。重构后的网络结构既可以在很大程度上降低线路损耗,又能均衡馈线之间的负荷。所以配电网重构是提高配电系统经济性和安全性的重要途径[1]。在电能的输送和分配过程中,配电网的网损占了整个电网网损相当大的比例,这就确定了配电网重构的必要性。

配电网络重构是一个大规模非线性混合规划问题,具有大量的局部最优解,一般不可微、不连续、多维、有约束条件、高度非线化等特点[2]。如何进行全局最优化,正是本文要做的工作。

1 数学模型

1.1 配电网重构的以线损最小为目标函数的数学模型

配电网络重构影响配电网的线损,所以线损最小的目标函数为

undefined (1)

式中:ri第i条弧的电阻;

Pi,Qi支路i的有功功率和无功功率;

Vi支路i末端的节点电压;

Ki开关i的状态变量,是0-l离散量;

0代表打开,1代表闭合。配电网线损:

Ploss可以通过潮流计算得到。

约束条件为

(1) 配电网重构必须满足潮流方程。

(2) 支路电流及节点电压约束

Si≤Si,max (2)

S1≤S1,max (3)

V1,min≤V1≤V1,max (4)

式中

SiSi,max各支路i流过的功率计算值及其最大容许值;

S1S1,max分别为变压器的供出功率及其最大容许值;

V1,min和V1,max: 节点i的电压上限和下限值。

(3) 网络结构约束:重构后的配电网必须为辐射状。

(4) 供电约束:所有负荷都有电源,不能存在孤立节点。

1.2 配电网重构的电压质量目标函数的数学模型

毕鹏翔等在文献[3]中提出将电压平衡指数作为配电网重构电压质量的目标函数,TSij表示节点i和节点j之间的联络开关,因此设环路中联络开关TSij处的电压平衡指数VBLij为

VBLi,j=max[Ui,Uj]/min[Ui,Uj] (5)

max[Ui,Uj]表示取其大者,min[Ui,Uj]表示取其小者,由此得到提高电压质量的目标函数为

undefined (6)

α为联络开关TSij两端的节点。

2 配网重构的自适应遗传算法和蚁群算法融合

自适应遗传算法和蚁群算法融合算法[4]初期采用遗传算法利用快速全局搜索能力强求得初始解,利用这些解生成蚁群算法的信息素分布,后期利用蚁群算法的正反馈机制求得精确解。进而形成时间效率和精确解效率兼得的一种新的智能算法。利用种群相似度来找到融合算法的最佳融合点:通过实验获得本文融合算法最佳融合点的种群相似度的差值,当所求差值小于该差值时停止迭代。即在遗传算法求最优解效率降低的时候能停止,进而使用求最优解效率较高的蚁群算法。

3 算法的具体实现

GAACA(遗传蚁群混合算法)中的遗传算法规则见文献[5]。

3.1 染色体编码

通过对配电网的简化分析,确定出有些开关必须闭合,否则形成孤岛等。将剩余的开关状态按编号顺序一次用0(开)或1(合)表示,即形成一条染色体。编号的开关数作为一条染色体的长度。

3.2 适应度函数的设计

遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,适应度函数值越大说明该个体越好。因此,以各支路上的有功损耗的总和的倒数为适应度函数

undefined (7)

其中pij每条支路上的有功损耗。

3.3 选择方式

每次从群体中随机选取两个个体进行适应度函数值比较,值较大的保留。若相等,任选一个保留。

3.4 自适应交叉算子

如文献[6]文献[7]提出的方法都是交叉率随适应度函数值自适应变化,这样使遗传算法能保持较强的搜索能力。但是人为因素重,难跳出这个局部最优解等。

因此,在初期采用较小交叉率,使个体在自己所在区域附近进行小范围搜索,使群体收敛到最优解,无论得到局部最优解还是全局最优解。此时再加大交叉率,使陷入局部最优解的个体跳出局部最优;因为采用了最优个体保留策略,将不影响全局最优的个体。这样既保证了算法的快速收敛,又避免了早熟早收敛。此种交叉率随最优个体保持代数双曲线上升,有下式决定

式中: Pundefined:最优个体已经保留m代时的交叉率。

Pc max:最大交叉率(这里取1.0)。

Pc min:最小交叉率(这里取0.5)。

m:最优个体已经保持的代数。

Mmax:遗传算法指定的最优个体最少代数。

按适应度函数值对个体进行由大到小的降序排列,保留前半部分个体[8],生成新的种群。

3.5 变异算子

文献[6]发现变异率随着遗传代数指数下降的效果最好,因此在本文中也采用指数函数,公式如下所示

式中: Pundefined:最优个体已经保留m代时的变异率。

Pm max:最大变异率(这里取0.45)。

Pm min:最小变异率(这里取0.01)。

λ:常数(这里取λ=10)。

m:最优个体已经保持的代数。

M max:遗传算法指定的最优个体最少代数。

3.6 迭代终止条件的确定

利用染色体相似度和种群相似度的差值来停止遗传算法的迭代

定义1 染色体相似度σ=p/q,其中p为两个不同染色体中相同基因的个数, q为两个染色体中的基因总数[9]。

定义2 种群相似度K为

undefined (10)

其中i为任意个体,j为最优个体,σi为个体i的染色体适应度函数值与最优个体j的染色体适应度函数值的差值,即σi=fj-fi,n为种群中的个体总数。任意两代K的差值ΔK越大,表明种群进化越慢;ΔK值越小,表明种群进化越快。当遗传算法迭代效率降低时对应的相邻两代的ΔK为两种算法最佳融合的值。我们用简单的实验选取ΔK值,测试数据见表1。

实验结果表明,当ΔK= 0. 15时使得GAACA在求解效率和迭代次数上都达到最优,因此本文取ΔK为0.15。

4 蚁群算法操作

本文使用蚁群算法来解决配电网网络重构问题,该算法避免了辐射型检查过程,只搜索可行解区域。

4.1 搜索策略

蚂蚁k在t时刻从节点i选择移动到节点j的转移概率Pundefined表示如下

其中,Eundefined=(0,1)表示蚂蚁下一步可行路径的集合,τundefined(t)为t时刻支路(i j)上信息素量,ηundefined(t)为配电网支路(i j)阻抗的倒数(ηundefined(t)=1/Zij);α,β用来调整τundefined(t)和ηundefined(t)对转移概率的影响程度。由(11)式可以看出,信息素越多且支路阻抗越小的支路越容易被选中。

4.2 信息素更新原则

本文算法的信息素更新分为两个部分[10]:第一部分,利用遗传算法生成的较优个体调整信息素的初始分布,公式如下

undefined

(12)

式中:C、Q为常数,fbest(x)和g(x)分别为第x个较优个体的适应度函数值和断开的支路集合。每次迭代后的信息素根据值确定的当前种群较优个体来更新,信息素调整如式(13)

τij(t+n)=τij(t)+Q·fbest(x) (13)

第二部分:蚂蚁搜索过程中的局部信息素更新。蚂蚁每走完一条配电网支路,根据式(14)调整配电网支路上的信息素

τij(t+n)=(1-ρ)τij(t)+Δτij(t,t+n) (14)

undefined

(15)

fbest=Rij/Pijloss (16)

式中:t为代数;ρ为信息素衰减系数,表示信息素随时间的消逝程度;Q为常数,f(x)为第x个个体的适应度函数值。其中,Δτij(t,t+n)表示本次搜索路径(i,j)上信息素的增量,通常设置ρ<1来避免路径上信息素的无限累加。本文根据配电网的实际将适应度函数进行了改进,将支路电阻考虑进来,实验仿真证明结果优于未改进时的结果。

5 算例及分析

本算例采用上图所示的美国PG&E额定电压为12.66 kV,总负荷为3 802 kW+j2694kvar,准功率:100 MVA,基准电压:12.66 kV。参数设置为染色体长度为57,种群数为30。

pc=0.6, pm=0.015, m=30, c=1

α=2, β=5, ρ=0.4, Q=1, Nc max=50

进行30次实验, 每次都能求解到最优解, 由图3可以看出,一般在第3～5代收敛, 可见本文采用的方法既能提高计算速度,又能求得精确解。

图4表明在n=39代时, 目标函数值保持不变,各条支路上信息素也不再更新,说明最优解已经找到。输出结果如表2所示。

图5反映了重构前后系统的负荷裕度。重构前,当负荷为原负荷的1.1倍时, 46节点电压已低于最低电压0.9(p.u.)。而重构后在负荷为原负荷的1.6倍时, 配电网仍然可以正常运行[11]。

【自适应蚁群优化算法】推荐阅读：

自适应蚁群算法08-01

蚁群算法优化策略综述10-13

自适应粒子群优化算法06-12

蚁群算法07-12