求解0-1背包问题的改进排挤遗传算法

提出了两种用于求解0-1背包问题的改进排挤遗传算法PFCGA和GCGA,PFCGA使用惩罚函数和排挤操作使算法能够比较稳定地求得最优解,GCGA把排挤遗传和贪婪算法相结合,对种群中非法染色体表示的不可行解进行修复使其变为可行解,对非优可行解进行修正使其尽量靠近最优解,GCGA在保证求解精度的前提下加快求解速度。通过仿真实验和比较分析结果表明,PFCGA和GCGA能够获得很高的求解精度和正确率,是求解0-1背包问题的有效算法。     

求解0-1整数规划问题的混沌遗传算法*

针对一类特殊的0-1整数规划求解问题提出一种混沌遗传算法。该算法采用幂函数载波技术提高混沌搜索的充分性与遍历性,以混沌搜索算法得出的优化个体作为遗传算法的新群体进行交叉、变异等操作,提高种群质量,同时增加种群多样性,改善遗传算法的早熟问题。该算法被用于解决片上网络映射A3MAP(architecture-aware analytic mapping) 0-1整数规划问题。实验仿真证明,该算法的收敛速度和解的精度均优于A3MAP-GA。     

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

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

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

遗传算法是一种基于自然选择和遗传机制的搜索算法。本文将其用于解决一个著名的NP完备问题——0- 1背包问题,并对经典遗传算法进行了改进。通过对贪婪算法进行了改进以产生初始种群,并在进行交叉和变异操作过程中引入了对无效个体的校正操作,从而较好地保持了种群的多样性和优良度。数值实验表明该算法具有较好的全局最优性。     

遗传算法求解背包问题

遗传算法属于改进式启发算法。实践证明,遗传算法作为现代最优化的手段,它应用于大规模、多峰多态函数、含离散变量等情况下的全局最优化问题是合适的,在求解速度和质量上远超过常规方法,因而是一种高速近似算法。此文介绍如何用遗传算法解决传统的背包问题。     

求解0-1背包问题的混沌二进制乌鸦算法

针对离散空间的最优化问题,提出了二进制乌鸦算法,并在初始解中利用Chebyshev映射产生两种混沌序列优化乌鸦的初始解,保证个体的初始位置在整个搜索空间均匀分布;然后,为快速有效地求解0-1背包问题,引入贪心修复与优化策略处理非正常编码个体,得到基于混沌理论的二进制乌鸦算法（chaotic binary crow search algorithm,CBCSA）。仿真实验表明,CBCSA具有良好的全局寻优能力和收敛速度,能快速求得最优解,且混沌序列的第一映射方式比第二映射方式性能更佳。     

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

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

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

背包问题是一个典型的NP完全问题。该文给出了背包问题基于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背包问题的混合贪婪遗传算法

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

一种新的求解0-1背包问题的混合算法

该文汲取了蚁群算法（ACA）和抗体免疫克隆算法（AICA）的优点,提出了一种求解0-1背包问题的混合型算法,该算法充分利用了前者的搜索能力和后者的种群多样性。仿真实验对算法的部分参数进行了分析,并与其他文献的算法进行比较,结果表明,该算法是一种具有较高性能的混合优化算法。     

求解0-1背包问题的量子蚁群算法

0-1背包问题是组合优化中经典的NP难题,在蚁群算法的基础上结合量子计算提出一种求解0-1背包问题的量子蚁群算法。算法采用量子比特表示信息素,用量子旋转门来更新信息素。大量数据实例的比较测试表明,算法可有效提高蚂蚁算法的性能,减少搜索时间,具有更好的全局寻优能力。     

一种求解0-1背包问题的改进遗传算法

针对传统遗传算法（SGA）容易“早熟”的不足,提出一种求解0-1背包问题（KP）的改进遗传算法。借鉴二重结构编码的解码处理方法设计了一种新解码方法,在保证解可行性的同时修正种群中无对应可行解的个体;采用模拟退火算法和改进的精英选择算子改进SGA。实例仿真结果验证了改进遗传算法在进化效率和最优解搜索能力上的优越性。     

求解0-1背包问题的二进制狮群算法

针对传统二进制群智能算法求解0-1背包问题易陷入局部最优、收敛速度慢的缺点,提出一种新的解决离散空间问题的二进制狮群算法BLSO。二进制狮群算法对狮王、母狮和幼狮的位置重新定义,引入反置运算、移动算子和学习算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化处理和充分利用,增强局部搜索能力,进一步提高收敛速度。对9个典型的0-1背包算例进行仿真实验,实验结果表明,该算法不仅可以有效求解0-1背包问题,而且还能够以较快的速度搜索到精度较高的次优解甚至全局最优解,具有较好的稳定性;同时,对高维背包问题的求解与参考算法相比,在寻优时间和精度上更具优势。