大规模多维背包问题的随机启发式修复
利用Smart Predict and Optimize (SPO)方法解决离散优化问题,通过弛化问题和启发式初始化学习和解决,证明了该方法在复杂调度和加权背包等大规模组合优化问题中的优势。
Nov, 2019
本论文研究了通过机器学习解决NP困难问题的可行性,指出了训练数据的易变性及其对模型的影响,并提出了改进的方法来适应这个问题。该方法被应用于非线性、非凸、离散组合问题的求解,取得了有效的结果。
Jun, 2021
本论文提出了两种自适应优化算法以及一个基于教学学习优化算法的离散框架,用于解决集合-联合背包问题。经过实验比较,发现其算法性能优于其他种群智能方法,尤其是基于物品的算法I-DTLBO表现突出,并且得到了当前集群智能算法的上限。
Jan, 2022
本文调查了利用机器学习解决混合整数规划(MIP)问题的趋势,介绍了MIP及其传统算法,提倡学习和MIP的不同集成,并引入了与学习相关的方法。最后,我们展望了基于学习的MIP求解器的前景。
Mar, 2022
本文提出了一种基于演化算法和大邻域搜索的启发式算法,用于解决0-1多维背包问题。此算法通过整数规划探索良好部分分配所确定的有前途的搜索空间,从而找到更高质量的解。反复实验结果表明,所提出的算法可以在解质量方面优于现有的TPTEA和DQPSO启发式算法,并为8个大型、困难实例找到了新的下界。
Oct, 2022
通过对容量约束背包问题(0-1 knapsack problem)之一的最大包含解(inclusionwise maximal solutions)进行研究,本研究提出了一类新的复杂的0-1 knapsack问题实例,并通过机器学习模型的训练发现了这类问题的14个计算复杂特征,同时使用实例空间分析方法表明难的0-1 knapsack问题类似地聚集于实例空间的一个相对密集的区域中,并且几个特征在实例空间的简单和难的部分表现出不同。
Nov, 2022
对于庞大规模的旅行推销员问题(TSP),现有算法在计算效率和解决方案质量方面面临巨大挑战。为了解决这个问题,我们提出了一种分层销毁和修复(HDR)方法,通过一系列精心设计的销毁和修复操作来改进初始解。一个关键创新概念是分层搜索框架,它递归地修复部分边缘,并将输入实例压缩成小规模的TSP,在某种等价保证下。这个巧妙的搜索框架能够在合理的时间内提供极具竞争力的解决方案。基于19个著名的大规模实例(城市数量从10,000到10,000,000个),公平比较显示HDR在计算效率和解决方案质量方面与现有最先进的TSP算法高度竞争。值得注意的是,在3,162,278个和10,000,000个城市的两个大型实例中,HDR打破了LKH及其变体先前创下的世界纪录(即无论计算时间如何,都是最好的已知结果),而HDR完全独立于LKH。最后,通过消融研究来证明分层搜索框架的重要性和有效性。
Aug, 2023
研究探讨应用三目标进化算法解决具有随机和动态约束的背包问题,通过将体重和背包容量建模为随机和动态组成部分,与二目标公式相比,三目标公式在应对动态背包问题中具有明显优势。
Apr, 2024
本研究针对在背包约束下非单调子模极大化问题,提出了一种高效的并行算法,有效将现有并行算法的最佳近似因子从$8+\epsilon$提高到$7+\epsilon$,且具备$O(\log n)$的自适应复杂度。通过构建新的交替阈值算法框架,该算法在保证自适应复杂度的同时显著提升了解的质量,在收入最大化、图像摘要和最大加权切割等多个应用上进行了广泛的实验研究,展现出优越的性能。
Sep, 2024
本研究针对启发式设计在搜索与优化问题中的局限性,提出将启发式搜索建模为多目标优化问题,考虑效率与可扩展性等实际需求。通过首次提出基于大型语言模型的多目标启发式搜索框架MEoH,该框架在单次运行中产生多种精英启发式,显著提升效率并拓展启发式设计的可能性,展示了更优的性能与选择空间。
Sep, 2024