HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs

• URL: http://arxiv.org/abs/2412.14995v1
• Date: Thu, 19 Dec 2024 16:07:00 GMT
• Title: HSEvo: Elevating Automatic Heuristic Design with Diversity-Driven Harmony Search and Genetic Algorithm Using LLMs
• Authors: Pham Vu Tuan Dat, Long Doan, Huynh Thi Thanh Binh,
• Abstract summary: Heuristic Design is an active research area due to its utility in solving complex search and NP-hard optimization problems. We introduce HSEvo, an adaptive LLM-EPS framework that maintains a balance between diversity and convergence with a harmony search.
• Score: 7.04316974339151
• License:
• Abstract: Automatic Heuristic Design (AHD) is an active research area due to its utility in solving complex search and NP-hard combinatorial optimization problems in the real world. The recent advancements in Large Language Models (LLMs) introduce new possibilities by coupling LLMs with evolutionary computation to automatically generate heuristics, known as LLM-based Evolutionary Program Search (LLM-EPS). While previous LLM-EPS studies obtained great performance on various tasks, there is still a gap in understanding the properties of heuristic search spaces and achieving a balance between exploration and exploitation, which is a critical factor in large heuristic search spaces. In this study, we address this gap by proposing two diversity measurement metrics and perform an analysis on previous LLM-EPS approaches, including FunSearch, EoH, and ReEvo. Results on black-box AHD problems reveal that while EoH demonstrates higher diversity than FunSearch and ReEvo, its objective score is unstable. Conversely, ReEvo's reflection mechanism yields good objective scores but fails to optimize diversity effectively. With this finding in mind, we introduce HSEvo, an adaptive LLM-EPS framework that maintains a balance between diversity and convergence with a harmony search algorithm. Through experimentation, we find that HSEvo achieved high diversity indices and good objective scores while remaining cost-effective. These results underscore the importance of balancing exploration and exploitation and understanding heuristic search spaces in designing frameworks in LLM-EPS.

Related papers

• Progressive Multimodal Reasoning via Active Retrieval [64.74746997923967]
  Multi-step multimodal reasoning tasks pose significant challenges for large language models (MLLMs) We propose AR-MCTS, a universal framework designed to progressively improve the reasoning capabilities of MLLMs. We show that AR-MCTS can optimize sampling diversity and accuracy, yielding reliable multimodal reasoning.
  arXiv  Detail & Related papers  (2024-12-19T13:25:39Z)
• EVOLvE: Evaluating and Optimizing LLMs For Exploration [76.66831821738927]
  Large language models (LLMs) remain under-studied in scenarios requiring optimal decision-making under uncertainty. We measure LLMs' (in)ability to make optimal decisions in bandits, a state-less reinforcement learning setting relevant to many applications. Motivated by the existence of optimal exploration algorithms, we propose efficient ways to integrate this algorithmic knowledge into LLMs.
  arXiv  Detail & Related papers  (2024-10-08T17:54:03Z)
• Multi-objective Evolution of Heuristic Using Large Language Model [29.337470185034555]
  We model the search as a multi-objective optimization problem and consider introducing additional practical criteria beyond optimal performance. We propose the first multi-objective search framework, Multi-objective Evolution of Heuristic (MEoH)
  arXiv  Detail & Related papers  (2024-09-25T12:32:41Z)
• Understanding the Importance of Evolutionary Search in Automated Heuristic Design with Large Language Models [24.447539327343563]
  Automated design (AHD) has gained considerable attention for its potential to automate the development of effectives. The recent advent of large language models (LLMs) has paved a new avenue for AHD, with initial efforts focusing on framing AHD as an evolutionary program search problem.
  arXiv  Detail & Related papers  (2024-07-15T16:21:20Z)
• Meta Reasoning for Large Language Models [58.87183757029041]
  We introduce Meta-Reasoning Prompting (MRP), a novel and efficient system prompting method for large language models (LLMs) MRP guides LLMs to dynamically select and apply different reasoning methods based on the specific requirements of each task. We evaluate the effectiveness of MRP through comprehensive benchmarks.
  arXiv  Detail & Related papers  (2024-06-17T16:14:11Z)
• Self-Exploring Language Models: Active Preference Elicitation for Online Alignment [88.56809269990625]
  We propose a bilevel objective optimistically biased towards potentially high-reward responses to actively explore out-of-distribution regions. Our experimental results demonstrate that when fine-tuned on Zephyr-7B-SFT and Llama-3-8B-Instruct models, Self-Exploring Language Models (SELM) significantly boosts the performance on instruction-following benchmarks.
  arXiv  Detail & Related papers  (2024-05-29T17:59:07Z)
• Large Language Model-Aided Evolutionary Search for Constrained Multiobjective Optimization [15.476478159958416]
  We employ a large language model (LLM) to enhance evolutionary search for solving constrained multi-objective optimization problems. Our aim is to speed up the convergence of the evolutionary population.
  arXiv  Detail & Related papers  (2024-05-09T13:44:04Z)
• 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)
• Large Language Models as Evolutionary Optimizers [37.92671242584431]
  We present the first study on large language models (LLMs) as evolutionarys. The main advantage is that it requires minimal domain knowledge and human efforts, as well as no additional training of the model. We also study the effectiveness of the self-adaptation mechanism in evolutionary search.
  arXiv  Detail & Related papers  (2023-10-29T15:44:52Z)
• Survival of the Most Influential Prompts: Efficient Black-Box Prompt Search via Clustering and Pruning [77.61565726647784]
  We propose a simple black-box search method that first clusters and prunes the search space to focus exclusively on influential prompt tokens. Our findings underscore the critical role of search space design and optimization in enhancing both the usefulness and the efficiency of black-box prompt-based learning.
  arXiv  Detail & Related papers  (2023-10-19T14:25:06Z)
• Corex: Pushing the Boundaries of Complex Reasoning through Multi-Model Collaboration [83.4031923134958]
  Corex is a suite of novel general-purpose strategies that transform Large Language Models into autonomous agents. Inspired by human behaviors, Corex is constituted by diverse collaboration paradigms including Debate, Review, and Retrieve modes. We demonstrate that orchestrating multiple LLMs to work in concert yields substantially better performance compared to existing methods.
  arXiv  Detail & Related papers  (2023-09-30T07:11:39Z)

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.