基于粒计算的大数据处理
摘要：在大数据时代,如何充分挖掘出蕴藏于数据资源中的价值正在成为各国IT业界、学术界和政府共同关注的焦点.使用云计算平台分布式地存储和分析大数据已经成为共识并且得到了广泛应用,但这并没有完全解决大数据的3V特性带来的问题.全面应对大数据的挑战需要来自存储技术、下一代网络、处理器、计算模型等各个领域的创新.粒计算是在求解问题过程中使用＂粒＂的理论、方法、技术和工具的集合,适用于近似求解有不确定性和层次结构的问题.该文综述了大数据处理的研究现状,分析了当前大数据处理研究存在的局限性;根据运用粒计算方法解决问题的不同特征,该文归纳了粒计算的3种基本模式,回顾了各种模式的相关研究工作;该文讨论了粒计算应用于大数据处理的可行性与优势,并探讨了在大数据的粒计算处理框架中需要解决的各个关键问题.多重二次背包问题的量子进化求解算法
摘要：多重二次背包问题是二次背包与多重背包两种NP（Non-Deterministic Polynomial,非确定多项式）难问题融合后的一种新问题,由于其决策变量间具有高耦合性,已有的启发式算法求解效率和精度不够理想.针对这一问题提出一种量子进化求解算法,这种算法的量子观测操作能将部分约束处理与观测一步完成,解码效率高且不易陷入局部极值.算法中的量子更新采用自适应调节整体更新方式,相比传统查表方式更简洁和高效.算法还设计了一种局部和全局修补算子以保证解的可行性.另外,设计的交换算子能增强算法在约束边界的搜索性能.标准算例测试实验的结果表明文中提出的求解算法比传统算法的精度和效率更高.求解三维装箱问题的启发式正交二叉树搜索算法
摘要：文中提出了一种求解三维装箱问题的启发式二叉树搜索算法,首先将所有箱子组合成多个优条,每个优条中的箱子沿容器高度方向排成一列;接着开始构建二叉树,其根节点表示空的装箱方案,每个树节点沿长度方向增加一排优条形成左子树节点,沿宽度方向增加一排优条形成右子树节点,二叉树必须扩展到所有叶子节点都无法再放入任何剩余的箱子为止,所有叶子节点中填充率最高的装箱方案即为最终结果.该算法满足三维装箱的3个著名的约束条件.在多样性最强的测试算例中,该文方法相对于现有最优秀装箱算法装箱率有显著提高.基于预测策略的动态多目标免疫优化算法
摘要：为了有效解决动态多目标优化问题,文中提出了一种新的基于预测策略的动态多目标免疫优化算法.该算法首先采用相似性检测算子较好地检测到环境的变化.同时利用前几个时刻的最优非支配抗体解集建立新的预测模型来预测产生新时刻的初始抗体种群,进一步提高了算法对环境变化的反应能力.此外,通过引入基于两种不同的父代个体选择策略而改进的差分交叉算子来加快算法的收敛速度.文中采用几个典型的标准测试问题验证算法的有效性,实验结果表明,提出的相似性检测算子的预测模型可以提高算法的跟踪能力,而改进的差分交叉算子能够提高算法的收敛性能.最大不全k满足问题的局部搜索近似算法
摘要：合取范式可满足与最大可满足问题是理论计算机科学的核心问题.最大不全满足问题是最大可满足问题的一般化.限制每个子句均含有k（≥2）个字母的最大不全满足问题又称为最大不全k满足问题.最大不全满足问题的算法进展,以解答该类问题的半定规划松弛法最具代表性.关于最大不全2满足、3满足和4满足问题,目前性能最好的近似算法分别由Goemans与Williamson、Zwick、Karloff与Zwick给出,近似性能比分别为1.139（1/0.878）、1.10047（1/0.9087）和8/7.当k≥5时,最大不全k满足问题的近似算法则未曾见到.文中给出了一个解答最大不全k满足问题的局部搜索算法,近似性能比可达到2k-1/（2k-1-1）,k≥2;进一步将该方法推广到解答由不少于k个字母的子句构成的最大不全k满足问题,近似性能比亦可达到2k-1/（2k-1-1）.利用解答最大不全k满足问题的近似算法,给出了解答最大k可满足问题的新近似算法,近似性能比可达到2k/（2k-1）.文中最后证明了若P≠NP,则k≥4的最大不全k满足问题不能近似到小于2k-1/（2k-1-1）,从而说明文中解答最大不全k满足问题的算法近似性能比是最优的.一种基于交叉熵的社区发现算法
摘要：作为复杂网络中的一个极其重要的研究领域,社区结构的搜寻和发现研究具有重要的应用价值.该文将信号处理领域的交叉熵概念引入到网络社区结构的发现算法中,提出了一种基于交叉熵的社区发现算法.算法利用Modularity值作为判别依据,使用交叉熵方法中的重要抽样方法提高收敛速度,从而在提高社区发现算法运算效率的同时,提高算法的精确性.针对计算机生成网络的社区划分结果表明,该算法所得MNI值和划分正确节点所占比例高于Girvan-Newman算法.在真实网络上的仿真结果表明,该社区划分算法的Modularity值高于Girvan-Newman算法,且不低于极值优化算法,进一步验证了该文提出算法的社区划分准确性优于已有的GirvanNewman算法和极值优化算法.进化算法首达时间分析的停时理论模型
摘要：计算时间分析是进化算法理论基础研究中的重要课题,也是一大难点.该文基于停时理论,结合时齐马氏过程的性质,将进化算法的首达时间视为停时,提出了分析进化算法首达时间的一个新方法.在此框架下,Level-reaching Estimation Technique作为特例得到了严格的证明.为展示如何用该理论方法分析具体问题,以（1＋λ）EA求解PEAK函数和（1＋λ）ES求解倾斜平面问题为实例,分析了平均首达时间.结果表明,该文所提出的方法不但适用于离散优化问题也适用于连续优化问题,具有通用性.半监督学习方法
摘要：半监督学习研究如何同时利用有类标签的样本和无类标签的样例改进学习性能,成为近年来机器学习领域的研究热点.鉴于半监督学习的理论意义和实际应用价值,系统综述了半监督学习方法.首先概述了半监督学习的相关概念,包括半监督学习的定义、半监督学习研究的发展历程、半监督学习方法依赖的假设以及半监督学习的分类,然后分别从分类、回归、聚类和降维这4个方面详述了半监督学习方法,接着从理论上对半监督学习进行了分析并给出半监督学习的误差界和样本复杂度,最后探讨了半监督学习领域未来的研究方向.基于非标准分析的粒计算研究
摘要：该文着力于研究粒计算的基本理论.粒计算作为一种粒数数系被研究,在这种数系中研究粒运算的基本定律、粒与粒之间的不可区分关系;研究这种粒数系中描述型的形式语言等.采用的方法是基于非标准分析中的超实数理论研究实值粒运算应遵循的规则,也研究了伴随二元关系的信息粒的合成、加粗、加细、并和交运算等;在分析前人工作的基础上、基于超实数理论进一步为粒计算研究定义了一种新的不可区分关系,得到了几个相关性质,并且证明了相关结果.随后定义了描述这种粒数数系的描述型形式语言——一种带不可区分关系词的二阶粒逻辑;粒常量、粒变量、粒函数项的相关运算定律也被定义了.最后,以示例演示了这种粒逻辑适应于描述粒数学定理、粒公式化简等.决策粗糙集理论研究现状与展望
摘要：经典Pawlak粗糙集理论中的核心概念上、下近似集是通过集合相交非空和包含来定义的.由于缺乏对错误的容忍能力,其实际应用受到了限制.20世纪90年代初,Yao等人结合贝叶斯决策理论提出了决策粗糙集模型.近年来,该模型逐渐得到重视,并在不确定性信息处理方面得到了广泛应用.该文首先就为什么要提出决策粗糙集模型、该模型具有什么特点以及该模型中需要解决的几个问题进行了详细讨论.然后,总结了国内外关于决策粗糙集模型的研究现状和进展,详细分析了存在的挑战性问题,并深入探讨了未来的研究方向.几何定理机器证明复系数质点法的改进及其应用
摘要：复系数质点法是以几何点的运算为基础而建立起来的一种新的几何定理机器证明方法.它能高效地证明大部分构造型几何命题,但现有的复系数质点法仍不能有效地处理一些非线性构造型几何命题.为此,该文在原有工作的基础上,对原复系数质点法机器证明算法进行了较大的改进,新添加了一些重要的构图方式,并选用Mathematica重新实现了改进的算法,创建了新的证明器CMPP（Complex Mass Point method Prover）.对上百个几何定理的运行结果显示,证明器CMPP能有效地处理非线性构造型几何命题以及许多非构造型几何命题,在解题能力及运行效率上均有所提高.特别地,CMPP能在短时间内实现五圆定理、莫莱定理等一些难度较大的几何定理的可读机器证明.三值汉明码检错纠错原理和方法
摘要：随着光通信技术的应用和千位三值光学计算机系统研究的推进,确保数据信息免受各种干扰以及系统的可靠运行显得十分重要.该文给出了三值汉明码的一种分组形式,提出了三值汉明码的检错原理和出错位置的确定方法.基于给出的三值汉明码的两个纠错码表,提出了三值汉明码的纠错原理,画出了基于三值光学计算机的三值汉明码检错纠错概念结构图.该工作为三值光学信息的检错纠错奠定了理论基础.分布式约束优化问题研究及其进展
摘要：多Agent协作过程中的许多问题都可以被抽象为分布式约束优化问题（DCOP）,如规划、行程安排、分布式控制和资源分配等.这些问题关注于如何通过协调多Agent之间的相互决定,以达到一个全局最优决策的目的.相应地,分布式约束优化算法是用来求解此类问题的一种有效方式.该文对分布式约束优化问题进行了综述,首先,阐述了分布式约束优化问题的基本概念,并提出了一种分布式约束优化算法的分类框架.其次,根据该分类框架,介绍了目前已有的分布式约束优化算法,并加以对比分析.此外,分析了分布式约束优化问题的相关应用.最后,指明了分布式约束优化领域的未来研究趋势.命题逻辑系统R0L3n＋1中公式的Γ-真度及性质
摘要：计量逻辑理论是王国俊教授于21世纪初期建立的一种新型逻辑理论,真度理论在计量逻辑理论中发挥着关键的作用.该文将真度概念加以推广,在（3n＋1）-值模糊命题逻辑系统R0L中引入了公式相对于含有限个命题变元的理论的Γ-真度;讨论了与析取连接词、合取连接词、蕴含连接词、否定连接词等基本逻辑连接词相关的Γ-真度性质;讨论了与分离规则MP,三段论规则HS等推理规则相关的Γ-真度性质.该文的工作为将计量逻辑的思想融入（3n＋1）-值模糊命题逻辑系统R0L并建立基于给定理论的近似推理基本框架和相关的逻辑度量空间奠定了基础.极大平面图理论研究进展
摘要：四色猜想是指平面图的色数不超过4.实际上,四色猜想只需证明对极大平面图成立即可.正因为如此,从1891年至今,有众多学者从不同的角度展开了对极大平面图的研究.该文拟对其中的一些重要成果进行较为详细的综述,主要包括极大平面图的度序列问题、Hamilton性、色多项式、生成运算系统、计数、翻转运算、分解与覆盖、生成树和算法等方面.在总结极大平面图研究现状的基础上,提出了一些与着色相关的问题,这些问题意在探索极大平面图的结构与着色之间的关系,有助于对四色问题的进一步研究.网络分析中求最大流的商空间方法
摘要：该文研究利用商空间的保真、保假原理给出分析网络的新方法,并以求网络中两点的最大流量为例进行说明,主要工作包括：（1）给出利用保真、保假原理求解问题的基本原则;（2）给出将所研究的问题（求最大流问题）化成＂问题求解＂形式的方法;（3）利用商空间理论建立对应问题求解的保真、保假原理,并证明对所研究的问题,保真、保假原理均成立;（4）根据保真、保假原理给出求两点最大流量的方法.新方法对求所有的点对点的最大流的计算量由原来需要求n（n-1）/2次点对点的最大流,变成只要求（n-1）次点对点的最大流,显著降低了计算的复杂性.