1. State Key Lab of Processor, Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China 2. University of Chinese Academy of Sciences, Beijing 100190, China 3. Central China Institute of Artificial Intelligence, Zhengzhou 450046, China 4. Henan Institute of Advanced Technology, Zhengzhou University, Zhengzhou 450002, China 5. Hangzhou Institute for Advanced Study, UCAS, Hangzhou 310024, China
This paper presents an overview of deep learning (DL)-based algorithms designed for solving the traveling salesman problem (TSP), categorizing them into four categories: end-to-end construction algorithms, end-to-end improvement algorithms, direct hybrid algorithms, and large language model (LLM)-based hybrid algorithms. We introduce the principles and methodologies of these algorithms, outlining their strengths and limitations through experimental comparisons. End-to-end construction algorithms employ neural networks to generate solutions from scratch, demonstrating rapid solving speed but often yielding subpar solutions. Conversely, end-to-end improvement algorithms iteratively refine initial solutions, achieving higher-quality outcomes but necessitating longer computation times. Direct hybrid algorithms directly integrate deep learning with heuristic algorithms, showcasing robust solving performance and generalization capability. LLM-based hybrid algorithms leverage LLMs to autonomously generate and refine heuristics, showing promising performance despite being in early developmental stages. In the future, further integration of deep learning techniques, particularly LLMs, with heuristic algorithms and advancements in interpretability and generalization will be pivotal trends in TSP algorithm design. These endeavors aim to tackle larger and more complex real-world instances while enhancing algorithm reliability and practicality. This paper offers insights into the evolving landscape of DL-based TSP solving algorithms and provides a perspective for future research directions.
randomly generated with node coordinates in the unit square
TSPLIB
14 – 85900
from various sources and of various types in the real world
Tab.1
Algorithm
Category
TSP20
TSP50
TSP100
Gap/%
Time/s
Gap/%
Time/s
Gap/%
Time/s
Heuristic
Concorde [36]
0.000
0.010
0.000
0.051
0.000
0.224
Nearest Neighbor [37]
17.448
0.000
23.230
0.001
25.104
0.006
Farthest Insertion [37]
2.242
0.002
7.263
0.022
12.456
0.174
Local Search [35]
1.824
0.007
3.358
0.086
4.169
0.574
LKH-3 [45] (1 trail)
0.000
0.001
0.009
0.017
0.022
0.050
LKH-3 [45] (10 trails)
0.000
0.001
0.004
0.021
0.011
0.065
LKH-3 [45] (100 trails)
0.000
0.002
0.001
0.062
0.002
0.212
DL-based algorithm
Kool et al. [50]
C
0.068
0.026
0.494
0.065
2.359
0.167
Costa et al. [63]
I
0.001
0.464
0.134
0.637
0.758
0.931
Joshi et al. [65]
D
0.035
0.974
0.227
2.261
1.516
4.327
Hudson et al. [66]
D
0.000
10.008
0.002
10.048
0.454
10.175
Xin et al. [71] (1 trail)
D
?
?
0.001
0.008
0.009
0.018
Xin et al. [71] (10 trails)
D
?
?
0.000
0.010
0.003
0.027
Xin et al. [71] (100 trails)
D
?
?
0.000
0.037
0.001
0.118
Ye et al. [74]
L
0.000
0.007
0.000
0.089
0.004
0.393
Tab.2
Fig.28
Fig.29
TSP
Kool et al. [50]
Costa et al. [63]
Joshi et al. [65]
Hudson et al. [66]
Xin et al. [71]
Ye et al. [74]
Gap/%
Time/s
Gap/%
Time/s
Gap/%
Time/s
Gap/%
Time/s
Gap/%
Time/s
Gap/%
Time/s
eil51
1.692
0.069
0.394
523.907
8.341
2.414
0.000
10.044
0.000
0.114
2.346
0.001
berlin52
17.953
0.073
1.743
531.19
41.694
2.377
0.000
10.053
0.000
0.070
3.862
0.001
st70
1.930
0.117
1.004
845.866
33.836
3.108
0.000
10.040
0.000
0.083
2.316
0.002
eil76
2.525
0.128
0.693
656.161
5.682
3.432
0.000
10.097
0.000
0.071
1.846
0.001
pr76
2.810
0.124
0.445
677.782
17.893
3.344
0.000
10.043
0.000
0.155
1.506
0.001
rat99
5.843
0.167
1.064
803.023
20.747
4.19
0.056
10.816
0.000
0.098
4.873
0.004
kroA100
6.674
0.161
2.918
749.98
0.774
4.357
0.042
10.885
0.000
0.117
2.534
0.003
kroB100
8.232
0.169
0.732
750.806
18.792
4.393
0.263
10.716
0.000
0.174
0.585
0.003
kroC100
6.127
0.175
0.946
758.839
1.111
4.409
0.000
10.776
0.000
0.103
5.573
0.003
kroD100
5.637
0.168
1.049
754.058
11.206
4.338
0.000
10.762
0.000
0.127
3.851
0.004
kroE100
3.939
0.163
1.163
710.341
23.053
4.439
0.983
10.818
0.000
0.133
4.352
0.005
rd100
3.366
0.169
0.371
763.456
0.057
4.445
0.077
10.793
0.000
0.092
2.950
0.005
eil101
2.526
0.173
1.390
771.908
0.426
4.542
0.519
10.792
0.000
0.097
1.302
0.003
lin105
16.414
0.190
1.935
783.738
85.133
4.601
0.161
10.190
0.000
0.098
0.734
0.004
pr107
8.004
0.183
28.617
784.38
47.583
4.592
1.033
10.286
0.000
2.051
0.617
0.003
pr124
4.350
0.226
0.629
821.876
24.467
5.407
1.367
10.218
0.000
0.561
1.890
0.004
bier127
9.253
0.231
4.953
854.601
36.361
5.517
2.878
10.092
0.027
0.194
1.299
0.004
ch130
3.228
0.242
1.178
887.715
11.329
5.501
1.498
10.044
0.000
0.310
5.985
0.004
pr136
4.961
0.285
0.856
901.362
36.47
5.812
1.893
11.850
0.000
0.932
6.789
0.006
pr144
11.274
0.288
1.218
805.555
49.799
6.187
1.519
12.197
0.000
0.823
1.281
0.005
ch150
4.475
0.318
1.325
994.263
28.499
6.529
0.930
10.425
0.000
0.406
2.110
0.006
kroA150
12.380
0.318
2.396
964.421
31.413
6.479
2.174
10.112
0.000
0.397
7.097
0.006
kroB150
8.431
0.313
2.777
981.929
55.122
6.443
2.142
10.281
0.000
0.313
3.720
0.016
pr152
10.478
0.306
5.793
857.961
54.053
6.605
5.473
10.896
0.000
2.613
1.892
0.006
u159
8.799
0.331
0.823
982.689
37.904
6.952
0.207
10.398
0.000
0.165
5.962
0.283
rat195
16.879
0.478
5.340
1259.682
42.35
8.684
2.843
11.714
0.000
1.006
1.089
0.015
d198
434.654
0.474
31.723
1128.726
51.979
8.492
7.814
10.912
0.360
1.201
2.039
0.010
kroA200
15.661
0.495
6.224
1206.469
40.861
8.77
2.481
10.754
0.000
0.321
0.861
0.014
kroB200
18.612
0.477
5.606
1196.682
46.528
9.062
1.881
10.355
0.000
0.243
5.511
0.016
Mean
22.659
0.242
3.976
852.047
29.775
5.359
1.318
10.599
0.013
0.451
2.992
0.015
Tab.3
Fig.30
Algorithm
Category
Model trained on TSP20
TSP20
TSP50
TSP100
TSP200
Gap/%
Time/s
Gap/%
Time/s
Gap/%
Time/s
Gap/%
Time/s
Kool et al. [50]
C
0.068
0.026
1.806
0.062
22.525
0.158
66.220
0.480
Costa et al. [63]
I
0.001
0.464
2.482
0.802
23.181
1.071
94.452
1.879
Joshi et al. [65]
D
0.035
0.974
28.892
9.176
66.655
13.264
149.489
21.563
Hudson et al. [66]
D
0.000
10.008
0.093
10.029
2.112
10.010
6.365
10.852
Tab.4
Algorithm
Category
Model trained on TSP50
TSP50
TSP100
TSP200
Gap/%
Time/s
Gap/%
Time/s
Gap/%
Time/s
Kool et al. [50]
C
0.494
0.065
2.876
0.160
20.541
0.480
Costa et al. [63]
I
0.134
0.637
1.404
1.074
7.824
1.801
Joshi et al. [65]
D
0.227
2.261
49.581
13.197
95.421
21.637
Hudson et al. [66]
D
0.002
10.048
1.028
10.091
5.765
10.632
Tab.5
Algorithm
Cateroty
Model trained on TSP100
TSP100
TSP200
Gap/%
Time/s
Gap/%
Time/s
Kool et al. [50]
C
2.359
0.167
6.785
0.479
Costa et al. [63]
I
0.758
0.931
2.785
1.676
Joshi et al. [65]
D
1.516
4.327
49.477
21.592
Hudson et al. [66]
D
0.454
10.175
3.285
10.422
Tab.6
1
W J Cook . In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton: Princeton University Press, 2012
2
Maire B F J, La V M Mladenov . Comparison of neural networks for solving the travelling salesman problem. In: Proceedings of the 11th Symposium on Neural Network Applications in Electrical Engineering. 2012, 21–24
3
Y, LeCun Y, Bengio G Hinton . Deep learning. Nature, 2015, 521( 7553): 436–444
4
K, Wei T, Li F, Huang J, Chen Z He . Cancer classification with data augmentation based on generative adversarial networks. Frontiers of Computer Science, 2022, 16( 2): 162601
5
H, Shi J, Wang J, Cheng X, Qi H, Ji C J, Struchiner D A M, Villela E V, Karamov A S Turgiev . Big data technology in infectious diseases modeling, simulation, and prediction after the COVID-19 outbreak. Intelligent Medicine, 2023, 3( 2): 85–96
6
Y, Wu P, Zhang H, Shen H Zhai . Visualizing a neural network that develops quantum perturbation theory. Physical Review A, 2018, 98( 1): 010701(R)
N, Sun J, Yi P, Zhang H, Shen H Zhai . Deep learning topological invariants of band insulators. Physical Review B, 2018, 98( 8): 085402
9
J, Jumper R, Evans A, Pritzel T, Green M, Figurnov O, Ronneberger K, Tunyasuvunakool R, Bates A, Žídek A, Potapenko A, Bridgland C, Meyer S A A, Kohl A J, Ballard A, Cowie B, Romera-Paredes S, Nikolov R, Jain J, Adler T, Back S, Petersen D, Reiman E, Clancy M, Zielinski M, Steinegger M, Pacholska T, Berghammer S, Bodenstein D, Silver O, Vinyals A W, Senior K, Kavukcuoglu P, Kohli D Hassabis . Highly accurate protein structure prediction with AlphaFold. Nature, 2021, 596( 7873): 583–589
10
K, Tunyasuvunakool J, Adler Z, Wu T, Green M, Zielinski A, Žídek A, Bridgland A, Cowie C, Meyer A, Laydon S, Velankar G J, Kleywegt A, Bateman R, Evans A, Pritzel M, Figurnov O, Ronneberger R, Bates S A A, Kohl A, Potapenko A J, Ballard B, Romera-Paredes S, Nikolov R, Jain E, Clancy D, Reiman S, Petersen A W, Senior K, Kavukcuoglu E, Birney P, Kohli J, Jumper D Hassabis . Highly accurate protein structure prediction for the human proteome. Nature, 2021, 596( 7873): 590–596
11
M, Baek F, DiMaio I, Anishchenko J, Dauparas S, Ovchinnikov G R, Lee J, Wang Q, Cong L N, Kinch R D, Schaeffer C, Millán H, Park C, Adams C R, Glassman A, Degiovanni J H, Pereira A V, Rodrigues Dijk A A, Van A C, Ebrecht D J, Opperman T, Sagmeister C, Buhlheller T, Pavkov-Keller M K, Rathinaswamy U, Dalwadi C K, Yip J E, Burke K C, Garcia N V, Grishin P D, Adams R J, Read D Baker . Accurate prediction of protein structures and interactions using a three-track neural network. Science, 2021, 373( 6557): 871–876
12
F, Ju J, Zhu B, Shao L, Kong T Y, Liu W M, Zheng D Bu . CopulaNet: learning residue co-evolution directly from multiple sequence alignment for protein structure prediction. Nature Communications, 2021, 12( 1): 2535
13
A, Davies P, Veličković L, Buesing S, Blackwell D, Zheng N, Tomašev R, Tanburn P, Battaglia C, Blundell A, Juhász M, Lackenby G, Williamson D, Hassabis P Kohli . Advancing mathematics by guiding human intuition with AI. Nature, 2021, 600( 7887): 70–74
14
A, Fawzi M, Balog A, Huang T, Hubert B, Romera-Paredes M, Barekatain A, Novikov F J R, Ruiz J, Schrittwieser G, Swirszcz D, Silver D, Hassabis P Kohli . Discovering faster matrix multiplication algorithms with reinforcement learning. Nature, 2022, 610( 7930): 47–53
15
W, Tenachi R, Ibata F I Diakogiannis . Deep symbolic regression for physics guided by units constraints: toward the automated discovery of physical laws. The Astrophysical Journal, 2023, 959( 2): 99
16
B, Romera-Paredes M, Barekatain A, Novikov M, Balog M P, Kumar E, Dupont F J R, Ruiz J S, Ellenberg P, Wang O, Fawzi P, Kohli A Fawzi . Mathematical discoveries from program search with large language models. Nature, 2024, 625( 7995): 468–475
17
N, Wu J, Wang W X, Zhao Y Jin . Learning to effectively estimate the travel time for fastest route recommendation. In: Proceedings of the 28th ACM International Conference on Information and Knowledge Management. 2019, 1923–1932
18
N, Wu X W, Zhao J, Wang D Pan . Learning effective road network representation with hierarchical graph neural networks. In: Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020, 6–14
19
J, Ji J, Wang Z, Jiang J, Ma H Zhang . Interpretable spatiotemporal deep learning model for traffic flow prediction based on potential energy fields. In: Proceedings of IEEE International Conference on Data Mining. 2020, 1076–1081
20
J, Wang N, Wu W X Zhao . Personalized route recommendation with neural network enhanced search algorithm. IEEE Transactions on Knowledge and Data Engineering, 2022, 34( 12): 5910–5924
21
Z, Wang Z, Pan S, Chen S, Ji X, Yi J, Zhang J, Wang Z, Gong T, Li Y Zheng . Shortening passengers’ travel time: a dynamic metro train scheduling approach using deep reinforcement learning. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 5): 5282–5295
22
J, Wang J, Ji Z, Jiang L Sun . Traffic flow prediction based on spatiotemporal potential energy fields. IEEE Transactions on Knowledge and Data Engineering, 2023, 35( 9): 9073–9087
23
J, Ji J, Wang C, Huang J, Wu B, Xu Z, Wu J, Zhang Y Zheng . Spatio-temporal self-supervised learning for traffic flow prediction. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence. 2023, 4356–4364
24
Y, Bengio A, Lodi A Prouvost . Machine learning for combinatorial optimization: a methodological tour d’horizon. European Journal of Operational Research, 2021, 290( 2): 405–421
25
Mele U, Junior Gambardella L, Maria R Montemanni . Machine learning approaches for the traveling salesman problem: a survey. In: Proceedings of the 8th International Conference on Industrial Engineering and Applications (Europe). 2021, 182–186
26
Y, Shi Y Zhang . The neural network methods for solving traveling salesman problem. Procedia Computer Science, 2022, 199: 681–686
27
Y, Yang A Whinston . A survey on reinforcement learning for combinatorial optimization. In: Proceedings of IEEE World Conference on Applied Intelligence and Computing. 2023, 131–136
28
R, Matai S P, Singh M L Mittal . Traveling salesman problem: an overview of applications, formulations, and solution approaches. In: Davendra D, ed. Traveling Salesman Problem, Theory and Applications. Rijeka: InTech, 2010, 1
29
W L Eastman . Linear programming with pattern constraints. Harvard University, Dissertation, 1958
30
D L, Miller J F Pekny . Exact solution of large asymmetric traveling salesman problems. Science, 1991, 251( 4995): 754–761
31
M, Held R M Karp . A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 1962, 10( 1): 196–210
32
G Laporte . The traveling salesman problem: an overview of exact and approximate algorithms. European Journal of Operational Research, 1992, 59( 2): 231–247
33
G, Dantzig R, Fulkerson S Johnson . Solution of a large-scale traveling-salesman problem. Journal of the Operations Research Society of America, 1954, 2( 4): 393–410
34
C E, Miller A W, Tucker R A Zemlin . Integer programming formulation of traveling salesman problems. Journal of the ACM, 1960, 7( 4): 326–329
35
G, Gutin A P Punnen . The Traveling Salesman Problem and Its Variations. New York: Springer, 2007
36
D, Applegate R, Bixby V, Chvatal W Cook . Concorde TSP solver. See Math. uwaterloo. ca/tsp/concorde website, 2006
37
D J, Rosenkrantz R E, Stearns II P M Lewis . An analysis of several heuristics for the traveling salesman problem. SIAM Journal on Computing, 1977, 6( 3): 563–581
38
D S, Johnson L A McGeoch . The traveling salesman problem: a case study in local optimization. Local Search in Combinatorial Optimization, 1997, 1( 1): 215–310
39
C, Voudouris E Tsang . Guided local search and its application to the traveling salesman problem. European Journal of Operational Research, 1999, 113( 2): 469–499
40
C Nilsson . Heuristics for the traveling salesman problem. Linkoping University, 2003, 38( 0085-9): 26
41
J, Sui S, Ding R, Liu L, Xu D Bu . Learning 3-opt heuristics for traveling salesman problem via deep reinforcement learning. In: Proceedings of the 13th Asian Conference on Machine Learning. 2021, 1301–1316
42
D S Johnson . Local optimization and the traveling salesman problem. In: Proceedings of the 17th International Colloquium on Automata, Languages, and Programming. 1990, 446–461
43
K Helsgaun . An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 2000, 126( 1): 106–130
44
K Helsgaun . General k-opt submoves for the Lin-Kernighan TSP heuristic. Mathematical Programming Computation, 2009, 1( 2-3): 119–163
45
K Helsgaun . An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems: technical report. Roskilde: Roskilde University, 2017, 966–980
46
O, Vinyals M, Fortunato N Jaitly . Pointer networks. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. 2015, 2692–2700
47
I, Bello H, Pham Q V, Le M, Norouzi S Bengio . Neural combinatorial optimization with reinforcement learning. In: Proceedings of the 5th International Conference on Learning Representations. 2017
48
M, Nazari A, Oroojlooy M, Takáč L Snyder . Reinforcement learning for solving the vehicle routing problem. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018, 9861–9871
49
M, Deudon P, Cournut A, Lacoste Y, Adulyasak L M Rousseau . Learning heuristics for the TSP by policy gradient. In: Proceedings of the 15th International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research. 2018, 170–181
50
W, Kool Hoof H, Van M Welling . Attention, learn to solve routing problems!2018, arXiv preprint arXiv: 1803.08475
51
Y D, Kwon J, Choo B, Kim I, Yoon Y, Gwon S Min . POMO: policy optimization with multiple optima for reinforcement learning. In: Proceedings of the 34th Conference on Neural Information Processing Systems. 2020, 21188–21198
52
X, Bresson T Laurent . The transformer network for the traveling salesman problem. 2021, arXiv preprint arXiv: 2103.03012
53
X, Pan Y, Jin Y, Ding M, Feng L, Zhao L, Song J Bian . H-TSP: hierarchically solving the large-scale traveling salesman problem. In: Proceedings of the 37th AAAI Conference on Artificial Intelligence. 2023, 9345–9353
54
A, Lischka J, Wu R, Basso M H, Chehreghani B Kulcsár . Less is more-on the importance of sparsification for transformers and graph neural networks for TSP. 2024, arXiv preprint arXiv: 2403.17159
55
F, Luo X, Lin F, Liu Q, Zhang Z Wang . Neural combinatorial optimization with heavy decoder: toward large scale generalization. In: Proceedings of the 37th Conference on Neural Information Processing Systems. 2024
56
H, Dai E B, Khalil Y, Zhang B, Dilkina L Song . Learning combinatorial optimization algorithms over graphs. In: Proceedings of the 31st Conference on Neural Information Processing Systems. 2017, 30
57
Q, Ma S, Ge D, He D, Thaker I Drori . Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. 2019, arXiv preprint arXiv: 1911.04936
58
I, Drori A, Kharkar W R, Sickinger B, Kates Q, Ma S, Ge E, Dolev B, Dietrich D P, Williamson M Udell . Learning to solve combinatorial optimization problems on real-world graphs in linear time. In: Proceedings of the 19th IEEE International Conference on Machine Learning and Applications. 2020, 19–24
59
W, Ouyang Y, Wang P, Weng S Han . Generalization in deep RL for TSP problems via equivariance and local search. 2021, arXiv preprint arXiv: 2110.03595
60
Z, Sun Y Yang . DIFUSCO: graph-based diffusion solvers for combinatorial optimization. In: Proceedings of the 37th International Conference on Neural Information Processing Systems. 2023, 164
61
H, Liu Y, Kuang J, Wang X, Li Y, Zhang F Wu . Promoting generalization for exact solvers via adversarial instance augmentation. 2023, arXiv preprint arXiv: 2310.14161
62
Y, Wu W, Song Z, Cao J, Zhang A Lim . Learning improvement heuristics for solving routing problems. 2019, arXiv preprint arXiv: 1912.05784
63
P R D O, Costa J, Rhuggenaath Y, Zhang A Akcay . Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In: Proceedings of the 12th Asian Conference on Machine Learning. 2020, 465–480
64
Y, Ma J, Li Z, Cao W, Song L, Zhang Z, Chen J Tang . Learning to iteratively solve routing problems with dual-aspect collaborative transformer. In: Proceedings of the 34th Conference on Neural Information Processing Systems. 2021, 11096–11107
65
C K, Joshi T, Laurent X Bresson . An efficient graph convolutional network technique for the travelling salesman problem. 2019, arXiv preprint arXiv: 1906.01227
66
B, Hudson Q, Li M, Malencia A Prorok . Graph neural network guided local search for the traveling salesperson problem. 2021, arXiv preprint arXiv: 2110.05291
67
J, Sui S, Ding B, Xia R, Liu D Bu . NeuralGLS: learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Computing and Applications, 2024, 36( 17): 9687–9706
68
Z H, Fu K B, Qiu H Zha . Generalize a small pre-trained model to arbitrarily large TSP instances. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021, 7474–7482
69
S, Sanyal K Roy . Neuro-Ising: accelerating large-scale traveling salesman problems via graph neural network guided localized Ising solvers. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022, 41( 12): 5408–5420
70
J, Zheng K, He J, Zhou Y, Jin C M Li . Combining reinforcement learning with Lin-Kernighan-Helsgaun algorithm for the traveling salesman problem. In: Proceedings of the 35th AAAI Conference on Artificial Intelligence. 2021, 12445–12452
71
L, Xin W, Song Z, Cao J Zhang . NeuroLKH: combining deep learning model with Lin-Kernighan-Helsgaun heuristic for solving the traveling salesman problem. In: Proceedings of the 35th International Conference on Neural Information Processing Systems. 2021, 572
72
J, Zheng K, He J, Zhou Y, Jin C M Li . Reinforced Lin–Kernighan–Helsgaun algorithms for the traveling salesman problems. Knowledge-Based Systems, 2023, 260: 110144
73
F, Liu X, Tong M, Yuan Q Zhang . Algorithm evolution using large language model. 2023, arXiv preprint arXiv: 2311.15249
74
H, Ye J, Wang Z, Cao F, Berto C, Hua H, Kim J, Park G Song . Large language models as hyper-heuristics for combinatorial optimization. 2024, arXiv preprint arXiv: 2402.01145
75
F, Liu X, Tong M, Yuan X, Lin F, Luo Z, Wang Z, Lu Q Zhang . Evolution of heuristics: towards efficient automatic algorithm design using large language mode. 2024, arXiv preprint arXiv: 2401.02051
76
D, Bahdanau K, Cho Y Bengio . Neural machine translation by jointly learning to align and translate. In: Proceedings of the 3rd International Conference on Learning Representations. 2015
77
R Sato . A survey on the expressive power of graph neural networks. 2020, arXiv preprint arXiv: 2003.04078
78
A, Vaswani N, Shazeer N, Parmar J, Uszkoreit L, Jones A N, Gomez Ł, Kaiser I Polosukhin . Attention is all you need. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017, 6000–6010
79
H, Naveed A U, Khan S, Qiu M, Saqib S, Anwar M, Usman N, Akhtar N, Barnes A Mian . A comprehensive overview of large language models. 2024, arXiv preprint arXiv: 2307.06435
80
D Hu . An introductory survey on attention mechanisms in NLP problems. In: Proceedings of Intelligent Systems Conference (IntelliSys) Volume 2. 2020, 432–448
81
M T, Luong H, Pham C D Manning . Effective approaches to attention-based neural machine translation. In: Proceedings of 2015 Conference on Empirical Methods in Natural Language Processing. 2015
82
A, Sperduti A Starita . Supervised neural networks for the classification of structures. IEEE Transactions on Neural Networks, 1997, 8( 3): 714–735
83
I I, Baskin V A, Palyulin N S Zefirov . A neural device for searching direct correlations between structures and properties of chemical compounds. Journal of Chemical Information and Computer Sciences, 1997, 37( 4): 715–721
84
M, Gori G, Monfardini F Scarselli . A new model for learning in graph domains. In: Proceedings of IEEE International Joint Conference on Neural Networks. 2005, 729–734
85
F, Scarselli M, Gori A C, Tsoi M, Hagenbuchner G Monfardini . The graph neural network model. IEEE Transactions on Neural Networks, 2009, 20( 1): 61–80
86
D, Duvenaud D, Maclaurin J, Aguilera-Iparraguirre R, Gómez-Bombarelli T, Hirzel A, Aspuru-Guzik R P Adams . Convolutional networks on graphs for learning molecular fingerprints. In: Proceedings of the 28th International Conference on Neural Information Processing Systems. 2015
87
Y, Li D, Tarlow M, Brockschmidt R S Zemel . Gated graph sequence neural networks. In: Proceedings of the 4th International Conference on Learning Representations. 2016
88
H, Dai B, Dai L Song . Discriminative embeddings of latent variable models for structured data. In: Proceedings of the 33rd International Conference on Machine Learning. 2016, 2702–2711
89
J, Gilmer S S, Schoenholz P F, Riley O, Vinyals G E Dahl . Neural message passing for quantum chemistry. In: Proceedings of the 34th International Conference on Machine Learning. 2017, 1263–1272
90
W L, Hamilton R, Ying J Leskovec . Inductive representation learning on large graphs. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017, 1025–1035
91
T N, Kipf M Welling . Semi-supervised classification with graph convolutional networks. In: Proceedings of the 5th International Conference on Learning Representations. 2017
P, Velickovic G, Cucurull A, Casanova A, Romero P, Liò Y Bengio . Graph attention networks. In: Proceedings of the 6th International Conference on Learning Representations. 2018
94
W X, Zhao K, Zhou J, Li T, Tang X, Wang Y, Hou Y, Min B, Zhang J, Zhang Z, Dong Y, Du C, Yang Y, Chen Z, Chen J, Jiang R, Ren Y, Li X, Tang Z, Liu P, Liu J Y, Nie J R Wen . A survey of large language models. 2023, arXiv preprint arXiv: 2303.18223
95
B, Min H, Ross E, Sulem A P B, Veyseh T H, Nguyen O, Sainz E, Agirre I, Heinz D Roth . Recent advances in natural language processing via large pre-trained language models: a survey. ACM Computing Surveys, 2024, 56( 2): 30
96
Tian H, Lu W, Li T O, Tang X, Cheung S C, Klein J, Bissyandé T F. Is ChatGPT the ultimate programming assistant-how far is it? 2023, arXiv preprint arXiv: 2304.11938
97
K M, Jablonka P, Schwaller A, Ortega-Guerrero B Smit . Is GPT-3 all you need for low-data discovery in chemistry? See Chemrxiv. org/engage/chemrxiv/article-details/63eb5a669da0bc6b33e97a35 website, 2023
98
P, Lee S, Bubeck J Petro . Benefits, limits, and risks of GPT-4 as an AI chatbot for medicine. New England Journal of Medicine, 2023, 388( 13): 1233–1239
99
H, Nori N, King S M, McKinney D, Carignan E Horvitz . Capabilities of GPT-4 on medical challenge problems. 2023, arXiv preprint arXiv: 2303.13375
100
K, Cheng Q, Guo Y, He Y, Lu S, Gu H Wu . Exploring the potential of GPT-4 in biomedical engineering: the dawn of a new era. Annals of Biomedical Engineering, 2023, 51( 8): 1645–1653
101
J, Blocklove S, Garg R, Karri H Pearce . Chip-chat: challenges and opportunities in conversational hardware design. In: Proceedings of the 5th ACM/IEEE Workshop on Machine Learning for CAD. 2023, 1–6
102
Z, He H, Wu X, Zhang X, Yao S, Zheng H, Zheng B Yu . ChatEDA: a large language model powered autonomous agent for EDA. 2023, arXiv preprint arXiv: 2308.10204
103
D, Shah M R, Equi B, Osiński F, Xia B, Ichter S Levine . Navigation with large language models: semantic guesswork as a heuristic for planning. In: Proceedings of the 7th Conference on Robot Learning. 2023
104
H, Xiao P Wang . LLM A*: human in the loop large language models enabled A* search for robotics. 2023, arXiv preprint arXiv: 2312.01797
105
C, Yang X, Wang Y, Lu H, Liu Q V, Le D, Zhou X Chen . Large language models as optimizers. In: Proceedings of ICLR 2024 Conference. 2024
106
X, Wu Y, Zhong J, Wu B, Jiang K C Tan . Large language model-enhanced algorithm selection: towards comprehensive algorithm representation. In: Proceedings of the 33rd International Joint Conference on Artificial Intelligence. 2024
107
F, Liu X, Lin Z, Wang S, Yao X, Tong M, Yuan Q Zhang . Large language model for multi-objective evolutionary optimization. 2024, arXiv preprint arXiv: 2310.12541
108
I, Sutskever O, Vinyals Q V Le . Sequence to sequence learning with neural networks. In: Proceedings of the 27th International Conference on Neural Information Processing Systems. 2014, 3104–3112
109
D E, Rumelhart G E, Hinton R J Williams . Learning representations by back-propagating errors. Nature, 1986, 323( 6088): 533–536
V, Mnih A P, Badia M, Mirza A, Graves T, Harley T P, Lillicrap D, Silver K Kavukcuoglu . Asynchronous methods for deep reinforcement learning. In: Proceedings of the 33rd International Conference on Machine Learning. 2016, 1928–1937
112
N Christofides . Worst-case analysis of a new heuristic for the travelling salesman problem. Pittsburgh: Carnegie-Mellon University, 1976
113
Perron L, Furnon V. OR-Tools. See developers.google.com/optimization/ website. 2023
114
R J Williams . Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine Learning, 1992, 8( 3-4): 229–256
115
D P, Kingma J Ba . Adam: a method for stochastic optimization. In: Proceedings of the 3rd International Conference on Learning Representations. 2015
116
R S, Sutton A G Barto . Reinforcement learning: an introduction. Robotica, 1999, 17( 2): 229–235
117
G Reinelt . TSPLIB—A traveling salesman problem library. ORSA Journal on Computing, 1991, 3( 4): 376–384
118
J, Ho A, Jain P Abbeel . Denoising diffusion probabilistic models. In: Proceedings of the 34th International Conference on Neural Information Processing Systems. 2020, 574
119
E, Perez F, Strub Vries H, De V, Dumoulin A Courville . FiLM: visual reasoning with a general conditioning layer. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence. 2018
120
A Misevičius . Using iterated Tabu search for the traveling salesman problem. Information Technology and Control, 2004, 32( 3): 29–40
121
P A Vikhar . Evolutionary algorithms: a critical review and its future prospects. In: Proceedings of International Conference on Global Trends in Signal Processing, Information Computing and Communication. 2016, 261–265
122
F, Arnold K Sörensen . Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 2019, 105: 32–46
