Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
GSM World (2009), http://www.gsmworld.com/news/statistics/index.shtml
Hale, W.K.: Frequency assignment: Theory and applications. Proceedings of the IEEE 68(12), 1497–1514 (1980)
Blum, C., Roli, A.: Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Surveys 35, 268–308 (2003)
Karaboga, D., Basturk, B.: A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization 39, 459–471 (2007)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Longman Publishing, Amsterdam (1989)
Glover, F., Laguna, M., Martí, R.: Scatter search. In: Advances in Evolutionary Computing: Theory and Applications, pp. 519–537. Springer, Heidelberg (2003)
Eisenblätter, A.: Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds. PhD thesis, Technische Universität Berlin (2001)
Mishra, A.R.: Fundamentals of Cellular Network Planning and Optimisation: 2G/2.5G/3G... Evolution to 4G, pp. 21–54. Wiley, Chichester (2004)
Kuurne, A.M.J.: On GSM mobile measurement based interference matrix generation. In: 55th Vehicular Technology Conference, VTC Spring 2002, pp. 1965–1969 (2002)
Luna, F., Blum, C., et al.: ACO vs EAs for Solving a Real-World Frequency Assignment Problem in GSM Networks. In: GECCO 2007, London, UK, pp. 94–101 (2007)
Chaves-González, J.M., Vega-Rodríguez, M.A., et al.: Solving a Real–World FAP Using the Scatter Search Metaheuristic. In: Moreno-Díaz, R., Pichler, F., Quesada-Arencibia, A. (eds.) Computer Aided Systems Theory - EUROCAST 2009. LNCS, vol. 5717, pp. 785–792. Springer, Heidelberg (2009)
da Silva Maximiano, M., et al.: A Hybrid Differential Evolution Algorithm to Solve a Real-World Frequency Assignment Problem. In: International Multiconference on Computer Science and Information Technology, Wisła, Poland, pp. 201–205 (2008)
Luna, F., Estébanez, C., et al.: Metaheuristics for solving a real-world frequency assignment problem in GSM networks. In: GECCO 2008, Atlanta, GE, USA, pp. 1579–1586 (2008)
Chaves-González, J.M., Vega-Rodríguez, M.A., et al.: Solving a Realistic FAP Using GRASP and Grid Computing. In: Advances in Grid and Pervasive Computing. LNCS, vol. 5529, pp. 79–90. Springer, Heidelberg (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chaves-González, J.M., Vega-Rodríguez, M.A., Gómez-Pulido, J.A., Sánchez-Pérez, J.M. (2010). Swarm Intelligence, Scatter Search and Genetic Algorithm to Tackle a Realistic Frequency Assignment Problem. In: de Leon F. de Carvalho, A.P., Rodríguez-González, S., De Paz Santana, J.F., Rodríguez, J.M.C. (eds) Distributed Computing and Artificial Intelligence. Advances in Intelligent and Soft Computing, vol 79. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14883-5_57
Download citation
DOI: https://doi.org/10.1007/978-3-642-14883-5_57
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14882-8
Online ISBN: 978-3-642-14883-5
eBook Packages: EngineeringEngineering (R0)