Title: Tuning the PBIL algorithm to solve a real-world FAP problem

Authors: Jose M. Chaves-Gonzalez, Miguel A. Vega-Rodriguez, David Dominguez-Gonzalez, Juan A. Gomez-Pulido, Juan M. Sanchez-Perez

Addresses: Department of Technologies of Computers and Communications, Extremadura University, Escuela Politecnica, Av. Universidad s/n, 10071, Caceres, Spain. ' Department of Technologies of Computers and Communications, Extremadura University, Escuela Politecnica, Av. Universidad s/n, 10071, Caceres, Spain. ' Department of Technologies of Computers and Communications, Extremadura University, Escuela Politecnica, Av. Universidad s/n, 10071, Caceres, Spain. ' Department of Technologies of Computers and Communications, Extremadura University, Escuela Politecnica, Av. Universidad s/n, 10071, Caceres, Spain. ' Department of Technologies of Computers and Communications, Extremadura University, Escuela Politecnica, Av. Universidad s/n, 10071, Caceres, Spain

Abstract: Frequency planning, also known as frequency assignment problem (FAP), is a very important task for current GSM operators. FAP basically tries to minimise the number of interferences (or conflicts in the communications) caused when a limited number of frequencies has to be assigned to a quite high number of transceivers (and there are much more transceivers than frequencies). In this work, we focus on solving this problem for a realistic-sized, real-world GSM network using the population-based incremental learning (PBIL) algorithm. The work described here is divided in two parts. In the first one, we analyse and fix the standard PBIL algorithm to solve the FAP; whereas in the second, we take as initial point the results obtained with the standard version of PBIL and we perform a complete study with the most relevant variations of the algorithm to discover which approach can compute the best frequency plans for real-world instances.

Keywords: frequency assignment problem; FAP; population-based incremental learning; PBIL; local search; M-solutions; evolutionary algorithms; frequency planning; transceiver; TRX; GSM networks; mobile communications.

DOI: 10.1504/IJRIS.2010.029811

International Journal of Reasoning-based Intelligent Systems, 2010 Vol.2 No.1, pp.2 - 12

Published online: 02 Dec 2009 *

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