DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization

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.

Strengths

**S1.** The method of combining meta-heuristic and deep neural networks is novel and applicable to various types of CO problems. **S2.** The performance of the ACO meta-heuristic has been greatly improved by deepACO. In addition, the experiments were appropriately designed and performed. **S3.** Compared to recent studies on NCO, DeepACO's performance was shown to be superior.

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. **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. ​

Questions

**Q1.** Please explain in more detail about neural-guided perturbation in 4.2. (refer to W2) **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? **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. **Q4.** How many TSP test instances were used in the experiment in Table 1 and Table 2?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

N/A

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).

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. 2. Experiments demonstrate that DeepACO consistently outperforms its ACO counterparts on eight combinatorial optimization problems (COPs).

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. 2. 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. [1] Chmiela, Antonia, et al. "Learning to schedule heuristics in branch and bound." Advances in Neural Information Processing Systems 34 (2021): 24235-24246.

Questions

Please refer to Weaknesses for my questions.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes.

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.

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. Broad 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. Automation: 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. Absence 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. Dependence 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. Unclear 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.

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? How do you see DeepACO being applied in real-world situations? What kind of problems do you envision it solving most effectively? Could you discuss more about the process and challenges of training the deep reinforcement learning (DRL) model for guiding the evolution of ACO meta-heuristics?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

N/A

Summary

This article proposes DeepACO, which is a generic framework leveraging deep reinforcement learning to automate heuristic designs. DeepACO serves to strengthen the heuristic measures of existing ACO algorithms. According 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. The 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.

Strengths

It is a well-written paper and I enjoyed reading it. All important concepts seem to be clearly explained. The method was tested in 8 benchmark problems which is a huge strength. On all of them, DeepACO outperformed standard ACO methods. In 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.

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: - 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.

Questions

Question to Fig. 6: does it make sense to combine all the extensions and use them at once?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

2 fair

Limitations

The authors adequately discussed the limitations.

Thanks for the response

Thanks for the response. I have read the rebuttal and the other reviews. I have no further questions.

Follow up

Dear Reviewer, We would appreciate if you would you be so kind as to acknowledge and respond to the authors' rebuttal. This is crucial to ensure the reviewing process is conducted adequately. AC