Swarm Intelligence, Scatter Search and Genetic Algorithm to Tackle a Realistic Frequency Assignment Problem

摘要

This paper describes three different approaches based on complex heuristic searches to deal with a relevant telecommunication problem. Specifically, we have tackled a real-world version of the FAP -Frequency Assignment Problem by using three very relevant and efficient metaheuristics. Realistic versions of the FAP are NP-hard problems because the number of available frequencies to cover the entire network communications is always much reduced. On the other hand, it is well known that heuristic algorithms are very appropriate methods when tackling this sort of complex optimization problems. Therefore, we have chosen three different strategies to compare their results. These methods are: a very novel metaheuristic based on swarm intelligence (ABC -Artificial Bee Colony) which has not ever been used previously to tackle the FAP; a very efficient Genetic Algorithm (GA) which is a classical and effective algorithm tackling optimization problems; and one of the approaches that provides better results solving our problem: Scatter Search (SS). After a detailed experimental evaluation and comparison with other approaches, we can conclude that all methodologies studied here provide very competitive frequency plans when they work with real-world FAP, although the best results are provided by the SS and the GA strategies.