A
Detailed Analysis of the Population-based Ant Colony
Optimization
Algorithm for the TSP and the QAP
by Sabrina
Oliveira, Mohamed
Saifullah Hussin, Thomas
Stützle, Andrea
Roli and Marco
Dorigo
Last updated in January 2017
Submitted to IEEE CEC 2017
This page contains
all
supplementary information that, for the sake of conciseness, was not
included in the paper.
Table of Contents
- Paper Abstract
- Instances
- Additional Plots
|
1. Paper Abstract
The
population-based ant colony optimization algorithm (P-ACO) differs from
other ACO algorithms through its implementation of the pheromone update
management. P-ACO keeps track of a population of solutions, which
serves as an archive of solutions generated by the ants' colony.
Pheromone updates in P-ACO are only done based on solutions that enter
or leave the solution archive. The population-based scheme reduces
considerably the computation time needed for the pheromone update when
compared to ACO algorithms such as Ant System. In this work, we study
P-ACO's behavior for solving the traveling salesman problem and the
quadratic assignment problem. In particular, we investigate the impact
of a local search on P-ACO parameters and performance. The results
clearly show that P-ACO is a very competitive tool in which its
parameters and behavior depend strongly on the problem tackled and
whether or not a local search is used.
Keywords: Traveling salesman problem, quadratic
assignment problem, ant colony optimization, population based ant
colony optimization.
2. Instances
Instances that were used for experiments
in this article can
be
downloaded below:
TSP instances.
QAP instances.
3. Additional Plots
3.1 Analysis of P-ACO Specific Parameters Settings - TSP
3.1.1 Analysis of K
(Without Local Search)
eil101
d198
kroA200
rd400
d657
u724
d2103
u2319
(With Local Search)
u724
u1817
d2103
u2319
3.1.2 Analysis of tmax
(Without Local Search)
eil101
d198
kroA200
kroA400
u1817
u2319
(With Local Search)
u724
u1817
d2103
u2319
3.1.3 Influence of using Different Strategies to Update the
Solution Archive
Elitist Strategy
Without Local Search
eil101
d198
kroA200
rd400
d657
d2103
u2319
(With Local Search)
u724
u1817
d2103
u2319
Quality Strategy
(Without Local Search)
eil101
d198
kroA200
rd400
d657
u724
u1817
d2103
u2319
(With Local Search)
u724
u2103
u2319
Strategies Comparison
(Without Local Search)
eil101
d198
d198
kroA200
rd400
d657
u724
u1817
d2103
u2319
(With Local Search)
u724
d2103
u2319
Quality Strategy with restart
(Without Local Search)
eil101
d198
kroA200
rd400
d657
u1817
d2103
u2319
(With Local Search)
u724
d2103
u2319
3.2 Analysis of P-ACO - QAP
3.2.1 Comparison between strategies - PACO without restart
mmas = max-min ant system, paconr = P-ACO with
age-based strategy, paconre = P-ACO with elitist strategy, paconrq =
paco with quality-based strategy
(without local search)
kra30a
wil50
tai80b
tai100b
ES300
(with local search)
kra30a
wil50
tai80b
tai100b
ES300
3.2.2 Comparison between strategies - PACO with restart vs without
restart
mmas = max-min ant system, pacoq014nr = P-ACO
without restart, pacoq014r100 = P-ACO with restart
(without local search)
wil50
tai80b
tai100b
(with local search)
wil50
tai80b
tai100b