概率故障条件下平衡超立方体的子网络可靠性

平衡超立方体具有许多优良的拓扑结构性质,较适合用于构建实际多处理器系统。在发生故障的互连网络中对无故障子网络的存在性进行量化评估有重要的现实意义。为了刻画n维平衡超立方体中(n-1)维平衡超立方体子网络存在性的保持能力,在概率故障条件下估计了n维平衡超立方体中无故障(n-1)维平衡超立方体子网络的存在概率。对于不小于3的n,得出了n维平衡超立方体中存在无故障(n-1)维平衡超立方体子网络的概率的一个上界和一个下界,并给出了这一子网络可靠性的基于蒙特卡洛仿真的近似评估算法。结果表明,当无故障(n-1)维平衡超立方体子网络的存在概率的上下界相差不大时,该上下界和近似结果是一致的;否则近似结果是较为准确的。

超立方体在对称PMC模型下的g-好邻条件诊断度和g-额外条件诊断度

故障诊断在维持多处理器系统的可靠性中起到了至关重要的作用,而诊断度是系统诊断能力的一个重要度量参数。除经典诊断度外还有条件诊断度,如g-好邻条件诊断度、g-额外条件诊断度等。其中g-好邻条件诊断度是在每个无故障顶点至少有g个无故障邻点的条件下定义的一种条件诊断度,g-额外条件诊断度是在每个无故障分支包含超过g个顶点的条件下定义的一种条件诊断度。故障诊断需要在特定的诊断模型下进行,如PMC模型、对称PMC模型等。对称PMC模型是在PMC模型的基础上通过添加两个假设而提出的一种新的诊断模型。n维超立方体因具有多种优越性质而被研究者们广泛研究。目前有不少在PMC模型下的诊断度研究,但缺乏在对称PMC模型下的诊断度研究。文中首先证明了超立方体在对称PMC模型下的g-好邻条件诊断度的上界和下界,当n≥4且0≤g≤n-4时上界为2^(g+1)(n-g-1)+2^(g)-1,当g≥0且n≥max{g+4,2^(g+1)-2^(-g)-g-1}时下界为(2n-2^(g+1)+1)2^(g-1)+(n-g)2^(g-1)-1。还证明了超立方体在对称PMC模型下的g-额外条件诊断度的上界和下界,当n≥4且0≤g≤n-4时上界为2n(g+1)-5g-2C_(g)^(2)-2,当n≥4且0≤g≤min n-4,23 n时下界为3/2n(g+1)-g-5/2C_(g+1)^(2)-1。最后通过模拟实验验证了相关理论结果的正确性。

基于拉丁超立方体的改进白骨顶鸡算法

针对白骨顶鸡算法求解工程问题时收敛速度慢,易陷入局部最优等不足,提出一种基于拉丁超立方体的改进白骨顶鸡算法。使用拉丁超立方体抽样增强初始种群的均匀性和多样性;引入非线性决策因子和自适应动态边界机制,提高算法全局搜索和局部开发能力;利用柯西变异对最优解进行扰动,帮助算法跳出局部最优。在16个基准函数、高维函数和工程问题进行仿真,其结果验证,该算法收敛速度和寻优精度良好,在工程问题上具有可行性和有效性。

一类正交拉丁超立方体设计二维投影均匀性的研究

正交拉丁超立方体设计(Orthogonal Latin hypercube designs, OLHDs)适用于计算机试验,是具有列正交性的一类空间填充设计。本文讨论了试验次数一般的一类正交拉丁超立方体设计在二维空间的投影均匀性,即在二维网格上的分层性质。结果表明该设计的所有列对都可以实现在s × s网格分层;来自相同组连续不相邻的列对可以实现在s × s2和s2 × s网格上分层,某些列对还能实现在s2 × s2网格上的分层。The Orthogonal Latin hypercube designs (OLHD), which is a class of space-filling designs with column orthogonality, is suitable for computer experiments. In this paper, the projection uniformity of a class of OLHDs with more general run sizes in two dimensions is discussed, i.e., the grid layering properties. The results show that the design can achieve stratifications on s × s grids in any two dimensions;most column pairs can achieve stratifications on finer s2 × s and s × s2 grids when the two columns are from the same group that are not adjacent to each other, and some column pairs achieve stratifications on s2 × s2 grids.

具有缺弧和失效点的单定向超立方体的诊断度

对于大规模多处理器系统,为了保证其可靠性,需要将发生故障的处理器及时诊断出来并进行更换。诊断度是系统能够自我识别的故障处理器的最大数目。n维单定向超立方体UQ_(n)是通过对超立方体Q_(n)所有的边进行定向得到的一个有向网络。研究了PMC模型下具有缺弧和失效点的单定向超立方体的诊断度。设S是UQ_(n)中缺弧和失效点的集合且S≤n/2」-1.通过对其缺弧和失效点的分布模式进行讨论,得到了UQ_(n)-S在PMC模型下的诊断度为UQ_(n)-S的最小入度,其中n≥3.

基于超立方体排队均衡的消防站布局和调度优化

科学合理的消防站布局与调度方案能够有效提升消防救援效率。本研究通过引入需求点对服务器效率的影响和系统饱和损失率,将现实中的复杂性和不确定性因素纳入消防资源优化模型,提出了一种基于超立方体排队均衡的消防站布局和调度优化模型,并设计了相应的遗传算法以实现模型的精准快速求解。研究结果表明,就近调派策略有可能对消防响应系统的整体效能提升带来负面影响;通过采用更加有效的消防系统布局及调度策略,能够显著提升消防资源利用率、救援平均通行效率以及系统饱和损失率等关键指标。

增强超立方体的分支连通度

利用r-分支(边)连通度作为可靠性的重要度量,对增强超立方体网络的可靠性进行分析,得到了r-分支(边)连通度,证明了cκ_(2)(Q_(n,k))=cλ_(2)(Q_(n,k))=n+1,其中2≤k≤n-1,cκ_(3)(Q_(n,k))=2n,cλ_(3)(Q_(n,k))=2n+1,其中4≤k≤n-1,cκ_(4)(Q_(n,k))=3n-2,其中4≤k≤n-1,cλ_(4)(Q_(n,k))=3n-1,其中6≤k≤n-1.

广义b-基超立方体网络的符号全控制数

该文研究了广义b-基超立方体网络GC_(n)(b)的符号全控制数γst(GC_(n)(b))的问题.首先给出了当n=2k+1,b=3时,网络GC_(n)(b)的符号全控制数的上下界,然后利用数学归纳递推和反证法,确定了当b=3,n=1,2,3时,网络GC_(n)(b)符号全控制数的精确值.

基于ADDPG策略的超立方体卫星编队控制

针对大规模卫星高精度编队控制问题,提出了一种基于吸引法则的深度确定性策略梯度控制方法(attraction-based deep deterministic policy gradient,ADDPG)。首先阐述了超立方体拓扑编队拓扑构型特性,建立了卫星编队动力学模型,设计了超立方体卫星编队虚拟中心用于衡量编队整体飞行状态。为解决无模型深度强化学习的探索和扩展平衡问题,设计了ε-imitation动作选择策略方法,最终提出了基于ADDPG的卫星编队控制策略。算法不依赖于环境模型,通过充分利用已有信息,可以降低学习模型初期探索过程中的盲目试错。仿真结果表明ADDPG策略以较少的能量消耗达到更高的精度,相比知名算法在加快编队收敛速度的同时,误差减少5%以上,能量消耗减少7%以上,验证了算法的有效性。

分层拉丁超立方体抽样方法及应用

为了提高样本数据的质量,文章提出了一种新的抽样方法——分层拉丁超立方体抽样,给出了该抽样方法的定义以及实现算法,证明了在相应条件下该抽样方法的估计精度比分层随机抽样方法更高,可以更有效地缩减蒙特卡罗方差。同时,还通过数值模拟比较了分层拉丁超立方体抽样与分层随机抽样在用蒙特卡罗方法估计定积分时的效果,数值模拟结果验证了上述结论的正确性。

基于h-extra边连通度的增强超立方体Qn,3的链路容错性分析

并行处理系统的设计和维护在很大程度上依赖于并行处理系统的可靠性评价.h-extra边连通度为评估这些系统在大规模故障链路下的互连网络的容错性和可靠性提供了一个更精确的参数.1991年Tzeng和Wei提出了(n,3)-增强超立方体Q_(n,3).研究了(n,3)-增强超立方体Q_(n,3)的h-extra边连通度,λh(Q_(n,3)),存在一个集中现象.对于整数「(11×2^(n−1))/48」≤h≤2^(n−1)和n≥9,λh(Q_(n,3))的精确值集中在2^(n−1)上.

一些特殊超立方体的Resolvent Estrada指标的研究

图G的Resolvent Estrada指标是E.Estrada和D.J.Higham 2010年引入的图的不变量,记作EE r G=(∑n i=11-λi n-1)-1=∑n i=1 n-1 n-1-λi.研究超立方体B n、折叠超立方体F n和增广超立方体D n的Resolvent Estrada指标的界.

交换超立方体的拓扑性质与嵌入问题研究

交换超立方体(Exchanged hypercube)作为超立方体的一种变型网络,降低了网络规模增大时所需要的拓扑连接的开销.本文根据交换超立方体的图形化定义,得到交换超立方体的公式化定义,证明了交换超立方部分子网与超立方网同构,提出EHS(s,t)和EHT(s,t)的概念,并在此概念的基础上证明了交换超立方体中只存在长度不小于4的偶数圈,证明了交换超立方体的顶点连通度和边连通度都为min{s+1,t+1}.为使交换超立方体具有更广阔的应用范围,本文还提出了超立方体在交换立方网中的三种嵌入策略,证明了n=s+t+1时,n-1维超立方体Qn-1能够同胚地嵌入到交换超立方体EH(s,t)中.

交叉超立方体网络的边泛圈性(英文)

作为超立方体Qn的变型,在点数和边数都相同的情况下,交叉超立方体CQn有比超立方体更好的性质.在已获证明的CQn包含所有长度(从4到2n)的圈的基础上,进一步改进了这一结果,证明了CQn中每条边落在所有长度(从4到2n)的圈中.

拉丁超立方体抽样遗传算法求解图的二划分问题

图的二划分问题是一个典型的NP-hard组合优化问题,在许多领域都有重要应用.近年来,传统遗传算法等各种智能优化方法被引入到该问题的求解中来,但效果不理想.基于理想浓度模型的机理分析,利用拉丁超立方体抽样的理论和方法,对遗传算法中的交叉操作进行了重新设计,并在分析图二划分问题特点的基础上,结合局部搜索策略,给出了一个解决图二划分问题的新的遗传算法,称之为拉丁超立方体抽样遗传算法.通过将该算法与简单遗传算法和佳点集遗传算法进行求解图二划分问题的仿真模拟比较,可以看出新的算法提高了求解的质量、速度和精度.

交换折叠超立方体的超连通度

超连通度(超边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数。设G是连通图,图G的超连通度(超边连通度)是指从G中删除最小数目的点(边)使得G不连通,且G的每个连通分支中都至少包含两个顶点。李等人(2015)提出了一个新的网络交换折叠超立方体网络EFH(s,t)。该文利用超连通度和超边连通度作为评价可靠性的重要度量,对交换折叠超立方体网络的可靠性进行分析,得到了交换折叠超立方体网络的超连通度和超边连通度,证明了EFH(s,t)的超连通度和超边连通度等于2s+2,1 s t。这个结果意味着,为了使EFH(s,t)不连通且不含孤立点,至少有2s+2个点(边)要同时发生故障。

关于加强超立方体互连网络的可诊断性的另一种证明方法

ｎ维加强超立方体是具有２ｎ个顶点，（ｎ＋１）２ｎ－１条边的（ｎ＋１）－正则图，它是通过对ｎ维超立方体增加２ｎ－１条边得到的．在［１］中证明了基于ＰＭＣ模型的ｎ维加强超立方体在精确诊断策略下是（ｎ＋１）－可诊断的，在悲观诊断策略下是（２ｎ）／（２ｎ）－可诊断的，但其证明很繁琐．本文利用［１０，３］中的结果，给出了加强超立方体可诊断性的另一个更为简洁的证明。

关于折叠超立方体的反馈数

研究了一类重要的互连网络拓扑结构折叠超立方体网络Qfn的反馈数．设F为Qfn的反馈集，通过构造剩余子图G[V（Qfn）-F]的极大无圈子图得到极小反馈集，从而得到反馈数的上界，用此方法研究折叠超立方体网络Qfn的反馈数问题．根据n维折叠超立方体网络的性质，提出一种新的方法构造无圈子图，改进了已有的”维折叠超立方体网络的反馈数的上界．结果表明，当n为奇数时构造的Qfn＋z的无圈导出子图的整体连通性能与已有结论中构造的Q中无圈导出子图R∪Qfon是一致的．

折叠超立方体网络的边容错哈密顿性(英文)

证明了在至多具有2n-3条故障边的n维(n≥3)折叠超立方体网络中,如果每个顶点至少与两条非故障边相邻,则存在一个不含故障边的哈密顿圈.这个界是最好的.

广义超立方体的点扩张

通过广义超立方体的一种点扩张方法构造了广义超立方体循环网络,它包括了人们熟悉的带环连通立方体;证明了广义超立方体循环网络是Cayley图.