Beyond the Hype: Benchmarking LLM-Evolved Heuristics for Bin Packing

• URL: http://arxiv.org/abs/2501.11411v1
• Date: Mon, 20 Jan 2025 11:23:50 GMT
• Title: Beyond the Hype: Benchmarking LLM-Evolved Heuristics for Bin Packing
• Authors: Kevin Sim, Quentin Renau, Emma Hart,
• Abstract summary: An escalating arms race is both rapidly producing news and improving the efficiency of the processes evolving them. We show that most of the LLMs do not generalise well when evaluated across a broad range of benchmarks. We suggest that any gains from generating very specialist Couplings that only work in small areas of the instance space need to be weighed carefully.
• Score: 0.1843404256219181
• License:
• Abstract: Coupling Large Language Models (LLMs) with Evolutionary Algorithms has recently shown significant promise as a technique to design new heuristics that outperform existing methods, particularly in the field of combinatorial optimisation. An escalating arms race is both rapidly producing new heuristics and improving the efficiency of the processes evolving them. However, driven by the desire to quickly demonstrate the superiority of new approaches, evaluation of the new heuristics produced for a specific domain is often cursory: testing on very few datasets in which instances all belong to a specific class from the domain, and on few instances per class. Taking bin-packing as an example, to the best of our knowledge we conduct the first rigorous benchmarking study of new LLM-generated heuristics, comparing them to well-known existing heuristics across a large suite of benchmark instances using three performance metrics. For each heuristic, we then evolve new instances won by the heuristic and perform an instance space analysis to understand where in the feature space each heuristic performs well. We show that most of the LLM heuristics do not generalise well when evaluated across a broad range of benchmarks in contrast to existing simple heuristics, and suggest that any gains from generating very specialist heuristics that only work in small areas of the instance space need to be weighed carefully against the considerable cost of generating these heuristics.

Related papers

• Efficient Non-Exemplar Class-Incremental Learning with Retrospective Feature Synthesis [21.348252135252412]
  Current Non-Exemplar Class-Incremental Learning (NECIL) methods mitigate forgetting by storing a single prototype per class. We propose a more efficient NECIL method that replaces prototypes with synthesized retrospective features for old classes. Our method significantly improves the efficiency of non-exemplar class-incremental learning and achieves state-of-the-art performance.
  arXiv  Detail & Related papers  (2024-11-03T07:19:11Z)
• 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)
• Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model [22.64392837434924]
  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.
  arXiv  Detail & Related papers  (2024-01-04T04:11:59Z)
• Generative Judge for Evaluating Alignment [84.09815387884753]
  We propose a generative judge with 13B parameters, Auto-J, designed to address these challenges. Our model is trained on user queries and LLM-generated responses under massive real-world scenarios. Experimentally, Auto-J outperforms a series of strong competitors, including both open-source and closed-source models.
  arXiv  Detail & Related papers  (2023-10-09T07:27:15Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Cross-Class Feature Augmentation for Class Incremental Learning [45.91253737682168]
  We propose a novel class incremental learning approach by incorporating a feature augmentation technique motivated by adversarial attacks. The proposed approach has a unique perspective to utilize the previous knowledge in class incremental learning since it augments features of arbitrary target classes. Our method consistently outperforms existing class incremental learning methods by significant margins in various scenarios.
  arXiv  Detail & Related papers  (2023-04-04T15:48:09Z)
• Generalization Properties of Retrieval-based Models [50.35325326050263]
  Retrieval-based machine learning methods have enjoyed success on a wide range of problems. Despite growing literature showcasing the promise of these models, the theoretical underpinning for such models remains underexplored. We present a formal treatment of retrieval-based models to characterize their generalization ability.
  arXiv  Detail & Related papers  (2022-10-06T00:33:01Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Multi-objective Asynchronous Successive Halving [10.632606255280649]
  We propose algorithms that extend successive asynchronous halving (ASHA) to the multi-objective (MO) setting. Our empirical analysis shows that MO ASHA enables to perform MO HPO at scale. Our algorithms establish new baselines for future research in the area.
  arXiv  Detail & Related papers  (2021-06-23T19:39:31Z)
• Exploring Complementary Strengths of Invariant and Equivariant Representations for Few-Shot Learning [96.75889543560497]
  In many real-world problems, collecting a large number of labeled samples is infeasible. Few-shot learning is the dominant approach to address this issue, where the objective is to quickly adapt to novel categories in presence of a limited number of samples. We propose a novel training mechanism that simultaneously enforces equivariance and invariance to a general set of geometric transformations.
  arXiv  Detail & Related papers  (2021-03-01T21:14:33Z)

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.