DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization
Authors: Haoran Ye
Jiarui Wang
Zhiguang Cao
Helan Liang
Yong Li
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural Combinatorial Optimization
Ant Colony Optimization
Evolutionary algorithm
Meta-heuristic
Deep reinforcement learning
Learned heuristic measure
Neural local search
Generalization
TL;DR: We propose a neural-enhanced version of Ant Colony Optimization meta-heuristic for Combinatorial Optimization.

Abstract: Ant Colony Optimization (ACO) is a meta-heuristic algorithm that has been successfully applied to various Combinatorial Optimization Problems (COPs). Traditionally, customizing ACO for a specific problem requires the expert design of knowledge-driven heuristics. In this paper, we propose DeepACO, a generic framework that leverages deep reinforcement learning to automate heuristic designs. DeepACO serves to strengthen the heuristic measures of existing ACO algorithms and dispense with laborious manual design in future ACO applications. As a neural-enhanced meta-heuristic, DeepACO consistently outperforms its ACO counterparts on eight COPs using a single neural model and a single set of hyperparameters. As a Neural Combinatorial Optimization method, DeepACO performs better than or on par with problem-specific methods on canonical routing problems. Our code is publicly available at https://github.com/henry-yeh/DeepACO.

DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization
Haoran Ye', Jiarui Wang', Zhiguang Cao*', Helan Liang", Yong Li
School of Computer Science & Technology, Soochow University
2 School of Computing and Information Systems, Singapore Management University
Department of Electronic Engineering, Tsinghua University [hrye, caraannguuffffo000ssme suda. edu. en, zgcao@smu. edu.sg, hlliangOsuda, edu. en, 1iyong07@t:sinhhaa edu. cn
Abstract
Ant Colony Optimization (ACO) is meta-heuristic algorithm that has been cessfully applied to various Combinatorial Optimization Problems (COPs). Tra- ditionally, customizing ACO for a specific problem requires the expert design of knowledge-driven heuristics. In this paper, we propose DeepACO, generic frame- work that leverages deep reinforcement learning to automate heuristic designs. DeepACO serves to strengthen the heuristic measures of existing ACO algorithms and dispense with laborious manual design future ACO applications. As a neural- enhanced meta-heuristic DeepACO consistently outperforms its ACO counterparts on eight COPs using single neural model and a single set hyperparameters. As Neural Combinatorial Optimization method, DeepACO performs better than on par with problem-specific methods on canonical routing problems. Our code publicly available at https:///ithub www///nrryyyc/eeeeeeeeeee
Introduction
Ant systems in nature self-learners. They utilize chemical signals and environmental cues to locate and return food to the colony. The pheromone trails deposited by ants indicate the quality and distance of food source. The intensity of pheromone trails increases as more visit and decreases due to evaporation, creating a self-learning foraging system.
Inspired by the ant systems in nature, researchers propose and develop Ant Colony Optimization (ACO) meta- hcuristics for (but not limited to) Combinatorial Optimization Problems (COPs) [24, 26]. ACO deploys population of artificial ants explore the solution space through repeated solution constructions and pheromone updates. The exploration is biased toward more promising areas through instance-spest pheromone trails and problem-specift. heuristic measures. Both the pheromone trail and the heuristic measure indicate how promising a solution component is. Typically, pheromone trails initialized uniformly for all solution components and learned while solving instance. On the contrary, heuristic measures are predefined based on prior knowledge of problem, and devising proper heuristic measures for complicated COPs is quite challenging (an example is [49]).
Over the past decades, research and practice efforts have been dedicated to a careful design of heuristic measures in pursuit of knovledge-driven performance enhancement [57, 62, 33, 49, 26, 24]. However, this routine of algorithm customization exhibits certain deficiencies: 1) it requires extra effort and makes ACO less flexible; 2) the effectivvness of the heuristic measure heavily relies expert knowledge and manual tuning; and 3) designing a heuristic measure for less-studied problems can be particularly challenging, given the paucity of available expert knowledge.
Corresponding authors: Zhiguang Cao and Helan Liang.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

This paper proposes DeepACO, a generic neural-enhanced ACO meta- heuristtuis,,, and a solution to the above limitations. DeepACO serves to strengthen the heuristic measures of existing ACO algorithms and dispense with laborious manual design in future ACO applications. It mainly involves two learning stages. The first stage learns problem-specific mapping from an instance to its heuristic measures by training neural models across COP instances. Guided by the learned measures, the second stage learns instance-specific pheromone trails while solving an instance with ACO, The heuristic measures learned in the first stage are incorporated into ACO (the second learning stage) by biasing the solution constructions and leading Local Search (LS) to escape local optima.
DeepACO is also along the line of recent progress in Neural Combinatorial Optimization (NCO) [12, 61, 7, 34]. Within the realm of NCO, DeepACO is more related to the methods that utilize heatmaps for algorithmic enhancement [32, 42, 90, 55, 42], but it is superior in its flexibility: DeepACO provides effective neural enhancement across eight COPs covering routing, assignment, scheduling, and subset problems, being the most broadly evaluated NCO technique to our knowledge. In addition, we propose three extended implementations for better balancing between exploitation and exploration: one featuring multihead decoder, one trained with additional top-k entropy loss, and one trained with an additional imitation loss. They can be generally applied to heatmap-based NCO methods.
As a neural-enhanced version of ACO, DeepACO consistently outperforms its counterparts on eight COPs using a single neural model and a single set of hyperparameters after only minutes of training. As an NCO method, DeepACO performs better than or competitively against the state- of-the-art (SOTA) and problem-specific NCO methods on canonical routing problems while being more generalizable to other COPs. To the best of our knowledge, we are the first to exploit deep reinforcement learning (DRL. to guide the evolution of ACO meta-heuristics. Such a coupling allows NCO techniques to benefit from decades of ACO research (notably regarding theoretical guarantees [7, 26)), while simultaneously offering ACO researchers and practitioners a promising avenue for algorithmic enhancement and design automation.
In summary, we outline our contributions as follows:
We propose DeepACO, a neural-enhanced ACO meta-heuristic. It strengthens existing ACO algorithms and dispenses with laborious manual design in future ACO applications.
We propose three extended implementations of DeepACO balance exploration and exploitation, which can generally be applied to heatmap-based NCO methods.
We verify that DeepACO consistently outperforms its ACO counterparts across eight COPs while performing better than or on par with problem-specift NCO methods.
2 Related work
2.1 Neural Combinatorial Optimization
Neural Combinatorial Optimization (NCO) is interdisciplinary field that tackles COPs with deep learning techniques. In general, existing NCO methods can be categorized into end-to-end and hybrid methods, and DeepACO belongs to the latter methodological category.
End-to-end methods in the former category learn autoregressive solution constructions or heatmap generation for subsequent sampling-base decoding. Within this realm, recent developments include better-aligned neural architectures [82, 64, 54, 50, 89, 13, 46), improved training paradigms [6, 56, 52, 83, 10, 66, 40, 45], advanced solution pipelines [47, 51, 48, 20, 78, 18, 65, 19], and broader applications [88, 95, 16, 29, 75, 9]. End-to-end methods are admirably efficient, but their constructed solutions can be further improved with iterative refinement and algorithmic hybridization.
Therefore, the hybrid methods in the latter category incorporate neural learners to make decisions within/for heuristics or generate heatmaps to assist heuristics. These methods either let neural learners make decisions within algorithmic loops [60, 87, 21, 17, 94, 86, 59], or generate heatmaps in one shot to assist subsequent algorithms. In the latter case, Xin et al. [90] propose to learn edge scores and node penalties to guide the searching process of LKH-3 [39], a highly optimized solver for routing problems. Kool et al. [55] train neural models to predict promising edges in routing problems, providing a neural boost for Dynamic Programming. Fu et al. [32] train scall-scale GNN to build heatmaps for large TSP instances and feed the heatmaps into Monte Carlo Tree Search for solution

---

improvements. Hudson et al. [42] utilize neural models to generate regret in Guided Local Search for TSP. DeepACO is along the line of these works, but superior in terms of its flexibility, i.e., it provides effective neural enhancement across eight COPs covering routing, assignment, scheduling, and subset problems while the existing hybridized methods mostly focus on a limited set of routing problems.
2.2 Ant Colony Optimization
Ant Colony Optimization (ACO) is meta- meta-heuristic and evolutionary algorithm (EA) [4, 73] inspired by the behavior of ants in finding the shortest path between their colony and food sources [26].
The representative ACO meta-heuristics such Ant System (AS) [25], Elitist AS [25], and MAX- MIN AS [76] provide general-purpose frameworks allowing for problem-specifee customization. Such customization may involve designs of heuristic measures [49, 331, the incorporation of local search operators [3, 93]. and the hybridization of different algorithms [44, 5J. DeepACO is not in competition with the most SOTA ACO algorithms for specific COP. Instead, DeepACO can strengthen them with stronger heuristic measures and can in turn benefit from their designs.
ACO can utilize group of techniques named syper-heuristie [69] that are conceptually related to DeepACO. But hecristcsssssies mostly involve expert-designtt heuristics to select from (heuristic selection hyper-heuristics) [27] or troblem-speciin and manually-definee components evolve heuristics (heuristic generation hyper-heuristics) [14]. By comparison, DeepACO is more generie, requiring little prior knowledge of a COP. Its aim is not to compete with any hyper-heuristics, instead, for example, we can utilize hyper-heuristics to improve LS components DeepACO.
Unlike the knowledge-driven ACO adaptations above, a recent method, namely ML-ACO [77], boosts the performance of ACO via Machine Learning (ML) for solution prediction. While ML-ACO provides initial insight into coupling ML with ACO, it is preliminary and limited. ML-ACO tailors five features for Orientcering Problem and trains ML classifiers in a supervised manner. It entails high-demanding expert knowledge for feature designs and specialized solvers for optimal solutions, making itself inflexible and hard to scale. By comparison, DeepACO leverages DRL and demands little expert knowledge to apply across COPs.
Preliminary on Ant Colony Optimization
The overall ACO pipeline is depicted in Fig. 1. We begin with defining a COP model and a pheromone model. They are prerequisites for implementing ACO algorithms.
COP model Generally, a COP model consists of, 1) a search space S defined over a set of discrete decision variables X,, I,...,,7,, n., where each decision variable X; takes value from finite set D. = {o....., v2 D.I 2) a set of constraints 1 that the decision variables must satisfy; and 3) an objective function f + iR to minimize. A feasible solution 8 to COP is complete assignment of all decision variables that satisfies all the constraints in Ω
Pheromone model A COP model defines pheromone model in the context of ACO. Without loss of generality, pheromone model a construction graph that includes decision variables as nodes and solution components edges [26]. Each solution component Cij. that represents the assignment of value uz to decision variable Xz, is associated with its pheromone trial Tız and heuristic measure Viy- Both Ti and Mij indicate how promising it is to include ej in a solution. Typically, ACO uniformly initializes and iteratively updates pheromone trails, but predefines and fixes heuristic measures.
As a motivating example, for TSP, a instance can be directly converted into a fully connected construction graph, where city i becomes node i and solution component Cıy represents visiting city immediately after city i. Then, 7hj is typically set to the inverse of the distance between city and After defining COP model and a pheromone model, introduce an ACO iteration, usually consisting of solution constructions, optional LS refinement, and pheromone updates.
Solution construction and local search (optional) Biased by Tij and Maa an artificial ant constructs solution { by traversing the construction graph. If an ant is located in node at the 1-th construction step (s,-1 = i) and has constructed partial solution scr {sc [s] the probability of
3

---

Problem definiton
Pheromone model
Problem
Pheromone model
defnition
Protkem resancos
Sailiing
Iiguit pusterioo
Excert
Inference
Wnou issaance
Huurisic
Heutert SeamTe
Reward
Pharomane triata
Heuraaii: IEVIRAATI
Haurbadic
Update
So udion consiruction and local (optional)
So uttor: consiruciion and muural local search (szlioane))
local wearch (opliemal)
ACO
DeepACO
The schematic diagrams of ACO and DeepACO, DeepACO 1) additionally trains a heuristic learner across instances, 2) applies the well-traine heuristic learner generate heuristic measures during inference, and 3) optionally leverages the learned heuristic measures to conduct local search interleaved with neural-guided perturbation.
Figure 1:
selecting node its next destination (s: j) is typically given by
if ((<()),
P(se|8<t p)) EcnEN(ess) T.
(1)
otherwise.
Here, p is COP instance, (sccr) is the set of feasible solution components given the partial solution, and a and B are the control parameters, which are consistently set to in this work unless otherwise stated. To simplify the notations, we omit the dependence on p т, 17. c, and N. Based on Eq. (1), constructing a complete solution requires an n-step graph traversal. The probability of generating can be factorized
P(spp) = II P(s.|s<r.)))
t=1
After solution constructions, local search (LS) is optionally applied to refine the solutions.
Pheromone update After solution constructions, the pheromone update process evaluates solutions and adjusts the pheromone trails accordingly. i.e., it increases the pheromone trails of components in the superior solutions while decreasing those in the inferior ones. The detailed update rules can differ depending the ACO variation used.
ACO intelligently explores the solution space by iterating above process, eventually converging on (sub)optimal solutions. We refer the readers to [26] for more details.
4 Methodology
DeepACO is schematically presented in Fig. wherein comparison made with ACO. It dispenses with expert knowledge and learns a of stronger heuristic measures to guide the ACO evolution. AeepACO involves parameterizing the heuristic space (Section 4.1), optionally interleaving LS with neural-guided perturbation (Section 4.2), and training a heuristic learner across instances (Section 4.3). Additionally, we introduce three extended designs (Section 4.4) to boost exploration.
4.1 Parameterizing heuristic space
We introduce heuristic learner, defined by a graph neural network (GNN) with trainable parameters 0, to parameterize the heuristic space. The heuristic learner maps input COP instance p to its

---

heuristic measures (p),,, where we rewrite it as Te for notation simplicity. It contains non non-negative real values 7hj;0 associated with each solution component Gjj, Vi [I....,.1 n.....,,,... Vjj (1..... D DeepACO constructs solutions following Eq. (2) but biased by no:
( (s|p) = II
Pmo ( P).
(3)
t=1
In particular, exploited the neural models recommended by Joshi al. [48] and Qiu al. [66]. It consists of GNN backbone relying on anisotropic message passing and an edge gating mechanism, and Multi-Layer Perceptron (MLP) decoder mapping the extracted edge features into heuristic measures. We defer the full details of this neural architecture to Appendix A.
4.2 Local search interleaved with neural-guided perturbation
In ACO, local search (LS) is optionally applied to refine the constructed solutions. However, LS a myopic procedure that greedily accepts any altered solution with a lower objective value and easily gets trapped in local optima. In DeepACO, we intend the well-learned heuristic measures to indicate the global optimality of solution components. Leveraging such indicators and including solution components with greater global optimality lead to better solutions eventually, if not immediately. Nevertheless, is unrealistic to solely rely on the learned heuristic measures due to the inherent complexity of COPs.
Based on these considerations, we propose LS interleaved with neural-guided perturbation (NLS for short) in Algorithm 1. NLS interleaves LS aiming for a lower objective value and neural-guided perturbation biasing the learned optima. In each iteration, the first stage utilizes LS repeatedly refine solution until (potentially) reaching local optima. The second stage utilizes LS to slightly perturb the locally optimal solution toward gaining higher cumulative heuristic measures.
Algorithm NLS
I: Input: A solution s; an objective function f; well-learned heuristic measures ne; a local search operator LS that takes three inputs: solution refine, the targeted objective function, and the maximum iterations before encountering local optima; the number of perturbation moves Tp: the number of NL.S iterations TNes
2: Output: The best improved solution s*
3: s LS, f00 Improve s until reaching a local optimum
4: s* copy(s)
TNLS do 6: 8 LS(s, 1 Tp) // Perturb a toward higher cumulative heuristic measures with Tp moves
5: for iter
7: LS(s, +00)
8: s" = arg ((
9: end for
4.3 Training heuristic learner
We train the heuristic learner across COP instances. The heuristic learner maps each instance its heuristic measures Tl. Then, we minimize the expected objective value of both constructed solutions and NLS-refined constructed solutions:
minimize L(0)p) = Eg- (1p) ( (
where W is a coefficient for balancing two terms. Intuitively, the first loss term encourages directly constructing optimal solutions, which is, however, often held off by the complexity of COP. The second term encourages constructing solutions most fit for NLS, and it could be easier to learn high-quality solutions coupling end-to-end construction with NLS. Even so, solely relying on second term leads to inefficient training due to the small quality variance of the NLS--reined solutions. As result, we find it useful to implement both terms for training. Note that the NI.S process itself does not involve gradient flow.
5

---

In practice, we deploy Ant Systems to construct solutions stochastically following Eq. (3) for estimating Eq. (4). The pheromone trials are fixed to ensure an unbiased estimation. We We apply REINFORCE-basee [85] gradient estimator:
VC(0)p) Ea-Pag (l))(((((())))))))))))))))))))() b(p)) + (V((NLS(s.f,+ ( log Pro (s|p) (5)
where b(p) and (p) are the average objective value of the constructed solutions and that of the NLS-refined constructed solutions, respectively.
4.4 Toward better exploration
The vanilla DeepACO fully exploits underlying pattern a problem and learns a set of aggressive heuristic measures (visualized in Appendix C.6) according to Eq. (4). Still, preserving exploration of critical importance since COPs often feature many local optima [89]. To that end, we further present three extended designs to enable better balance of exploration and exploitation. Note that they can generally be applied to heatmap-based NCO methods.
4.4.1 Multihead decoder
Multihead DeepACO implements m MLP decoders on the top of the GNN backbone. It aims to generate diverse heuristic measures to encourage exploring different optima the solution space. similar multihead design has been utilized for autoregressive solution construction [89]. We extend this idea the non-autoregressive heuristic generation here.
For training, Multihead DeepACO utilizes Eq. (4) calculated individually and independently for m decoders and extra Kullback-Leible (KL) divergence loss expressed
1 m
m n
T
(kL(O)p)
Vijo log
m²n
j=l
where oi is the heuristic measure of the solution component Gyy output by the k-th decoder after row-wise normalization.
In the inference phase, Multihead DeepACO deploys ant groups guided by their respective MLP decoders while the whole ant population shares the same set of pheromone trails.
4.4.2 Top-k entropy loss
Entropy loss (reward) incentivizes agents to maintain the diversity of their actions. It is often used regularizer to encourage exploration and prevent premature convergence suboptimal policies [68, 37, 51]. I. In the context of COP, however, most solution components are far from a reasonable choice for the next-step solution construction. Given this, we implement top-k entropy loss while optimizing Eq. (4), promoting greater uniformity only among the top k largest heuristic measures:
LH (H(p))
Σ
Σ Mujo log( (7):)))
i=1 jEK,
Here, IC; is set containing top & solution components of decision variable X,, and Miji the heuristic measures normalized within the set.
4.4.3 Imitation loss
If expert-designed heuristic measures are available, we can additionally incorporate imitation loss, enabling the heuristic learner to mimic expert-designed heuristics while optimizing Eq. (4). holds two primary merits. First, the expert-designed heuristic measures are less aggressive than the learned ones. So, it can function as a regularization to maintain exploration. Second, the heuristic learner can acquire expert knowledge. Perfecting the imitation first guarantee that the learned heuristics at least not inferior to the expert-designed counterparts.
Accordingly, the imitation loss is formulated as
D.
1
Cr(0pp)
nig
log
(8)
Tkjo

---

where ni and πi:0 are expert-designed and learned heuristic measures, respectively, both after row-wise normalization.
5 Experimentation
5.1 Experimental setup
Benchmarks We evaluate DeepACO on eight representative COPs, including the Traveling Sales- man Problem (TSP), Capacitated Vehicle Routing Problem (CVRP), Orienteering Problem (OP), Prize Collecting Traveling Salesman Problem (PCTSP), Sequential Ordering Problem (SOP), Single Machine Total Weighted Tardiness Problem (SMTWTP), Lesourrce-oonstriinee Project Schedul- ing Problem (RCPSP), and Multiple Knapsack Problem (MKP). They cover routing, assignment, scheduling, and subset COP types. Their definitions and setups given in Appendix D.
Hardware Unless otherwise stated, we conduct experiments on 48-core Intel(R) Xeon(R) Platinum 8350C CPU and an NVIDIA GeForce RTX 3090 Graphics Card.
5.2 DecpACO as an enhanced ACO algorithm
In this part, we do not apply NLS and set W in Eq. (4) to O for training. It only entails minutes of training to provide substantial neural enhancement as shown in Fig. 2 (also Appendix C.4). On the other hand, the extra inference time for DeepACO is negligible; for example, it takes less than 0.001 seconds for TSP100.
DeepACO for fundamental ACO algorithms We implement DeepACO based three funda- mental ACO meta- meta-heuristicc: Ant System [25], Elitist Ant System [25], and MAX-MIN Ant System
[76]. They are widely recognized as the basis for many SOTA ACO variations [44, 2, 5, 3, 93]. We compare the heuristic measures learned by DeepACO to the expert-designee ones (detailed separately for eight COPs in Appendix D) on 100 held-out test instances for each benchmark COP. The results in Fig. 2 show that DeepACO can consistently outperform its ACO counterparts, verifying the universal neural enhancement DeepACO can bring. We defer the results on more COP scales Appendix C.I.
DeepACO for advanced ACO algorithms We also apply DeepACO to Adaptive Elitist Ant System (AEAS) [2]. a recent ACO algorithm with problem-specific adaptations. In Fig. 3, we plot the evolution curves of AEAS based on the original and learned heuristic measures, respectively, and DeepACO shows clearly better performance. In light of this, we believe that it is promising to exploit DeepACO for designing new ACO SOTAS.
TSP1.0
CURP110
7CTSP100
12.5
35.9
1220
2005
10/00
2000
10:00
550
1900
2003
1001
1568
1000
520
1250
1500
2005
NC75P120
355
40.
25-
425
65.
30
300
535-
530
2003
1263
2000
300
33000
1206
2039
530
1090
1549
2000
3800
1000
2009
DeepACD
DeepACO (ERtis))
DeepACD [MAX-NIN]
Figure 2: Evolution curves of fundamental DeepACO and ACO algorithms on eight different COPs. For each COP, we plot the so-t-so-far objective value (averaged over 100 held-out test instances and 3 runs) w.r.t. the number of used evaluations along the ACO iterations.
7

---

CVRP20
CVRP100
CVRP500
5.5
25.0
220
22.5
ACD (AEAS)
300
DespACO (ALAS)
20.0
17.5
4.5
0
500
1000
1503
2000
0
500
1000
1950
2000
500
1000
1500
2000
offeralcaiioss
of ovaluations
Figure 3: Evolution curves of DeepACO and ACO based on Adaptive elitist-ant system (AEAS) [2].
DeepACO for different pheromone models The pheromone model used in ACO can vary, even for the same problem [63]. Following the naming convention in [63]. we use PHe to denote the pheromone model that captures the successively chosen items and P items the one that directly captures how good each item is. We extend DeepACO from PHe suc to PHstems using Transformer [79] encoder equipped with an MLP decoder. We showease such flexibility of DeepACO on MKP in Fig. 7, where DeepACO using PH can still outperform its ACO counterparts, It validates that DeepACO can be readily extended to variations pheromone models using properly aligned neural models. We defer further discussions to Appendix A and C.5.
DeepACO for better robustness to hyperparameter choice Increasing the robustness ACO to hyperparameter choices has long been an important research topic [84, 92]. In Fig. 4, we adjust two important hyperparameters, i.c., Alpha that controls the transition probability of solution construction and Decay that controls the pheromone updates, evaluate DeepACO (AS) and ACO (AS) the TSP100 test dataset, and plot their best objective values within the evolution of 4K evaluations. The results indicate that DeepACO is more robust to the hyperparameter choice given its much lower color variance. We thereby argue that data-driven training can also dispense with high-demanding expert knowledge for hyperparameter tuning.
DeepACO for real-world instances We draw all 49 real-world symmetric TSP instances featuring EUC 2D and containing less than 1K nodes from TSPLIB. We infer instances with 50 nodes using the model trained on TSP20, those with 50 < n < 200 nodes using the model trained on TSP100, and the rest using the model trained TSP500. The evolution curves of DeepACO and ACO are shown in Fig. 5, suggesting that DeepACO can consistently outperform its ACO counterparts even when generalizing across scales and distributions.
DespAco
A20
TSPLB
becayd
lockpedi
11e
ACO
Decaye
becaped
150
ACD (MAX-MIK)
25
DeepAGO (AS)
DespACO (Eliik))
35
DespACO
Aplends
Abrtad
Abbec
2000
2200
Figure 4: Sensitivity of DeepACO and ACO the Figure 5: Evolution curves of DeepACO and ACO averaged over TSPLIB instances.
hyperparameter choice.
5.3 DeepACO as an NCO method
Comparison on routing problems As shown in Table 1, DeepACO demonstrates competitive performance against the SOTA NCO methods for TSP. Here, we apply the generic 2-opt for NLS (TvLs = 10, T, 20) and set W in Eq. (4) to 9. Note that most NCO baselines are specialized for TSP or routing problems, while DeepACO a general-purpose meta-heuristic and validated across eight different COPs. In addition, the results of ablation studies in Table 2 further validate our designs; that is, both neural- -uidedd perturbation and training with I.S effectively strengthen DeepACO. More results on TSP100 and CVRP given in Appendix C.2.
8

---

Table 1: Comparison results of DeepACO and NCO
baselines. We report per-instance execution time.
Table 2: Ablation studies of DeepACO. We ad-
ditionally evaluate DeepACO 1) with vanilla LS and more iterations, 2) implementing ran-
TSP500 Gugp(S)
TSP|OO
Dbj.
Timets)
Obj
CupetS)
Timets)
dom perturbation for LS, and 3) trained with
LKHH3 [39]
10:55
A00
17.57
5.16
7.87
54
W 0 for Eq. (4).
AM [54]
21.46
29.7
POMO* [16]
20.57
24.4
GCN-MCTS*1R [32]
16.97
2.54
23.86
3.22
100
DeepACO
TSP50U
TSP1000
DIMES+MCTS [6o]
17.01
2.78
11
26.43
5.75
32
Obj.
Timo(s)
Obj.
Timo(s)
DIPUSCO+MCTS [75]
16.3
1146
4.7
23.39
1.17
11
SU" [18]
1094
2.40
15
23.77
2,80
26
vanilla LS
16.90
23.89
Peinteerfrmmrr (46)
17.14
3.56
1.4
34,00
7.30
4.0
random perturbation
16.92
23.90
H-TSP" [65]
24.65
6.62
0.3
(W = for training
17.05
10
24.23
32
DargACO 77 2)
1694
2.56
2.0
23.99
3.76
6.4
Original
16.86
23.85
DeepACO 7T 101
16.86
1.4
10
23.85
3,16
32
For heatmaps with better exploration We implement the three extended designs introduced in Section 4.4 without LS and compare their evolution curves with vanilla DeepACO in Fig. 6. We apply 4 decoder heads for Multihead DeepACO and set to 5 for the top-K entropy loss. The coefficients for the additional loss terms (i.e., LKL, LH, and L1) are to 0.05, 0.05, and 0.02, respectively. The results indicate that these designs lead to better performance on TSP20, 50, and 100 since small-scale COPs typically desire more exploration.
For enhancing heatmap decoding with pheromone update Though we can conduct pure solution samplings similar [47, 66, 78] given the learned heuristic measures, demonstrate the superiority of ACO evolution (without NLS) with self-learning pheromone update in Fig. 8. Furthermore, coupling heatmaps with ACO can benefit from extensive ACO research, such as advanced ACO variations, algorithmic hybridizations, and seamless incorporation of local search operators.
TSP20
13P50
1SP100
1.6
1.4
6.3
2.0
250
240
200
Venilla DeepACO
1.4
9.4
With tation los
With encroay loss
With muchhodd decader dzoder
1.00
20.33
20000
2000
3200
5232
1.200
2200
30.00
4030
Figure 6: Evolution curves vanilla DeepACO and three extended implementations on TSP20, 50, and 100. The results are averaged over 3 runs on held-out test datasets each with 100 instances.
TSP20
67.5
52.
5 57.5
2,22
5-5
226
20
evalustinn
951
1666
200
851
1700
502
1000
1502
1000
1000
2003
2020
4000
5000
(5)
DeepAC3
ACC (31141
DeepACD 1D
DezDACO (601
CoupACo (VACMING
Figure 7: Evolution curves of DeepACO and ACO on MKP300 and MKP500 using the pheromone model PHitems-
Figure 8: Solution comparison between using Ant System evolution and pure sampling.
6 Conclusion and limitation
In this work, we propose DeepACO to provide universal neural enhancement for ACO algorithms and automate heuristic designs for future ACO applications. We show that DeepACO performs

---

consistently better than its ACO counterparts and is on par with the specialized NCO methods. For the Operations Research (OR) community, DeepACO demonstrates promising avenue toward leveraging deep reinforcement learning for algorithmic enhancement and design automation. For the Machine Learning (ML) community, DeepACO presents versatile and adaptable NCO framework that can seamlessly integrate with SOTA ACO and EA techniques, including improved rules for solution construction and pheromone update [76, 11], algorithmic hybridizations [67, 91], and incorporation of sophisticated local search operators [3, 93].
However, DeepACO is potentially limited by compressing all learned heuristic information into an n X n matrix of heuristic measures. Due to the complexity of COPs and this restricted way of expressing problem patterns, DeepACO may fail to produce close-to-optimal solutions when not incorporating LS components. To address such limitations, we plan to investigate 3D or dynamic heuristic measures in our future work.
Acknowledgments and Disclosure of Funding
The authors appreciate the helpful discussions with Yu Hong, Juntao Li, and anonymous review- ers. Yu Hu, Jiusi Yin, and Tao Yu also contributed to this work. This work was supported by the National Natural Science Foundation of China (NSFC) [grant numbers 61902269, 52074185); the National Key R&D Program of China [grant number 0018YT007017001 the Undergraduate Training Program for Innovation and Entrepreneurship. Soochow University [grant number 2022102850012, 2023 10285041Z;; the Priority Academic Program Development of Jiangsu Higher Education Insti- tutions, China; and Provincial Key Laboratory for Computer Information Processing Technology. Soochow University [grant number KJS1938J.
References
[1] D. Abitz, T. Hartmann, and M. Middendorf. A weighted population update rule for paco applied to the single machine total weighted tardiness problem. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, pages 4-, 2020.
[2] A. Abuhamdah. Adaptive elitist-ant system for solving combinatorial optimization problems. Applied Soft Computing, 105:107293, 2021.
[3] Z. A. Ali, H. Zhangang, and W. B. Hang. Cooperative path planning of multiple uavs by using max-min ant colony optimization along with cauchy mutant operator. Fluctuation and Noise Letters, 20(01)22150002, 2021.
[4] Z. N. Ansari and Daxini. A state-of-the-art review on meta-heuristics application in remanufacturing. Archives of Computational Methods in Engineering, 29(1):427-470, 2022.
[5] E. Babaee Tirkolaee, I. Mahdavi, M. M. Seyyed Esfahani, and G.-W. Weber. A hybrid augmented ant colony optimization for the multi-trip capacitated are routing problem under fuzzy demands for urban solid waste management. Waste management research, 38(2):156 172, 2020.
[6] I. Bello, H. Pham, Q. Le, M. Norouzi, and S. Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv: 161 1.09940, 2016.
[7] Y. Bengio, A. Lodi, and A. Prouvost. Machine learning for combinatorial optimization: methodological tour d'horizon. European Journal of Operational Research, 290(2):405-421, 2021.
[8] I. BenMansour. An effective hybrid ant colony optimization for the knapsack problem using multi-directional search. SN Computer Science, 4(2):164, 2023.
[9] F. Berto, C. Hua, J. Park, M. Kim, H. Kim, J. Son, H. Kim, J. Kim, and J. Park. RI4co: an extensive reinforcement learning for combinatorial optimization benchmark. arXiv preprint arXiv:2306.17100 17100, 2023.
10

---

[10] J. Bi, Y. Ma, J. Wang, Z. Cao, J. Chen, Y. Sun, and Y. M. Chee. Learning generalizable models for vehicle routing problems via knowledge distillation. arXiv preprint arXiv:2210.07686, 2022.
[11] C. Blum. coam-acco-hbbridizzin ant colony optimization with beam search: An application to open shop scheduling. Computers & Operations Research, 32(6):1555-1591 2005.
[12] A. Bogyrbayeva, M. Meraliyev, T. Mustakhov, and B. Dauletbayev. Learning solve vehicle routing problems: A survey. arXiv preprint 1.Xiv:22005.02553. 2022.
[13] X. Bresson and T. Laurent. The transformer network for the traveling salesman problem. arXiv preprint arXiv: 103.03012, 2021.
[14] E. K. Burke, M. Gendreau, M. Hyde, G. Kendall, G. Ochoa, E. Özcan, and R. Qu. Hyper- heuristics: A survey of the state of the art. Journal of the Operational Research Society, 64: 1695-1724, 2013.
[15] J. Cai, P. Wang, S. Sun, and H. Dong. A dynamic space reduction ant colony optimization for capacitated vehicle routing problem. Soft Computing, 26(17):875-88756 2022.
[16] Chen, Z. Zong, Y. Zhuang, H. Yan, D. Jin, and Li. Reinforcement learning for practical express systems with mixed deliveries and pickups. ACM Transactions Knowledge Discovery from Data (TKDD), 2022.
[17] X. Chen and Y. Tian. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
[18] H. Cheng, Zheng, Cong, W. Jiang, and S. Pu. Select and optimize: Learning to aolve large-scale tsp instances, In International Conference Artificial Intelligence and Statistics, pages 1219-1231. PMLR, 2023.
[19] A. Chmiela, E. Khalil, A. Gleixner, A. Lodi, and S. Pokutta. Learning to schedule heuristics in branch and bound. Advances in Neural Information Processing Systems, 00124235-222444 2021.
[20] J. Choo, Y.-D. Kwon, J. Kim, J. Jac, A. Hottung, K. Tierney, and Y. Gwon. Simulation-guidde beam search for neural combinatorial optimization. arXiv preprint arXiv:2207.06199, 2022.
[21] R. O Costa, J. Rhuggenaath, Y. Zhang, and A. Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian Conference on Machine Learning, pages 465-480. PMLR, 2020.
[22] P. R. O Costa, J. Rhuggenaath, Y. Zhang, and A. Akcay. Learning 2-opt heuristics for the traveling salesman problem via deep reinforcement learning. In Asian conference on machine learning, pages 465-480. PMLR, 2020.
[23] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 18Xiv: 2018
[24] M. Dorigo and T. Stützle. Ant colony optimization: overview and recent advances. Springer, 2019.
[25] M. Dorigo, V. Maniezzo, and A. Colorni. Ant system: optimization by a colony cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1): 49- 1996.
[26] M. Dorigo, M. Birattari, and T. Stutzle. Ant colony optimization. intelligence magazine, 1(4):28-39 2006.
IEEE computational
[27] H. Drake, Kheiri, E. Özcan, and E. K. Burke. Recent advances in selection hyper-heuristics. European Journal of Operational Research, 285(2):405-428, 2020.
[28] S. Elfwing, F. Uchibe, and K. Doya. Sigmoid-weighted linear units for neural network function approximation in reinforcement learning. (arXiv:1702.031 Nov 2017. doi: 10.48550/arXiv. 1702.03118 18.. URL http:// // www.xxi.rggabs///ooee http://ab//112...33333 03118. 1tXiv:1702.033 [cs].

---

[29] M. Fan, Y. Wu, T. Liao, Z. Cao, H. Guo, G. Sartoretti, and G. Wu. Deep reinforcement learning for uav routing in the presence of multiple charging stations. IEEE Transactions on Vehicular Technology, 2022.
[30] S. Fidanova. Hybrid ant colony optimization algorithm for multiple knapsack problem. In 2020 Sth IEEE International Conference on Recent Advances and Innovations in Engineering (ICRAIE), pages 1-5. IEEE, 2020.
[31] M. Fischetti, S. Gonzalez, and Toth. Solving the orienteering problem through branch- and-cut. INFORMS Journal on Computing, 10(2):133-148, 1998.
[32] Z.-H. Fu, K.-B. Qiu, and H. Zha. Generalize a small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7474-7482, 2021.
[33] W. Gao, Q. Tang, B. Ye, Y. Yang, and J. Yao. An enhanced heuristic ant colony optimization for mobile robot path planning. Soft Computing, 24:6139-611 6150, 2020.
[34] A. Garmendia, J. Ceberio, and A. Mendiburu. Neural combinatorial optimization: a new player in the field. arXiv preprint arXiv:2205.0/33 2022.
[35] Y. L. Goh, W. S. Lee, X. Bresson, T. Laurent, and N. Lim. Combining reinforcement learning and optimal transport for the traveling salesman problem. arXiv preprint arXiv:2203.0090 2022.
[36] A. Gonzalez-Parie Pardo, Del Ser, and Camacho. Comparative study of pheromone control heuristics in aco algorithms for solving repsp problems. Applied Soft Computing, 60:241-255, Nov 2017. ISSN 1568-4946. doi: 10. 201....0..2.....6....
[37] T. Haarnoja, A. Zhou, K. Hartikainen, G. Tucker, S. Ha, J. Tan, V. Kumar, H. Zhu, A. Gupta, P. Abbeel, et al. Soft actor-critic algorithms and applications. arXiv preprint arXiv:/812.0500 2018.
[38] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[39] K. Helsgaun. An extension of the in-kernighan--helgaun tsp solver for constrained traveling salesman and vehicle routing problems. Roskilde: Roskilde University, pages 24-50, 2017.
[40] A. Hottung, Y.-D. Kwon, and K. Tierney. Efficient active search for combinatorial optimization problems. arXiv preprint 2xXx:2100.051222 2021.
[41] Q. Hou, J. Yang. Y. Su, X. Wang, and Y. Deng. Generalize learned heuristics solve large-scale vehicle routing problems in real-time. In The Eleventh International Conference on Learning Representations, 2022.
[42] B. Hudson, Q. Li, M. Malencia, and A. Prorok. Graph neural network guided local search for the traveling salesperson problem. arXiv preprint arXiv:21 2021.
[43] S. loffe and C. Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift, (arXiv:1502.03167) Mar 2015. doi: 10. 15550000 URL http://arxiv org/ abo//////./////////////////// 03167. 1502.0315 [cs].
[44] G. M. Jaradat, A. Al-Badareen, M. Ayob, M. Al-Smadi, I. Al-Marashdeh, M. Ash-Shuqran, and E. Al-Odat. Hybrid elitist-ant system for nurse-rostering problem. Journal of King Saud and Information Sciences, 31(3):378-33 2019.
Universiry-Compune
[45] Y. Jiang, Y. Wu, Z. Cao, and J. Zhang. Learning solve routing problems via distributionally robust optimization. arXiv preprint 21X1v:2202.07221, 2022.
[46] Y. Jin, Y. Ding, X. Pan, K. He, L. Zhao, T. Qin, L. Song, and J. Bian. Pointerformer: Deep reinforced multi-pointer transformer for the traveling salesman problem. arXiv preprint arXiv:2304.09400 2023.
12

---

[47] C. K. Joshi, T. Laurent, and X. Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.012 01227, 2019.
[48] C. K. Joshi, Q. Cappart, L.-M. Rousseau, and Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, pages 1-29, 2022.
[49] S. Kashef and H. Nezamabadi-pour. An advanced aco algorithm for feature subset selection. Neurocomputing, 147:271-279, 2015.
[50] E. Khalil, H. Dai, Y. Zhang, B. Dilkina, and L. Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[51] M. Kim, J. Park, al. Learning collaborative policies to solve np-hard routing problems. Advances in Neural Information Processing Systems, 34: 10418-10400, 2021.
[52] M. Kim, J. Park, and J. Park. Sym-nco: Leveraging symmetricity for neural combinatorial optimization. arXiv preprint arXiv:2205. 2022.
[53] R. Kolisch and A. Sprecher. Psplib project scheduling problem library: Or software orsep operations research software exchange program. European Journal of Operational Research, 96(1):205-21) 216, Jan 1997. ISSN 0377-2217. doi: 02.1016/0077-2211766000000
[54] W. Kool, H. Van Hoof, and M. Welling. Attention, learn solve routing problems! arXiv preprint 1rXiv 08475, 2018.
[55] W. Kool, H. van Hoof, J. Gromicho, and M. Welling. Deep policy dynamic programming for ve- hicle routing problems. In International Conference on Integration of Constraint Programming. Artificial Intelligence, and Operations Research, pages 190-213. Springer. 2022.
[56] Y.-D. Kwon, J. Choo, B. Kim, I. Yoon, Y. Gwon, and S. Min. Pomo: Policy optimization
with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21 188-18881 21 21198, 2020.
[57] G. Leguizamon and Z. Michalewicz. A new version of ant system for subset problems. In Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), volume 2, pages 1459-1464. IEEE, 1999.
[58] J. Levine and F. Ducatelle. Ant colony optimization and local search for bin packing and cutting stock problems. Journal of the Operational Research society, 55(7):705-716, 2004.
[59] S. Li, Z. Yan, and C. Wu. Learning to delegate for large-scale vehicle routing. Advances in Neural Information Processing Systems, 01226198-222221 2021.
[60] Y. Ma, J. Li, Z. Cao, W. Song, L. Zhang, Z. Chen, and J. Tang. Learning iteratively solve routing problems with aspe-aspect collaborative transformer. Advances in Neural Information Processing Systems, 34:1 1096-1910777 2021.
[61] N. Mazyavkina, S. Sviridov, S. Ivanov, and E. Burnaev. Reinforcement learning for combinato- rial optimization: A survey. Computers & Operations Research, 134:105400 2021.
[62] D. Merkle, M. Middendorf, and H. Schmeck. Ant colony optimization for resource-conssrrined project scheduling, IEEE Transactions on Evolutionary Computation, 6(4):333-346, Aug 2002. ISSN 1941-0026. doi: 10. (0.1000//EC.222022802225
[63] J. Montgomery, M. Randall, and T. Hendtlass. Solution bias in ant colony optimisation: Lessons for selecting pheromone models. Computers & Operations Research, 35(9):2728-2777 2749, 2008.
[64] M. Nazari, A. Oroojlooy, L. Snyder, and M. Takác. Reinforcement learning for solving the vehicle routing problem. Advances in neural information processing systems, 31, 2018.
[65] X. Pan, Y. Jin, Y. Ding, M. Feng, L. Zhao, L. Song, and J. Bian. H-tsp: Hierarchically solving the large-scale travelling salesman problem. arXiv preprint arXiv:2304.09335, 2023.
[66] R. Qiu, Sun, and Y. Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. arXiv preprint arXiv:2210.04123. 2022.
13

---

[67] N. Rokbani, R. Kumar, A. Abraham, A. M. Alimi, H. V. Long, I. Priyadarshini, and L. H. Son. Bi-heuristic ant colony optimization-base approaches for traveling salesman problem. Soft Computing, 25:3775-3794, 2021.
[68] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization 2017.
algorithms. arXiv preprint arXiv:
[69] E. Singh and N. Pillay. A study of ant-based pheromone spaces for generation constructive hyper-heuristies. Swarm and Evolutionary Computation, 72:101095, 2022.
[70] R. Skinderowiez. Population-bas based ant colony optimization for sequential ordering problem. In Computational Collective Intelligence: 7th International Conference, ICCCI 2015, Madrid, Spain, September 21-23, 2015, Proceedings, Part II, pages 99-109, Springer, 2015.
[71] R. Skinderowicz. An improved ant colony system for the sequential ordering problem. Comput- & Operations Research, 86:1-17, 2017.
[72] R. Skinderowicz. Improving ant colony optimization efficiency for solving large tsp instances. Applied Soft Computing, 100:108653, 2022.
[73] A. Slowik and H. Kwasnicka. Evolutionary algorithms and their applications to engineering problems. Neural Computing and Applications, 32: 123633112237, 2020.
[74] S. Sohrabi, K. Ziarati, and M. Keshtkaran. Acs-ophs: Ant colony system for the orienteering problem with hotel selection. EURO Journal on Transportation and Logistics, 10: 100036, 2021.
[75] W. Song, N. Mi, Q. Li, J. Zhuang, and Z. Cao. Stochastic economic lot scheduling via self- attention based deep reinforcement learning. IEEE Transactions on Automation Science and Engineering, 2023.
[76] T. Stützle and H. H. Hoos. Max-min ant system. Future generation computer systems, 16(8): 2000.
[77] Y. Sun, S. Wang, Y. Shen, X. Li, A. T. Ernst, and M. Kirley, Boosting ant colony optimization via solution prediction and machine learning. Computers & Operations Research, 143:105769, 2022.
[78] Z. Sun and Y. Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. arXiv preprint htt::2302.082244 2023.
[79] A. Vaswani, N. Shazeer, N. Parmar, Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[80] Vidal. Hybrid genetic search for the evrp: Open-source implementation and swap* neighbor- hood. Computers & Operations Research, 140: 1406400,43, 2022.
[81] T. Vidal, T. G. Crainic, M. Gendreau, N. Lahrichi, and W. Rei. A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 60(3):611 1-644, 2012. doi: 10. 120.1048.
[82] O. Vinyals, M. Fortunato, and N. Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
[83] C. Wang, Z. Yu. S. McAleer, T. Yu, and Y. Yang. Asp: Learn a universal neural solver! arXiv preprint arXiv:2303.004-6 2023.
[84] Y. Wang, L. Wang. G. Chen, Z. Cai, Y. Zhou, and I., Xing. An improved ant colony optimization algorithm to the periodic vehicle routing problem with time window and service choice. Swarm and Evolutionary Computation, 55:100675, Jun 2020. ISSN 2210-6502, doi: 10.1016/j.swevo. 2020.100673
[85] R. J. Williams. Simple statistical gradient-followin algorithms for connectionist reinforcement learning. Reinforcement learning, pages 5-32, 1992.
14

---

[86] Y. Wu. W. Song, Z. Cao, and J. Zhang, Learning large neighborhood search policy for integer programming. Advances in Neural Information Processing Systems, 34:30075-30087, 2021.
[87] Y. Wu, W. Song, Z. Cao, J. Zhang, and A. Lim. Learning improvement heuristics for solving routing problems.. IEEE transactions neural networks and learning systems, 2021.
[88] Y. Wu, J. Zhou, Y. Xia, X. Zhang. Z. Cao, and J. Zhang. Neural airport ground handling. arXiv preprint Xxv:2333.00242, 2023.
[89] I. Xin, W. Song, Z. Cao, and J. Zhang. Multi-decoder attention model with emhedding glimpse for solving vehicle routing problems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12042-12049, 2021.
[90] L. Xin, W. Song, Z. Cao, and J. Zhang. Neurolkh: Combining deep learning model with lin- heelgghnn heuristic for solving the traveling salesman problem. Advances Neural Information Processing Systems, 34:7472-7483, 2021.
[91] H. Ye, H. Liang, T. Yu, J. Wang, and H. Guo. A bi- popooollttion clan-based genetic algorithm for heat cone-cons component layout optimization. Expert Systems with Applications, 213: 1 118881, 2023.
[92] X. Zhou, H. Ma, J. Gu, H. Chen, and W. Deng. Parameter adaptation-baset ant colony opti- mization with dynamic hybrid mechanism. Engineering Applications of Artificial Intellignnce 1 14: 105139, Sep 2022. ISSN 0952-1976. doi: 00.006/f.engaapaii22222. 2t2p:/ennnaaaa.22222011011111 105139.
[93] Y. Zhou, X. Liu, Hu, Y. Wang, and M. Yin. Combining max ant system with effective local search for solving the maximum set k-covering problem. Knowledge-Band -aaseeeee-Bedd Systems, 239: 108000, 2022.
[94] Z. Zong, H. Wang, Wang. M. Zheng, and Y. Li. Rbg: Hierarchically solving large-scale routing problems in logistic systems via reinforcement learning. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4648-4658, 2022.
[95] Z. Zong, M. Zheng, Y. Li, and Jin. Mapdp: Cooperative multi-agent reinforcement learning to solve pickup and delivery problems. In Proceedings of the AAAI Conference Artificial Intelligence, volume 36, pages 9980-99988 2022.
15

---

DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization (Appendix)
Neural architecture
A.1
GNN
For pheromone model PH we employ the neural architecture recommended by Joshi et [48] and Qiu et al. [66] as the GNN backbone, which relies on an anisotropic message passing scheme and edge gating mechanism. The GNN we use has 12 layers. For the [-th layer, we denote the node feature of iú as hy and the edge feature of edge < i,j > as e'g. The propagated features are defined as
h.t2 h¹ + aBBN(U') + (o v'ij)).
(9)
/ e'j + o (BN(P'') Q' R().)).
(10)
where U², V V'P''' E IRdxd are learnable parameters, a denotes the activation function, BN denotes batch normalization [43], AJeN; denotes the aggregation operation over the neighbourhood of 0h a is the sigmoid function, and @ is the Hadamard product. In this paper, we define a as SiLU [28] and as mean pooling.
We map the extracted edge features into real-valued heuristic measures using 3-layer MLP with skip connections [38] to the embedded node feature h We apply SiLU [28] as the activation function except for the output layer, where the sigmoid function is utilized obtain normalized outputs.
A.2 Transformer
For pheromone model itemm the architecture mostly follows the transformer encoder Srum_hidden Sidden_layer layers 3, hidden sscieeesssseee______e_ 32, num attention, heads 2) but deprecates its positional encoding. On top of it, we add position- wise feedforward layers (num hind_ddddenn. _aaeer_aarrrss = size saaee 32) that map the hidden representations of each solution component into its
3, hiddenn real-valued heuristic measure. Overall, it is similar to the neural networks used in [23,35].
B Details of NLS
In NLS, neural-guided perturbation does not involve new neural network other than that introduced in Section 4.1. It directly leverages the learned heuristic measures to guide the perturbation process. Specifically, each time solution reaches local optima, gets perturbed with local search (LS) which iteratively maximizes the heuristic measures of its solution components. Note that NLS can be implemented using an arbitrary LS operator.
Take TSP as an example. With 2-opt as the LS operator, NLS alternates between (a) optimizing solution minimize its tour length and (b) perturbing of its edges. The two processes are similar, except that we use the inverse of heuristic measures in (b) while the distance matrix in (a) as indicators of good edges (line 6 in Algorithm 1). Our training is customized for NLS. The heuristic learner is trained to minimize the expected TSP length of the NLS-refined sampled solutions.
maximize the total heuristic measures
C Extended results
C.1 DeepACO for more COP scales
We evaluate DeepACO on more COP scales and present the results Fig. 9. The evolution curves demonstrate that DeepACO can provide consistent neural enhancement across COP scales.
16

---

2.2
2.4
250
1890
3259
1500
3750
2003
3900
1000
4003
3900
1053 #sfnekuriia
CVRP29
8.0
150
4.5
250
500
1990
1250
1960 3750
2003
150 10.00
1.00
1758
2000
930
150
1900
1900
1750
2900
27.5
250
1890 3250
1568 3150
2003
150 10.00
1500 1758
536
150
30000
1200
1500
1750
2000
115
124
04
250
500
750
1090
3250
1568
3750
2003
150 10.0
1500
1758
2000
530
150
1000
1500
1750
3000
250
500
1000
3250
1568 3750
2003
150 10.00
1500
1758
2000
3300
1390
000
5
25
210
250
300
750
1000
3250
1568
3750
2003
150 eflaaalantra
1000
1500
1758
2000
530
150
3200
1500
1750
3000
120
155
150
155
150
740
1031
1991
1986 1997
2104
197
18:0
1968
1992
200
525
152
1900
1901
1791
4/.-
ACD (AS)
ACO (Ultst)
(MAX- MINI
5753
DeepACO (AS)
DespACO (Elitit)
DeepACO (MIX-MIN)
350
750 1231 1993 1950
1997
2100
197
1900 1992 10:00
Figure 9: Evolution curves of fundamental DeepACO and ACO algorithms eight different COPs with more scales. For each COP, we plot the best-so-far objective value (averaged over 100 held-out test instances) w.r.t. the number of used evaluations along the ACO iterations.
17

---

Table Comparison results on TSPI00.
TSP100
Method
Obj.
Time (s)
AM [54]
7.945
0.36
GCN [47]
7.907
6.13
da Costa et al. [22]
7.821
30.66
Hudson et al. [42]
7.815
10.11
Ar-GCRN+MCTS [32]
7.764
0.53
DeepACO (NLS, T=4)
7.767
0.50
DeepACO (NLS, T=10)
7.763
1.23
Table 4: The comparison results CVRP.
CVRPI00
CVRP400
CVRP1000
CVRP2000
Method
Obj.
Time (s)
Obj.
Time (s)
Obj.
Time (s)
Obj.
Time (s)
AM [54]
16.42
0.06
29.33
0.20
61.42
0,59
114.36
1.87
TAM-LKH3 [41]
16.08
0.86
25.93
1.35
46.34
1.82
64.78
5.63
DecpACO (NLS,T==)
16.07
2.97
25.31
3.65
45.00
10.21
61.89
14.53
DcepACO (N15,T=10)
15.77
3.87
25.27
5.89
44.82
15.87
61.66
35.94
C.2 TSP and CVRP
Table and gather the comparative experimental results on more diverse routing tasks, i.e., TSP100, CVRP100, 400, 1000, and 2000. They demonstrate DeepACO's consistent and competitive performance. "Time" in the tables refers to the duration needed to solve a single instance, and the results of the baselines drawn from their respective papers [41]. NLS for CVRP is based on the local search strategy in the HGS-CVRP algorithm [80, 81].
NLS for CVRP searching among 5 collections of neighborhoods, including SWAP, RELOCATE, 2-opt, 2-opt", and SWAP neighborhood. NLS for CVRP follows Algorithm and apply LSfas as the local search strategy. In practice, we implement the code provided by Vidal [80] and set T Tivs to 1. To be noted that LSwas occasionally produces infeasible solutions, and such solutions are discarded in NLS. We refer the reader to [80] for more details.
The local search strategy proposed by Vidal [80] (denoted LSHGs) consists of
C.3 Generalizability of DeepACO
The generalizability of DeepACO across COPs is rooted in the generalizability of the ACO meta-heuristic and the feasibility to represent many COPs' solutions using binary variables. In paper, we evaluated DeepACO across 8 diverse COPs, including routing, assignment, scheduling, and subset COP types. Furthermore, we extend DeepACO to the Bin Packing Problem (BPP), grouping problem, aiming optimally splitting items into groups. We follow the experimental setup in [58] and demonstrate the consistent neural enhancement provided by DeepACO in Table 5.
Across COPs
Across scales Table compares the performance of ACO, DeepACO trained TSP100, and DeepACO trained on the respective test scale, all implementing vanilla LS (instead of NLS to ensure the execution time for DeepACO and ACO). The results show that DeepACO still outperforms its ACO counterpart even with a significant distributional shift (i.e., from TSP100 to TSP1000).
Table 5: The evolution trend of ACO and DeepACO on the Bin Packing Problem.
T
10
20
30
40
ACO f DeepACO
0.877
0.896
0.902
0.907
0.909
0.910
0.947
0.952
0.954
0.956
0.957
0.958
18

---

Table 6: The generalization performance of DeepACO across TSP scales.
Method
TSP500
TSP1000
ACO (LS)
17.55
24.93
DeepACO (LS, trained on TSP100)
17.18
24.69
DeepACO (LS)
16.98
23.96
C.4 Training duration
As presented in Table 7, DeepACO entails only minutes of training to provide substantial neural
enhancement in Fig. 2. is mainly because our training hybridizes 1) heatmap-baase based on-policy sampling without costly step-by-step neural decoding [66], and 2) parallel multi-start sampling leveraging the solution symmetries [56, 52].
Table 7: Training settings for DeepACO. "m" denotes minutes.
CОP
Problem scale
Total traninig instances
Total training time
TSP
20 / 100 500
640 / 640 / 640
1m / 2m / 8m
CVRP
20 100 500
640 / 640 640
2m / 4m 18m
OP
100 200 300
320 / 320 / 320
4m / 6m 7mm
PCTSP
20 / 100 500
320 320 640
Im / Im 10m
SOP
50/50/ 100
640 / 640 / 640
Im / 2m 4m
SMTWTP
50 / 100 500
640 / 640 640
Im / 2m 11m
RCPSP
30 / 60 120
3200 3200 3200
2m / 4m 8m
MKP
300 500
640 / 640
26m 30m
C.5 Flexibility for a different pheromone model
The pheromone model used in ACO can vary, for the same problem [63]. The pheromone model used in this work models the successive relationships of the nodes in a COP graph, which applies to most COPs but by no means exhaustive. This section aims to show the flexibility of DeepACO for different pheromone models.
Here, we use the Multiple Knapsack Problem (MKP) (formally defined in Appendix D.8) as an example. Section 5.2, we mostly use the pheromone model PH that models successively chosen items [63], where the pheromone trails are deposited on the edges connecting two items. One alternative, i.e., PHitem is to directly model how good each item is, where the pheromone trails deposited on the items, i.e., the graph nodes. On the one hand, PH is reasonable because the quality of an item must be considered in conjunction with how it is combined with other items. On the other hand, P Paeme makes sense because solution to MKP is indariinvariant. Both pheromone models have their own advantages [63] and are used in the recent literature [30, 8].
Isomorphic GNN [48] is applied in this work to PH suc due to its ability to extract edge features. To apply DeepACO to variations of pheromone models, aligned with the pheromone model. As showcase, we use a lightweight Transformer [79] encoder (without positional encoding) with an MLP decoder on top of it to model PHittems for MKP. Under the same experimental setup as in Section 5. we compare DeepACO with its ACO counterparts using P Hittmm for MKP. The results presented Fig. 7 demonstrate that DeepACO using PHitems can also outperform its ACO counterparts. It validates that DeepACO can be readily extended to variations of pheromone models using properly aligned neural models.
necessary to use a neural model properly
C.6 Visualization of the learned heuristic
We visualize the learned heuristic Fig. 10. After the graph sparsification (see Appendix D), we scatter the remaining solution components (i.e., the TSP edges in this case) in unit square by normalizing (in row-wise fashion) their manually designed and learned heuristic measures. We can observe that the solution components with large learned heuristic measure do not necessarily
19

---

TSP20
TSP100
TSP500
1.0
Leamed hautetcc measure
heureete meacure
Leamed messure
0.8
0.6
0.6
0.6
0.4
0.2
0.2
0.2
0.0
0.0
0.2
Visualization of the learned heuristic on TSP. randomly sample a TSP instance p and scatter its learned heuristic measure (p) w.r.t. the manually designed ones, both after normalization. The dashed line represents an identical mapping.
Figure 10:
obtain an equivalently large 1 and vice versa. particular, DeepACO learns a set of more aggressive heuristic measures, where most solution components associated with normalized measures close to zero.
D Benchmark problems
D.1 Traveling Salesman Problem
Definition Traveling Salesman Problem (TSP) seeks the shortest route that visits a given set of nodes and returns the starting node, visiting each node exactly once.
Instance generation Nodes are sampled uniformly from [o, 1]² unit.
Model inputs TSP instance corresponds complete graph. Node features are their coordinates. and edge attributes are relative distances between nodes.
Graph sparsification All nodes are only adjacent to their & nearest neighbors to exclude highly unpromising solution components and speed up computation. The same graph sparsification is conducted for ACO baselines to ensure fair comparison. k is set to 10 for TSP20, 20 for TSP50, 20 for TSPI00, and 50 for TSP500.
Baseline heuristic
The baseline heuristic measure the inverse edge length [72].
D.2 Capacitated Vehicle Routing Problem
Definition Capacitated Vehicle Routing Problem (CVRP) is natural extension TSP that involves multiple vehicles. In CVRP, each vehicle has a limited capacity, and each customer has its own demand that must be satisfied. The objective is to find the optimal route that satisfies all customer demands and minimizes the total distance traveled by the fleet.
Instance generation We follow the same instance generation settings as in previous work [94]. Customer locations are sampled uniformly in the unit square; customer demands are sampled from the discrete set 21.2...., 9): the capacity of each vehicle is set to 50; the depot is located at the center the unit square.
Model inputs We transform a CVRP instance into a complete graph, where the node features are the demand values, and the edge attributes are relative distances between nodes.
Baseline heuristic
The baseline heuristic measure is the inverse of edge length [15].
20

---

D.3
Orienteering Problem
Following the problem setup [54], each node has a prize p;, and the objective the Orienteering Problem (OP) is to form tour that maximizes the total collected prize. The tour starts from a special depot node and should be subject to a maximum length constraint.
Definition
Instance generation We uniformly sample the nodes, including the depot node, from the unit dos [0, 1|2. We use challenging prize distribution [31]: p: (1 99 maxf-, dag 1/100, where doi is the distance between the depot and node i. The maximum length constraint is also designed to be challenging, As suggested by Kool et al. [54], we set 5, and 6 for OP100, OP200, and OP300, respectively.
Model inputs We transform an OP instance into a complete graph. The node features are two- dimensional, consisting of nodes' prizes and distances the depot. The edge attributes are relative distances between nodes. We do not include the maximum length constraint in input features because, in our case, it constant for each problem scale. It is easy to model the constraint explicitly as an additional node feature or context feature, or implicitly by using it to normalize nodes' distances to the depot.
Graph sparsification k is set to 20 for OP100, 50 for OP200, and 50 for OP300.
Baseline heuristic
The baseline heuristic measure Ti
PL day
[74].
D.4 Prize Collecting Traveling Salesman Problem
Definition Prize Collecting Traveling Salesman Problem (PCTSP) is a variant of TSP. In PCTSP, each node has associated prize and penalty. The objective is to minimize the total length of the tour (which visits a subset of all nodes) plus the sum of penalties for unvisited nodes while also ensuring a specified minimum total prize collected.
Instance generation We follow the design of Kool et al. [54] for instance generation. All nodes sampled uniformly in the unit square. The prize for each node is sampled uniformly from (0, 1). As a result, the minimum total prize constraint is set to 2t for PCTSPn, such that n nodes are expected to be visited. The penalty of each node is sampled uniformly from (0, 3L" ). where L is the expected tour length for TSPn and is set to 4, 8, 18 for 20, 100, 500, respectively. For additional depot node, its prize and penalty are set to O.
Model inputs We transform PCTSP instance into a complete graph. The node features are two-dimensional, consisting of nodes' prizes and penalties. The edge attributes are relative distances between nodes.
Baseline heuristic PCTSP related to OP but inverts the goal [54]. The bascline heuristic measure of edge < i, > is Pi [74].
D.5 Sequential Ordering Problem
Definition The Sequential Ordering Problem (SOP) involves finding a consistent and linear ordering of a set of elements. Consider that we have n. jobs to handle sequentially for SOPn. Let æ; be the processing time of job i and by the waiting time between job and j. Specially, job a dummy node, and Zo 0. We also have set of constraints that indicate the precedence between jobs. The objective is to minimize the processing time for all jobs under precedence constraints.
Instance generation We sample both æ; and lij uniformly from (0, 1). We stochastically sample the precedence constraints for all job pairs while ensuring at least one feasible solution and maintaining the constraints' transitive property; if job precedes job j and job precedes job k; then job precedes job k. The probability of imposing the constraint pair of jobs is set to 0.2.
21

---

Model inputs We construct directed graph where each job is node and each job pair < i,J >, as long as job j does not precedes job i, is connected with directed edge. The node feature is z; for job i and the edge attribute for job pair < i.j is lij-
Baseline heuristic The baseline heuristic measure Viy
ty [70, 71].
D.6 Single Machine Total Weighted Tardiness Problem
The Single Machine Total Weighted Tardiness Problem (SMTWTP) is scheduling problem in which set jobs must be processed on single machine. Each job has processing time Pi, weight wi, and due date 4, The objective is to minimize the sum of the weighted tardiness of jobs, where the weighted tardiness is defined as the product of job's weight and the duration by which its completion time exceeds the due date.
Definition
Instance generation Due dates, weights, and processing time are sampled as follows: t2 x (0, 1), w; ~ Uni(O, 1), Uni(0, 1).
Model inputs To ensure that all jobs can be the first to get processed, we include dummy job with all its features set to zero. Then, we transform an SMTWTP instance into directed complete graph with n + nodes. The features of a node are its normalized due date and weight. The attribute of edge < i,j > is Pj-
Baseline heuristic
The baseline heuristic prefers jobs with shorter due time: Maj = 1) [1].
D.7 Resource-Constraanne Project Scheduling Problem
Definition Resource-Constraine Project Scheduling Problem (RCPSP) is to schedule set of activities and minimize the schedule's makespan while satisfying precedence and resource constraints.
Instances Due to the complexity of generating random RCPCP instances, we draw the instances from PSPLIB [53] for training and held-out test.
Model inputs As stated by Gonzalez- Pardo et al. [36], parallelism is not allowed if we sample directly from the constraint graph. So the input graph is an extension of it by adding edges between unrelated nodes, i.e., the edge between node and j (i o j) exists only if j & S A & Sj, where S denotes all the successors (direct and indirect) of node on the constraint graph.
ACO algorithm The ACO algorithm follows the architecture proposed by Merkle et al. [62] but without the additional features. We sample the solutions in a topological order accelerate the convergence.
The baseline heuristic the combination of the greatest rank positional weight all (GRPWA) heuristic, and the weighted resource utilization and precedence (WRUP) heuristic [62].
Baseline heuristic
D.8 Multiple Knapsack Problem
Knapsack Problem (KP) is to select subset of items from given such that the total weight of the chosen items does not exceed a specified limit and the sum of their values is maximized. Multiple Knapsack Problem (MKP), also known as m-dimensional Knapsack Problem, impose m different constraints on m types of weight. Formally, MKP can be formulated as follows:
Definition
maximize
(11)
s.t.
Σ
Wij 5 Ci i= I,..., m,
1=1
Øj E {0, 1], j= j=1,... I.....
22

---

Here, U/ is the value of the item j. way is the i-th type of weight of the item j, and 2 is the decision variable indicating whether the item j is included in the knapsack.
Instance generation The values and weights are uniformly sampled from [0, 1]. To make all instances well-stated [57], we uniformly sample o; from (max Waj Σ wiy).
Model inputs For PH we transform an MKP instance into complete directed graph. The node features are their weights. The attribute of edge i,j is te. For PH the model input is m + 1-dimensional feature vectors items. The feature vector of item j is concatenation of Vij and Wij. 1, normalized by dividing Ca2 i 1, ,,..., respectively.
Baseline heuristic For Pluc the baseline heuristic Tke baseline heuristic 72 Σ3 wej [30].
[30]. For itetme the
Σn wky
D.9 Bin Packing Problem
Definition
The objective of the Bin Packing Problem (BPP) is to optimally arrange items within containers of specific capacity, in order to reduce the overall number of containers used. We follow the specific setup [58].
Instance generation Following [58], we set the number of items to 120 and the bin capacity to 150. Item sizes are uniformly sampled between 20 and 100.
Model inputs We transform BPP instance into complete graph where each node corresponds to an item. Node features are their respective item sizes, while edge features are set to We additionally include dummy node with 0 item size as an unbiased starting node for solution construction.
Baseline heuristic Heuristic measure an item equals size [58]; that is, the heuristic measure of solution component in PH is the item size of its ending node.
23


Reviews:
[{"review_id": "a9K5Faddzv", "reviewer": "Reviewer_hKqX", "summary": "This article proposes DeepACO, which is a generic framework leveraging deep reinforcement learning to automate heuristic designs.\nDeepACO serves to strengthen the heuristic measures of existing ACO algorithms.\nAccording to the experiments, DeepACO consistently outperforms its ACO counterparts on eight COPs using a single neural model and a single set of hyperparameters. It also performs better than or competitively against the problem-specific methods on the canonical Travelling Salesman Problem.\n\nThe article reviews the related works, explains ACO and the proposed methodology, and presents the experiments: their settings results and analysis. It is followed by supplementary materials.\n", "questions": "Question to Fig. 6: does it make sense to combine all the extensions and use them at once?", "limitations": "The authors adequately discussed the limitations.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 2, "strengths": "It is a well-written paper and I enjoyed reading it. All important concepts seem to be clearly explained.\nThe method was tested in 8 benchmark problems which is a huge strength. On all of them, DeepACO outperformed standard ACO methods.\nIn general, the results of the experiments are very good. The limitations of the method are discussed as well and the authors declared that the code used in experiments will be made publicly available and I found it in supplementary materials, indeed.\n", "weaknesses": "For some reason, hyperlinks to the bibliography do not work in the PDF that I received. I didn't find information on how the parameters alpha and beta (control parameters) were set in experiments. The writing can be slightly improved:\n- p.7: \"On the other hand\" appears at the beginning of 2 consecutive sentences, so maybe in 1 of those sentences, it can be substituted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer hKqX\n\nTo begin with, we are encouraged that you enjoyed reading our paper and we sincerely appreciate your insightful feedback. Below, we provide our point-to-point response.\n\n> W1: Hyperlinks to the bibliography do not work.\n\nWe sincerely regret any inconvenience caused by the hyperlink issue. We'll ensure the hyperlinks to the bibliography work in the final version.\n\n> W2: Missing information on how the parameters alpha and beta (control parameters) were set.\n\nThank you for pointing this out. We've consistently set alpha and beta as 1 during our experiments, except when testing for hyperparameter robustness in Fig. 4. This setting will be incorporated into the final edit.\n\n> W3: writing can be slightly improved on p.7.\n\nThank you for this suggestion. We will rephrase the sentence to avoid repetition.\n\n> Q: In Fig. 6, does it make sense to combine all the extensions and use them at once?\n\nThank you for this insightful question. Yes, we can combine them since they are not mutually exclusive. However, combining all of them may not be more effective than implementing just one. This is because they are designed for a similar purpose, and a combination entails tuning more hyperparameters for effective training."}, {"review_id": "Qxe5HDHMlR", "reviewer": "Reviewer_YjbH", "summary": "This paper presents DeepACO, a neural-enhanced solution to the limitations of Ant Colony Optimization (ACO) meta-heuristics, namely, the laborious manual design of heuristic measures and their heavy reliance on expert knowledge. ACO, which is a foraging system inspired by ant colonies, deploys artificial ants to explore solution spaces, and these solutions are biased toward promising areas through pheromone trails and heuristic measures. DeepACO innovates by learning a problem-specific mapping from an instance to its heuristic measures, leveraging neural models across instances, and incorporating these measures into ACO to influence solution constructions and help escape local optima. The paper also proposes three extended implementations of DeepACO to balance exploration and exploitation. DeepACO outperforms traditional ACO methods and is competitive against state-of-the-art and problem-specific Neural Combinatorial Optimization (NCO) methods across eight combinatorial optimization problems, even with only minutes of training.", "questions": "Could you provide further insight into the \"3D heuristic measures\" or \"dynamic heuristics\" you mention in the conclusion? How might they help to overcome the limitations of the current implementation?\n\nHow do you see DeepACO being applied in real-world situations? What kind of problems do you envision it solving most effectively?\n\nCould you discuss more about the process and challenges of training the deep reinforcement learning (DRL) model for guiding the evolution of ACO meta-heuristics?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Novelty: The paper proposes DeepACO, a new approach to enhancing Ant Colony Optimization (ACO) algorithms through a neural-enhanced meta-heuristic. This application of deep reinforcement learning to ACO is stated as being the first of its kind, thereby representing an innovative contribution to the field.\n\nBroad Applicability: DeepACO has been tested across eight different Combinatorial Optimization Problems (COPs), indicating its versatility and adaptability. It also shows competitive performance with specialized Neural Combinatorial Optimization (NCO) methods on the Travelling Salesman Problem (TSP), suggesting it is a robust method.\n\nAutomation: The paper presents a method to automate the design of heuristics for future ACO applications, potentially saving significant manual effort and expert knowledge.", "weaknesses": "Limitations in Current Implementation: The authors themselves note that DeepACO may underperform when not incorporating local search (LS) components due to the current restriction of compressing all learned heuristic information into an n × n matrix. This could limit the solution's effectiveness in complex COPs.\n\nAbsence of Comparison to Other Methods: While the paper mentions that DeepACO outperforms other ACO methods and is competitive with specialized NCO methods, there's no mention of a comparison with other non-ACO or non-NCO optimization methods. This could limit the ability to gauge how novel or effective DeepACO truly is in the broader context of optimization techniques.\n\nDependence on Machine Learning: The performance of DeepACO appears to be heavily dependent on machine learning. While this isn't necessarily a weakness, it could limit its application in situations where computational resources are restricted, or where machine learning models are difficult to train due to lacking training data.\n\nUnclear Generalizability: Although DeepACO is tested on eight different COPs, it's unclear how it would perform on a broader range of problems, particularly those that don't closely resemble the tested ones. More comprehensive testing across a diverse set of problems and datasets would provide stronger evidence of its generalizability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer YjbH\n\nWe appreciate the time and effort you have dedicated to reviewing our submission. Your comments have provided us with a fresh perspective and have undoubtedly enhanced the quality of our work. Below we present our point-to-point response.\n\n---\n\n## Response to Weaknesses\n\n> W1: Limitations in Current Implementation: The authors themselves note that DeepACO may underperform when not incorporating local search (LS) components.\n\nWe acknowledge the limitation of compressing learned heuristics into an n $\\times$ n matrix. It is a limitation inherited from ACO as well as other constructive (meta-)heuristics for COPs. Since we directly sample solutions on this matrix (probabilistic graph), addressing this limitation leads to constructing higher-quality COP solutions in one shot with O(n) complexity. It is an exciting direction for future work, and we present several possible avenues toward it in our response to Q1.\n\n> W2: Absence of Comparison to non-ACO/NCO Methods\n\nWe appreciate the reviewer highlighting the opportunity for comparison with non-ACO/NCO methods. As this work focuses on enhancing ACO algorithms with NCO techniques, we believe comparisons within these two domains are most relevant and fair. We agree further comparisons would provide a more holistic evaluation, and have added comparisons with Guided Local Search in our Global Response, showing DeepACO's superior performance on TSP.\n\n\n> W3: Dependence on Machine Learning: demanding computational resources and training data.\n\nWe believe the reasons below can help address your concern and make DeepACO widely accessible.\n\n- **Low computational demand.** DeepACO only requires **minutes** of training (Appendix B.2) and a lightweight model (~50k parameters) to provide substantial neural enhancement. Moreover, we observed that training DeepACO solely on a **CPU**, rather than utilizing a GPU, even accelerates the training process on our hardware. This expedited training is primarily because most of the computational time is spent on on-policy solution sampling, rather than on the forward and backward neural network propagation.\n\n- **Minimal reliance on (real-world) training data.** DeepACO requires only **a few hundred training instances** in most tasks to achieve significant neural enhancement (Appendix B.2). Furthermore, when obtaining a realistic data distribution is challenging, we can confidently train DeepACO on algorithmically generated (Appendix C) **inexhaustible synthetic data** and generalize it effectively. Fig. 5 shows that DeepACO trained on fixed-scale and uniform synthetic data can clearly outperform its ACO counterparts on variable-scale real-world benchmarks.\n\n> W4: Unclear Generalizability: More comprehensive testing across a diverse set of problems and datasets would provide stronger evidence of its generalizability.\n\nThe generalizability of DeepACO is rooted in the generalizability of the ACO meta-heuristic and the feasibility to represent many COPs' solutions using binary variables. In our paper, we evaluated DeepACO on **26 datasets** (please also refer to Appendix B.1 for more details) spanning **8 diverse COPs**, including routing, assignment, scheduling, and subset COP types, which do not resemble one another. Furthermore, DeepACO can be extended to an even broader range of COPs (e.g., Karp's 21 NP-complete problems), as exemplified in our general response.\n\n---\n\n## Response to Questions\n\n> Q1: further insight into the \"3D heuristic measures\" or \"dynamic heuristics\"\n\n\"3D heuristic measures\" and \"dynamic heuristics\" are possible extensions of the current 2D heuristic matrix, allowing for compressing more learned heuristics of a COP. It is possible that we can realize such extensions in various ways, where two possibilities are described below.\n\n- One option is to assign each ant its unique heuristic matrix and collaboratively train the ant population using individual-specific \"niching loss\" (inspired by the niching methods in Evolutionary Computation). In this manner, we obtain 3D heuristic measures, allowing for cooperatively exploring multiple optima of complex COPs or the Pareto front of multi-objective COPs.\n\n- Another possible approach, i.e., dynamic heuristics, generates heuristic measures at various points either throughout the solution-constructing process or during ACO iterations. In the first scenario, heuristic measures can be generated based on partial solutions. In the second scenario, we can learn to adapt the heuristic measures according to the updated pheromone trails.\n\n> Q2: How do you see DeepACO being applied in real-world situations? What kind of problems do you envision it solving most effectively?\n\nThe ACO metaheuristic already has broad applicability in real-world situations [1]. DeepACO takes it one step further by dispensing with the required expert knowledge and automatically enhancing its performance, thereby extending its applications to scenarios involving more complex and black-box COPs. We believe it is particularly competitive for problems with little or suboptimal expert knowledge, as well as when instances to solve follow similar distributions.\n\n[1] Dorigo, M., & Stützle, T. (2019). *Ant colony optimization: overview and recent advances* (pp. 311-351). Springer International Publishing.\n\n\n> Q3: the process and challenges of training the deep reinforcement learning (DRL) model\n\nTo train a DRL model for ACO, we need to (1) build a simulation environment based on COP constraints and ACO algorithm, (2) determine the distribution for sampling synthetic instances or gather real-world data, (3) set the RL reward based on COP objective, and (4) code the RL algorithm. Overall, DeepACO is relatively easy to train. Most coding effort was spent on building the simulation environment for each problem to enable efficient parallel solution sampling. By comparison, less effort was spent on the DRL training part, which is generic for different problems."}, {"review_id": "RMlLo2TQmQ", "reviewer": "Reviewer_BitH", "summary": "This paper proposes DeepACO, a generic framework leveraging deep reinforcement learning to automate heuristic designs. Specifically, DeepACO serves to strengthen the heuristic measures of existing ACO algorithms and dispense with laborious manual design in future ACO applications.  Experiments demonstrate that DeepACO consistently outperforms its ACO counterparts on eight combinatorial optimization problems (COPs). \t", "questions": "Please refer to Weaknesses for my questions.", "limitations": "Yes. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. To the best of my knowledge, this work is the first to exploit deep reinforcement learning to guide the evolution of ACO meta-heuristics.   \n2. Experiments demonstrate that DeepACO consistently outperforms its ACO counterparts on eight combinatorial optimization problems (COPs). \t\n", "weaknesses": "1. Previous work [1] has proposed a data-driven Heuristics Schedule framework in modern mixed-integer linear programming (MILP) solvers. The authors may want to discuss the major novelty of this work over previous work.  \n2. It would be more convincing if the authors could show some generalization results, as the ability of generalizing to larger instances is also important in solving MILPs. \n\n[1] Chmiela, Antonia, et al. \"Learning to schedule heuristics in branch and bound.\" Advances in Neural Information Processing Systems 34 (2021): 24235-24246.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer BitH\n\nThank you for your time and effort in reviewing our submission, and we appreciate the fresh perspective you've offered. Below, we provide a thorough point-to-point response, trying to address each of your remarks.\n\n> W1: The authors may want to discuss the major novelty of this work over previous work [1].\n\nThe two works tackle different problem domains with different goals, learned components, and training methodologies. DeepACO provides a flexible neural enhancement framework for ACO, while [1] optimizes heuristic scheduling within a branch and bound solver. The techniques are largely complementary.\n\nThe key differences between the two works are as follows.\n\n- **Problem domains.** DeepACO focuses on combinatorial optimization and is based on ACO metaheuristics. In contrast, [1] targets mixed integer programming problems and operates within a branch and bound solver framework.\n\n- **Complementary goals.** Many combinatorial optimization problems can be formulated as Mixed Integer Linear Programs. MILP is a powerful tool for solving them exactly, especially for moderate-sized instances. However, for large, complex, and even black-box problems, using MILP may become infeasible. In such cases, (meta-)heuristics can be used to find good-quality solutions efficiently.\n\n- **Learned components.** DeepACO learns heuristic measures to guide the ACO construction process. [1] learns ordering and iteration limits for primal heuristics during branch and bound.\n\n- **Training methodology.** DeepACO leverages deep reinforcement learning to train neural networks across problem instances. [1] formulates training as an optimization problem using collected heuristic performance data.\n\n[1] Chmiela, Antonia, et al. \"Learning to schedule heuristics in branch and bound.\" Advances in Neural Information Processing Systems 34 (2021): 24235-24246.\n\n> W2: It would be more convincing if the authors could show some generalization results.\n\nThank you for bringing this to our attention. In Fig. 5, we demonstrate that DeepACO can generalize across scales and distributions while preserving its neural enhancement. Moreover, additional generalization results are presented in our **Global Response**, where we effectively generalize DeepACO trained on TSP100 to TSP1000, and extend DeepACO to even larger-scale CVRP."}, {"review_id": "fIymzLkwlJ", "reviewer": "Reviewer_d7BW", "summary": "This paper proposes a method to improve the performance of existing meta-heuristic algorithms using deep neural networks. At the same time, the method described in this paper makes it possible to design a high-performing meta-heuristic without requiring expert domain knowledge. In particular, the study in this paper is generally applicable to many types of COPs. This paper presents a deep neural network model to output the heuristic measure of ACO, as well as a training method for it. In addition, a neural-guided pertubating method is presented in the local search process. Experiments were conducted on 8 different types of CO problems, which showed that DeepACO significantly improves the performance of conventional ACO. It also showed excellent results when compared with the recent NCO studies. Finally this paper is excellently written and well organized. ", "questions": "**Q1.** Please explain in more detail about neural-guided perturbation in 4.2. (refer to W2)  \n\n**Q2.** Since $\\tau_{i,j}$ is fixed to $1$ when training a heuristic learner(line 183), $\\tau$ is not considered in the training process. However, in Figure 4, DeepACO is robust against changes in alpha. What makes DeepACO robust to changes in alpha?  \n\n**Q3.** In line 252, you wrote \"We extend DeepACO from $PH_{suc}$ to $PH_{items}$ using a Transformer encoder equipped with an MLP decoder\". This is a new neural network different from the heuristic learner described in 4.3. Please explain in detail about this neural network.\n\n**Q4.** How many TSP test instances were used in the experiment in Table 1 and Table 2? ", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "**S1.** The method of combining meta-heuristic and deep neural networks is novel and applicable to various types of CO problems.  \n\n**S2.** The performance of the ACO meta-heuristic has been greatly improved by deepACO. In addition, the experiments were appropriately designed and performed.  \n\n**S3.** Compared to recent studies on NCO, DeepACO's performance was shown to be superior. \n", "weaknesses": "**W1.** In section 5.3, it is difficult to conclusively state that DeepACO demonstrates state-of-the-art performance when compared to the latest NCOs, because only the TSP500 and TSP1000 tasks are being used for comparison with existing NCOs. It would be nice to have comparative experiment results with existing NCOs for more diverse tasks. For example, adding CVRP 500/1000 experiments or adding TSP 100/CVRP 100, etc.  \n\n**W2.** In section 4.2, details about neural-guided perturbation are lacking. Specifically, there is a lack of explanation regarding the structure of the neural network used for perturbation, as well as details on the input and output of the network, and the processes of learning and inference.  \n\n​", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "# Response to Reviewer d7BW\nWe appreciate your insightful comments and constructive suggestions. Below we present our point-to-point response.\n\n---\n\n### Response to Weaknesses\n\n> W1. It would be nice to have comparative experiment results with existing NCOs for more diverse tasks, e.g., CVRP 500/1000 or TSP 100/CVRP 100.\n\nThank you for raising this concern. We have added the suggested experiments and presented the results in our **Global Response**. They demonstrate DeepACO's competitive performance across diverse combinatorial optimization tasks (TSP100, CVRP100, 400, 1000, and 2000).\n\n> W2. In section 4.2, details about neural-guided perturbation are lacking, i.e., the structure of the neural network, its input and output, and its processes of learning and inference.\n\nNeural-guided perturbation does not involve a new neural network other than that introduced in Section 4.1. It directly leverages the learned heuristic measures $\\eta_{\\theta}$ to guide the perturbation process. Specifically, each time a solution reaches local optima, it gets perturbed with local search (LS) which iteratively maximizes the heuristic measures of its solution components. Note that NLS can be implemented using an arbitrary LS operator.\n\nTake TSP as an example. With 2-opt as the LS operator, NLS alternates between (a) optimizing a solution to minimize its tour length and (b) perturbing it to maximize the total heuristic measures of its edges. The two processes are similar, except that we use the inverse of heuristic measures in (b) while the distance matrix in (a) as indicators of good edges (line 6 in Algorithm NLS). Our training is customized for NLS. The heuristic learner is trained to minimize the expected TSP length of the NLS-refined sampled solutions.\n\nRegarding the heuristic learner introduced in Section 4.1, it utilizes the neural architecture described in lines 155-158 and Appendix A. The inputs and outputs of this learner are COP graphs as detailed in Appendix C, and learned heuristic measures, respectively. Its training process is described in Section 4.3, and it follows the ACO algorithm introduced in Section 3 during inference.\n\n---\n\n### Response to Questions\n\n> Q1. Please explain in more detail about neural-guided perturbation in 4.2.\n\nPlease refer to our response to W2.\n\n> Q2. What makes DeepACO robust to changes in alpha?\n\nThank you for this insightful question. Traditionally, $\\alpha$ is tuned to balance pheromones and heuristics for controlling convergence speed. Both premature convergence and slow convergence could lead to poor solutions. In DeepACO, the learned heuristic measures already provide a close-to-optimal initial search point. As a result, controlling convergence speed becomes less critical.\n\n> Q3. Please explain in detail about the neural network used for $PH_{items}$.\n\nThe neural architecture used for $PH_{items}$ is detailed below and will be added to our paper.\n\nThe architecture mostly follows the transformer encoder (num_hidden_layers=3, hidden_size=32, num_attention_heads=2) but deprecates its positional encoding. On top of it, we add position-wise feedforward layers (num_hidden_layers=3, hidden_size=32) that map the hidden representations of each solution component into its real-valued heuristic measure. Overall, it is similar to the neural networks used in [1,2].\n\n> Q4. How many TSP test instances were used in the experiment in Table 1 and Table 2?\n\nAs in previous works, we utilized the datasets released in [3], each comprising 128 test instances. This information will be added to the paper.\n\n---\n\n**References**\n\n[1] Devlin, J., Chang, M. W., Lee, K., & Toutanova, K. (2018). Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805.\n\n[2] Goh, Y. L., Lee, W. S., Bresson, X., Laurent, T., & Lim, N. (2022). Combining reinforcement learning and optimal transport for the traveling salesman problem. arXiv preprint arXiv:2203.00903.\n\n[3] Fu, Z. H., Qiu, K. B., & Zha, H. (2021). Generalize a small pre-trained model to arbitrarily large TSP instances. In Proceedings of the AAAI conference on artificial intelligence (Vol. 35, No. 8, pp. 7474-7482)."}]

Author rebuttal:
# Global Response

We are grateful to the reviewers for their insightful feedback and for recognizing the merit of our paper, e.g., novelty (Reviewer YjbH, BitH, d7BW), generalizability (Reviewer hKqX, YjbH, d7BW), effectiveness (Reviewer YjbH, BitH, d7BW), excellent presentation (Reviewer hKqX, d7BW). We have tried our best to address your primary concerns and will also rectify all minor issues raised. 

In our paper, we evaluated DeepACO on 26 datasets (please also refer to Appendix B.1) spanning 8 diverse COPs, including routing, assignment, scheduling, and subset COP types. To further demonstrate the generalizability and superiority of DeepACO, we perform additional experiments with more diverse tasks/scales and introduce more baselines. Before responding to each reviewer's specific comments, we present additional experimental results here.

---

(*Review YjbH-W2*) The table below compares DeepACO with Guided Local Search, a non-ACO/NCO metaheuristic used in Google OR tools, and reported to be “generally the most efficient metaheuristic for vehicle routing [1]”. The results show DeepACO's superior performance on TSP.

||TSP100||TSP500||TSP1000||
|-|-|-|-|-|-|-|
||Obj.|Time|Obj.|Time|Obj.|Time|
|Guided Local Search|7.83|10s|17.32|20s|24.29|40s|
|DeepACO (ours)|7.76|1.2s|16.86|10s|23.85|32s|

---

(*Review YjbH-W4*) The table below showcases that DeepACO can be extended to an even broader range of COPs. Specifically, we additionally tackle Bin Packing Problem (BPP), a grouping problem, aiming to optimally split items into groups. We follow the experimental setup described in [2] and demonstrate DeepACO’s consistent neural enhancement.

T|1|5|10|20|30|40
-|-|-|-|-|-|-
ACO $\uparrow$|0.877|0.896|0.902|0.907|0.909|0.910
DeepACO $\uparrow$|0.947|0.952|0.954|0.956|0.957|0.958

---

(*Reviewer BitH-W2*) The table below compares the performance of ACO, DeepACO trained on TSP100, and DeepACO trained on the respective test scale, all implementing vanilla LS (instead of NLS to ensure the same execution time for DeepACO and ACO). The results show that DeepACO still outperforms its ACO counterpart even with a significant distributional shift (i.e., from TSP100 to TSP1000).

||TSP500|TSP1000|
|-|-|-|
ACO (LS)|17.55|24.93|
|DeepACO (LS, trained on **TSP100**)|17.18|24.69|
|DeepACO (LS)|16.98|23.96|

---

(*Reviewer d7BW-W1, BitH-W2*) The tables below gather the comparative experimental results with existing NCO methods for more diverse tasks, i.e., CVRP100, 400, 1000, 2000 and TSP100. They demonstrate DeepACO's consistent and competitive performance. The NLS strategy for CVRP is based on the SWAP* neighborhood [3].

|                   | CVRP100      | CVRP400      | CVRP1000      | CVRP2000      |
| -----             | -----        | -----        | -----         | -----         |
| AM [4]            | 16.42(0.06s) | 29.33(0.20s) | 61.42(0.59s)  | 114.36(1.87s) |
| TAM-LKH3 [5]      | 16.08(0.86s) | 25.93(1.35s) | 46.34(1.82s)  | 64.78(5.63s)  |
| DeepACO(NLS,T=4)  | **16.07**(2.97s) | **25.31**(3.65s) | **45.00**(10.21s) | **61.89**(14.53s) |
| DeepACO(NLS,T=10) | **15.77**(3.87s) | **25.27**(5.89s) | **44.82**(15.87s) | **61.66**(35.94s) |

|                     | TSP100        |
| -----               | -----         |
| AM [4]              | 7.945(0.36s)  |
| GCN [6]             | 7.907(6.13s)  |
| da Costa et al. [7] | 7.821(30.66s) |
| Hudson et al. [8]   | 7.815(10.11s) |
| Att-GCRN+MCTS [9]   | 7.764(0.53s)  |
| DeepACO(NLS,T=4)    | 7.767(0.50s)  |
| DeepACO(NLS,T=10)   | **7.763**(1.23s)  |

---

**References**

[1] Google. Google or-tools.

[2] Levine, J., & Ducatelle, F. (2004). Ant colony optimization and local search for bin packing and cutting stock problems. Journal of the Operational Research Society, 55(7), 705-716.

[3] Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. *Computers & Operations Research*, *140*, 105643.

[4] Kool, W., van Hoof, H., & Welling, M. (2019). Attention, Learn to Solve Routing Problems! (arXiv:1803.08475). arXiv.

[5] Hou, Q., Yang, J., Su, Y., Wang, X., & Deng, Y. (2023). Generalize Learned Heuristics to Solve Large-scale Vehicle Routing Problems in Real-time. The Eleventh International Conference on Learning Representations.

[6] Joshi, C. K., Laurent, T., & Bresson, X. (2019). An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem (arXiv:1906.01227). arXiv.

[7] Costa, P. R. d O., Rhuggenaath, J., Zhang, Y., & Akcay, A. (2020). Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning. Proceedings of The 12th Asian Conference on Machine Learning, 465–480.

[8] Hudson, B., Li, Q., Malencia, M., & Prorok, A. (2022). Graph Neural Network Guided Local Search for the Traveling Salesperson Problem (arXiv:2110.05291). arXiv.

[9] Fu, Z. H., Qiu, K. B., & Zha, H. (2021). Generalize a small pre-trained model to arbitrarily large TSP instances. In Proceedings of the AAAI conference on artificial intelligence (Vol. 35, No. 8, pp. 7474-7482).

Meta-review: This paper proposes ways to use deep RL algorithms for automating the heuristic designs of the ACO (Ant Colony Optimization) algorithms for Combinatorial Optimization Problems (COPs). The authors then show via experiments their algorithm DeepACO performs better than the heristic baselines in the Traveling Salesman Problem. Although tepidly the reviewers agreed on the value and novelty of this work. There was good amount of enthusiasm for the experimental results shown in the paper.
Decision: Accept (poster)