I'm studying the paper "Minimizing Total Tardiness on a Single Machine Using Ant Colony Optimization" which has proposed to use Ant colony optimization to SMTWTP.

According to this paper:

Each artificial ant iteratively and independently decides which job to append to the sub-sequence generated so far until all jobs are scheduled, Each ant generates a complete solution by selecting a job $j$ to be on the $i$-th position of the sequence. This selection process is influenced through problem-specific heuristic information called visibility and denoted by $\eta_{ij}$ as well as pheromone trails denoted by $\tau_{ij}$. The former is an indicator of how good the choice of that job seems to be and the latter indicates how good the choice of that job was in former runs. Both matrices are only two dimensional as a consequence of the reduction in complexity

They have proposed this formula for the probability that job $j$ be selected to be processed on position $i$ (page 9 of the linked paper):

$$ \mathcal{P}_{i j}=\left\{\begin{array}{cl} \frac{\left[\tau_{i j}\right]^{\alpha}\left[\eta_{i j}\right]^{\beta}}{\sum_{h \in \Omega}\left[\tau_{i h}\right]^{\alpha}\left[\eta_{i h}\right]^{\beta}} & \text { if } j \in \Omega \\ 0 & \text { otherwise } \end{array}\right.\tag{1}\label{1} $$

but I can't understand what $[]$ surrounding $\eta_{ij}$ and $\tau_{ij}$ indicates. Does it show that these values are matrices?


1 Answer 1


The square brackets $[]$ in $[\tau_{ij}]^\alpha$ and $[\eta_{ij}]^\beta$ may be just a way of emphasing that the elements $\tau_{ij} \in \mathbb{R}$ and $\eta_{ij} \in \mathbb{R}$ of respectively the matrices $\mathbf{\tau} \in \mathbb{R}^{n \times n}$ and $\mathbf{\eta} \in \mathbb{R}^{n \times n}$ (where $n$ is the number of nodes in the graph) are respectively raised to $\alpha$ and $\beta$, so they could have used also other type of brackets, for example, $()$. It may also be a way of indicating that $[\tau_{ij}]$ and $[\eta_{ij}]$ are $1 \times 1$ matrices or vectors that contain respectively the scalars $\tau_{ij}$ and $\eta_{ij}$, so you are multiplying matrices or vectors (dot product).

This notation is also used in the paper that introduced the ant colony system (ACS) (and it is probably used in many other papers related to ant colony optimization). See equation 1 of Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem (1997) by Dorigo and Gambardella.

  • 1
    $\begingroup$ By the way, in the past, I've implemented the ant colony system (ACS). I've looked at my implementation and it seems to be consistent with my explanations above. $\endgroup$
    – nbro
    Commented Nov 1, 2019 at 16:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .