刘梦佳, 向凤红, 郭宁, 毛剑琳[1]2017年在《求解多维0/1背包问题的Memetic算法》文中提出根据多维0/1背包问题的特点,结合遗传算法和模拟退火算法的优点,设计了一种Memetic算法。该算法以基于模式替换的改进遗传算法作为全局搜素算法,采用模拟退火算法进行局部搜索。全局搜索算法引入了模式替换,使每代种群中的最好基因个体保存下来形成模式,引导种群搜索方向,提高搜索性能,然后进行选择、均匀交叉和变异操作,最后采用最大化修复策略,对不可行解进行修复,并对可行解进行修正。模拟退火算法以一定概率接受较差的解,从而避免陷入局部最优解。通过实验仿真和算法比较验证了Memetic算法的优越性和有效性。
乐天[2]2013年在《遗传算法求解0/1背包问题的综述》文中进行了进一步梳理背包问题是一种组合优化问题,有很多类型,如多维背包问题等,本文讨论的0/1背包问题是背包问题中最原始最基本的类型。遗传算法在求解背包问题上已经显示了巨大优势。本文分析了遗传算法求解0/1背包问题存在的主要问题,在总结分析近6年的相关文献基础上,提出了未来研究方向,为遗传算法求解0/1背包问题提供参考。
刘梦佳, 向凤红, 郭宁, 毛剑琳[3]2018年在《改进的遗传蚁群混合算法求解多维0/1背包问题》文中研究表明针对传统遗传蚁群混合算法求解精度低、收敛速度慢等缺陷,设计了一种改进的遗传蚁群混合算法,该算法选择部分优秀蚂蚁进行遗传算法寻优并更新全局信息素,其它蚂蚁采用蚁群算法寻优,并更新局部信息素。其中对传统遗传算法的交叉和变异操作进行了改进,并在蚁群算法的运行过程中引入概率和为u的轮盘赌方式以减少计算量、采用禁忌表交换策略以及信息素的混沌更新策略来增强种群多样性,避免陷入局部最优。实验结果表明,该算法在求解精度和收敛速度方面都有明显提高。
胡欣, 汪红星, 康立山[4]1999年在《求解多维0—1背包问题的混合遗传算法》文中研究说明文章研究一类典型的组合优化问题——多维０－１背包问题，提出了在简单遗传算法（ＳＧＡ）中加入局部搜索机制的混合遗传算法（ＨＧＡ）来求解该类问题，并在大量数值实验的基础上，将ＨＧＡ与传统的求解方法及ＳＧＡ进行了比较，实验的结果表明，该算法具有一定的优越性。
张欣, 王志刚, 夏慧明[5]2012年在《差异演化算法求解多维0—1背包问题》文中提出多维0—1背包问题是典型的NP难题。设计了一种求解它的差异演化算法,阐述了算法求解多维0—1背包问题的具体操作过程。用提出的算法对55个测试算例进行了仿真实验,得到了全部算例的最优解。测试结果表明了算法是求解多维0—1背包问题的一种有效方法。
常龙[6]2015年在《基于OpenCL的并行遗传算法在0/1背包问题的研究及实现》文中研究表明随着多核时代的到来,当前的并行计算机系统通常包括多核CPU、GPU和其他处理器,CPU和GPU的融合已经成为处理器发展的趋势。如何充分利用当前多核异构系统的并行计算能力已经成为一大研究热点。OpenCL计算技术的出现为异构计算资源的利用提供了技术支持,利用其对传统串行算法进行并行化改进将可能获得巨大的加速性。背包问题在实际生活中具有广泛的应用前景,0/1背包问题是背包问题中最基本的问题,而其它背包问题通常可以转换成0/1背包问题。遗传算法作为一种智能优化算法,具有简单、实用和较好的鲁棒性等优点,在求解背包问题上已经显示了巨大优势。遗传算法其天然的并行性十分符合OpenCL技术的并行模型,而传统遗传算法求解背包问题是通过对群体中个体逐个串行计算实现的,不能发挥遗传算法个体独立的并行优势。于是,本文就提出了一个利用OpenCL技术提高遗传算法运行效率来并行求解背包问题的研究课题。本文针对基于串行遗传算法实现的0/1背包问题的低效率进行了并行化加速,利用个体之间遗传操作先天独立的特点,对背包问题的计算过程进行并行分割,并基于OpenCL实现该并行算法,同时使用局部缓存等技术对计算过程进行了优化。对比并行实现和串行实现的实验结果表明,并行化后不仅算法运行效率得到很大提升,而且算法运行时间随计算规模呈线性增长。此外,本文还对比了分别使用GPU和CPU进行并行计算时,不同个体数和进化代数条件下的算法运行时间,分析了GPU和CPU在本问题实现上的优劣。
熊伟清, 魏平, 王小权[7]2006年在《蚁群算法求解多维0/1背包问题》文中研究说明0/1背包问题是一类典型的组合优化问题,并且是NP-完全的问题,研究它具有很重要的意义。本文针对多维0/1背包问题的特点,设计了二进制编码的有向图,使得蚁群算法可以应用到背包问题上。仿真结果表明,该蚁群算法在求解多维0/1背包问题上的是相当出色的。
钱乾, 程美英, 周鸣争, 卜天然[8]2013年在《人工生命Bug模型二元蚁群算法求解多0/1背包问题》文中指出从一维有趣的Bug人工生命模型出发,并对该模型进行扩展,将蚂蚁对信息素的大小进行选择的概率函数作为细胞的转换函数,对二元蚁群算法从人工生命的角度重新进行描述,同时引入更多的随机因素有效防止二元蚁群算法易陷入局部最优的缺陷,然后通过增加细胞状态集合元素数目的方式对Bug模型二元蚁群算法进行扩展,应用于多0/1背包问题的求解。仿真实验表明,运用文中算法不仅能快速有效地完成多0/1背包问题的求解过程,而且在一定程度上体现了计算的本质。
参考文献：
[1]. 求解多维0/1背包问题的Memetic算法[J]. 刘梦佳, 向凤红, 郭宁, 毛剑琳. 软件导刊. 2017
[2]. 遗传算法求解0/1背包问题的综述[J]. 乐天. 浙江海洋学院学报(自然科学版). 2013
[3]. 改进的遗传蚁群混合算法求解多维0/1背包问题[J]. 刘梦佳, 向凤红, 郭宁, 毛剑琳. 电子科技. 2018
[4]. 求解多维0—1背包问题的混合遗传算法[J]. 胡欣, 汪红星, 康立山. 计算机工程与应用. 1999
[5]. 差异演化算法求解多维0—1背包问题[J]. 张欣, 王志刚, 夏慧明. 科学技术与工程. 2012
[6]. 基于OpenCL的并行遗传算法在0/1背包问题的研究及实现[D]. 常龙. 昆明理工大学. 2015
[7]. 蚁群算法求解多维0/1背包问题[J]. 熊伟清, 魏平, 王小权. 计算机工程与科学. 2006
[8]. 人工生命Bug模型二元蚁群算法求解多0/1背包问题[J]. 钱乾, 程美英, 周鸣争, 卜天然. 计算机技术与发展. 2013