A genetic algorithm for frequency assignment with problem decomposition Online publication date: Tue, 05-Sep-2006
by Gualtiero Colombo
International Journal of Mobile Network Design and Innovation (IJMNDI), Vol. 1, No. 2, 2006
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.
Existing subscribers:
Go to Inderscience Online Journals to access the Full Text of this article.
If you are not a subscriber and you just want to read the full contents of this article, buy online access here.Complimentary Subscribers, Editors or Members of the Editorial Board of the International Journal of Mobile Network Design and Innovation (IJMNDI):
Login with your Inderscience username and password:
Want to subscribe?
A subscription gives you complete access to all articles in the current issue, as well as to all articles in the previous three years (where applicable). See our Orders page to subscribe.
If you still need assistance, please email subs@inderscience.com
Our Blog 
Follow us on Twitter 
Visit us on Facebook