Ant-Q
Algorithms AIMech:AntQ DRAFT
A family of cooperative ant-based optimization algorithms that learns shared edge desirabilities using Q-learning-inspired next-state estimates and delayed reinforcement from completed solutions.
Identity Notes & Concept Scope
This record denotes the Ant-Q family through its traveling-salesman formulations, especially pseudo-random-proportional construction and best-tour reinforcement. Its next-state estimate distinguishes the nondegenerate Ant-Q update from the selected ACS rule targeting a constant tau0. The authors relate Ant System to the broader family; that relationship does not make every Ant-Q configuration identical to Ant System. This is an algorithm-family concept, not a trained value function or a proof of Q-learning equivalence. No normalized identity match was found across all 442 pinned AIO labels/scoped synonyms and 291 preceding native IDs/names/aliases. Full-checkout fixed-string searches included ignored and hidden files in worktree and main, returning 61 and 71 lines respectively. Text hits were prior candidate leads, citations to a reused Ant System source, neighboring mechanism distinctions, saved review/report material, and unrelated PBIL strings in ignored HOGENOM prefix-map URLs. Eight exact AIO CLASS nodes with scoped synonyms/comments and outgoing edges and five native neighboring mechanisms were inspected. Absence is bounded to this snapshot and semantic neighborhood.
Claims & Grounded Evidence
1 Claim
Mechanism
#method
Maintain shared positive AQ(r,s) edge values, a heuristic HE(r,s) such as inverse positive distance, and each ant’s set J of unvisited cities. In the pseudo-random-proportional variant, draw q uniformly in [0,1]: for q<=q0 choose an eligible edge maximizing AQ^delta*HE^beta, otherwise sample with probabilities proportional to those weights over eligible cities. While constructing tours, the displayed update is AQ(r,s)_new=(1−alpha)*AQ(r,s)+alpha*(DeltaAQ(r,s)+gamma*max_{z in J(s)} AQ(s,z)); immediate DeltaAQ is zero in the inspected variants. After completing tours, delayed reinforcement is W/L_best on edges of a selected best tour and zero elsewhere. The paper studies both iteration-best and best-so-far choices and selects iteration-best for most subsequent experiments. In the 1995 Figure1 delayed phase, the next-state term is explicitly declared zero, so the per-edge update where applied reduces to (1−alpha)*AQ+alpha*DeltaAQ. The 1996 presentation explicitly restricts that global phase to the iteration-best tour and resets per-tour ant state each iteration. These are source-scoped formulations; terminal handling and the exact edge-update schedule must be declared when implementing a concrete member.
⚠️ Curated Limitations & Negative Results
- The eligible action set depends on an ant’s visited-city history, while AQ is shared per edge. City identity alone is therefore not a complete Markov state for tour feasibility. The 1995 conclusion treats transfer of Q-learning theory as future work; standard Q-learning convergence is not an established Ant-Q guarantee here.
- The 1995 generic diagram loops over edges to compute delayed reinforcement and gives an incompletely specified final update domain; its repeat jump omits explicit state reset and its terminal local maximum needs a convention. The 1996 method makes best-tour-only global updates and per-tour reset explicit but references its update equation without restating the earlier zero-next-state convention. The record preserves these version details instead of claiming a fully executable common pseudocode.
- The pseudo-random, pseudo-random-proportional and random-proportional construction rules are distinct members. Positive trails alone do not ensure exploration when q0=1, candidates are excluded or weights vanish. Empty eligible sets, zero distances, ties, repeated edge updates and numerical underflow require explicit handling.
- The learned edge values guide stochastic search rather than certify globally optimal tours. Heuristic choice, parameters, number of ants, update ordering and stopping affect results. Neither the paper’s observed noncollapse nor its TSP/ATSP comparisons is asserted as a universal guarantee.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:ReinforcementLearning
Reinforcement Learning
|
related_match | Ant-Q explicitly constructs shared action-like values using a Q-learning-inspired discounted next-state term and delayed reinforcement. This relates the concrete combinatorial optimizer to the pinned learning-task class; it asserts neither identity nor subclass membership. History-dependent feasibility and source-specific update schedules prevent importing standard Q-learning guarantees. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Luca M. Gambardella, Marco Dorigo
|
primary paper
full_text
|
ID: https://staff.washington.edu/paymana/swarm/gambardella95-icml.pdf
sha256:60ea0bfe6b4f…
|
later-formulation
|
Marco Dorigo, Luca Maria Gambardella
|
author technical report
full_text
|
ID: doi:10.1007/3-540-61723-X_1029
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T13:37:30Z
Updated: 2026-10-11T13:37:30Z
Source File:
data/curated/AntQ.yaml