多维背包问题的启发式算法研究探讨

多维背包问题是NP难组合优化问题,其模型及算法近年来在众多领域得到了广泛应用。本文主要探讨多维背包问题的启发式求解算法,通过对相关文献进行研究,阐述现有算法的优缺点,针对多维背包问题设计更高效的启发式求解算法,为其提供新的思路和参考。

自记忆的深度强化学习模型求解多维背包问题

本文针对多维背包问题维度高,约束强的特点提出了自记忆的学习优化模型(self memorized learn to improve,SML2I),通过深度强化学习的学习机制选择迭代搜索过程中的算子即模型学习当前的解以及历史搜索过程中的解,判断对当前解采用提升策略或者是扰动策略,在此基础上,进一步提出了哈希表与设计了2种有效的基于价值密度的扰动算子.使用哈希表记录历史搜索过程中的解,防止模型重复探索相同的解,基于价值密度的扰动策略生成的新解与之前的解决方案完全不同,因此针对扰动后的解再次采用提升策略同样有效,通过测试89个MKP数据集并与其他文献中先进的求解方法进行对比,实验结果验证了SML2I模型求解MKP问题的可行性与有效性.

求解多维背包问题的双决策交互差异算法

针对传统多维背包问题的求解算法存在的修复方式单一、种群动态适应性差等问题,提出一种双决策交互差异算法(DDEA)。融合自主学习思想,设计多维加权价值密度和相对价值概率指标,双重决策确定物品选择顺序,制定相应解的修复优化策略。采用双种群交互差异进化算法,设置主群和辅助群2个种群,种群间进行信息交互,提高种群多样性,避免陷入局部最优,提高算法寻优能力。主群实施差异进化机制,依照个体优劣依次划分为3个子群,分别按照特定方式进化,并在进化过程中完成与辅助群的交互,增强算法群智能性。引入刺激-响应机制,平衡算法的全局和局部搜索能力,并加入精英库协同寻优,加快算法收敛速度。仿真结果表明,DDEA算法可求出全部最优解,平均相对误差率为3.04×10-5,相比于同类算法降低2个数量级,有效提升了多维背包问题的求解精度、效率和稳定性。

求解多维背包的改进差分进化算法

针对多维背包问题,提出了一种改进的差分进化(IDE)算法。该算法保留了基本差分进化算法的交叉策略,同时将特定维数的0-1变异融入其中;为提高算法的收敛性,设计了最大和最小可装入背包的物品数量模型,作为对后续操作产生解的一个条件判断,从而缩小了搜索范围及时间;最后,通过对10个背包测试集进行测试,并与贪心二进制狮群优化(GBLSO)算法、混合粒子群(HPSO)算法进行比较。结果表明,该算法能较好的求得最优解,具有更快的收敛速度及更高的精度。

基于鱼群算法的多维背包问题研究

将鱼群算法应用于求解多维背包问题,提出一种求解多维背包问题的鱼群算法,MKPAFSA。定义MKPAFSA中的各元素,且引入启发因子和动态因子,并对鱼群算法进行了改进和优化。它减少了人工鱼的搜索时间,有效改善了鱼群算法后期收敛较慢且一般仅能得到满意解域的缺陷。仿真试验取得了较好的结果。

利用改进的二进制狼群算法求解多维背包问题

狼群算法启发于狼群群体生存智慧,已被用于复杂函数寻优和0-1普通背包问题求解。针对多维背包问题特点,设计了试探装载式的修复机制有效修复和改进人工狼群中的不可行解,改进了传统基于大惩罚参数的目标函数,减小了由于惩罚参数过大而导致算法陷入局部最优的风险;并受狼群的繁衍方式的启发,在二进制狼群算法的基础上提出了求解多维背包问题的改进二进制狼群算法(improve binary wolf pack algorithm,IBWPA)。通过求解19组不同规模的典型多维背包算例和与其他算法的对比分析,例证了算法的有效性和计算稳定性。

二进制反向学习烟花算法求解多维背包问题

为将烟花算法应用于离散优化领域并有效求解多维背包问题,构建一种二进制反向学习烟花算法。首先,通过定义二进制字符串距离、二进制转置算子将烟花算法的爆炸算子、变异算子离散化,构建二进制烟花算法;其次,设计不完全二进制反向算子并证明其收敛性,构建二进制反向学习烟花算法;最后,对10个多维背包问题典型算例进行仿真分析并与多种智能优化算法进行对比分析。仿真实验结果表明,二进制反向学习烟花算法在求解多维背包问题时具有良好的收敛效率、较高的寻优精度和很好的鲁棒性。

基于变异和信息素扩散的多维背包问题的蚁群算法

针对蚁群算法在求解大规模多维背包问题时存在的迭代次数过多、精度不高的不足,提出一种新的高性能的蚁群求解算法.算法将信息素更新和随机搜索机制的改进相融合.首先,基于对较优解的偏爱,采用Top-k策略从每次迭代的k个解中挖掘出对象间的关联距离;其次,以对象为信源借助关联距离建立信息素的扩散模型,通过信息素扩散的耦合补偿,强化了蚂蚁间的协作和交流;最后,利用一种简单的变异策略对迭代的结果进行优化.在通用数据集上的大量实验表明:与最新的蚁群算法相比,新算法不仅能获得更好的最优解,而且收敛速度有显著的提高.

求解多维背包问题的MapReduce蚁群优化算法

应用MapReduce编程模式实现蚁群优化算法的并行化计算,提出基于MapReduce的改进背包问题蚁群算法。通过改进概率计算时机、轮盘赌、交叉、变异等技术,降低蚁群算法的计算复杂度。在云计算环境中应用该算法分布式并行地求解大规模多维背包问题,仿真实验结果表明,该算法能改善蚁群算法搜索时间长的缺陷,增强对大规模问题的处理能力。

元胞微粒群算法及其在多维背包问题中的应用

针对离散微粒群算法早熟收敛问题,基于元胞自动机的原理和离散微粒群算法,提出一种元胞微粒群算法.将元胞及其邻居引入到算法中来保持种群的多样性,利用元胞的演化规则进行局部优化,避免算法陷入局部极值.通过对典型多维背包问题的仿真实验和与其他算法的比较,表明本算法可行有效,有良好的全局优化能力.

多维背包问题的一个蚁群优化算法

蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低用ACO求解MKP的复杂性,文章基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息,从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法.实验结果表明,无论串行执行还是虚拟并行执行,在计算相同任务时,新算法耗用时间少且解的价值更高.不仅如此,在实验中,文中的新算法获得了ORLIB中测试算例5.250-22的两个"新"解.

一种求解多维背包问题的小世界算法

针对遗传算法求解复杂组合优化问题时出现早熟收敛和种群多样性丧失等问题,提出了一种解决多维背包问题的二进制编码小世界算法(BSWA).BSWA算法依据社会学中的小世界现象搜索机理,采用类似遗传变异操作的局部搜索,而非遗传算法中的交叉操作.针对多维背包问题的多约束性,BSWA算法还按照价值资源比大小对不可行解进行贪婪修正,以保证求解的正确性.与遗传算法相比,BSWA可以在一定程度上克服早熟收敛,在保持种群多样性和求解精度方面均体现出较大的优势,具有解决复杂组合优化问题的潜力.对55个标准的多约束0-1背包问题进行了50次随机实验,结果表明,BSWA算法对于其中72.73%的问题可以次次获得最优解,对于其他不能次次求解到最优解的问题,也可以获得非常接近全局最优解的满意解.

求解多维背包问题的改进布谷鸟搜索算法

针对多维背包问题,提出了一种改进的布谷鸟搜索算法(Modified Cuckoo Search Algorithm,MCS)。该算法保留了基本布谷鸟搜索算法在实数域中的莱维飞行特征,只对其进行截断取整操作,采用了异或操作将鸟蛋被主人发现后位置的随机生成定义到0-1空间。通过对典型多维背包问题的仿真实验和与基本布谷鸟搜索算法、二进制微粒群算法和禁忌搜索算法的比较,表明了所提出的算法的收敛速度更快,全局寻优能力更强。

多维背包问题的二进制蚂蚁算法

针对著名的多维背包问题(MKP),在蚁群优化系统高维立方体结构的基础上,提出了一种二进制蚂蚁算法(BAS).与其他求解MKP问题的蚂蚁算法不同,BAS根据二进制解的结构设计了特殊的信息素放置方式,同时在算法的迭代过程中允许非可行解的产生,并通过基于问题特征信息的修改算子修复每次迭代所产生的非可行解.BAS算法采用了特殊的信息素更新规则,使得各个选择路径上的信息素可以直接作为选择概率,同时,为了避免算法陷入早熟,BAS设计了简单的局部搜索法,并根据算法所处的不同收敛状况,采用了不同的信息素更新规划和信息素重新初始化的方法.针对MKP基准问题的实验结果表明,BAS具有超越其他蚂蚁算法的求解结果,其求解不同基准测试问题的能力表明了BAS具有解决超大规模MKP问题的潜力.

基于有导向变异算子求解多维背包问题

多维背包问题(MKP)是经典的NP难的组合优化问题。引入有导向变异算子的进化算法GM-EA(Guided Mutation EA)来求解该问题,通过结合粒子群优化的方法改进郭涛算法,更好地利用种群中的全局信息,取得较好的效果。实验结果表明GM-EA是求解MKP有效的算法。

贪心二进制狮群优化算法求解多维背包问题

针对经典的多约束组合优化问题——多维背包问题(MKP),提出了一种贪心二进制狮群优化(GBLSO)算法。首先,采用二进制代码转换公式将狮群个体位置离散化,得到二进制的狮群算法;其次,引入反置移动算子对狮王位置进行更新,同时对母狮和幼狮位置重新定义;然后,充分利用贪心算法进行解的可行化处理,增强搜索能力并进一步提高收敛速度;最后,对10个MKP典型算例进行仿真实验,并把GBLSO算法与离散二进制粒子群(DPSO)算法和二进制蝙蝠算法(BBA)进行对比。实验结果表明,GBLSO算法是一种有效的求解MKP的新方法,在求解MKP时具有相对良好的收敛效率、较高的寻优精度和很好的鲁棒性。

多维背包问题的DNA计算

提出了一种基于DNA计算的求解多维背包问题的算法,该算法分两个阶段执行,第一个阶段采用试管方法,分别求出满足各个约束方程的可行域;第二个阶段采用表面方法,对第一个阶段求出的多个可行域取交集,即得满足整个约束方程组的可行域,再比较该可行域中各可行解对应的目标函数值,进而得到最优解.并通过实例分析验证了该算法的有效性和正确性.该算法将试管方法和表面方法结合使用,充分利用了两种方法各自的优点.

区域分割粒子群算法及多维背包问题求解

为克服离散粒子群算法早熟的缺陷,通过引入区域分割算法后,移除了解空间中一些无希望的点集,缩小了解的搜索空间,提高了找到最优解的概率,并通过贪心策略对产生的粒子进行了修复和改进,克服了离散粒子群算法收敛慢的缺点。对典型多维背包问题的仿真实验表明,区域分割粒子群算法寻优能力更强,收敛更快。

一种新的求解多维背包问题的分散算法

为了避免蚁群算法在优化搜索过程中易陷入局部最优和早熟收敛,提出一种求解多维背包问题的新型分散搜索算法。该算法是把蚁群算法的构解方法引入到分散搜索算法中,在搜索过程中,既考虑解的质量,又考虑解的分散性。同时,该分散算法还采用了动态更新参考集与阈值接收算法的阈值参数,以控制搜索空间来加快收敛速度。通过选取国际通用MDKP实例库中的多个实例进行测试表明,该算法可以避免陷入局部最优解,能提高全局寻优能力,其结果优于其他现有的方法,并获得了较好的结果。

改进二进制布谷鸟搜索算法求解多维背包问题

针对多约束组合优化问题——多维背包问题(MKP),提出了一种改进二进制布谷鸟搜索(MBCS)算法。首先,采用经典的二进制代码变换公式构建了二进制布谷鸟搜索(BCS)算法。其次,引入病毒生物进化机制和病毒感染操作,一方面赋予布谷鸟鸟巢位置自变异机制增加种群多样性;一方面将布谷鸟鸟巢位置所组成的主群体的纵向全局搜索和病毒群体的横向局部搜索进行动态结合,进一步提高了算法的收敛速度,降低了陷入局部极值的概率。再次,针对MKP特点设计了不可行解的混合修复策略。最后将MBCS算法同量子遗传算法(QGA)、二进制粒子群优化(BPSO)算法、BCS算法就来源于ELIB数据库和OR_LIB数据库的15个算例进行了仿真对比。实验结果表明,所提算法计算误差均小于1%,标准差小于170,相比这3种算法具有相对更好的寻优精度和求解稳定性,是一种求解多维背包等NP难问题有效的算法。