解决合并背包问题的自适应优化算法
利用Smart Predict and Optimize (SPO)方法解决离散优化问题,通过弛化问题和启发式初始化学习和解决,证明了该方法在复杂调度和加权背包等大规模组合优化问题中的优势。
Nov, 2019
本文从动态规划的角度出发,探索了神经网络的表达能力与重复神经网络计算背包问题的最佳解或最小保证解值,提出了一种具有四层深度且宽度依据背包问题最优解的平方级别的背包问题重复神经网络,可以找到最优解或最小保证解值,得出了衡量神经网络大小和计算背包问题最佳解或最小保证解值之间的权衡关系。
May, 2020
本文调查了利用机器学习解决混合整数规划(MIP)问题的趋势,介绍了MIP及其传统算法,提倡学习和MIP的不同集成,并引入了与学习相关的方法。最后,我们展望了基于学习的MIP求解器的前景。
Mar, 2022
本研究论文总结了最近学习型多目标进化算法在解决不同尺度多目标优化问题中的进展和挑战,并提供了四个有吸引力的方向,即用于环境选择的可学习进化鉴别器,用于繁殖的可学习进化生成器,用于函数评估的可学习进化评估器,以及用于共享或重复使用优化经验的可学习进化传输模块,作为这一领域的努力的参考。
Jun, 2022
本文提出了一种基于演化算法和大邻域搜索的启发式算法,用于解决0-1多维背包问题。此算法通过整数规划探索良好部分分配所确定的有前途的搜索空间,从而找到更高质量的解。反复实验结果表明,所提出的算法可以在解质量方面优于现有的TPTEA和DQPSO启发式算法,并为8个大型、困难实例找到了新的下界。
Oct, 2022
通过对容量约束背包问题(0-1 knapsack problem)之一的最大包含解(inclusionwise maximal solutions)进行研究,本研究提出了一类新的复杂的0-1 knapsack问题实例,并通过机器学习模型的训练发现了这类问题的14个计算复杂特征,同时使用实例空间分析方法表明难的0-1 knapsack问题类似地聚集于实例空间的一个相对密集的区域中,并且几个特征在实例空间的简单和难的部分表现出不同。
Nov, 2022
研究探讨应用三目标进化算法解决具有随机和动态约束的背包问题,通过将体重和背包容量建模为随机和动态组成部分,与二目标公式相比,三目标公式在应对动态背包问题中具有明显优势。
Apr, 2024
在本研究中,我们考虑了基于背包约束的子模型最大化问题,该问题涉及大小为n的总体。我们将最快确定性算法的近似因子从6+ε改进为5+ε,同时保持了O(n)的最佳查询复杂度。我们的技术是基于两个组件的性能优化:阈值贪婪子程序和建立两个不相交集合作为候选解。此外,通过仔细分析候选解的成本,我们获得了更紧的近似因子。
May, 2024
本研究针对在背包约束下非单调子模极大化问题,提出了一种高效的并行算法,有效将现有并行算法的最佳近似因子从$8+\epsilon$提高到$7+\epsilon$,且具备$O(\log n)$的自适应复杂度。通过构建新的交替阈值算法框架,该算法在保证自适应复杂度的同时显著提升了解的质量,在收入最大化、图像摘要和最大加权切割等多个应用上进行了广泛的实验研究,展现出优越的性能。
Sep, 2024