A genetic algorithm for frequency assignment with problem decomposition. (6th September 2006)

• Record Type: Journal Article
• Authors: Colombo, Gualtiero
• Is Part Of: International journal of mobile network design and innovation. Volume 1:Number 2(2006)
• Page Start: 102
• Page End: 112
• Publication Date: 2006-09-06
• Subjects: genetic algorithms -- GA -- frequency assignment problem -- FAP -- graph partitioning -- wireless networks -- mobile networks; Mobile communication systems -- Periodicals; Wireless communication systems -- Design and construction -- Periodicals; 384.535
• Languages: English
• ISSNs: 1744-2869

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.