LLM2D
基于大型语言模型的多目标启发式算法进化
Multi-objective Evolution of Heuristic Using Large Language Model
作者: Shunyu Yao, Fei Liu, Xi Lin, Zhichao Lu, Zhenkun Wang, Qingfu Zhang
发布日期: 9/26/2024
arXiv ID: oai:arXiv.org:2409.16867v1

摘要

启发式算法通常用于解决各种搜索和优化问题。设计启发式算法通常需要使用领域知识进行繁琐的手动设计。最近的研究将大型语言模型 (LLM) 整合到自动启发式搜索中,利用其强大的语言和编码能力。然而,现有的研究只关注目标问题的最优性能作为唯一目标,而忽略了效率和可扩展性等其他标准,这些标准在实践中至关重要。为了应对这一挑战,我们建议将启发式搜索建模为一个多目标优化问题,并考虑引入除最优性能之外的其他实用标准。由于搜索空间的复杂性,传统的 多目标优化方法难以有效地处理多目标启发式搜索。我们提出了第一个基于 LLM 的多目标启发式搜索框架,即多目标启发式进化 (MEoH),该框架以零样本的方式集成 LLM,以生成一组非支配启发式算法,以满足多个设计标准。我们设计了一种新的支配-差异机制,用于有效的种群管理和选择,该机制结合了搜索空间中的代码差异和目标空间中的支配关系。MEoH 在两个著名的组合优化问题中得到证明:在线装箱问题 (BPP) 和旅行推销员问题 (TSP)。结果表明,在一次运行中自动生成了各种精英启发式算法,提供了比现有方法更多的折衷方案。它成功地实现了具有竞争力或优于现有方法的性能,同时将效率提高了 10 倍。此外,我们还观察到,多目标搜索为启发式设计带来了新的见解,并导致了多种启发式算法的发现。