Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model

• URL: http://arxiv.org/abs/2401.02051v3
• Date: Sat, 1 Jun 2024 16:48:37 GMT
• Title: Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model
• Authors: Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, Qingfu Zhang,
• Abstract summary: EoH represents the ideas of thoughts in natural language, termed thoughts. They are translated into executable codes by Large Language Models (LLMs) EoH significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.
• Score: 22.64392837434924
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Heuristics are widely used for dealing with complex search and optimization problems. However, manual design of heuristics can be often very labour extensive and requires rich working experience and knowledge. This paper proposes Evolution of Heuristic (EoH), a novel evolutionary paradigm that leverages both Large Language Models (LLMs) and Evolutionary Computation (EC) methods for Automatic Heuristic Design (AHD). EoH represents the ideas of heuristics in natural language, termed thoughts. They are then translated into executable codes by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it very effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent AHD methods including FunSearch. Particularly, the heuristic produced by EoH with a low computational budget (in terms of the number of queries to LLMs) significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.

Related papers

• Automatic programming via large language models with population self-evolution for dynamic job shop scheduling problem [12.535474591707105]
  This paper proposes a novel population self-evolutionary (SeEvo) method, a general search framework inspired by the self-reflective design strategies of human experts. Experimental results show that the proposed SeEvo method outperforms GP, GEP, end-to-end deep reinforcement learning methods.
  arXiv  Detail & Related papers  (2024-10-30T02:54:31Z)
• Multi-objective Evolution of Heuristic Using Large Language Model [29.337470185034555]
  Heuristics are commonly used to tackle diverse search and optimization problems. Recent works have incorporated large language models (LLMs) into automatic search leveraging their powerful language and coding capacity. We propose to model search as a multi-objective optimization problem and consider introducing other practical criteria beyond optimal performance.
  arXiv  Detail & Related papers  (2024-09-25T12:32:41Z)
• What's Wrong with Your Code Generated by Large Language Models? An Extensive Study [80.18342600996601]
  Large language models (LLMs) produce code that is shorter yet more complicated as compared to canonical solutions. We develop a taxonomy of bugs for incorrect codes that includes three categories and 12 sub-categories, and analyze the root cause for common bug types. We propose a novel training-free iterative method that introduces self-critique, enabling LLMs to critique and correct their generated code based on bug types and compiler feedback.
  arXiv  Detail & Related papers  (2024-07-08T17:27:17Z)
• PhaseEvo: Towards Unified In-Context Prompt Optimization for Large Language Models [9.362082187605356]
  We present PhaseEvo, an efficient automatic prompt optimization framework that combines the generative capability of LLMs with the global search proficiency of evolution algorithms. PhaseEvo significantly outperforms the state-of-the-art baseline methods by a large margin whilst maintaining good efficiency.
  arXiv  Detail & Related papers  (2024-02-17T17:47:10Z)
• Guided Evolution with Binary Discriminators for ML Program Search [64.44893463120584]
  We propose guiding evolution with a binary discriminator, trained online to distinguish which program is better given a pair of programs. We demonstrate our method can speed up evolution across a set of diverse problems including a 3.7x speedup on the symbolic search for MLs and a 4x speedup for RL loss functions.
  arXiv  Detail & Related papers  (2024-02-08T16:59:24Z)
• ReEvo: Large Language Models as Hyper-Heuristics with Reflective Evolution [35.39046514910755]
  This paper introduces Language Hyper-Heuristics (LHHs), an emerging variant of Hyper-Heuristics, featuring minimal manual intervention and open-ended spaces. To empower LHHs, we presentive Evolution (ReEvo), a novel integration of evolutionary search for efficiently exploring the white space, and reflections to provide verbal gradients within the space.
  arXiv  Detail & Related papers  (2024-02-02T05:04:51Z)
• Algorithm Evolution Using Large Language Model [18.03090066194074]
  We propose a novel approach called Evolution Algorithm using Large Language Model (AEL) AEL does algorithm-level evolution without model training. Human effort and requirements for domain knowledge can be significantly reduced.
  arXiv  Detail & Related papers  (2023-11-26T09:38:44Z)
• Connecting Large Language Models with Evolutionary Algorithms Yields Powerful Prompt Optimizers [70.18534453485849]
  EvoPrompt is a framework for discrete prompt optimization. It borrows the idea of evolutionary algorithms (EAs) as they exhibit good performance and fast convergence. It significantly outperforms human-engineered prompts and existing methods for automatic prompt generation.
  arXiv  Detail & Related papers  (2023-09-15T16:50:09Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  We propose complexity-impacted reasoning score (CIRS) to measure correlation between code and reasoning abilities. Specifically, we use the abstract syntax tree to encode the structural information and calculate logical complexity. Code will be integrated into the EasyInstruct framework at https://github.com/zjunlp/EasyInstruct.
  arXiv  Detail & Related papers  (2023-08-29T17:22:39Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  We describe a set of program transformations, a simple metric for assessing the efficiency of a transformed program, and a search procedure to improve this metric. We show that in practice, automated search can find substantial improvements to the initial program.
  arXiv  Detail & Related papers  (2021-09-14T20:52:55Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.