QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915164110979072 |
|---|---|
| author | Chen, Zijie Zhou, Zhanchao Lu, Yu Xu, Renjun Pan, Lili Lan, Zhenzhong |
| author_facet | Chen, Zijie Zhou, Zhanchao Lu, Yu Xu, Renjun Pan, Lili Lan, Zhenzhong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20694 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution Chen, Zijie Zhou, Zhanchao Lu, Yu Xu, Renjun Pan, Lili Lan, Zhenzhong Neural and Evolutionary Computing Artificial Intelligence Computation and Language 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. |
| title | QUBE: Enhancing Automatic Heuristic Design via Quality-Uncertainty Balanced Evolution |
| topic | Neural and Evolutionary Computing Artificial Intelligence Computation and Language |
| url | https://arxiv.org/abs/2412.20694 |