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

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

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

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

摘要：针对多维背包问题(MKP)约束性强和复杂度高的特点,提出一种新型二级协作果蝇优化算法(TCFOA).提出一级果蝇和二级果蝇的产生机制,将二级果蝇划分为开发用果蝇和探索用果蝇两类以协调开发与探索之间的平衡;设计果蝇交流策略以及基于全局性价比的解的修复补偿机制,并利用二级结构扩大搜索范围、改善一级果蝇的质量,以提高求解质量.基于MKP两个标准测试集的测试结果和算法性能对比,表明TCFOA在求解MKP方面具有较强的优势.

摘要：针对多维背包问题(MKP)NP-hard、约束强的特点,提出一种高效的蚁群-拉格朗日松弛(LR)混合优化算法.该算法以蚁群优化(ACO)为基本框架,并基于LR对偶信息定义了一种MKP效用指标.ACO使得整体算法具有全局搜索能力,所设计的效用指标将MKP的优化目标与约束条件有机地融合在一起.该指标一方面可以用来定义MKP核问题,降低问题规模;另一方面,可以用作ACO的启发因子,引导算法在有希望的解区域中强化搜索.在大量标准算例上的测试结果表明,所提出算法的鲁棒性较好;与其他已有算法相比,在求解质量和求解效率方面均具有很强的竞争力.

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

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

摘要：针对二进制人工蜂群算法收敛速度慢、易陷入局部最优的缺点,提出一种改进的二进制人工蜂群算法。新算法对人工蜂群算法中的邻域搜索公式进行了重新设计,并通过Bayes公式来决定食物源的取值概率。将改进后的算法应用于求解多维背包问题,在求解过程中利用贪婪算法对进化过程中的不可行解进行修复,对背包资源利用不足的可行解进行修正。通过对典型多维背包问题的仿真实验,表明了本文算法在解决多维背包问题上的可行性和有效性。

摘要：利用DNA自组装执行计算的思想已从实验上被证明具有可行性。利用DNA瓦片自组装执行计算的方法,由于其通用性正被广泛研究,已有多种理论模型被提出以解决各种NP问题。基于DNA Tile自组装模型理论在三维下的扩展,设计了可以实现这一算法的三维DNA Tile组装系统。提出了一种用于解决多维背包问题的三维DNA自组装模型;该模型可以非确定性的输出可行性解决方案。分析表明系统可以在线性组装步骤内完成计算,所需的Tile种类数与问题维数无关。为探索三维DNA自组装的计算能力进行了一次有意义的尝试。