求解具有单连续变量的0-1背包问题的智能优化算法研究

来源 :福建农林大学 | 被引量 : 0次 | 上传用户:keke127
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
具有单连续变量的背包问题(Knapsack Problem with a single Continuous variable,KPC)是标准0-1KP的自然延伸,可应用于商业、投资决策、资源分配、计算复杂性理论、密码学和应用数学等领域。KPC的背包容量是不固定的,所以比0-1KP求解更为困难。同时,KPC属于NP-难的混合优化问题,精确算法求解耗时长,不适合求解高维问题。智能优化算法具有思路简单、通用性强、易于实现等优点,已经广泛应用于NP-难问题的求解中。因此,利用智能优化算法高效地获得一个KPC近似解更具有现实意义。目前已经存在若干求解KPC的智能优化算法,并且取得了不错的效果,但稳定性普遍不高。为进一步提高求解KPC的智能优化算法性能,论文对求解KPC的差分进化(Differential Evolution,DE)算法、蚁群优化(Ant Colony Optimization,ACO)算法和模拟退火(Simulated Annealing,SA)算法进行了研究,本文工作主要包括以下三个方面:1.提出基于拉马克进化的DE(Lamarckian Evolution-based DE,LEDE)算法,利用拉马克进化能够有效加快算法收敛速度的特点,设计基于拉马克进化的修复优化算子,将解在修复和优化过程中产生的改进遗传给后代,帮助算法在高维数据上加快收敛。在贪心修复优化算子中引入基于价值的贪心优化策略,避免算法陷入局部最优。2.提出了混合ACO(Hybrid ACO,HACO)算法。在HACO算法中,设计了一种简化的ACO算法来搜索物品的最优子集,并利用DE算法的变异算子来搜索连续变量的最优值。在简化ACO算法中,提出了独立选择策略和基于信息素的选择策略,以提高算法的求解速度和简化参数的调整。同时引入基于价值的贪心优化策略来增强解的质量。3.提出了基于多智能体的混合SA(Hybrid Multi-agent SA,HMSA)算法。针对随机采样的不足,提出了随机采样和基于知识采样结合的策略,使得采样过程既保持一定随机性,又能向更有希望的区域进行搜索,提高采样效率,加快算法收敛。对迭代过程中生成的不可行解进行贪婪修复后,使用基价值的优化算子来提高算法的寻优能力。在四类共40个KPC实例上对提出的算法进行了实验分析,充分分析了所提出策略的必要性和有效性。实验结果表明提出的LEDE算法、HACO算法和HMSA算法在获得最优解和平均解方面均优于其它智能优化算法。
其他文献
在大力构建新发展格局的背景下,维护国内的经济金融稳定已然成为了中国金融监管工作的首要目标。为探索双支柱政策对平抑金融周期的协调效果,首先,本研究通过CSMAR数据库采集并测度2002年1月~2021年3月中国信贷规模增速、杠杆增速、房地产价格增速和股票价格增速数据。其次,采用BP滤波法和主成分分析法提取、测度中国金融周期指数并对金融周期分项指数和金融周期总指数的波动特征展开分析。接着,本研究选取I
学位
多幅(帧)图像信息融合通过特定的算法将来源于同一场景的两幅或多幅图像的信息综合成一幅新的图像,从而能够获得比单一图像更丰富的信息,增强人们的视觉感知。多幅图像融合和多帧图像超分辨率是这一思想的两个问题。其中来自不同波段的多幅图像融合实现了不同波段的信息互补,而多帧图像超分辨率则通过融合相关帧序列增强图像的空间分辨率。在不同波段图像融合方面,红外与可见光图像融合是关注焦点之一,通过长波通道的红外图像
学位
以高质量发展为主题、以改革创新为根本动力已经成为应对中国经济发展新常态、破解发展难题的主要抓手。东部地区在经济总量和创新资源数量上都在全国占据绝对优势,对带动全国推进高质量发展具有示范引领作用。实现经济高质量与创新要素配置效率协同发展,是东部地区率先实现高质量发展面临的重要问题。本文在系统梳理经济高质量发展与区域创新效率耦合作用机理的基础上,从综合效益、协调发展、绿色发展、开放发展、共享发展五个方
学位
高质量的特征匹配选择是在给定的初始特征匹配集合中寻找正确的特征匹配,是计算机视觉中一项基础且重要的任务。其是许多高层次计算机视觉任务的基础,如图像配准、三维重建、闭环检测、图像拼接、三维目标识别等。因此,高质量的特征匹配选择结果的好坏会对后续的计算机视觉任务产生直接的影响。同时,由于高质量的特征匹配选择问题在本质上是一个十分复杂的组合优化问题,特别是在待处理的数据量较大且外点率较高时,其计算复杂度
学位
5G技术、物联网、大数据、云计算和人工智能等互联网技术的出现,推动信息化的发展进入大数据时代。面对海量数据的浪潮,决策问题在大数据背景下往往呈现出多样性、模糊性以及复杂性。如何完整表征这些复杂信息并对决策评价进行合理地聚合,是现代决策理论与方法领域中的一项重要研究课题。模糊集理论作为决策理论研究中处理不确定性的一种强有力的数学工具,在处理不确定信息方面具有独特的优越性。在大数据背景下,为使多属性决
学位
显著性目标检测是模拟人类的视觉特点提取单幅图像中最感兴趣的物体,即显著性物体。基于深度学习的协同显著性研究旨在检测多张图像中同时出现的显著性物体。该任务存在两大难点:(1)如何针对不同视觉场景中的不同物体得到鲁棒的特征表达。(2)如何通过这些特征表达进一步建模同组图像的共识关系,利用组内语义一致性来提升协同显著性检测的性能。现有的协同显著性研究对上述难点进行了深入研究,但因实际检测场景受到遮挡、形
学位
分类是机器学习领域的一个重要课题。随着数据获取技术的快速发展,高维数据集越来越普遍,但并不是所有的特征都与分类目标相关。不相关和冗余的特征甚至会降低分类性能。特征选择作为数据挖掘和机器学习中一种重要的数据预处理方法,旨在选择较少的相关和非冗余的特征,以获得与使用所有特征相似甚至更好的分类性能。特征选择本质上是一个NP难问题。随着维数的增长,搜索空间呈指数增长,因此进行穷举搜索是不切实际的,而元启发
学位
随着互联网技术的飞速发展,多媒体通信成为人与人之间交流的主要方式之一,在人类生活中有着广泛的应用。数字图像作为互联网上用户量最大的、传播速度最快的媒体之一,在传输过程中的信息安全以及版权保护问题也随之而来,因此如何保护数字图像在传输过程中的安全性问题已经成为了信息安全领域的研究热点之一。为了保护图像在传输过程中的安全性,研究者将图像加密与信息隐藏两者的优点结合起来提出了许多密文域信息隐藏算法,成为
学位
文献检索、文献筛选、文献质量评估、数据提取等Meta分析过程中均存在报告偏倚。报告偏倚主要有发表偏倚、时滞偏倚、多重发表偏倚、地域偏倚、引用偏倚、语言偏倚以及结果报告偏倚七大类,其中发表偏倚是报告偏倚中最难控制且影响范围最广的偏倚。过分夸大的阳性结果促使发表偏倚对现有的研究进行过度评价,从而丧失科研数据的可信度与真实性,甚至会让后续研究人员做出错误的推断。这种现象不仅浪费科学研究的资源,而且对Me
学位
集成异常检测算法有较强的鲁棒性和泛化能力,能够应用于许多领域,受到了广泛的研究和关注,其中不同个体学习器的结合方式对模型的性能具有显著影响,因此是一个重要的研究主题。传统多数投票法采用投票的方式来确定样本的最后标签,无法充分发挥各个个体学习器的优势,性能往往不理想。本文从个体学习器输出的异常得分之间的联系出发,通过确定最优个体学习器来确定样本的预测标签,提出了考虑结合稳定性的集成异常二次检测算法(
学位