Title: Parallel artificial immune system for the constrained graph list multicolouring problem

Authors: Riad Hadji; Nabil Menni; Ahmed Meraga; Malika Bessedik

Addresses: Laboratoire des Méthodes de Conception de Systèmes (LMCS), E.S.I ex I.N.I., BP 68M Oued Smar, 16309, Alger, Algeria ' Ecole Supérieure d'Informatique, E.S.I ex I.N.I., BP 68M Oued Smar, 16309, Alger, Algeria ' Ecole Supérieure d'Informatique, E.S.I ex I.N.I., BP 68M Oued Smar, 16309, Alger, Algeria ' Laboratoire des Méthodes de Conception de Systèmes (LMCS), E.S.I ex I.N.I., BP 68M Oued Smar, 16309, Alger, Algeria

Abstract: The constrained graph list multicolouring problem (CGLMP) is a generalised form of the graph colouring problem (CGP). It is NP-hard combinatorial optimisation problem. In this paper, the CGLMP is used to solve the well-known frequency assignment problem (FAP). The artificial immune system (AIS) has been proposed for solving several combinatorial optimisation problems. This paper presents a hybrid approach based on AIS combined to a local search for solving the CGLMP. To validate the implemented approach, many tests were carried out on academic benchmarks, and, an empirical adjustment of its parameters has been achieved. To improve the performance of this algorithm, a parallel implementation has been realised.

Keywords: artificial immune system; AIS; combinatorial optimisation; graph list multicolouring; hybrid metaheuristics; parallel algorithms; graph colouring.

DOI: 10.1504/IJMHEUR.2014.058861

International Journal of Metaheuristics, 2014 Vol.3 No.1, pp.1 - 20

Received: 06 Apr 2013
Accepted: 30 Sep 2013
Published online: 25 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article