一种求解0-1背包问题的二进制修正和声搜索算法

针对0-1 背包问题, 提出一种二进制修正和声搜索算法. 该算法修正了即兴创作过程, 对参数PAR进行动态调整, 同时提出一种随机修复机制, 有效修复不可行的和声, 增强算法的局部搜索. 采用一种可行和声初始化方式, 保证初始和声都是可行的, 整个搜索过程完全采用0-1 二进制模式, 对14 个0-1 背包问题进行测试. 将所提出算法与其他算法进行比较, 结果验证了所提出算法的有效性.

     

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

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

改进二进制和声搜索算法求解多维背包问题

和声搜索（HS）是一种已广泛应用于连续优化问题的元启发式方法。针对典型的组合优化问题——多维背包问题（MKP）,提出一种改进二进制和声搜索（IBHS）算法。算法通过伯努利随机过程生成二进制群体,在候选和声生成算子中,引入动态自适应参数,通过算法参数的自适应调整来协调算法的全局搜索和局部搜索,并提出一种新的更有效的衡量商品多维加权价值密度的方法用于二进制个体修正和优化;引入精英局部搜索机制进行协同寻优,提高IBHS的收敛速度。通过求解10组不同规模的典型多维背包算例和与贪心二进制狮群优化（GBLSO）算法、改进的差分演化（MBDE）算法以及二进制修正和声（BMHS）算法的对比分析,实验结果表明,所提算法在求解MKP时有具有良好的收敛效率、较高的寻优精度和很好的鲁棒性。     

基于和声搜索算法求解组合优化问题

为了能够应用和声搜索算法（HSA）求解组合优化问题,基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA),并将BHSA用于求解著名的k-可满足性(k-SAT)问题和0-1背包问题,通过与粒子群优化（BPSO）和遗传算法（GA）的实例计算对比验证了新算法的可行性与有效性。     

浅析利用动态规划法求解0-1背包问题

0-1背包问题是一个NP完全问题,被广泛应用在货物装箱、物资分配与存储等各行各业。因此,对0-1背包问题的研究既具有伦理价值又具有实际意义。本文首先介绍了什么0-1背包问题,然后描述了该问题的数学模型,并总结了利用动态规划法求解0-1背包问题的过程。     

遗传变异蝙蝠算法在0-1背包问题上的应用

0-1背包问题是经典组合优化NP难题。在蝙蝠算法的基础上结合遗传变异的思想,引入主动进化算子、无效蝙蝠和当前最优位置蝙蝠集聚的处理规则,提出了遗传变异蝙蝠算法,并将其用于求解0-1背包问题。仿真结果表明：该算法在收敛速度和精度上优于基本蝙蝠算法,并且能够有效地求解0-1背包问题。     

基于蚁群算法的多维0-1背包问题的研究

系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种求解多维0-1背包问题的算法——多维0-1背包问题蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好的结果。     

解决0-1背包问题的遗传分布估计算法

0-1背包问题是典型的NP难问题,针对0-1背包问题提出分布估计算法（EDA）与遗传算法（GA）相结合的算法（E-GA）。该算法在每一次迭代中由二者共同产生种群,并行搜索,两种方法产生的个体数目动态变化,将EDA的全局搜索与GA的局部搜索能力、EDA的快速收敛性与GA的种群多样性结合,实现优势互补。通过三个背包问题算例进行算法验证,与以往文献相比,结果显示该算法所获最优值优于文献最优值,运行时间短且收敛速度快。     

DNA折纸术在0-1背包问题中的应用

DNA折纸术因其反应的可编程性、纳米可寻址性等优点被广泛地应用于DNA计算中。利用DNA折纸术和杂交链式反应构建0-1背包问题的计算模型。以四个变量的0-1背包问题为例,首先将九种发夹结构和一种分子信标锚定在DNA折纸基底上并加入足量的辅助链;其次通过加入不同的引发链可以触发不同路径上的杂交链式反应,并得到问题的所有可能解;最后,通过荧光信号的数量确定可行解,从而找到问题的最优解。该模型不受权重过大或过小的影响,在折纸基底上可等比例的缩放权重。用Visual DSD软件对该模型进行仿真,模型显示出良好的可行性。     

基于0-1背包问题的两种算法

0-1背包问题是计算机科学中一个经典问题,0-1背包问题是一个最优化问题。因其结构简单,可扩展性强,可作为其他问题的子问题,因此通过对其研究可以解决更为复杂的优化问题。本文概述了两种求解0-1背包问题的算法设计方法,并对两种算法进行了分析和比较。     

求解0-1背包问题的混沌二进制乌鸦算法

针对离散空间的最优化问题,提出了二进制乌鸦算法,并在初始解中利用Chebyshev映射产生两种混沌序列优化乌鸦的初始解,保证个体的初始位置在整个搜索空间均匀分布;然后,为快速有效地求解0-1背包问题,引入贪心修复与优化策略处理非正常编码个体,得到基于混沌理论的二进制乌鸦算法（chaotic binary crow search algorithm,CBCSA）。仿真实验表明,CBCSA具有良好的全局寻优能力和收敛速度,能快速求得最优解,且混沌序列的第一映射方式比第二映射方式性能更佳。     

一种用于求解0-1背包问题的动态伸缩算法

针对0-1背包这个非确定多项式（NP）完全难题,提出一种新的启发式搜索算法来解决0-1背包问题。算法采用多维实数编码,将物品按价值/重量比从大到小排序装包,通过用启发式策略选择交换背包内和背包外物品的位置,采用动态伸缩策略调整背包大小,选取种群中部分优秀解进入下一代继续进行优化。通过5个背包实例进行测试,实验结果表明该算法收敛速度快、求解精度高,并且具有良好的稳定性。     

求解0-1背包问题的一种新混合算法

用动态规划算法求解0-1背包问题的时空复杂度为O（nC）。这个空间复杂度在求解大规模问题上是不可接受的。从计算0-1背包问题最优值的递归方程出发,给出高效利用内存的动态规划算法。为了克服内存高效的动态规划算法带来的缺点,设计新混合算法求解0-1背包问题。该新混合算法的时间复杂度为O（nC）;它消除了回溯阶段,并且为求得放入背包的物品所使用的空间复杂度仅为O（「n/d?+C）,其中d为计算机字长。实验结果表明,混合算法的工作效率与理论分析相同。     

求解0-1背包问题的混合蝙蝠算法

针对基本蝙蝠算法易陷入局部最优、收敛速度慢等缺点,对其进行优化研究。基于0-1背包问题的具体特征,在基本蝙蝠算法原有概念和框架的基础上,引入遗传算法中的交叉机制以及反置算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化和充分利用,增强局部搜索能力,加快算法收敛速度,构建全新的混合蝙蝠算法。将混合蝙蝠算法应用于两组0-1背包算例,仿真实验结果优于自适应元胞粒子群算法、基本蝙蝠算法和贪心二进制蝙蝠算法。结果验证了该混合算法求解0-1背包问题的可行性和有效性。     

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

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

一种新的求解0-1背包问题的混合算法

该文汲取了蚁群算法（ACA）和抗体免疫克隆算法（AICA）的优点,提出了一种求解0-1背包问题的混合型算法,该算法充分利用了前者的搜索能力和后者的种群多样性。仿真实验对算法的部分参数进行了分析,并与其他文献的算法进行比较,结果表明,该算法是一种具有较高性能的混合优化算法。     

求解0-1背包问题的二进制蝙蝠算法

为了求解离散空间中的最优化问题,提出了一种二进制蝙蝠算法,并引入时变惯性因子来提高算法的全局收敛速度;在此基础上,为提高求解0-1背包问题时找到最优解的机率,利用贪心优化策略对无效的蝙蝠个体进行优化,从而给出了贪心二进制蝙蝠算法（GBBA）。仿真计算结果表明,GBBA算法在寻优能力和收敛性能方面比已有的GMBA算法都更优越。     

一种全新的0-1背包问题的优化方法

为了进一步优化难解背包问题,在传统理论基础上给出了一种基于动态预期效率的经济学模型,构造了一种全新的背包优化算法,并进行了单独仿真实验和对比实验仿真。实验表明,在同一类背包问题中,该算法优于贪心算法、回溯法、动态规划算法和分支限界算法;与萤火虫群算法对比,该算法较大程度地提高了收敛速度并节省了存储空间,收敛速度几乎是萤火虫群算法的10倍。最后,经过对20个背包问题的探究,验证了该算法的可行性,并确定了该算法的适应范围。