基于混合编码的差异演化算法解0-1背包问题*

针对典型的一类NP完全问题——背包问题,提出一种混合编码的差异演化求解方法。该方法基于差异演化算法框架,采用混合编码机制,每个决策变量均由一个实数和一个二进制数的组合表示。利用新定义的映射算子,构建混合编码的种群;增加边界约束处理算子,确保变异算子计算结果满足边界约束条件;利用新定义的丢弃算子对于不可行的装包策略进行修正。通过数值仿真实验,将该方法与遗传算法、二进制差异算法的计算结果比较分析,表明该算法求解背包问题的有效性与适用性。     

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

求解0-1背包问题（KP）的最优解的时候,传统遗传算法（GA）的局部求精能力不足而简单局部搜索算法的全局探索能力有限,针对上述问题,将这两个算法整合并提出了混合贪婪遗传算法（HGGA）。在GA全局搜索框架下增加局部搜索模块,并改进传统仅基于物品价值密度的修复算子,增加基于物品价值的贪婪混合选项,从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索,另一方面依靠GA的经典操作算子开拓全局搜索空间,从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试,结果表明在第一组15个测试用例中的12个上,HGGA能够百分百找到最优解,成功率达到80%;在第二组小规模数据集上,HGGA的性能明显好于其他同类GA和其他元启发算法;在第三组大规模数据集上,HGGA较其他元启发式算法具有更好的稳定性和高效性。     

用基于贪婪算法的混合遗传算法求解0/1背包问题

为了克服传统优化方法的缺点,提高求解的速度和精度,将贪婪算法的思想融入基本遗传算法之中,形成了基于贪婪算法的混合遗传算法.介绍用该算法求解0/1背包问题的基本思路和方法,通过实例计算证明了该方法的可行性和有效性.     

混合二进制差异演化算法解0-1背包问题

为了有效求解0-1背包问题,提出一种混合二进制差异演化算法.该算法基于差异演化算法框架,采用二进制编码,通过增加映射操作、S型变换操作和逆映射操作等3种新的操作,将差异演化算法从实数优化领域推广至离散优化领域,成功解决了差异演化算法直接求解离散优化问题时的计算不封闭问题.此外,在每次迭代求解时,利用贪婪变换法对违反约束条件的不可行解进行变换,使其成为可行解.不同规模的背包问题的数值实验结果表明了该算法的有效性与适用性.     

一种求解0-1背包问题的退火贪婪遗传算法

将贪婪算法和退火算法融入遗传算法,结合各自算法的优点形成了一种混合遗传算法。通过实验表明,运用此算法求解0-1背包问题,搜索能力明显优于基本遗传算法和贪婪算法。     

高维0-1背包问题的双种群角度调制DE算法

针对高维0-1背包问题,提出一种双种群新型DE算法。该算法采用双种群编码机制,其中一个为低维的实数编码种群,另一个为高维的二进制编码种群。借鉴通信领域的角度调制原理,通过低维种群中的个体,生成高维种群个体,实现将高维优化问题转换到低维空间进行优化求解。此外,新定义丢弃算子对演化过程中的不可行解实时进行修正。仿真实验结果表明了该算法求解高维0-1背包问题的有效性。     

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

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

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

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

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

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

混合差异演化算法在背包问题中的应用

提出了一种用于求解0-1背包问题的混合差异演化算法,详细阐述了该算法求解背包问题的具体操作过程。算法主要使用了两个思想策略,即启发式贪婪算法和基于二进制编码的差异演化算法。通过对其它文献中仿真实例的计算和结果对比,表明该算法对求解0-1背包问题的有效性,这对差异演化算法解决其它离散问题会有些帮助。     

求解大规模0-1背包问题的主动进化遗传算法

针对遗传算法求解大规模0-1背包问题中存在的不足,将定向变异机制引入到遗传算法中,提出了基于主动进化遗传算法的0-1背包问题求解算法。该算法利用概率编码方案对种子个体进行编码,每代种群中的个体通过对该代种子个体进行测度而产生,用于定向变异的诱变因子将参与种子个体的进化。实验结果表明,该算法具有较好的全局寻优能力和执行效率。     

0-1背包问题的一种新解法

针对目前求解0-1 背包问题算法的优缺点,开发了一种新的非递归算法。从计算0-1 背包问题最优值的递归方程出发,使用形式推导技术及序列抽象数据类型。在开发出循环不变式的同时,归纳得到用抽象程序设计语言Apla描述的非递归算法,并形式化证明了其正确性,在相关工具及部件库的支持下进一步得到C++程序。理论分析和实验结果表明,该算法的时间耗费受背包容量变化的影响很小,是一种有效的方案。     

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

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

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

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

0/1背包问题的贪心优化解法

介绍了0／1背包问题的基本贪心算法的解决策略，通过对贪心算法的改进和优化，找出0／1背包问题的最优解的很好近似。     

求解多维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背包问题的算法设计方法,并对两种算法进行了分析和比较。