PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization

Haoran Ye, Jiarui Wang, Zhiguang Cao, Helan Liang, Yong Li

arXiv:2309.14032v2cs.NEcs.AIcs.LG

TL;DR

ACO customization traditionally depends on expert-designed heuristics, motivating a more automated approach. DeepACO uses deep reinforcement learning to learn heuristic measures that enhance ACO, and it outperforms ACO counterparts across eight COPs while matching or exceeding specialized routing NCO methods.

  • Problem

    ACO customization relies on expert knowledge and manual tuning of heuristic measures, creating flexibility and design challenges across COPs.

  • Method

    DeepACO learns heuristic measures across instances with deep reinforcement learning and uses them to enhance existing ACO algorithms.

  • Results

    DeepACO consistently outperforms ACO counterparts across eight COPs and performs better than or on par with problem-specific NCO methods on canonical routing problems.

  • Takeaways & Limitations

    DeepACO provides a general framework for neural enhancement and automation of ACO heuristic design across diverse COPs.

  • Takeaways & Limitations

    Compressing learned heuristic information into an n × n matrix may limit solution quality on complex COPs without local-search components.

Abstract

from arXiv · show

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

1 Introduction

DeepACO addresses the expert-dependent design of ACO heuristics by learning heuristic measures across instances with deep reinforcement learning. It strengthens ACO across eight COPs and performs competitively with specialized NCO methods on routing problems.

  • 1 Introduction: ACO customization requires expert knowledge and manual tuning, making it effortful, inflexible, and difficult for less-studied problems.The challenge is specifically the design of effective problem-specific heuristic measures.
  • 1 Introduction: DeepACO learns a problem-specific mapping from instances to heuristic measures, then uses those measures to guide instance-specific pheromone learning during ACO solving.The framework therefore replaces fixed, manually designed heuristics with learned measures.
  • 1 Introduction: DeepACO consistently outperforms ACO counterparts across eight COPs using one neural architecture and one hyperparameter set after minutes of training.It also performs better than or competitively against state-of-the-art and problem-specific NCO methods on canonical routing problems.
  • 1 Introduction: DeepACO combines neural heuristic learning with ACO and offers extended implementations that balance exploration and exploitation.The paper presents three such extensions intended for broad application to heatmap-based NCO methods.

2 Related work

Related NCO methods combine neural models with heuristics, while ACO provides general-purpose algorithmic frameworks requiring problem-specific customization. DeepACO is positioned as a more flexible hybrid approach spanning eight COPs rather than focusing mainly on routing.

  • 2 Related work: DeepACO belongs to hybrid NCO methods that use neural learners within heuristics or generate heatmaps for subsequent algorithmic procedures.Hybrid methods complement end-to-end neural construction with heuristic decisions or downstream search.
  • 2 Related work: End-to-end NCO methods can be efficient, but their constructed solutions may benefit from iterative refinement and algorithmic hybridization.This motivates hybrid approaches that combine neural components with search procedures.
  • 2 Related work: Unlike existing hybridized methods that mostly focus on limited routing problems, DeepACO provides neural enhancement across routing, assignment, scheduling, and subset COPs.The paper describes this as broader flexibility and evaluation across eight COPs.
  • 2 Related work: Representative ACO frameworks support customization through heuristic measures, local search, and algorithmic hybridization rather than competing directly with every problem-specific ACO.DeepACO is intended to strengthen these frameworks.
  • 2 Related work: DeepACO differs from hyper-heuristics and ML-ACO by requiring less prior knowledge than expert-designed heuristic selection, generation, or feature-based supervised learning.ML-ACO is described as tailored to Orienteering Problem features and specialized optimal-solution supervision.

3 Preliminary on Ant Colony Optimization

ACO models COPs with construction graphs, pheromone trails, and heuristic measures, then iteratively constructs solutions, optionally refines them locally, and updates pheromones. Solution construction is probabilistically biased toward promising feasible components.

  • 3 Preliminary on Ant Colony Optimization: A COP model defines a discrete search space, constraints, and an objective function, with feasible solutions satisfying all constraints.A feasible solution is a complete assignment of the decision variables.
  • 3 Preliminary on Ant Colony Optimization: ACO represents solution components as edges in a construction graph and associates each with pheromone trails and heuristic measures indicating promise.Pheromone trails are iteratively updated, whereas heuristic measures are typically predefined and fixed.
  • 3 Preliminary on Ant Colony Optimization: An ACO iteration consists of solution construction, optional local-search refinement, and pheromone updating.Updates increase trails for components in superior solutions and decrease trails for inferior ones, with rules varying by ACO variant.
  • 3 Preliminary on Ant Colony Optimization: During solution construction, ants choose feasible next components with probabilities weighted by pheromone trails and heuristic measures.A complete solution requires an n-step graph traversal, and its generation probability factorizes across construction steps.
  • 3 Preliminary on Ant Colony Optimization: DeepACO extends the ACO pipeline by learning stronger heuristic measures across instances and optionally interleaving local search with neural-guided perturbation.Its schematic adds heuristic learning, learned-measure generation at inference, and optional local-search integration.

4 Methodology

DeepACO parameterizes ACO heuristic measures with a neural learner, combines them with local search and pheromone-guided construction, and adds designs that improve exploration.

  • 4.1 Parameterizing heuristic space: DeepACO learns instance-dependent heuristic measures with a GNN-based learner, replacing fixed expert-designed measures while guiding ACO solution construction.The learner maps each COP instance to non-negative measures for solution components, using a GNN backbone and MLP decoder.
  • 4.2 Local search interleaved with neural-guided perturbation: NLS alternates local-search refinement with neural-guided perturbation toward solutions having higher cumulative heuristic measures.It repeatedly refines a solution to a local optimum, perturbs it using the learned measures, and applies local search again before retaining the better solution.
  • 4.3 Training heuristic learner: The training objective jointly evaluates constructed solutions and NLS-refined solutions, balancing both terms with coefficient W.The first term favors directly constructing good solutions, while the second favors constructions that are effective for NLS; NLS itself is not differentiated.
  • 4.4 Extended designs: Three extensions preserve exploration by diversifying heuristic measures, restricting entropy regularization to top-k components, or imitating expert heuristics.Multihead DeepACO uses multiple decoders and ant groups, top-k entropy promotes uniformity among the largest heuristic measures, and imitation can regularize learning.

5 Experimentation

Across eight COPs, DeepACO consistently improves fundamental and advanced ACO variants, remains robust across pheromone models, hyperparameters, scales, and distributions, and compares competitively with routing-focused NCO methods.

  • DeepACO for fundamental ACO algorithms: DeepACO consistently outperforms its ACO counterparts across eight COPs, demonstrating broad neural enhancement of fundamental ACO algorithms.The evaluation covers routing, assignment, scheduling, and subset problems, with results averaged over 100 held-out instances for each benchmark COP.
  • DeepACO for advanced ACO algorithms: DeepACO shows clearly better performance than AEAS using learned rather than original heuristic measures, extending enhancement to an advanced ACO algorithm.The comparison uses Adaptive Elitist Ant System, a recent ACO algorithm with problem-specific adaptations.
  • DeepACO for different pheromone models: DeepACO using PHitems still outperforms ACO on MKP, indicating that its neural enhancement can extend across pheromone-model variations with aligned neural architectures.The PHitems implementation uses a Transformer encoder with an MLP decoder.
  • DeepACO for better robustness to hyperparameter choice: DeepACO is more robust to Alpha and Decay choices on TSP100, showing much lower color variance than ACO across the evaluated hyperparameter settings.The comparison evaluates best objective values within 4K evaluations.
  • DeepACO for real-world instances: DeepACO consistently outperforms ACO on 49 TSPLIB instances while generalizing across node-count scales and distributions.Models trained on TSP20, TSP100, and TSP500 are applied to different instance-size ranges below 1K nodes.
  • Comparison on routing problems: On TSP, DeepACO is competitive with state-of-the-art NCO methods while remaining a general-purpose method evaluated across eight COPs.Ablations further support neural-guided perturbation and training with local search as effective design components.

6 Conclusion and limitation

DeepACO provides neural enhancement for ACO and reports stronger performance than ACO counterparts while matching specialized NCO methods. Its learned heuristic representation is limited by compression into an n × n matrix, especially without local search.

  • 6 Conclusion and limitation: DeepACO provides universal neural enhancement for ACO algorithms and automates heuristic design for future applications.
  • 6 Conclusion and limitation: DeepACO consistently outperforms its ACO counterparts and is on par with specialized NCO methods.
  • 6 Conclusion and limitation: Compressing learned heuristic information into an n × n matrix can limit solution quality when local-search components are absent.

A Neural architecture

DeepACO uses neural architectures aligned with pheromone models to learn heuristic measures and guide ACO search. Its implementations include GNN- and Transformer-based components, plus neural-guided perturbation using local search.

  • A Neural architecture: The PHsuc architecture uses a 12-layer GNN with anisotropic message passing, edge gating, and an MLP decoder for normalized heuristic measures.
  • A Neural architecture: For PHitems, a positional-encoding-free Transformer encoder and feedforward layers map solution-component representations to heuristic measures.
  • A Neural architecture: Neural-guided perturbation reuses learned heuristic measures to perturb locally optimal solutions and can work with arbitrary local-search operators.
  • A Neural architecture: With TSP 2-opt, NLS alternates between minimizing tour length and maximizing the heuristic measures of solution edges.

C.1 DeepACO for more COP scales

Across larger COP scales, DeepACO maintains consistent neural enhancement and competitive routing performance. The evaluation uses evolution curves and expanded TSP and CVRP comparisons, with CVRP NLS based on HGS-CVRP local search.

  • C.1 DeepACO for more COP scales: DeepACO provides consistent neural enhancement across COP scales in evolution-curve evaluations.
  • C.1 DeepACO for more COP scales: Comparative experiments cover TSP100, CVRP100, CVRP400, CVRP1000, and CVRP2000 and demonstrate consistent, competitive performance.
  • C.1 DeepACO for more COP scales: For CVRP, NLS uses the HGS-CVRP local-search strategy, while infeasible solutions produced by that strategy are discarded.

C.3 Generalizability of DeepACO

DeepACO generalizes across diverse COP families and scales because ACO supports broad solution representations and neural enhancement. It remains stronger than ACO under a substantial TSP distribution shift.

  • C.3 Generalizability of DeepACO: DeepACO is evaluated across eight COPs spanning routing, assignment, scheduling, and subset problems, with further extension to bin packing.
  • C.3 Generalizability of DeepACO: Table 5 reports consistent neural enhancement for DeepACO on the Bin Packing Problem.
  • C.3 Generalizability of DeepACO: DeepACO trained on TSP100 still outperforms ACO on TSP1000 despite a significant distributional shift.

C.4 Training duration

DeepACO requires only minutes of training while providing neural enhancement to ACO. Its training combines efficient sampling strategies, and its learned heuristics can differ substantially from manually designed measures.

  • C.4 Training duration: Minutes of training provide substantial neural enhancement for DeepACO.The training settings are summarized in Table 7.
  • C.4 Training duration: Heatmap-based on-policy sampling avoids costly step-by-step neural decoding during training.
  • C.4 Training duration: Parallel multi-start sampling leverages solution symmetries to improve training efficiency.
  • C.4 Training duration: DeepACO can accommodate alternative pheromone models when the neural architecture is aligned with the modeled relationships.The work uses successive-item pheromones generally and presents item-level pheromones as an alternative for MKP.
  • C.4 Training duration: Learned TSP heuristics do not necessarily match manually designed heuristics and are more aggressive, assigning near-zero normalized measures to most solution components.

D Benchmark problems

The benchmark covers routing, ordering, scheduling, resource-constrained scheduling, and knapsack problems. Each problem is represented with graph-based inputs and problem-specific features, constraints, and baseline heuristics.

  • Routing and selection: The benchmark spans TSP, CVRP, OP, PCTSP, SOP, SMTWTP, RCPSP, and MKP.
  • Routing benchmarks: The routing objectives include minimizing tour or fleet distance, maximizing collected prize, and balancing tour length, penalties, and minimum prize.
  • Routing benchmarks: Routing benchmarks model instances as complete or sparsified graphs using coordinates, demands, prizes, penalties, and relative distances.TSP and CVRP use nearest-neighbor sparsification, while OP and the other routing problems specify their own graph inputs.
  • Scheduling benchmarks: SOP represents jobs and feasible precedence-respecting transitions in a directed graph, with processing and waiting times as node and edge features.
  • Scheduling benchmarks: SMTWTP represents jobs in a directed complete graph using normalized due dates, weights, and processing-time edge attributes, minimizing weighted tardiness.
  • Scheduling benchmarks: RCPSP uses PSPLIB instances and an extended constraint graph, while ants construct solutions in topological order with GRPWA and WRUP as baseline heuristics.
  • Knapsack benchmark: MKP selects value-maximizing items under multiple weight constraints, extending the single-constraint knapsack formulation.
Loading 2309.14032v2…