1 Introduction↩︎

Heuristics are commonly used for tackling complex search and optimization problems. Over the last several decades, much effort has been devoted to designing effective heuristics, leading to simulated annealing [1], tabu search [2], and iterated local search [3], among many other methods [4]. These hand-crafted methods have been successfully used in a wide spectrum of real-world applications. However, different applications may require different algorithms and/or algorithm configurations. Manually designing, modifying, and configuring a heuristic for a given problem can be very labor-intensive and demands rich expert experience. This is a bottleneck in many application domains. To address this issue, Automatic Heuristic Design (AHD) has been proposed and become an active research area [5], [6]. AHD selects, tunes, or constructs effective heuristics for a given problem class automatically. Genetic Programming (GP) has been used in AHD [7], [8]. GP requires a set of permissible primitives or mutation operations for defining and generating heuristics. It could be very difficult to construct a suitable set in practice [9].

It is believed that Large Language Models (LLMs)  [10]–[12] could be a powerful tool for generating new ideas and heuristics. However, standalone LLMs with prompt engineering can be insufficient for producing novel and useful ideas beyond existing knowledge [13]. Some attempts have been made to couple LLMs with Evolutionary Computation (EC) methods to produce heuristics in an automatic manner [14]–[16]. One representative work is FunSearch [17]. It models AHD as a search problem in the space of functions, where each function is a heuristic represented by a program and it uses LLMs in an evolutionary framework to iteratively improve the quality of generated functions. FunSearch has been applied on several problems with great success. However, its mechanism is not very efficient and it needs a very large amount of computational resources to generate a quality heuristic.

In this paper, we present a new evolutionary paradigm, dubbed Evolution of Heuristic (EoH) ¹, to take advantage of both LLMs and EC for AHD. Specifically, we leverage a linguistic description, referred to as a thought, to represent a high-level idea (i.e., key logic) of a heuristic. Then, a corresponding code representation, i.e., an executable implementation of a heuristic, is generated via an LLM. We propose an evolutionary framework to simultaneously evolve the thoughts and codes of heuristics in a cooperative manner. We demonstrate that the LLM-assisted evolution of both thoughts and codes with curated prompts leads to state-of-the-art AHD performance. We expect that EoH serves as a step towards efficient and automatic algorithm design.

In summary, our contributions are as follows:

• We propose EoH, a novel paradigm that uses LLMs to evolution both thoughts and codes for the automatic design of heuristics with minimum hand-craft design and no domain model training.

• We develop several simple yet effective prompt strategies to guide LLMs toward generating more diverse and effective heuristics. These prompt strategies are generally applicable to other LLM-assisted search methods.

• We comprehensively evaluate EoH on three widely-studied combinatorial optimization benchmark problems. We demonstrate that EoH outperforms many existing AHD methods. In particular, EoH identifies heuristics with better performance than those designed by FunSearch. EoH uses much fewer queries to LLMs than FunSearch on online bin packing problem.

2 Background and Related Works↩︎

2.1 Automatic Heuristic Design↩︎

Automatic heuristic algorithm design is commonly known as hyper-heuristics [5], [6], [19]. With various effective methodologies [20]–[22] and frameworks [19], one can tune heuristics or combine different algorithmic components in an automatic manner. Much effort has been made to use machine learning techniques in automatic algorithm design [23]–[26]. Among them, genetic programming [27], [28] provides an explainable approach to algorithm design. However, it requires hand-crafted algorithmic components and domain knowledge.

2.2 LLMs for Heuristic Design↩︎

Over the last few years, the ability of large language models has increased significantly [29]. Recently, some effort has been made to use LLMs as basic algorithmic components to improve the performance of algorithms [14], [30]. Most of these works adopt LLM as optimizers [14] to directly generate new trial solutions through in-context learning. This approach faces challenges when applied to complex problems with large search space [14], [31]–[33]. Others integrate LLMs to assist algorithm design to extract deep algorithm features for heuristic selection [34], provide a guide for heuristic [35], and design an algorithmic component [36]. However, designing a competitive heuristic is still a challenge for standalone LLMs with prompt engineering.

2.3 LLMs + EC↩︎

Evolutionary computation is a generic optimization principle inspired by natural evolution [37], [38]. Integration of EC in the prompt engineering of LLMs is very promising in improving performance in various domains [39]–[41]. Evolutionary methods have been adopted in both code generation [42]–[45] and text generation [39], [46], [47]. The most related work to our effort is FunSearch [17], an evolutionary framework with LLMs to search functions automatically. Algorithms generated by FunSearch outperform hard-crafted algorithms on some optimization problems. However, FunSearch is computationally expensive and usually needs to generate millions of programs (i.e., queries to LLMs) to identify an effective heuristic function, which is not very practical for many users.

3 Evolution of Heuristics (EoH)↩︎

3.1 Main Idea↩︎

EoH aims at evolving both thoughts and codes to mimic the heuristic development conducted by human experts for efficient automatic heuristic design. To achieve this goal, EoH

• maintains both a natural language description and its corresponding code implementation for each heuristic. In each trial, it allows LLMs to first generate a heuristic in terms of natural language and then generate its corresponding code. The natural language description summarizes the main idea and provides a high-level understanding, while the code provides implementation details and settings that supplement the high-level thought.

• employs several prompt strategies to guide LLMs to do reasoning over existing thoughts and codes. These strategies are designed to learn from previous experiences and effectively explore the heuristic space. They can be regarded as fine-grained in-context learning approaches that combine thoughts and codes for heuristic search.

• evolves a population of candidate heuristics. It uses LLMs in genetic operators such as crossover and mutation to produce new heuristics. Selection is also used to direct the search. The quality of each heuristic is evaluated on a set of problem instances.

Unlike most evolutionary algorithms where individuals are candidate solutions to an optimization problem, An individual in EoH is a heuristic designed for solving a given problem. We believe that the evolution of “thoughts" should be an important research direction.

EoH Integrates LLMs into an evolutionary framework. It generates and refines heuristics automatically. Unlike some classic automatic heuristic design methods [5], EoH doesn’t need any hand-crafted heuristic components or train new models.

EoH evolves both thoughts and codes. Thoughts in natural language and designed prompt strategies enable EoH to generate more diverse and effective heuristics. In contrast, FunSearch performs evolution of codes only and does not use prompt strategies explicitly.

3.2 Evolution Framework↩︎

EoH maintains a population of \(N\) heuristics, denoted as \(P = \{h_1, \dots, h_N\}\), at each generation. Each heuristic \(h_i\) is evaluated on a set of problem instances and assigned a fitness value \(f(h_i)\).

Five prompt strategies are designed to generate new heuristics. At each generation, each strategy is called \(N\) times to generate \(N\) heuristics. Each newly generated heuristic will be evaluated on problem instances and added to the current population if it is feasible. At most \(5N\) new heuristics will be added to the current population at each generation. Then, \(N\) best individual solutions from the current population will be selected to form the population for the next generation.

EoH are summarised as follows:

Step 0 Initialization: Initialize the population \(P\) of \(N\) heuristics \(h_1, \ldots, h_N\) by prompting LLMs using Initialization prompt, its detail can be found in Section 3.4.

Step 1 Generation of Heuristics: If the stopping condition is not met, five Evolution prompt strategies (detailed in Section 3.4) are used simultaneously to generate \(5N\) new heuristics. For each of the five prompt strategies, repeat the following process \(N\) times:

• Step 1.1: Select parent heuristic(s) from the current population to construct a prompt for the strategy.

• Step 1.2: Request LLM to generate a new heuristic as well as its corresponding code implementation.

• Step 1.3: Evaluate the new heuristic on a set of evaluation instances to determine its fitness value.

• Step 1.4: Add the new heuristic to the current population if the heuristic and code are feasible.

Step 2 Population Management: Select the \(N\) best individual heuristics from the current population to form a population for the next generation. Go to Step 1.

3.3 Heuristic Representation↩︎

Each heuristic consists of three parts: 1) its description in natural language, 2) a code block in a pre-defined format, and 3) a fitness value.

The heuristic description comprises a few sentences in natural language. It is created by LLMs and presents a high-level thought.

The code block is an implementation of the heuristic. It should follow a pre-defined format so that it can be identified and seamlessly integrated into EoH framework. In the experiments, we choose to implement it as a Python function. Three basic components should be explicitly given to format the code block: 1) Name of the function, 2) Input variables, and 3) Output variables.

The evaluation of heuristics in EoH involves running the resulting algorithms on an instance set of the problem in question. This evaluation process differs from traditional evolutionary algorithms, which typically evaluate the objective function in a single instance. It is similar to some AHD approaches [21], [48] and is often costly.

3.4 Prompt Strategies↩︎

3.4.0.1 Initialization prompt

In our experiments, we use LLMs to create all the initial heuristics, eliminating the need for expert knowledge. We inform the LLMs of the heuristic design task and instruct it to design a new heuristic by first presenting the description of the heuristic and then implementing it as a Python code block. The details of prompts for each problem are listed in the corresponding subsections in the Appendix. We repeat \(N\) times to generate \(N\) initial heuristics.

3.4.0.2 Evolution prompts

Five prompt strategies are proposed for creating new heuristics during evolution to mimic the heuristic development by humans. They are categorized into two groups: Exploration (E1, E2) and Modification (M1, M2, M3). The exploration strategies focus more on the exploration of the space of heuristics by conducting crossover-like operators on parent heuristics. The modification strategies refine a parent heuristic by modifying, adjusting parameters, and removing redundant parts. The details of these evolutionary prompts are listed as follows:

E1: Generate new heuristics that are as much different as possible from parent heuristics. First, \(p\) heuristics are selected from the current population. Then, LLM is prompted to design a new heuristic that is different from these selected heuristics as much as possible in order to explore new ideas.

E2: Explore new heuristics that share the same idea as the selected parent heuristics. First, \(p\) heuristics are selected from the current population. Then, LLM is instructed to identify common ideas behind these heuristics. Then, a new heuristic is designed that are based the common ideas but are as much different as possible from the selected parents by introducing new parts.

M1: Modify one heuristic for better performance. Firstly, one heuristic is selected from the population. Then, LLM is prompted to modify it to produce a new heuristic.

M2: Modify the parameters of one selected heuristic. First, one heuristic is selected from the current population. Then, LLM is prompted to try different parameters in the current heuristic instead of designing a new one. M3: Simplify heuristics by removing redundant components. First, one heuristic is selected from the current population. Then, LLM is prompted to analyze and identify the main components in the selected heuristic and analyze whether there are any redundant components. Finally, LLM is prompted to simplify the code implementation of the heuristic based on its analysis.

In all the above prompts, LLM is asked to first describe the heuristic and then provide a code implementation in a pre-defined format.

Any selection method can be used in EoH. In our experimental studies, all the heuristics in the current population are ranked according to their fitness. Heuristic \(i\) in the current population is randomly selected with probability \(p_i \propto 1/(r_i+N)\), where \(r_i\) is its rank and \(N\) is the population size.

4 Experiments↩︎

4.1 Experimental Settings↩︎

4.1.0.1 Benchmarks and datasets.

We consider three well-studied combinatorial optimization benchmark problems:

• Online bin packing problem. The objective is to allocate a collection of items of different sizes into the fewest possible bins with a fixed capacity \(C\). We focus on the online scenario [49], where items are packed as they arrive, in contrast to the offline scenario where all items are known beforehand. The instances that are used for evaluation during heuristic evolution are five Weibull instances of size 5k with a capacity of 100 [17]. The fitness value is set as the average \(\frac{lb}{n}\) on the five instances, where \(lb\) represents the lower bound of the optimal number of bins computed as in [50] and \(n\) is the number of bins used to pack all the items by the evaluated heuristic.

  Methods in comparison include

  • human hand-crafted heuristics: the first fit and best fit heuristics [17]. The first fit heuristic assigns the incoming item to the first bin that has sufficient available space, while the best fit heuristic selects the bin with the least available space that can still accommodate the item.

  • heuristics generated automatically: FunSearch [17] is considered due to its excellent performance. We directly use the heuristic generated by FunSearch [17] for comparison.

• Traveling Salesman Problem (TSP) [51]. It is to find the shortest route to visit all the given locations once and return to the starting location. It is one of the most widely-studied combinatorial optimization problems and a commonly used test bed for heuristics. The heuristic evolution process is conducted on a set of 64 TSP100 instances. The locations in these instances are randomly sampled from \([0,1]^2\) [52]. The average gap from the optimal solution (which is generated by Concorde [53]) is used as the fitness value.

  Methods in comparison include

  • hand-crafted heuristics: The nearest insertion[54] and farthest insertion [54], two commonly used constructive heuristics are used in comparison. Google Or-Tools [55], one of the most popular solvers is also used. We use the default settings of Or-Tools and the local search option suggested in OR-Tools to improve the solution quality. The stopping criterion is 60s for each instance.

  • heuristics designed automatically by AI methods: they are the attention model (AM) [52], POMO [56] and LEHD [57]. AM [52] is a seminal and well-known method for using neural networks to learn heuristics for combinatorial optimization. POMO [56] adopts AM ideas and achieves state-of-the-art results. LEHD [57] is a new revision of AM with a different heavy decoder structure and is trained using supervised learning.

• Flow Shop Scheduling Problem (FSSP) [58]. It is to schedule \(n\) jobs on \(m\) machines, where each job contains \(m\) operations that must be performed in a predetermined order on the respective machine. The objective is to minimize the total schedule length, known as the makespan. In the perturbation flow-shop scheduling problem, the processing order remains consistent throughout each step and no machine can execute multiple operations simultaneously. During heuristic evolution, we conduct evolution on 64 randomly generated instances. Each instance consists of 50 jobs and 2 to 20 machines. The processing times of the jobs are randomly generated from a uniform distribution ranging from 0 to 1 [59]. The average makespan serves as the fitness value.

  Methods in comparison include

  • hand-crafted heuristics: They are GUPTA [60], CDS [61] NEH [62] and NEHFF [63]. GUPTA [60] and CDS [61] are two classic methods for flow-shop scheduling. NEH [62] and NEHFF [63] are widely recognized efficient heuristics for this problem.

  • heuristics designed automatically: PFSPNet and PFSPNet_NEH [59] are used. They are two recently proposed end-to-end deep learning solvers for flow-shop scheduling.

4.1.0.2 Implementation details.

• Online bin packing. We adopt the settings in [17] to design heuristics to determine the suitable bin allocation for incoming items [64]. Specifically, the task for EoH is to design the scoring function for assigning items. The inputs are the size of the item and the rest capacities of bins. The output is the scores for the bins. The item will be assigned to the bin with the maximum score.

• Traveling salesman. We use EoH to design Guided Local Search (GLS) heuristics [65]. GLS is a strategy to help a local search to escape local optimal solutions. A key issue in GLS heuristics is how to update the objective function (i.e. landscape) to guide the local search to move to more promising areas. Noting that the landscape is primarily determined by the distance matrix, the goal of EoH is to produce a method for updating the distance matrix. Following [65], [66], the inputs are the distance matrix, the current route, and the number of edges. The output is an updated distance matrix. GLS runs local search operators on updated landscapes iteratively. Two local search operators used in our experiments are the relocate and 2-opt operators. A detailed introduction of the GLS heuristics is presented in the Appendix.

• Flow shop scheduling. We use the EoH to produce a heuristic for updating the objective landscape in GLS for this problem. The inputs in the heuristic are the time matrix, current scheduling, and the number of machines and jobs. The outputs are the updated time matrix and the calculated job perturbation priority. The local search operators used are the relocate and swap operators.

In our experiments, the number of generations in EoH for all problems is set to 20. The population size is 20 for online bin packing and 10 for TSP and FSSP. The number of parent heuristics used in E1 and E2 is \(p=5\). The GPT-3.5-turbo pre-trained LLM is used. For TSP and FSSP, the maximum number of iterations for local search is set to 1,000, and the maximum running time for each instance is 60 seconds. The entire framework and the implementations of EoH on the three problems are implemented in Python and executed on a single CPU i7-9700.

4.2 Results↩︎

4.2.0.1 Online bin packing.

We visualize the evolution of EoH for the online bin packing problem in Figure 2. We outline the key thoughts and the corresponding codes of the best heuristic found in some generations in the evolution process. We also list the prompt strategies that generate the thoughts and codes. The fitness value (objective) increases from 0.962 to 0.993 in 20 generations, which involves 2,000 LLM queries. As shown in Figure 2, in comparison to the best fit heuristic, the heuristics designed by both FunSearch and EoH are sophisticated. The best heuristic found by EoH is a hybrid function with multiple components. It consists of remaining capacities, exponent term of remaining capacities, square root term of remaining capacities, and their combinations. It is the result of evolution. An example of the heuristic design using E2 prompt strategy is detailed in the Appendix [e2].

We test the best heuristic produced by EoH on instances of various sizes and capacities and compare it with two hand-crafted heuristics (i.e., first and best fit), and the best heuristic produced by FunSearch. The problem size ranges from 1k to 10k and the capacities are 100 and 500. Each set includes 5 randomly generated instances. Table 1 presents the average gaps to the lower bounds, where the best results are highlighted in bold. Our method is the best except for the results on the 10k_C100 set (instances with a problem size of 10k and a capacity of 100). EoH makes only a few thousands of LLM queries, which is much faster than FunSearch (around 1 million queries reported in [17]). Furthermore, our method achieves the same best gap in the training distribution and demonstrates excellent generalization performance to out-of-distribution instances. For instance, on the instance set with 1k items and a capacity of 500, FunSearch performs worse than two hand-crafted heuristics, whereas our method achieves the best gap of 2.13%. More results are provided in the Appendix [more95results95bp]

4.2.0.2 Traveling salesman.

Figure 3 (a) illustrates the evolution process of heuristics in EoH for TSP. The y-axis represents the gap (%) to the optimal solution and the x-axis represents the number of generations. Each blue data point represents a GLS heuristic produced by EoH. Every population consists of 10 heuristics. The red curve shows how the performance of the best heuristic found at each generation is improved. The orange curve shows the average performance of the population at each generation. It is clear that EoH converges after about 20 generations. We list the gap (%) to the best-known solutions on six instances from TSPLib [67] in Table 2. Comprehensive evaluation on other TSP instances and comparison with some other heuristics including hand-crafted GLS algorithms are provided in the Appendix [more95results95tsp].

It should be pointed out that the heuristics produced by EoH consistently outperform other heuristics on all test instances. Notably, for pr124, kroA150, and u159, the EoH heuristic finds the best-known solutions (i.e., gap= 0%). OR-Tools works well on average. However, its performance on large instances becomes worse perhaps due to the limited running time. The neural solvers are trained on the instances from a uniform distribution, which is the same as those used in EoH for fitness evaluation. These solvers can generate high-quality solutions on the instances from the same distribution. However, they deteriorate on out-of-distribution instances, such as the TSPLib instances. In contrast, the heuristic designed by EoH works well on these out-of-distribution instances.

4.2.0.3 Flow shop scheduling.

Figure 3 (b) depicts the evolution process of heuristics on FSSP, demonstrating that it converges in about 20 generations. Table 3 lists the experimental results of different heuristics on Taillard instances with the number of jobs (\(n\)) ranging from 20 to 100 and the number of machines (\(m\)) ranging from 10 to 20. The table displays the average gap (%) to the upper bound provided in [68]. Each set consists of 10 instances. The best results are highlighted in bold. EoH produces the best results on all the test sets among all the heuristics. More results can be found in the Appendix [more95results95fssp].

4.3 Ablation Study↩︎

An ablation study is carried out to provide a better understanding of the contribution of major components in EoH. We consider the following variants of EoH:

• EoH-e1: it doesn’t use the three modification prompt strategies and E2, i.e. It uses only E1.

• EoH-e2: it doesn’t use the three modification prompt strategies, i.e. It uses only E1 and E2.

• EoC: it is the code-only variant of EoH. It doesn’t include the thought part (i.e. the description of the heuristic in natural language). EoC only uses E1 (without linguistic description) to generate new codes. The number of parents \(p=5\).

Table 4 summarizes the components used in various compared variants.

Experiments are carried out on online bin packing problem. The population size is 20. The GPT-3.5-turbo pre-trained LLM is used. The number of parent heuristics used in E1 and E2 is \(p=5\). To have a fair comparison, all the variants use the same initial population. Consider that EoH uses five prompt strategies while others use few strategies. We increase the numbers of generations correspondingly in each variant so that the total number of evaluated heuristics is the same. Table 5 compares the final best heuristics produced by different variants. We can make the following observations:

• On average, EoH performs the best and EoH-e2 performs the second best. This implies that \(M_1, M_2, M_3\), and \(E_2\) do make positive contribution to the performance of EoH.

• EoC performs the worst or the second worst on these test instances. It implies that the thought part in EoH is also very beneficial.

5 Discussion and Future Works↩︎

5.1 Discussion↩︎

5.1.0.1 Interaction between Thoughts and Codes

We carry out the following experiments to demonstrate the benefits of the use of both thoughts and codes in EoH. The thought and code can be regarded as multiple views of the heuristic. We will show that the multi-view thought and code representation contribute to EoH. We compare EoH with the following three variants:

• C2C: It uses only code to represent a heuristic. There is no natural language (thought) representation.

• T2T2C: It uses only thought for heuristic representation. Evolutionary prompts (i.e., E1-2, M1-3) only use thought representation to generate new heuristics. However, we still need to query LLMs to produce a code implementation for each heuristic for performance evaluation.

• T&C2T2C: It uses both thought and code representations of input heuristics in evolutionary prompts. We query LLMs with these prompts (i.e., E1-2, M1-3) to give only a natural language presentation of the produced heuristic. As in T2T2C, we need to request LLMs to produce a code implementation for each produced heuristic for performance evaluation.

Table 6 lists comparison results (average gap (%) to lb) of EoH with the above three variants on the online bin packing Weibull test instances. All experiments are carried out in the same experimental settings three times on the online bin packing problem.

It is evident that only use of codes (C2C) or thoughts (T2T2C) in evolutionary prompts is much worse than EoH. Thus, we can claim that the evolution of both codes and thoughts does make significant contribution to EoH. EoH is also better than T&C2T2C. It implies that letting these prompts output both the codes and thoughts are helpful for the quality of the produced heuristics.

5.1.0.2 Different LLMs

We compare four commonly used LLMs: GPT3.5, Gemini Pro, CodeLlama, and Deepseek. All experiments are carried out in the same experimental settings three times on the online bin packing problem. In general, EoH can generate good-performance heuristics using these different LLMs. EoH using different LLMs with 2,000 queries to LLMs performs better than randomly querying GPT3.5 10,000 times. Nevertheless, our experimental results also show the benefits of using more powerful LLMs, e.g., GPT3.5 and Gemini Pro outperform other LLMs.

5.1.0.3 Use of Expert Heuristic

We investigate the impact of the use of existing heuristics (expert heuristics) in EoH. Take the bin packing problem as an example, we adopt the heuristic provided in FunSearch paper [17] as the existing expert heuristic and put it into the initial population of EoH. The rest of the initial heuristics are randomly generated. The results are given in Table 8. We term the EoH with an expert in the initial population EoH expert and compare it to the original EoH and FunSearch. The results show that the adoption of elite expert heuristic benefits in the population benefits the final results in our test case. The EoH expert clearly surpasses both FunSearch and EoH. The knowledge of expert heuristics can be inherited and evolved during evolution to produce better heuristics.

5.2 Future Works↩︎

It should be pointed out that the development of the evolution of heuristics using LLMs is still in its very early infancy. This paper and other research [17] show that it is very promising for automatic algorithm design. Much effort should be made to advance this area.

5.2.0.1 Pre-trained domain LLM

Instead of using a general pre-trained LLM with linguistic and code generation capability, it is worthwhile studying how to train an LLM specifically for automatic algorithm design. Domain knowledge can be used for this purpose.

5.2.0.2 Understanding of search space of heuristics

EoH directly does its search on the space of heuristics. It is different from classic optimization algorithms which conduct their search in a well-defined math space such as \(R^n\). It should be very important to study and understand search spaces of heuristics for further establishing theory and basic principles for the automatic design of algorithms.

5.2.0.3 Interaction with human experts

A LLM in EoH can be regarded as an intelligent agent. During the process of EoH, It is straightforward to let human experts to replace LLM for generating, modifying, and evaluating heuristics at some stage. It should be interesting to study how to implement efficient and effective interaction with human experts in EoH. Ideas and techniques in collective intelligence [69] should be used for this purpose.

6 Conclusion↩︎

This paper has proposed Evolution of Heuristics (EoH), which combines large language models (LLMs) and evolutionary computation (EC) methods to design heuristics in an automatic manner. By introducing the evolution of both thoughts and codes and using five prompt strategies, EoH mimics the process of heuristic design by human experts. We have tested EoH on three well-studied optimization problems, namely the online bin-packing problem, travel salesman problem, and flow shop scheduling problem. Experiments have shown that EoH can outperform human hand-crafted heuristics in some problem instances. EoH requires only a few thousand LLM requests while achieving better performance on most test instances. EoH offers a principled approach to automatic algorithm design. The source code can be found in https://github.com/FeiLiu36/EoH.

Acknowledgements↩︎

The work described in this paper was supported by the Research Grants Council of the Hong Kong Special Administrative Region, China (GRF Project No. CityU11215622), the National Natural Science Foundation of China (Grant No. 62106096), the Natural Science Foundation of Guangdong Province (Grant No. 2024A1515011759), the National Natural Science Foundation of Shenzhen (Grant No. JCYJ20220530113013031).

Impact Statement↩︎

This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.

7 Additional Related Work↩︎

7.1 Neural Solvers↩︎

Recently, much effort has been made to develop end-to-end neural solvers, especially for combinatorial optimization [23]. A pointer network as a neural solver was proposed to construct solutions autoregressively in [70]. Some improvements to this work have been made including using an efficient reinforcement learning framework to replace the original supervised learning [71] and adopting an attention model to replace the pointer network [52], [72]. Among these variants [56], [73], [74], a multiple optimal policy proposed in [56] archives the state-of-the-art performance on diverse problems of small or moderate sizes. Recent progress, leveraging a heavy encoder and light decoder, enhances its scalarization [57], [75].

Some effort has also been made to hybridize neural solvers and classic heuristic algorithms including heat map-based methods [76]–[78], heat map guided beam search [76], Monte Carlo tree search (MCTS) [77], dynamic programming [79], and guided local search [80], [81]. The hybridization often requires significant effort to design and train domain neural models.

7.2 Prompt Engineering↩︎

LLMs with simple promoting face challenges in solving complex reasoning tasks [82]. To address this challenge, Chain-of-Thought (CoT) [83] was proposed to do in-context learning with step-by-step reasoning processes to enhance the reasoning ability of LLMs without human annotation.

Consequently, there have been many extensions and modifications on CoT such as multi-sampling, tree-of-thoughts [84], graph-of-thoughts [85], algorithm-of-thoughts [86], and automatic CoT construction [87], [88]. The prompt strategies used in EoH can be regarded as variants of CoT for the design of heuristics with parent heuristics and instructions as in-context information.

8 Online Bin Packing Problem↩︎

8.1 Prompt Engineering↩︎

In the following, we introduce the detailed prompt engineering used for online bin packing problem. The prompt engineering for each evolution procedure consists of five main parts: 1) Task description, 2) Strategy-specific prompt, 3) Expected output, 4) Note, and 5) Parent heuristic(s). Figure 4 presents two examples of prompts: initialization prompt and E2 prompt. The prompt engineering for other operators (E1, M1, M2, and S1) has the same structure as these two examples and is not listed for brevity. The five parts in different colors are introduced as follows:

• Task description: It informs LLMs of the problem description. Different prompt strategies usually share the same task description.

• Strategy-specific prompt: It instructs LLMs to do reasoning over the in-context information and generate new heuristics as well as its corresponding code implementation. Different prompt strategies have different strategy-specific prompts. For example, during initialization, we instruct the LLM to create a totally new heuristic. During evolution, we request LLM to perform different types of reasoning over parent heuristic(s) to explore the heuristic search space.

• Expected output: It asks the LLM to provide a description of the designed heuristic and then produce the code implementation for the heuristic. In this paper, the code implementation is a function in Python. We explicitly define the name, input, and output of the code for easy identification by EoH framework.

• Note: It provides additional instructions for LLM to improve the efficiency and robustness. For example, we may suggest specific types of inputs and outputs and discourage extra explanations to prevent a long response.

• Parent heuristic(s): It includes parent heuristic(s) to enable in-context learning over both the linguistic heuristic description and the code implementation. The initialization prompt does not include this part.

8.2 Heuristic Evolution↩︎

The convergence process of evolution has been discussed in the main part. Figure 6 presents a detailed illustration of E2 in one generation. Five heuristics are chosen from the population, each of them consists of a high-level description and a detailed Python implementation. These heuristics are then used as inputs for prompt engineering in E2, which was introduced in the previous section. The LLMs are given three instructions: firstly, to identify the shared concept among the provided heuristics based on their descriptions and codes; secondly, to design a new heuristic based on this analysis; and thirdly, to implement the heuristic in Python with a given name, input, and output. The improved heuristic follows the identified common idea and integrates new components.

8.3 Designed Heuristic↩︎

Comparison of heuristics designed by humans, EoC, FunSearch, and our proposed EoH is presented in Figure 6. We present them as Python functions with the same inputs and output. The inputs ‘item’ and ‘bins’ represent the size of the current item and the rest capacities of bins following [17]. The output is the scores assigned to the bins. At each step, the item is assigned to the bin with the highest score. It is worth noting that the two most commonly utilized hand-crafted heuristics can be implemented in one line of code. On the other hand, the heuristics designed by EoC, FunSearch, and our method EoH are more complicated, making them difficult to achieve for human designers.

8.4 More Results↩︎

Table 9 summarizes the results of First Fit, Best Fit, and the algorithm produced by FunSearch, EoC, and EoH on Weibull instances with different capacities and sizes. The average gap to the lower bound on five instances is reported for different heuristics. The best results, indicated in bold, represent the heuristics with the lowest average gap to the lower bound. We observe that the heuristic designed by EoC overfits on the distribution (100, 5k) which is used to evaluate the fitness of heuristics generated in the evolution process. Among all the heuristics, EoH consistently achieves the best performance, with an average gap to the lower bound of 1.18%. Importantly, EoH only utilizes a few thousand queries, which accounts for much less computational budget required by FunSearch (around 1 million queries reported in [17]). EoH achieves the same best gap in the training distribution while demonstrating superior generalization performance, particularly for different capacities.

9 Traveling Salesman Problem↩︎

9.1 Guided Local Search↩︎

The heuristics designed by EoH work with local search operators in a guided local search framework for both TSP and FSSP. In contrast to the complicated local search in SOTA solvers [89], We only adopt the two basic local search operators. We show that even with these two simple operators, EoH can design a very competitive algorithm.

Guided local search (GLS) is a widely used strategy to guide a local search escape from local optimal solutions for solving combinatorial optimization problems  [65], [90]. In a typical local search [65], when a local search is trapped in a local optimal solution, GLS modifies the objective function to guide the local search to move to other promising search regions [65].

A GLS algorithm alternates the two phases: local search and perturbation [66]. During the local search phase, we employ local search operators to search. When the search is trapped in a local optimum, the perturbation phase is invoked to update the objective function (i.e., landscape) using a heuristic strategy.

EoH is employed to design a strategy to update the objective function. With some pre-selected local search operators, this strategy can define a GLS heuristic. In our experiments, for each updating strategy generated in EoH, the performance of its corresponding GLS heuristic is evaluated on a set of problem instances, with the average performance as its fitness value.

9.2 Prompt Engineering↩︎

In the following, we give details of prompt engineering used for TSP. We use the same five components outlined in the prompt engineering section for bin packing. In Figure 7, we provide two illustrative examples of prompts for initialization and E2, with each component represented in different colors. For the sake of brevity, we omit the prompt engineering details for other prompt strategies.

9.3 Designed Heuristic Strategy↩︎

Figure 8 illustrates the heuristic strategy designed by EoH for updating the distance matrix for TSP. This matrix is obtained by modifying the original distance matrix and adding some random factors, which involves several intermediate variables, including the average of distances, the average of edge used, and a penalty on the current local optimal route.

9.4 More Experimental Results↩︎

We also compare the heuristic generated by EoH with the following methods:

• Graph Convolutional Network (GCN) method for TSP [76].

• Attention Model (AM) [52]. It uses neural networks to learn heuristics for combinatorial optimization.

• POMO [56]. It adopts AM ideas and achieves state-of-the-art results.

• LEHD [57]. It is a new variant of AM with a different heavy decoder structure and is trained using supervised learning.

• GLS [90]. It is the vanilla version of GLS for TSP.

• EBGLS [91]. It extends the GLS by considering the big valley feature of the TSP.

• KGLS [66]. It uses multiple features extracted from previous knowledge of routing problems.

• GNNGLS [80] and NeuralGLS [81]. They use deep learning models in GLS.

We set the maximum number of calls of LS to be 1,000 for each GLS algorithm on every test instance. We use the source code of POMO [56] , BQ [75], and LEHD [57] in our experiments. The experimental results for GNNGLS [80], NeuralGLS [81], AM [80] and GCN  [81] are directly extracted from their respective papers. The solutions obtained by Concorde [53] are used as the baselines for computing the performance gap.

We consider three different numbers of locations: 20, 50, and 100. For each number of locations, we randomly generate 1,000 locations from \([0,1]^2\) and thus obtain 1,000 test instances. Table 10 shows the average performance of the heuristics on these random instances. The table provides the average gap compared with the baseline solver Concorde, as well as the average running time on each instance. It should be pointed out that POMO, BQ, and LEHD run in a parallel manner on the GPU, so single-instance running time is not provided. It is very clear from Table 10 that the heuristic produced by EoH performs the best.

We also conduct experiments on 29 TSPLib instances. As shown in Table 11, The GLS algorithm designed by EoH outperforms all the other heuristics including hand-crafted ones in terms of the average gap on the 29 instances.

10 Flow Shop Scheduling Problem↩︎

10.1 Prompt Engineering↩︎

This subsection is to introduce details of prompt engineering used for FSSP. We use the same components for bin packing. Figure 9 provides two illustrative examples of prompts for initialization and E2, with each component represented in a different color.

10.2 Designed Heuristic Strategy↩︎

We adopt the same GLS framework with two selected local search operators: Swap and Relocate. EoH is used to design a heuristic strategy for updating both the execution time matrix and to determine the perturbed jobs. Figure 10 illustrates a heuristic designed by EoH for FSSP. Some selected elements in the original matrix are updated.

10.3 More Results↩︎

  We also compare the heuristic produced by EoH with the following methods.

• GUPTA [60]. It is a classic heuristic algorithm for FSSP.

• CDS [61]. It is a classic heuristic algorithm for FSSP.

• NEH [62]. It is widely recognized as an efficient heuristic for FSSP.

• NEHFF [63]. It is a revision of NEH.

• PFSPNet and PFSPNet_NEH [59]. They are recently developed deep learning solvers for flow-shop scheduling.

• Local Search (LS). It is the basic local search with the same operators used in EoH.

• ILS1 [92]: It is an iterated local search developed for FSSP.

• ILS2: It uses the same framework as ours but with hand-crafted heuristic strategy.

We evaluate the algorithms on the widely-used Taillard Instances. We test 11 different test sets. The number of jobs in these instances ranges from 20 to 200, and the number of machines ranges from 5 to 20.

Table 12 presents the results obtained from different algorithms on Taillard instances. The table gives the average gaps to the upper bounds provided in [68]. The average is calculated on 10 instances for each test set. The best results are highlighted in bold. EoH is the best on most test sets and obtain the best average gap of 0.23%. EoH outperforms these commonly used heuristics as well as the recent deep learning neural solvers. Notably, EoH outperforms ILS2, which shares the same framework and local search operators but uses a human hand-crafted heuristic strategy for perturbation.

References↩︎