改进的量子粒子群优化算法对多维多选择背包问题的求解

针对多维多选择背包问题无法在多项式时间内找到最优解,且由于其强约束限制条件,在求解过程中易陷入局部最优的问题,提出一种改进的量子粒子群优化算法对该问题进行求解.首先,在量子粒子移动过程中,通过判断其与下次迭代个体的位置关系确定其位置信息的可用性,通过该信息充分保留粒子位置的多样性;其次,提出一种新的位置扰动方法,避免种群陷入局部最优.最后,将该算法在标准数据集上进行测试,对算法的收敛速度和运行时间进行分析,测试结果表明,该算法在求解准确性上得到明显提升.

一种求解多维多选择背包问题的分布估计算法

针对多维多选择背包问题(MMKP)局部难以优化的特点,提出将分布估计算法(EDA)应用于优化MMKP问题。为了提升EDA优化局部的能力,以构建待选物品价值权重因子的方式来改进EDA的初始模型和概率模型更新方法;并平衡了极值效应对算法寻优过程的影响,克服了传统EDA局部优化能力不强的缺陷.同时采用新的非可行解的修复机制,维护了机器学习法对概率模型的促进作用,提高了改进算法的全局优化能力。实验结果表明,该算法能够有效地优化MMKP问题,其性能高于传统的优化算法。

基于核算法解决多维多选择背包问题

针对目前尚无多维多选择背包问题(MMKP)高效核算法的现状,提出用多种方法来构造处理这种类型背包的核。首先论述了如何在一般背包问题中获得核;接着根据事先设定的度量指标详细讨论了MMKP的基本解和两种排序关系,并利用三种备选方案得出MMKP的核,亦即子空间。第一种方案是基于观察数据E[lc]和E[d∞]比较小来得到核;第二种方案基于基本解和最优解的曼哈顿距离不算太远来实施;第三种方案是为所有元素定义一个全序并取第一组k元素作为核。比较了这三种方案的不同与优劣,结果表明:第一种方案比其他两种方案无论从定义子空间的精度和枚举时间平均值上,性能都更优越,利用该方案定义的核能高效解决MMKP。

广义多维多选择背包问题

在分析多维背包问题和多选择背包问题的基础上,提出一种广义的多维多选择背包问题,给出了该问题的数学模型并改进传统的贪婪算法对其进行了求解。该算法以价值密度为准则,并对每个约束条件先后执行贪婪优化,从而得到问题的近似最优解。

基于资源预测的智能终端资源缓存算法

针对智能电视终端应用间资源竞争导致的系统性能下降问题,基于资源消耗预测,提出一种智能终端资源缓存算法。根据系统记录的各应用程序的资源消耗统计数据,应用Markov模型预测下一时间段可能出现的资源瓶颈和应用的资源状态,利用应用的资源状态动态调整应用权重,并以最小化应用切换时间为目标,将资源缓存问题转化为多维多选择背包问题,采用轻量级的启发式算法求解资源缓存问题。仿真实验结果表明,在智能终端中该算法对于资源消耗的预测精确度比其他算法提高5.4%,而应用响应时间缩短约45%。

基于资源缓存的应用快速切换技术

为了加快嵌入式智能终端多应用切换速度,提出了一种基于资源缓存的应用快速切换技术。设计了一种使用资源缓存代理机制的资源管理框架,缓存应用切换到后台运行时的资源状态,建立以最小化应用切换时间为目标的资源管理模型,并将该模型转化为多维多选择背包问题,为解决该问题分别提出基于穷举搜索和启发式方法的资源缓存算法。实验结果表明,基于穷举搜索的资源缓存算法复杂度虽高,但是可以求得应用切换时间问题的最优解;而与之相比,启发式的资源缓存算法可以在较短时间内求得次优解,更适合于嵌入式终端采用,以实现多应用间的快速切换。

基于核的MMKP问题算法研究

多维多选择背包问题(MMKP)是0-1背包问题的延伸,背包核已经被用来设计解决背包问题的高效算法。目的是研究如何获得一种背包核,并以此高效处理多维多选择背包问题。首先给出了一种方法确定MMKP的核,然后阐述了利用核精确解决MMKP问题的B&B算法,列出了具体的算法步骤。在分析了算法的存储复杂度后,将算法在各种实例上的运行效果与目前解决MMKP问题的常用算法的运行效果进行了比较,发现本文的算法性能优于以往任何算法。

分布式训练异构任务调度算法研究

分布式机器学习中的工作结点在训练过程中经常需要处理异构任务,但任务发布者可能无法根据有效的先验知识确定边缘服务器集群中哪些是处于训练状态的工作结点。针对边缘服务器集群无法同时满足训练性能与服务质量最大化的问题,对异构任务调度算法进行了研究。首先在集群资源约束下分析了分布式训练收敛性能的影响因素;其次建立了最大化训练性能的优化目标;最后转化为多维多选择背包问题进行求解。仿真结果表明,所提异构任务调度算法能够在保证服务质量的同时,最大化分布式训练性能。