IEEE Computational Intelligence Magazine - February 2020 - 54

can change: 1) the set of nodes [13], and
2) the weights on the arcs [11]. A change
to any of these problem components will
also cause a change to the weight matrix
defined in Equation  1 and, thus, it may
affect the algorithm's output: the best
output before a change may not be the
best (or even feasible) after the change.
Real-world applications that encompass
the aforementioned types of dynamic
changes can be found in many fields,
including transportation. For example,
changes in the traffic situation (i.e.,
weight changes) or changes in the visiting locations (i.e., node changes).
1) DTSP with Node Changes
The key idea to generate a dynamic test
case with this type of changes is to replace
nodes from the current working node set
N in(T ), where N in(0) = N, with newly
introduced nodes drawn from another set
N out(T ). The latter set N out(T ) is initially generated with n new random nodes
in the range of the N set. A dynamic
change of this type occurs as follows.

1

Node Changes
. . .
n

. . .

1

n
(a)
1

Weight Changes
. . .
n

Every f evaluations exactly ^mnh nodes
are randomly selected from N out(T ) to
replace exactly ^mnh randomly selected
nodes from N in(T ), where m (m ! (0, 1])
defines the magnitude of change. The
higher the value of m, the more nodes
will be replaced. In this way, the weight
matrix will be affected because the
weights on the arcs connecting the
replaced nodes will be modified.
2) DTSP with Weight Changes
A dynamic test case with this type of
changes can be generated by assigning an
increasing/decreasing factor value to the
arc connecting nodes i and j as follows:
w ij(T + 1) =
w ij(0) + R ij, if arc (i, j ) ! A S(T ),
(3)
'
w ij(T ),
otherwise,

where w ij(0) is the initial weight of arc
(i, j ) (from the static TSP instance when
T = 0), R ij is a normally distributed
random number (with zero mean and
standard deviation set proportional to
w ij(0) as in [20]) that defines the modified f actor value to arc (i, j ), and
A S(T ) 1 A defines the set of arcs randomly selected for the change at that
period. Consider that the size of the set
A is defined by the number of arcs as
follows: n(n - 1). Then, the size of
A S(T ) is defined by the magnitude of
change (i.e., m ! (0, 1]) and the size of
A. Therefore, every f evaluations
exactly ^mn (n - 1)h arcs will be selected
to change their weights. The higher the
value of m, the more arcs will be selected for changes.

1

. . .

C. Some Additional Remarks

n
(b)
FIGURE 1 Illustration of the weight matrix
when node (a) and weight (b) dynamic
changes (with m = 0.2 in this example)
occur. Gray boxes denote a change to the
weight. Note that the symmetry with respect
to the main diagonal line is due to the fact
that symmetric problem instances are used
to generate DTSPs.

54

It must be noted that there are some
ACO algorithms that benefit from the
use of less ants (e.g., the Ant Colony
System [1]), resulting in less evaluations
per algorithmic iteration, and some
other ACO algorithms that benefit from
the use of more ants (e.g., the hyper
populated ant colonies [25], [26]),
resulting in more evaluations per algorithmic iteration. Therefore, the frequency of change is expressed in
evaluations in the described dynamic
benchmark framework. In this way, a fair

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2020

comparison between the competing
algorithms is ensured with the generated
DTSP test cases because the dynamic
changes occur at exactly the same period of time (i.e., all algorithms have
exactly the same number of evaluations
available between the environmental
changes). Also, the period of change is
restricted either at the start or at the end
of an algorithmic iteration [27].
From the way the magnitude of change
is defined for both DTSP types, there
exists an interesting observation: the
weights of the same number of arcs, but
not necessarily the same arcs, are modified
when the same value of m is selected for
DTSPs that utilize symmetric problem
instances. For example, in Figure  1 the
dynamic change with magnitude set to
m = 0.2 will change one node for a
problem of size five (i.e., ^0.2 # 5h) when
node changes occur and four arcs for the
same problem (i.e., ^0.2 # 5(5 - 1)h)
when weight changes occur. Consider
that there are two arcs connecting a pair
of nodes and their weights are the same in
symmetric problem instances. For a problem of size five in a fully connected graph,
each node is connected with the remaining four nodes; therefore, when one node
is replaced, the weights of eight arcs in
total will be modified as shown in Figure  1(a). For the same problem, the
weights of the four selected arcs will be
modified when weight changes occur,
but, due to the symmetric property of the
problem instance, each time the weight of
an arc (i, j ) changes, the weight of the arc
( j, i ) changes to the same value. As a
result, the weights of eight arcs in total
will actually change (as in the case of
node changes) as shown in Figure 1(b).
III. Classification of ACO
Algorithms
A. ACO for the Dynamic Travelling
Salesperson Problem

In the ACO metaheuristic, a colony of ~
artificial ants constructs solutions by incrementally selecting feasible solution components. Each solution component is
associated with a pheromone value which
is used to guide artificial ants when selecting the next solution component. Since
IEEE Computational Intelligence Magazine - February 2020

Table of Contents for the Digital Edition of IEEE Computational Intelligence Magazine - February 2020
