BK-means:骨架初始解K-means

K-means是典型的启发式聚类算法,容易受到初始解的影响而无法获得高质量的聚类结果。骨架是近年来启发式算法设计的研究热点,它是指所有全局最优解中相同的部分,对于提高启发式算法性能具有重要意义。给出的骨架初始解K-means算法(BK-means)的基本思想是:首先利用K-means算法得到一组局部最优解(聚类结果),通过对局部最优解求交得到骨架簇。利用骨架簇构造骨架初始解及新的搜索空间。最后以骨架初始解引导K-means算法在新的搜索空间中搜索聚类结果。在15组仿真数据集和4组实际数据集上的实验结果表明,BK-means算法具有获得高内聚、高分离的聚类结果能力。     

一种可信子空间标志方法*

在D-S证据理论的基础上,给出了可信子空间的定义及能够发现所有可信子空间的贪心算法CSL(creditable subspace labeling)。该方法迭代地发现原始特征空间的信任子空间集Cs。用户根据应用领域的需求, 对Cs中的每个可信子空间调用传统聚类算法发现聚类结果。实验结果表明,CSL具有正确发现原始特征空间的真实子空间的能力,为传统聚类算法处理高维数据空间聚类问题提供了一种新的途径。     

一种应用于网格计算环境的任务调度模式*

提出了一种新的网格任务调度模式,针对网格计算资源有组织、松耦合、自治等特性,建立基于多层次虚拟组织形式的计算资源模型;根据网格环境中应用任务粗粒度、特定资源依赖等特点,建立了网格任务的描述模型;提出并实现了相应的子任务生成算法、任务初始调度算法及自动调整算法。设计实现了能够支持仿真及实际网格计算环境可扩展网格任务调度器,通过理论分析和仿真实验对算法的正确性、效果和效率进行了评价。     

共有信息引导的启发式聚类算法

启发式聚类算法采用局部搜索策略发现使得目标函数取极小值的聚类结果,即局部最优聚类结果。算法虽然具有收敛速度快等优点,但是初始解敏感问题严重地影响了聚类结果的质量。利用多个局部最优聚类结果中的共有信息设计启发式聚类算法。首先给出共有信息的定义及其发现算法FCI_G;然后利用共有信息设计启发式聚类算法CIGC;最后在多组仿真和实际数据集上考察了CIGC算法的性能。实验结果表明,共有信息对提高聚类算法质量有着显著的作用。     

基于时间STM的软件形式化建模与验证方法

状态迁移矩阵(state transition matrix,简称STM)是一种基于表结构的状态机建模方法,前端为表格形式,后端则具有严格的形式化定义,用于建模软件系统行为.但目前STM不具有时间语义,这极大地限制了该方法在实时嵌入式软件建模方面的应用.针对这一问题,提出了一种基于时间STM(time STM,简称TSTM)的形式化建模方法,通过为STM各单元格增加时间语义和约束,使其适用于实时软件行为刻画.此外,针对TSTM给出了一种基于界限模型检测(bounded model checking,简称BMC)技术的时间计算树逻辑(time computation tree logic,简称TCTL)模型检测方法,以验证TSTM时间及逻辑属性.最后,通过对某型号列控制软件进行TSTM建模与验证,证明了上述方法的有效性.     

基于反馈机制的网格动态授权新模型

网格现有的授权系统存在静态性问题,表现为没有提供机制来反馈用户对授予的权限的使用情况.当一个本来可信的用户或服务变成不可信时,授权系统不能及时发现,对其权限进行调整可能导致恶意用户对网格系统的破坏.因此,在授权系统中建立反馈机制,根据用户的行为动态地调整用户角色,对于网格系统的安全具有重大意义.文中分析了网格中现有的授权系统及信任模型的特点,指出它们存在的不足.在此基础上提出一种基于反馈机制的动态授权新模型,很好地解决了现有授权系统的静态性的缺点.该模型是对CAS授权系统的改进,增加了反馈机制和信任度计算机制.其中,信任度计算机制中提出的基于行为的分层信任新模型较以往的信任模型相比,使用服务权值来区分重要服务和普通服务,从而保护了网格中的重要服务并且能有效地抑制恶意节点的行为;文中提出了一种新的更加精确地计算域间推荐信任度的方法,从而解决了不诚实反馈的问题.反馈机制则利用基于行为分层信任模型给出的用户信任度的变化,实现了根据用户的行为动态调整他的角色.文中还设计了三组模型实验,分别验证新模型的特点、对网格中恶意实体行为的抑制情况,从不同的角度对模型进行了实验,对基于行为的分层信任模型对行为的敏感性、收敛性、有效性及合理性加以了证明.     

基于调整学习的聚类算法

调整学习是一种逐步求精的近似学习方法,是提高局部搜索解质量的重要途径之一.该方法调用调整算子填平局部最优解陷阱,构造一系列不同粒度的搜索空间,降低局部最优解对解质量的影响.利用调整学习的基本原理设计了聚类算法框架CAT_L,并给出了适合处理聚类问题的噪声平滑调整算子.实验对比了经典FCM算法与FCM-CAT_L(以FCM算法作为CAT_L框架的聚类算子)算法的聚类质量.实验结果表明,调整学习方法对提高聚类质量是有效的.     

基于非完全信息博弈的网格资源分配模型

针对网格计算环境动态,异构和分布的特性以及网格资源分配中资源利用率低、效益不均等问题,结合微观经济学理论,建立了一种多赢家式的网格资源拍卖模型(muti-winners auction model,简称MWAM).将隐马尔可夫模型应用在网格用户t时刻出价状态预测方面,并结合分配算法计算出能够获得所需资源的概率;并且在原有资源分配机制的基础上,结合非完全信息纳什均衡理论设计了一种多赢家拍卖算法.从理论上证明了资源分配结束后系统收益最大,且本模型符合微观经济学中的激励相容性与个人理性准则.实验模拟在验证了隐马尔可夫预测的可行性的同时,又与几种具有代表性的算法相比较,从资源利用率、系统总收益等方面突显了本模型的优势.