一种求解背包问题的自适应算法

针对二表算法和动态二表算法求解背包问题,提出一个并行自适应算法,能用 个处理机、 的时间、 的空间求解背包问题 ,根据处理机的数目以及存储器的容量来选择参数,充分利用已有的硬件资源,以求得最快的求解速度。实验结果证明了该算法的有效性。     

一种新的背包加强算法

背包问题是著名的NP问题,因此它一度成为密码学界的研究热点。由最初的Merkle-Hellman背包算法到后来的Chor-Rivest背包算法,但很多算法都相继被破译。本文提出了一种加强背包算法,具有操作简易性和较强的安全性,可以运用于网络通信加密系统。     

一种求解背包问题的混合遗传微粒群算法

背包问题是计算科学理论中一个著名的NP-hard问题,也是典型的组合优化问题,在物流系统的库存分配和货物装载等方面都有非常重要的应用.采用借鉴遗传算法的编码、交叉和变异的遗传微粒群算法对背包问题进行求解.为了增强遗传微粒群算法的搜索性能,将基于自学习规则的启发式算法与遗传微粒群算法相结合得到混合遗传算法用于求解背包问题.对多个标准测试实例的仿真计算表明,该算法能有效求解KP问题.     

一种新的背包加强算法

背包问题是著名的NP问题,因此它一度成为密码学界的研究热点.由最初的Merkle-Hellman背包算法到后来的Chor-Rivest背包算法,但很多算法都相继被破译.本文提出了一种加强背包算法,具有操作简易性和较强的安全性,可以运用于网络通信加密系统.     

一种求解0-1背包问题的快速蚁群算法

0-1背包问题是典型的NP完全问题,且蚁群算法已成功地解决了许多组合优化的难题。因此,文中介绍一种基于蚁群算法求解0-1背包问题的算法,并对此算法进行优化,提出一种求解0-1背包问题的快速蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷,当物品数较大时,也取得了较好的求解质量。仿真实验取得了较好的结果。     

一种求解0-1背包问题的快速蚁群算法

0—1背包问题是典型的NP完全问题，且蚁群算法已成功地解决了许多组合优化的难题。因此，文中介绍一种基于蚁群算法求解0—1背包问题的算法，并对此算法进行优化，提出一种求解0—1背包问题的快速蚁群算法。它大大减少了蚁群算法的搜索时间，有效改善了蚁群算法易于过早地收敛于非最优解的缺陷，当物品数较大时，也取得了较好的求解质量。仿真实验取得了较好的结果。     

对一种新的背包加强算法的破解

自从Shamir提出攻击Ralph Merkle和Martin Hellman背包密码系统的算法以来，背包密码系统在算法设计上进行了改进，使其在改进后能抵挡Shamir攻击。但由于自身算法设计上可能存在缺陷，其中有一些改进后的背包密码系统会带来新的安全问题。本文是关于一篇题为《一种新的背包加强算法》（注：发表于《电脑与知识》第2004．29期）一文中提出的背包密码算法的破解算法。     

一种基于多背包的密码算法

本文介绍了背包问题和L3-格基约简算法并加以深刻的分析,在此基础上提出了一种基于多背包的加密算法,该算法大大加强了背包加密算法的安全性,可以有效的对抗L3-格基约简算法。     

一种新的求解0-1背包问题的自适应算法

提出了一种新的求解0-1背包问题的自适应算法——改进郭涛算法IGT。新算法实现了真正意义上的子空间搜索过程,引入了变维子空间,加入了变异算子,同时还与贪心算法相结合,并引入启发式修正算子,以保证算法的局部搜索能力和群体多样性。     

"背包"问题的一种高效精确收敛算法

在所有装包方案中，寻找一种最为精确的装包方案，使背包剩余体积最小，本文就该问题的快速收敛算法进行探讨。     

背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

免疫算法在背包问题中的应用

介绍了人体免疫系统的基本原理及其免疫算法在0-1背包问题中的应用。生物免疫算法是基于人体免疫系统基本原理的一种新型仿生学算法,将它应用于求解0-1背包问题,对解决现实世界中的组合优化问题有很好的借鉴作用。     

背包问题的知识进化算法

知识进化算法是在分析知识进化机制基础上提出的一种新型优化算法。该文根据0-1背包问题的特点,提出用于求该问题的知识进化算法方案,阐明算法的具体实现过程。通过对其他文献中仿真实例的计算和结果比较,表明应用该算法求解背包问题取得了良好的效果。该算法同样可以应用于其他组合优化问题。     

基于Matlab的0-1背包问题的动态规划方法求解

背包问题是经典的NP-hard组合优化问题之一,在经济管理、资源分配、投资决策、装载设计等领域有着重要的应用价值。文中用动态规划方法解决0-1背包问题,通过在Matlab6.5环境下对其算法进行测试和与其他方法对比分析,表明应用该方法可节省大量的计算时间,因而具有更高运行效率。     

Optimal Parallel Algorithm for the Knapsack Problem Without Memory Conflicts

Abstract The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on an EREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches.     

带权重的贪心萤火虫算法求解0-1背包问题

根据萤火虫算法的自身特点，将自适应权重、改进贪心算法、变异算子与基本萤火虫算法相结合，提出一种带权重的贪心萤火虫算法。通过加入自适应权重与变异算子，可以提高算法全局搜索能力，加入贪心算法在一定程度上可提高算法收敛速度，整体看，改进萤火虫算法提高了算法性能。通过仿真实验将改进后的算法与一些基本算法进行比较，实验结果表明，该算法在求解0-1背包问题时，无论在运算速度还是求解精度上都有明显改进。     

求解0/1背包问题的自适应元胞粒子群算法

对0/1背包问题进行研究,提出一种自适应元胞粒子群算法。在算法设计过程中,重新定义粒子位置和速度的更新方程,引入自适应因子,为有效粒子的主动进化和无效粒子的主动退化提供依据,新的编码方式使得新产生的粒子能够以更大的概率和更快的速度成为有效粒子,将元胞及其邻居引入到算法中保持种群的多样性,利用元胞的演化规则进行局部优化,避免算法陷入局部极值。对多组不同规模的背包问题进行仿真实验,结果表明,该算法不仅可以有效求解0/1背包问题,而且能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性。     

背包问题的基因学习优化算法

背包问题是典型的NP完全问题，针对背包问题，给出一种新的基于基因学习思想的求解算法。基因学习算法是在PBIL算法与自私基因算法基础上提出的一种适应性和搜索能力更强的优化算法。试验取得较好的效果，表明该算法加快收敛速度和提高全局寻优能力。     

一种求解动态背包问题的离散粒子群优化算法

动态背包问题(DKP)是一类经典的动态优化问题,可以用来描述许多实际的问题。迄今为止,针对动态背包问题的研究主要集中在遗传算法上,而对粒子群优化算法的研究较少。在离散粒子群优化模型的基础上,引入环境变化的探测以及环境变化后的响应机制,提出一种求解动态背包问题的离散粒子群优化算法(DSDPSO)。将该算法和现有经典的自适应原对偶遗传算法(APDGA)在两个动态背包问题上进行了对比实验,结果表明,DSDPSO算法在环境变化后能迅速地找到最优解并稳定下来,更适合于求解动态背包问题。