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

对于0-1背包问题设计一种价值密度,并在此基础上提出求解0-1背包问题的混合遗传算法.经大量数值实验比较该方法与传统方法及简单遗传算法,结果表明算法能有效求解0-1背包问题.     

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

介绍了0-1背包问题的基本贪心算法,借助于启发式算法在求解NP问题中的良好表现,设计了一种基于贪心修正策略的遗传算法。该算法结合了贪心算法和遗传算法各自的优点,利用贪心算法强化了初始最优解,通过对遗传算法的改进,使其在寻求最优的过程中更具有优越性。实际数值计算和结果比较表明,该算法能有效解决0-1背包问题。     

基于贪心算法的改进遗传算法解决背包问题

本文分析了简单遗传算法解决背包问题时候的一些缺陷,并通过适应度函数的计算以及选择方式的改进,给出了一种基于贪心算法的混合遗传算法以解决这些缺陷。实验表明,改进的遗传算法具有一定的优越性。     

差异演化算法求解多选择背包问题

多选择背包问题是典型的NP难题,文中建立了多选择背包问题的数学模型,设计了差异演化算法对其进行求解。通过对其它文献中实例的仿真试验和结果对比,表明了算法求解多选择背包问题的可行性和有效性。     

考虑主观需求的0-1背包问题及其求解算法

背包问题的约束条件通常由客观因素构成,如背包的额定容量,但在实际生活中,确定物品选择方案时,需要结合决策者的主观需求进行调整.基于此,建立考虑决策者主观需求的0-1背包问题模型,并设计一种混合贪心遗传算法(hybrid greedy genetic algorithm,HGGA)对该模型进行求解.针对此模型,首先考虑主观需求,再考虑客观约束,设计一种贪心算子,对初始种群进行优化与修正;然后,设计一种局部搜索算子,改进扰动位点的选择方式,实现对局部最优解的扰动,达到跳出局部最优得到更优质解的目的;最后,在随机生成的9个算例上,分别与同类型的遗传算法进行对比实验.实验结果表明:混合贪心遗传算法在求解精度与算法鲁棒性上具有明显的优势.     

基于改进探路者算法求解0-1背包问题

为了有效地求解0-1背包问题,提出了改进探路者算法(IP FA).首先,对种群个体进行二进制编码,把连续问题变为离散问题,然后,使用探路者算法进行寻优,并结合贪心修复与优化算法(greedy repair and optimization algorithm,GROA)修复不可行解和对解进行优化,通过变异策略来增加种群...     

改进贪心算法求解扩展简化折扣{0-1}背包问题

扩展简化折扣{0-1}背包问题(ESD{0-1}KP)是折扣{0-1}背包问题(D{0-1}KP)的拓展.ESD{0-1}KP增加了D{0-1}KP中单个项集中的物品数量,导致其求解难度增加,并且现有贪心策略算子(GSOR)算法效果不理想.基于ESD{0-1}KP模型,在每个项集中增加一个价值为0,质量为0的虚拟物品,同时对ESD{0-1}KP模型中的约束进行松弛,从理论上证明了ESD{0-1}KP与多选择背包问题(MCKP)等价.结合改进帕累托算法(IPA),提出新的贪心策略算子(NGSOR).NGSOR首先将同一项集多个物品的选择情况通过在项集内增加物品来表示,按从价值密度从高到低顺序选择物品,若被选择物品的价值比物品所在项集已选择物品的价值更大,则对该项集进行迭代.仿真实验结果表明：NGSOR相比于GSOR,求解精度平均提升24.56%,求解速度平均提升44.95%.     

用贪心算法求解删数问题

贪心算法作为解决问题的一类重要方法,因其直观、高效的特点而受到重视。如果某一类实际问题,能够具有最优予结构和贪心选择性质,那么它就可以通过一系列局部最优选择来获得整体最优解。本文首先对删数问题进行了分析,然后给出了该问题的贪心解法。最后对所提出算法的时间复杂度进行了分析。     

多选择背包问题的快速求解算法

背包问题属于组合优化中的经典问题,它有许多重要的变形,其中以多选择背包问题最为复杂.为更快地求解多选择背包问题,文中首先对该问题进行了理论分析,然后基于动态规划提出了一种新的求解算法,并对一个复杂的案例进行了测试.结果表明,这种新算法比遗传算法快9.4倍,比传统的0-1整数规划求解法快78倍.通过对数学模型的改进可大大降低问题的规模.更重要的是,所用方法可避免求解任何线性规划问题.     

基于人类进化算法的背包问题求解方法

背包问题是计算机算法中的一个NP完备类困难问题,使用传统的优化方法在求解较大规模的背包问题时,都存在计算量大、迭代时间长的缺陷．人类进化算法是模拟人类进化机理而建立的一种智能优化算法,本文阐述了人类进化算法的基本原理和实现方法．为提高背包问题的求解速度和精度,将人类进化算法应用于背包问题的求解,演示了算法的工作过程．试验结果表明,使用该方法求解背包问题是完全可行的和有效的,与众多优化算法相比,人类进化算法具有更高的求解效率．     

最优顶点覆盖的贪心边近似算法

提出了一种新的贪心边近似算法,能保证性能比不大于2的同时比传统的选任意边算法有更优的解,在可验证（能得到最优覆盖点数）时,统计数据表明贪心边算法非常有效,是一个集合了传统的任选一边近似算法和选择度数最大点的贪心算法两者优点的新算法.     

背包公钥密码系统的安全性与设计

本文讨论了一般背包公钥密码系统的位安全性问题，建立了这种系统中原文整体和某些特定位的安全性的等价关系。提出了一个新的基于背包问题的公钥系统，且不涉及任何背包分量超递增序列，与Merkle-Hellman系统有着本质的区别。此外，适当选择参数时，系统密度可达很高。因而，现有的Shamir的破译算法和Brickell解低密度背包问题的算法对该系统均无效。     

用于集装箱配装问题的Memetic算法

针对集装箱配装问题这一NP-hard问题,提出了用于求解背包式强异类货箱的集装箱配装问题的memetic算法,该算法采用了“WB＋DBL”的解码方式,并结合了常规遗传算法的广度搜索能力和局部搜索的深度搜索能力,能够有效地提高集装箱配装问题的求解质量。通过仿真实验,表明该算法是有效的。     

求解背包问题的一种改进粒子群优化算法

针对0—1背包问题,提出了一种改进的粒子群优化算法。在物品规模增大时,该算法能够有效寻找全局最优解,提高背包的空间利用率,降低背包的空置率。通过仿真实验表明,改进的粒子群优化算法在背包问题求解中具有更好的收敛性和稳定性。     

0-1背包问题的非线性降维近似算法

求解0-1背包问题的精确算法不能在较短时间内求解大规模0-1背包问题,使其实用性受到限制.针对该问题,给出求解0-1背包问题的非线性降维算法,并进行了数值实验,验证了算法的有效性.该算法属于近似算法,相对其他一些近似算法,计算结果更为精确.     

混合粒子群算法求解多维背包问题

提出了一种求解多维0-1背包问题的混合粒子群算法,算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品的贪婪策略和基于二进制编码的粒子群算法.用提出的算法,对55个测试算例进行了测试,得到了全部算例的最优解.测试结果表明,提出的混合粒子群算法求解多维0-1背包问题,计算结果的优度高,时间短,是求解此问题的有效算法.     

基于遗传算法求解0—1背包问题的算法探讨

0-1背包问题是一类典型的组合优化问题,并且是NP完全问题,具有重要的研究意义.介绍了贪婪算法和基本遗传算法求解背包问题的设计思想,提出了基于贪婪算法的混合遗传算法求解0-1背包问题.实验结果表明改进的遗传算法有更好的近似解.     

有序组合树法求解0-1背包问题初探

以0-1背包问题为研究对象,建立数学模型,采用有序组合树法对中小规模的背包问题进行求解.与传统的贪婪算法相比,该算法更容易找到最优解.并通过实例说明该算法对解决中小规模的0-1背包问题是行之有效的.     

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

针对基本遗传算法在求解大规模问题时，收敛速度缓慢、容易早熟的现象，借鉴生物区域性进化的原理，设计了一种基于星型迁移策略的并行混合遗传算法（Parallel Hybrid Genetic Algorithm，简称PHGA）．该算法采用高效的超贪心算子进行解码，使遗传进化过程从多个平均适应度较高的文明群体开始进化，并采用定期将各群体的最优个体输出给其他群体，使得最优个体共享，促进所有群体共同进化的共产主义迁移策略．在PVM环境下，对背包问题进行求解的实验，已取得超线性的加速比，并改进了解质量．     

有限期任务安排算法的改进

优先策略(即贪心算法),通过一系列选择来得到问题的一个最优解,它所做的每一个选择都是当前状态下某种意义上的最佳选择."有限期任务安排问题" 是可以用优先策略求解的一个很好例子.本文从避免移动操作的角度出发,并充分利用历史数据,提出了对传统的基于优先策略解决"有限期任务安排问题"的算法的改进策略,从而大大提高了算法性能,并通过大量实验数据验证了改进算法的有效性.