Optimizing a realistic large-scale frequency assignment problem using a new parallel evolutionary approach

Abstract

This article analyses the use of a novel parallel evolutionary strategy to solve complex optimization problems. The work developed here has been focused on a relevant real-world problem from the telecommunication domain to verify the effectiveness of the approach. The problem, known as frequency assignment problem (FAP), basically consists of assigning a very small number of frequencies to a very large set of transceivers used in a cellular phone network. Real data FAP instances are very difficult to solve due to the NP-hard nature of the problem, therefore using an efficient parallel approach which makes the most of different evolutionary strategies can be considered as a good way to obtain high-quality solutions in short periods of time. Specifically, a parallel hyper-heuristic based on several meta-heuristics has been developed. After a complete experimental evaluation, results prove that the proposed approach obtains very high-quality solutions for the FAP and beats any other result published.

Keywords:

• parallel hyper-heuristic
• frequency assignment problem
• realistic frequency planning
• parallel heuristic based on metaheuristics

Acknowledgements

The work presented here was partially funded by the Spanish Ministry of Science and Innovation and the ERDF (European Regional Development Fund) under the contract TIN2008-06491-C04-04 (the M* project).