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

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

基于Visual c^＋＋ 的0-1背包问题的贪婪算法

背包问题是经典的NP组合优化问题之一,在管理中的资源分配、投资决策、装载问题等领域有着广泛的应用。文中给出0-1背包问题的数学模型,然后简单介绍了贪婪算法,并使用这这种算法解决0-1背包问题,通过在viusal c 6.0环境下对算法进行测试和分析,实验结果证实了所提出方法的有效性。     

一种改进的模拟退火算法求解0-1背包问题

从增强算法收敛性和减少参数依赖性的角度出发,提出应用改进的模拟退火算法求解0-1背包问题.对模拟退火算法有所改进,并有效地克服它的弱点,使其在优化性能,优化效率和可靠性方面有明显的优越性.阐明了用该算法求解0-1背包问题的具体实现过程,并通过实际数值计算和结果比较表明,该算法在求解0-1背包问题优于传统的模拟退火算法,并且得到更有效的近似解.     

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

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

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

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

离散正弦余弦算法求解大规模0-1背包问题

针对0-1背包问题的数学特征,设计了相应离散算法进行求解。算法在基本正弦余弦算法的框架内,首先采用实数编码进行个体初始化,并设计非线性指数递减函数根据迭代深度调节个体更新步长,借用贪婪修复算子对不可行解进行修复及优化。算法性能采用2组大规模的0-1背包问题进行测试,并通过与同类新兴算法的对比表明,本算法高效、简洁,不仅为0-1背包问题提供了高效率的解决方案,还拓展了正弦余弦算法的应用领域。     

0／1背包问题的动态状态树的回溯算法

本文给出了一个以动态状态空间树为基础的０／１背包问题的回溯算法。动态树方法对求解线性规划问题等是非常有用的，该算法所用时间比静态状态空间树方法要少。文中给出的Ｓｐａｒｋｓ算法经用Ｃ语言写成程度上机验证，思路正确。     

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

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

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

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

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

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

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

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

一类可分离的非线性0-1背包问题的分枝定界算法

构造出了一类可分离非线性0-1背包问题的分枝定界算法．分枝的过程是酱通的0-1变量分枝，用简单的取整启发式法确定更好的可行解；而在每个分枝结点处用线性松弛技术确定了它的子问题的一个线性规划松弛逼近。由此得到最优值的一个下界．数值结果表明所提出的算法是有效的．可以求解中等规模的问题．     

具有多父代重组的遗传算法解0-1背包问题

遗传算法的创始人最初是从自然界获取灵感的,但是后来的遗传算法的研究者也试图将生物界不存在的特征引入遗传算法,多父代重组(或称为N父代重组,N>2)就是其中的一种。有文献显示这种机制在解很多不同的问题时都能有较好的效果。本文用几种多父代重组方法(包括一种新的面向特定问题的方法)解0-1背包问题,结果显示多父代重组确实有较好的性能。     

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

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

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

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

基于区域分割的差分进化算法求解0-1背包问题

为了更有效地求解0-1背包问题,提出了基于区域分割的差分进化算法(PDE).为保证变异算子的封闭性,对传统差分进化算法(DE)的变异算子进行了修改.引入区域分割算法以后,解空间中一些没有希望的点被移除,缩小了最优解的搜索范围,增加了找到最优解的概率.将区域分割和贪婪算法相结合,用搜索到的最好解替换了种群中目标函数值最差的个体,保证了种群的多样性.数值实验表明:该算法比文献中的DE算法更稳健,全局搜索能力更强,能以更大的概率找到背包问题的最优解.     

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

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