求解多背包问题的混合遗传算法

针对多背包问题最优解的求解,设计了一种新的价值密度;在此基础上结合传统的贪心算法,提出了一种求解多背包问题的混合遗传算法。该算法采用整数编码,并采用轮盘赌选择方法,对背包资源利用不足的可行解进行修正处理,对不可行解进行修复处理。并在大量的数值实验的基础上,将该方法与传统方法及简单遗传算法进行比较,实验结果表明,该混合遗传算法提高了问题求解的速度和精度,有一定的优越性。     

格雷码混合遗传算法求解0-1背包问题

给出0-1背包问题的数学模型,修改传统二进制编码为格雷码混合遗传算法,使用贪心算法来解决约束问题,对每个个体使用价值密度来衡量,提高了算法搜索效率,同时使用精英保留机制来加速算法收敛的速度。最后通过数值实验证明了算法的有效性。     

求解0-1背包问题的改进混合遗传算法

针对一种混合遗传算法所采用的贪心变换法的不足,给出了一种改进的贪心修正法;并基于稳态复制的策略,对遗传算法的选择操作进行改进,给出了随机选择操作。在此基础上,提出了一种改进的混合遗传算法,并将新算法用于解决大规模的0-1背包问题,通过实例将新算法与 HGA 算法进行实验对比分析,并研究了变异概率对新算法性能的影响。实验结果表明新算法收敛速度快,寻优能力强。     

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背包问题时找到最优解的机率,利用贪心优化策略对无效的蝙蝠个体进行优化,从而给出了贪心二进制蝙蝠算法（GBBA）。仿真计算结果表明,GBBA算法在寻优能力和收敛性能方面比已有的GMBA算法都更优越。     

基于贪心策略的遗传算法求解0-1背包问题

介绍了基于贪心思想的改进遗传算法,并用该算法解决0-1背包问题,试验数据证明该算法能有效求解0-1背包问题,而且比原遗传算法效率高.     

求解背包问题的演化算法

背包问题(Knapsack Problem, KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.本文对近十余年来利用EAs求解KP的研究情况进行一个较为详细的总结,它一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面为今后进一步利用最新提出的EAs求解KP问题提供一个可借鉴的思路.     

混合差异演化算法求解多维背包问题

提出了一种求解多维0-1背包问题的混合差异演化算法,算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品的贪婪算法和基于二进制编码的差异演化算法。对10个测试算例进行了仿真试验,结果表明文章提出的算法可以快速找到这些测试算例的最优解,是求解多维背包问题的一种有效方法。     

求解0-1背包问题的融合贪心策略的回溯算法

0-1背包问题作为经典的NP完全问题一直得到广泛的关注和研究.研究发现,经典回溯算法在解决0-1背包问题时的算法时间复杂度较高,尤其是在物品数量较多时,短时间内不能得到问题的解,导致算法的适用性较差.虽然经典贪心算法和现阶段涌现出的大量新型算法能够极大地缩减算法的运行时间,但普遍是以牺牲算法的准确性为代价的,不能保证可...     

0-1背包问题贪婪算法应用研究

结合生活中顾客中奖后奖品的选择问题,给出0-1背包问题的数学模型,介绍基于0-1背包问题的的贪婪算法,使用这种算法解决奖品选择问题,最后在viusal c 6.0下编程实现.     

求解多维0-1背包问题的一种改进的遗传算法

针对多维0-1背包问题,通过应用贪心法和二分搜索法的思想,本文提出了一种新的杂交算子——中值杂交,并且基于此算子提出了求解多维0-1背包问题的一种改进的遗传算法。最后本文通过一系列数值实验,把改进算法与传统的遗传算法以及其他最新的遗传算法进行比较,经过对求得近似解的精度及计算所需时间两方面的对比,验证了其有效性。     

求解多约束0-1背包问题的遗传算法的改进

提出对基本遗传算法(Genetic Algorithm,GA)的改进策略,并将其应用于多约束0-1背包问题(Multi-constrained 0-1Knapsack Problems,MKP)的求解。改进策略主要有:将线性规划松弛法求得的MKP的解作为初始解,另外为了避免种群多样化的丧失,将复杂的修复操作和局部优化操作应用于每一个最近产生的解。最后,对大规模测试数据的标准集进行实验,并将该算法与先前的方法进行比较,结果表明新的遗传算法在大多数时间能够更快速地收敛到较优解。     

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

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

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

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

求解折扣{0-1}背包问题的新遗传算法

折扣{0-1}背包问题（Discounted {0-1} Knapsack Problem,D{0-1}KP）是比0-1背包还要难以求解的NP-hard问题。提出了一种求解D{0-1}KP的新遗传算法GADKP。GADKP针对D{0-1}KP问题本身结构特征,借鉴启发式搜索思想设计了3种有效的交叉算子和1种变异算子。4种算子的操作都能够保证进化过程中解的可行性;3种交叉算子从3个不同的角度提高算法的搜索能力;变异算子采用逐层贪心机制提高个体的局部开发能力。通过4组共40个D{0-1}KP实例测试,和已有的求解D{0-1}KP的遗传算法相比,GADKP求解精度更高,是一种新颖有效的求解D{0-1}KP的方法。