An evolutionary approach for frequency assignment in cellular radio networks

Abstract

This paper presents a study of evolutionary algorithms (EAs) for a real application: the frequency assignment problem (FAP) in cellular radio networks. This problem is of great importance both in practice and in theory. In practice, solving this problem efficiently will allow the telecommunications operator to manage larger and larger cellular networks. In theory, the simplification of FAP is reduced to the graph coloring problem which is NP-complete. In our work, we take a progressive approach: first, we study separately the different components of EAs in order to understand the interest of each of them for our application; then, we design hybrid EAs which integrate efficient techniques (local search, constraint programming, etc.) into evolutionary operators. Experiments using our approach on real-size FAP instances (up to 300 cells and 13000 constraints) give very encouraging results. Direct comparison of our approach with simulated annealing (SA), constraint programming (CP) and graph coloring algorithms on the same set of tests shows the strong interest of our hybrid evolutionary approach for this application.