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
  1. Paper Abstract
  2. Instances
  3. 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)

               
                kra30akra30a_norestart_nols                wil50
wil50_norestart_nols
                tai80b
tai80b_norestart_nols                tai100b
tai100b_norestart_nols                ES300
es300_norestart_nols 

(with local search)

                kra30a
kra30a_norestart_withls                wil50
wil50_norestart_withls                tai80b
tai80b_norestart_withls                tai100b
tai100b_norestart_withlsES300
es300_norestart_withls

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
wil50_restart_nols                tai80b
tai80b_restart_nols                tai100b
tai100b_restart_nols

(with local search)

                wil50
wil50_restart_withls                tai80b
tai80b_restart_withls                tai100b
tai100b_restart_withls