0/1背包问题的量子算法

近年来针对各种问题提出了许多量子算法,这些量子算法都利用了量子态的可迭加性(Superposition)和纠缠性(Entan-glement),本文在量子环境下对0/1背包问题进行求解,介绍了量子算法的基本思想及相关概念。然后分析并给出求解0/1背包问题的量子算法,在量子物理环境下它能在多项式时间内求出所需要的解。这个量子算法可以推广解决其它NPC问题,如旅行售货员问题等。     

求解0/1背包问题的萤火虫算法

该文将萤火虫算法应用于求解小规模0/1背包问题,利用基本萤火虫算法的求解思想,对0/1背包问题进行分析,通过对物品数为10、25和50的背包问题进行了仿真实验,实验结果表明该算法在解决小规模0/1背包问题是可行的。     

求解0-1背包问题的量子蚁群算法

0-1背包问题是组合优化中经典的NP难题,在蚁群算法的基础上结合量子计算提出一种求解0-1背包问题的量子蚁群算法。算法采用量子比特表示信息素,用量子旋转门来更新信息素。大量数据实例的比较测试表明,算法可有效提高蚂蚁算法的性能,减少搜索时间,具有更好的全局寻优能力。     

基于群体智能的0/1背包问题求解研究进展

0/1背包问题是运筹学中一个经典组合优化NP问题。在简要介绍0/1背包问题基础上,分析展望了0/1背包问题的应用前景。结合已有研究成果,总结并详细分析了蚁群算法、微粒群算法等群体智能算法在0/1背包问题求解方面具有的较好收敛速度、健壮性、稳定性、算法简单等优点。最后,针对群体智能算法在求解0/1背包问题过程中所出现的缺陷,提出了群体智能算法在0/1背包问题求解需要进一步解决的几个问题。     

浅析0/1背包问题

0/1背包问题是个典型问题,其解法有很多,如回溯法、分枝限界法、动态规划法、递归策略等.本文以动态规划的方法(向前处理法)为例,详细解析了本问题,首先根据公式对问题一步步进行了推导,然后用图解法再次进行了研究,比较简单的解决了问题,并采用不同于资料上的方法,通过实例对其的可行性进行了验证,达到了预期的效果.     

浅析0/1背包问题

0/1背包问题是个典型问题,其解法有很多,如回溯法、分枝限界法、动态规划法、递归策略等。本文以动态规划的方法(向前处理法)为例,详细解析了本问题,首先根据公式对问题一步步进行了推导,然后用图解法再次进行了研究,比较简单的解决了问题,并采用不同于资料上的方法,通过实例对其的可行性进行了验证,达到了预期的效果。     

改进型遗传蚁群混合算法求解0/1背包问题

针对原有的遗传蚁群混合算法收敛速度慢、运行时间长等缺陷,提出了一种新混合算法,该算法从蚁群中选取部分优良个体采用遗传算法寻优,所选个体数目随迭代次数自适应变化,同时,对算法中的交叉、变异操作以及赋值等方面进行了一些改进。仿真结果表明,该算法在搜索能力、收敛速度以及程序运行时间方面都有明显的提高,由此证明了该算法的有效性。     

用基于贪婪算法的混合遗传算法求解0/1背包问题

为了克服传统优化方法的缺点,提高求解的速度和精度,将贪婪算法的思想融入基本遗传算法之中,形成了基于贪婪算法的混合遗传算法.介绍用该算法求解0/1背包问题的基本思路和方法,通过实例计算证明了该方法的可行性和有效性.     

0/1背包问题的贪心优化解法

介绍了0／1背包问题的基本贪心算法的解决策略，通过对贪心算法的改进和优化，找出0／1背包问题的最优解的很好近似。     

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

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

分配问题的计算机方法

分配问题是一个组合优化问题。传统计算机求解分配问题的方法中，既有枚举法、最小元素法、行（列）扫描法和损益分析等算法，也有如分枝限界法、匈牙利算法及其改进算法。本文在对这些计算机方法进行分析和仿真的基础上，将一个随机并行算法用在解决分配问题上，并且对各种方法的运行结果进行了比较。     

0/1背包问题竞争决策算法

竞争决策算法是在分析大自然生物世界特别是人类的各种竞争机制和决策原理的基础上,利用竞争造就优化、决策左右结果的特性来到达优化目的的新型寻优算法。在考虑0/1背包问题特点的基础上给出了用竞争决策算法求解0/1背包问题的算法,经过大量数据测试和验证,获得了较好的结果。     

基于0/1背包问题的讨论

简单介绍了贪婪算法、启发式贪婪算法和模拟退火算法(SAA),并使用这三种算法解决了0/1背包问题,给出了具体的算法描述和求解过程。对三种方法解决此问题,进行了仿真模拟和算法分析,指出了在不同规模下各种方法的优缺点,最后分析了解的质量和CPU时间。     

一类难解0/1背包问题的有效搜索算法

针对一类难解0/1背包问题,给出背包最大价值与物品集中元素的组合特性,在价值密度比贪心策略的基础上,采用组合交叉搜索策略设计一个快速搜索算法——ZHKnap。实验表明,在多项式时间复杂度内得到的解的质量优于目前算法的结果,证明最优解与元素的重量和价值参数的大小分布无关,而只与元素的重量及背包零头的组合相关。     

Tackling 0/1 knapsack problem with gene induction

We propose a gene induction approach for genetic algorithms. It is more robust compared to the traditional approach in genetic algorithms. The approach was applied to 0/1 knapsack problem. It found near optimal results in all the representative problem instances reported in the literature, while traditional approaches failed in a number of instances because of preponderance of infeasible individuals in the population. In combination with a heuristic mutation operator, our method provided better results for all the problem instances investigated.The authors are indebted to the anonymous referees for their valuable comments for improving the quality of presentation of the paper. The authors thank Michael J. Wax for making available the C++ source code for GA on the Internet.     

基于贪婪策略的0/1背包问题算法研究

对求解0/1背包问题的贪婪策略进行了详细的讨论.在分析价值密度贪婪算法缺陷的基础上,提出了重做贪婪选择的改进算法,并从理论和实验两个方面证明了其求解质量的提高.本文还详细分析了k阶优化算法,并证明了其近似比为k/(k 1),最后编程模拟了该算法的实现过程,并对结果进行了分析.     

一种改进的量子进化算法及其在乡村邮路问题的应用

针对基本量子进化算法易陷于局部最优解的缺陷,提出一种改进的量子进化算法(QEA)。结合乡村邮路问题,对算法进行了测试,结果表明,改进算法在全局寻优能力和种群多样性方面比基本量子进化算法有所改进,是求解乡村邮路问题的一种有效算法。