遗传算法求解0/1背包问题的综述

背包问题是一种组合优化问题,有很多类型,如多维背包问题等,本文讨论的0/1背包问题是背包问题中最原始最基本的类型.遗传算法在求解背包问题上已经显示了巨大优势.本文分析了遗传算法求解0/1背包问题存在的主要问题,在总结分析近6年的相关文献基础上,提出了未来研究方向,为遗传算法求解0/1背包问题提供参考.     

背包问题的遗传算法求解

探讨利用遗传算法解决背包问题并设计新型的遗传算法，给出了背包问题的数学模型，建立了有效的约束条件。在引入一种新的具有自适应性的杂交概率和变异概率的基础上，提出了面向背包问题的遗传算法和一种构造染色体的新方法，提供了遗传算法的结构并讨论了遗传算法，给出了一个例子说明算法的收敛性和收敛效率，仿真说明了算法的有效性。     

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

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

求解背包问题的基因属性保留遗传算法

遗传算法是解决大规模背包问题的有效方法,在研究几种有效的遗传算法求解背包问题基础上,注意到遗传算法的进化代数对求解结果的影响大于群体规模,保持基因位数据的有效性,对进化效率有重大影响.提出了基因属性保留遗传算法(attribute gene-reserved genetic algorithm,AGGA),将每一位基因的属性差异,在不同代遗传中加以保留,结合精英保留方法,很好地解决了提前收敛、GA欺骗问题,从很少的群体出发,就可以达到好的结果,实证了AGGA对背包问题的高效性,得到好于参考文献的结果,并构造了150个物体的背包问题实例.     

利用遗传算法求解0/1背包问题

背包问题是著名的N-P难题.对此问题已有许多经典的求解方法,本文利用遗传算法的求解思想,对0/1背包问题进行了详细的分析,按照遗传算法的基本结构设计了编码,并在构造适应度函数时给出了两种不同的形式.本文通过仿真实验对这两种情况下的遗传算进行了比较,试验结果表明了幂函数适应度函数的遗传算法可得到更好的近似解.     

多维O-1背包问题的混合遗传算法

将贪婪法和遗传算法相结合，设计了一种价值密度，提出了一种求解多维0-1背包问题的混合遗传算法。经实例证明，该方法能较好地解决多维0-1背包问题并较简单遗传算法有较好的改善。     

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

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

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

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

基于遗传算法的多约束背包问题求解方案

采用混合遗传算法求解多约束背包问题.首先构建多约束背包问题的数学模型,然后采用多维实数编码方式的遗传算法,结合附带染色体库技术、局部启发式算子和扰动算子对问题进行求解,并给出了一个实验实例.实验证明文中采用这种混合遗传优化算法解决多约束背包问题切实可行,有较高的搜索效率.     

解0-1背包问题的遗传算法及其改进

遗传算法是一种基于自然选择和遗传机制的搜索算法.讨论了用其解决著名的0-1背包问题,尝试混合使用一点杂交与多点杂交以及将传统的算法与遗传算法相结合的方法,对经典遗传算法进行改进,并在实验中获得了对于问题的更佳近似解.     

基于遗传算法求解NPC问题的研究

首先建立了0-1KP问题和3-SAT问题的数学模型;然后分别基于遗传算法（GA）与贪心策略相结合给出了一种求解0-1KP的有效算法,基于GA与局部搜索相结合给出了一种求解3-SAT问题的可行算法;最后通过对0-1KP实例和3-SAT实例的仿真计算验证了算法的可行性与有效性。     

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

遗传算法是一种基于自然选择和遗传机制的搜索算法．为解决著名的0-1背包问题，尝试混合使用一点杂交与多点杂交以及将传统的算法与遗传算法相结合的方法，对经典遗传算法进行改进，并在实验中获得了更佳近似解．     

求解0/1背包问题的自适应遗传退火算法

针对标准遗传算法易早熟收敛以及收敛速度慢的问题,提出一种自适应遗传退火算法用于解决高维约束优化问题.该算法采用轮盘赌和最优保存策略相结合的选择机制,并结合自适应交叉、变异概率,继而引入模拟退火算法,加快迭代后期算法的收敛速度.最后,比较了标准遗传算法和自适应遗传算法的实验结果,证明了自适应遗传退火算法在0/1背包应用中的高效性和精确性.     

Genetic Tabu Search for the Multi-Objective Knapsack Problem

We introduce a hybrid algorithm for the 0 - 1 multidimensional multi-objective knapsack problem.This algorithm, called GTS^MOKP, combines a genetic procedure and a tabu search operator. The algorithm is evaluated on 9 well-known benchmark instances and shows highly competitive results compared with two state-of-the-art algorithms.     

遗传退火进化算法在背包问题中的应用

从增强算法收敛性和减少参数依赖性的角度出发，提出应用遗传退火进化算法求解背包问题，遗传退火进化算法结合了遗传算法和模拟退火算法的优点，并有效地克服了各自的弱点，使其在优化性能、优化效率和可靠性方面具有明显的优越性．阐明了用该算法求解背包问题的具体实现过程，并通过实际数值计算和结果比较表明，该算法优于遗传算法和模拟退火算法．     

基于粒子群优化和两性二倍体的遗传算法及其应用

分别采用粒子群生物进化原理和自然界生物两性繁殖原理，对传统遗传算法进行改进，得到两种新型的遗传算法，并分别应用于背包问题和标准测试函数上。实验结果表明，这两种算法在全局搜索能力和收敛速度上比传统遗传算法都显示出了绝对的优越性。     

量子免疫算法及在0-1背包问题中的应用

将免疫算法的免疫算子思想引入到量子遗传算法中,提出了改进的算法:量子免疫算法。算法在保持量子遗传算法优点的同时,提高了算法的全局收敛性。并将此算法应用在0-1背包问题中,仿真结果表明,此改进算法具有良好的性能。     

多维0/1背包与遗传算法的网格调度研究

首先分析了网格调度的代价和成本,设计出一个将多目标、多约束的网格任务转换成单目标、单任务的0/1背包的网格调度模型.提出使用多维0/1背包与改进的二重结构编码的遗传算法的方法来求解网格最优调度,并通过编程实现其算法,经实验验证该算法优于基本的遗传算法.     

差异演化算法求解多维0-1背包问题

多维0-1背包问题是典型的NP难题,设计了一种求解它的差异演化算法,阐述了算法求解多维0-1背包问题的具体操作过程。用提出的算法对55个测试算例进行了仿真实验,得到了全部算例的最优解。测试结果表明了文中算法是求解多维0-1背包问题的一种有效方法。