Hierarchical parallel approach for GSM mobile network design

Cellular network design is a major issue in second generation GSM mobile telecommunication systems. In this paper, a new model of the problem in its full practical complexity, based on multiobjective constrained combinatorial optimization, has been used. We propose an evolutionary algorithm that aims at approximating the Pareto frontier of the problem, which removes the need for a cellular network designer to rank or weight objectives a priori. Specific coding scheme and genetic operators have been designed. Advanced intensification and diversification search techniques, such as elitism and adaptive sharing, have been used. Three complementary hierarchical parallel models have been designed to improve the solution quality and robustness, to speed-up the search and to solve large instances of the problem. The obtained Pareto fronts and speed-ups on different parallel architectures show the efficiency and the scalability of the parallel model. Performance evaluation of the algorithm has been carried out on different realistic benchmarks. The obtained results show the impact of the proposed parallel models and the introduced search mechanisms. (c) 2005 Elsevier Inc. All rights reserved.