现有的机器学习算法不能对加密后的数据进行分析计算,而很多领域如医疗、金融等又要求数据保持机密性和安全性,这促进了加密机器学习的产生和发展。同态加密技术是解决这一问题的主要思路,它可以保证在不解密的情况下对密文进行计算,使得解密后的结果与对明文执行相同计算得到的结果相同。文中对同态加密在加密机器学习中的 相关 应用研究进行了综述,主要介绍了目前用同态加密实现加密机器学习的3种算法(加密神经网络、加密k-NN、加密决策树和完全随机森林),并从正确性、安全性、执行效率方面分析了方案设计,总结并对比了不同加密机器学习算法的构造思路,指出了同态加密用于加密机器学习的关键问题和进一步研究需要关注的内容,为同态加密和加密机器学习提供参考。

文中提出考虑时间因素的0-1背包调度问题这一具有NP难度的组合优化问题。给定n个物体(每个物体i的重量为w_i,连续加工时间为t_i),以及一个容量为S的背包,要求给出一个调度方案(物品的放入顺序和放入时间),使得任意时刻放入背包的物品总重量不超过背包容量,每个物体需放入背包连续加工时长t_i后才能取出,该问题是求使所有物体均加工完毕的时间尽可能短的调度方案。提出了3种求解算法:迭代动态规划算法、基于分枝限界的完备算法和遗传进化算法。迭代动态规划算法使用动态规划策略放置尽可能多的未加工物体到背包中,然后每次迭代取出加工完成的物品后再使用动态规划放入尽可能多的剩余未加工物品,直至所有物品被加工完成。基于分枝限界的完备算法通过定义上下界及剪枝操作,有效地降低了算法的计算复杂度。遗传进化算法将一个物品装填序列定义为个体,并定义了相应的适应度、选择、交叉与变异操作。在所设计的3组共计36个算例上的实验结果表明,迭代动态规划算法可以很快求出高质量的解,基于分枝限界的完备算法对小规模算例有很好的效果,遗传算法在处理几百个物体的算例时能在1500s内得到比动态规划算法更好的结果。

组合多个边缘云可以向用户提供更强大的云计算服务,在大量边缘云节点集合中选择适当的节点进行组合是一项具有挑战性的任务。该问题被建模成由云节点作为顶点、节点之间的链路作为边的资源拓扑图。云组合的构建过程等同于在该图中选择子图的过程,这是一个NP完全问题。子图的选择策略是决定云组合性能的重要因素,现有的minStar算法贪心地选择节点之间通信延迟最小的子图,将最优资源分配给当前用户,导致了局部最优和全局性能不良的问题。鉴于此,提出基于极大团的边缘云资源分配算法,提取图中的极大团并将其划分为若干互不重叠的规模较小的完全子图,以子图为单位构建资源块,以资源块为单位进行资源的分配。实验结果表明,与minStar算法相比,新算法将全局最大通信延迟降至原来的50%。

针对传统的基于统计模型的词性标注存在人工特征依赖的问题,提出一种有效的基于注意力长短时记忆网络的中文词性标注模型。该模型以基本的分布式词向量作为单元输入,利用双向长短时记忆网络提取丰富的词语上下文特征表示。同时在网络中加入注意力隐层,利用注意力机制为不同时刻的隐状态分配概率权重,使隐层更加关注重要特征,从而优化和提升隐层向量的质量。在解码过程中引入状态转移概率矩阵,以进一步提升标注准确率。在《人民日报》和中文宾州树库CTB5语料上的实验结果表明,该模型能够有效地进行中文词性标注,其准确率高于条件随机场等传统词性标注方法,与当前较好的词性标注模型也十分接近。

分布式模型检测是一种缓解状态空间爆炸的有效途径,已有文献提出了定性的分布式模型验证算法,然而定量LTL验证算法并行化问题还未得到有效解决。对此,展开两个方面的工作:提出一种新的动态系统状态空间划分方法;在定性LTL分布式验证算法的基础上给出了定量模型检测并行化验证算法。首先,将系统模型转化为可能的Kripke结构并选取一个并发分量,依据状态之间的关系完成系统状态的分割,使得关系紧密的状态尽可能分布在同一个计算节点上；其次,调整划分结果以使得计算负载平衡；然后,将划分结果与其他并发分量的状态进行叉乘,以完成系统状态空间的划分；最后,将待检测性质用自动机表示,在两者的乘积上,利用扩展的基于嵌套DFS的分布式验证算法完成系统的定量验证。

文中研究了具有NP难度的混合车辆路径问题(Mixed Capacitated General Routing Problem,MCGRP),其是在基本车辆路径问题(Vehicle Routing Problem,VRP)的基础上通过添加限载容量约束及弧上的用户需求而衍生的。给定一列车辆数不限的车队,使车辆从站点出发向用户提供服务,服务完用户需求后仍返回站点；规定每辆车的总载重不能超过其载重量,且每个需求只能被一辆车服务且仅服务一次。MCGRP旨在求解每辆车的服务路线,使得在满足以上约束条件的情况下所有车辆的旅行消耗之和最小。混合车辆路径问题具有较高的理论价值和实际应用价值,针对该问题提出了一种高效的混合进化算法。该算法采用基于5种邻域算符的变邻域禁忌搜索来提高解的质量,并通过一种基于路径的交叉算符来继承解的优异性,从而有效地加速算法的收敛。在一组共计23个经典算例上的实验结果表明,该混合进化算法在求解混合车辆路径问题时是非常高效的。

图G=(V,E)上的混合支配集D是由图G中的顶点和边组成的集合,因此对于图G中的任意一条边或一个顶点,若其不在D中,则其必须与D中某条边或某个顶点相邻。混合支配问题是在一个图中找到一个基数最小的混合支配集。混合支配问题是图顶点支配问题和边支配问题的混合,在实际生活中有着许多应用,最近在算法中也备受关注。混合支配问题在一般图上是NP完全的。带权混合支配问题则是混合支配问题的一个自然推广,其将图中的点和边以不同权重进行区分。令图中所有点的权重均为w_v,所有边的权重均为w_e,带权混合支配问题则要求寻找一个混合支配集使得其点和边的权重之和达到最小。尽管针对混合支配问题已存在一个简单2倍近似算法,但是对带权混合支配问题的近似算法的研究进展却非常缓慢。在点的权重不大于边的权重的情况下,文中给出了带权混合支配问题的一个3倍近似算法。

为提高城市道路建设时序决策的鲁棒性,提出了城市道路建设时序决策优化的双 层规划模型。模型假定出行需求在一定范围内扰动,上层规划是在有限资金的约束下寻求各建设阶段的系统总出行时间与系统总出行时间对出行需求的灵敏度之间的综合最小值,下层规划为各建设阶段的随机用户均衡配流。文中推导出了系统总出行时间对出行需求灵敏度的计算式,并给出了模型的求解算法。最后以一个测试路网为例,对基于系统总出行时间、基于灵敏度、基于系统总出行时间与灵敏度综合出行时间的决策优化模型进行了计算分析,结果显示3种决策优化模型均可寻求到各自目标最优的城市道路建设时序,但在需求不确定的情景下基于灵敏度、基于系统总出行时间与灵敏度综合出行时间的决策优化结果更具鲁棒性。

计算量较大的应用程序由于需要大量的能耗,因此在电池容量有限的移动设备上运行时十分受限。云计算迁移技术是保证此类应用程序在资源有限的设备上运行的主流方法。针对无线网络中应用程序任务图的调度和迁移问题,提出了一种快速高效的启发式算法。该算法将能够迁移到云端的任务都安排在云端完成这种策略作为初始解,通过逐次计算可迁移任务在移动端运行的能耗节省量,依次将节省量最大的任务迁移到移动端,并依据任务间的通讯时间及时更新各个任务的能耗节省量。为了寻找全局最优解,构造了适用于此问题的禁忌搜索算法,给出了相应的编码方法、禁忌表、邻域解以及算法终止准则。构造的禁忌搜索算法以提出的启发式解为初始解进行全局搜索,并实现对启发解的进一步优化。通过 实验 将所提方法与无迁移、随机迁移、饱和迁移3类算法进行对比,结果表明提出的启发式算法能够快速有效地给出能耗更小的解。例如,在宽度为10的任务图上,当深度为8时,无迁移、随机迁移与饱和迁移的能耗分别为5461、3357和2271能量单位,而给出的启发解对应的能耗仅为2111。在此基础上禁忌搜索算法又将其能耗降低到1942, 这进一步说明了提出的启发式算法能够产生高质量的近似解。

最小二乘对支持向量机(LSTSVM)是一种有效的分类技术。然而,该方法需计算点到平面的平方L2-范数距离,从而易受野值或噪声的影响。为了缓解此问题,提出了一种有效的鲁棒 LSTSVM方法,即基于L1-范数距离的LSTSVM(LSTSVML1D)。该方法由于使 用L1范数作为距离度量,因此不易受到野值或噪声数据的影响。此外,设计了一种有效的迭代算法,旨在求解目标问题,并从理论上证明了其收敛性。在人工数据集和UCI数据集上验证了LSTSVML1D 的有效性。

玉米螟是玉米种植中的主要虫害之一。为了解决人工识别的劳动强度大,且识别不够准确、及时的问题,文中提出了一种在自然场景下基于多生长时期模板匹配的不同生长时期亚洲玉米螟的识别方法。该方法首先对获取到的图像进行数学形态学预处理；其次利用直方图反向映射法和多模板图像得到总的概率图像；然后利用约束空间的大津法对二值图像进行轮廓提取,并根据周长和面积特征进行初步筛选；最后结合基准轮廓,利用Hu矩等特征选出符合亚洲玉米螟特征的轮廓,进而得出识别结果并以三角形标记。实验和理论分析证明,在复杂自然场景图像中,该方法不仅时效性强,而且具有很好的识别准确度,能够有效降低不同生长时期的玉米螟颜色变化带来的影响。