CoChat
Sign Up
PreprintCited by 14Evolutionary Algorithms and ApplicationsMetaheuristic Optimization Algorithms ResearchSoftware Engineering Research

Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model

Open access
Liu, Fei, Tong, Xialiang, Yuan, Mingxuan, Lin, Xi, Luo, Fu, Wang, Zhenkun, Lu, Zhichao, Zhang, Qingfu·2024·arXiv
DOI 10.48550/arxiv.2401.02051arXiv 2401.02051
Open this paper in CoChat — free accountOpen PDF

Abstract

Heuristics are widely used for dealing with complex search and optimization problems. However, manual design of heuristics can be often very labour extensive and requires rich working experience and knowledge. This paper proposes Evolution of Heuristic (EoH), a novel evolutionary paradigm that leverages both Large Language Models (LLMs) and Evolutionary Computation (EC) methods for Automatic Heuristic Design (AHD). EoH represents the ideas of heuristics in natural language, termed thoughts. They are then translated into executable codes by LLMs. The evolution of both thoughts and codes in an evolutionary search framework makes it very effective and efficient for generating high-performance heuristics. Experiments on three widely studied combinatorial optimization benchmark problems demonstrate that EoH outperforms commonly used handcrafted heuristics and other recent AHD methods including FunSearch. Particularly, the heuristic produced by EoH with a low computational budget (in terms of the number of queries to LLMs) significantly outperforms widely-used human hand-crafted baseline algorithms for the online bin packing problem.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2401.02051

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • EoH showed LLM-plus-evolution could beat FunSearch on heuristic design at a fraction of the query budget.

    “EoH showed LLMplus-evolution could beat FunSearch on heuristic design at a fraction of the query budget [159]”

    From Recursive Self-Improvement in AI: From Bounded Self-Refinement to Autonomous Research Loops (2026) · cites this paper as [159]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 80

  1. Akiba, T., Sano, S., Yanase, T., Ohta, T., and Koyama, M. Optuna: A next-generation hyperparameter optimization framework. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2623-2631, 2019.
  2. Angelopoulos, S., Kamali, S., and Shadkami, K. Online bin packing with predictions. Journal of Artificial Intelli- gence Research, 78:1111-1141, 2023.
  3. Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q., et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021. · arXiv
  4. Bäck, T., Fogel, D. B., and Michalewicz, Z. Handbook of evolutionary computation. Release, 97(1):B1, 1997.
  5. Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940, 2016. · arXiv
  6. Bengio, Y., Lodi, A., and Prouvost, A. Machine learning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
  7. Blot, A., Hoos, H. H., Jourdan, L., Kessaci-Marmion, M.-É., and Trautmann, H. Mo-paramils: A multi-objective auto- matic algorithm configuration framework. In Learning and Intelligent Optimization: 10th International Con- ference, LION 10, Ischia, Italy, May 29-June 1, 2016, Revised Selected Papers 10, pp. 32-47. Springer, 2016.
  8. Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., and Qu, R. Hyper-heuristics: A survey of the state of the art. Journal of the Operational Research Society, 64:1695-1724, 2013.
  9. Burke, E. K., Hyde, M. R., Kendall, G., Ochoa, G., Özcan, E., and Woodward, J. R. A classification of hyper- heuristic approaches: revisited. Handbook of metaheuris- tics, pp. 453-477, 2019.
  10. Chen, A., Dohan, D., and So, D. Evoprompting: Language models for code-level neural architecture search. In Ad- vances in Neural Information Processing Systems, 2023.
  11. Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. d. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021. · arXiv
  12. Chen, T., Chen, X., Chen, W., Wang, Z., Heaton, H., Liu, J., and Yin, W. Learning to optimize: A primer and a benchmark. The Journal of Machine Learning Research, 23(1):8562-8620, 2022.
  13. Chu, Z., Chen, J., Chen, Q., Yu, W., He, T., Wang, H., Peng, W., Liu, M., Qin, B., and Liu, T. A survey of chain of thought reasoning: Advances, frontiers and future. arXiv preprint arXiv:2309.15402, 2023. · arXiv
  14. Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., and Rousseau, L.-M. Learning heuristics for the tsp by policy gradient. In International conference on the integration of constraint programming, artificial intelligence, and operations research, pp. 170-181. Springer, 2018.
  15. Drakulic, D., Michel, S., Mai, F., Sors, A., and Andreoli, J.-M. Bq-nco: Bisimulation quotienting for generaliz- able neural combinatorial optimization. arXiv preprint arXiv:2301.03313, 2023. · arXiv
  16. Eiben, A. E. and Smith, J. From evolutionary computation to the evolution of things. Nature, 521(7553):476-482, 2015.
  17. Emmons, H. and Vairaktarakis, G. Flow shop scheduling: theoretical results, algorithms, and applications, volume 182. Springer Science & Business Media, 2012.
  18. Fernando, C., Banarse, D., Michalewski, H., Osindero, S., and Rocktäschel, T. Promptbreeder: Self-referential self-improvement via prompt evolution. arXiv preprint arXiv:2309.16797, 2023. · arXiv
  19. Fu, Z.-H., Qiu, K.-B., and Zha, H. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 35, pp. 7474-7482, 2021.
  20. Glover, F. and Laguna, M. Tabu search. Springer, 1998.
  21. Guo, P.-F., Chen, Y.-H., Tsai, Y.-D., and Lin, S.-D. Towards optimizing with large language models. arXiv preprint arXiv:2310.05204, 2023a. · arXiv
  22. Guo, Q., Wang, R., Guo, J., Li, B., Song, K., Tan, X., Liu, G., Bian, J., and Yang, Y. Connecting large language mod- els with evolutionary algorithms yields powerful prompt optimizers. arXiv preprint arXiv:2309.08532, 2023b. · arXiv
  23. Gupta, J. N. A functional heuristic algorithm for the flow- shop scheduling problem. Journal of the Operational Research Society, 22:39-47, 1971.
  24. Hemberg, E., Moskal, S., and O'Reilly, U.-M. Evolv- ing code with a large language model. arXiv preprint arXiv:2401.07102, 2024. · arXiv
  25. Hudson, B., Li, Q., Malencia, M., and Prorok, A. Graph neural network guided local search for the traveling sales- person problem. arXiv preprint arXiv:2110.05291, 2021. · arXiv
  26. Hutter, F., Hoos, H. H., and Leyton-Brown, K. Sequential model-based optimization for general algorithm config- uration. In Learning and Intelligent Optimization: 5th International Conference, LION 5, Rome, Italy, January 17-21, 2011. Selected Papers 5, pp. 507-523. Springer, 2011.
  27. Jia, Y.-H., Mei, Y., and Zhang, M. Learning heuristics with different representations for stochastic routing. IEEE Transactions on Cybernetics, 2022.
  28. Joshi, C. K., Laurent, T., and Bresson, X. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019. · arXiv
  29. Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. Ad- vances in neural information processing systems, 35: 22199-22213, 2022.
  30. Kool, W., Van Hoof, H., and Welling, M. Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475, 2018. · arXiv
  31. Kool, W., van Hoof, H., Gromicho, J., and Welling, M. Deep policy dynamic programming for vehicle routing problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 19th International Conference, CPAIOR 2022, Los Angeles, CA, USA, June 20-23, 2022, Proceedings, pp. 190-213. Springer, 2022.
  32. Kwon, Y.-D., Choo, J., Kim, B., Yoon, I., Gwon, Y., and Min, S. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Informa- tion Processing Systems, 33:21188-21198, 2020.
  33. Kwon, Y.-D., Choo, J., Yoon, I., Park, M., Park, D., and Gwon, Y. Matrix encoding networks for neural combina- torial optimization. In Advances in Neural Information Processing Systems, 2021.
  34. Langdon, W. B. and Poli, R. Foundations of genetic pro- gramming. Springer Science & Business Media, 2013.
  35. Lehman, J., Gordon, J., Jain, S., Ndousse, K., Yeh, C., and Stanley, K. O. Evolution through large models. In Handbook of Evolutionary Machine Learning, pp. 331- 366. Springer, 2023.
  36. Lehman, J., Gordon, J., Jain, S., Ndousse, K., Yeh, C., and Stanley, K. O. Evolution Through Large Models, pp. 331-366. Springer Nature Singapore, Singapore, 2024.
  37. Li, N., Ma, L., Yu, G., Xue, B., Zhang, M., and Jin, Y. Sur- vey on evolutionary deep learning: Principles, algorithms, applications, and open issues. ACM Computing Surveys, 56(2):1-34, 2023a.
  38. Li, R., Allal, L. B., Zi, Y., Muennighoff, N., Kocetkov, D., Mou, C., Marone, M., Akiki, C., Li, J., Chim, J., et al. Starcoder: may the source be with you! arXiv preprint arXiv:2305.06161, 2023b. · arXiv
  39. Liu, F., Lin, X., Wang, Z., Yao, S., Tong, X., Yuan, M., and Zhang, Q. Large language model for multi-objective evo- lutionary optimization. arXiv preprint arXiv:2310.12541, 2023a. · arXiv
  40. Liu, F., Tong, X., Yuan, M., and Zhang, Q. Algorithm evolution using large language model. arXiv preprint arXiv:2311.15249, 2023b. · arXiv
  41. Liventsev, V., Grishina, A., Härmä, A., and Moonen, L. Fully autonomous programming with large language mod- els. arXiv preprint arXiv:2304.10423, 2023. · arXiv
  42. Long, J. Large language model guided tree-of-thought. arXiv preprint arXiv:2305.08291, 2023. · arXiv
  43. Lourenc ¸o, H. R., Martin, O. C., and Stützle, T. Iterated local search. In Handbook of metaheuristics, pp. 320-353. Springer, 2003.
  44. Luo, F., Lin, X., Liu, F., Zhang, Q., and Wang, Z. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. arXiv preprint arXiv:2310.07985, 2023. · arXiv
  45. Ma, Y. J., Liang, W., Wang, G., Huang, D.-A., Bastani, O., Jayaraman, D., Zhu, Y., Fan, L., and Anandkumar, A. Eureka: Human-level reward design via coding large lan- guage models. arXiv preprint arXiv:2310.12931, 2023. · arXiv
  46. Mahowald, K., Ivanova, A. A., Blank, I. A., Kanwisher, N., Tenenbaum, J. B., and Fedorenko, E. Dissociating lan- guage and thought in large language models: a cognitive perspective. arXiv preprint arXiv:2301.06627, 2023. · arXiv
  47. Malone, T. W. and Bernstein, M. S. Handbook of collective intelligence. MIT press, 2022.
  48. Mart, R., Pardalos, P. M., and Resende, M. G. Handbook of heuristics. Springer Publishing Company, Incorporated, 2018.
  49. Martello, S. and Toth, P. Lower bounds and reduction procedures for the bin packing problem. Discrete applied mathematics, 28(1):59-70, 1990.
  50. Matai, R., Singh, S. P., and Mittal, M. L. Traveling salesman problem: an overview of applications, formulations, and solution approaches. Traveling salesman problem, theory and applications, 1(1):1-25, 2010.
  51. Mei, Y., Chen, Q., Lensen, A., Xue, B., and Zhang, M. Ex- plainable artificial intelligence by genetic programming: A survey. IEEE Transactions on Evolutionary Computa- tion, 2022.
  52. Meyerson, E., Nelson, M. J., Bradley, H., Moradi, A., Hoover, A. K., and Lehman, J. Language model crossover: Variation through few-shot prompting. arXiv preprint arXiv:2302.12170, 2023. · arXiv
  53. Nasir, M. U., Earle, S., Togelius, J., James, S., and Cleghorn, C. Llmatic: Neural architecture search via large language models and quality-diversity optimization. arXiv preprint arXiv:2306.01102, 2023. · arXiv
  54. Naveed, H., Khan, A. U., Qiu, S., Saqib, M., Anwar, S., Usman, M., Barnes, N., and Mian, A. A comprehen- sive overview of large language models. arXiv preprint arXiv:2307.06435, 2023. · arXiv
  55. Nawaz, M., Enscore Jr, E. E., and Ham, I. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1):91-95, 1983.
  56. Pan, Z., Wang, L., Wang, J., and Lu, J. Deep reinforcement learning based optimization algorithm for permutation flow-shop scheduling. IEEE Transactions on Emerging Topics in Computational Intelligence, 2021.
  57. Qiu, R., Sun, Z., and Yang, Y. Dimes: A differentiable meta solver for combinatorial optimization problems. arXiv preprint arXiv:2210.04123, 2022. · arXiv
  58. Reinelt, G. Tsplib-a traveling salesman problem library. ORSA journal on computing, 3(4):376-384, 1991.
  59. Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J., Ellenberg, J. S., Wang, P., Fawzi, O., et al. Mathematical discoveries from program search with large language models. Nature, 625 (7995):468-475, 2024.
  60. Rosenkrantz, D. J., Stearns, R. E., and Lewis, II, P. M. An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3):563-581, 1977.
  61. Seiden, S. S. On the online bin packing problem. Journal of the ACM (JACM), 49(5):640-671, 2002.
  62. Sel, B., Al-Tawaha, A., Khattar, V., Wang, L., Jia, R., and Jin, M. Algorithm of thoughts: Enhancing explo- ration of ideas in large language models. arXiv preprint arXiv:2308.10379, 2023. · arXiv
  63. Shah, D., Equi, M. R., Osiński, B., Xia, F., Ichter, B., and Levine, S. Navigation with large language models: Se- mantic guesswork as a heuristic for planning. In Confer- ence on Robot Learning, pp. 2683-2699. PMLR, 2023.
  64. Stützle, T. and López-Ibáñez, M. Automated design of metaheuristic algorithms. Handbook of metaheuristics, pp. 541-579, 2019.
  65. Sui, J., Ding, S., Xia, B., Liu, R., and Bu, D. Neuralgls: learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Com- puting and Applications, pp. 1-20, 2023.
  66. Taillard, E. Benchmarks for basic scheduling problems. european journal of operational research, 64(2):278-285, 1993.
  67. Van Laarhoven, P. J., Aarts, E. H., van Laarhoven, P. J., and Aarts, E. H. Simulated annealing. Springer, 1987.
  68. Vinyals, O., Fortunato, M., and Jaitly, N. Pointer networks. Advances in neural information processing systems, 28, 2015.
  69. Voudouris, C. and Tsang, E. Guided local search and its application to the traveling salesman problem. European journal of operational research, 113(2):469-499, 1999.
  70. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D., et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35: 24824-24837, 2022.
  71. Wu, X., Zhong, Y., Wu, J., and Tan, K. C. As-llm: When algorithm selection meets large language model. arXiv preprint arXiv:2311.13184, 2023. · arXiv
  72. Wu, X., Wu, S.-h., Wu, J., Feng, L., and Tan, K. C. Evolu- tionary computation in the era of large language model: Survey and roadmap. arXiv preprint arXiv:2401.10034, 2024. · arXiv
  73. Xiao, H. and Wang, P. Llm a*: Human in the loop large language models enabled a* search for robotics. arXiv preprint arXiv:2312.01797, 2023. · arXiv
  74. Xin, L., Song, W., Cao, Z., and Zhang, J. Step-wise deep learning models for solving routing problems. IEEE Transactions on Industrial Informatics, 17(7):4861-4871, 2020.
  75. Xu, C., Sun, Q., Zheng, K., Geng, X., Zhao, P., Feng, J., Tao, C., and Jiang, D. Wizardlm: Empowering large language models to follow complex instructions. arXiv preprint arXiv:2304.12244, 2023a. · arXiv
  76. Xu, W., Banburski-Fahey, A., and Jojic, N. Reprompting: Automated chain-of-thought prompt inference through gibbs sampling. arXiv preprint arXiv:2305.09993, 2023b. · arXiv
  77. Yang, C., Wang, X., Lu, Y., Liu, H., Le, Q. V., Zhou, D., and Chen, X. Large language models as optimizers. arXiv preprint arXiv:2309.03409, 2023. · arXiv
  78. Yao, Y., Li, Z., and Zhao, H. Beyond chain-of-thought, effective graph-of-thought reasoning in large language models. arXiv preprint arXiv:2305.16582, 2023. · arXiv
  79. Zhang, F., Mei, Y., Nguyen, S., and Zhang, M. Survey on genetic programming and machine learning techniques for heuristic design in job shop scheduling. IEEE Trans- actions on Evolutionary Computation, 2023.
  80. Zhao, Z., Lee, W. S., and Hsu, D. Large language models as commonsense knowledge for large-scale task planning. arXiv preprint arXiv:2305.14078, 2023. · arXiv

Cited by

Sorted by citations

Authors
Liu, F., Tong, X., Yuan, M., Lin, X., Luo, F., Wang, Z., Lu, Z., & Zhang, Q.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2024
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2401.02051
arXiv
2401.02051
OpenAlex
W4390647620
Cited by
14
References
0
Citations by year
2026: 2 · 2025: 6 · 2024: 6
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • City University of Hong Kong
  • National Natural Science Foundation of China (62106096)
  • Natural Science Foundation of Guangdong Province
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
  • Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
  • Physical Sciences › Computer Science › Information Systems › Software Engineering Research
Keywords
large language models, evolutionary computation, heuristic evolution, combinatorial optimization, online bin packing

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review