2014, 25(5):913-928. DOI: 10.13328/j.cnki.jos.004514
摘要:目前,大多数多目标进化算法采用为单目标优化所设计的重组算子.通过证明或实验分析了几个典型的单目标优化重组算子并不适合某些多目标优化问题.提出了基于分解技术和混合高斯模型的多目标优化算法(multiobjective evolutionary algorithm based on decomposition and mixture Gaussian models,简称MOEA/D-MG).该算法首先采用一个改进的混合高斯模型对群体建模并采样产生新个体,然后利用一个贪婪策略来更新群体.针对具有复杂Pareto前沿的多目标优化问题的测试结果表明,对给定的大多数测试题,该算法具有良好的效果.
2014, 25(5):929-938. DOI: 10.13328/j.cnki.jos.004547
摘要:随着二代测序技术的发展,产生了海量16S rRNA基因序列数据.如何有效地挖掘这些数据中隐藏的基因组学信息,是当前研究的热点与难点.序列聚类研究如何将来源于同一物种的序列合并在一起,其构成了物种多样性、结构及功能多样性研究的基础.针对454测序误差的来源特点,提出一种基于邻域种子序列的启发式序列聚类算法(NbHClust).实验结果表明,该算法具有良好的鲁棒性能.与传统启发式序列聚类算法相比,该算法能够降低操作分类单元(operational taxonomy unit,简称OTU)过估计问题,提高聚类精度,有效地进行操作分类单元计算.
刘佳升 , 张凤军 , 张镇嵩 , 陈辉 , 戴国忠 , 王宏安
2014, 25(5):939-952. DOI: 10.13328/j.cnki.jos.004418
摘要:现有多触点交互桌面系统通常只提供触点位置、形状等信息,不包括触点左右手归属信息.触点所属手及左右手手性信息的提供,对于多指手势识别、丰富双手交互技术,尤其是非对称双手交互技术具有重要意义.基于手的解剖结构特征,提出一种不需辅助硬件设备的触点左右手归属判定方法.首先,以手势设计的基本原则为指导,根据手的解剖结构特征,提出交互桌面手-臂系统三角形模型;其次,基于该三角形模型,给出多触点交互桌面同手触点聚类方法及左右手识别方法;然后,对MTDriver做扩展,实现了提供左右手信息的多触点跟踪工具箱,并提出了基于左右手信息的交互桌面交互技术;最后,评估结果表明,同手触点聚类方法及触点左右手手性识别方法均具有较高的正确率,而且在时间性能方面满足交互桌面交互实时性要求.
2014, 25(5):953-969. DOI: 10.13328/j.cnki.jos.004428
摘要:借鉴标杆管理理念,提出了一种基于标杆管理的优化算法(benchmarking-based optimization algorithm,简称BOA).根据标杆管理的核心价值观,设计了一套基于动态小生境的竞争性学习机制,针对常用的编码方案,设计出了具体可行的执行方法.种群内个体执行方向明确的主动学习式搜索,通过对标杆的模仿学习,能够快速搜索到解空间内的目标区域内,具有较好的智能性.此外,整个小生境种群系统通过自组织学习实现与环境的友好交互,较好地解决了保持种群的多样性的难题.分析了BOA算法与遗传算法等现代智能优化方法在搜索模式上的重要区别,并通过对比仿真实验,表明算法能够与环境进行稳定而友好的交互,表现出较强的鲁棒性,其搜索速度和寻优能力在实验中均有较好的表现.
2014, 25(5):970-983. DOI: 10.13328/j.cnki.jos.004441
摘要:以一种特殊的粗糙逻辑为研究对象,视全体赋值之集为通常乘积拓扑空间,通过利用赋值集上的Borel概率测度,提出了能融合粗糙逻辑与计量逻辑为一体的公式的Borel型概率粗糙真度理论,给出了公式概率粗糙真度的公理化定义,建立起了相应的概率真度表示定理.公式的概率粗糙真度理论可被看作粗糙逻辑中已有工作的计量化,也可看作计量逻辑学中真度理论的粗糙化.基于这一核心概念,进一步给出了粗糙逻辑中已有概念的程度化表示形式,如公式的粗糙度、精确度、公式之间的粗糙相似度等,并建立起了基于粗糙相似度的3种近似推理模式.该结果实现了粗糙逻辑与计量逻辑的和谐统一,为进一步基于粗糙真值的程度化推理搭建了一个可能的框架.
2014, 25(5):984-996. DOI: 10.13328/j.cnki.jos.004448
摘要:根据自适应离散差分进化(SaDDE)算法的提出过程,对算法策略选择问题进行了重点研究.策略池在SaDDE中起着重要作用,策略池的设计面临着3个问题,即:(1)怎样鉴别某个候选解产生策略(CSGS)是有效的还是无效的;(2)应该选择哪些CSGS组成策略池;(3)策略池的大小应该是多少.为了解决这些问题,提出了基于相对排列顺序的标度法(RPOSM)和基于RPOSM的层次分析法(RPOSM-AHP).主要采用某电子对抗(electronic countermeasure,简称ECM)仿真实验平台上的6个测试实例(T_INS)进行测试实验.首先,设计了144个不同的CSGS,为了获得这些CSGS在求解问题上的性能排序序列,做了144×6个独立的实验;然后,采用RPOSM和RPOSM-AHP计算这144个CSGS的最终优先级向量;接着,设计了16个具有不同策略池大小的算法,然后在同样的6个测试实例上测试这些算法的性能;最后,再一次采用RPOSM和RPOSM-AHP为SaDDE寻找到了合适的策略池大小.与其他类似算法的对比实验结果表明:在有限的评估次数(NFE)内,SaDDE比同类算法性能优越.
2014, 25(5):997-1013. DOI: 10.13328/j.cnki.jos.004452
摘要:半监督聚类旨在根据用户给出的必连和不连约束,把所有数据点划分到不同的簇中,从而获得更准确、更加符合用户要求的聚类结果.目前的半监督聚类算法大多数通过修改已有的聚类算法或者结合度规学习,使聚类结果与点对约束尽可能地保持一致,却很少考虑点对约束对周围无约束数据的显式影响程度.提出一种由在顶点上的低层随机游走和在组件上的高层随机游走两部分构成的双层随机游走半监督聚类算法,其中,低层随机游走主要负责计算选出的约束顶点对其他顶点的影响范围和影响程度,称为组件;高层随机游走则进一步将各个点对约束以自适应的强度在组件上进行约束传播,把它们在每个顶点上的影响综合在一个簇指示矩阵中.UCI数据集和大型真实数据集上的实验结果表明,双层随机游走半监督聚类算法比其他半监督聚类算法更准确,也比较高效.
2014, 25(5):1014-1024. DOI: 10.13328/j.cnki.jos.004500
摘要:由于必然模态词□的引入,谓词模态逻辑的公式在一个可能世界中的真假值可能依赖于其可达的可能世界.在谓词模态逻辑中存在个体跨可能世界相等问题.针对这一问题,Lewis提出了对应物理论,并且在对应物理论中用对应物关系来表示个体跨可能世界相等.但是,当一个对象具有一个以上的对应物时,谓词模态逻辑中的跨可能世界相等关系无法与对应物关系建立一一对应.通过限制谓词模态逻辑中全称量词∀的范围,给出了一种公式分层的谓词模态逻辑.它是谓词模态逻辑的一个子逻辑,并且其语言与谓词模态逻辑的语言是相同的.但其公式是分层定义的,使得∀可以出现在□的范围内,并且□不能出现在∀的范围内.由于任意形如∀x□φ(x)的表达式都不是该逻辑的公式,以量词开头的公式在一个可能世界w中的真假值只依赖于w,该逻辑避免了个体跨可能世界相等问题.给出了该逻辑的语言、语法和语义,并证明了该逻辑是可靠的和完备的.
胡旺 , Gary G. YEN , 张鑫
2014, 25(5):1025-1050. DOI: 10.13328/j.cnki.jos.004496
摘要:粒子群优化算法因形式简洁、收敛快速和参数调节机制灵活等优点,同时一次运行可得到多个解,且能逼近非凸或不连续的Pareto最优前端,因而被认为是求解多目标优化问题最具潜力的方法之一.但当粒子群优化算法从单目标问题扩展到多目标问题时,Pareto最优解集的存储与维护、全局和个体最优解的选择以及开发与开采的平衡等问题亦随之出现.通过目标空间变换方法,采用Pareto前端在被称为平行格坐标系统的新目标空间中的分布熵及差熵评估种群的多样性及进化状态,并以此为反馈信息来设计进化策略,使得算法能够兼顾近似Pareto前端的收敛性和多样性.同时,引入格占优和格距离密度的概念来评估Pareto最优解的个体环境适应度,以此建立外部档案更新方法和全局最优解选择机制,最终形成了基于Pareto熵的多目标粒子群优化算法.实验结果表明:在IGD性能指标上,与另外8种对等算法相比,该算法在由ZDT和DTLZ系列组成的12个多目标测试问题集中表现出了显著的性能优势.
2014, 25(5):1051-1060. DOI: 10.13328/j.cnki.jos.004492
摘要:研究了带有多折扣选项的滑雪租赁问题(ski-rental problem with multiple discount options,简称多折扣租赁问题)的离线和在线算法.多折扣租赁问题是经典的滑雪租赁问题的一个自然扩展,在现实生活中有着非常广泛的应用.在多折扣租赁问题中,除了租借一次装备和购买滑雪装备的选项以外,还存在多次租借装备的选项,这种多次租借可以得到折扣.一次租借次数越多,折扣就越大.规则价格子问题则是多折扣租赁问题中要求各选项的价格成倍数关系的一类子问题.证明了多折扣租赁问题的离线问题是NP难的,但对于规则价格子问题的离线问题,给出了一种线性时间算法.基于对离线问题的算法分析,给出了规则价格子问题的一个2倍竞争比的在线策略,同时证明了该问题的最优竞争比是2.基于规则价格子问题的在线策略,又给出了多折扣租赁问题的一个新的4倍竞争比的在线策略,该竞争比同样达到了最优.最后,通过对现实生活中的数据和随机数据进行实验,说明所给出的在线算法具有实际应用价值.
黄浩军 , 尹浩 , 陈和平 , 张俊宝 , 钱峰 , 宋伟
2014, 25(5):1061-1084. DOI: 10.13328/j.cnki.jos.004579
摘要:无线Ad Hoc网络(以下简称为Ad Hoc网络)能量感知地理路由协议深度影响网络性能,具有降低网络能量消耗、延长网络寿命等功效,受到越来越多的关注.系统阐述了Ad Hoc网络能量感知地理路由协议的研究进展.首先介绍了Ad Hoc网络地理路由,进而详细概述了能量感知地理路由协议形成的背景、度量指标、节点选择规则、研究意义及分类;然后,详细介绍了典型能量感知地理路由协议,并从多角度对其进行了归纳总结与比较;最后,阐述了能量感知地理路由协议研究存在的问题,指出了未来需要研究的内容,并在此基础上进行总结.
程红举 , 黄行波 , XIONG Naixue
2014, 25(5):1101-1112. DOI: 10.13328/j.cnki.jos.004455
摘要:在实际的通信环境中,由于噪声、报文冲突、信号衰减等因素的影响,无线传感器网络节点间信息交换往往是不可靠的.广播是无线传感器网络中广泛使用的操作,如何在不可靠通信环境下实现能量高效的广播算法,对提高整个无线传感器网络的性能具有重要的理论和应用价值.研究了不可靠通信环境下的无线传感器网络最小能耗广播问题,首先,分析了相邻节点之间最小能耗通信模型,并给出了保证节点接收概率不低于P*的最优发送半径;然后,讨论了多跳转发策略与节点位置信息之间的关系.在此基础上,提出了一种基于PSO的最小生成树广播算法,通过优化各节点的发送半径,在保证所有节点都能以不低于P*的概率接收到广播数据包的前提下,实现广播操作的总能耗最小.实验结果表明:所提出的广播算法不仅可使每一个节点的接收概率不小于P*,而且广播总能耗比改进后的BIP算法要小,具有较好的性能.
2014, 25(5):1113-1124. DOI: 10.13328/j.cnki.jos.004524
摘要:在无线认知网络的协作式频谱感知方案中,非授权用户(次要用户)将各自感知到的可用频谱信息转发给邻居节点,作为频谱分配的依据.而实际上,仅有部分数据影响着频谱分配的结果.无用信息的传递不仅产生了大量额外的通信开销,而且在频谱分配过程中浪费了计算资源.这种情况对于频谱资源稀缺的无线认知网络和能量有限的认知终端来说是无法接受的.因此,如何减少无用信息的传递是一个具有重大实际意义的问题.基于skyline查询处理,提出了多目标约束下skychannel查询处理方法,以减少冗余感知信息传递.其基本思想是:将数据空间划分为控制区域、被控区域和自由区域,按照信道的性能参数,将要查询的信道放入相应区域.传输时,直接忽略被控信道的信息而仅传输非被控信道的数据.在保证不影响频谱分配结果的前提下,可以大量降低网络开销,节约用户的计算资源.仿真结果显示,skychannel查询方法在节约查询时间、降低通信开销和计算开销等方面具有优势.
2014, 25(5):1125-1131. DOI: 10.13328/j.cnki.jos.004526
摘要:基于身份的数字签名方案最显著的特点是,只需要签名人的身份信息而无需签名人的证书来验证签名的有效性,这极大地简化了密钥管理.2006年,Paterson和Schuldt构造了标准模型下可证明安全的基于身份的数字签名方案,但计算效率不高.谷科等人提出了新型的改进方案来提高效率,并声称新方案在标准模型下可证明安全且比同类方案更高效.然而,新方案并不具备不可伪造性.给出了两种具体的攻击:敌手可以伪造用户的密钥或者敌手可以直接伪造任何消息的签名.进一步指出安全性证明中的缺陷,即,敌手的view与安全模拟成功的事件不独立.