基于遗传算法的多态计算网格成本带宽优化

沙特国王大学学报一种基于遗传算法的开销和带宽约束Dasa，C.R.Tripathya，P.K.Tripathyb，M.R.卡巴特aa计算机科学与工程系，Veer Surendra Sai University of Technology，Burla，印度b印度布巴内斯瓦尔硅技术学院计算机科学与工程系阿提奇莱因福奥文章历史记录：接收日期：2018年2018年9月15日修订2018年10月9日接受2018年10月11日在线提供保留字：多态计算网格可靠性成本带宽遗传算法A B S T R A C T计算网格需要具有成本效益和高度可靠性。它必须能够传输最大量的数据，以实现端到端交付。计算网格的许多研究工作都是在二元状态下进行的。虽然一些研究表明网格是以多种连接和操作状态运行的，但它们没有提到上述约束。由于存在多态操作，因此可靠性取决于负载、带宽和成本。本文提出了一种基于遗传算法的计算网格可靠性优化方法，在成本和带宽约束下，满足期望的可靠性。通过实例说明了该方法的有效性，并给出了该方法在网格网络上的实现.该方案的高效编码、交叉、变异和选择操作保证了算法快速收敛到最优解。通过比较，发现该方法比现有方法更有效©2018作者（S）。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍网格计算是一种分布式系统范例，其中多个资源互连并协调以实现共同的目标（Cassanova，2002; Foster等人， 2002年）。这些计算网格应用于不同的科学和技术领域，用于解决各种问题（Xhafa和Abraham，2010）。一个网格可能有多个状态，这取决于负载、带宽、可靠性和成本这样的计算网格在这里被称为多态计算网格。多态计算网格在文献中没有得到在现实生活中的计算网格网络中，边缘被认为是多状态的，这是因为某些故障（保护）、维护和其他此类条件的偶然性（Dash等人， 2012年）。然而，实际上，这些链路的可靠性随着时间的推移而逐渐降低，这取决于各种因素，如负载、带宽、成本等。*通讯作者。电 子 邮 件 地 址 ： debashreetdas12@gmail.com （ D.Das ） ， gmail.com（P.K.Tripathy）。沙特国王大学负责同行审查在计算网格上进行的许多早期研究工作都以二元操作状态结束。因此，必须在适当考虑负载、带宽和成本等约束的情况解决这三个因素的短板不仅可以提高可靠性的有效性，还可以提高系统的连通性、容错性和成本效益（Sathya和Babu，2010年）。这种优化布局随着网格连接数的增加而变得相当复杂因此，优化布局需要解决这种复杂性和可靠性。根据Kuo et al. （2001），“系统可靠性是衡量一个系统满足其设计目标的程度，通常用子系统或部件的可靠性来表示”。可靠性取决于子系统和连接到给定系统的元件。但在实际应用中，由于各种原因，各个部件的可靠性可能会发生波动。对于一种技术来说，生产具有完全相同可靠性的不同组件此外，人为因素、不适当的储存设施和其他环境因素可能会影响单个组件的可靠性结果表明，可靠性优化问题的目标函数为区间值，并对区间值进行了优化.这些类型的优化问题与区间目标，可以解决一个众所周知的，强大的，启发式搜索和优化方法，即。遗传算法（GA）方法。它https://doi.org/10.1016/j.jksuci.2018.10.0061319-1578/©2018作者。由爱思唯尔公司出版代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier可在ScienceDirect上获得目录列表沙特国王大学学报杂志首页：www.sciencedirect.com444D. Das等人/Journal of King Saud University在实数/二进制编码的解决方案集上迭代执行，称为人口。在每次迭代中，称为生成，三个基本操作，即选择/生产，交叉和变异进行。在一些预定义的约束（如成本、可靠性和带宽）下的计算多状态网格的布局优化是高度期望的（Tripathy等人， 2015年）。这里的计算网格可以看作是一个图G（V，E），其中V表示节点集，E表示连接节点的链接集合E中的每个链路本质上是多状态的，这取决于负载和带宽（Lin，2010）。因此，这个优化问题变成了一个拓扑优化问题，其中选择合适的链路决定了网络的可靠性和成本，这使得问题的NP-难的性质。启发式方法适用于搜索空间很大的情况。提出的基于遗传算法的方法旨在通过从网络中选择合适的链路来优化多态计算网格，使得在给定的成本、带宽和负载约束下，整个网络的可靠性较高在本文中，我们提出了一种基于遗传算法的方法，通过选择适当的链接与所需的可靠性下的成本和带宽的限制，找到最佳布局的多态计算网格。论文第二部分拟议办法的细节以及在第3节中给出了算法和图示。第四节介绍了结果和讨论。结论性意见载于本文件第52. 相关工作在过去的研究工作中，人们对网格系统的可靠性进行了大量Wang和Watada（2009）提出了一些多目标模糊随机分配模型，以最大化系统的可靠性以及最小化成本。 在Gupta et al. （2009），作者解决了冗余分配问题。其目的是最大限度地提高系统的可靠性考虑资源的约束。Li等人（2010）通过使用称为通用生成函数或UGF的特殊函数来估计系统的可靠性他们还使用遗传算法作为优化方法来设计系统结构。Li等人（2008）提出了两种优化模型，其目标是最大化系统的可靠性以及最小化总成本。然而，（Dai和Wang，2006;Feng和Buyya，2016; Kaushik和Vidyarthi，2018）建议GA也可以Carrestrial et al.（2007）对这些不同版本的遗传算法及其在网格调度中的应用进行了深入研究。此外，（Higashino et al.，2016年，Singh和Singh，2016年）研究了一种将GA与模拟退火和禁忌搜索相结合的调度方法。Nesmachnow和Iturriaga（2013）提出了一种并行GA实现机制，可以改善调度结果。大多数涉及可靠性优化的实际设计或决策问题需要同时优化多个目标函数。 Sakawa（1978）报道了这一领域的早期研究。为了同时使系统可靠性最大化和可靠性分配的系统成本最小化，他使用代理价值权衡方法制定并解决了一个多目标问题。Inagaki等人（1978）通过实施交互优化方法最大化系统可靠性并最小化系统成本和重量来解决不同的对这一领域的研究趋势进行综述关于这一领域，可以参考Dhingra（1992年）、Rao和Dhingra（1992年 ） 、 Srinivas 和 Kalyanmoy （ 1994 年 ） 、 Ravi 等 人 的 著 作 。（2000），Huang et al. （ 2005），Coit and Konak（2006）andothers.近年来，Taboada和Coit（2007）提出了一种基于多目标进化算法和数据聚类相结合的方法。Ramirez-Marquez和Coit（2007）提出了一种用于改善多态系统可靠性的多态组件临界分析。Li等人（2009）提出了一种用于多目标决策的两阶段方法，并将其应用于系统可靠性优化。Ramirez-Marquez和Rocco（2010）发展了一种新的多目标问题中多态双终端可靠性分配的进化优化技术。一些研究人员已经解决了单目标的可靠性优化问题（Agarwal和Gupta，2005; Coit和Smith，1996;Ha Kuo，（2006）;Hikita等人（1992）; Kim和Yum（1993）; Kuo和 Prasad （ 2000 ） ; Misra 和 Sharma （ 1991 ） ; Nakagawa 和Nakashima（1977））。在单目标优化中，人们试图获得最佳设计或决策，其通常是全局最小值或全局最大值，这取决于优化问题是最小化还是最大化类型。另一方面，对于多个目标，可能不存在一个相对于所有目标最好的解决方案（全局最小值或最大值）。由于每个部件的可靠度都是区间值，因此系统的可靠度也是区间值。作者用遗传算法解决了区间目标的多目标这里考虑的目标是系统可靠性的最大化和系统成本的另外，我们还考虑了成本系数为区间值.为此目的，几个问题具有区间值目标的多目标可靠性优化问题已制定和解决。然而，现有的方法存在以下缺点。由于目标函数（系统可靠性，系统成本）是区间值，所以所得到的最佳解也是区间值。在这种情况下，有一个不确定性，这是什么，但间隔的宽度有几种方法可以提高系统的可靠性。其中的一些是（i）增加系统的每个组件的可靠性（ii）对不太可靠的组件使用并行冗余（iii）使用备用冗余。结果，系统成本、体积和重量可能增加。因此，为了在系统可靠性、系统成本、体积和重量的背景下优化系统，相应的问题被表述为多目标优化问题。在这类问题中，系统可靠性最大化，而其他措施，如系统成本，体积和重量最小化。Gupta et al.（2009）和Bhunia et al.（2010）将其应用于解决约束冗余分配问题。Sahoo等人（2012）只考虑了系统可靠性的最大化和系统成本的最小化。为了解决优化问题，他们使用了基于GA的Big-M惩罚方法。在那里，不计算不可行解的适应度函数的值。相反，M的值被认为是拟合函数的值在他们的著作中，没有关于M的值的指示然而，对于不可行的解决方案，M的值可以根据适应度函数值来取。对于M，可以考虑小值（在最大化问题的情况下）或大值（在最小化问题的情况下）来解决约束优化问题。在文献中，作者使用了确定性的方法或启发式方法来解决优化问题。然而，现有的方法受到许多限制。例如，这些方法适用于小尺寸D. Das等人/Journal of King Saud University445图1.一、（a）6 N和15 L的全连接MCG（b）6 N和9 L的MCG仅具有12个节点的网格（Jan等人， 1993）和20个节点（Dengiz等人， 1997年）。本文研究了多目标规划的布局优化问题，3.1. 符号由于设计因素，如可靠性，成本和带宽。 主要目标是设计一个Uij =利用函数th th具有成本和带宽约束的高可靠性计算网格。本文的下一部分是致力于发展的建议遗传算法为基础的模型，设计一个可靠的多态计算网格下的成本和带宽的限制。3. 该方法在本节中，我们提出了一种基于GA的技术，用于优化计算网格的布局，以便在某些假设的成本和带宽约束下利用最佳的本节以各种符号和注释为支持，随后是问题陈述和拟议方案的详细逐步描述。图二. 具有9个节点和11个链接的多态计算网格。表1图1的网格网络的编码矩阵。二、Rij = i之间链路的可靠性和jnode. Cij=连接第i个节点和第j个节点的链路的成本。L =网络D =图的所有节点的度的总和平均d=所有度N =节点Hd =节点的最高度数Maxd =最大度数Mind =最小度数DS =每个节点的计算度G =图AMd =计算的度数的平均值Pr1 =父1Pr2 =母体2Ch1 =儿童1Ch2 =儿童2PS =人口规模R =投入可靠性C =投入成本Ropt =优化的可靠性3.2. 假设在本文中，我们做了以下假设：节点是完全可靠的。链路有两种状态：活动或失败。一条链路的故障不取决于其他链路的故障3.3. 问题陈述问题公式化在这一小节中完成。分析了多态计算系统各链路的成本、可靠性和带宽节点编号123456789101011000021010100003010011000410001010051111011116001010001700011001080000101019000011010446D. Das等人/Journal of King Saud UniversityX¼X.Σ¼（一）（b）第（1）款图三. (a)Pr 1和Pr 2的交叉操作;（b）交叉操作后的子网格Ch 1和Ch 2。解决了大部分的最大化问题。对于该算法的应用，原点必须是可行点。只有当所有约束条件都较少且右侧为正常数时，此指定条件才为真目标函数：MaxRij：xijCijN1/1Njli1Uij见图4。 突变前的网络（有6个节点和6个链接）。假设网格是已知的。问题是要找到一个最佳的网络布局，使最大的可靠性，最小的xijSt：i成本G成本≤最大成本ii带宽G带宽≤带宽1;如果节点i和j0;否则这里的利用函数是两个独立的在给定的成本和带宽下的成本网格然而，随着网格大小的增加，选择最优布局的过程在本质上变得NP难。为了避免上述问题，这里提出了一种新的方法来解决优化问题。基于GA的Big-M（Bhunia等人，2010; Sahoo等人，2012）pen-alty方法用于解决优化问题。在这种方法中，不计算适应度函数的值为infasible解决方案。相反，M的值被认为是适应度函数的值Big-M算法是精确的算法，功能即可靠性和成本。问题是最大化在成本和带宽约束内的利用率，其中3.4. 拟议办法该方法是基于遗传算法的方法。该方法由两个算法组成：Optimize_NetworkD. Das等人/Journal of King Saud University447ð Þ¼Adj. 节点程度节点编号程度020213平均以上学位1222232324251低于平均水平5424总度数：12 / 6 = 2图五. 定期检查和维修。Regularity_Repair（G）。该算法有交叉和变异等操作.首先，该算法生成一个人口池，然后在构成人口池的生成树上应用交叉算子。提出了Regularity_ repair算法作为变异算子，并根据迭代次数确定了停止准则。首先选择任意两个已知链路、费用、可靠性等信息的网格网络。该网络被编码为一个二维二进制状态矩阵表示的邻接表。首先，使用形成人口池的函数Initial_population（）从所述网络生成一组建议的生成树。从种群池中，使用轮盘赌轮选择方法选择两个候选网络（生成树），并将其带入下一次迭代进行交叉。在交叉中，使用所提出的函数交叉（Pr1，Pr2），所选择的生成树形成父母Pr1和Pr2。在交叉操作期间，选择父Pr1和Pr2的节点之间的公共链路。如果公共链路不存在，则在节点之间建立虚拟链路，以得到两个新的子节点Ch1和Ch2，这两个新的子节点Ch1和Ch2被发现优于父节点。在交叉操作完成后，其中一个子节点通过下一次迭代进入变异步骤。我们已经提出了另一种称为“Regular-ity_repair（G）”的算法，它充当变异算子。在此步骤中，调用子例程“Regularity_repair（G）”来执行网络的规则性检查。在下一步中，通过调用函数“fitness（）”来评估每个孩子的适应度值。这些步骤 以 迭 代 方 式 执 行。 一 旦 达 到 可 靠 性 的 稳 定 状 态 ， 则终 止 算 法“Optimize_N etwork”。该算法收敛到最优解时，达到稳定状态或当所有新产生的后代推断从当前的一代。编码、交叉和变异的过程已经被通过合适的示例来说明。考虑具有6个节点和9个链路的多态计算网格（MCG）（图1（b）），其是图1（b）的子集。 1（a）. MCG的每个链路本质上是多状态的，即，链路在不同的负载、带宽和成本约束下具有不同的可靠性值。在给定负载、成本和带宽约束的情况下，目标是选择合适的链路，以最大限度地提高网络的带宽。提高可靠性。系统可靠性已使用Dejorreet Das等人的公式计算，2018年3.5. 该算法优化_网络该算法首先构建一个种群池，该种群池构成一组可供选择的染色体。染色体包含关于染色体所代表的解的信息。每个染色体都有一个二进制字符串，最常见的编码方式是使用二进制字符串，其中字符串中的每个位都可以表示解决方案的某些特征。遗传算法Optimize_Network的步骤如下所述：优化_网络步骤：1. 电流 Generation¼Initial Population2. 从总体池使用选择算法。3. 将Crossover应用于选定的网络以获得两个子网络。4. 检查规则性，并在必要时对每个子节点应用规则性修复G5. 使用[18]计算每个孩子的可靠性，满足适应度（），父母和孩子中更好的一个被提升到下一代。6. 对来自人口库。7. 如果达到停止条件，则终止该过程并打印在所有计算生成中具有最大可靠性的网络。其他i) 下一代产品ii) 转到步骤2。3.5.1. Initial_population（）本小节介绍了为所提出的算法生成函数Initial_population（）所448D. Das等人/Journal of King Saud University(a)输入网络，N=10，L = 18(b)输入网络，N=12，L=18(c)输入网络，N=12，L=20(d)输入网络，N=14，L= 18(e)输入网络，N=14，L=20(f)输入网络，N = 16，L=20(g)输入网络，N=16，L=25(h)输入网络，N=18，L=24(i)输入网络，N=18，L=26(j)输入网络，N=20，L=30见图6。 考虑用于仿真的输入网络。D. Das等人/Journal of King Saud University449ðÞ(k)输入网络，N=30，L=40(l)输入网络，N=41，L=47(m)输入网络，N =61，L=70(n)输入网络，N = 82，L =93图6（续）步骤：1. 从一个完全连通网生成Sn-生成树，其中Sn等于G的生成树个数2. i）使用Regularity_repair（G）计算每个n-网络的适应度值。ii）丢弃任何不满足适应度约束的网络选择生成树的目的是为了得到一个覆盖所有节点的连通网络。3.5.2. 选择在上述Initial_ population步骤期间生成生成树之后，开始选择过程。在选择过程中，最好的染色体（随机选择的生成树）被选为交叉操作期间的父代。通常，存在几种选择方法，如轮盘赌选择，玻尔兹曼选择等，其中，我们选择了轮盘赌选择方法来选择最佳染色体。3.5.3. 编码该网络被编码为一个二维矩阵，表示- ING的链接的邻接。它是一个二进制状态矩阵，其中存在链路表示1，不存在链路表示0。以下示例说明了所提出的编码技术。说明：让我们以图1所示的多态计算网格为例。所提出的编码过程的细节如下所示。在这里，我们假设4号节点充当路由器，所有其他节点单独被认为是一个小规模的计算网格网络。图中的网格的编码矩阵。 2在下面的表1中给出。3.5.4. 交叉（Pr1、Pr2）在生成初始种群集之后，执行编码过程。下一步是执行Crossover操作。 交叉运算符Crossover Pr1;Pr 2选择从母体染色体中分离基因并创造新的后代450D. Das等人/Journal of King Saud University←（一）（b）第（1）款（c）第（1）款（d）其他事项（五）（f）第（1）款见图7。 应用该算法后生成的优化网络。并且依赖于染色体的编码。针对特定问题进行特定的交叉操作可以提高遗传算法的性能.交叉操作的步骤如下：步骤：1. 从交配池中随机选择两个亲本Pr1和Pr2。2. CL←找到Pr1和Pr23. 如果CL=0，则4. VL在G的任意两个节点i和j之间建立虚拟链路5. CL = VL6. 其他7. 选择Pr1和Pr2中存在的公共链接。7.1. 公共链路的节点和与父Pr1的那些节点相关联的链路被结转以形成子Ch1的一部分。7.2. 公共链路的节点和与父Pr2的那些节点相关联的链路被结转以形成子Ch2的一部分。7.3. 子Ch1和Ch2的其余链接分别来自父Pr2和Pr1返回：Pr1、Pr2、Ch1和Ch2。说明：通过以下示例说明了网格的建议交叉方法的过程。在这里，我们考虑图2中的计算网格网络，以说明交叉操作。所提出的交叉操作分别如图3（a）和（b）用上述例子解释交叉操作。我们已经采取了生成树的父母和后代。根据该算法，两个父母Pr1和Pr2Pr2从步骤1的交配池中随机选择在步骤D. Das等人/Journal of King Saud University451（g）（h）（一）（十）（k）图7（续）2，则选择Pr1和Pr2中存在的公共链路，例如节点1和节点2之间的在步骤3中，我们检查两个父节点的任何两个节点之间是否存在公共链接。如果不是，那么我们在任意两个节点之间建立虚拟链路。在步骤7中，公共链路的节点（例如，节点1和2）以及与Pr 1的那些节点相关联的链路（例如，节点1和2之间的链路）被结转以形成子Ch1的一部分。类似地，公共链路的节点（例如，节点5和6）以及与Pr 2的那些节点相关联的链路（例如，节点5和6之间的链路）被向前结转以形成子Ch2的一部分最后，子Ch1和Ch2的其余链路分别从父Pr2和Pr1引入。3.5.5. Fitness（）：对于我们的优化问题，染色体的适应度取为：使用Regularity Repair检查图形的规则性i成本G≤最大成本ii.最大带宽3.5.6. 突变在交叉操作之后，下一个操作是变异。这样做是为了防止种群中的所有解落入已解决问题的局部最优解突变操作随机地改变新的后代。突变取决于编码以及交叉操作。在我们的例子中，我们设计了一个称为“Regularity_repair“的算法建议的算法：Regularity _repair（G）正则性修复算法将在这里表现为突变算子，以修复图G（如果是正则的），使其成为正则图。所提出的算法的步骤如下所述452D. Das等人/Journal of King Saud University[图7（l）图7（m）图7（n）图7（续）1. D = degree_Sum（G）2. 平均d= D/N表2遗传算法的参数设置。3. |= 0，最小值d = 0|=ø , Min d =ø4.如果度（Ni）>平均d（G）6i2N人口规模平均人口为111人。|最大xd|为|最大xd|[Ni世代2005. If degree（Ni）平均d（G）6i2N|为|最小d|Min d| Ni. 执行{初始群体选择操作者20个随机生成的生成树轮盘6. | H D|=Find_node with_Highest_degree（N）7. |一|= Adj_nodes（|H|）8. DS = A中每个元素的计算度9. AMd =max（DS）10.如果最大值d= 111.选择（Mind，AMd）else12.选择任何一个元素，使Min d形成（H，Mind）13.Mind = Min_degree（N）14.从G中删除（H，Mind15.Add（G，Add（Mind，AMd）16.} while（graph becomes regular）说明：拟议的突变过程如下所示。在这里，我们以图4中的网络为例，说明使用所提出的算法Regularity_repair（G）进行变异的过程。D. Das等人/Journal of King Saud University453交叉率0.85个单位变异率0.20停止当前世代的平均系统可靠性是等于前几代的在这个例子中，网格的平均度被计算为2。这里，节点1具有比平均度大的度，并且与节点编号1相邻的节点是0、2和3。如果任何节点（0，2，3）具有大于平均度的最高度（即图5中的2），则该链接将被选择用于删除，并且需要添加具有低于平均度的节点之一。这里，在这种情况下（图5），节点编号0、2、3具有相同的度2。由于（1，0），（1，2），（1，3）具有相同的度，因此，它们之间的任何一条链路都被选择删除，而同一条链路被添加到节点5。让选择删除的链接为（1，2）。那么，添加的新链接是（2，5）。454D. Das等人/Journal of King Saud University表3在多状态计算网格上使用该方法生成优化网格网络输入网络（N，L）投入成本（C）Input BW（inMbps）输入可靠性（R）输入群体大小（PS）输出优化网络输出R选择CPU时间（秒）图6（a）（10，18）25030.8149258图 7（a）0.92242.92图6（b）（12，18）28050.780615图 7（b）0.97023.50图6（c）（12，20）30060.8537258图 7（c）0.95094.01图6（d）（14，18）28050.840334图 7（d）0.97024.82图6（e）（14，20）28050.857966图 7（e）0.97024.97图6（f）（16，20）30060.747566图 7（f）0.94085.86图6（g）（16，25）35070.7726130图 7（g）0.93196.01图6（h）（18，24）35070.848634图 7（h）0.94129.23图6（i）（18，26）38080.8673130图 7（i）0.94159.75图6（j）（20，30）400100.771466图 7（j）0.970225.68图6（k）（30，40）460100.7900164图 7（k）0.899033.33图6（l）（41，47）51780.6824170图 7（l）0.7018118.25图6（m）（61，70）84780.6019200图 7（m）0.6211189.89图6（n）（81，93）1290100.5809250图 7（n）0.6107262.3910.950.90.850.80.75240260 280 300 320 340 360380成本400图8.第八条。优化可靠性和输入可靠性与成本的比较10090807060504030201000 50 100 150 200 250 300人口规模见图9。 CPU时间（秒）与人口大小。优化的可靠性输入可靠性可靠性CPU时间（秒）D. Das等人/Journal of King Saud University455ð Þ0.940.920.90.880.860.840.820.80.780.766 8 10 12 14 16 18 20数量的节点图10个。可靠性与节点数量2001801601401201008060402008 10 12 14 16 18数量的节点见图11。平均计算时间与节点数的比较。3.5.7. 停止标准当网络达到稳定状态时，所提出的优化网络的算法即当前代的平均系统可靠性等于前代时。3.6. 算法的收敛性所提出的优化网络算法在以下任何条件下收敛到最优解：i) 当达到稳定状态时：这是人口库没有发生变化的状态当总体的可靠度/费用参数处于稳态时，算法收敛到最优解。ii) 当所有新生成的后代都从它们的父母推断出来，所以没有新的更好的解决方案可以从现有的池中获得。条件（i）和（ii）的出现是非常自然的，这确保了所提出的算法的收敛性。4. 结果和讨论本文提出的算法OptimizeN etwork和Regularityrepair G在MATLAB7.9.0.529（R2009 b）中在Intel Core i3 CPU@2.00 GHz的 64位系统上执行，RAM大小为4 GB。用于GA的各种参数取如下：考虑到遗传算法的上述参数，所提出的方法被应用于一些计算可靠性建议的方法（Sahoo L. et.al，2012年）平均计算时间456D. Das等人/Journal of King Saud University10.990.980.970.960.950.940.930.920.910.9建议的方法（Sahoo L等人，2012年）0 50 100 150 200 250 300人口规模图12个。系统可靠性与人口规模的比较10.950.90.850.80.750.70.650.60.550.50.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95交叉率图13岁系统可靠性与交叉率的比较图6（a）-（k）所示的网格网络。输出优化网络与优化可靠性如图所示。 7（a）-（k）。实验结果表明，该算法在费用和带宽等约束条件下，优化了网络输入的系统可靠性该算法拓扑优化甚至复杂的网络。为了说明的目的，我们考虑了一个网络的成本为280，带宽为5 Mbps，输入可靠性为R = 0.8403到一个新的网络在相同的约束下，优化的可靠性为Ropt= 0.9702，合理的时间为4.82秒。 在上述所有考虑的网格网络的情况下，输出网络的输出可靠性（R opt）总是大于图1的输入网络的可靠性R。 6在假设的成本和带宽限制下。表2中的结果清楚地表明，在给定的成本和带宽约束条件下（见表3），提出的方法在生成具有最佳可靠性的优化网络布局方面具有优势。图8示出了各种计算网格网络的优化可靠性和输入可靠性与成本将成本作为约束条件，将输入可靠度与计算的最优可靠度值进行比较可以观察到，可靠性随着成本的增加而高度优化。图8中的曲线图显示，与优化前网络的输入可靠性值相比，优化后的可靠性值总是更好这清楚地表明，这是我们所提出的方法的优点，因为由于所提出的优化过程的应用，可靠性显著增加到相当高的值一个显示CPU时间（以秒为单位）随种群规模增加的图表绘制在图中。9.第九条。从图中的结果。 9，可以观察到CPU时间随着种群大小的增加而增加，这是由于交叉，突变和选择等操作的开销。图10描绘了可靠性相对于网格中的节点数量的变化。然而，链接的数量在其可靠性方面也起着重要作用。节点的可靠性、链路的可靠性和拓扑结构共同决定了网格的整体网络可靠性在节点和链路的可靠性值一致的情况下从图中可以进一步观察到，具有8个节点和14个链路的网络的可靠性比具有16个节点和25个链路的另一网络的可靠性高得多可以获得类似的观察结果，因为与12个节点和20个链路相比，具有10个节点和18个链路的网格具有更高的可靠性值具有20个节点和30个链路的相对较大尺寸的网格具有比用于比较的其他网格小得多的这是因为存在较少数量的链路和链路可靠性值。系统可靠性方法（Sahoo L et.al，2012年）系统可靠性D. Das等人/Journal of King Saud University457为了证明所提出的基于GA的方法的效率，将所提出的方法与（Sahoo等人，2012年）。输入网络（Sahoo等人，2012年）最初转换为可靠性图。这里考虑的输入网络模拟使用所提出的方法。如此获得的结果记录并描绘于图11、图12和图13中。分别为12和13。从图 可以观察到，与方法相比，使用所提出的方法的平均计算时间总是相当小（Sahoo等人， 2012年）。从图中可以看出，随着节点数量的增加，平均计算时间有显著所提出的方法证明，由于用于生成更好的后代的交叉和变异率，它可以用于大规模的网络，其中该方法（Sahoo等人，2012）可能无法在合理的时间内计算。为了研究所提出的方法的整体性能，系统的可靠性进行了分析，相对于不同的- ent遗传参数分别保持其他参数常数。图12示出了使用所提出的方法计算的优化的系统可靠性，该方法与Sahoo等人的现有方法相比总是更好， 2012年。因此，可以得出结论，所提出的基于GA的方法不满足局部最小值，并且总是收敛以产生最优化的解决方案。相反，尽管该方法（Sahoo等人， 2012）优化了可靠性，但该方法遇到了局部最小值。从图13中可以得出结论，发现使用所提出的方法在不同交叉率上计算的系统可靠性比Sahoo等人提出的方法更好，2012年。所提出的方法被证明产生更好的最优解在不同的交叉率。该算法采用高效的编码、交叉、变异和选择策略，保证了算法的快速收敛.在各种交叉率上，使用所提出的方法的系统可靠性没有如此显著的变化，而使用Sahoo等人的方法发现变化相当高， 2012年。5. 结论本文提出了一种基于遗传算法的技术，以优化多态计算网格网络的可靠性成本和带宽的限制。为此提出了两种算法该方法同样适用于大规模的多级网格网络。该方法通过适当的例子进行了说明该方法被认为是更有效的与其他现有的方法相比。引用阿加瓦尔，M.，古普塔河，巴西-地2005.约束冗余可靠性优化启发式算法中的罚函数法。IEEE Trans. Reliab. 54（3），549- 558。Bhunia，A.例如，2010.基于遗传算法的部件可靠度为区间数的串联系统可靠性随机优化。Appl. 数学Comput. 216，929-939。Carrestan，Javier等人，2007.基于遗传算法的网格计算系统调度器。Int. J. 创新计算INF. - 是的 6（3），1-19.Cassanova，H.，2002.分布式计算研究课题。ACM数字图书馆33，50-70。Coit，D.W.，史密斯，A.E.，1996.基于罚函数的遗传搜索算法在可靠性设计优化中的应用。Comput. Ind.Eng.30（4），895-904.Dai，Y.S.，Wang，L.X.，2006.基于遗传算法的网格系统服务可靠性最大化资源优化分配。可靠性工程系统安全性Elsevier 91，1071-1082.达斯D.例如，2018.约束多状态计算网格的系统可靠性估计。Int. J. Inf. Technol.https://doi.org/10.1007/s41870-018-0132-1.Dash，K.R. 例如，2012年。节点-边缘失效模型下互连网络的可靠性优化问题。Appl.软计算 Elsevier 12，2322- 2328.登吉兹湾例如，1997.用进化方法有效优化全终端可靠网络。IEEE Trans.可靠性 46（1），18-26。Dhingra，A.K.，1992.多目标下串联系统可靠度和冗余度的最优分配。IEEE Trans.可靠性 41（4），576-582。Feng，G.，Buyya河，2016年。最大限度地实现以收入为导向的云资源分配Int. J.GridUtil.Comput.7（1），12-21.https://doi.org/10.1504/IJGUC.2016.073772。福斯特岛例如，2002. 网格剖析：支持可扩展的虚拟组织。国际J.高性能。Comput.Appl.15，200-222.Gupta，K.R.例如，2009.基于遗传算法的惩罚函数法求解串联系统约束冗余分配问题与元件的区间值可靠性J.计算机《应用数学》，Elsevier 232，274-284。东野县例如，2016.混合粒子群-遗传算法在电网调度中的应用Int. J. 网格实用程序计算第七条第四款，113113-129129. https://doi.org/10.1504/IJGUC.2016.077493网站。Hikita等人，1992.用代理约束算法进行系统可靠性优化。IEEE Trans. Reliab. 4（3），473-480。Huang，H.Z.，田志Zuo，M.J.，2005.智能交互多目标优化方法及其在可靠性优化中的应用。IIE Trans. 37（11），983-993.Inagaki，T.例如，1978.多目标下系统可靠性交互优化。IEEE Trans. Reliab. 27（4），264-267。简，H.R.例如，1993.受可靠性约束的通信网络拓扑优化。IEEE Trans.可靠性 42（1），63-70。Kaushik，Achal，Vidyarthi，Prakash Deo，2018.计算网格中能量最优使用的混合启发式资源 分 配 模 型 。 Int. J. Grid Util. Comput.9 （ 1 ） ， 51-74 。 https ：//doi.org/10.1504/IJGUC.2018.10011390，pp. 5 1 比74金，J.H.，好吃B.J. 1993.求解复杂系统冗余优化问题的一种启发式方法。IEEE Trans.可靠性 42（4），572-578。郭，W.例如，2001年最佳可靠性设计：基础与应用。北京大学