基于蚁群算法的多维0-1背包问题的研究

系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种求解多维0-1背包问题的算法——多维0-1背包问题蚁群算法。它大大减少了蚁群算法的搜索时间,有效改善了蚁群算法易于过早地收敛于非最优解的缺陷。仿真实验取得了较好的结果。     

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

针对传统差异演化算法(DE)无法求解采用二进制编码问题的缺点,通过采用新的变异方法,提出了一种用于求解0-1背包问题的二进制差异演化算法,阐明了该算法求解背包问题的具体实现过程.通过多个0-1背包问题的仿真试验,表明了该算法在求解0-1背包问题时不仅能达到最优解,而且收敛速度快,同时也验证了算法在解决二进制编码问题上的可行性和有效性.     

遗传变异蝙蝠算法在0-1背包问题上的应用

0-1背包问题是经典组合优化NP难题。在蝙蝠算法的基础上结合遗传变异的思想,引入主动进化算子、无效蝙蝠和当前最优位置蝙蝠集聚的处理规则,提出了遗传变异蝙蝠算法,并将其用于求解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背包问题中的应用。生物免疫算法是基于人体免疫系统基本原理的一种新型仿生学算法,将它应用于求解0-1背包问题,对解决现实世界中的组合优化问题有很好的借鉴作用。     

用动态规划法求解0-1背包问题

0-1背包问题是算法分析中的著名问题,有重要的使用价值,是算法研究的热点。目前较成熟的常用算法有贪心算法、动态规划、回溯法、分枝-限界法等。本文主要通过动态规划原理来求解0-1背包问题。     

基于群体智能的0/1背包问题求解研究进展

0/1背包问题是运筹学中一个经典组合优化NP问题。在简要介绍0/1背包问题基础上,分析展望了0/1背包问题的应用前景。结合已有研究成果,总结并详细分析了蚁群算法、微粒群算法等群体智能算法在0/1背包问题求解方面具有的较好收敛速度、健壮性、稳定性、算法简单等优点。最后,针对群体智能算法在求解0/1背包问题过程中所出现的缺陷,提出了群体智能算法在0/1背包问题求解需要进一步解决的几个问题。     

差分进化变异策略rand/3/bin求解0-1背包问题

0-1背包问题是背包问题中的基础也是最为经典的一大分支,其组合优化模型被广泛的应用于社会生产生活的各个领域,对NP完全问题的求解有重要价值.传统的启发式算法如遗传算法、基本差分进化算法、粒子群算法,在解决相同0-1背包问题时,差分进化算法在解决离散型0-1背包问题时收敛更快,但存在早熟问题.论文从启发式算法角度出发,结合差分进化算法中变异策略的特点,提出一种新的变异策略rand/3/bin求解方法,与遗传算法、粒子群算法、采取两种变异策略的差分进化进行性能对比实验(实验测试数据已公开在Github),结果表明:该算法实现了相对于原有实验收敛更快和结果更优的结果,具有良好的应用价值.     

0-1背包问题及其算法分析

0-1背包问题是算法设计分析中的经典问题,本文主要通过对回溯法、动态规划、贪心算法和遗传算法的研究,分析这四种方法在求解0-1背包问题时的优缺点并进行了比较.     

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

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

一种求解多维0-1背包问题的拟人算法

在项目决策与规划,资源分配,货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了诸如模拟退火算法,遗传算法,蚁群算法及其它一些启发式算法等求解算法。该文提出了一种新的启发式求解算法。该算法使用了两个主要的思想策略,即依据物品单位容积价值的高低选择物品并对其进行标记的策略和拟人跳坑策略。用本文提出的算法,对55个测试算例进行了实算测试,得到了其中54个算例的最优解。测试结果表明,用该文提出的拟人算法求解多维0-1背包问题,计算结果的优度高,计算时间短,是求解此问题的有效算法。     

基于动态状态树的回溯算法

介绍了背包问题及0-1背包问题,阐述了回溯算法(算法设计的基本方法之一)和状态空间的概念,提出一个基于动态状态空间树的回溯算法.以0-1背包问题为例,说明动态树方法对求解线性规划问题等是非常有用的,且该算法所用时间少于静态状态空间树方法,有助于扩大回溯算法的应用.     

An improved monkey algorithm for a 0-1 knapsack problem

The 0-1 knapsack problem is a classic combinational optimization problem. However, many exiting algorithms have low precision and easily fall into local optimal solutions to solve the 0-1 knapsack problem. In order to overcome these problems, this paper proposes a binary version of the monkey algorithm where the greedy algorithm is used to strengthen the local search ability, the somersault process is modified to avoid falling into local optimal solutions, and the cooperation process is adopted to speed up the convergence rate of the algorithm. To validate the efficiency of the proposed algorithm, experiments are carried out with various data instances of 0-1 knapsack problems and the results are compared with those of five metaheuristic algorithms.     

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

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

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

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

基于交换策略的蚁群算法求解多维0-1背包问题

在项目决策与规划、资源分配、货物装载等工作中,提出了多维0-1背包问题,对这一问题,国内外学者提出了许多算法。本文推广了文献[7]中求解单维0-1背包问题的蚁群算法,并从结合2-opt等局部优化的蚁群算法求解旅行商问题中得到启示：通过交换策略可以加快算法的收敛速度和获取更高质量的解,因此提出了基于交换策略的蚁群算法。再把这种算法与AIAACA算法进行比较,实验结果显示该算法与AIAACA算法效果相当,用时更少,是求解多雏0-1背包问题的有效算法。     

求解0-1背包问题的烟花算法

为了克服现有方法在求解0-1背包问题时存在的缺陷,提出了一种改进的烟花算法.在给出0-1背包问题的数学模型后,利用Kent混沌映射对基本烟花算法的解初始化以使初始位置分布更加均匀,同时引入Sigmoid函数得到渐变的爆炸半径使得算法的求解精度与搜索速度达到某种平衡,用改进的烟花算法来对其进行求解.通过对典型测试函数和0-1背包问题的求解结果说明了所提出的改进烟花算法求解精度更高,性能更加稳定.