用新评估准则提升大模型进化算法设计启发式策略的效率
QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution
- 引入质量-不确定性权衡准则，优化大模型与进化算法结合的搜索策略
- 在多个难解NP完全问题上，性能显著优于FunSearch和基线方法
- 适合研究智能优化、自动算法设计的学者和工程师参考
求解NP难问题传统上依赖启发式算法，但为复杂问题手动设计高效启发式仍具挑战。尽管近期如FunSearch等方法已证明大语言模型（LLMs）可融入进化算法（EAs）进行启发式设计，其潜力受限于探索与利用之间的平衡问题。本文提出质量-不确定性平衡进化（QUBE），通过重新定义FunSearch框架内的优先级准则来增强LLM+EA方法。QUBE采用基于新提出的包含不确定性的质量度量的品质-不确定性权衡准则（QUTC），以评估并引导进化过程。在多个困难的NP完全问题上的大量实验表明，QUBE相比FunSearch及基线方法有显著性能提升。代码已开源：https://github.com/zzjchen/QUBE_code。
原文摘要 · Abstract (English)
Solving NP-hard problems traditionally relies on heuristics, yet manually designing effective heuristics for complex problems remains a significant challenge. While recent advancements like FunSearch have shown that large language models (LLMs) can be integrated into evolutionary algorithms (EAs) for heuristic design, their potential is hindered by limitations in balancing exploitation and exploration. We introduce Quality-Uncertainty Balanced Evolution (QUBE), a novel approach that enhances LLM+EA methods by redefining the priority criterion within the FunSearch framework. QUBE employs the Quality-Uncertainty Trade-off Criterion (QUTC), based on our proposed Uncertainty-Inclusive Quality metric, to evaluate and guide the evolutionary process. Through extensive experiments on challenging NP-complete problems, QUBE demonstrates significant performance improvements over FunSearch and baseline methods. Our code are available at https://github.com/zzjchen/QUBE_code.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。