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

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

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

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

基于核的MMKP问题算法研究

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

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

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