关键字 |
| 随机流网络;能力;系统的可靠性;遗传算法;meta-heuristics。 |
|
 |
假设 |
| 以下是其他部分的假设 |
| 1。所有弧和节点有几个可能的能力和可能会失败 |
| 2。两种类型的商品运输/ s t传播。 |
| 3所示。当前容量ξ值从{0,1,2,…,Mi},我= 1,2,…,n + q。 |
| 4所示。不同的组件是相互统计独立的能力。 |
| 5。每个商品都必须保护Σ流动米j = 1fjk= dkk = 1, 2 |
介绍 |
| 网络的可靠性的概率是源节点和终端节点之间的连通性t。从质量管理和决策makingpoint来看,就必须不仅要定义每个节点的负荷能力和弧的网络也制定一些措施来评估系统的性能[1],[2]。许多现实生活系统如计算机系统、通信系统、交通系统、城市交通系统、电力传输系统、物流供应链和互联网等都属于流网络,大多与性能。流网络中每个输电线路由几种物理s和t之间的界限,和每一个物理行有几个成功的国家也可能会失败;因此,每个分支都有几个值的能力。这样的网络被称为stochastic-flow网络。随机流网络性能的条件下,每个弧流量都是决定性的,不仅是与网络可靠性也是最大流量的测量单位时间内来源之间terminalt [3]。 |
| 在二进制状态流网络,每个分支的能力(最大流量通过分支单位时间)有两个层次:0,一个正整数。对于完美的节点没有预算限制,[4]计算系统的可靠性,网络的最大流量的概率不小于需求,议员。分支机构的议员是一个有序序列s totthat没有循环。请注意,议员与所谓的最小路径不同。后者是与最小成本路径[5]。研究人员在[6],[7]扩展随机流网络系统可靠性的问题。stochastic-flow网络也被称为多态多态弧组成的网络,因为它是。s t之间的最高流量并不是一个固定数量在这些网络。几个作者(地位)提出算法来生成所有最小路径(较低的边界点)需求d为了评估系统的可靠性。d是最小的下边界点系统状态会议需求约束。 The flow networks can allow single as well as multicommodity (multiple types of commodity) to be transmitted through it. Such a network is called a multicommodity capacitated-flow network [5]. Modern systems like a broadband computer network(audio files, video files, multimedia, etc.) and urban traffic controletc. are the examples of multicommodity flow systems. In all such systems the arc capacity / bandwidth is shared simultaneously by multicommodity. The pioneer work in this field is attributed to authors [16], [17], discussed the multicommodity minimum cost flow problem to minimize the total cost of multicommodity by assuming the capacity of each arc is a constant(i.e., the arc is deterministic). Besides, some authors [18], [19] have solved the multicommodity maximal flow problem to find the maximal total flow assuming the arc is deterministic. However, the maximal total flow is not an appropriate performance index especially in case different type of commodity consumes the arc capacity differently [1]. For instance, let’s consider a case of a telecommunication network through which different type of information, like data, audio, video and pictures are transmitted simultaneously from s to t. For clear understanding let’s consider that two commodities, one consisting of 150 data files of 100KB each (commodity 1) and other having 100 video files of 200KB each (commodity 2) have to be routed. Further it is assumed that there exists no direct path between s to t. The each route from s to t must pass through some intermediate nodes. All or any of the arc connecting source to terminal can fail, may be under maintenance or be occupied by some other transportation. Due to multiplicity of routes between source and terminal, the capacity of each arc is multistate. If at least two data packets of each commodity must be transported simultaneously (i.e. d1= 2和d2= 2)数据包的形式通过网络1000 kb。很明显,商品消费的每个分支能力不同。它清楚地表明,弧流网络的不同商品的消费能力。进一步有预算限制在所有这些运输必须完成。运输的成本必然会增加数量增加的容器。因此,流网络的目标是最大化和最小化成本。 |
| 目前的工作提出了一个连续整数基于遗传算法(GA)的模型来评估预算约束下multicommodity随机流网络的可靠性。该模型从作者[3]的工作动机是基于两个主要特点1)每个节点或弧有几个可能的能力和可能失败;2)能力体重随弧、节点和类型的商品。实现该算法流网络模型为宽带通信网络允许混合模式的信息(例如音频、视频和数据等)流经它。为了方便两个商品多态流网络问题(TCMFN)被认为是出于演示目的即网络允许流两个大宗商品(音频文件作为商品1和视频文件作为商品2)并发共享网络的带宽(能力)。 |
问题公式化 |
| 弧和节点的路径是一个有序序列连接sto t。适当的路径子集不再是路径被称为最小的路径。系统可靠性的概率是给定的需求(d1d2)预算中的传播接通源目的地。因此,电流容量的必要条件是服从向量Xto (d1d2(即,B)最小流路径。(d1d2,B)议员)are1) Xmust属于一套可行的流 |
 |
 |
 |
| 生成所有(d1d2,B) - MP |
| 生成所有(d1d2,B) -议员设定一个新的连续遗传算法。通用航空的发展可以称为一个概率方法的适应基于自然进化原理。自然观察适者的生存原则,软弱和不适宜的物种在其环境正面临着灭绝的自然选择。强烈的有更大的机会将他们的基因传递给后代通过繁殖[20],[21]。遗传算法遵循人口进行连续变化的过程通过杂交育种,基因突变和自然选择。生成的所有(d1d2,B) -议员(性能指标)和评估Rd1d2B议员有效的遗传算法的目标函数是由考虑制定X是一个d1d2,B) - MP意味着存在一个流分配(F1、F2)满足需求约束等; |
 (9) |
 |
| b .提出遗传算法 |
| 评估所有d1d2B−议员提出了一个新的连续GA在这一节中。任何GA的成功取决于它的参数值,如;染色体形成(即编码技术)、人口规模、交叉率、变异率等。这些参数的值可以适当选择平衡解的质量和计算工作。固定数量的解决方案的一个初始种群是随机生成的第一代人口的遗传算法。然后交叉和变异算子进行人口成员产生后代。一个有效的GA取决于互补的交叉和变异算子。交叉算子决定收敛速度,而变异算子可以防止算法过早收敛。每个成员的人口是评估按照其目标函数,它用作基础选择父母解决方案和扑杀下解决不同的进化的人口[25]。在遗传算法的情况下,如果变量是连续的值,那么它需要许多位来表示它。此外,如果变量的数量很大,染色体的大小也大。 When the variables are naturally quantized, the binary GA fits nicely and the precision is limited to the binary representation of variables. However, when the variables are continuous, it is more logical to represent them by floating-point numbers. In addition, using floating point numbers allows chromosome representation to the machine precision and requires less storage than the binary GA. The continuous GA’s also have better inherent temporal efficiency because the chromosomes decoding prior to the evaluation of the objective function is not needed at all. |
| 一个流网络的可靠性评估问题在预算约束下当每个节点或弧有几个可能的能力和可能失败,体重随弧能力,节点和类型的商品通过网络称为多目标优化(MOO)随机流网络。MOO通常没有单一的解决方案中最优对所有目标和结果的最优解集被称为帕累托最优解决方案。没有额外的信息,所有这些解决方案都是令人满意的。MOO的目标是找到尽可能多的这些解决方案。如果资源配置不能提高一个成本不增加另一个成本,然后是帕累托最优的解决方案。[23]作者首先介绍了多目标进化算法称为vector-evaluated GA和织女星。后来作者[24]建议使用nondominated排序过程加上一个小生境策略叫做分享。共享考虑到个人在同一细分市场必须共享可用的资源。以后的工作[25]表明,多目标遗传算法(分公司)可以通过寻找实现所有nondominated染色体的人口,给他们一个排名。这些染色体从人口中删除。 Next all the nondominated chromosomes of this smaller population are found and assigned a rank of two. This process continues until all the chromosomes are assigned a rank. |
| c . GA的步骤 |
| 一个新的连续遗传搜索算法使用基于非惯用的染色体做空的方法来优化随机流网络并评估其可靠性提出了以下部分。 |
| 1)染色体表示:染色体表示是任何遗传算法的一个至关重要的部分。有几种方法representingchromosome对于任何给定的问题。一般遗传算法适用于二进制编码,但对于许多工业问题二进制字符串不是一个自然的编码。因此各种non-string技术如:实数编码约束优化问题和整数编码被用来建立染色体组合问题。的非线性整数规划问题的类型(3)以上,连续的整数编码作为一个向量表示更有效率 |
| 2)初始种群的生成:固定数量的染色体是随机生成的一个初始种群。染色体,在任何一个基因位点是随机生成的整数之间的上下极限定义为每个子系统。人口规模2000人被为每个测试的问题。 |
| 3)评估染色体的适应性:染色体的适应度计算通过使用(9)的目标函数。所有的染色体和约束满足流量需求按降序排列的健身和升序运输和相关成本的1级能力向量。保持一份这些染色体池(d1d2,B) - MP的解决方案。其他所有的解决方案都排名的升序违反流约束和成本从2。获得的人口因此被认为是第一代人口。 |
| 4)遗传算子:两个遗传算子交叉和变异是任何GA的支柱。使用这两个操作符创建新的弹簧的基因在每一代 |
| •交叉算子:它提供了一个彻底的搜索区域的样本空间产生良好的解决方案。排名基于加权随机配对技术是用于执行交叉/交配操作。概率交配池中分配给染色体排列成反比。这种方法不依赖于问题的本质,并确定交叉概率的等级n的染色体。等级概率句决定 |
 (14) |
| 流行保持代表总数的染色体为下一代保持给定的人口在每个迭代中。如果排名n人口的秩和流行吗保持= 5是染色体的数目保持那么Σ累积概率分配n排名流行= 1p流行是显示在表1。 |
| 列4中列出的累积概率选择染色体用于交配的目的。一个随机数πgeneratedbetween限制0≤p≤1 0。从列表的顶部开始,第一个染色体的累积概率大于或等于的随机数p选择交配池。例如,如果随机数是p = 0.437, 0.333 < p≤0.60,所以chromosome2被选中。这个过程重复创建完成交配池。两点交叉方法用于配偶父母和削减positionsare生成随机的时间间隔(1,n)。 |
| •突变:随机突变改变部分的一定比例的染色体。突变是另一种方式去探索详尽的搜索空间。新基因的突变ratepmis ratethe率引入人口受审。如果太低,那么一些基因会有用从未被尝试了,但是如果它太高了,那么将会有很多随机扰动和弹簧将开始失去他们的相似之处将失去父母和算法能够从历史中学习。目前,采购经理人指数为0.20。随机数π为每个基因生成区间内间隔0≤p≤1。如果p < pmthen基因随机翻转到另一个从相应的一系列的选择。 |
| 5)选择:每一代后进行遗传操作产生好的或坏的解决方案。所有的解决方案(初始种群、儿童和弹簧)按降序排列选择健康和人口的下一代。在步骤(3)(5)迭代直到达到停止条件或最大数量的迭代是感动。 |
插图 |
| 为了说明提出的,所使用的基准问题[1]。图1显示了一个桥接网络组成的4节点和6弧和multicommodity运输通过流网络从t。每个从年代t必须通过节点a7和a8节点。Considertwo商品,分别由150 100 kb的数据文件(商品1)和其他有75视频文件的200 kb(商品2)已经考虑路由从s t。s t的每个路线必须通过一些中间节点a7和a8。弧源连接到终端的所有或任何可以失败,可能在维护或被其他交通工具。由于多样性的来源和终端之间的路线,每个弧的容量是多态的。如果至少有两个数据包的每个商品都必须同时运输(即d1= 2和d2= 2)包1000 kb的形式通过网络。很明显,商品1消耗15包(wj1 = 1 1)和商品分别2消耗30包(wj1 = 1 1)。进一步的运输必须完成在一个预算constraintC b (X)≤。运输的成本必然会增加数量增加的容器。因此,流网络的目标是最大化和最小化成本。例子的数据流的网络图1表2中给出的目标发现概率或多或等于系统容量需求预算约束下(2,2)B = 4400。评价过程中描述的问题是以下三个部分: |
 |
 |
 |
 |
结论 |
| 该方法是一个基于GA methodto评估预算限制下随机流网络的可靠性。它流的评估所有能力向量网络满足给定的流和预算限制使用一种新的基于连续GA算法。实现的算法可以很容易地通过建立约束(流和预算等)不平等的算法没有复杂的数学归纳的知识制定。因此,它可以很容易地确定实现大流量网络的性能指标有效地找到所有的现代交通网络的效用。 |
表乍一看 |
|
|
数据乍一看 |
 |
| 图1 |
|
引用 |
- y K.Lin”,计算机网络的可靠性与弧容量重量不同,节点和类型的商品”,可靠性工程和系统安全,卷2(5),页1 - 7,2006。
- y . k .林“流网络的可靠性受到预算限制”,IEEE反式。的完整性。,Vol. (56), pp. 10-16, 2007.
- y . k .林“多态系统可靠性评估供应链网络与故障节点使用最少的路径”,IEEE Trans.Reliab。卷,58(1)34-40,2009页。
- k . k . Aggarwal y . c . Chopra, j·s·Bajwa,“容量考虑通信系统的可靠性分析,“IEEE Trans.Rel。31卷,第180 - 177页,1982年。
- y . k .林”的可靠性k单独的最小路径在时间和预算限制”,IEEE Tran。的完整性。,Vol. 59(1), 183-190,2010.
- w·j·Rueger与产能有限,”网络可靠性分析和失败在树枝和节点,“IEEE反式。Rel。,35卷,pp.523 - 528, 1986。
- d·w·李和b . j .百胜”,确定最小上层路径平面流网络的可靠性分析,“的完整性。Eng。系统。Saf。,卷。39岁,1 - 10,1993页。
- j .雪“多态系统分析”,IEEE反式的完整性。34卷,页329 - 1985。
- w·c·叶”,修改后的分层网络的算法来搜索所有d-minpaths limited-flow非循环网络”,IEEE反式。的完整性。,Vol.47, pp.436–42, 1988.
- j·s·林,c . c .简和j .元”的可靠性评估capacitatedflownetwork最小pathsets”,网络,3卷,页。131 - 138年,1995年。
- y . k .林”,一个简单的可靠性评估算法astochastic-flow网络节点故障”,计算机和操作研究,卷。28日(13),pp.1277 - 1285, 2001。
- w·c·叶“一个简单的方法来搜索所有d-MCs limitedflownetwork”,完整性。注意事项。系统安全、卷。71 (1)pp.15-19, 2001年。
- y . k .林,“capacitatedflownetwork multicommodity可靠性的研究”,与计算机。数学。与应用程序,42 (1 - 2),pp.255 - 264, 2001。
- y . k .林”,使用最少的削减astochastic-flow网络评估系统可靠性与故障节点和弧”,完整性。注意事项。系统安全、卷。75 (1)pp.41-46, 2002年。
- 后来叶”,一个简单的算法来搜索所有d-MPs withunreliable节点”的完整性。注意事项。系统安全、卷。73(1)页。49-54,2003年。
- j . e . Cremeans r . a . Smith, g . R.Tyndall“最佳multicommodity与资源分配网络流”,海军Res物流问,卷。17日,第279 - 269页,1970年
- j·r·埃文斯”组合之间的等价类multicommodity流问题和生产配送运输问题”,数学编程,Vol.10, 401 - 404年,1976页。
- l·r·福特·d·r·Fulkerson“最大的建议计算multicommodity网络流”,管理科学。pp.822 - 844卷。20日,1974年。
- 答:答:阿萨德“Multicommodity网络涌入有如调查”,网络,8卷,页37 - 91,1978。
- ·库马尔·d·k·查图尔维迪和g . l . Pahuja”约束的复杂系统可靠性冗余优化使用GeneticAlgorithm”,麻省理工学院电气和仪表工程的Int。J,1卷,1号,页41-48 2011。
- p•库马尔“限制流网络的可靠性冗余优化使用遗传算法”,Int。j .放置加热器>,电。本月,工程卷。2(5),1885 - 92年,2013页。
- d .屁股,a·史密斯、“可靠性优化串并联系统利用遗传算法”,IEEE反式。的完整性。,Vol. 45(2), pp.254–60, 1996.
- j·d·谢弗,et al,“控制参数影响的研究网络性能函数优化的遗传算法”,法学博士谢弗(主编),Proc。第三Int.Conf。在遗传算法。洛斯拉图斯,CA:摩根考夫曼,51-60页。1989 . .
- d·e·戈德堡和j·理查森,“多峰函数优化遗传算法与分享”,在j。j Grefenstette(主编),遗传算法及其应用:Proc。2ndInt。Conf.遗传算法,山谷,新泽西:劳伦斯•Erlbaum 41-49, 1987页。
- c . m . Foneseca弗莱明和p . j .“遗传算法多目标优化:配方,讨论,和泛化”,Proc。第五Int。Conf.遗传算法。旧金山,CA:摩根考夫曼,416 - 423年,1993页。
|
菜单
(9)
(14)
