论文部分内容阅读
【摘 要】 在通信网络铺设时,建立各节点及节点之间距离的矩阵,利用图论中的方法,转化为一个全连通的图,在只考虑距离最短的情况下,利用prim算法得到了费用的最小生成树及最短路径。为了更加清楚、全面的表现出影响网络铺设的各种因素,建立起了涵盖链路通断的概率、链路数目及网络流量的组合优化模型,采用蚁群算法计算在不同的度的要求、不同的链路通断概率、最大的流通量这三个约束下的连接情况及对应的铺设距离。
【关键词】 prim算法 网络铺设 蚁群算法 优化设计
Study Ant colony algorithm based on network rollout planning
【Abstract】 Laying in communications network, to establish the distance between each node and nodes in the mat.rix, using graph theory methods, into a fully connected graph, considering only the shortest distance in the circumstances, the use of prim algorithm has been cost The minimum spanning tree and shortest path. In order to more clearly and comprehensively the performance of laying out the various factors that affect the network has established a link off covering the probability of links a combination of numbers and network traffic optimization model, using ant colony algorithm in a different degree requirements, different link-off probability, the largest circulation of these three constraints of the connections and the corresponding distance laying.
【Key words】 Prim algorithm Network rollout Ant colony algorithm Optimization design
通信网络铺设一直是网络发展规划研究领域的热点,很多学者为此展开了广泛而深入的研究,并取得了很多具有参考价值的结果。为了将分散终端连接起来,一般通过地下电缆进行连接,当已测知各结点之间的需要连接的距离,考虑到费用与效率问题,则需为网络规划者提供最佳连接方案。
针对通信网络铺设问题,首先要考虑的是设计一个网络的标准:确定网络的拓扑结构;确定网络中的信息的路径方向;网络中流量的分配控制;网络在使用过程中是否稳定可靠。因此网络优化也应针对上述四个方面,即拓扑结构优化、路径优化、流量分配优化和可靠性优化。通信网网络优化的最终目标是在尽量满足特定要求的情况下,使整个网络的总投资最小。对于一个通信网,不同的网络结构,其最优的组织方式可能不同,对于不同的组织方式,其最优的流量分配方案可能不同,因此以上四个优化过程是紧密相连的整体。
1 通信网络规划模型
在通信网络规划上,一般具备以下假设:网络费用仅与铺设距离相关,可假设成简单的正比关系;各个节点之间的重要性是对等的,不存在级次差别;一个节点和其它的节点的连接是等可能的,且一个节点可以连接的节点是不受限制的;节点的度不相同将导致的各个节点间的流量存在差异;网路的稳定性仅与节点及节点所连的线路的多少有关。
根据前面的假设,铺设成本仅与铺设长度相关。这样问题就转化成为了求解一个保证连通性的最短铺设方案。根据节点及节点之间距离的矩阵,首先可以构造一个全联通的图,每一个连接点是图中的一个节点,矩阵中第i行第j列的元素值大小就是边(i,j)的权重。根据前面的分析,问题就抽象成为了求解这个完全图的最小生成树。对于赋权连通图G=(V,E,W),式中W=[wij]n•n为图G的有权矩阵,其中wij>0且wij=wji,wii=∞,D(i,j)=wij表示顶点i与顶点j之间的距离[(i,j)∈V]。引入一个0、1变量xij,0表示该路径未被选入,1表示该路径被选入,那么最小化费用这一目标函数可以表示为:min z=wij•xij
根据图论知道,最终生成的为一棵树,由树的性质,我们知道树的边的总和应等于总节点数减去一:wij=n-1
最小生成树是一个无环的图,用V表示所有节点,S表示V的子集,那么在任一子集中必须要满足不存在环的条件,数学表示为: xij≤s-1?坌s?奂V,s≠?覫
现实中若仅考虑费用的问题常常无法满足要求,对于度为一的节点,若与它连接的链路被断开,那么它们就处于“瘫痪”的状态,没有与外界连接,因此这样的节点的稳定性是最差的。所以要人为的增加度的约束,以达到增加稳定性的目的。在实际过程中两条线路同时发生故障的概率很低,可以忽略,于是仅须要求节点的度数不小于2,我们即可满足稳定性的影响,定义为第i个节点的度数。则约束条件可表述为:λi≥2(i=1,2,3,L n)
于是模型一可以改进为: min z=wij•xij
xij=n-1 xij≤s-1?坌s?奂V,s≠?覫xij∈0,1 i,j∈Vλi≥2 (i=1,2,3,L n)λi=(i=1,2,3,L n)
2 推广模型建立
上述模型考虑了铺设路径长短对最终费用的影响以及稳定性对网络的影响,利用prim算法可以求出了图形的最小生成树,在保证连通性的情况下最小化了铺设成本;利用每一个节点的度来表征网络的稳定性,但是模型中仅仅对度定义了统一的下界,而没有上界,模型仍然不是十分的全面。于是我们希望建立一个全面的模型,综合考虑以上模型并对之进行进一步的改进。即我们继续引入流量和链路断开这两个因素,建立目标函数。
铺设成本目标函数不变:fp=wijgxij
接着考虑流量目标函数:我们知道,当一个节点的度越多,流过这个节点的最大流量也就越大。所以流量可以看作是图中节点的度数之和的增函数。而在节点度之和一定的情况下,各个节点度数的波动越大,度数小的节点就成为流量的约束。所以流量的大小是节点度数的方差的函数。令代表图M(deg)的均值,std(deg)代表方差。我们构造如下函数来表示一个图的流量:fl=
因此,使用线性加权的方法将两个因素综合起来,首先将两个函数归一化,然后定义偏好系数γ∈(0,1),γ越接近0表示决策者越倾向于费用因素,越接近1表示决策者越倾向于流量因素,所以最终的目标函数(满意度函数)就是:
f=std(wij•xij)+γstd
节点稳定性的约束:首先我们引入一个的故障矩阵DP,DPij表示在节点i和节点j之间存在连接线时,连接线出现故障的概率。我们仍然假定节点不会出现故障,所有的故障都是来自于链路。而每一个边相对于点来说是并联的,利用概率统计的知识,我们可以求得节点i能够正常工作的概率:
RPi=1-?蒹DPi
令RPmin为用户规定的平均最小工作概率。如果在整个网络中所有节点工作概率的算数平均值大于RPmin,则这个网络就是可接受的,否则就是不可接受的。由此,我们引入了另一个约束条件。RPij>RPmin。可靠性约束(度):凡是有节点度数不在此区间的方案都被认为是不可行解。为了防止蚂蚁在寻优的过程产生不可行解。定义[low,up]为度的约束区间。对于每一个节点deg(i),其度为我们定义一个函数:
s=0,若deg(i)∈(low,up)low-deg(i),若deg(i)∈(∞,low)deg(i)-up,若deg(i)∈(up,∞)
则我们可以定义罚函数为:fhs(i)= sij
预算成本的约束:我们在前面推导出了一个新的目标函数满意度函数,所以铺设成本不再是要优化的对象。而在实际的过程中,决策方所能够承担的最大铺设成本一定不大于预算。所以很自然的,我们应当定义一个最大预算Fmax。第一问中,我们已经求出了仅考虑铺设成本的情况下的最小铺设成本。根据心理学的知识,决策者对费用的容忍度通常都是与最少成本的比较过程中产生的,所以我们在此定义一个容忍百分比Ratio:
Ratio= ×100%
= ×100%
相应的最大容忍为Rbd
根据上面的分析,求解满足这样的子图的过程其实就是一个如下的组合优化的过程。
min z=wij•xij
st.xij=n-1 xij≤s-1?坌s?奂V,s≠?覫deg(i)∈(up,low),?坌i∈(0,N)Ratio=RbdRPij>RPminxij∈0,1 i,j∈V
根据以上的方程,我们可以得知:这个问题类似于图论中经典的背包问题(KP)。但不同于背包问题的是,除了资源的限制之外,这个组合优化的问题还有一个评价函数的约束。根据文献,如上的组合优化问题是一个典型的NP难问题,传统的精确算法法复杂度为O(2n),难于求解如此大规模的问题,所以我们可以利用蚁群算法来求得满意解。
3 实例研究
以下是某大学希望将多个不同建筑内的计算机终端连接起来,这些终端将通过地下电缆进行连接,已测知各建筑之间的需要连接的距离,现在要求完成以下两个方面的问题:自行设定决策标准,为决策者提供最佳连接方案;考虑某两个节点之间的连接与否对整个网络的影响,若有影响提出相应的解决方案。
各终端结点的距离矩阵如下:
根据模型,若不限定结点的度,利用prim算法,我们求得的最小距离为,可以求出度为1时的网络铺路规划示意图,如上。
显然,上述网络规划的很多节点度数为1,可见网络的稳定性很低,若某一结点出现故障,则会出现局部网络瘫痪。因此在满足最大容忍度Rbd 时,稳定性重要程度参数S∈[2,5]的情况下,利用蚁群算法得到如下示意图:
最小度>=2的连接方案
从图中可以直观的看到任意一个节点的度都大于等于2,满足对可靠度的要求,最终得到的总的距离为S=3985。
4 模型评价
如不考虑稳定性,只考虑费用问题,得到了最小的费用(即距离),对于只考虑成本的投资者,这是一个不错的结果,他完全可以按所求得的网络进行施工铺设。
当加入了度的约束,保障网络的稳定性,这一结果适合于资本相对丰裕,希望网络的稳定性能够得到提高的决策者,此时网络中不存在节点 “命悬一线”的情况。因此,考虑稳定性也是极有指导意义的,可以作为决策者的决策之道。
在模型求解过程中,使用了prim算法,可以得到该算法的时间复杂度为O(n2),与网中的边数无关,因此适用于求边稠密的网的最小生成树。 在此基础上,考虑稳定性,则需包含最小生成树的复杂度,接着它再进行一个一维的搜索,所以它的时间复杂度为O(n3),仍然在可计算的范围类。
在模型推广中又加入了流通性的约束,如果再在原算法的基础上改进的话,复杂度将变得非常的大。因此需要“另辟蹊径”,于是采用了蚁群算法,由算法的流程图得复杂度为O(mn2)(m为边数,n为点数),即约等于O(n4),相比于指数级复杂度要好很多。
参考文献
1 姜启源.数学建模[M].高等教育出版社,2003.8
2 甘应爱.运筹学[M].北京:清华大学出版社,2004
3 严蔚敏等.数据结构[M].北京:清华大学出版社,2004.7
4 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2002
5 王笑蓉.蚁群优化的理论模型及在生产调度中的应用研究[D].杭州:浙江大学,2003
5 李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004.9
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文
【关键词】 prim算法 网络铺设 蚁群算法 优化设计
Study Ant colony algorithm based on network rollout planning
【Abstract】 Laying in communications network, to establish the distance between each node and nodes in the mat.rix, using graph theory methods, into a fully connected graph, considering only the shortest distance in the circumstances, the use of prim algorithm has been cost The minimum spanning tree and shortest path. In order to more clearly and comprehensively the performance of laying out the various factors that affect the network has established a link off covering the probability of links a combination of numbers and network traffic optimization model, using ant colony algorithm in a different degree requirements, different link-off probability, the largest circulation of these three constraints of the connections and the corresponding distance laying.
【Key words】 Prim algorithm Network rollout Ant colony algorithm Optimization design
通信网络铺设一直是网络发展规划研究领域的热点,很多学者为此展开了广泛而深入的研究,并取得了很多具有参考价值的结果。为了将分散终端连接起来,一般通过地下电缆进行连接,当已测知各结点之间的需要连接的距离,考虑到费用与效率问题,则需为网络规划者提供最佳连接方案。
针对通信网络铺设问题,首先要考虑的是设计一个网络的标准:确定网络的拓扑结构;确定网络中的信息的路径方向;网络中流量的分配控制;网络在使用过程中是否稳定可靠。因此网络优化也应针对上述四个方面,即拓扑结构优化、路径优化、流量分配优化和可靠性优化。通信网网络优化的最终目标是在尽量满足特定要求的情况下,使整个网络的总投资最小。对于一个通信网,不同的网络结构,其最优的组织方式可能不同,对于不同的组织方式,其最优的流量分配方案可能不同,因此以上四个优化过程是紧密相连的整体。
1 通信网络规划模型
在通信网络规划上,一般具备以下假设:网络费用仅与铺设距离相关,可假设成简单的正比关系;各个节点之间的重要性是对等的,不存在级次差别;一个节点和其它的节点的连接是等可能的,且一个节点可以连接的节点是不受限制的;节点的度不相同将导致的各个节点间的流量存在差异;网路的稳定性仅与节点及节点所连的线路的多少有关。
根据前面的假设,铺设成本仅与铺设长度相关。这样问题就转化成为了求解一个保证连通性的最短铺设方案。根据节点及节点之间距离的矩阵,首先可以构造一个全联通的图,每一个连接点是图中的一个节点,矩阵中第i行第j列的元素值大小就是边(i,j)的权重。根据前面的分析,问题就抽象成为了求解这个完全图的最小生成树。对于赋权连通图G=(V,E,W),式中W=[wij]n•n为图G的有权矩阵,其中wij>0且wij=wji,wii=∞,D(i,j)=wij表示顶点i与顶点j之间的距离[(i,j)∈V]。引入一个0、1变量xij,0表示该路径未被选入,1表示该路径被选入,那么最小化费用这一目标函数可以表示为:min z=wij•xij
根据图论知道,最终生成的为一棵树,由树的性质,我们知道树的边的总和应等于总节点数减去一:wij=n-1
最小生成树是一个无环的图,用V表示所有节点,S表示V的子集,那么在任一子集中必须要满足不存在环的条件,数学表示为: xij≤s-1?坌s?奂V,s≠?覫
现实中若仅考虑费用的问题常常无法满足要求,对于度为一的节点,若与它连接的链路被断开,那么它们就处于“瘫痪”的状态,没有与外界连接,因此这样的节点的稳定性是最差的。所以要人为的增加度的约束,以达到增加稳定性的目的。在实际过程中两条线路同时发生故障的概率很低,可以忽略,于是仅须要求节点的度数不小于2,我们即可满足稳定性的影响,定义为第i个节点的度数。则约束条件可表述为:λi≥2(i=1,2,3,L n)
于是模型一可以改进为: min z=wij•xij
xij=n-1 xij≤s-1?坌s?奂V,s≠?覫xij∈0,1 i,j∈Vλi≥2 (i=1,2,3,L n)λi=(i=1,2,3,L n)
2 推广模型建立
上述模型考虑了铺设路径长短对最终费用的影响以及稳定性对网络的影响,利用prim算法可以求出了图形的最小生成树,在保证连通性的情况下最小化了铺设成本;利用每一个节点的度来表征网络的稳定性,但是模型中仅仅对度定义了统一的下界,而没有上界,模型仍然不是十分的全面。于是我们希望建立一个全面的模型,综合考虑以上模型并对之进行进一步的改进。即我们继续引入流量和链路断开这两个因素,建立目标函数。
铺设成本目标函数不变:fp=wijgxij
接着考虑流量目标函数:我们知道,当一个节点的度越多,流过这个节点的最大流量也就越大。所以流量可以看作是图中节点的度数之和的增函数。而在节点度之和一定的情况下,各个节点度数的波动越大,度数小的节点就成为流量的约束。所以流量的大小是节点度数的方差的函数。令代表图M(deg)的均值,std(deg)代表方差。我们构造如下函数来表示一个图的流量:fl=
因此,使用线性加权的方法将两个因素综合起来,首先将两个函数归一化,然后定义偏好系数γ∈(0,1),γ越接近0表示决策者越倾向于费用因素,越接近1表示决策者越倾向于流量因素,所以最终的目标函数(满意度函数)就是:
f=std(wij•xij)+γstd
节点稳定性的约束:首先我们引入一个的故障矩阵DP,DPij表示在节点i和节点j之间存在连接线时,连接线出现故障的概率。我们仍然假定节点不会出现故障,所有的故障都是来自于链路。而每一个边相对于点来说是并联的,利用概率统计的知识,我们可以求得节点i能够正常工作的概率:
RPi=1-?蒹DPi
令RPmin为用户规定的平均最小工作概率。如果在整个网络中所有节点工作概率的算数平均值大于RPmin,则这个网络就是可接受的,否则就是不可接受的。由此,我们引入了另一个约束条件。RPij>RPmin。可靠性约束(度):凡是有节点度数不在此区间的方案都被认为是不可行解。为了防止蚂蚁在寻优的过程产生不可行解。定义[low,up]为度的约束区间。对于每一个节点deg(i),其度为我们定义一个函数:
s=0,若deg(i)∈(low,up)low-deg(i),若deg(i)∈(∞,low)deg(i)-up,若deg(i)∈(up,∞)
则我们可以定义罚函数为:fhs(i)= sij
预算成本的约束:我们在前面推导出了一个新的目标函数满意度函数,所以铺设成本不再是要优化的对象。而在实际的过程中,决策方所能够承担的最大铺设成本一定不大于预算。所以很自然的,我们应当定义一个最大预算Fmax。第一问中,我们已经求出了仅考虑铺设成本的情况下的最小铺设成本。根据心理学的知识,决策者对费用的容忍度通常都是与最少成本的比较过程中产生的,所以我们在此定义一个容忍百分比Ratio:
Ratio= ×100%
= ×100%
相应的最大容忍为Rbd
根据上面的分析,求解满足这样的子图的过程其实就是一个如下的组合优化的过程。
min z=wij•xij
st.xij=n-1 xij≤s-1?坌s?奂V,s≠?覫deg(i)∈(up,low),?坌i∈(0,N)Ratio=RbdRPij>RPminxij∈0,1 i,j∈V
根据以上的方程,我们可以得知:这个问题类似于图论中经典的背包问题(KP)。但不同于背包问题的是,除了资源的限制之外,这个组合优化的问题还有一个评价函数的约束。根据文献,如上的组合优化问题是一个典型的NP难问题,传统的精确算法法复杂度为O(2n),难于求解如此大规模的问题,所以我们可以利用蚁群算法来求得满意解。
3 实例研究
以下是某大学希望将多个不同建筑内的计算机终端连接起来,这些终端将通过地下电缆进行连接,已测知各建筑之间的需要连接的距离,现在要求完成以下两个方面的问题:自行设定决策标准,为决策者提供最佳连接方案;考虑某两个节点之间的连接与否对整个网络的影响,若有影响提出相应的解决方案。
各终端结点的距离矩阵如下:
根据模型,若不限定结点的度,利用prim算法,我们求得的最小距离为,可以求出度为1时的网络铺路规划示意图,如上。
显然,上述网络规划的很多节点度数为1,可见网络的稳定性很低,若某一结点出现故障,则会出现局部网络瘫痪。因此在满足最大容忍度Rbd 时,稳定性重要程度参数S∈[2,5]的情况下,利用蚁群算法得到如下示意图:
最小度>=2的连接方案
从图中可以直观的看到任意一个节点的度都大于等于2,满足对可靠度的要求,最终得到的总的距离为S=3985。
4 模型评价
如不考虑稳定性,只考虑费用问题,得到了最小的费用(即距离),对于只考虑成本的投资者,这是一个不错的结果,他完全可以按所求得的网络进行施工铺设。
当加入了度的约束,保障网络的稳定性,这一结果适合于资本相对丰裕,希望网络的稳定性能够得到提高的决策者,此时网络中不存在节点 “命悬一线”的情况。因此,考虑稳定性也是极有指导意义的,可以作为决策者的决策之道。
在模型求解过程中,使用了prim算法,可以得到该算法的时间复杂度为O(n2),与网中的边数无关,因此适用于求边稠密的网的最小生成树。 在此基础上,考虑稳定性,则需包含最小生成树的复杂度,接着它再进行一个一维的搜索,所以它的时间复杂度为O(n3),仍然在可计算的范围类。
在模型推广中又加入了流通性的约束,如果再在原算法的基础上改进的话,复杂度将变得非常的大。因此需要“另辟蹊径”,于是采用了蚁群算法,由算法的流程图得复杂度为O(mn2)(m为边数,n为点数),即约等于O(n4),相比于指数级复杂度要好很多。
参考文献
1 姜启源.数学建模[M].高等教育出版社,2003.8
2 甘应爱.运筹学[M].北京:清华大学出版社,2004
3 严蔚敏等.数据结构[M].北京:清华大学出版社,2004.7
4 段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2002
5 王笑蓉.蚁群优化的理论模型及在生产调度中的应用研究[D].杭州:浙江大学,2003
5 李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工业大学出版社,2004.9
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文