Publication: Optimization Algorithms for Large-Scale Real-World Instances of the Frequency Assignment Problem
Loading...
Identifiers
Publication date
2010
Defense date
Advisors
Tutors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Impact
Export
Abstract
Nowadays, mobile communications are experiencing a strong growth, being more and more indispensable. One of the key issues in the design of mobile networks is the Frequency Assignment Problem (FAP). This problem is crucial at present and will remain important in the foreseeable future. Real world instances of FAP typically involve very large networks, which can only be handled by heuristic methods. In the present work, we are interested in optimizing frequency assignments for problems described in a mathematical formalism that incorporates actual interference information, measured directly on the field, as is done in current GSM networks. To achieve this goal, a range of metaheuristics have been designed, adapted, and rigourously compared on two actual GSM networks modeled according to the latter formalism. In order to generate quickly and reliably high quality solutions, all metaheuristics combine their global search capabilities with a local-search method specially tailored for this domain. The experiments and statistical tests show that in general, all metaheuristics are able to improve upon results published in previous studies, but two of the metaheuristics emerge as the best performers: a population-based algorithm (Scatter Search) and a trajectory based (1+1) Evolutionary Algorithm. Finally, the analysis of the frequency plans obtained offers insight about how the interference cost is reduced in the optimal plans.
Description
Keywords
Frequency Assignment Problem, Large- Scale Real-World Instances, Metaheuristics, Optimal Design
Bibliographic citation
Soft Computing: A Fusion of Founfations, Methodologies and Applications, 2010, vol. 15, nº 5, p. 975-990