摘要:在免疫多目标优化算法的基础上,引入了分布估计算法(EDA)对进化种群进行建模采样的思想,提出了一种求解复杂多目标优化问题的混合优化算法HIAEDA(hybrid immune algorithm with EDA for multi-objectiveoptimization).HIAEDA 的进化过程混合了两种后代产生策略:一种是基于交叉变异的克隆选择算子,用于在父代种群周围进行局部搜索的同时开辟新的搜索区域;另一种是基于EDA 的模型采样算子,用于学习多目标优化问题决策变量之间的相关性,提高算法求解复杂多目标优化问题的能力.在分析两种算子搜索行为的基础上,讨论了两者在功能上的互补性,并利用有限马尔可夫链的性质证明了HIAEDA 算法的收敛性.对测试函数和实际工程问题的仿真实验结果表明,HIAEDA 与NSGAII 算法和基于EDA 的进化多目标优化算法RM-MEDA 相比,在收敛性和多样性方面均表现出明显优势,尤其是对于决策变量之间存在非线性关联的复杂多目标优化问题,优势更为突出.

摘要:为求出具有箱式约束的非线性全局优化问题所有的局部极小点,提出了一种基于Multistart 方法的新算法.结合目标函数在可行域内的总变差、下降率和凹凸性等信息,构造了一个刻划局部极小点分布的G-度量.将可行域剖分为若干个小区域,把初始点按G-度量值的比例分配在每块区域上,使得局部极小点密集的区域能够被分配较多的初始点进行搜索;给出了有效初始点的判断条件为了进一步减少局部优化算法的运行次数.针对G-度量计算量较大的问题,设计了相应的近似计算方法,降低了计算量.选择了4 个2 维~10 维具有大量局部极小点的测试函数进行求解,与Multisatart 和Minfinder 算法的实验结果进行对比,表明了该方法在收敛速度和搜索全部局部极小点上都有了较大的改进和提高.

摘要:超椭圆曲线密码体制与椭圆曲线密码体制相比,具有安全性高、密钥短的特点.标量乘计算是这两个密码体制中最为核心和重要的计算,其中,Montgomery 阶梯算法是计算标量乘的一种重要算法,且因为其可以抵抗简单的边带信道攻击,而被广泛研究和应用.近几年,椭圆曲线上的Montgomery 阶梯算法和相应的点运算公式一直在不断改进,但是在超椭圆曲线上,直接设计快速运算公式来提高Montgomery 阶梯算法的速度,却一直没有太大的进展.Lange 曾经探讨过这种快速公式存在的可能性,但却并没有得到一个实用、有效的计算公式.在特征为2 的域上,通过改进超椭圆曲线上的除子类加法公式来提高超椭圆曲线上的Montgomery 阶梯标量乘计算,提出了一种新的思路来改进多种坐标系下的加法公式.分析和仿真结果表明,在特征为2 的域上,新的运算公式的运行速度比之前的标准公式均有所提高.在某类常用曲线上,新的公式比之前的公式快了4%~8.3%.这说明,直接设计快速除子运算公式来提高Montgomery 阶梯算法的速度是可行的.同时,使用新的公式实现的Montgomery 阶梯算法可以抵抗简单边带信道攻击.

摘要:并行发生(may happen in parallel,简称MHP)分析计算并行程序中哪些语句可以并行执行,它是并行分析技术的重要组成部分.提出一种针对Java 程序的新颖的MHP分析算法.与已有算法相比,新算法抛弃了“子线程只会被父线程等待同步”的假设,以非耦合的方式分别处理start 同步和join 同步;新算法的处理逻辑虽然更加简单,但却更加完备;在计算控制信息时,新算法不必像已有算法那样通过内联构造全局的控制流图,显著地提高了算法的扩展性.新的MHP 算法被用来过滤静态数据竞争检测中虚假的数据竞争.在14 个Java 测试程序上的实验结果表明,新的MHP 算法计算控制信息的开销远远小于已有算法.

摘要:针对困扰词义消歧技术发展的知识匮乏问题,提出一种基于依存适配度的知识自动获取词义消歧方法.该方法充分利用依存句法分析技术的优势,首先对大规模语料进行依存句法分析,统计其中的依存元组信息构建依存知识库;然后对歧义词所在的句子进行依存句法分析,获得歧义词的依存约束集合;并根据WordNet 获得歧义词各个词义的各类词义代表词;最后,根据依存知识库,综合考虑词义代表词在依存约束集合中的依存适配度,选择正确的词义.该方法在SemEval 2007 的Task#7 粗粒度词义消歧任务上取得了74.53%的消歧正确率;在不使用任何人工标注语料的无监督和基于知识库的同类方法中,取得了最佳的消歧效果.

摘要:针对回归问题中存在采集数据不完整而导致预测性能降低的情况,根据支撑向量回归机(support vectorregression,简称SVR)等价于中心约束最小包含球(center-constrained minimum enclosing ball,简称CC-MEB)以及相似领域概率分布差异只与两域各自的最小包含球中心点位置有关的理论新结果,提出了针对大数据集的领域自适应核心集支撑向量回归机(adaptive-core vector regression,简称A-CVR).该算法利用源域CC-MEB 中心点对目标域CC-MEB 中心点进行校正,从而提高目标域的回归预测性能.实验结果表明,这种领域自适应算法可以弥补目标域缺失数据的不足,大大提高回归预测性能.

摘要:路标信息能够准确描述智能规划问题解空间的基本形态.提出由路标信息引导的分解规划方法,求解过程由路标计数启发式引导增强爬山算法向目标方向进行,根据路标的完成情况分段求出规划解.从全局范围上看,爬山过程逐渐实现更多的路标,路标计数启发式估值的降低引发规划任务的分解,当搜索过程遇到估值更低的状态时,提取一段爬山路径.如此反复执行“搜索-提取”过程,直至路标计数启发式的估值降低为0,各段爬山路径构成最终的规划解.采用最新国际通用的标准测试问题进行实验测试,结果表明:由路标计数启发式引导的分解规划方法能够更好地发挥路标信息的优势,实现了搜索范围的压缩,可更快地生成规划解.

摘要:噪声可学习性理论指出,有监督学习方法的性能会受到训练样本标记噪声的严重影响.然而,已有相关理论研究仅针对二类分类问题.致力于探究结构化学习问题受噪声影响的规律性.首先,注意到在结构化学习问题中,标注数据的噪声会在训练过程中被放大,使得训练过程中标记样本的噪声率高于标记样本的错误率.传统的噪声可学习性理论并未考虑结构化学习中的这一现象,从而低估了问题的复杂性.从结构化学习问题的噪声放大现象出发,提出了新的结构化学习问题的噪声可学习性理论.在此基础上,提出了有效训练数据规模的概念,这一指标可用于在实践中描述噪声学习问题的数据质量,并进一步分析了实际应用中的结构化学习模型在高噪声环境下向低阶模型回退的情况.实验结果证明了该理论的正确性及其在跨语言映射和协同训练方法中的应用价值和指导意义.

摘要:中心引力优化算法(central force optimization,简称CFO)是一种新型的基于天体动力学的多维搜索优化算法.该算法是一种确定性的优化算法,利用一组质子在万有引力作用下的运动,搜索目标函数在决策空间上的最优值.利用天体力学理论对该算法中质子运动方程进行了深入的研究,并利用天体力学中万有引力定理对质子运动方程进行了推导,建立起天体力学与CFO 算法之间的联系,通过天体力学中数学分析的方法对该算法中质子收敛性能进行了分析,最后,通过严格的数学推导证明出:无论初始时质子是何种分布,CFO 算法中所有的质子始终都会收敛于CFO 空间的确定最优解.作为测试效果,将CFO 算法与常见的BP 训练算法相结合,提出了CFO-BP 训练算法,优化前馈型人工神经网络的权值和结构.实验结果表明,采用CFO-BP 算法优化神经网络比其他常见优化算法有更好的收敛精度和收敛速度.

摘要:针对用户获取事件类信息的需求,在分析Web 新闻特征、事件多要素检索特点的基础上,研究了面向Web 新闻的事件多要素检索方法.首先,提出了面向Web 新闻的事件多要素检索模型;然后,使用BNF(Backus-Naur form)形式化定义了事件多要素查询项;最后,结合事件的动作要素、Web 新闻标题的重要性及事件项与约束项之间的距离,提出了事件查询项与文档相关性的计算方法.设置了16 个事件多要素查询项,基于Baidu 搜索引擎对P@n 指标进行了实验分析,所提方法得到的平均P@10 结果为0.87,平均P@20 结果为0.83.对16 个事件查询主题,通过人工标注语料的方法对F-measure 指标进行了实验分析,所提方法得到的平均F-measure 为0.74.结果表明,所提方法对事件多要素的检索较为有效.

摘要:借助cage 作为代理几何来处理高精度复杂模型,正成为计算机动画与几何造型中的一种重要方法.目前,已有的cage 生成算法尚缺乏普适性,很大程度上依赖于几何的表示和模型的复杂度.因此,提出一种基于可视外壳的cage 生成算法.通过逆向模拟计算机视觉领域可视外壳的生成过程获取cage,以实现cage 生成与几何表示和模型复杂度无关的目标.实验结果表明,该方法易于实现且效率高.

摘要:从图像中提取出头发区域,能够为头发分析、发型趋势预测等任务提供有利的线索.但是,头发的类内模式非常复杂,并且它与其他物体类间也常因光照复杂、表观特征相似等因素而难以分离.因此,头发分割是一个非常具有挑战性的问题.为了一定程度地解决这些问题,提出了一种由粗到细的头发分割方法.首先,该方法利用最新提出的利用视点进行主动分割(active segmentation with fixation,简称ASF)的方法,粗略提取头发分割的候选范围,保证头发区域的高召回率(准确率也许较低),并由此排除大部分与头发区域难以分离的背景区域;然后,利用特定于当前图像的头发类别信息,使用图割(graph cuts,简称GC)法在限定的范围内进行更加精细的分割.具体地,采用均值漂移(mean shift,简称MS)方法对输入图像进行区域的过分割;然后,利用贝叶斯方法选择一些可靠的、有较大概率属于头发或背景的“种子区域”,针对头发和背景的种子区域,采用支持向量机(support vector machine,简称SVM)在线学习头发和背景的分类器,并将其用于预测每个像素或区域属于头发或背景的概率;最后,将得到的概率用以GraphCuts 的初始化,求解得到最终的头发分割结果.实验结果表明,所提出的头发分割方法能够超越当前提出的头发分割方法.为了验证方法的可推广性,对其进行了一定扩展,并在马、汽车、飞机这3 个类别的公开数据库上作了评测,取得了较好的性能.

摘要:真实环境下数据集中广泛存在着标签噪声问题,数据集的弱标签性已严重阻碍了图像语义标注的实用化进程.针对弱标签数据集中的标签不准确、不完整和语义分布失衡现象,提出了一种适用于弱标签数据集的图像语义标注方法.首先,在视觉内容与标签语义的一致性约束、标签相关性约束和语义稀疏性约束下,通过直推式学习填充样本标签,构建样本的近似语义平衡邻域.鉴于邻域中存在噪声干扰,通过多标签语义嵌入的邻域最大边际学习获得距离测度和图像语义的一致性,使得近邻处于同一语义子空间.然后,以近邻为局部坐标基,通过邻域非负稀疏编码获得目标图像和近邻的部分相关性,并构建局部语义一致邻域.以邻域内的语义近邻为指导并结合语境相关信息,进行迭代式降噪与标签预测.实验结果表明了方法的有效性.

摘要:近些年,在计算机图形学与虚拟现实技术领域中,自然现象的模拟得到了广泛的关注和研究.如何快速且逼真地模拟自然现象,是此类研究的目的.以液体表面作为研究对象,总结了关于液体模拟近年来的部分研究成果;针对三维液体的复杂流体状态,提出了一种基于半拉格朗日的液体实时仿真方法,并对仿真结果进行了表面构建.该方法首先将Navier-Stokes 方程离散化,并通过求解构造的Poisson 方程得到每一时间步长的数值解,进而精确驱动粒子运动以构建真实液体表面;之后,利用液体表面追踪及Marching Cubes 表面重建,生成了真实的液体表面模型.实验结果表明,该仿真方法不但在运算过程中遵循经典的流体力学方程,从而保证了结果的真实性,并且运算速度快且能取得较好的视觉效果.在计算机游戏、电影制作以及医学等领域的仿真,均有广泛的应用前景.

摘要:在对程序进行并行化时,为了保证结果的正确性,并行编译器只能采取一种保守的策略,也就是,如果它不能确定两段代码在并行执行时是否会发生冲突,它就不允许这两段代码并行执行.虽然这种做法保证了正确性,但同时也限制了对并行性的开发.在这种背景下,许多推测多线程方法被提了出来,这些方法通过允许可能冲突的代码段并行执行来把握更多的并行机会,同时,通过从冲突中恢复来保证结果的正确性.然而,传统推测多线程方法所使用的“沿控制流将串行程序划分为多个线程”的做法并不适合不同数据结构上的操作在控制流中相互交错的情况,因为如果沿控制流将程序线性地划分为多个线程,则同一个数据结构上的操作将被分到不同的线程中,从而非常容易发生冲突.为了有效地对这些程序进行并行化,提出了一种基于数据结构的线程划分方法与执行模型.在这种方法中,程序中的对象被划分成多个组,同一组中对象上的操作被分派到同一个线程中去执行,从而降低了在同一个数据结构上发生冲突的可能性.

摘要:高功耗已成为制约高性能计算机发展的重要问题之一.近年来,大量研究关注于如何在满足系统功耗约束的条件下优化系统执行性能.然而,已有方法大都针对同构系统,未考虑异构处理器之间的功耗或速度差异,难以高效应用于基于加速器的异构系统.对当前异构并行系统执行模型进行了抽象,并提出了融合两级功耗控制机制的系统功耗管理框架,自顶向下依次为系统级功耗控制器和异构处理引擎功耗控制器.在异构处理引擎功耗控制中,针对类OpenMP 并行循环,首先分析了异构多处理器在满足功耗约束条件下达到性能最优的条件.基于该结果,给出了功耗受限的并行循环划分算法,该方法通过协调并行循环调度和动态电压频率调节技术以优化异构并行处理.在系统级功耗控制中,建立了异构处理引擎效能评估方法,以此作为功耗划分的依据,在兼顾并发应用公平性的同时,提高系统整体执行效能.最后,基于典型CPU-GPU 异构系统验证了方法的有效性.