Title: A genetic algorithm for frequency assignment with problem decomposition

Authors: Gualtiero Colombo

Addresses: School of Computer Science, Centre for Intelligent Network Design, Cardiff University, Cardiff, UK

Abstract: The FAP is an optimisation problem which assigns frequencies to ransmitters in as efficient way as possible, either in terms of interference, FS-FAP, or range of channels used, MS-FAP. The FAP can be modelled in graph theoretic terms. This paper uses a |permutation-based| steady-state GA adapted to solve both types of FAP. Problem decomposition techniques have been introduced to improve the GA performance. A large problem is decomposed into smaller subproblems consisting of distinct induced subgraphs. Then the GA is applied to each of them in turn producing partial solutions. Finally, these are recombined into a final solution of the original problem. We have used a basic decomposition based on the generalised-degree of the graph vertices and one obtained by solving the balanced graph partitioning problem. The GA produces better or comparable results with other widely known meta-heuristics in all the test problems considered.

Keywords: genetic algorithms; GA; frequency assignment problem; FAP; graph partitioning; wireless networks; mobile networks.

DOI: 10.1504/IJMNDI.2006.010812

International Journal of Mobile Network Design and Innovation, 2006 Vol.1 No.2, pp.102 - 112

Published online: 05 Sep 2006 *

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