Towards Automatic Algorithm Design: Learning and Evolution

Abstract

Human experts and practitioners have devoted much effort to designing effective algorithms for solving complex search and optimization problems. Algorithm design requires not only tedious hand-crafting but also good intuition and rich experience from designers. Automatic Algorithm Design (AAD) minimizes manual intervention in algorithm development while enhancing performance through automation. It has gained significant interest from both academia and industry due to its potential to revolutionize how algorithms are created and optimized.

The effort on AAD can be broadly classified into three categories: Automatic Algorithm Selection (AAS), Automatic Algorithm Configuration (AAC), and Automatic Algorithm Generation (AAG). AAS focuses on selecting the optimal algorithm from a predefined algorithm portfolio for the target problem. AAC involves the automatic tuning of an algorithm's configuration to improve its efficacy on a given problem. AAG, which is the primary focus of this thesis, extends beyond selection and tuning by automatically generating new algorithms or components tailored to solve specific problems more effectively. The existing works on AAG include training neural solvers and genetic programming. However, they either face challenges in generalization or still demand much human design in algorithmic primitives.

This thesis focuses on exploring practical and generalized automatic algorithm design. The main contributions are summarized as follows:

The thesis first demonstrates the utility of offline machine learning in assisting the design of multiobjective evolutionary algorithms for complex real-world combinatorial optimization problems. We address a multi-faceted routine-packing problem by transforming it into a multiobjective routing problem with packing constraints. By employing offline machine learning methods for packing feasibility checking, we achieve a significant reduction in computational time — up to 1,000 times faster — while maintaining high accuracy. The performance of these machine learning-enhanced solutions is comparable to existing algorithms on both benchmark and real-world instances, with a substantial decrease in computational costs.

Next, the thesis develops two end-to-end deep learning solvers to tackle generalized combinatorial optimization challenges, particularly in Vehicle Routing Problems (VRPs). We develop a prompt learning approach that enables the adaptation of a pre-trained attention model to different problem instances across varying distributions. The results outperform existing meta-learning methods across diverse instances with different geometric distributions and sizes. Moreover, we introduce the first cross-problem neural solver for VRPs. By conceptualizing different VRP variants through a combination of shared attributes, the model can address multiple problems simultaneously. The results on more than 10 routing problems exhibit robust zero-shot generalization capabilities in both synthetic instances and real-world applications.

Lastly, the integration of Large Language Models (LLMs) with evolutionary computing is investigated to further advance AAD. We first make a preliminary attempt at applying LLM as optimizers for multi-objective evolutionary optimization. Then, more importantly, a novel paradigm, termed Evolution of Heuristic (EoH), is proposed. EoH evolves a population of heuristics, represented as both linguistic descriptions and code implementations, within an evolutionary framework. This approach significantly reduces human involvement and eliminates the need for model training. Comprehensive evaluations across various combinatorial optimization benchmarks and other tasks confirm that EoH not only outperforms many human-designed algorithms and existing learning-based methods but also offers new insights into algorithm design.

Date of Award	3 Apr 2025
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Qingfu ZHANG (Supervisor)