IEEE Computational Intelligence Magazine - February 2020 - 52

Research
Frontier

Michalis Mavrovouniotis
KIOS Research and Innovation Center of Excellence, Department of Electrical
and Computer Engineering, -University of Cyprus, Nicosia, CYPRUS
Shengxiang Yang
School of Computer Science and Informatics, De Montfort University,
Leicester, UK
Mien Van
School of Electronics, Electrical Engineering and -Computer Science, Queen's
University Belfast, Belfast, UK
Changhe Li
School of Automation, China University of Geosciences, Wuhan, China, and
Hubei Key Laboratory of Advanced Control and Intelligent Automation for
Complex Systems, Wuhan, CHINA
Marios Polycarpou
KIOS Research and Innovation Center of Excellence, Department of Electrical
and Computer Engineering, -University of Cyprus, Nicosia, CYPRUS

Ant Colony Optimization Algorithms for Dynamic Optimization:
A Case Study of the Dynamic Travelling Salesperson Problem
Abstract

A

nt colony optimization is a swarm
intelligence metaheuristic inspired
by the foraging behavior of some
ant species. Ant colony optimization has
been successfully applied to challenging
optimization problems. This article
investigates existing ant colony optimization algorithms specifically designed
for combinatorial optimization problems
with a dynamic environment. The investigated algorithms are classified into two
frameworks: evaporation-based and population-based. A case study of using
these algorithms to solve the dynamic
traveling salesperson problem is de--
scribed. Experiments are systematically
conducted using a proposed dynamic
benchmark framework to analyze the
effect of important ant colony optimization features on numerous test
cases. Different performance measures
are used to evaluate the adaptation
capabilities of the investigated algorithms, indicating which features are the
most important when designing ant colDigital Object Identifier 10.1109/MCI.2019.2954644
Date of current version: 10 January 2020

52

©ISTOCKPHOTO.COM/CLICKCLICK1

ony optimization algorithms in dynamic
environments.
I. Introduction

Ant colony optimization (ACO) is a
well-known metaheuristic for combinatorial optimization problems inspired by
Corresponding Author: Michalis Mavrovouniotis (Email:
mavrovouniotis.michalis@ucy.ac.cy)

IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE | FEBRUARY 2020

the foraging behavior of real ant colonies [1], [2]. Ants are able to find the
shortest path between a food source and
their nest [3]. They lay pheromones (a
chemical substance produced by ants)
on the ground to mark their path, forming in this way a pheromone trail, and
they tend to follow paths marked by
strong pheromone concentrations. In
this way, the ants are able to share information with their nest mates.
In ACO, a colony of (artificial) ants
cooperates in constructing high-quality
solutions to difficult combinatorial optimization problems [4]. The construction
of solutions is guided by (artificial) pheromone trails. The pheromone model
used to update the pheromone trails is
inspired by the pheromone trail laying
and following behavior of real ants. This
is basically a parametrized probabilistic
model that is modified by the ants to
reflect their experience while optimizing a particular problem.
ACO was initially designed for solving
static combinatorial optimization problems
[4]. However, the environments of many
real-world problems are often dynamic [5].
A dynamic combinatorial optimization

1556-603X/20©2020IEEE
http://www.ISTOCKPHOTO.COM/CLICKCLICK1
IEEE Computational Intelligence Magazine - February 2020

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