- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies how to use large language models (LLMs) to develop heuristics for an unseen problem using only the evaluation feedback of the source problems. To this end, the paper proposes an LLM-driven multi-task evolutionary framework called MECo. Specifically, MECo constructs the heuristic population for different tasks and performs task interactions according to the transfer gap among different populations. Then, MECo leverages the performance complementarity between source tasks to select a compact heuristic set to apply to the target task without search or adaptation. Experiments on the vehicle routing problem (VRP) and flexible job-shop scheduling problem (FJSP) construct 32 problem variants and verify the effectiveness of the proposed method in ID and OOD settings. The experimental results report that MECo outperforms all baselines in terms of mean costs under the same budgets.
Critical strengths
- The paper studies a practical and valuable problem. In real-world scenarios, new constraint combinations are emerging continuously. However, it is expensive to perform a separate heuristic search for each new problem.
- The paper provides extensive experiments, which cover 32 problem variants across VRP and FJSP with eight automated heuristic design methods as baselines. The comparisons within these experiments are controlled due to shared source tasks and proposal budgets.
- The paper presents the performance of baselines (EoH, ReEvo, and HSEvo) equipped with the proposed method. It not only verifies the effectiveness of the proposed method in a new combination task, but also demonstrates the applicability of the proposed method across different heuristic search methods.
Critical weaknesses
- The generalization evidence in the paper is limited by the scope of the OOD setting. The OOD experiment investigates the performance of the proposed method on combined-constraint tasks derived from seen single-constraint tasks within the same problem family. This supports the generalization capability on limited changes of constraint combinations and cannot demonstrate the generalization capability under broader changes. The authors should evaluate the effectiveness of the proposed method on more complex constraint combination settings, such as narrower time windows.
- Further clarification of methodological contributions compared to existing methods is necessary. EoH-S [1] has already employed a complementary heuristic selection and selected parents according to performance differences. EMO-STA [2] has investigated the sharing and transfer of programs across tasks. The authors should further demonstrate the distinct methodological design of the proposed method compared to these two methods.
- It is unclear whether a smaller transfer gap indicates greater gains from cross-population recombination. Specifically, the paper fails to verify that Eq. 6 is an effective metric to predict gains after combining two single-constraint tasks. Eq. 6 measures the cross-task performance reduction of the current populations, but its ability to predict gains after cross-population recombination remains under-explored. Thus, the authors should provide empirical or theoretical evidence to verify the relationship between the transfer gap in Eq. 6 and gains from cross-population recombination.
- The advantage of the proposed method compared to the strongest baseline (MoH) needs more convincing validation. Specifically, the experimental results in Table 2 are averaged over three runs. Meanwhile, in Appendix E.5, the authors perform ten searches to report the final results. The paper should increase the number of independent runs for the key comparisons, such as the comparison between the proposed method and MoH. Meanwhile, it is also important to increase the number of independent runs for the ablation study.
Minors
- In line 121, the last word in this line, “geberakuzatuin” may be “generalization”.
- In lines 236-239, and are referred to as exploratory crossover and single-parent mutation, while Table 4 uses w/o diversification and w/o transfer repair. The authors should use consistent terminology and clarify the correspondence.
References
[1] EoH-S: Evolution of Heuristic Set using LLMs for Automated Heuristic Design.
[2] Evolutionary Multi-Task Optimization for LLM-Guided Program Discovery.
Questions for authors
Refer to Critical Weaknesses for more details.