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

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

基于遗传算法的背包问题求解

背包问题是计算机算法研究中NP完备类的一个困难问题,对这个问题国内外很多学者已经研究出了不少经典的方法,但是这些传统的优化方法存在一些缺点。本文介绍了近年来兴起的一种机器学习算法——遗传算法解决背包问题的基本思路,并通过实例计算证明了此方法的可行性和有效性。     

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

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

基于进化规划算法的背包问题求解研究

背包问题是一个具有较强应用价值的NP完全问题.如何设计求解此类问题的算法,则具有很强的实用价值和理论意义.目前已有很多的求解方法,但背包问题并没有完全解决.本文在启发式算法的理论基础上,改进了进化规划算法求解背包问题,此方法简单通用、易于操作.数值实验表明该方法具有较高的准确率,能较快的收敛到全局最优点.     

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

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

背包问题的遗传算法求解

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

基于遗传算法求解背包问题

本文对0/1规划的背包问题展开讨论,提出了一种基于遗传算法的问题求解方法,给出遗传算子,并对模型进行了实验数据的结果分析。     

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

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

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

0-1背包问题是计算机算法研究中NP完备类的一个困难问题,对这个问题国内外很多学者己经研究出了不少经典的方法,但是这些传统的优化法存在一些缺点。本文介绍了近年来兴起的一种演化算法—遗传算法解决背包问题的基本思路,井通过实例计算证明了此方法的可行性和有效性。     

一种求解0-1背包问题的整数混沌粒子群优化算法

针对0-1背包问题(0-1KP)的特点,以经典的速度-位移模型为基础整数编码各粒子,以混沌序列指导全局搜索,以排列的改变描述粒子的飞行.更新粒子的位置,进而提出用于求解0-1KP的整数混沌粒子群优化(ICPSO)算法.该算法由于背包容量的限制,融入到编码和粒子飞行中,因而不会在进化中产生无效的粒子,从而提高了算法的求解效率.实验结果表明:ICPSO算法简明、有效,较典型遗传算法,及粒子群算法具有更好的收敛性能和求解速度.     

遗传大洪水演算法求解多维背包问题

由于遗传算法具有较强的全局搜索能力,但在实际应用中容易产生早熟收敛现象,且进化后期搜索效率较低,而大洪水演算法是求解组合优化问题的独特算法,结合两者的优点,形成基于遗传算法的大洪水演算法（Genetic Great Deluge Algorithm,GGDA）,然后应用该混合算法求解不同规模的多维背包问题（Multidimensional Knapsack Problem,MKP）,求解结果表明提出的算法是简单有效的,优于标准遗传算法和大洪水演算法。     

动态规划求解0-1背包问题的教学探索

针对动态规划在0—1背包问题中求解最优值时的教学难度,结合教学过程和特点,对计算最优值的算法进行了改进,在与最优值递归公式保持一致的情况下简化了迭代过程,消除算法技巧,增加了算法的规范性和连贯性,收到了理想的教学效果。     

多维0-1背包问题的新型近似解法

运用属性论的转换程度函数,结合贪婪算法和核问题的研究思路提出了多维0-1背包问题的一种新型近似解法。该算法对生产实践中的四大类背包实例都有很快的收敛速度。特别是常规方法难以解决的最大子集和实例及强相关实例,算法能在一个很好的时间范围内给出近似度为99.7%的近似满意解甚至是最优解。     

0-1多项式背包问题的一种精确算法

提出了0-1多项式背包问题的一种新的精确算法. 该算法是一个基于拉格朗日松弛和对偶搜索的分枝定界方法. 用外逼近法求拉格朗日对偶问题得到上界,其中拉格朗日松弛问题通过转化为一个网络最大流问题来求解. 为了提高算法的效率,利用两种启发式方法求初始可行解,并用填充和交换的方法改进后得到初始下界; 并且在分枝定界前, 利用所得到的拉格朗日界, 先固定最优解中某些变量的值. 数值结果表明该算法是有效的.     

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

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

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

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

遗传算法控制参数选择的仿真研究

控制参数选择得是否合适是非常重要的,这些控制参数对遗传算法的影响是非常大的。这些参数主要包括:交叉概率(pc)、变异概率(pm)以及种群的大小等。本文首先简要介绍了遗传算法的工作机理,然后从理认上分析了控制参数对遗传算法运算的影响。最后通过软件仿真,验证了不同参数的选择对遗传算法运算结果的影响,并根据仿真结果对实际使用遗传算法时的控制参数选择提出了一定的选择范围,这在实际工程应用中有一定的实用价值。     

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

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

基于空间优化的三维装箱布局混合遗传算法

针对三维装箱问题使用了一种便于空间优化的二维链表结构表达三维矩形物体布局状态空间分解方法和利用混合遗传算法产生待装物体的顺序序列.二维链表结构可以表达空间相连结点之间的关系,易于空间结点的重组,达到更好的利用空间;也可减少产生好的待装物体顺序序列的搜索次数.结合混合遗传算法的搜索方法,能在合理的时间内找到问题的满意解.经过实验表明通过这两种方法的结合本算法能取得较好的较果.     

基于改进的模拟退火算法求解0／1背包问题

提出了一种改进的具有变异和倒位算子的模拟退火算法,并将其用于求解0／1背包问题,其性能较标准模拟退火算法和贪心算法都有很大的改善．通过大量的数值实验,证明了文中改进的模拟退火算法求解背包问题的有效性和实用性．