Ant Colony Optimisation

The following is a article adaptation of a research project I did on Ant Colony Optimisation.

1. Introduction

The Travelling Salesman Problem (TSP) is an NP-hard combinatorial optimisation problem aimed at finding the minimum-cost Hamiltonian circuit¹ for some weighted graph.

TSP is ubiquitous across various domains and fields, such as network performance, package delivery routing, water resource management, and beyond [1].

Within this article, we are considering the classic formulation of this problem, where each node represents a city and edge weights represent the distances between them. This setup allows us to pose the problem statement simply and clearly:

Given a list of cities and the distances between each pair, what is the shortest possible route that visits every city exactly once and returns to the origin city?

As this problem is NP-hard, the complexity of finding an optimal solution to TSP is computationally intractable for large graph sizes. A theoretically close-to-optimal method is the Bellman-Held-Karp algorithm, which is still exponential in runtime with Big-O of $\mathrm{𝒪︀}\left({𝑛}^2{2}^{𝑛}\right)$ [2].

As such, approximation algorithms are generally used in practice to generate best-effort solutions to TSP. One such class of algorithms are “Ant Colony Optimisation” (ACO) algorithms, from which the model for this article is sourced.

The term “Ant Colony Optimisation” describes the metaheuristic of simulating ants to optimise paths in some search space. The Ant Colony Model (ACM) used in ACO is a bio-inspired stochastic algorithm, modelled on the real-life foraging behaviours of ants in an ant colony.

Real life ants have limited visual perceptive faculties, and some species are completely blind [3]. In order to coordinate, they lay trail pheromone on the ground they walk. The path that an ant takes is random, with preference for paths marked by strong pheromone concentrations. When introduced to a new environment, ants will explore the search space randomly, and over time converge to a more efficient network by positively reinforcing shorter paths. The search procedure for ants is an autocatalytic process where the shortest routes are reinforced by the fact that pheromones have less time to dissipate when they are travelled quicker.

ACMs take inspiration from this. For a given graph, the general procedure starts with simulating a population of artificial ants that each construct a solution by randomly moving from node to node, biasing their choices toward edges with higher pheromone concentrations and favorable heuristic metrics. Once the ants complete their tours, the virtual pheromone levels are updated. By letting the shortest routes found by the ants have the greatest effect on the pheromone trails, subsequent generations are guided toward more optimal paths. The next iteration of ants will be more likely to select better paths, and will then influence the next iteration of ants after that with their own findings. The result is a dynamic system that converges to probabilistically better distributions of solutions every iteration. The next section will expand on the mechanics of this.

The base model for this analysis will be the original “Ant-Cycle” (AC) algorithm (commonly referred to as the Ant System), introduced by Marco Dorigo in 1992 [4]. To address the base model’s susceptibility to stagnation, the proposed extension divides the simulated ant population into two distinct classes of ant. “Explorers” will operate with a high tendency towards greedily selecting the shortest local paths, relying heavily on distance heuristics rather than existing pheromone trails. Conversely, “Foragers” will exhibit a stronger bias towards exploiting established pheromone trails to positively reinforce known efficient routes. This heterogeneous approach aims to balance broad search space exploration with the rapid exploitation of optimal paths, directly mitigating the risk of premature convergence.

Ultimately, this article seeks to utilise the stochastic computational simulation of ant colonies to generate near-optimal solutions for the TSP, whilst conducting rigorous empirical and theoretical analyses to evaluate the model’s vulnerability to local optima. This investigation begins with a Markov chain-based analytical model of a restricted state space to calculate the exact theoretical probability of suboptimality, then extrapolate this to full-sized problems as a trend. These analytical derivations are validated against numerical results obtained via Monte Carlo simulations. Finally, the heterogeneous heuristic extension is introduced, evaluated, and directly compared against the baseline model to demonstrate its impact on convergence rates and final solution optimality.

2. Ant Colony Model

2.1. Model Details

Building upon the search process outlined in the Introduction, candidate solutions are constructed in each iteration. As a simulated ant traverses the graph, its routing decisions are stochastic; at any given node, the ant selects its next destination by sampling a discrete probability distribution weighted by both historical trail data and local heuristics.To formally define the transition probability for an ant positioned at node $𝑖$, we introduce the following notation:

• Let ${𝜏}_{𝑖𝑗}$ represent the current pheromone concentration on the edge $\left(𝑖,𝑗\right)$, and $𝑇$ be the matrix of these pheromones.
• Let ${𝑑}_{𝑖𝑗}$ denote the distance of traversing an edge from $𝑖\to 𝑗$.
• Let $𝑈$ be the set of valid, unvisited candidate nodes remaining in the ant’s current tour.

Figure 1 depicts an ant at some node ${𝐾}_{𝑖}$ with three nodes left to visit in its trail ($𝑈=\left\{{𝐾}_1,{𝐾}_2,{𝐾}_3\right\}$).

When constructing the probability distribution for the ant to sample from, we want to make its choice biased towards stronger pheromones but also a heuristic value to guide convergence. Thus we must introduce a heuristic factor, ${𝜂}_{𝑖𝑗}$, that nudges the probability function in the right direction where the search space has not been adequately explored. Hence, the probability that an ant selects a given path is given by

Where ${𝜂}_{𝑖𝑗}=\frac{1}{{𝑑}_{𝑖𝑗}}$. By making ${𝑃}_{𝑖𝑗}\propto {𝜏}_{𝑖𝑗}\frac{1}{{𝑑}_{𝑖𝑗}}$, we both bias ants toward stronger pheromone values, and shorter distances. In Figure 1, the ant is most likely to choose ${𝐾}_4$, as

1. The distance is the shortest of the available options.
2. The relatively high pheromone concentration indicates that previous generations of ants were successful when choosing that edge.

So far, however, we have no control over the relative effects of ${𝜏}_{𝑖𝑗}$ and ${𝜂}_{𝑖𝑗}$. To this end, we introduce two model parameters $𝛼,𝛽\ge 0$, which act as exponents to modulate the relative influence of historical trail pheromone density versus locality. Incorporating these tuning parameters yields:

In a given iteration of this algorithm, many² ants are simulated, each beginning at randomly uniformly sampled starting nodes.

Once all ants have been simulated and have each provided a candidate path, ${𝑉}_{𝑘}$, with total distance ${𝐿}_{𝑘}$, the pheromone matrix, $𝑇$, must be updated to encode the relative success of these traversals. This global update phase consists of two processes: pheromone evaporation and pheromone deposition.

First, to bound the pheromone accumulation and to allow the simulated colony to gradually “forget” sub-optimal paths, all edges in the graph undergo a uniform evaporation process. We introduce an evaporation rate parameter $𝜌\in \left(0,1\right]$, which dictates the fraction of pheromone that dissipates per iteration:

Following evaporation, the system simulates the ants depositing new pheromones. Each ant $𝑘$ deposits a quantity of pheromone exclusively on the edges belonging to its constructed tour, ${𝑉}_{𝑘}$. The volume of pheromone deposited is inversely proportional to the total distance ${𝐿}_{𝑘}$ of the tour, scaled by a constant $𝑄$. This mechanism ensures that shorter, more optimal paths receive stronger reinforcement. The specific pheromone contribution $\mathrm{\Delta }{𝜏}_{𝑖𝑗}^{𝑘}$ added by ant $𝑘$ to edge $\left(𝑖,𝑗\right)$ is defined as:

Consequently, the complete global pheromone update rule applied to every edge $\left(𝑖,𝑗\right)$ at the conclusion of an iteration combines both evaporation and the cumulative deposition from all $𝑚$ ants:

The initial state of the pheromone matrix $𝑇$ must be defined prior to the first iteration. A standard convention is to initialise all transitions to a uniform positive constant (e.g., ${𝜏}_{𝑖𝑗}=1$ for all $𝑖,𝑗$). This uniform distribution ensures that the initial algorithmic search space is entirely exploratory and driven primarily by the heuristic factor ${𝜂}_{𝑖𝑗}$.

The result of this update process is not a guarantee that any single ant will find the optimal traversal in a given iteration, but rather tracking the best traversal found so far is a matter of recording it across iterations as the search progresses. The pheromone update does not directly select for the best path; it simply increases the likelihood that future ants will be guided toward it

2.1.1. Note on Model Parameters

The parameter $𝛼$ controls the intensity of the history-reinforcement mechanism. When $𝛼\gg 1$, subsequent generations strongly exploit the choices of past ants, accelerating pheromone accumulation but severely elevating the risk of premature convergence.

Conversely, the parameter $𝛽$ regulates the influence of the local distance heuristic. A relatively high $𝛽$ value forces the ants to act myopically, favoring immediate short edges even if they ultimately lead into dead ends or expensive long-distance penalties later in the Hamiltonian tour.

Tuning the ratio between $𝛼$ and $𝛽$ balances the choice between global exploration of the graph and local exploitation of known short paths.

2.2. Model Categorisation

The ACM is fundamentally a numerical, rather than analytical, model. Because the algorithm relies on complex, path-dependent interactions, there is no closed-form analytical solution to predict the exact state of the pheromone matrix at an arbitrary iteration.

Consequently, the model is highly non-linear. As an example, the transition probability, ${𝑝}_{𝑖𝑗}$, is a non-linear function of both the accumulated pheromone ${𝜏}_{𝑖𝑗}^{𝛼}$ and the heuristic information ${𝜂}_{𝑖𝑗}^{𝛽}$. Because these terms are raised to the exponents $𝛼$ and $𝛽$, the relative influence of historical reinforcement versus greedy heuristic choices does not scale linearly, creating complex feedback loops as the algorithm progresses.

Structurally, the ACM operates as a discrete-time, continuous-state system. The underlying search space is finite, and the algorithmic timeline advances in discrete steps between iterations. However, the global state of the system (the pheromone matrix) is continuous, with each edge’s pheromone concentration ${𝜏}_{𝑖𝑗}\in {ℝ}^{+}$. While the pheromones exist in a continuous domain, the probability distribution from which ants sample their next node (Equation 2) remains a discrete categorical distribution, albeit one parameterized by continuous variables.

Importantly, the model is inherently stochastic. The primary mechanism for “learning” optimal routes is predicated on probabilistic exploration. Rather than following a deterministic rule, ants make weighted random walks through the graph. This stochasticity ensures a broad exploration of the solution space, allowing the colony to generate diverse candidate paths while exploiting past successes through positive pheromone reinforcement.

2.3. Failure-state Analysis

In order to characterise the propensity this model has to early convergence to sub-optimal states, we conduct an analysis by modelling ACO as a discrete-time Markov chain.

This presents significant challenges in the general case, as the full pheromone matrix $𝑇$ constitutes a continuous, high-dimensional state that grows combinatorially with the number of nodes, making exact analysis impossibly large for realistic problem sizes.

To obtain a manageable analytical model, we introduce a restricted graph topology and a set of simplifying assumptions that preserve the essential dynamics of the ACO metaheuristic while reducing the state space to a controllable size:

• 4-Node Search Space: The graph contains exactly 4 nodes: A, B, C, D.
• Single Origin: All ants are released only from node A at the start of each iteration.
• Forced Routing: We consider only 2 cycles on this graph, and all edges not on either cycle are assigned infinite cost, strictly eliminating them from the ant’s routing consideration.
• Single Ant: One ant is simulated per iteration, isolating the effect of a single pheromone update per step.

Figure 3 shows only two traversable paths,

1. The optimal path (ABCDA) with ${𝐿}_{\text{opt}}=40$.
2. The trap path (ADCBA) with ${𝐿}_{\text{trap}}=100$.

When considering the assumptions, it becomes clear that this graph has been deliberately constructed to deceive the ACO metaheuristic. The optimal path’s first edge (${𝑑}_{\text{AB}}=5$) is longer than the trap path’s (${𝑑}_{\text{AD}}$ = 2). Hence, the local distance heuristic, ${𝜂}_{𝑖𝑗}=\frac{1}{{𝑑}_{𝑖𝑗}}$, will favour the trap.

The causes a contension between the greedy heuristic signal and the emergent, globally optimal reinforcement via the pheromone mechanism.

2.3.1. Markov Chain Construction

The Markov chain constructed for this analysis tracks the evolution of pheromone concentrations over discrete iteration steps. The system state at iteration $𝑡$ can be fully described by two continuous variables:

1. The current pheromone value over the optimal path, ${𝜏}_{\text{opt}}^{𝑡}$.
2. The current pheromone value over the trap path, ${𝜏}_{\text{trap}}^{𝑡}$.

Given these values, the ant at origin node A samples a Bernoulli choice, selecting the optimal path with probability ${𝑝}_{\text{opt}}$:

where the initial heuristic biases are defined as ${𝜂}_{\text{opt}}=\frac{1}{{𝑑}_{\text{AB}}}$ and ${𝜂}_{\text{trap}}=\frac{1}{{𝑑}_{\text{AD}}}$.

Following the global update rule, the pheromone state transitions deterministically once the ant’s path is sampled:

Because these transition probabilities and subsequent updates depend solely on the current pheromone state, $\left({𝜏}_{\text{opt}}^{\left(𝑡\right)},{𝜏}_{\text{trap}}^{\left(𝑡\right)}\right)$, and not on prior routing history, the sequence satisfies the markov property. Consequently, the algorithmic behaviour can be entirely evaluated through the transition matrices of this defined state space.

2.3.2. Absorbing States

To evaluate the algorithm’s vulnerability to the deceptive topology, we define three mutually exclusive absorbing states. These states classify the exact outcome of the system after a finite horizon of $𝑚$ iterations:

• ${𝐴}_1$ (Success): The optimal path has become overwhelmingly dominant. This is achieved when the pheromone concentration ratio satisfies $\frac{{𝜏}_{\text{opt}}}{{𝜏}_{\text{opt}}+{𝜏}_{\text{trap}}}\ge {\mathrm{\Theta }}_{\text{opt}}$.
• ${𝐴}_2$ (Stagnation): The system is trapped in the local optimum. This occurs when the trap path dominates, defined by the ratio $\frac{{𝜏}_{\text{opt}}}{{𝜏}_{\text{opt}}+{𝜏}_{\text{trap}}}\le {\mathrm{\Theta }}_{\text{trap}}$.
• ${𝐴}_3$ (Limited Convergence): The system fails to converge decisively on either path within the $𝑚$-iteration horizon, meaning the ratio remains strictly between the two thresholds.

The threshold parameters ${\mathrm{\Theta }}_{\text{opt}}$ and ${\mathrm{\Theta }}_{\text{trap}}$ are analytical modelling choices that define a “decisive” algorithmic convergence. Aligning with the empirical simulations, we set ${\mathrm{\Theta }}_{\text{opt}}=0.80$ and ${\mathrm{\Theta }}_{\text{trap}}=0.20$.

2.3.3. State Space Expansion and Absorption Probabilities

Because the pheromone updates are deterministic given the ant’s binary routing decision, the evolution of the system over $𝑚$ iterations can be mapped as a binary decision tree of depth $𝑚$. Each node represents a unique transient pheromone state, and its two children represent the subsequent states following an optimal or trap path choice. The probability of reaching any specific leaf is the product of the Bernoulli transition probabilities (${𝑝}_{\text{opt}}$, $1-{𝑝}_{\text{opt}}$) along its path.

To rigorously compute the exact probabilities of reaching ${𝐴}_1$, ${𝐴}_2$, or ${𝐴}_3$, we cast this state-space tree into the canonical form of an absorbing discrete-time Markov chain. Let the $𝑛$ internal nodes of the tree represent the transient states, indexed $1,\dots ,𝑛$, with the three terminal absorbing states appended. The complete transition matrix $𝑃$ is structured as:

where $𝑄\in {ℝ}^{𝑛\times 𝑛}$ contains the transition probabilities between transient states, $𝑅\in {ℝ}^{𝑛\times 3}$ contains the probabilities of transitioning from a transient state directly into one of the three absorbing states, $\mathrm{𝟎}$ is a zero matrix, and $𝐼$ is the $3\times 3$ identity matrix.

From this canonical form, we compute the fundamental matrix, $𝑁$:

The entry ${𝑁}_{𝑖𝑗}$ represents the expected number of times the chain visits transient state $𝑗$ before absorption, given it started in transient state $𝑖$. Finally, the exact matrix of absorption probabilities, $𝐵$, is calculated as:

Here, ${𝐵}_{𝑖𝑘}$ yields the probability that the system will eventually be absorbed into state ${𝐴}_{𝑘}$ when originating from transient state $𝑖$. Consequently, the first row of this matrix provides the theoretical probabilities of Success, Stagnation, and Limited Convergence from the initial, unweighted root state $\left({𝜏}_{\text{opt}}=1,{𝜏}_{\text{trap}}=1\right)$.

Results from this will be discussed with respect to Monte Carlo simulations of a simplified version of the AC algorithm, modified to satisfy the simplifying assumptions and restraints introduced for the markov analysis.

2.4. Double Ant Colony Extension

The proposed extension to the base model introduces a heterogeneous population structure. The standard ACO model is inherently limited by the homogeneity of ant decisions; governed by a single set of global parameters ($𝛼$, $𝛽$), the entire colony risks being either too greedy (leading to premature stagnation in local optima) or not exploitative enough (resulting in slow convergence).

To resolve this, we introduce the Double Ant Colony extension. For every iteration, we simulate two distinct ant phenotypes:

1. Explorers: Configured with high $𝛽$ and low $𝛼$. These ants rely heavily on the local distance heuristic ($𝜂$) and largely ignore existing pheromone trails.
2. Foragers: Configured with low $𝛽$ and high $𝛼$. These ants are highly sensitive to pheromone concentrations ($𝜏$) and largely ignore local distance penalties.

The dual-population setup decouples the exploration-exploitation dilemma. Explorers act as pathfinders, greedily seeking out locally efficient edges that may have been overlooked. Conversely, Foragers act as optimisers; they exploit the known, established paths to reinforce and maintain the global trail. Together, they allow the algorithm to continuously search for novel solutions while simultaneously refining the best-known routes.

2.5. Assumptions

2.5.1. Original Model

• All ants utilize identical, static weighting parameters ($𝛼,𝛽$) throughout the entire execution.
• The search space is represented as a connected graph where ants perform a stochastically biased random walk, capable of traversing from any node to any connected neighbor.
• The assumption that ants tending towards locally shorter paths (via the distance heuristic $𝜂=\frac{1}{𝑑}$) will ultimately construct a globally optimal path. As demonstrated by our restrained graph analysis, this assumption is vulnerable to deceptive topologies.

2.5.2. Double Ant Colony Extension

• We relax the assumption of homogeneous ant tendencies. The assumption in the base model is that all ants will act the exact same; the extension assumes that a structural division of labor yields a mathematically more robust search process.
• We assume that the problem topology contains deceptive local optima (traps) that require forced, heuristic-driven exploration to escape, which standard homogenous ants fail to do.

3. Algorithms

• Ant-Cycle was implemented in Julia (src/AntSystem.jl). This is the main algorithm, executing the discrete routing, local heuristic evaluation, and global pheormone updates for each of the standard, simplified and extended Ant Colony models.

• A Julia script was written to generate and solve the Markov chain, and compare this against Monte Carlo simulations (project_scripts/markov_v_monte_carlo.jl).

  • Monte Carlo simulations were conducted and the relative frequency of pheromone trails in states ${𝐴}_1,{𝐴}_2,$ and ${𝐴}_3$ were recorded.
  • The analytical chain was generated by algorithmically expanding the full binary decision tree of the ant’s choices up to depth $𝑚$. At each internal node, the exact Bernoulli probability of the ant’s choice was calculated, and the subsequent deterministic pheromone update was applied. The leaves of this tree were then classified into the three absorbing states, allowing us to compute the fundamental matrix and derive the exact theoretical absorption probabilities to validate against the numerical simulations.

4. Results

4.1. Markov Chain Analysis

We utilise the Markov chain composition to characterise the interactions that the model parameters $𝛼$ and $𝛽$ have on the probability of converging to each of the three absorbing states.

4.1.1. Effect of Pheromone Parameter ($𝛼$)

We observe a multi-faceted relationship between the pheromone weighting parameter ($𝛼$) and the algorithmic convergence states in Figure 4.

Initially, a low $𝛼$ induces a high rate of deadlock (No Convergence). Because the ants are effectively ignoring the historical pheromone trails, their routing decisions are primarily driven by the localized distance heuristic ($𝛽=0.2$) and inherent randomness. Consequently, pheromones are distributed relatively evenly across the network. However, the probability of Success (${𝐴}_1$) remains higher than Stagnation (${𝐴}_2$). This is a result of the global update rule: because the optimal path is significantly shorter (${𝐿}_{\text{opt}}=40$) than the trap path (${𝐿}_{\text{trap}}=100$), successful traversals deposit substantially more pheromones per iteration ($\frac{𝑄}{𝐿}$). This provides a baseline statistical bias toward the global optimum, even when the colony’s historical reliance is weak.

As $𝛼$ increases towards 2.0, deadlock sharply decreases while both success and stagnation rates rise. The probability of success scales at a steeper rate before plateauing. This indicates that an active reliance on collective pheromone history is a positive, necessary mechanism for the colony to overcome the deceptive local optima engineered into the search space.

Beyond the optimal threshold, the operational dynamic inverses: the probability of success degrades while stagnation steadily climbs. In this high-$𝛼$ configuration, the exponential parameter heavily skews the probabilistic routing outcomes to the first choice of the system. Because the local distance heuristic favors the initial edge of the trap path (${𝑑}_{\text{AC}}=2.0$ versus ${𝑑}_{\text{AB}}=5.0$), early iterations are highly likely to deposit initial pheromones there. A severe $𝛼$ exponent immediately magnifies this early deposit, prematurely locking the colony into the sub-optimal trap path and rendering it virtually inescapable before the globally optimal path can be fully reinforced.

These results demonstrate that $𝛼$ must be strictly modulated. It serves as a critical regulator to avoid two algorithmic extremes:

1. under-utilizing the colony’s collective memory (resulting in inefficient deadlock) and
2. over-amplifying early exploratory choices (resulting in catastrophic premature convergence).

4.1.2. Effect of Heuristic Sensitivity ($𝛽$)

In contrast to the complex phase transitions observed with the pheromone mechanism, the relationship between the heuristic weighting parameter ($𝛽$) and the convergence states presented in Figure 5 is notably straightforward. We observe a monotonic, near-linear degradation in algorithmic success as $𝛽$ increases. Specifically, the probability of Success (${𝐴}_1$) steadily declines, mirrored by a proportionally inverse rise in Stagnation (${𝐴}_2$). The probability of Deadlock (${𝐴}_3$) remains marginal throughout the parameter sweep, exhibiting only a slight convex inflation, peaking around $𝛽=0.5$.

This strictly inversely proportional relationship is a direct consequence of the intentionally pathological topology of the restrained search space. Recall that the local distance heuristic ($𝜂=\frac{1}{𝑑}$) heavily biases the ant toward the trap path because its initial edge (${𝑑}_{\text{AC}}=2.0$) is significantly shorter than the optimal path’s initial edge (${𝑑}_{\text{AB}}=5.0$). Therefore, increasing the $𝛽$ parameter simply amplifies the algorithm’s inherent susceptibility to this deception. By raising $𝛽$, the metaheuristic is forced to heavily prioritize a greedy, myopic routing strategy that aligns perfectly with the trap.

Consequently, while the $𝛼$ sweep reveals intrinsic behavioral thresholds within the colony’s collective memory, the $𝛽$ sweep primarily serves as a mathematical validation of the experimental design. Rather than exposing hidden emergent properties of the Ant System model, it confirms that the constructed graph functions correctly.

4.1.3. Monte Carlo Accuracy

Figure 6 illustrates the convergence of the empirical Monte Carlo simulations toward the exact analytical limits derived from the Markov chain model. As dictated by the Law of Large Numbers, the Mean Absolute Error (MAE) across all three absorbing states decreases predictably as the sample size grows. When evaluated at ${10}^6$ trials, the empirical simulation tightly aligns with the theoretical model, yielding a marginal error bound of approximately ${10}^{-3}$. This strong convergence directly validates both the operational algorithm implementation and the mathematical integrity of our state-space expansion.

4.2. Metaheuristics

To evaluate the practical impact of the Double Ant Colony extension on a realistic problem instance, both the baseline single-population ACO and the Double ACO extension were run on the a280 TSPLIB benchmark instance (a 280-node Euclidean TSP problem). Both algorithms were run under comparable total ant-population sizes and identical evaporation and deposition parameters, with the Double ACO splitting its population between Explorer and Forager phenotypes as described in the model section.

Figure 7 and Figure 8 show the lengths of the five shortest tours discovered by the colony at each iteration, plotted across $𝑚$ iterations. Both figures exhibit the characteristic ACO convergence pattern: an initially high tour length distribution during early exploration, which quickly narrows and shifts downward as pheromone reinforcement guides the colony toward shorter tours.

It can be seen that the variance of the top-5 tour lengths is significantly higher in the Double ACO plot. This reflects the Explorer population’s continued heuristic-driven search of the graph, which is largely decoupled from the pheromone trail being reinforced by the Foragers. This sustained exploration broadens the pool of candidate tours that the colony draws from, increasing the likelihood that a genuinely shorter tour is discovered before the pheromone trail commits the colony to a particular route.

The Double ACO extension achieves a markedly better best-known tour length than the single-population baseline, with a shortest discovered tour of 2999.0 compared to 3215.0 for the single-population model - an improvement of approximately 6.7%. The dispersion of the top-5 tour lengths is also visibly tighter in Figure 8 by the later iterations, suggesting that the Forager population’s pheromone-driven exploitation rapidly consolidates the colony’s search around the higher-quality solutions surfaced by the Explorers. These results support the hypothesis that decoupling exploration and exploitation into separate ant phenotypes improves both the diversity of the early search and the final solution quality on realistic problem topologies prone to local optima.