Second Order Swarm Intelligence
Vitorino Ramos1, David M.S. Rodrigues2,3, and Jorge Louçã3
1

LaSEEB – Evolutionary Systems and Biomedical Eng. Lab., ISR – Robotic and Systems Institute, Technical University of Lisbon (IST), Av. Rovisco País, 1 Torre Norte, 6.21, 1049-001
Lisbon, PORTUGAL
vitorino.ramos@ist.utl.pt
2
The Open University, Milton Keynes, UNITED KINGDOM
david.rodrigues@open.ac.uk
3
The Observatorium - ISCTE-IUL, Lisbon University Institute (IUL), Av. Forças Armadas,
1649-026 Lisbon, PORTUGAL
jorge.l@iscte.pt

Abstract: An artificial Ant Colony System (ACS) algorithm to solve generalpurpose combinatorial Optimization Problems (COP) that extends previous AC
models [21] by the inclusion of a negative pheromone, is here described. Several Traveling Salesman Problem (TSP) were used as benchmark. We show that
by using two different sets of pheromones, a second-order coevolved compromise between positive and negative feedbacks achieves better results than single positive feedback systems. The algorithm was tested against known NPcomplete combinatorial Optimization Problems, running on symmetrical TSPs.
We show that the new algorithm compares favorably against these benchmarks,
accordingly to recent biological findings by Robinson [26,27], and Grüter [28]
where "No entry" signals and negative feedback allows a colony to quickly reallocate the majority of its foragers to superior food patches. This is the first
time an extended ACS algorithm is implemented with these successful characteristics.
Keywords: Self-Organization, Stigmergy, Co-Evolution, Swarm Intelligence,
Dynamic Optimization, Foraging, Cooperative Learning, Combinatorial Optimization problems, Symmetrical Traveling Salesman Problems (TSP).

1

Introduction

Research over hard NP-complete Combinatorial Optimization Problems (COP’s) has,
in recent years, been focused on several robust bio-inspired meta-heuristics, like those
involving Evolutionary Computation (EC) algorithmic paradigms [1-3], as well as
other kind of heuristics and approximation algorithms [4-5]. One particularly successful well-know meta-heuristic [6] approach is based on Swarm Intelligence (SI) [7-8],
i.e., the self-organized stigmergic-based [9-11] property of a complex system whereby
the collective behaviors of (unsophisticated) entities interacting locally with their en-

vironment cause coherent functional global patterns to emerge [12]. This line of research recognized as Ant Colony Optimization (ACO) [13-15], uses a set of stochastic
cooperating ant-like agents to find good solutions, using self-organized Stigmergy
[16-19] as an indirect form of communication mediated by an artificial pheromone,
whereas agents deposit pheromone-signs on the edges of the problem-related complex
network, encompassing a family of successful algorithmic variations such as: Ant
Systems (AS) [20], Ant Colony Systems (ACS) [21], Max-Min Ant Systems (Max-Min
AS) [22] and Ant-Q [23].
Albeit being extremely successful these algorithms mostly rely on positive feedbacks [13], causing excessive algorithmic exploitation over the entire combinatorial
search space. This is particularly evident over well-known benchmarks as the symmetrical Traveling Salesman Problem (TSP) [24]. Being these systems comprised of a
large number of frequently similar components or events, the main challenge is to
understand how the components interact to produce a complex pattern that is still a
feasible solution [25] (in our case study, an optimal robust solution for hard NPcomplete dynamic TSP-like combinatorial problems).
In order to overcome this hard search space exploitation-exploration compromise,
our present algorithmic approach follows the route of very recent biological findings [26-28] showing that forager ants lay attractive trail pheromones to guide nest
mates to food, but where, the effectiveness of foraging networks were improved if
pheromones could also be used to repel foragers from unrewarding routes. Increasing
empirical evidences for such a negative trail pheromone exists, deployed by Pharaoh's ants (Monomorium pharaonis) as a 'no entry' signal to mark unrewarding foraging paths.
The new algorithm was exhaustively tested on a series of well-known benchmarks
over hard NP-complete COP’s, running on symmetrical TSP [24]. Different network
topologies and stress tests were conducted over low-size TSP's, medium-size TSP’s,
and as well as large sized ones. We show that the new co-evolved stigmergic algorithm compared favorably against the benchmark. In order to deeply understand how
a second co-evolved pheromone was useful to drive the collective system into such
results, the influence of negative pheromone was tracked (fig. 3-4-5), and as in previous tests [29-30], a refined phase-space map was produced mapping the pheromones
ratio between a pure Ant Colony System and the present second-order approach.

2

Towards a Co-Evolving Swarm-Intelligence

In order to make use of co-evolution we created a double-pheromone model on top
of the traditional ACS, thus allowing the comparison between the two, by having an
additional parameter. Traditional approaches to the TSP via Ant Systems include only
a positive reinforcement pheromone. Our approach uses a second negative pheromone, which acts as a marker for forbidden paths. These paths are obtained from the
worse tour of the ants and this pheromone then blocks access of ants in subsequent
tours. This blockade isn't permanent and as the pheromone evaporates it allows paths

to be searched again for better solutions. This leads to equations 5-9 that expand equations 1-4 of the original ACS and AS approaches.
Ant Colony System (ACS, [21]) state transition rule

$
(1)
β
if q ≤ q0 (exploitation)
& argmax u∈Jk (r ) [τ (r, u)] ⋅ [η (r, u)] ,
s=%
&
S,
otherwise (biased exploration)
'

{

}

Ant System (AS, [20]) random proportional rule

$
&
&
pk = %
&
&
'

(2)

β

[τ (r, s)] ⋅ [η(r, s)] ,
β
∑ [τ (r, u)] ⋅ [η(r, u)]

if s ∈ J k (r)

u∈J k (r )

0,

otherwise

Ant Colony System (ACS, [21]) local updating rule

τ (r, s) ← (1− ρ )⋅ τ (r, s) + ρ ⋅ Δτ (r, s)

(3)

Ant Colony System (ACS, [21]) global updating rule

τ (r, s) ← (1− α )⋅ τ (r, s) + α ⋅ Δτ (r, s)

2.1

(4)

ACS double-pheromone state transition rule

Following the guidelines of Dorigo and Gambardella [21], in ACS the state transition
rule is as follows: an ant positioned on node r chooses the city s to move to by applying the rule given in Eq.5

)
α
α −1
β
+ argmax u∈Jk (r ) "#τ + (r, s)$% ⋅ [η (r, s)] ⋅ "#τ − (r, s)$% , if q ≤ q0
s=*
+
S,
otherwise
,

{

}

(5)

where q is a random number uniformly distributed in [0...1], q0 is a parameter
(0<=q0<=1) and S is a random variable selected according to the probability distribution in Eq. 6. In Eq.5, the parameter q0 determines the relative importance of exploitation versus exploration, that is, every time an ant in city r has to choose a city s to
move to, it samples a random number between 0<=q0<=1. If q<=q0 then the best edge
according to Eq.5 is chosen (exploitation), otherwise an edge is chosen according to
Eq.6 (biased exploration) or random-proportional rule coming from the classic Ant
System (AS), which follows:

)
+
+
pk = *
+
+
,

α

α −1

!"τ + (r, s)#$ ⋅ [η (r, s)]β ⋅ !"τ − (r, s)#$
, if s ∈ J k (r)
α
α −1
β
∑ !"τ + (r, u)#$ ⋅ [η(r, u)] ⋅ !"τ − (r, u)#$

(6)

u∈J k (r )

0,

otherwise

Eq.6 gives the probability with which ant k in city r chooses to move to city s,
where τ is the pheromone on the (r,s) network edge, η=1/δ is the inverse of the distance δ(r,s), Jk(r) is the set of cities that remain to be visited by ant k positioned on
city r (in order to make the solution feasible), and β is a parameter which determines
the relative importance of pheromone versus distance (β>0) and α controls the ratio
between positive and negative pheromone influences. In Eq.6 the pheromones on
edge (r,s) are multiplied by the corresponding heuristic value η(r,s), thus favoring the
choice of edges which not only are shorter but also with a greater amount of positive
pheromone and some amount of negative pheromone.
The final ACS state transition rule resulting from Eqs. 5 and 6 is then called pseudo-random-proportional rule. This state transition rule, as with the previous AS random-proportional rule, favors transitions towards nodes connected by short edges and
with a large amount of pheromone.
2.2

ACS double-pheromone global updating rule

While AS used Lk, the length of the tour performed by every ant k, as a heuristic
measure for the pheromone global updating rule, ACS instead focus only in the globally best ant, among all m, i.e. the ant which constructed the shortest tour from the
beginning of the trial is allowed to deposit pheromone. This choice, along with the
use of the pseudo-random-proportional state transition rule (above) was intended to
make the search more directed: ants search in a neighborhood of the best tour found
up to the current iteration of the algorithm. Global updating is performed after all ants
have completed their tours. The pheromone level is then updated by applying the
global updating rule of Eq.7 and 8 below:
(7)
τ + (r, s) ← (1− ρ + )⋅ τ + (r, s) + ρ + ⋅ Δτ + (r, s)

&(
(L )−1, if (r, s) ∈ Global best tour
Δτ + (r, s) = ' gb
0,
otherwise
)(
where 0< ρ± <1 is the pheromone decay parameter (evaporation) and Lgb the length
of the globally best tour from the beginning of the trial. As it was the case in AS, the
ACS global pheromone updating provides a greater amount of pheromone to shorter
tours. Eq.7 dictates that only those edges belonging to the global best tour will receive
reinforcement while Eq.8 dictates that only those edges that belong to the worse tour
receive negative pheromone deposition.

2.3

ACS double-pheromone local updating rule

In order for the 2nd order algorithm (as in ACS) to build a solution, i.e. a TSP tour,
ants visit edges and change their pheromone level by applying a local updating rule
given by Eq.9:

τ − (r, s) ← (1− ρ − )⋅ τ − (r, s) + ρ − ⋅ Δτ − (r, s)
&(
(nLgb )−1, if (r, s) ∈ Global worse tour
Δτ − (r, s) = '
0,
otherwise
()

(8)

τ + (r, s) ← (1− ρ + )⋅ τ + (r, s) + ρ + ⋅ Δτ + (r, s)

(9)

τ − (r, s) ← (1− ρ − )⋅ τ − (r, s) + ρ − ⋅ Δτ − (r, s)
where 0<ρ<1 is a parameter. From here several options are possible where, Δτ(r,s)
could assume the form of Δτ(r,s)=γ. max τ(s,z) [z Jk(S) ] similarly to a reinforcement
learning problem, onto which ants have to learn which city to move to as a function of
their current location. This first option assumes Q-learning, an algorithm which allows an agent to learn such an optimal policy by the recursive application of a rule
similar to that in Eq.4, giving rise to the first Ant-Q ant systems. In fact, Δτ(r,s)=γ.
max τ(s,z) is exactly the same formula used in Q-learning where 0<γ<1 is a parameter.
The other two choices are normally: (1) setting Δτ(r,s)=τ0, being τ0 the initial pheromone level, or (2) simply setting Δτ(r,s)=0. Finally, experiments could also be ran in
which local-updating are not applied at all, that is, where the local updating rule is not
used as in the case of the older and previous AS).
Current research work however, suggests that local-updating is not only definitely
useful, but that the pheromone local updating rule with Δτ(r,s)=0 yields worse performance than Δτ(r,s)=τ0 or even Ant-Q. In fact, Δτ(r,s)=τ0 was chosen for the standard ACS, from the beginning [13-15][20,21,23]. Since the ACS local updating rules
not only requires less computation than Ant-Q as well as achieving better results, we
chose to focus our attention on ACS, which will be used, along others, to run the
comparison experiments against our new co-evolved pheromone-based algorithm in
the following paper sections.

3

Results

The new algorithm was exhaustively tested on a series of well-known
benchmarks over hard NP-complete COP’s) running on symmetrical TSP’s. Different
network topologies and stress tests were conducted over low-size TSP's (eil51.tsp;
eil78.tsp; kroA100.tsp), medium-size (d198.tsp; lin318.tsp; pcb442.tsp; rat783.tsp) as
well as large sized ones (fl1577.tsp; d2103.tsp) [numbers here referring to the number

of nodes in each network].
Table 1. Comparison of Standard ACS with the 2nd order AS algorithm
problem
n.º of nodes
Standard ACS
2nd order+ AS
eil51.tsp
eil78.tsp
kroA100.tsp
d198.tsp
lin318.tsp
pcb442.tsp
rat783.tsp
fl1577.tsp
d2103.tsp

51
78
100
198
318
442
783
1577
2103

427.96
**
21285.44
16054
42029***
51690
9066
23163
-

428.87
544.65
21285.44
15900.2
42683.90
51464.48
8910.48
22518
81151.9

optimal tour
426
538
21282
15780
42029
50778
8806
22249
80450

All optimal tours from http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html
+ Average over 20 runs and limited to 1000 iterations
** Value for similar problem eil75,.tsp - 542.37 *** uses 3-opt local search
Comparing Traditional AS Models with 2nd Order

It is clear from table 1 that the 2nd order AS performs at least equally, if not better,
than the standard ACS. It is clearly seen the averages of the runs (bold) that are better
than the traditional ACS.












Fig. 1. Influence of negative pheromone on kroA100.tsp problem
(values on lines represent 1-ALPHA)

We investigated the evolution of different ratios of negative pheromone and found
that a small amount of negative pheromone applied as a non-entry signal indeed produces better results, but the effect is cancelled if the ratio of the negative pheromone
is high when compared to the positive pheromone.
Best Length for different values of ALFA and EPSILON
Problem: rat783.tsp
(averged over 20 runs)
EPSILON 0.0080 ALFA 0.0920
EPSILON 0.0087 ALFA 0.0913
EPSILON 0.0093 ALFA 0.0907
EPSILON 0.0100 ALFA 0.0900
EPSILON 0.0107 ALFA 0.0893
EPSILON 0.0113 ALFA 0.0887
EPSILON 0.0120 ALFA 0.0880
EPSILON 0.0127 ALFA 0.0873
EPSILON 0.0133 ALFA 0.0867
EPSILON 0.0140 ALFA 0.0860
ACS

9040

9020

distance

9000

8980

8960

8940

8920

2

3

10

10
iteration

nd

Fig. 2. Best tour of the 2 order AS for different ratios of negative pheromone in the
rat783.tsp problem

ACS alpha=0.94

The effect of negative pheromone can be observed both in figure 1 and figure 2
where one can observe that small amounts of negative pheromone produce better results and quicker convergence to those results. On the other hand if one increases the
ratio of negative pheromone to higher values then it isn’t possible to ripe the benefits
of the no-entry signal and the system performs worse.

21300

21400

21500

21600

21700

21800

Fig. 3. Influence of negative pheromone on kroA100.tsp problem.

The detailed analysis of the kroA100.tsp problem showed that this effect is statistically significant. Comparing 120 runs with alpha=1 (equivalent to traditional ACS)
and alpha=0.94, we obtained a p-value of 3x10-4. This result is summarized in fig-

ACS

alpha=0.94

ure 3, where one compares traditional ACS with our 2nd order approach.

9200

9300

9400

9500

9600

9700

Fig. 4. Influence of negative pheromone on rat783.tsp problem.

alpha

0.85 0.88 0.91 0.94 0.97

1

The same results where observed for problem rat783.tsp when comparing 70 runs
of the ACS (alpha=1) with 70 runs of the 2nd order approach (with alpha=0.94) in
figure 4. The two samples means were tested for statistical significance resulting in a
p-value of 2.2x10-3.
Both these examples show that on average the 2nd order approach performs better
than traditional ACS. This effect of the negative pheromone is important but cannot
be extended further as to dominate the solving strategy, making results worse. This
can be seen clearly on figure 5 where further diminishing of alpha (giving more
weight to negative pheromone as a consequence) produces worse results.

● ● ●

●

9100

Fig. 5. If dominant,

4

9200

9300

9400

distance
negative
pheromone
has negative
impact
(problem
(rat783.tsp,
20 runs, beta=4.4,
rho=0.075,
q0=0.95)

rat783.tsp)

Conclusion

We show that the new co-evolved stigmergic algorithm compared favorably against
the benchmark. The inclusion of a negative pheromone acting as a `non-entry’ signal
in the strategy of construction of solutions is beneficial as the convergence to optimal
solutions is quicker, as shown in figure 2, while achieving better results (figures 3 and

4). The algorithm was able to equal or majorly improve every instance of those standard algorithms.
The new algorithm comprises a second order approach to Swarm Intelligence, as
pheromone-based no entry-signals cues, were introduced, coevolving with the standard pheromone distributions (collective cognitive maps [12]) in the aforementioned
known algorithms.
The use of the negative pheromone is limited to small quantities (alpha close to 1,
but not 1, in which case we would end up with a pure ACS) and cannot be extended to
a point of dominance in the search strategy as shown in figure 5. The results found for
the TSP problems in that case are severely worse. This implies that the use of a negative pheromone strategy has to be fine tuned as not to dominate the search strategy.
This is done with the introduction of the parameter alpha that balances the weight of
the two pheromones deposition in equations 5 and 6.
This work has implications in the way large combinatorial problems are addressed
as the double feedback mechanism shows improvements over the single-positive
feedback mechanisms in terms of convergence speed and of major results.

References
1.
2.
3.
4.
5.
6.
7.

8.
9.
10.

11.
12.

13.
14.

Holland, J.H., Adaptation in Natural and Artificial Systems, University of Michigan Press, MI,
USA, (1975).
Goldberg, D.E., Genetic Algorithms in Search, Optimization, and Machine Learning. AddisonWesley, USA, (1989).
Fogel, D.B., Evolutionary Computation, IEEE Press, Piscataway, NJ, USA, (1995).
106 - Siarry, P. and Michalewicz, Z. Advances in Metaheuristics for Hard Optimization, Springer, (2008).
Gonzalez, T. F. (Ed.), Approximation Algorithms and Metaheuristics, CRC Press, (2007).
44 - Alba, E., Parallel Metaheuristics. A New Class of Algorithms, Wiley, Cambridge, NJ, USA,
(2005).
Bonabeau, E., Dorigo, M., Theraulaz, G., Swarm Intelligence: From Natural to Artificial Systems, Santa Fe Institute series in the Sciences of Complexity, Oxford Univ. Press, New York,
NY, (1999).
Blum, C. and Merkle, D. (Eds.), Swarm Intelligence: Introduction and Applications, Natural
Computing Series, Springer-Verlag, Heidelberg, (2008).
Camazine, S., Deneubourg, J.-L., Franks, N., Sneyd, J., Theraulaz, G. and Bonabeau, E., SelfOrganization in Biological Systems, Princeton University Press, Princeton, NJ, USA, (2003).
Chialvo, D.R., Millonas, M.M., How Swarms build Cognitive Maps, In Steels, L. (Ed.): The Biology and Technology of Intelligent Autonomous Agents, 144, NATO ASI Series, 439-450,
(1995).
Millonas, M.M., A Connectionist-type model of Self-Organized Foraging and Emergent Behavior in Ant Swarms, J. Theor. Biol., nº 159, 529, (1992).
Ramos, V., Fernandes, C., Rosa, A.C., On Self-Regulated Swarms, Societal Memory, Speed and
Dynamics, in Artificial Life X - Proc. of the Tenth Int. Conf. on the Simulation and Synthesis of
Living Systems, L.M. Rocha, L.S. Yaeger, M.A. Bedau, D. Floreano, R.L. Goldstone and A.
Vespignani (Eds.), MIT Press, pp. 393-399, Bloomington, Indiana, USA (2006).
Dorigo, M., Maniezzo, V. and Colorni, A., Positive Feedback as a Search Strategy, Technical
report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Italy, (1991).
Dorigo, M. and Di Caro, G.: The Ant Colony Optimization Meta-heuristic, in New Ideas in Op-

15.
16.

17.
18.
19.
20.
21.
22.
23.

24.
25.

26.
27.

28.

29.

30.

timization, Corne, D., Dorigo, M, and Glover, F. Eds., McGraw-Hill, New York, p.11 (1999).
Dorigo, M., Di Caro, G. and Gambardella, L.M., Ant algorithms for Discrete Optimization, Artificial Life, 5(2), p. 137 (1999).
Grassé, P.P.: La reconstruction du nid et les coordinations interindividuelles chez Bellicositermes natalensis et Cubitermes sp. La théorie de la Stigmergie : Essai d’interpretation des termites
constructeurs. Insect Sociaux, 6, 41-83 (1959).
Theraulaz, G., Bonabeau, E., A Brief History of Stigmergy, Artificial Life, special issue dedicated to Stigmergy, Vol. 5, n. 2, MIT Press, pp. 97-116, (1999).
Abraham, A, Grosan, C., and Ramos, V. (Eds.), Stigmergic Optimization, Studies in Computational Intelligence (series), Vol. 31, Springer-Verlag, 295 p., Hardcover, (2006).
Diaf, M., Hammouche, K., Siarry, P., From the Real Ant to the Artificial Ant. Nature-Inspired
Informatics for Intelligent Applications and Knowledge Discovery, 298-322, (2010).
Dorigo, M., Maniezzo, V. and Colorni, A., Ant System: Optimization by a Colony of Cooperating Agents, IEEE Trans. Syst., Man, and Cybern. - Part B, 26(1), 29, (1996).
Dorigo, M. and Gambardella, L.M.: Ant Colony System: A Cooperative Learning approach to
the Travelling Salesman Problem, IEEE Trans. Evol. Computation, 1(1), 53 (1997).
Stützle, T. and Hoos, H.H., MAX-MIN Ant System, Future Generation Comput. Syst., 16(8), p.
889 (2000).
Gambardella, L.M. and Dorigo, M. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem. Proceedings of ML-95, Twelfth International Conference on Machine
Learning, Tahoe City, CA, A. Prieditis and S. Russell (Eds.), Morgan Kaufmann, 252260, (1995).
Lawler, E.L., Lenstra, J.K., Rinnooy-Kan, A.H.G., and Shmoys, D.B., The Travelling Salesman
Problem, Wiley, New York, NY, (1985).
Ramos, V., Almeida, F., Artificial Ant Colonies in Digital Image Habitats: A Mass Behavior Effect Study on Pattern Recognition, in Dorigo, M., Middendorf, M., Stützle, T. (Eds.): From Ant
Colonies to Artificial Ants – ANTS 2000 - 2nd Int. Wkshp on Ant Algorithms, 113-116, (2000).
Robinson, E.J.H et al. “Insect communication - ‘No entry’ signal in ant foraging.” Nature
438.7067 (2005): 442-442.
Robinson, E.J.H; Jackson, D; Hocombe, Mike; and Ratnieks, F.L.W, No entry signal in ant foraging (Hymenoptera: Formicidae): new insights from an agent-based model, Myrmecological
News, 10: 120, Vienna, Sept. (2007)
Grüter C, Schürch R, Czaczkes TJ, Taylor K, Durance T, et al. (2012) Negative Feedback Enables Fast and Flexible Collective Decision-Making in Ants. PLoS ONE 7(9): e44501.
doi:10.1371/journal.pone.0044501
Rodrigues, D.M.S., Louçã, J., Ramos, V., From Standard to Second-Order Swarm Intelligence
Phase-space Maps, in 8th European Conference on Complex Systems, Stefan Thurner (Eds.),
poster, Vienna, Austria, Sept. (2011).
Ramos, V., Rodrigues, D.M.S., Louçã, J., Spatio-Temporal Dynamics on Co-Evolved Stigmergy, in 8th European Conference on Complex Systems, Stefan Thurner (Eds.), poster, Vienna,
Austria, Sept. (2011).

