三支区间集半概念的代数结构及覆盖粗糙近似算子

针对在一个形式背景中以区间集为底集,考虑一个属性集(对象集)拥有的对象集(属性集)和不拥有的对象集(属性集)的知识表述而进行知识提取的问题,采取将区间集概念与三支决策、经典半概念相结合的方法,产生AE-区间集半概念和OE-区间集半概念两种形式的三支区间集半概念,同时发现AE-区间集半概念与OE-区间集半概念的纯双布尔代数结构。进一步深入讨论可知,AE-区间集半概念可分为AE1-区间集半概念与AE2-区间集半概念,利用粗糙集理论分别挖掘与AE1-区间集半概念和AE2-区间集半概念有关的近似算子的结构性质,对偶地可得OE-区间集半概念的相关结果。所得三支区间集半概念拓广了已有的三支决策集分别与区间集概念和半概念相结合的相关成果,成为一个新的知识表述。

融合GPU的拟单层覆盖近似集计算方法

拟单层覆盖粗糙集是一种匹配集值信息系统且有高质量和高效率的粗糙集模型。拟单层覆盖近似集的计算过程中存在大量计算密集且逻辑简单的运算,为此,提出拟单层覆盖近似集的矩阵化表示方法,以利用图形处理器(GPU)强大的计算性能加速计算过程。为了实现这一目标,使用布尔矩阵表示拟单层覆盖近似空间中的元素,引入与集合运算对应的布尔矩阵算子,提出拟单层覆盖粗糙近似集(DE、DA、DE0与DA0)的矩阵表示,并设计矩阵化拟单层覆盖近似集算法(M_SMC)。同时,相应的定理证明了拟单层覆盖近似集的矩阵表示形式与原始定义的等价性。然而,M_SMC运行过程中出现了矩阵存储和计算步骤的内存消耗过多问题。为了将算法部署到显存有限的GPU上,优化矩阵存储和计算步骤,提出分批处理的矩阵化拟单层覆盖近似集算法(BM_SMC)。在10个数据集上的实验结果表明,融合GPU的BM_SMC算法与单纯使用中央处理器(CPU)的BM_SMC算法相比计算效率提高2.16~11.3倍,BM_SMC算法可以在有限的存储空间条件下充分利用GPU,能够有效地提高拟单层覆盖近似集的计算效率。

量子近似优化算法在精确覆盖问题中的应用

精确覆盖问题属于组合优化中的NP完全问题,使用经典算法难以在多项式时间范围内求解。为解决该问题,在开源量子计算框架qiskit上,提出基于量子近似优化算法(QAOA)的量子线路求解方案,并采用基于单纯形法的线性近似约束优化(COBYLA)算法对量子逻辑门中的参数进行优化。首先,通过精确覆盖问题的数学模型建立经典伊辛模型;其次,利用量子理论中的旋转变量对经典伊辛模型进行量子化,再用泡利旋转算子代替旋转变量,得到量子伊辛模型和问题哈密顿量,提高QAOA寻找最优的速度;最后,以混合哈密顿量为生成元的酉变换和问题哈密顿量为生成元的酉变换乘积的累积,得到问题哈密顿量期望的表达式,并由此设计生成量子线路。另外,通过经典处理器对两个酉变换中的参数进行优化,调整问题哈密顿量的期望值,从而提高求解的概率。该线路在IBM的开源量子计算框架qiskit上进行仿真实验,实验结果表明,所提方案能够在多项式时间内以95.6%的概率获得问题的解,验证了所提量子线路能够以较高的概率求得精确覆盖问题的解。

基于一般二元关系粗糙近似算子的格结构研究

刻画了基于一般二元关系及悲观多粒度粗糙近似算子的完备格结构,证明了在选取蕴涵算子之后,基于一般二元关系的粗糙近似算子构成MV、R0与布尔代数。

无线传感器网络中基于μ律爆炸算子的烟花虚拟力混合覆盖策略

针对烟花算法在无线传感器网络节点部署过程中易陷入局部最优导致节点分布不均匀、后期收敛速度慢等问题,本文提出一种基于μ律爆炸算子的烟花虚拟力混合算法(μFW–VFA).首先,采用μ律特性曲线重新定义爆炸算子,增强烟花间的差异性,通过动态调整μ值使烟花爆炸的数目和幅度随迭代次数动态调整,以平衡烟花局部和全局的寻优能力.其次,引入虚拟力调节停滞烟花内传感器节点的位置信息,加速烟花种群进化,增强算法跳出局部最优的能力,提高算法收敛速度.仿真实验表明,经μFW–VFA部署后,网络的重叠区域和监测盲区显著减少,有效提升了网络覆盖率并压缩节点移动距离.

覆盖模糊粗糙集近似算子的拓扑性质

通过闭包与内部算子研究覆盖模糊粗糙集的拓扑结构,证明了覆盖近似空间中模糊粗糙集的上、下近似算子分别为一个模糊拓扑的闭包、内部算子;反之,满足一定条件的模糊拓扑的闭包与内部算子也恰为一覆盖近似空间中模糊粗糙集的上、下近似算子.

基于覆盖的粗糙近似算子

研究Bonikowski覆盖近似算子。借助覆盖近似空间的代表元,证明了下近似算子保交、上近似算子保并、以及上近似算子单调等是相互等价的,另外给出了上、下近似算子对偶的等价条件。

变精度覆盖近似算子与覆盖近似算子的关系

变精度覆盖粗糙集模型是在放宽了覆盖标准的前提下给出的,因而导致近似算子发生了变化,但其变化有一定的规律。在介绍了覆盖粗糙集模型和变精度覆盖粗糙集模型的概念的基础上,给出并证明了变精度覆盖粗糙近似算子与覆盖粗糙近似算子之间的关系,即定理1、定理2及其推论。

覆盖粗糙近似算子

首先给出了模糊集的覆盖上、下近似算子的定义,讨论了它们的简单性质.其次,覆盖近似空间中,由于覆盖粗糙不等式在进行并、交运算时会使信息丢失,因而讨论了覆盖粗糙不等式取等号的充分条件.

变精度覆盖粗糙集模型近似算子的性质

变精度覆盖粗糙集模型是在放宽了覆盖标准的前提下给出的,因而导致近似算子发生了变化.在介绍了覆盖粗糙集模型和变精度覆盖粗糙集模型的概念的基础上,给出并证明了变精度覆盖粗糙集模型的近似算子的几个性质,即定理1、定理2、定理3及其推论.

一类覆盖近似算子的动态更新方法

粗糙集理论是一种有效的数据挖掘工具,覆盖粗糙集理论是粗糙集理论中的重要部分。给出了一对覆盖近似算子随数据对象增加的更新方法,并以实例说明了所提出的更新方法的有效性。

协调映射下一类覆盖上近似算子的不变性质

协调映射可以将信息系统映成对象较少的信息系统,从而压缩数据.本文讨论覆盖粗集在协调映射下的不变性质,指出满的协调映射可以保证原覆盖近似空间的一类覆盖上近似与像覆盖近似空间覆盖上近似之间一一对应.

基于对象的广义粗糙近似算子的拓扑性质

粗糙集理论是一种处理不确定性问题的数学工具。近似算子是粗糙集理论中的核心概念,基于等价关系的Pawlak近似算子可以推广为基于一般二元关系的广义粗糙近似算子。近似算子的拓扑结构是粗糙集理论的重点研究方向。文中主要研究基于对象的广义粗糙近似算子诱导拓扑的性质,证明了广义近似空间中所有可定义集形成拓扑的充分条件也是其必要条件,研究了该拓扑的正则、正规性等拓扑性质;给出了串行二元关系与其传递闭包可以生成相同拓扑的等价条件;讨论了该拓扑与任意二元关系下基于对象的广义粗糙近似算子所诱导拓扑之间的相互关系。

有向传感器网络中基于公平的目标覆盖最大化问题研究

以视频传感器和图像传感器为代表的有向传感器可以为安全防卫提供有效信息,已经被广泛应用于各种场景。首次提出了有向传感器网络中基于公平的目标覆盖最大化问题:在有向传感器网络中,采用具有P个确定工作方向的有向传感模型,研究基于公平的目标覆盖最大化问题,目的是激活最少的传感器,通过调度有向传感器的工作方向使目标被覆盖的最小累积覆盖时间达到最大,从而保证目标被覆盖的时间尽量均衡。首先选择最少的传感器,保证所有目标位于所选传感器的传感圆之内(该问题是NP-困难问题),为解决该问题设计了近似比为(1+lnγ)的最少传感器选择算法,其中γ=max 1≤i≤N{|s_(i)||s_(i)∈S};其次,基于最大需求优先覆盖的原则,提出了最大的无冲突目标集合选择算法。实验结果表明,该算法能有效解决有向传感器网络中基于公平的目标覆盖最大化问题。

基于改进遗传算法的无线传感器网络覆盖优化

提出一种基于逆模型引导算法搜索的多目标演化算法(MOEA-OMG),通过对种群的目标空间随机采样,然后利用高斯过程将采样解映射回决策空间,得到包含种群分布信息的试验解,引导算法搜索,利用提出的重组算子将试验解与其他解个体进行组合,产生高质量后代解。将算法应用到解决无线传感器网络(WSNs)覆盖问题,并与传统的几种优化算法进行实验对比,结果表明,所提算法在求解WSNs覆盖问题时,展现出较为明显的性能优势。

基于模糊β-覆盖的(I,T)-模糊粗糙近似算子

利用模糊β-邻域和模糊逻辑算子,提出两种基于模糊β-覆盖的(I,T)-模糊粗糙集模型;研究了模型中上、下近似算子的基本性质;对比分析这两对广义模糊粗糙近似算子与其他模糊粗糙近似算子之间的关系,刻画了相关近似算子等价的条件。

一种求解图分割问题的量子近似优化算法

量子近似优化算法(Quantum Approximate Optimization Algorithm,QAOA)是求解组合优化问题的算法框架,是近期最有可能展示量子计算优势的算法之一.在QAOA框架内,表征解的量子态采取的二进制编码方案导致的对称性限制了QAOA的性能.为了克服这一局限性,本文受Dicke态制备算法的启发,给出了一种新的解编码方案,消除了现有编码方案中的对称性.本文还设计了新的演化算子——星图(Star Graph,SG)算子,及其对应的SG算法,给出了算法求解图分割问题时的量子电路.在IBM Q上的实验结果显示,星图算法比标准QAO算法平均约有25.3%的性能提升.

处理Non-LTE谱线覆盖效应的有效方法——近似A算子法

本文在分析完全线性化方法不能很好地处理Non-LTE谱线覆盖效应的基础上,介绍了一种由Werner(1986年)引进的能有效的处理Non-LTE谱线覆盖效应的计算Non-LTE恒星大气模型的方法——近似A算子法。并对这种方法的优缺点和可能的应用作了分析和讨论。

内部、闭包算子、邻域与近似算子的关系

研究了 RiA与i RA、RclA与clRA的关系.引入评价函数、外开域算子、内闭域算子等概念,得出了iA i RiA、clRclA clA等重要结论.在邻域与近似算子的关系的研究中,定义了近似强、弱、非邻域、近似拓扑和近似拓扑邻域等概念,并研究了各种邻域之间,以及它们与近似算子的关系.

求图的最小顶点覆盖集的一个近似算法

已有的求图的最小顶点覆盖集近似算法或者近似比较高,或者为降低时间复杂度限制了图的规模.根据顶点的度分析了图的局部结构特征,提出了悬挂链、封闭链和稠部等重要概念,并在这些概念的基础上提出了相应的3个伪最小覆盖点选取启发式策略.运用这些伪最小覆盖点选取启发式策略设计了一个近似算法.该算法不限制图的规模,时间复杂度为O(|V|2),近似比为4/3,接近已知的可能的近似比下界1.1666,低于2005年认为最低的近似比1.361.与同类算法相比,该算法设计思路清晰,容易理解,易于编程实现,执行效果好,是图的最小顶点覆盖集问题的近似算法的一个重要补充.