Ant Colony Optimization metaheuristic in SAS Optimization

Authors: Subbu Pazhani and Rob Pratt

In a recent post, we demonstrated how Simulated Annealing (SA) can be used to solve the Traveling Salesman Problem (TSP) by using SAS Optimization. In this post, we extend that discussion by exploring how the Ant Colony Optimization (ACO) metaheuristic can be applied to the same problem by using SAS Optimization. We will showcase its ability to deliver competitive solutions for challenging combinatorial problems.

Solving large-scale, real-world optimization problems using traditional optimization algorithms is often challenging due to complex business constraints and dynamic environments. Metaheuristic algorithms often complement classical optimization techniques to overcome these limitations. Metaheuristics offer a flexible approach to exploring vast solution spaces, identifying promising regions, and generating high-quality initial solutions within practical computational limits. Traditional methods can further fine-tune these solutions to improve accuracy and performance.

Ant Colony Optimization (ACO)

One widely used metaheuristic is Ant Colony Optimization (ACO). This is a bio-inspired, population-based heuristic framework motivated by the foraging behavior of real ant colonies. In nature, ants collectively discover short paths between their nest and food sources by depositing pheromones along traveled routes. Over time, frequently used paths accumulate stronger pheromone trails. This reinforces good solutions through positive feedback. In the optimization context, artificial ants iteratively construct solutions by probabilistically selecting a solution based on:

1. Pheromone intensity, representing learned experience
2. Heuristic information, representing problem-specific knowledge (for TSP, inverse distance)

ACO has proven effective in tackling various combinatorial optimization problems, including routing, scheduling, and network design. ACO operates by simulating a colony of artificial ants that iteratively construct solutions. The algorithm balances exploration and exploitation: ants probabilistically choose paths influenced by pheromone intensity and problem-specific heuristics information. This balance enables ACO to efficiently navigate large combinatorial search spaces and avoid premature convergence to poor local optima. Over time, pheromone updates reinforce high-quality solutions, guiding the search toward near-optimal regions.

A key strength of ACO lies in its adaptability and robustness in handling large, complex search spaces. By leveraging collective learning and positive feedback, ACO can efficiently escape local optima and converge toward high-quality solutions.

Pseudocode of the algorithm

The pseudocode in this section summarizes the main logic of the ACO algorithm before translating it into PROC OPTMODEL code. Each iteration enables multiple artificial ants to construct feasible tours by using pheromone and heuristic information, identifies the best tour, updates pheromone levels to reinforce promising edges, and checks the stopping criteria. This outline provides context for the variables and equations used in the implementation.

• \(\alpha\): Influence of pheromone trails
• \(\beta\): Influence of heuristic information (inverse distance)
• \(\rho\): Pheromone evaporation rate
• (i, j): the directed edge (arc) from node i to node j.
• distance (i, j): travel distance of edge (i,,j)
• \(\tau_{ij}\): Pheromone level or pheromone trails on edge (i, j)
• \(\eta_{ij}\): Heuristic desirability or heuristic information of edge (i, j), often set as 1 / distance (i, j))
• iter: Iteration number
• k: ant identifier
• best_ant: best ant in an iteration
• obj_step(iter,k): objective of that ACO iteration iter for ant k
• arc_selection_probability (i, j) = \((\tau_{ij})^\alpha \times (\eta_{ij})^\beta\), is the attraction score for edge (i, j)
• \(\Delta\tau_{ij}\): pheromone contribution by best_ant in each iteration on edge (i, j)
• \(\tau_\min\), \(\tau_\max\): lower/upper bounds on pheromone levels
• Q: a constant (pheromone quantity)
• best_obj: best upper bound
• best_iter: iteration identifier corresponding to the best upper bound
• aco_cons_obj_count: number of iterations with the same best upper bound
• max_cons_obj: maximum allowable consecutive solutions
• ANTS: Number of ants per iteration
• ITERATIONS: Maximum number of iterations

Initialization step

• \(\tau_{ij}\): constant for all edges (1)
• Set best_obj to a large value
• Initialize random number generator

Iterations:

Input data

To illustrate the ACO algorithm and its usefulness, we consider an example from the Traveling Salesman Tour of US Capital Cities. This problem seeks the shortest route that visits the capital city of every U.S. state (and the District of Columbia), excluding Alaska and Hawaii.

PROC OPTMODEL code

The model is coded and solved by using the OPTMODEL procedure in SAS Optimization. We start by defining the index sets and parameters for the TSP problem, then use a READ DATA statement to read data into them.

   proc optmodel;
 
      /* Declare parameters and read data */
      set  NODEPAIRS;
      set  NODES = union { in NODEPAIRS} {i,j};
      set  NODES_TMP;
      num distance{NODEPAIRS};
      num node_id{NODES};
      num id init 1;
      read data CitiesDist (where=(upcase(city1) ne upcase(city2)))
         into NODEPAIRS=[city1 city2] distance;
      set  NUM_NODES = 1..CARD(NODES);
      for {n in NODES} do;
         node_id[n] = id;
         id = id + 1;
      end;

The next line calls a macro named aco_tsp_dec, which defines index sets and variables needed for the ACO algorithm:

Followed by:

     %macro aco_tsp_dec(
     );
 
          /* Ant Colony optimization - index sets and variables */
          num alpha = 2.0;
          num beta = 7.5;
          num rho = 0.3;
          num max_ants = 20;
          num max_steps = 1000;
          set  ITERATIONS = 1..max_steps;
          set  ANTS = 1..max_ants;
          num init_pheromone_trail = 1;
          num pheromone_trail{NODEPAIRS} init init_pheromone_trail; /* Initialize the pheromone trail */
          num heuristic_info{ in NODEPAIRS} = 1/distance[i,j];
          num Q = 1000;
          num best_ant init 0;
          num best_iter init 0;
          num best_obj init 100000;
          num probabilities{NODEPAIRS};
          num temp_cum_prob;
          num min_pher = 0.001;
          num max_pher = 20;
          num aco_starttime;
          num aco_endtime;
          num aco_runtime init 0;
          num obj_step{ITERATIONS, ANTS};
          str aco_tsp_tour{ITERATIONS, NUM_NODES, ANTS};
          num best_obj_step{ITERATIONS};
          num node_total_probability;
          set  TSPEDGES init {};
          num next_i{i in NUM_NODES} = if i < card(NUM_NODES) then i+1 else 1;
          num rand_num;
          num delta_pheromone;
          str next_node;
          num aco_cons_obj_count init 0;
          num prev_best_obj;
          num dec_roundoff = 0.1;
          num max_cons_obj = 20;
          call streaminit(100);
 
     %mend aco_tsp_dec;

The following statements implement the main ACO loop, iterating over ACO iterations and, within each iteration, over all ants. The aco_ant_behavior macro is the core of the algorithm: each ant builds a complete tour by repeatedly selecting the next edge probabilistically using the attraction score arc_selection_probability(i,j) (as defined in the pseudocode). Each ant starts at node_id=1 and constructs a tour until all cities are visited. This behavior mimics how real ants lay down and follow pheromone trails. The objective value of each ant’s constructed tour is evaluated by using the aco_compute_obj macro. Finally, the tour objective value is compared with the incumbent best solution. The best objective (best_obj), best iteration (best_iter), and best ant (best_ant) variables are updated whenever an improved solution is found.

     aco_starttime = time();
 
     /* ACO iterations */
     for{iter in ITERATIONS} do;
        prev_best_obj = best_obj;
        for {k in ANTS} do;
           /* Construct paths for ants */
           %aco_ant_behavior();
 
           /* Evaluating objective function value */
           %aco_compute_obj();
 
           /* Updating best objective and best iteration variables
              - across all K ants */
           if (obj_step[iter,k] < best_obj) then do;
              best_obj = obj_step[iter,k];
              best_iter = iter;
              best_ant = k;
           end;
        end;
     end;

     %macro aco_ant_behavior();
 
     /* Compute raw attraction scores once per ant tour */
     for { in NODEPAIRS}
        probabilities[i,j] = (pheromone_trail[i,j]**alpha) * (heuristic_info[i,j]**beta);
 
     NODES_TMP = NODES;
     for {n in NODES: node_id[n] = 1} do;
        aco_tsp_tour[iter, 1, k] = n;
        NODES_TMP = NODES_TMP diff {n};
     end;
 
     id = 1;
     do while (CARD(NODES_TMP) >= 1);
 
          /* Compute total probability */
          node_total_probability = sum{n1 in NODES_TMP}
             probabilities[aco_tsp_tour[iter, id, k], n1];
 
          /* Scale rand_num - Avoiding normalizing the probabilities array */
          rand_num = rand('UNIFORM') * node_total_probability;
          temp_cum_prob = 0;
          next_node = '';
 
          /* Running sum to pick next node */
          for {n1 in NODES_TMP} do;
             temp_cum_prob = temp_cum_prob
                + probabilities[aco_tsp_tour[iter, id, k], n1];
             if rand_num <= temp_cum_prob then do;
                next_node = n1;
                leave;
             end;
          end;
 
          id = id + 1;
          aco_tsp_tour[iter, id, k] = next_node;
          NODES_TMP = NODES_TMP diff {next_node};
     end;
 
     %mend aco_ant_behavior;

     %macro aco_compute_obj(
     );
 
     obj_step[iter,k] = sum{i in NUM_NODES} distance[aco_tsp_tour[iter, i,k],aco_tsp_tour[iter,next_i[i],k]];
 
     %mend aco_compute_obj;

The following statements update the pheromone levels on all edges by first applying evaporation and then depositing pheromone in proportion to the contribution of the best_ant (in each iteration) on the visited edges.

          /* Updating pheromone values - across all K ants */
          %aco_ant_pheromone();

     %macro aco_ant_pheromone (
     );
          /* Evaporation of current pheromone trail values on the edges */
          for { in NODEPAIRS} pheromone_trail[i,j] = ((1-rho)*pheromone_trail[i,j]);
 
          TSPEDGES = union{i in NUM_NODES} {[iter,i,best_ant],aco_tsp_tour[iter,next_i[i],best_ant]>};
 
          for { in NODEPAIRS} do;
             if  in TSPEDGES then delta_pheromone = Q/obj_step[iter,best_ant];
             else delta_pheromone = 0;
             pheromone_trail[i,j] = pheromone_trail[i,j] + delta_pheromone;
             pheromone_trail[i,j] = min(max_pher,max(min_pher,pheromone_trail[i,j]));
          end;
 
     %mend aco_ant_pheromone;

During the pheromone update, edges in higher-quality tours receive larger pheromone deposits. Consider an edge (i,j) with current pheromone level \(\tau_{ij} = 0.40\), evaporation rate \(\rho = 0.10\), and bounds \(\tau_\min = 0.10\), and \(\tau_\max = 1.00\), with \(Q = 1\). Suppose two ants produce objective values of 250 and 200. Because the objective function is minimized, the ant with a value of 200 becomes the best_ant. The pheromone deposit is \(\Delta\tau_{ij} = 1/200 = 0.005\). Compared to the other ant with the objective value of 250 (which would deposit 1/250 = 0.004), the best_ant deposits a larger amount of pheromone. As a result, edges belonging to the better tour (objective 200) receive stronger reinforcement and become more attractive in future iterations.

The algorithm then computes the number of consecutive iterations during which the incumbent best solution remains unchanged, compares this count with the maximum allowable threshold, and either resets the pheromone levels on all edges to their initial values or updates the counter tracking consecutive best solutions.

     /* Computing number of consecutive same best solution */
     if abs(best_obj - prev_best_obj) <= dec_roundoff then do;
        aco_cons_obj_count = aco_cons_obj_count + 1;
     end;
     else aco_cons_obj_count = 0;
     if aco_cons_obj_count > max_cons_obj then do;
        for { in NODEPAIRS} pheromone_trail[i,j] = init_pheromone_trail;
     end;
 
     /* Reporting variables */
     best_obj_step[iter] = best_obj;
     put iter= best_obj= best_iter= best_ant= aco_cons_obj_count=;
 
     end;

The following statement extracts and outputs the best solution generated by the ACO algorithm:

     /* Run time of the ACO algorithm */
     aco_endtime = time();
     aco_runtime = intck('second',aco_starttime,aco_endtime );
     put aco_runtime=;
 
     /* Creating output table */
     TSPEDGES = union{i in NUM_NODES} {[best_iter, i,best_ant],aco_tsp_tour[best_iter,next_i[i],best_ant]>};
     create data TSPTourLinks from [city1 city2]=TSPEDGES distance;
     create data TSPACOIterations from [Iteration_no]=ITERATIONS best_obj_step;
 
quit;

We execute the ACO algorithm coded within PROC OPTMODEL using the input data. The optimal objective value of the problem is 10,635.09. The algorithm began with a solution with an objective function value of 12,657.15 and terminated with one of 10,977.56 (a gap of 3.22% from the optimal objective value). The algorithm took 143 seconds to run 1000 iterations with 20 ants per iteration. Snapshots of the iterations with starting solutions (first 20 iterations) and the final solution (last 20 iterations), from the TSPACOIterations table, are shown in Tables 1 and 2.

Table 1: Solutions of the ACO algorithm from the first 20 iterations

Table 2: Solutions of the ACO algorithm from the last 20 iterations

The performance and quality of solutions produced by the ACO algorithm are strongly influenced by the choice of runtime parameters, such as the influence of pheromone trails, the influence of heuristic information, the pheromone evaporation rate, the number of iterations, the number of ants per iteration, and the pheromone update rule. Extensive and careful tuning of these parameters enhances the robustness of the search process, leading to improved solution quality, greater diversity, and more effective exploration of complex optimization landscapes. Equally important is the solution construction mechanism in ACO: designing procedures that construct feasible solutions is a requirement for the algorithm, and a fundamental requirement for metaheuristic approaches in general.

Plots of solutions

The statements for producing a graphical display of the solution can be referred to in the example of the Traveling Salesman Tour of US Capital Cities. The early-stage ACO solution (iteration 1) produces scattered, inefficient routes with many unnecessary crossings and detours, as shown in Figure 1. Figure 2 shows the converged ACO solution (iteration 500), where the algorithm generates better-structured, geographically coherent routes that demonstrate improved optimization.

Figures 3 and 4 show the optimal solution and the best-cost tour of the capital cities obtained by the ACO algorithm. The best-cost ACO solution (Figure 4) represents a well-organized, near-optimal tour that efficiently connects all cities with minimal crossings and a reduced total travel distance.

In the northwest region (shown in Figures 5 and 6), the ACO solution matches the optimal route, capturing the same optimal tour in this part of the network.

We also observe differences in routes between the optimal solution and the best solution from the ACO algorithm, reflecting the heuristic nature of the search. Figures 7 and 8 present the optimal tour and the best ACO solution for the Northeast region. The ACO solution shows small local crossings and route overlaps in dense regions, reflecting inefficiencies in the search process. This highlights the importance of careful parameter tuning to enhance convergence and solution quality in ACO.

The following statements generate plots of the iterations and the progress of the best objective value.

     /* Progress of best objective */
     title 'Iterations vs best objective value';
     %let optimal = 10635;
     proc sgplot data=TSPACOIterations noautolegend;
        step x=Iteration_no y=best_obj_step / markers;
        refline &optimal.;
        xaxis label='Iteration';
        yaxis label='Objective Value' min=10500;
     run;

Figure 9 shows the plot of the best objective value found as a function of the number of iterations. The overall downward trend reflects the algorithm’s effectiveness in navigating the solution landscape towards near-optimality. Figure 9 also highlights the exploration–exploitation trade-off: rapid early gains from exploration, followed by slower convergence as the algorithm intensifies the search near high-quality solutions.

Conclusion

This post demonstrates how to implement an ACO metaheuristic algorithm in PROC OPTMODEL. It applies it to a TSP instance from the SAS documentation. The results illustrate the characteristic ACO search dynamics: solution construction guided by pheromone and heuristic information, progressive reinforcement of high-quality edges through pheromone updates, and gradual improvement in the best objective value over the course of the iterations.
Metaheuristics such as ACO are often most effective when used alongside exact or specialized algorithms. The ACO algorithm provides only an approximate solution to the problem, not a globally optimal one. However, it could be useful for obtaining a good, feasible solution to a wide variety of complex, real-world problems, serving as a warm start within a unified optimization workflow. Other applications of ACO include vehicle routing problems and extensions, multicommodity network design, and scheduling problems.

To explore further, SAS Optimization has specialized solvers for various graph theory, combinatorial optimization, and network analysis algorithms, including TSP.