导读:本文包含了二次背包问题论文开题报告文献综述及选题提纲参考文献，主要关键词:集合联盟背包问题,乌鸦算法,二次贪心修复与优化,莱维飞行
二次背包问题论文文献综述
刘雪静,贺毅朝,吴聪聪[1]（2018）在《求解集合联盟背包问题的二次贪心变异乌鸦算法》一文中研究指出针对确定性算法难以求解的集合联盟背包问题(Set-Union Knapsack Problem,SUKP),提出了二次贪心变异乌鸦算法(quadratic greedy mutated crow search algorithm,QGMCSA).首先结合SUKP问题模型对贪心策略进行改进,提出了处理其潜在解的二次贪心修复和优化策略;其次,为了扩大乌鸦个体的搜索范围,对乌鸦算法进行变异操作,在跟踪过程中引入莱维飞行;最后,利用叁类SUKP实例验证本文算法.仿真结果表明:QGMCSA是比二进制人工蜂群算法求解SUKP的结果更优的一个高效算法.(本文来源于《微电子学与计算机》期刊2018年11期）
温亚楠[2]（2018）在《L1范数正则化连续二次背包问题算法研究》一文中研究指出生活中,优化问题十分常见,力学中的优化更是无处不在.l_1范数正则化连续二次背包问题(CQKPL1)是一类重要的最优化问题,在结构分析、图像处理、压缩传感等领域都具有广泛的应用背景.尤其l_1范数正则化良好的稀疏性早已在计算机领域有较好的应用.对该问题理论和算法的研究早已备受国内外优化领域学者的关注,尤其在工程力学中,成为近年来研究的一个热点问题.本文在以上应用背景下,重点对求解_1l范数正则化连续二次背包问题的算法进行研究,通过数据实验比较几种算法的优劣.论文内容可概括如下:第1章首先介绍了二次背包问题的演化过程和发展历程,介绍了几种常用的求解可分离二次背包问题的算法.第2章在上述的研究背景下,提出了对CQKPL1算法进行研究.通过对模型的子问题及含参量问题的分析将该模型转化为求解方程根的问题并在此基础上提出叁种求解算法.第3章提出改进二分法,算法首先对断点进行分类,其次对包含断点的方程进行二分迭代搜索,同时加入加速迭代的步骤,加快算法收敛,搜索到最优解终止.第4章研究了改进割线法,算法包括两个步骤:步骤1(Bracketing Phase):目的是确定方程根的存在区间;步骤2(Secant Phase):在确定的区间内用割线法搜索方程的根.第5章对改进牛顿法进行讨论,首先引入了Moreau-Yosida正则化的概念将问题显示解进行重新研究,得到更多良好的解析性质.算法中利用改进的导数值得到迭代方向,利用Armijo线搜索产生迭代步长.最后,给出了改进牛顿法的全局收敛性定理,从理论上证明了算法的可行性.第6章对本文提出的叁个算法进行数据实验,将实验结果与当前商业中广泛使用的优化器Gurobi和Mosek的结果进行对比,验证本文算法的可行性和高效性.(本文来源于《沈阳航空航天大学》期刊2018-03-07）
刘梦佳,向凤红,毛剑琳,郭宁[3]（2018）在《求解多重二次背包问题的改进遗传算法》一文中研究指出多重二次背包问题,旨在将具有单独价值与协作价值的对象分配到一组容量有限的背包中,使总利润最大化,是一种具有广泛应用的NP难组合优化问题。针对该问题提出一种引入自适应模式替换和贪心算法思想的改进遗传算法(IGA)。首先对初始种群进行自适应模式替换,使每代种群中的最好基因个体保存下来形成模式,替换原种群中质量较差的个体,通过设计贪婪算子改进贪心思想对问题进行排序,然后进行扰动交叉操作和双重选择变异操作,最后采用最大化修复策略以保证解的可行性。标准算例仿真结果表明,相比传统算法,IGA具有较强的寻优能力。(本文来源于《软件导刊》期刊2018年01期）
秦进[4]（2017）在《二次多背包问题及其扩展问题的启发式算法研究》一文中研究指出二次多背包问题是经典0-1背包问题的一个扩展,在实际生活着中有着广泛的应用,例如当不同工人相互合作时有不同效率的情况下将工人分配到不同的任务、有预算约束下通信卫星的地球站选址问题以及铁路站点、货物运输终端、机场的选址问题等。与之相关的组成医疗小组问题来源于意大利米兰的某个医疗服务中心,该问题与二次多背包问题有着相似的结构,可以看成二次多背包问题的变种问题。这两个问题除了广泛的实际应用背景,也是一类十分复杂的组合优化问题,对于设计启发式算法求解十分有挑战。鉴于其实用性和理论挑战性,已经吸引了大批学者的目光,在文献中提出了各类求解这两个问题的启发式算法,但是仍然存在不足之处,还需要进一步的深入研究。本文拟在在已有的研究求解二次多背包问题以及组成医疗小组问题文献的基础上,提出更为高效的启发式算法并提升现有文献中的最好解,为求解这类问题提供更多的选择。首先,研究了使用混合了可行与不可行局部搜索的禁忌搜索算法求解二次多背包问题。该算法引入了不可行解搜索阶段,允许算法在搜索过程中搜索不可行解,能够为算法带来更多的自由度。然后,我们在算例上进行了大量的实验来证明该算法的有效性并分析了算法各个重要组成部分的关键作用。其次,本文根据二次多背包问题的分组特性,提出了一种基于backbone交叉算子混合算法求解该问题,该算子能够保留父代中的物品分配信息并遗传到子代,产生高质量的解。我们将该混合算法在不同时间限制下的计算结果与文献中求解QMKP最好的几种算法进行了对比,证明了该算法优异性并给出了小结。第叁,研究了由二次多背包问题变种而来的组成医疗小组问题,结合该问题的特点,提出了一种求解组成医疗小组问题的二阶段禁忌搜索算法。该算法中的二阶段局部搜索过程可以很好的处理目标函数和约束之间相互影响的关系,能够防止算法过早地陷入局部最优。我们通过实验将该算法与文献中的最好算法进行了对比,并分析了二阶段搜索过程对算法性能的影响,最后给出了小结。第四,延续了第五章所研究的组成医疗小组问题,根据该问题的分组特性,将求解二次多背包问题的混合问题移植到用来求解组成医疗小组问题。该算法使用了基于的backbone交叉算子来生成高质量的子代并集成了一种基于质量和距离的种群更新规则来保持算法搜索过程中种群的健康度。我们同样给出了算例实验将其性能与文献中的算法进行了对比,并进行了额外的实验分析了算法各个重要组成部分在算法中的巨大作用。(本文来源于《华中科技大学》期刊2017-04-01）
钱洁,王保华,郑建国,陈宇峰,周奎[5]（2015）在《多重二次背包问题的量子进化求解算法》一文中研究指出多重二次背包问题是二次背包与多重背包两种NP(Non-Deterministic Polynomial,非确定多项式)难问题融合后的一种新问题,由于其决策变量间具有高耦合性,已有的启发式算法求解效率和精度不够理想.针对这一问题提出一种量子进化求解算法,这种算法的量子观测操作能将部分约束处理与观测一步完成,解码效率高且不易陷入局部极值.算法中的量子更新采用自适应调节整体更新方式,相比传统查表方式更简洁和高效.算法还设计了一种局部和全局修补算子以保证解的可行性.另外,设计的交换算子能增强算法在约束边界的搜索性能.标准算例测试实验的结果表明文中提出的求解算法比传统算法的精度和效率更高.(本文来源于《计算机学报》期刊2015年08期）
孙文浩,陈伟[6]（2015）在《二次整数背包问题的新算法》一文中研究指出给出了一种求解一般二次整数背包问题(quadratic integer knapsack problem,QIKP)的新算法.该方法把占优的概念与分支定界思想结合,旨在寻求全局最优解.对QIKP给出了占优的定义,通过变量系数之间的关系,很容易找到占优组和极小占优组,从而删除可行域中那些非最优点.新的占优定义对凹的二次函数尤其有效.在理论证明的基础上,设计相应的算法,并进行了数值计算.结果显示,在随机产生的例子中,该算法是有效的,并且与传统的分支定界算法相比,得到了更好的最优解,最优值有了较大的提升.(本文来源于《应用数学与计算数学学报》期刊2015年03期）
王杉林,杨雪绒[7]（2014）在《解二次背包问题的一个线性化方法》一文中研究指出讨论了二次背包问题(QKP)的一种线性化方法.利用文献中的相关结论,通过增加变量和线性约束,将(QKP)的二次0-1规划模型等价转化为一个线性混合整数规划模型,再利用计算线性混合整数规划的软件(如Ilog-cplex或Lingo)求解,从而解决原问题.对所构造问题实例的计算,验证了求解(QKP)方法的有效性.(本文来源于《兰州文理学院学报(自然科学版)》期刊2014年05期）
陈娟娟,陈伟[8]（2014）在《可分离的二次背包问题的一种直接算法》一文中研究指出研究了可分离二次背包问题的一种直接算法.此类背包问题的目标函数是二次的,且含有严格的一次项,其不等式约束是线性的.给出所求模型的一般形式,经过预处理该模型,最终归为求解两类问题(P_1)和(P_2).重点是求解(P_2)问题的最优解,通过分析(P_2)问题的结构特点,假设固定一次项后问题的最优解和相应不等式的拉格朗日乘子已求出,通过比较拉格朗日乘子和(P_2)问题的一次项系数来调节λ的大小,从而求出(P_2)问题的最优解.对于(P_1)问题,改进了Bretthauer和Shetty给出的算法(Bretthauer K M,Shetty B.A pegging algorithm for the nonlinear resource allocation problem.Computers and Operations Research,2002,29(5):505-527).此算法的计算复杂性为O(n).数值算例表明,将这种固定变量算法和文中的定理5结合起来,能够快速有效地求解此类更一般的二次背包问题.(本文来源于《应用数学与计算数学学报》期刊2014年02期）
钱洁,郑建国[9]（2012）在《二次背包问题的贪婪量子进化算法求解》一文中研究指出二次背包问题是一种NP难组合优化问题,其精确算法求解难度大,针对该问题提出了一种量子进化算法求解方法。该算法采用一种相对贪婪修补算子,该修补算子不但考虑了二次背包问题的每一物品项价值,而且考虑了物品的协作价值,是一种动态修补算子。同时算法借鉴粒子群算法中粒子的运动方程,提出了一种具有叁类知识学习能力的量子更新模式,使得量子进化中获得的知识更全面。通过对100个国际上大规模二次背包问题进行测试实验,验证了提出的求解算法比相应的其他启发式算法性能有较大提升。(本文来源于《计算机集成制造系统》期刊2012年09期）
刘勇,马良[10]（2011）在《随机扩散算法求解二次背包问题》一文中研究指出针对二次背包问题,提出一种新的基于群体智能的随机扩散算法.算法采用一对一的通信机制;利用部分函数估计评价候选解;利用量子机制构造个体;采用1-OPT和异或操作提高搜索性能.通过数值实验并与微粒群算法、蚁群算法作比较,结果表明算法具有较好的优化性能.(本文来源于《控制理论与应用》期刊2011年08期）
二次背包问题论文开题报告
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
生活中,优化问题十分常见,力学中的优化更是无处不在.l_1范数正则化连续二次背包问题(CQKPL1)是一类重要的最优化问题,在结构分析、图像处理、压缩传感等领域都具有广泛的应用背景.尤其l_1范数正则化良好的稀疏性早已在计算机领域有较好的应用.对该问题理论和算法的研究早已备受国内外优化领域学者的关注,尤其在工程力学中,成为近年来研究的一个热点问题.本文在以上应用背景下,重点对求解_1l范数正则化连续二次背包问题的算法进行研究,通过数据实验比较几种算法的优劣.论文内容可概括如下:第1章首先介绍了二次背包问题的演化过程和发展历程,介绍了几种常用的求解可分离二次背包问题的算法.第2章在上述的研究背景下,提出了对CQKPL1算法进行研究.通过对模型的子问题及含参量问题的分析将该模型转化为求解方程根的问题并在此基础上提出叁种求解算法.第3章提出改进二分法,算法首先对断点进行分类,其次对包含断点的方程进行二分迭代搜索,同时加入加速迭代的步骤,加快算法收敛,搜索到最优解终止.第4章研究了改进割线法,算法包括两个步骤:步骤1(Bracketing Phase):目的是确定方程根的存在区间;步骤2(Secant Phase):在确定的区间内用割线法搜索方程的根.第5章对改进牛顿法进行讨论,首先引入了Moreau-Yosida正则化的概念将问题显示解进行重新研究,得到更多良好的解析性质.算法中利用改进的导数值得到迭代方向,利用Armijo线搜索产生迭代步长.最后,给出了改进牛顿法的全局收敛性定理,从理论上证明了算法的可行性.第6章对本文提出的叁个算法进行数据实验,将实验结果与当前商业中广泛使用的优化器Gurobi和Mosek的结果进行对比,验证本文算法的可行性和高效性.
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
二次背包问题论文参考文献
[1].刘雪静,贺毅朝,吴聪聪.求解集合联盟背包问题的二次贪心变异乌鸦算法[J].微电子学与计算机.2018
[2].温亚楠.L1范数正则化连续二次背包问题算法研究[D].沈阳航空航天大学.2018
[3].刘梦佳,向凤红,毛剑琳,郭宁.求解多重二次背包问题的改进遗传算法[J].软件导刊.2018
[4].秦进.二次多背包问题及其扩展问题的启发式算法研究[D].华中科技大学.2017
[5].钱洁,王保华,郑建国,陈宇峰,周奎.多重二次背包问题的量子进化求解算法[J].计算机学报.2015
[6].孙文浩,陈伟.二次整数背包问题的新算法[J].应用数学与计算数学学报.2015
[7].王杉林,杨雪绒.解二次背包问题的一个线性化方法[J].兰州文理学院学报(自然科学版).2014
[8].陈娟娟,陈伟.可分离的二次背包问题的一种直接算法[J].应用数学与计算数学学报.2014
[9].钱洁,郑建国.二次背包问题的贪婪量子进化算法求解[J].计算机集成制造系统.2012
[10].刘勇,马良.随机扩散算法求解二次背包问题[J].控制理论与应用.2011