蚁群算法模型

2024-10-15

蚁群算法模型（精选9篇）

蚁群算法模型篇1

传统的疏散系统只能指示固定的方向,在意外发生时,不能确保是安全通道和最近的出口的指向,甚至在人员逃生过程中可能会误导逃生人员。人员在紧急疏散过程中有趋光性和趋众性,大部分人会按疏散标志逃离,另一部分人会跟着他人逃离。因此,消防疏散指示系统在应急逃生过程中发挥着越来越重要的作用。

最短路径算法是智能疏散系统中疏散模型的核心算法,目前常见的最短路径算法有Dijkstra算法、模拟退火算法、遗传算法等。这些算法运算效率低,计算过程复杂,花费时间长。意大利学者Dorigo等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径的行为,提出的一种基于种群启发式仿生进化系统的蚁群算法,具有分布式计算、信息正反馈和启发式搜索的特征,有较强的鲁棒性、优良的分布式计算机制等优点。

笔者模拟楼层拓扑结构,建立楼层疏散节点地图,用蚁群算法计算出各个节点到出口的最短路径。提出一种最短最大的节点预处理方法,对节点进行排序,优化蚁群算法处理节点的顺序,减少疏散模型求解最短路径的时间,通过实验对比表明该方法的有效性。

1疏散模型分析

用蚁群算法求出某个节点到安全出口的最短路径。首先建立有多个安全出口的楼层拓扑节点的蚁群算法疏散模型,其次提出最短最大的方法对模型进行优化。

1.1楼层拓扑结构构建

模拟某一楼层的拓扑结构,在中间节点、拐弯点和安全出口等处建立若干节点,将各个节点依次编号并设置节点间的连通关系。节点号集为V={1,2,…,n},连通关系为边集E={e1,e2,…,el},建立节点间关系图G= (V,E),设置安全出口节点,节点以二维坐标存储。

1.2多出口的蚁群算法

蚁群算法是启发式算法的局部更新的自适应算法, 算法迭代的次数和循环次数越多,计算所得的最短路径越准确。

假设禁忌表Tabuk(k=1,2,…,n)记录蚂蚁k当前所走过的节点,蚂蚁数量为m;α、β分别表示蚂蚁积累的信息及启发式因子在选择路径中所起作用的程度;Tauij(t)表示t时刻在节点i、j之间残留的信息量;启发式因子ηij(t)=1/dij,dij表示节点i和j之间的权值;Pikj(t)表示在t时刻蚂蚁k由位置i转移到位置j的概率,如式 (1)所示。

式中:alowedk={0,1,2,…,n-1}-Tabuk为蚂蚁k允许选择的节点;Taui,j(t),ηij(t)与Pikj成正比。

蚂蚁k通过Pikj(t)来确定下一步节点,如果仅依据转移概率确定下一步的节点,会有较快的收敛速度,可能导致局部最优的产生。此时,用0~1的随机数r,如果r< Pikj(t),则选择该节点,扩大搜索范围,较好地避免了局部最优化。集合Tabuk随着进化过程作动态调整,已经走过的节点放在Tabuk中,不再作为下一步判断的节点。每只蚂蚁k在寻找到出口或达到最大循环次数时结束循环,同时把路径保存起来。在某代循环结束时找到到达出口的最短路径,通过式(2)更新该路径上的信息素。

式中:ρ为信息素蒸发的系数;ΔTauij为每代循环中到达出口的蚂蚁在节点i,j上的信息量的增量,当第k只蚂蚁在某次循环中得到最短的路径,用Ant-cycle模型策略更新最短路径信息素,如式(3)所示。

式中:Q为常数,其值为每次释放信息素的总量;Tauikj为第k只蚂蚁在一次循环中到达出口留在路径i、j上的信息量;Lk为第k只蚂蚁在本次循环所走路径的长度。

1.3疏散模型的优化

蚁群算法的时间复杂度较高,智能疏散模型的运算时间主要由蚁群算法的运算时间决定。疏散模型调用蚁群算法每次只能求出若干个节点到出口的最短路径,需要多次调用蚁群算法,又因蚁群算法比较成熟,疏散模型优化的关键是减少蚁群算法的调用次数。最短最大方法是按照到出口最远的距离对节点进行排序,增加蚁群算法每次经过节点的数量,经过的节点不再进行计算,以达到减少蚁群算法计算的次数的目的。

在发生火灾的应急条件下,将楼层的拓扑结构图中节点的坐标值、连通关系和出口的标号值作为数据用于蚁群算法计算节点到出口的最短路径。疏散模型的流程图如图1所示。

2疏散模型实验分析

在如图2的楼层中设置24个节点V={1,2,…,24},连通关系为边集E={e1,e2,…,e32},节点号2、23是安全出口,左右节点连通权值是10,上下连通权值为15,安全出口是2、23,如图2所示。

通过多次仿真计算设置参数值为α=0.1,β=0.1,ρ =0.1,Q=1,初始化信息素矩阵值Tauij(0)=c=1,m= 100,循环次数Nc=100,实验平台是HPZ820工作站。

假设节点3和4之间发生火灾,收到火灾报警信息, 设置节点3和4之间距离为无穷大。在相同的实验条件下,实验1是从节点值1开始计算,未预处理节点的某次运算得到的疏散路径顺序,如表1所示。实验2用最小最大方法预处理,某次运算得到的疏散路径顺序,见表2所示。

两个实验得到了相同的疏散路径,如图3所示。

由图3可知,两次实验结果得出的指示路径是相同的,其中表1经过12次运算,所有节点运算结束,表2运算9次即可,说明经过节点预处理后,每次蚁群算法得到最短路径的节点数增加,疏散模型调用蚁群算法的次数较少。对实验1和2分别进行50次实验,进行优化前和优化后蚁群执行次数和疏散模型运算时间进行对比,如图4、图5所示。

在重复实验时,虽然实验1和实验2的结果有时不完全相同,但得到的疏散路径是等效的,即各个节点到出口的疏散路径长度相等。由图4和图5可知,优化后疏散模型调用蚁群算法的次数减少,运算时间减少。通过计算可知,调用的次数减少了18.53%,运算时间减少了10.52%。此外,改变图2中楼层的拓扑结构后对优化前后进行50次实验对比,结果同样表明,优化后调用蚁群算法次数和运行时间减少。

3结论

通过蚁群算法建立疏散模型,在火灾应急的条件下计算各个节点到出口的最短路径。根据节点的坐标计算节点到出口的欧式距离,提出最小最大算法对节点的进行排序,优化蚁群算法调用节点的顺序,减少了蚁群算法的运算次数,缩短了运行的时间,提高了疏散模型的效率。未来可以考虑烟气的减光性、毒害性、高温等因素, 将楼道的长度改为当量长度,随着楼道环境不断的变化更新其通行能力。

摘要：针对智能疏散系统中运算时间复杂度高的问题,提出一种预处理方法优化疏散模型。建立楼层蚁群算法疏散模型,用该方法对拓扑节点进行排序,使得模型每次调用蚁群算法求最短疏散路径时尽可能地经过多个节点,减少调用蚁群算法的次数,缩短模型的运算时间,通过对优化前后的实验对比表明该方法的有效性。

关键词：蚁群算法,拓扑结构,最短路径,疏散模型

蚁群算法模型篇2

基于蚁群算法的无人机航路规划

为了提高无人机(UAV)作战任务的成功率,在执行敌方防御区域内攻击任务前必需规划设计出高效的无人机飞行航路,保证无人机能够以最小的被发现概率及可接受的`航程到达目标点.针对这一问题,对新近发展的蚁群算法进行了讨论,提出适用于航路规划的优化方法,并对无人机的攻击任务航路进行了仿真计算.仿真结果表明该方法是一种有效的航路规划方法.

作者：柳长安李为吉王和平作者单位：西北工业大学,航空学院,陕西,西安,710072刊名：空军工程大学学报(自然科学版) ISTIC PKU英文刊名：JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY (NATURAL SCIENCE EDITION)年，卷(期)：5(2)分类号：V279关键词：无人机航路规划蚁群算法生物信息激素

蚁群算法模型篇3

由意大利学者 Dorigo等人于1991年提出的蚁群算法(ACS)是解决复杂网络问题的新仿生类算法。蚁群算法是自然界中蚂蚁所表现出的集体行为的数学总结。蚂蚁群体所表现出来的高度结构化,可以通过简单的个体行为来实现。在蚂蚁的群居生活中,最重要的是信息素。蚂蚁借助信息素进行协作觅食,信息素指导后面蚂蚁的行进方向,高信息素会促使更多的蚂蚁再次选择同一条路。ACS不依赖具体的数学模型,具有本质上的并行性,较强的鲁棒性,并表现出高度的灵活性和强壮性。

文中从分析蚁群算法入手,通过加入启发式因子改进了蚂蚁算法,加快了收敛速度。增加启发式参数,避免停留在局部最优解,提高了计算效率,实现最优路径的选择,达到了优化城市交通网络的目的。

1 基本蚁群算法

蚁群算法的提出最初是为了解决旅行商问题(TSP)。以TSP问题为例,初始时计算出城市i和j之间的路径长度,形成无向图G(N,E),其中,dij=dji,N是城市数目,E是城市之间的连通边的集合。Bi(t)表示t时刻位于城市的蚂蚁个数,蚁群中蚂蚁数量 $m = \sum_{i = 1}^{Ν} B_{i} (t)$ ;τij表示t时刻在边e(i,j)上残留的信息量。初始时刻各条路径上信息量相等,即τij(0)=C,C为常数。蚂蚁k(k=1,2,…,m)在运动过程中,根据每条路径上的信息量决定转移的方向,t时刻蚂蚁k由位置i转移到j的概率p $_{i j}^{k}$ (t)设定为[2]

$p_{i j}^{k} = {\begin{cases} τ_{i j}^{α} \cdot η_{i j}^{β} (t) / [\sum_{s \in a l l o w e d} τ_{i j}^{α} \cdot η_{i j}^{β} (t)], j \in a l l o w e d_{k} \\ 0, o t h e r s \end{cases} (1)$

其中,allowedk={0,1,…,n-1}-tabuk表示蚂蚁k下一步允许选择的城市,tabuk(k=1,2,…,m)表示第k个蚂蚁的禁忌表,即蚂蚁k已经经过的城市,且随运动过程动态调整。ηij为由城市i转移到城市j的期望程度(又称可见度)。α为信息量τij(t)对蚂蚁选择该路径的影响因子,β为期望度ηij(t)的影响因子,它们是控制信息激素强度与可见度的相对重要性的参数。

设信息激素的保留系数为ρ(0<ρ<1),它体现了信息激素强度的持久性;而1-ρ表示信息激素的消逝程度(信息激素蒸发)。经过Δt时段,蚂蚁完成一次循环,各路径e(i,j)上信息激素量需按式(2)刷新[3]

${\begin{cases} τ_{i j} (t + n) = (1 - ρ) \cdot τ_{i j} (t) + ρ \cdot Δ τ_{i j} (Δ t) \\ Δ τ_{i j} (Δ t) = \sum_{k = 1}^{m} Δ τ_{i j}^{k} \end{cases} (2)$

其中,Δτ $_{i j}^{k}$ 表示第k只蚂蚁在本次循环(Δt时间内)中,在路径e(i,j)边上留下的信息激素量。故Δ $_{i j}^{k}$ (Δt)表示全部 m只蚂蚁在本次循环(Δt时间内)中在路径e(i,j)边上留下的信息激素量;而Δτ $_{i j}^{k}$ 用式(3)计算

$Δ τ_{i j}^{k} = {\begin{cases} Q / L_{k}, 若第 k 只蚂蚁在本次循环中经过路径 e (i, j) \\ 0, o t h e r s \end{cases} (3)$

其中,Q为常数,Lk表示第k只蚂蚁在本次循环中所走过路径的长度,它可表示为

$L_{k} = \sum_{i = 1, j = 1}^{n} d_{i j} (4)$

式(4)中,n表示蚂蚁k在本次循环中所漫游的城市数目(n≤N)。

2 改进的蚁群算法

2.1 TSP与路径规划问题的区别

(1) 在TSP问题中,起始点与终止点是任意的,因而在初始时蚂蚁可以随机的出现在任意一个城市。而在路径规划问题中,起始节点与目标节点都是事先确定的[4]。在TSP问题中,起始节点与目标节点一般是相同的,而在交通网络中,起始节点与目标节点是不同的;

(2) 在TSP问题中,城市间的距离矩阵一般为对称矩阵,即dji=dji,而在城市交通中,上行与下行交通状况不同,即dji≠dji;

(3) 城市网络中节点数较大(200以上),在初始时计算城市距离耗费大量时间,且由于城市交通网络的特殊性,距离矩阵往往是稀疏矩阵;

(4) 城市交通网络中存在一个结点只发散一条边,类似于陷阱,会使蚂蚁丧失前进能力,TSP问题中不存在此问题。

2.2 适用于交通网络的蚁群算法

利用一般蚁群算法解决交通问题[5,6,7],容易陷入局部最优解。使用动态信息素权重的算法[4],虽然提高了蚁群算法跳出局部最优解的能力,但在初始时没有有效地启发因子,初期搜索时具有盲目性,为此提出以下改进方法。

2.2.1 启发式因子

在自然界中蚂蚁寻路除受信息素的影响外,还受到食物的吸引。通过增加食物对蚂蚁的吸引力来提高蚂蚁前往目标节点的效率。即在每个节点增加食物在该节点的影响因素

Si=k·[abs(Xgoal-Xi)+abs(Ygoal-Yi)] (5)

其中,(Xgoal,Ygoal)为目标节点的坐标,(Xi,Yi)为第i个节点的坐标,因为城市网络往往呈现一定的栅格特性,这里选择曼哈顿距离作为距离的计算准则[6]。Si在程序的执行过程中不会发生变化。参数k的选取必须合适,如果参数k过小,则额外启发因素起不到作用;如果k选取过大,则信息素作用消失,退化成为贪婪算法。

t时刻蚂蚁k由位置i转移到的概率p $_{i j}^{k}$ (t)更新为

$p_{i j}^{k} = {\begin{cases} [τ_{i j}^{α} \cdot η_{i j}^{β} (t) + S_{j}] / {\sum_{s \in a l l o w e d} [τ_{i j}^{α} \cdot η_{i j}^{β} (t) + S_{j}]}, j \in a l l o w e d \\ 0, o t h e r s \end{cases} (6)$

在初始时刻,蚂蚁选择下一节点的概率由于有额外信息素的影响而不再均等,蚂蚁趋向于前往离目标节点接近的节点,加快初始时向目标节点靠近的速度。随着时间的推移,信息素的浓度增加,蚂蚁受信息素影响增加,使更多的蚂蚁通过在最优的道路。

2.2.2 参数的改进

蚁群算法中参数α,β的选取会影响蚁群算法的收敛速度与解的质量[5]。参数α,β分别表示信息素及模拟运行时下一点对蚂蚁所起作用的重要性。若α=0,则靠近i的城市将很可能被选出来,这时蚁群算法退化为经典随机贪心算法,如果β=0,那么只有信息素的放大系数在起作用,没有任何与道路有关的期望信息,特别当此时若α>1时,算法将很快陷入局部最优解。

为此采用自适应的方案改进参数:

(1) 设定初始值α=α0,β=β0;

(2) 如果相邻两代最优解与上次变化不大,说明运算有可能陷入局部最优解,应该减少信息素对蚂蚁的影响。下一次采用如式(7)所示以更新α,β

(3) 如果相邻两代最优解与上次变化很大,说明受信息素影响过大,受期望度影响过小。下一次则采用如式(8)所示以更新α,β

2.2.3 “陷阱”问题

若蚂蚁陷入一个陷阱中,则将该节点视为群体禁忌表中的一点,于是下一代蚁群中蚂蚁的禁忌表不再为空。这样下次蚂蚁在路口选择时受到禁忌表的约束,“陷阱”被选中的概率为0,于是不再会有蚂蚁陷在该陷阱中。

3 仿真实验

采用某大学的简易地图作为算例。图1中包含39个路口,56条路。下面分别使用文中提出的算法和基本蚁群算法进行仿真实验,检测算法的性能(S为起点,G为终点)。

取θ=0.8,ε=1.2,γ=1.3,δ=0.6,k=0.002,其余参数两种算法相同,分别取α0=1.0,β0=2.0,ρ=0.1,Q=8。

随机生成每条道路的拥挤程度φ,用数字1～4表示,含义如表1所示。

各路段的代价函数如式(8)所示

$D_{i j} = {\begin{cases} 0.1 \times d_{i j}, φ = 1 \\ d_{i j}, φ = 2 \\ 3 \times d_{i j}, φ = 3 \\ 100 \times d_{i j}, φ = 4 \end{cases} (8)$

其中,dij为i,j之间的道路长度,通过调节代价函数,使所获得的路径满足驾驶真实需求,算法不再寻找路径最短,改为寻找最优解。

通过对比图2和图3可以看出,改进型算法增加了启发因子,在初期的选择中蚂蚁更倾向于向接近于目标节点靠近,种群的平均距离比较小,加快了收敛速度。后期由于有启发因子的调节,蚂蚁不断改变策略,于是平均值变化较大,易于跳出局部最优。

图4和图5给出了每次执行获得的最优解的变化。由于初始时增强了对目标节点的导向性,即在开始时改进算法获得了较好的开始值,提高了蚁群接近于目标节点的速度,加快了收敛速度,在短时间内寻找到最优值,减少消耗的计算资源。

4 结束语

文中从基本的蚁群算法入手,针对交通问题的特殊性,提出了增加启发式因子,通过“食物”的吸引,加快了算法的收敛速度,同时为了增强算法跳出局部最优解的能力,增加了参数的自适应能力。随后的仿真试验表明,文中改进算法与基本蚁群算法相比,能够加快收敛速度,提高跳出局部最优解的能力,进一步改善了蚁群算法,为该类优化问题提供了优化方式。

参考文献

[1]赵家俊,于宝琴.现代物流配送管理[M].北京:北京大学出版社,2004.

[2]Colorni A,Dorigo M,Maniezzo V.Distributed Optimizati on by Ant Colonies[C].Paris:Proc of European Confer-ence of Artificial Life,1991:1342-144.

[3]Dorigo M,Bonabeau E,Theraulaz G.Ant Algorithm and Stigmergy[J].Future Generation Computer Systems,2000,16(6):851-871.

[4]温惠英,徐建闽.基于改进型蚁群算法的车辆导航路径规划研究[J].公路交通科技,2009,1(26):125-129.

[5]范红平,陈丽娟,杨国军,等.GAAA算法在直线步进电机控制中的应用[J].电子科技,2006(10):51-54,58.

[6]靳凯文,李春葆,秦前清.基于蚁群算法的最短路径搜索方法研究[J].公路交通科技,2006,23(3):128-134.

蚁群算法模型篇4

基于改进蚁群算法的无人机侦察航路规划研究

蚁群算法是一种新的源于大自然生物界的仿生随机优化方法,在一系列组合优化问题求解中取得了成效.本文将蚁群算法引入无人机侦察航路的规划,对基本蚁群算法提出了改进,提供了一种新的有效的航路优化算法,并对无人机的侦察航路进行了仿真计算.仿真结果表明改进的`蚁群算法克服了基本蚁群算法的收敛速度慢、易于过早陷入局部最优的缺点,仿真结果验证了该算法的有效性.

作者：蒋定定李万泉 JANG Ding-Ding LI Wan-Quan 作者单位：海军航空工程学院,青岛分院,山东,青岛,266041刊名：飞机设计英文刊名：AIRCRAFT DESIGN年，卷(期)：28(2)分类号：V279+.2关键词：蚁群算法无人机航路规划生物信息

蚁群算法模型篇5

侦察卫星等地球低轨道卫星每天获取的大量数据都需要通过地面站及数据接收天线(简称“数传资源”)传输到地面以供用户分析使用,由此产生的卫星数传调度问题就是在一定的规划调度周期TimeLine内,由m个不完全相同的数传资源R={R1,R2,…,Rm}执行n个相互独立的数传任务T={T1,T2,…,Tn},以满足数传任务的调度收益最大等目标。其中,每个任务Tj(j=1,2,…,n)具有优先级Tprij和任务最短持续时间Tdurj,以及由任务最早开始时间Tstj和最迟结束时间Tetj决定的任务执行时间窗口[Tstj,Tetj],任务Tj的可用数传资源集R(Tj)⊆R,显然R(Tj)≠∅,当任务要求频段Tbj与资源Ri(i=1,2,…,m)的频段Rbi一致时,两者之间具有可见时间窗口TWij=[TWstij,TWetij],其中Ri∈R(Tj)。

卫星数传调度问题研究中,李云峰建立了基于数传任务框架的卫星数传调度模型[1],先后提出基于试探性启发式调度算法、综合优先度调度算法和混合遗传算法[2,3,4]。Sylvain Damiani等将卫星数据下载调度作为一个独立于卫星侦察调度的决策问题, 建立了动态规划模型, 并用贪婪算法求解[5]。针对Gooly首先提出的SRS(satellite range scheduling)问题[6],L.Barbulescu证明了具有多资源的SRS问题是NP-hard问题[7],并证明了在大规模SRS问题中,遗传算法比传统启发式算法更具优势。针对COSMO-SkyMed星座中的SRS问题, Bianchessi等提出了具有前向搜索和反向回溯能力的构造算法[8]。N.Zufferey等借鉴图着色技术的基本思想,设计了禁忌搜索和适应存储两种算法求解多资源的SRS问题[9]。以上学者的研究,主要侧重于任务调度收益建模,强调的是任务调度完成的数量及价值收益,没有考虑执行任务的资源负荷均衡问题。实际上,一个合理的调度方案必须考虑到资源负荷的均衡性,否则就可能造成某些资源长期处于高负荷工作状态,而某些资源则总处于低负荷工作状态,资源负荷均衡性较差,显然不利于资源利用及人员配备。

通过对数传资源负荷进行定义与分析,建立基于资源负荷均衡的卫星数传调度模型,并提出基于蚁群算法[10]的模型求解算法, 在满足调度收益目标的情况下, 提高资源负荷均衡度,使调度方案更具合理性和可操作性。蚁群算法已在混合车间调度问题[11]、排列流水调度问题[12]、资源受限项目调度问题[13]中得到深入研究,并开始应用于航天调度领域[14,15],但是相关的算法只针对特定的问题。

2 模型建立与调度方案评价

2.1 数传资源负荷

引入0-1决策变量xij,任务Tj在资源Ri上执行数传时xij=1,否则xij=0。因此,可构造调度方案决策矩阵Xm×n.引入具有起止时间Dstij,Detij的时间窗口变量Dij=[Dstij,Detij],构造卫星数传调度方案矩阵Dm×n,Dij(i=1,2,…,m;j=1,2,…,n)表示数传任务Tj在数传资源Ri上的数传执行时间窗口,其长度为|Dij|=Detij-Dstij.当Dij⊆TWij时,任务Tj在资源Ri上执行数传,否则不执行数传,|Dij|=0。

时间窗口限制是卫星数传调度问题中的一个重要特征,数传任务的完成与时间窗口密切相关,因此,可以把时间作为资源负荷的度量依据。定义数传资源负荷为所有数传任务在某个数传资源上的数传时间之和。根据定义,资源Ri的负荷为 $C_{i}^{S c h e} (X, D) = \sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j}$ ,所有资源的负荷为 $C_{R}^{S c h e} (X, D) = \sum_{i = 1}^{m} C_{i}^{S c h e} (X, D) ‚ C_{R}^{S c h e} (X, D)$ 是上限为 $C_{R}^{\max} = \sum_{j = 1}^{n} Τ_{j}^{d u r}$ 的非常数,其均值满足 $\min_{1 \leq i \leq m} {C_{i}^{S c h e} (X, D)} \leq C_{R}^{S c h e} (X, D) / m \leq \max_{1 \leq i \leq m} {C_{i}^{S c h e} (X, D)}$ 。显然, 只要使得各资源负荷CSchei(X,D)之间的差值尽可能小, 资源负荷的均衡度就越高, 各资源负荷就越接近于CScheR(X,D)/m.由于资源负荷均值有界, 即CScheR(X,D)/m≤CmaxR/m,所以数传资源负荷均衡的调度问题必然收敛。

2.2 资源负荷均衡调度模型

卫星数传调度问题的主要优化目标是调度收益,一般情况下, 其调度收益取决于成功完成任务的数量、任务的优先级大小以及任务执行时间,因此可确定调度收益目标函数为成功调度任务数传时间优先级加权和最大。根据对数传资源负荷的定义与分析,在满足任务调度收益目标的情况下, 数传资源负荷越均衡, 其调度方案越合理, 因此可确定数传资源负荷差值最小为资源负荷均衡目标函数,建立如式(1)所示的基于资源负荷均衡的数传调度模型。

O1:

$\max \sum_{i = 1}^{m} \sum_{j = 1}^{n} Τ_{j}^{p r i} \cdot | D_{i j} | \cdot x_{i j}$

O2:

$\min {\frac{\sum_{i = 1}^{m} (\sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j} - \frac{\sum_{i = 1}^{m} \sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j}}{m})^{2}}{m}}^{1 / 2}$

s.t.

i=1,2,…,m

j=1,2,…,n

C1: xij=1, Tbj=Rbi

C2: xij=1, Dij⊆TWij

C3: $\forall j, x_{i j} = 1, Τ_{j}^{d u r} \leq \sum_{i = 1}^{m} | D_{i j} |$

C4: $\forall i, x_{i j} = 1, 0 < \sum_{j = 1}^{n} | D_{i j} |$

C5: ∀j, xij=1, Tstj≥min(Dst1j,Dst1j,…,Dstmj)

C6: ∀i, xij=1, Tetj≤max(Det1j,Det1j,…,Detmj)

C7: ∀i, xij=1, Di1∩Di2∩…∩Dmn=∅

C8: ∀j, xij=1, D1j∩D2j∩…∩Dmn=∅ (1)

其中,O1表示数传调度收益目标函数,其值越大越好;O2表示资源负荷均衡目标函数,其值越小越好。约束C1表示数传任务与数传资源天线频段必须一致;约束C2表示数传任务只能在与数传资源的可见时间窗口内执行;约束C3表示一个数传任务成功完成必须满足其最短持续时间要求;约束C4表示为了达到资源均衡调度,一个数传资源至少为一个数传任务提供服务;约束C5、C6分别表示任务调度必须满足最早开始时间和最迟结束时间要求;约束C7表示同一时刻一个数传资源只能为一个数传任务提供服务;约束C8表示同一时刻,一个数传任务只能在一个数传资源上执行。另外,数传资源在为不同任务提供数传服务时,还要满足设备状态切换时间要求。

2.3 调度方案评价

为了评估基于资源负荷均衡的数传调度模型所取得的调度方案,需要将调度模型中的两个目标函数的量纲相互统一,因此定义数传时间优先级加权满足度和数传资源负荷均衡度两个调度方案评估指标,分别评估调度方案的调度收益和资源负荷均衡度,然后基于这两个指标来设计调度方案的效能评估函数。

①数传时间优先级加权满足度

数传时间优先级加权满足度是成功调度数传任务的最短持续时间优先级加权和与所有任务最短持续时间优先级加权和的比值,由于分母为常量,分子为目标函数,所以该指标值越大目标函数O1值也越大。

$E Ι_{Τ} (X, D) = \frac{\sum_{i = 1}^{m} \sum_{j = 1}^{n} Τ_{j}^{p r i} \cdot | D_{i j} | \cdot x_{i j}}{\sum_{j = 1}^{n} Τ_{j}^{p r i} \cdot Τ_{j}^{d u r}} (2)$

②数传资源负荷均衡度

数传资源负荷均衡度是1减去资源负荷均方差与资源负荷均值的比值,由于资源负荷均值有界,当资源负荷均方差越小的时候,负荷均衡度越高,该指标值越大,其目标函数O2值越小。

$\begin{array}{l} E Ι_{R} (X, D) = 1 - \\ \frac{{(\sum_{i = 1}^{m} (\sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j} - (\sum_{i = 1}^{m} \sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j}) / m)^{2}) / m}^{1 / 2}}{(\sum_{i = 1}^{m} \sum_{j = 1}^{n} | D_{i j} | \cdot x_{i j}) / m} \end{array} (3)$

③效能评估函数

数传时间优先级加权满足度和数传资源负荷均衡度两个评估指标分别反映了调度收益和资源均衡度两个目标函数的优化程度,由于需要对调度模型中的两个目标函数同时优化,在此定义如式(4)所示调度方案的效能评估函数,并以效能函数值的大小作为调度方案评估依据。

$\max E (X, D) = {E Ι_{Τ} (X, D)}^{γ} \cdot {E Ι_{R} (X, D)}^{λ} (4)$

式中,γ≥0表示调度收益评价指标(数传时间优先级加权满足度)的重要系数,λ≥0表示资源负荷均衡评价指标(数传资源负荷均衡度)重要系数。

3 蚁群解构造及算法流程

3.1 矩阵解构造图

J.Montgomery研究发现,在组合优化问题中,解的表示与信息素分布模型对于蚁群优化算法的应用至关重要[16,17,18]。针对卫星数传调度问题,构造矩阵解构造图模型G=(N,E),其中:N={Nij|i=1,2,…,m;j=1,2,…,n}为图G中结点集合,Nij表示任务Tj在资源Ri上执行调度;E={(Nij,Nkl)|i,k=1,2,…,m;j,l=1,2,…,n},其中(i≠k)||(j≠l)为图G中各结点之间的连接边或弧。

信息素分布于图G中各结点上,τij表示在结点Nij上的信息素浓度,是任务Tj在资源Ri上执行数传的期望。ηij表示人工蚂蚁经过结点Nij时,任务Tj在资源Ri上执行数传的启发式信息,可取如式(5)所示的数传时间满足度δ作为启发式信息,则可定义ηij如式(6):

$\begin{array}{l} δ = \frac{\min (Τ_{j}^{e t}, Τ W_{i j}^{e t}) - \max (Τ_{j}^{s t}, Τ W_{i j}^{s t})}{Τ_{j}^{d u r}} (5) \\ η_{i j} = {\begin{matrix} \min {1.0, δ}, & 0 < | Τ W_{i j} | \\ 0, & o t h e r w i s e \end{matrix} (6) \end{array}$

3.2 解构造过程

规模大小为Amax的蚁群中的每只蚂蚁在调度可行解构造过程中,首先从某个虚拟结点N0出发,根据图中结点上的信息素和问题启发式信息进行列选择,按照式(7)、式(8)选择图G=(N,E)中某列πT(j),这相当于首先确定当前调度的任务。信息素相对重要系数α>0和启发式信息相对重要系数β≥0表明蚂蚁在解构造过程中对两种信息的偏好程度。

$\begin{array}{l} π^{Τ} (j) = {\begin{matrix} \arg \max_{j \in Τ_{a l l o w e d}} {[\sum_{i = 1}^{m} τ_{i j}]^{α} \cdot [η_{i j}^{*}]^{β}}, & q \leq q_{0} \\ S_{Τ}, & o t h e r w i s e \end{matrix} (7) \\ p_{j}^{Τ} = {\begin{matrix} \frac{[\sum_{i = 1}^{m} τ_{i j}]^{α} \cdot [η_{i j}^{*}]^{β}}{\sum_{l \in Τ_{a l l o w e d}} [\sum_{i = 1}^{m} τ_{i l}]^{α} \cdot [η_{i l}^{*}]^{β}}, & j \in Τ_{a l l o w e d} \\ 0, & o t h e r w i s e \end{matrix} (8) \end{array}$

其中, $\sum_{i = 1}^{m} τ_{i j}$ 表示调度任务Tj时的可用资源期望。 $η_{i j}^{*} = (1 - \frac{\sum_{i = 1}^{m} η_{i j}}{m}) + \frac{Τ_{j}^{p r i} \cdot Τ_{j}^{d u r}}{\sum_{l \in Τ_{a l l o w e d}} Τ_{l}^{p r i} \cdot Τ_{l}^{d u r}} ‚ (1 - \frac{\sum_{i = 1}^{m} η_{i j}}{m})$ 表示优先调度平均数传时间满足度较小的任务,而 $\frac{Τ_{j}^{p r i} \cdot Τ_{j}^{d u r}}{\sum_{l \in Τ_{a l l o w e d}} Τ_{l}^{p r i} \cdot Τ_{l}^{d u r}}$ 表示当前任务调度收益的相对大小。

q∈[0,1]为均匀分布的随机数,q0∈[0,1]是蚂蚁在解构造过程中的知识利用与随机搜索的相对重要性。当q≤q0时,蚂蚁在调度任务选择时倾向于的知识利用,选择 $[\sum_{i = 1}^{m} τ_{i j}]^{α} \cdot [η_{i j}^{*}]^{β}$ 最大的列为πT(j),否则在ST中以概率pTj选择πT(j)。

为避免列搜索空间过大,假设虚拟结点N0是从调度周期开始时刻确定列搜索空间,如果两个列所代表任务Tp,Tq(p,q=1,2,…,n;p≠q)的任务需求时间窗口相交,由式(9)判定,这两个任务调度的先后顺序可能对列结点遍历时的资源分配产生影响,所以将与当前列所代表任务时间窗口相交的任务集合作为列搜索空间Tallowed.

$\frac{\max {Τ_{p}^{e t}, Τ_{q}^{e t}} - \min {Τ_{p}^{s t}, Τ_{q}^{s t}}}{| Τ_{p}^{e t} - Τ_{p}^{s t} | + | Τ_{q}^{e t} - Τ_{q}^{s t} |} < 1 (9)$

确定当前列πT(j)之后,再按照式(10)、式(11)遍历此列中的各结点,相当于资源分配。

$\begin{array}{l} π_{j}^{R} (i) = {\begin{matrix} \arg \max_{i \in R_{a l l o w e d}} {[τ_{i j}]^{α} \cdot [η_{i j}]^{β}}, & q \leq q_{0} \\ S_{R}, & o t h e r w i s e \end{matrix} (10) \\ p_{i j}^{R} = {\begin{matrix} \frac{[τ_{i j}^{*}]^{α} \cdot [η_{i j}]^{β}}{\sum_{k \in R_{a l l o w e d}} [τ_{k j}^{*}]^{α} \cdot [η_{k j}]^{β}}, & i \in R_{a l l o w e d} \\ 0, & o t h e r w i s e \end{matrix} (11) \end{array}$

其中,Rallowed=R(Tj)-Tabuj(R),Rallowed⊆R,Tabuj(R)为已经为任务Tj分配了时间窗口的资源。当q≤q0时, 蚂蚁倾向于任务资源分配的知识利用, 选择[τij]α·[ηij]β最大的结点为πRj(i),否则在SR中以概率pRij确定πRj(i)。在确定调度任务及可用数传资源之后, 按照式(1)中的约束条件为任务分配数传时间窗口, 直到满足数传任务的最短持续时间或者无数传资源可用。然后重复进行列选择和列结点遍历, 并进行数传任务的资源与时间窗口分配, 直到所有列中的结点都被遍历之后, 完成可行调度解构造。

3.3 信息素更新规则

蚂蚁在当前算法迭代t的解构造过程中,为了减小蚁群中其他蚂蚁走相同路径的可能性,按式(12)进行局部信息素更新,其中局部信息素挥发系数ρl∈(0,1),τ0是路径上初始信息素大小。

$τ_{i j} (t) = (1 - ρ_{l}) τ_{i j} (t) + ρ_{l} \cdot τ_{0} (12)$

全局信息素更新在算法迭代t中蚁群都完成调度可行解构造之后,采用效能函数式(4)对蚁群中各蚂蚁所构造的解进行评价,并获得历史最优解,将历史最优解作为全局信息素更新依据。设全局信息素挥发系数ρg∈(0,1),全局信息素更新规则由式(13)确定:

$τ_{i j} (t + 1) = (1 - ρ_{g}) τ_{i j} (t) + ρ_{g} \cdot (Δ τ_{i j}^{g b} + Δ τ_{i j}) (13)$

Δτgbij表示蚂蚁在历史最优解的解构造路径上在结点Nij上遗留的信息素,由式(14)决定。

$\begin{array}{l} Δ τ_{i j}^{g b} = \\ {\begin{matrix} (\frac{γ}{γ + λ} \cdot E Ι_{Τ}^{g b} + \frac{λ}{γ + λ} \cdot E Ι_{R}^{g b}) \cdot \frac{| D_{i j} |}{Τ_{j}^{d u r}}, & x_{i j} = 1 \\ 0, & o t h e r w i s e \end{matrix} \end{array} (14)$

其中,EIgbT,EIgbR分别为历史最优解的数传时间优先级加权满足度和数传资源负荷均衡度指标的评估值。γ/(γ+λ)为调度收益目标的相对重要系数,λ/(γ+λ)表示资源负荷均衡目标的相对重要系数,|Dij|/Tdurj表示每个结点上的遗留信息素大小与数传执行时间所占任务最短持续时间的比例相关。

Δτij为每次算法迭代中,蚁群在结点Nij上遗留的局部信息素之和,由式(15)决定:

$Δ τ_{i j} = \sum_{k = 1}^{A_{\max}} Δ τ_{i j}^{k} = \sum_{k = 1}^{A_{\max}} ρ_{l} \cdot τ_{0} (15)$

为避免τij过大或者过小,使算法过早陷入局部最优,其大小必须限制在[τmin,τmax]范围内,如式(16)。

$τ_{i j} (t) = {\begin{matrix} τ_{\max}, & τ_{i j} (t) \geq τ_{\max} \\ τ_{i j} (t), & τ_{\min} < τ_{i j} (t) < τ_{\max} \\ τ_{\min}, & τ_{i j} (t) \leq τ_{\min} \end{matrix} (16)$

3.4 算法基本流程

基于资源负荷均衡的卫星数传调度蚁群优化算法基本流程如下:

步骤1 根据问题实例确定任务和资源规模,并问题实例映射为矩阵解构造图G=(N,E)中,并完成图中结点上的初始信息素τ0设置,以及τmin,τmax设置;

步骤2 设置算法基本参数,包括α,β,q0,蚁群规模Amax,算法最大迭代次数NCmax,以及算法终止条件,同时确定γ,λ的值;

步骤3 算法运行

3.1 初始化蚁群,将任务集合加入每只蚂蚁k(k=1,2,…,Amax)的任务调度禁忌表Tabuk,并从初始结点出发;

3.2 根据式(9)确定调度任务的搜索领域,按照式(7)、式(8)选择要执行调度的任务;

3.3 确定调度任务后,根据式(10)、式(11)确定该任务的资源分配序列;

3.4 根据式(1)中的调度约束限制,结合已构造的解,按照任务资源分配顺序表进行资源及时间窗口分配,当任务满足调度要求或者可用资源分配完毕之后,记录该任务所构造的解;

3.5 根据当前任务解按式(12)进行局部信息素更新,并从Tabuk中删除;

3.6 转入3.2进行下一调度任务的选择和解构造,当Tabuk为空时,蚂蚁k完成调度可行解构造;

3.7 当蚁群中所有蚂蚁都完成调度可行解构造之后,根据调度方案效能函数式(4)评价每只蚂蚁所构造的解,记录效能评价值最高的解;

步骤4 以历史最优解为全局信息更新依据,按照式(13)进行全局信息素更新;

步骤5 循环算法迭代,直到满足算法终止条件或者最大迭代次数限制;

步骤6 按照式(2)、式(3)进行最优解的指标评价,记录并输出全局最优解。

4 算例仿真

4.1 算例设计

设一个包括12颗卫星、 4个地面站的调度场景, 其中每颗卫星和每个地面站都具有1根同频段数传天线。场景调度周期为2008-8-8 0:00:00至2008-8-9 0:00:00,根据金光提出的冲突评估方法[19],计算得到场景冲突统计结果如表1所示,可以看出该场景具有较强的“可见时间窗口”冲突。地面站和卫星的基本参数分别列于表2和表3。

根据STK工具生成的场景预报流数据,并依据一定规则生成数传任务共计103个,任务最短时间优先级加权和为360208秒。

任务生成规则:

① 将每颗卫星存在重叠的可见时间窗口依次合并为一个时间窗口。

② 针对每个长度大于5分钟的合并后的时间窗口,生成一个0-1之间的随机数q.

③ 如果0≤q<0.3,则以时间窗口内的两个时间点作为任务的最早开始时间和最迟结束时间,任务最短持续时间为时间区间长度,并满足大于5分钟的要求。该类任务调度时的时间窗口约束更为严格,调度相对困难。

④ 如果0.3≤q≤1.0,则以时间窗口的起止时间作为任务的最早开始时间和最迟结束时间,任务的最短持续时间在5分钟到时间窗口长度之间抽样生成。该类任务的开始时间具有一定的灵活性,调度成功的可能性更大。

⑤ 为每个任务随机生成一个1-10之间的整数作任务优先级,以表明任务的重要程度及价值,并假设值越大优先级越高。

4.2 仿真结果分析

通过大量试验,确定算法参数为:α=1.0,β=0.5,q0=0.25,Amax=8,NCmax=100,ρg=0.75,ρl=0.25,τ0=0.5, τmin=0.01, τmax=10.0。为充分验证算法模型的正确性和有效性, 当γ=0.0,λ=1.0时, 只考虑调度收益(scheduling profits)目标函数O1, 将算法模型称为“SPACO”;当γ=1.0,λ=0.0时,只考虑负荷均衡(load balance)目标函数,将算法模型称为LBACO;当γ>0.0,λ>0.0时,综合考虑目标函数O1和O2的多目标(multi objective)蚁群算法模型称为“MOACO”,现在取值为γ=2.0,λ=0.5。在算法参数设置不变的条件下, 对SPACO、 LBACO、 MOACO分别运行10次, 取效能函数值表现最优的方案, 进行数传时间优先级加权满足度和数传资源负荷均衡度指标评估,结果见表4。

表4中, GA是文献[3]中提出的一种基于遗传算法的卫星数传混合调度算法,并采用与文献中相同的参数设置。TSP是文献[4]中提出的一种基于卫星数传任务综合优先度的启发式算法。MPA是STK/Scheduler中采用的一种多次扫描算法,通过计算每一种方案的FOM(figure of merit)值,对每一种方案进行比较评价,最后挑选出FOM值最大的调度方案作为最终的调度方案。PBS是基于优先级的调度算法,其基本思想是优先调度任务优先级高的任务。FCFS为先到先服务调度算法,基本思想是优先调度开始时间较早的任务。

从表4可以看出,MOACO、LBACO、SPACO所取得的调度方案两个评估指标值均高于现有算法,说明基于数传资源负荷均衡的调度模型是正确的,算法的解寻优效果较好。当只考虑资源负荷均衡目标时, LBACO取得高达99.85%的资源负荷均衡度, 远远高于没有考虑资源负荷均衡的其他算法模型。当同时考虑数传资源负荷均衡和数传时间优先级加权时, MOACO不仅达到了SPACO所求得的93.21%的数传时间优先级加权满足度,而且数传资源负荷均衡度比SPACO高3.62%,说明算法均有良好的目标优化和平衡能力。

图1是仿真中不同算法模型求得的最优方案的数传资源负荷(数传执行时间)分布情况,可以看出,资源负荷均衡度指标客观的反映了数传资源负荷的分布状况,与表4中的数传资源负荷均衡度指标评估值相一致。说明在算法在解构造过程中,考虑了资源负荷均衡性,避免了资源负荷出现较大差异。

图2是MOACO所求调度方案的数传资源负荷均衡度指标和数传时间优先级加权满足度指标随算法迭代进化曲线图,可知算法具有良好的收敛性能,并能同时优化两个调度目标。在试验过程中还发现,本文提出的蚁群算法运算速度明显快于文献[3]提出的遗传算法。

5 结论

合理的卫星数传调度方案应该在确保任务调度收益最大的同时考虑数传资源的负荷均衡,以减少因为资源负荷不均而造成的资源利用与人力分配之间的矛盾。通过分析定义数传资源负荷,建立了卫星数传资源负荷均衡调度模型,提出了基于数传时间优先级加权满足度和数传资源负荷均衡度指标的调度方案效能评价函数。在矩阵解构造图的基础上,提出了具有调度任务确定和资源分配两个决策阶段的蚁群解构造过程,以及基于效能评价函数的全局信息素更新规则。算例仿真表明,本文提出的调度模型和蚁群算法综合考虑了任务调度收益和资源负荷均衡两个优化目标,能够在保证任务调度收益的同时,提高数传资源负荷均衡度,所取得的调度方案获得了较好的数传时间优先级满足度和数传资源负荷均衡度指标评价值。

蚁群算法模型篇6

维修保障体系是作战体系的重要组成部分,它对作战能力的形成和发挥有着很强的支撑和推动作用,人力资源作为维修资源的主要方面,在维修保障工作中有着关键的影响。为适应平战一体化建设,在装备维修领域提出了平战兼容的“基本保障单元”概念,对于保障力量的平时使用、平战快速转换以及与战时上级加强力量的运用等方面,具有很强的现实意义。

基本保障单元是指由人员、装备、设备、器材等要素构成,能够独立完成指定专业维修保障任务的最小保障单位。在执行维修保障任务过程中,如何配置保障单元的人力资源,能够以最少人员在规定的时间内完成修理任务是目前亟待解决的实际问题。在目前常用的优化模型中有通过缩短关键线路来压缩工期的“工期模型”;寻求在某一时间点下,总费用最低的“工期费用”模型和在固定工期下,通过调整各工序的前后施工顺序以达到资源利用最均衡的“工期资源”模型,而对于给定工期,求人员最少配置问题还没有成熟的模型,为此,本文在备品备件等供应充足的前提下,建立“工期人员”模型对基本保障单元的人员数量进行优化,并对模型的求解方法进行了分析研究。

一、人力资源优化问题描述

1、修理工期与人员数量的关系

装备维修是一个复杂的过程,在装备的维修过程中通常涉及多工种,但在实际工作中各工种之间的工作基本上没有交叉,所以可以将维修项目按工种分解成若干项工作,每项工作由若干个工序节点组成,工序节点可根据需要包括的内容可多可少,范围可大可小。整个项目的修理工期是由各工序节点的修理时间决定的,所以首先讨论工序节点的修理时间与人员数量的关系。

在设施设备完善,备品备件供应充足的条件下,节点的修理工时是固定值,所以节点的修理时间在某个范围内随人员数量的增加成近似直线的线性关系,但节点不可能随人员的无限增加而工期无限缩短,当人员数量增加到某固定值时,对时间的影响变得很小。因为人员数量为必须取整数,所以节点修理时间与人员数量的关系是一些离散的点,根据大量实际工作的统计,节点的修理时间与人员关系的近似关系可以用图1所示:

在图中Dic表示节点的极限时间,即节点可能的最短修理时间。

2、工期与人员的优化模型

为了建立“工期人员”的优化模型,本文假定:

1.每个节点都只有在其所有的紧前节点都结束后才能开始,并且节点的修理工作一旦开始,就不得中断,直至结束。

2.节点的修理时间都在最小和最大范围内变化

3. 项目的总工期是在各节点持续时间确定的条件下计算出来的关键线路的长度。

若某修理项目规定必须在工期内完成,要求总人数最少,可以建立工期固定,人员最少数学模型如下:

其中:HT为项目所需的人数;

di为节点的持续时间;

f1(d,)为节点所需的人数;

F为项目的总人数与单个节点人数之间的函数关系;

D为节点i极限状态下的持续时间;

DN为节点i正常状态下的持续时间;

ti为节点的结束时间;

TN为项目的实际工期;

TD为项目的计划工期;

P(j)为节点的紧前工序集合，P(j)={i|i工序为工序j的紧前工序}。

约束(2)是对节点修理时间的约束,保证节点的修理时间在允许的范围内,约束(3)是工序约束,保证节点的施工顺序符合逻辑关系。约束(4)是对工期的约束,因为在求解时约束(4)很难处理,所以引入罚函数的概念,把工期约束转换为罚函数M*max{0,TN-TD},其中M为充分大的正数,于是目标函数转化为:

式中M*max{0,TN-TD}的含义是:当实际工期TN大于计划工期TD时,取值M*(,TN-TD),这样目标函数的值将会非常大;当实际工期TN小于计划工期TD时,取值0,M*max{0,TN-TD}对目标函数无影响。采用罚函数的主要目的就是为了避免实际工期大于计划工期的情况出现[1]。

目标函数中,总人数与各节点人数的函数关系F可以利用时标网络计划法进行计算,即编制时标网络后,通过逐时段人员需要量叠加的方法,确定各时段的人员需求量,目标函数的取值HT就是所需人员最多的时段的人数。

二、优化模型求解算法

1、算法的基本思路

对于“工期人员”模型,本文采用基于网格划分策略的连续域蚁群算法的思想,转化为类似旅行商问题(简称TSP)。所谓网格划分就是在变量区域内打网格,在网格点上求约束函数与目标函数的值,对于满足约束条件的点,在比较目标函数的大小,从中选择较小者,并把该网格点作为一次迭代结果;然后在求出的点附件将分点加密,再打网格,并重复前面的计算与比较,直到网格的间距小于预先给定的精度[2]。

在本文的模型中,假设某一项目有n个节点(节点0为虚拟节点,表示项目的开始),将每一个节点时间变量分成N等份,这样共有(N+1)*n个子节点,图中每一个子节点表示一个对应的人数(0对应节点持续时间下限tmin,N对应节点持续时间上限tmx,在初始状态下分别等于极限状态下的持续时间和正常状态下的持续时间),如图2所示。这样,节点i位于第k个子节点时,对应时间为:tik=tiN+hj (N-k),对应的人员数量为:Hik=H i.o+hj△HiDck(其中hj=tmx-tm/N,△HIDc，,是图1中ab段的斜率,正常为负值)。图2中的边采用三元组表示,(i,j1,j2)表示第i个活动位于第j1个网格点上,第i+1个活动位于第j2个网格点上。这样工期人员模型实际上就是从第0列到第n列找出一条线路,使项目的总人数最少。

2、求解的步骤

对于本文‘工期人员”模型的改进蚁群算法的步骤如下:

1.确定各节点时间变量的取值范围:

2.将各节点的时间变量分成N等份,

3. 若max(h1,h2…….hn)<ε(其中ε为定义的精度),则算法停止,最优解为,否则跳到第(4)步。

4. 确定最大循环次数Ncmax和蚂蚁数n,给图2中各边(i,j1,j2)的信息素i,j1,j2赋予相同的初值,采用随机方法产生初始解。

5. 循环次数Nc=Nc+1,为每只蚂蚁搜索出的线路根据关键线路法(CPM)求出项目的工期T,并根据(5)求出项目所需的人员数H,记录人员数最少的蚂蚁路径作为问题的解。

6. 经过一次循环后,各边的信息素强度按以下公式更新:

式中:Tij1j2(Nc)，τij1p(Nc+1)分别表示第Nc次和第Nc+1次循环后各边的信息素强度;p为[0,1]之间的常数,表示路径上信息素的挥发因子;f表示此次循环后的人数H。若此次循环蚂蚁没有经过边(i,j1,j2)，则值Q/f为零。

7. 蚂蚁按照留在各边上的信息素强度以及各边的可见度选择路径,各边的选择概率按下式计算:

式中:α,β是用于调节信息素与路径可见度之间的关系的参数,η1j2为边(i,j1,j2)的可见度,表示搜索过程中的局部信息，ηij1j2=1/Hi+1j2 (Hi+1j2表示节点i+1采用第j2个方案时的人数)。

8. 对每只蚂蚁按照(7)选择下一节点,并根据(6)更新信息量。

9. 若Nc

工期人员优化模型问题的算法流程如图3所示:

三、实例应用

假设某一维修工作,其工作节点的逻辑关系及参数如图4所示,正常人数和正常时间是指正常工作条件下的参数,在此例中可以得出正常情况下项目的总工期为1590小时,人数为10人,而极限状态下可能的最短工期为960小时,所需人数为16人。由于各方面的需求,此修理工作要求必须在1200小时内完成,求所需的最少人数是多少。

采用Mat lab仿真进行求解计算,根据图(3)的算法流程进行编程,并设定算法的参数如下:Ncmax=50,n=20,P=0.1,α=1,β=1,ε=10程序运行结果如表1所示:

从程序运行结果,根据关键线路法求出该项目的完成时间为1192.1工时,所需最少人数为13人。

四、结束语

装备维修在现代战争中的地位越来越重要,而在战时,装备的维修时间是关心的首要因素。本文针对装备维修的性质,在装备维修网络图的基础上提出了“工期人员”的优化模型,并应用改进的蚁群算法对要求的时间内完成规定装备维修任务的最小人数问题提出了相应的求解方案,对装备维修保障工作具有一定的现实意义。

摘要：针对装备维修中基本保障单元的概念,为保证在维修工作过程中,以最少的人员在固定的时间内完成预定的维修任务,分析了修理工期与人力资源的关系,建立了固定工期人员最少的“工期人员”数学模型,并应用基于网格划分策略的连续域蚁群算法的思想对该模型的求解过程进行了研究。

关键词：装备维修,人力资源,优化,蚁群算法

参考文献

[1]胡华选.网络计划工期费用优化及其蚁群算法[D].大连:大连理工大学,2007.

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

[3]李万庆,孟文清,等.工程网络计划技术[M].北京:科学出版社,2009.

[4]Dero J,Siarry P.Continuous interacting ant colony algorithm based on dense heterarchy [J].Future Generation Computer System,2004,20 (5):841-856.

[5]傅英定,成孝予,唐应辉.最优化理论与方法[M].北京:国防工业出版社,2008.

蚁群算法模型篇7

近年来,国家电网公司确定建立以智能化为关键点的新型坚强电网,而低压电力线载波通信技术作为电力公司与终端用户信息交互的最直接方法, 已成为研究热点[1]。针对电力线载波通信技术的研究主要集中在阻抗匹配及耦合电路设计[2]、扩频与正交频分复用技术在电力线上的应用及性能分析[3-4]、电力线通信网络结构及路由算法[5-6]、信道估计与信道模型建立[7]。

信道建模技术是电力线载波通信系统设计和性能评估的关键。目前国内外电力线信道建模主要分为自底向上和自顶向下两类方法。所谓自底向上法是根据电力线网络的实际连接状态,考虑阻抗不匹配引起的反射和衰减特性来建立信道模型,该方法物理概念清晰,对不同的电力线拓扑结构能准确、快速地确定其传递函数,但计算量大,且由于实际的低压配电网阻抗的时变性及拓扑结构的复杂性,其实用性较差[8]。自顶向下法又分为两类:第1类是基于多导线传输理论的建模方法,它利用双端口传输矩阵求解电力线信道传递函数,其应用前提是传输线规格和网络的拓扑结构已知,然而由于低压电力线网络结构的复杂多变,这些参数难以准确获得,因此模型精确度不高[9-10];第2类是文献[11]提出的基于信道测量的多径信道传输模型,通过相应的参数拟合算法确定模型参数,该方法在传输线规格和网络拓扑结构未知的条件下,用少量参数即可描述复杂的电力线网络传输函数,较适用于高噪声、强衰减、阻抗变化范围大、具有频率选择性衰落的电力线信道建模。目前已有研究将人工神经网络[12]和遗传算法[13]等各种参数拟合法,以及改进粒子群优化算法[14]应用于电力线多径传输模型参数辨识。与文献[13]相比,改进粒子群优化算法在实验室环境下可获得较好的参数辨识效果,但其没有考虑复杂多变的电力线噪声特性对模型参数辨识的影响。

对于非线性系统参数估计,无先导卡尔曼滤波(unscented Kalman filter,UKF)算法采用自回归方法,根据观测信息和测量获得最小均方误差意义下的最优估计。应用UKF算法辨识系统模型参数需要解决两个问题:系统噪声协方差矩阵和测量噪声协方差矩阵的选取。前者影响UKF算法的滤波性能及参数估计精度,增大了系统的不确定性;后者取值不当会影响滤波器的修正速度,使滤波过程不稳定甚至发散。蚁群粒子群算法模拟生物进化过程, 可以随机搜索得到全局最优参数。为解决上述问题,本文采用蚁群粒子群算法对UKF噪声矩阵进行优化,从而实现电力线多径传输模型参数的最优估计。

1低压电力线多径传输模型

由于低压配电网存在众多分支和负载阻抗的不匹配,使高频信号在电力线上传输产生频率选择性衰减,引起多径传输。文献[12]把电力线通信通道看做是一个黑匣子,采用传递函数来描述信号传递特性,所提出的多径传输模型幅频特性如下式所示:

式中:N为路径总数;f为信号频率;gl和dl分别为第l条路径的加权因子和路径长度;va为信号传播速度,考虑到国内电力电缆通常所使用的PVC材料介电常数为4,取va=1.5×108m/s;a0和a1为衰减系数;a2为衰减因子,通常为0.5~1之间的常数,由电缆的物理几何特性决定。

实验表明,模型精度随N的增加而提高,但N增加,需要估计的参数也增加。当N=4时,需估计11个参数,当N=12时,需估计27个参数。

2蚁群粒子群优化的UKF参数辨识实现

2.1基于蚁群粒子群优化的UKF结构

基于蚁群粒子群优化的UKF结构如图1所示,其中Q和R分别为系统噪声和测量噪声协方差矩阵。UKF根据系统各时刻的测量值yk、输入值uk及选定的滤波参数值,通过时间更新与量测更新得到系统状态的后验估计w^k;根据各时刻当前的目标函数值和滤波参数值,使用蚁群粒子群算法对滤波参数Q和R进行寻优,将得到的修正值作为UKF的输入参数进行参数估计,直至得到优化的状态估计值w^opt。

2.2蚁群粒子群混合算法

2.2.1粒子群优化算法

粒子群优化算法是模拟鸟群捕食行为过程中通过集体协作,寻求群体最优解的全局优化算法。每个粒子(d维解空间的一个候选解)根据自身和群体经验调整飞行轨迹向最优点靠拢。根据式(2)和式(3),粒子x通过迭代更新自己的速度和位置:

式中:Xxd和vxd分别为粒子x的飞行位置和速度; pbest为粒子x迄今为止搜索到的最好位置;gbest为整个粒子迄今为止搜索到的最好位置;G为迭代次数; ω 为惯性权重;c1和c2为学习因子;r1和r2为0~1之间的随机数。

通过不断学习更新,粒子向个体最优位置和全局最优位置加速运动,最终输出全局最优解。惯性权重ω 使粒子具有扩展搜索空间、保持运动惯性的作用。为使ω 能针对不同的高维、复杂非线性问题自适应选取,将粒子群算法的ω 划分若干子区间离散化取值,并赋予相应的信息素作为蚁群算法的一条路径。根据不同路径上信息素和粒子的空间分布,按概率选择ω 生成新粒子来更新各条路径的信息素。

2.2.2蚁群算法

蚁群算法是意大利学者Dorigo受蚂蚁觅食时路径选择行为启发提出的。蚂蚁通过行走不同的地点(路径)之间转移,t时刻蚂蚁p从位置z向位置δ 的转移概率Mzδp(t)为:

式中:τzδ为t时刻蚂蚁的信息素轨迹强度;ηzδ反映了蚂蚁由位置z转移到位置δ 的启发程度,也称为能见度;s为蚂蚁允许到达的位置;Yp为蚂蚁p下一步可以选择的位置;α和β为调节系数。

由式(4)可知,转移概率与ηzδ和τzδ成正比。一次循环完成后,t+1时刻蚁群在路径(z,δ)的信息量 τzδ(t+1)根据式(5)调整:

式中:Δτzδp(t,t+1)为第p只蚂蚁在本次循环过程中留在路径(z,δ)上的信息素量,路径越短信息素释放就越多;ρ为信息素挥发系数,则1-ρ为信息素残留因子,通常设置0<ρ<1以避免路径上信息量的无限累加。

2.2.3惯性权重参数区间离散化

在蚁群粒子群优化算法中,将划分不同的区间, 惯性权重ω 以截断正态分布概率分别在各子区间取值,如果在进化初期接近最好点,ω 可能随机产生相对小的值,可加快收敛速度;如果在算法初期找不到最好点,ω 的线性递减使算法最终收敛不到此点, 经仿真对比验证,采取ω 随机化就可以克服这个缺点。正态分布曲线是一个中间高、两边低的 “凸字形”曲线,如果ω 选择两边偏平滑的区间,则ω 值在整个迭代过程中变化相对平缓,因此,将ω 的取值限定在中间凸起的部分。ω 取值如式(6)所示:

式中:h为区间个数;l对应不同的路径。

以l对惯性权重进行编码,l值确定则相应的ω 也就确定。各粒子需要从h个区间的l种路径中选择生成ω 的方法。通过对ω 取值区间的离散化,将各个ω 子区间作为蚁群算法的一条路径,根据各条路径上的信息素浓度与粒子的空间分布信息,选择路径(即ω)实现粒子进化搜索,并根据粒子进化信息实现各条路径信息素浓度的更新。

2.3基于蚁群粒子群优化的UKF辨识算法的实现

结合式(1),系统的状态变量为电力线信道模型的待求参数,将UKF滤波参数作为粒子群算法的粒子,根据系统输入频率f和观测信息H (f),对增广状态变量使用UKF技术,递推求出系统状态变量,以获得最优系统噪声和观测噪声矩阵。

系统状态变量根据电力线路径数目不同分为11个(4径)和27个(12径),模型输出变量为1个。以4径模型为例,系统噪声和观测噪声协方差矩阵分别记为式(7)和式(8)。

为使优化计算简化,令系统噪声矩阵对角元素相等,即q11=q22=…=q1111=q,则待优化的参数矩阵可表示为式(9)。

2.3.1适应度函数的选取

使用蚁群粒子群算法进行参数优化时,需要正确设计适应度函数,否则会发生早熟收敛,只获得局部最优解。本设计中,3种算法优化是以实测数据yk与滤波输出w^(ψ^xk(G))的均方误差最小为目的,即

式中:f(ψ^x(G))为迭代到第G代时第x个个体的测量值与估计值的均方差;M为估计长度;ψ^xk(G)为迭代到第G代时第x个个体的参数辨识值。

2.3.2基于UKF的参数辨识算法流程

1)初始化:

式中:E(·)表示数学期望;w0为初始状态向量;w^0为初始状态向量估计;P0为初始状态误差协方差矩阵。

2)计算采样点χk-1和权值μi:

式中:μim(i=0,1,…,2n)为一阶统计特性加权系数;μic(i=0,1,…,2n)为二阶统计特性加权系数;n为状态向量w的维数;常数ε为采样点的分散程度, 通常取10-4≤ε≤1;λ=ε2(n+k)-n,为一个比例因子;常数ξ的值取决于w的先验分布,高斯分布的ξ 最优值为2。

3)计算预测状态均值w^k|k-1及协方差矩阵Pk|k-1,重新计算采样点:

4)计算预测测量均值y^k、协方差矩阵Pyy，k和状态向量与测量值的协方差矩阵Pwy，k:

5)计算卡尔曼增益矩阵Kk,并更新状态向量w^k及其协方差矩阵Pk:

式中:k即为所求的提取向量。

3基于蚁群粒子群优化的UKF参数辨识算法验证

3.1初始值的确定

电力线信道初始值由多次测量的平均值确定, 分别在哈尔滨某居民小区相距1 000m的实际供电插座之间测量。实验中采用数字存储示波器记录发送及接收信号后,在计算机上通过计算得出信道的幅频和相频响应函数。取4路径和12路径,采用基于蚁群粒子群优化的UKF算法、UKF算法和文献[14]的改进粒子群优化(EPSO)算法进行参数辨识。辨识中衰减和路径参数的选取根据最小二乘法拟合结果得到,路径参数dl的选取以实际载波通信网络的物理长度为依据。试验中经过反复调解UKF滤波参数,系统噪声qs和观测噪声ro的取值范围分别取[0,0.000 6]和[1,7]较为理想。

3.2仿真与性能分析

运用本文提出的基于蚁群粒子群优化的UKF算法进行电力线多径信道参数辨识,计算该模型的动态响应来拟合实际测量值。参数设置为:粒子数取100,h=10,α=1,β=7,ρ=0.7,c1=c2=1.8,预定迭代次数为300,进行200次运算得出平均结果。运行本文提出算法,经300次迭代后种群目标函数值分布如图2所示,几种算法目标函数最优解的变化如图3所示。

可见,基于蚁群粒子群优化的UKF算法目标函数的最优解(均方误差)经过约100次迭代后趋于恒定值,比UKF算法的240次快得多,与EPSO算法的82次相当,但性能明显优于EPSO算法。经过120次迭代后,种群中80%的个体目标函数值均在最优解附近,得到了限定范围内的全局最优解。

标准粒子群算法复杂度为O(d′),d′为粒子数量;蚁群算法复杂度为O(l3);UKF算法的复杂度为O(n3)[15]。比较3种算法在首次迭代时的时间复杂度可见,粒子群算法复杂度最低,具有较快的收敛速度,但后期容易陷入局部极值点,导致算法精度降低。本文算法通过蚁群算法选择最优惯性权重,根据粒子群算法找到最优粒子,通过更新的粒子来更新信息素浓度,再利用蚁群粒子群算法对UKF的滤波参数进行寻优,将得到的修正值作为UKF的输入参数,从而在降低系统复杂度的同时,保证了算法求解精度。

3.2.1参数辨识结果

将基于蚁群粒子群优化的UKF算法对仿真所得的数据进行辨识,4径和12径辨识参数分别如表1和表2所示。

注:衰减参数a2=1,a0=0.035,a1=6.78×10-10。

注:衰减参数a2=1,a0=0.001 6,a1=2.26×10-9。

3.2.2比较与分析

几种算法仿真与居民区实测曲线的幅频衰减特性及相位失真特性拟合结果如图4—图7所示。

对比图4—图7中的实测曲线和拟合曲线,可看出其幅频特性和相频特性均得到较好的吻合效果,验证了电力线多径传输模型的可行性。使用基于蚁群粒子群优化的UKF算法的4径拟和精度明显低于12径拟和精度,证明了路径数越多,模型精度越高,但也增加了运算时间,因此,路径数的选择需折中考虑。

分别采用UKF算法、EPSO算法和基于蚁群粒子群优化的UKF算法对低压电力线信道幅值衰减特性进行了200次辨识,路径数分别取4和12,最大迭代次数设为300,所得误差统计特性如表3和表4所示。

由表3和表4可见:虽然4径参数辨识中, UKF算法的精度略高于本文算法,但运算时间远大于本文算法,实际应用中应综合考虑运算精度与运算时间确定最优算法。实验中对4~20径信道模型均进行了仿真,6径以上本文算法的精度均高于UKF算法,运算时间则远低于UKF算法(约为UKF算法的1/2)。本文算法搜索到全局最优附近区间的概率远大于EPSO算法,说明其稳定性明显优于EPSO算法;且本文算法与EPSO算法的平均辨识时间接近,但其平均误差只有EPSO算法的1/2,说明本文算法具有优良的性能。

4结语

低压电力线分布广泛,连接千家万户,使得低压电力线载波通信技术在实现家居防范、家用电器控制和多表集中抄送方面具有得天独厚的优势,但电网环境的污染给可靠通信带来了一些特殊困难。建立一个能够模拟低压电力线信道特性,针对载波通信设备进行实际测试和分析的系统,对低压电力线通信技术的研究具有实际价值。本文对不同电力线通信场景进行测量,通过相应参数拟合算法确定模型参数,构建丰富的模型参数信息库,力求建立一个完善的电力线信道模拟仿真测试分析系统,为载波通信产品开发者提供一个试验平台。

蚁群算法模型篇8

时间表问题TTP (Timetabling Problem) , 是指在一段时间里, 为一组任务安排合理的时间片, 且要满足特定的约束条件。1962年Gotlieb提出一个课表问题的数学模型[1], 此后人们对课表编排问题的算法, 解的存在性等问题作了许多探讨, 从而使课表编排问题成为TTP的典型问题。Cooper等人在文献[2]中以5种不同的方式证明了TTP问题是NP-完全类问题。

相继出现了基于整数规划算法[3,4], 网络流算法[5]等的求解算法。此外, 研究者还通过简化问题本身, 使之转换成和图着色问题相似的问题来处理[6]。近十多年来, 又出现了一些基于新的搜索技术的算法, 比方说模拟退火[7], 禁忌搜索[8], 遗传算法[9], 最大最小蚂蚁算法 (MMAS) [10]。在不同的文献中时间表问题有相当多数量的不同变体, 限制条件差异大[11]。

1 大学课程时间表问题概论

1.1 问题描述

本文测试的是Socha等在文献[10]中使用的11个问题实例, 是一个典型的大学课程时间表问题[12,13]的简化问题, 给定了三类软限制条件, 三类硬限制条件。问题实例包括一个课程任务集合E, 时间片集合T, T={t1, …, tk} (k = 45, 一周5天每天9个时间片) , 教室集合R, 学生集合S, 教室的特征集合F, 每个教室有一个最大的容量。一个可行的时间表, 要求所有的课程任务都能分配到一个时间片和一个教室, 且满足下面的硬限制条件:

1) 同一个时间片中, 没有一个学生分配到两个或多个课程任务;

2) 教室足够大, 能够容纳上课的学生, 且要满足容纳的课程任务所要求的所有特征;

3) 任何一个时间片, 只能分配一个课程任务到一个教室中。

对于上面的三类硬限制, 一旦违反就是非可行解, 产生的硬限制条件违反函数叫HCV (hard constraint violations) 。

此外, 下面三个软限制条件:

1) 学生在一天的最后一个时间片分配到课程任务;

2) 学生在一天中分配到的连续课程任务超过两个;

3) 学生在一天中只分配到一个课程任务。

如果符合条件, 就会产生对应的软限制条件违反值, 软限制条件违反函数SCV (soft constraint violations) 是问题的目标函数。

不论SCV多大, 可行解总是比任何非可行解都具有更高的优先级, 可行解中SCV越小, 解的质量越高;所有的非可行解被认为具有一样的优先级。问题的目标是, 产生可行解且最小化SCV的值。

1.2 蚂蚁的数据结构和局部搜索

蚂蚁的数据结构:

局部搜索LS (local search) 是一种重要的改进搜索过程, 本文的LS采用了两种交换操作:第一种是移动一个课程任务到一个新的位置中;第二种是两个课程任务的位置交换。LS通过在解的邻域中进行选择比较, 从而获得一个局部的最优解。

2 UCTP求解过程

基于以上的问题描述, 本文将考虑如何将分配问题, 转化为蚁群算法能够解决的路径优化问题。

2.1 图的构造

ACO (Ant Colony Optimization) 算法中很关键的一个部分, 是将实际问题映射为一个图的构造过程[14], 图上的一条路径就代表了问题的一个解。本文采用了一种新的构造模型, 如图1所示。

图1中蚂蚁按照课程任务集的顺序, 为每一个课程任务e∈E选择时间片t∈T和教室r∈R, 时间片、教室笛卡尔集中的元素tkrk (本文中称作一个位置) 只能被使用一次, 一旦分配给某个课程任务, 就不能再分配给其它课程任务。

2.2 课程任务相关性及课程任务集合的排序

满足下面条件之一, 两个课程任务就具有相关性:

1) 如果某位同学既要上课程e又要上课程e’, 那么课程e与e’就不能安排在同一个时间片, 课程e与课程e’相关。

2) 如果课程e, e’, 都只能分配到唯一的教室C, 课程e, e’, 相关。函数c (e, e’) 定义如下:

d (e) ={e′∈E＼e|c (e, e′) ≠0} (2)

计算课程任务相关性, 并定义顺序≺,

e≺ e’ ⇔ d (e) ≥ d (e’) (3)

对于给定的课程任务集, 本文中的算法采用了两种不同的排序方式, 让一只蚂蚁走按照课程任务相关性排序后的路径, 剩余的蚂蚁走随机排序后的路径。按照课程任务相关性排序, 增强了对蚂蚁行走过程的指导性, 让限制比较多的课程任务优先进行选择;其它蚂蚁走随机排序后的路线, 是为了增大蚂蚁的搜索范围, 保证初始解的多样性。结果表明, 相关性进行排序, 有助于小规模的问题迅速找到可行解, 而随机的顺序则有利于中等规模问题找到可行解, 提高了解的质量。

2.3 带预处理机制的解的构造

依照排序后的课程任务顺序, 每只蚂蚁为当前课程任务, 在满足条件的所有位置中, 根据概率pei, t, r, 尝试寻找一个合适的位置。

设部分解集Ai: Ei→ ( T, R ) , i = 0, … , |E|, Ei = { e1 , …, ei}, 初始解A0 =Ø, Ai=Ai-1∪ { (ei, t, r) }。 (T’, R’) 是 (T, R) 中除去已经分配位置后剩余的位置, 信息素τ ( Ai-1 ) ∈[τmin , τmax], η ( Ai-1 ) 是启发信息。概率选择公式如下:

$p_{e_{i}, t, r} (τ (A_{i - 1}), η (A_{i - 1})) = \frac{(τ_{e_{i}, t, r} (A_{i - 1}))^{α} (η_{e_{i}, t, r} (A_{i - 1}))^{β}}{\sum_{θ \in (Τ^{'}, R^{'})} (τ_{e_{i}, θ} (A_{i - 1}))^{α} (η_{e_{i}, θ} (A_{i - 1}))^{β}}$ (4)

为了保证蚂蚁在满足条件的位置中进行选择, 进行了如下的预处理:

1) 在剩余的位置中选择, 已经被使用过的位置不再使用, 保证HCV1=0;

2) 课程任务与待分配到的时间片中的其它课程任务不存在相关性, 保证HCV2=0;

3) 在满足课程任务特征要求的教室集合中选择, 保证HCV3=0;

这样就保证课程任务如果分配到位置, 都应该是合适、可行的, 当然, 可能产生由于前面课程任务位置的不合理分配, 后面的课程任务分配不到合适位置的情况, 本文会在下一步的改进过程中, 尝试为没有分配到位置的课程寻找合适的位置。

2.4 启发信息

与文献[10]将启发信息设置为常数 (实质是没有起到作用) 区别, 本文设置了如下的启发信息计算公式:

$η_{e, t, r} (A_{i - 1}) = \frac{1.0}{1.0 + V_{(e, t, r)} (A_{i - 1})}$ (5)

V (e , t , r) ( Ai-1 ) 是将 (e , t , r) 加入到部分解后, 可能产生的软限制条件的惩罚值;实验结果表明, 启发信息对于中小规模问题迅速构建可行解是有帮助的。

2.5 信息素更新

设置路径上的初始信息素为τmax, 每次迭代之后, 在所有蚂蚁经过的路径上, 进行信息素的更新, 只有最好解蚂蚁的路径上获得新的的增量, 更新公式如下:

ρ∈[0, 1]是信息素挥发因子, 由于采用的是MMAS[15], 更新后的信息素还要进行下面的检测:

3 改进过程

本文借鉴文献[16], 基于上面构造的问题模型, 通过下面的改进过程对未分配课程任务进行处理。分三步骤:

(1) 改进函数为所有未分配到位置的课程检查每一个时间片, 看时间片是否排满课程, 若没有, 且未分配的课程与时间片里面的已有课程都不相关, 则试着将课程插入, 调整此时间片里所有课程的教室顺序后, 看是否时间片中的所有课程能够都分配到合适教室, 不可行则不插入, 尝试下一个时间片。

(2) 洗牌函数为剩余未分配课程随机选择一个时间片, 尝试插入, 检查课程相关性, 调整教室顺序[同上], 如若能够插入且没有新的课程被挤出或插入后有新的课程被挤出, 则将此课程插入。此时, 给被挤出的新课程一次机会, 调用改进函数。

(3) 求生函数如若还存在未分配的课程, 则随机找寻一个时间片, 将这个时间片中的课程全部移出;将未分配的课程放入, 逐个插入移出的课程并判断相关性, 然后为所有放入的课程重新分配教室, 最后为产生的未分配的课程调用改进函数和洗牌函数。

上面三个过程, 一旦得到可行解就退出, 经过改进, 所有课程任务都能够分配到合适的位置, 保证了解的可行性。

4 算法的框架

以下是本文算法的框架

读取问题实例中的数据, 如课程任务、学生、教室集等;

按照课程任务相关性为课程任务集合排序;

构造global best ant并赋予随机解;

输出:Cglobal best ant, 释放申请空间。

5 结果比较及分析

所有10个问题实例分为小规模、中等规模[17]。通过修改问题发生器的输入参数可以产生不同规模的问题, 修改随机种子数的值, 可产生同等规模的不同实例[18]。

每个问题实例都独立地运行10次, 按规模大小, 每次运行的最长时间分别是30s, 300s, 10只蚂蚁, α, β和ρ分别是1, 0.5, 0.7。运行环境, PC机, Intel 1.66 GHz处理器, 512MB内存, 操作系统为Windows XP, 程序设计工具Microsoft Visual C++ 6.0。

表1, 表2给出了本文算法与其它算法, 在求解不同规模问题上的比较, 表中的值是目标函数值。表2中的百分比是运行结果中, 未得到可行解的比例, 两张表中的最好值都用粗体标出。其中NEW Ant是本文的算法。

表1中, 本文的算法在三个问题实例上都取得了最优解, 目标函数值都是0, 解的总体质量上不如RIIA和VNS with Tabu, 但运行时间比RIIA和VNS with Tabu的50s要短, 同时解的质量好于其它4种算法。

表2中, 本文的算法在所有的中等规模的问题实例上都取得了绝对优势的解, 且运行时间短, 比方说, RIIA用了8小时, Ant Algorithm使用了900s, NEW Ant是300s。可见, 在10个问题实例中, 本文的算法在8个实例中都获得了绝对优势的解。

6 总结

时间表问题是一类特殊的资源调度问题, 随着现代社会相对可利用资源的日益紧张, 做好各类资源的统筹安排、优化利用是一件非常有意义的事情。本文分析了大学课程表问题的特征, 重新构造求解模型, 对已有的蚁群算法求解过程进行优化, 并加入改进的过程, 保证问题都能得到可行解, 并利用局部搜索优化目标函数。所有10个问题实例的结果表明, 本文的算法在时间和解的质量方面取得了明显的改进。

蚁群算法模型篇9

蛋白质折叠问题是生物信息学中最突出的问题之一。蛋白质的生物学功能和属性主要取决于它们的结构。从化学上来看，蛋白质是每个元素只有20个不同氨基酸的链。每个氨基酸由一个中心碳原子组成，键合到氨基、羧基和侧链或残基。因此，氨基酸的不同就在于残基。残基之间的最大的差异就是其疏水性。残基属性与环境共同影响使得蛋白质链折叠成一个复杂的构象，构象被称为分子的“天然”构象。天然构象有小的Gibbs自由能，这种构象对蛋白质功能是非常重要的。

为了掌握蛋白质结构，已经引入很多种格点模型。其中一种最有名的用于蛋白质折叠的格点模型是所谓的疏水极性模型(HP)[1]，其中只考虑两种氨基酸，疏水性(H)和极性(P)。目前，一些有名的启发式优化方法已被应用于预测2D HP格点模型的蛋白质结构，包括模拟退火(SA)[2]、遗传算法(GA)[3]、蒙特卡洛算法(MC)[4]和蚁群优化(ACO)[5]。后者已被证明是2D HP蛋白质折叠问题最有效的算法。本文将ACO算法结合牵引移动和本地搜索机制，提出了一种基于牵引移动的蚁群优化算法(ACO+)来预测蛋白质结构。

1 HP模型

HP模型是最重要和最简单的代表性格点模型。该模型的理论基于疏水性是小的球蛋白形成天然构象的主要驱动力。在HP模型中，蛋白质的氨基酸序列的序列被描述成一个由疏水残基(H)和极性残基(P)组成的序列，HP模型的序列构象根据自避免原则限制在一个二维格点上，也就是说，所有的氨基酸是嵌入在格点中，例如，在序列中的相邻的字符在格点中占据相邻的网格点，在格点中的网格点不能被多个字符所占据。构象的能量被定义为结构上不相邻但拓扑相邻的疏水残基对的个数，可以通过拓扑HH的数目来计算，EHH=-1和EHP=EPP=0。因此，最小自由能构象与构象的最大HH键的数目有关。例如，蛋白的最低能量构象(HPHPPHHPHPPHPHHPPHPH)如图1所示，其中“○”代表“极性”，“●”代表“疏水性”。这个问题已被证明是NP完全问题[6]。

2 蚁群优化算法

蚁群优化算法是受自然界真实蚁群的集体觅食行为启发用于解决各种组合优化问题的随机搜索方法[7]。蚁群算法基于stigmergy思想，成员与群体之间通过环境的相互作用间接地沟通。蚂蚁在觅食过程中，在地面留下信息素间接地与对方沟通。信息素会影响其他蚂蚁的决策过程。这种蚂蚁个体之间简单形式的沟通使蚁群产生复杂的行为和能力。

从计算的角度来看，ACO是一个迭代搜索方法，在该方法中，蚁群对一个给定的问题重复构造候选解。蚁群算法已经成功地应用到很多方面，包括旅行商问题、图着色问题、二次分配问题和车辆路径问题[8,9]等。

下面以旅行商问题为例，介绍蚁群优化算法基本原理。

设bi(t)表示t时段位于城市i的蚂蚁数目，τi j(t)为t时段路径(i,j)上的信息量，n表示城市的个数，即该问题的规模，m为蚂蚁的总数目，则有:

设Γ为t时刻集合C中城市两两路径上残留的信息素量集合，则:

在初始时刻各条路径上的信息素量相等，均为P，τij(0)=P。那么基本蚁群算法的寻优是通过有向图g(C,L，Γ)来实现的。

因为蚂蚁k不能重复经过同一个城市，所以建立一个禁忌表tabuk(k=1,2，…，m)来记录蚂蚁k走过的城市，禁忌表随着时间作动态调整。

建立蚂蚁k由i城市转移到j城市的状态转移概率如下:

式中α为信息启发式因子，表示路径的相对重要性，是对所积累的信息素影响作用的一个加权值;β为期望启发式因子，表示能见度的相对重要性;ηij(t)为启发函数，其表达式为:

在一个循环结束后，要对残留信息进行更新处理。所以对于t+n时刻给定如下信息量处理规则:

式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留，ρ∈[0,1);Δτkij(t)表示本次循环中蚂蚁k留在路径上的信息素量。

信息素的更新策略有多种方法，每种更新策略的主要差别体现在Δτkij(t)的求法上。我们规定蚂蚁在完成一个循环后更新所有路径上的信息素，其方程式为:

式中Q表示蚂蚁携带信息素的量，其值的大小影响算法的收敛速度;Lk表示第k只蚂蚁在本次循环中所走路径的总长度。

3 求解2D蛋白质折叠问题的蚁群算法

对于一个给定的HP蛋白质序列，由ACO算法中的蚂蚁构建候选构象，采用相对折叠方向代表候选构象如图2所示。其中直走(Straight)，左转(Left)，右转(Right)表示相对于它给定序列中的直接前辈在格点上每个氨基酸的位置[10]。

3.1 构建阶段

在本文的蚁群算法中，初始化时，信息素τi,d=1/3,i=1,2，…，n,d∈{L,S,R}，每个蚂蚁首先在格点上确定第一和第二氨基酸的位置。第一个氨基酸在0，即(x1,y1)=(0,0)。而第二个氨基酸在右侧0，即(x2,y2)=(0,1)。然后每个蚂蚁的构建从第三个氨基酸开始(i=3)。蛋白质构型选择哪个相对方向折叠由启发式函数ηi,d和信息素τi,d决定如式(8):

在这里，参数α>0和β>0确定信息素和启发信息的相对影响力。然后，启发式值定义为ηi,d=exp(ΔEi,d/0.3)，其中d∈{L,S,R}，并ΔEi,d被定义为发生在每个方向上的部分构象的能量变化。信息素表明在序列位置i使用d方向是可取的。

如果没有方向可能折叠(如果所有邻位的氨基酸位置被其他氨基酸占用了，一个未完成的构象不能在给定的格点位置扩展)，改进算法使用复制机制来解决这个问题:如果部分构象不能够构建在序列位置i，复制目前具有最低能量的其他蚂蚁的部分构象(从j=1到i-1)，继续构建。当然，必须确保所有蚂蚁同步。复制机制有效地消除了无效结构以维持构象的多样性[11]。

3.2 基于牵引移动的局部搜索

在局部搜索阶段，采用一个有效的方法—牵引移动[12]，这组移动是完整、可逆和局部的。构建结束后，每只蚂蚁对各自的候选构象应用牵引移动。

沿着氨基酸序列加速方向，假设顶点i为第i个氨基酸位置(xi,yi)。空位F是(xi+1,yi+1)的邻位，同时也是(xi,yi)的对角相邻位置，如图3所示。(xi,yi),(xi+1,yi+1)和空位F构成正方形的三个角。假设位置L的第四个角是C。对于发生牵引移动，位置C必须是空位或恰好为(xi-1,yi-1)。如果C=(xi-1,yi-1)，只需把顶点i移动到位置F完成移动。如果C是空位，顶点i移动到位置F，顶点i-1移动到位置C，然后执行以下移动:从顶点j=i-2开始直到顶点1，置(xj,yj)=(xj+2,yj+2)，直到达到一个有效的构象。

为了获得低能量构象，沿着给定序列对每个氨基酸执行牵引移动。过程中，将牵引移动获得的所有有效构象保存。最后，接受以最小能量构象作为局部搜索的结果。

如图3,(a)如果第四个角C为顶点i-1，移动顶点i到空位F。(b)否则，顶点i-1移动到C，移动可能已完成。(c)如果未完成移动，顶点i-2移动到顶点i先前位置，顶点i-3移至顶点i-1先前位置，直到重新达到一个有效的构象。

3.3 信息素更新

在每一次构型和局部搜索以后，所有的蚂蚁以标准方式更新信息素:τi,d=ρτi,d+Δi,d,c。ρ<1是信息素的保留系数，Δi,d,c是给定蚁群候选构象的解的相对质量，如果该构象在序列位置i向d位置折叠，否则为0。这里，定义Δi,d,c=E(c)/(E*)3，其中E(c)是当前构象的自由能，E是2D标准蛋白质序列最低的自由能。

3.4 算法描述

通过将牵引移动引入ACO，提出了一种改进的ACO算法(ACO+)。计算过程如下所示:

初始化信息素(见3.1节)，并设置最大迭代次数m=300。设n为蚂蚁数量，并设α=1，β=2，ρ=0.8。

设j=1

While(j≤m)do

设置第一和第二氨基酸的位置(见3.1节)

For i=3 to len do

//len是氨基酸序列长度

For k=1 to n do

If位置i没有位置折叠

复制目前最小能量的另一只蚂蚁的构件(从i=1到i1)

计算τi,d和ηi,d

根据方程(1)确定氨基酸的位置

Else

计算τi,d和ηi,d

根据方程(1)确定氨基酸的位置

End do

对每只蚂蚁(见3.2节)的构象应用牵引移动，并保存该构象的最低能量

更新信息素值(见3.3节)

End do

输出最低能量构象

4 实验结果及分析

为了测试改进蚁群算法(ACO+)的性能，在八个基准实例上分别运行蚁群算法和ACO+，如表1所示，设置最大迭代数m=300，使用200只蚂蚁为最小序列(N≤25),1500只蚂蚁为最大序列。算法在英特尔酷睿i5 2.40 GHz的CPU和4 GB的RAM电脑上运行。

表1中，Emin是2D标准蛋白质序列的已知最小能量。EACO是ACO算法得到的相应的最小能量的蛋白质序列。EACO+是ACO+算法获得的最小能量。从表1中可以看出，ACO序列1、2、3获得的最优解，序列4、5获得的次优解。针对序列6、7、8，结果不够好:它们与最优值都有-2的差异。然而，ACO+除了三个长序列都实现最佳解决方案。对于这些长序列，ACO+实现次优值，与最优值有-1的差异。显然，针对表1中序列4～8,ACO+比蚁群算法取得更好结果。ACO+的这五个序列最低能量构象如图4所示。

5 结语

本文引入蚁群算法来解决蛋白质折叠问题，通过将基于牵引移动的本地搜索机制加入ACO，提出一种改进的蚁群算法(ACO+)来预测蛋白质结构。实验结果表明，ACO+可以比ACO获得更低能量构象，特别是对长氨基酸序列。显然，对于采用蚁群算法解决2D HP格点模型蛋白质折叠问题，牵引移动能真正提高ACO性能。在今后的研究中，将进一步考虑改进的ACO+算法，并将改进的算法应用于3D HP格点模型，并为蛋白质折叠模拟设计更有效的算法。

参考文献

[1]Lau K F,Dill K A.A lattice statistical mechanics model of the conformational and sequence spaces of proteins[J].Macromolecules,1989,22(10):3986-3997.

[2]Sali A,Shakhnovich E,Karplus M.How does a protein fold?[J].Nature,1994,369(6477):248-251.

[3]Unger R,Moult J.Genetic algorithms for protein folding simulations[J].Journal of molecular biology,1993,231(1):75-81.

[4]Liang F,Wong W H.Evolutionary Monte Carlo for protein folding simulations[J].The Journal of Chemical Physics,2001,115:3374.

[5]Shmygelska A,Hoos H H.An ant colony optimisation algorithm for the2D and 3D hydrophobic polar protein folding problem[J].BMC bioinformatics,2005,6(1):30.

[6]Berger B,Leighton T.Protein folding in the hydrophobic-hydrophilic(HP)model is NP-complete[J].Journal of Computational Biology,1998,5(1):27-40.

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

[8]Dorigo M,Di Caro G.Ant colony optimization:a new meta-heuristic[C].Evolutionary Computation,1999.CEC 99.Proceedings of the1999 Congress on.IEEE,1999,2.

[9]Dorigo M,Di Caro G,Gambardella L M.Ant algorithms for discrete optimization[J].Artificial life,1999,5(2):137-172.

[10]何莲莲,石峰,周怀北.改进的蚁群算法在2D HP模型中的应用[J].武汉大学学报:理学版,2005,51(1):33-38.

[11]周方,廖波.改进的蚁群算法及其在2D HP模型中的应用[J].计算机工程与设计,2009,30(22):5175-5177,5181.

【蚁群算法模型】推荐阅读：

蚁群算法07-12

蚁群路由算法05-18

蚁群系统算法10-04

并行蚁群算法08-16