research-article

Metaheuristics for solving a real-world frequency assignment problem in GSM networks

Authors:

Francisco Luna,

César Estébanez,

Coromoto León,

José M. Chaves-González,

Miguel A. Vega-Rodríguez,

Antonio J. Nebro,

José M. Valls,

Juan A. Gómez-PulidoAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 1579 - 1586

https://doi.org/10.1145/1389095.1389396

Published: 12 July 2008 Publication History

Abstract

The Frequency Assignment Problem (FAP) is one of the key issues in the design of GSM networks (Global System for Mobile communications), and will remain important in the foreseeable future. There are many versions of FAP, most of them benchmarking-like problems. We use a formulation of FAP, developed in published work, that focuses on aspects which are relevant for real-world GSM networks. In this paper, we have designed, adapted, and evaluated several types of metaheuristic for different time ranges. After a detailed statistical study, results indicate that these metaheuristics are very appropriate for this FAP. New interference results have been obtained, that significantly improve those published in previous research.

References

[1]

K. I. Aardal, S. P. M. van Hoesen, A. M. C. A. Koster, C. Mannino, and A. Sassano. Models and solution techniques for frequency assignment problems. Annals of Operations Research, 153(1):79 -- 129, 2007.

[2]

S. Baluja. Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning. 1994.

[3]

C. Blum and M. Dorigo. The hyper-cube framework for ant colony optimization. IEEE Trans. on System, Man, and Cybernetics -- Part B, 34(2):1161--1172, 2004.

Digital Library

[4]

C. Blum and A. Roli. Metaheuristics in combinatorial optimization: Overview and conceptual comparison. ACM Computing Surveys, 35(3):268--308, 2003.

Digital Library

[5]

E.K. Burke and G. Kendall. Search methodologies: introductory tutorials in optimization and decision support techniques. Springer, 2005.

[6]

J. Demšar. Statistical comparison of classifiers over multiple data sets. Journal of Machine Learning Research, 7:1 -- 30, 2006.

Digital Library

[7]

A. Eisenblätter. Frequency Assignment in GSM Networks: Models, Heuristics, and Lower Bounds. PhD thesis, Technische Universität Berlin, 2001.

[8]

FAP Web. http://fap.zib.de/.

[9]

A. Furuskar, J. Naslund, and H. Olofsson. EDGE -- enhanced data rates for GSM and TDMA/136 evolution. Ericsson Review, (1), 1999.

[10]

F. W. Glover and G. A. Kochenberger. Handbook of Metaheuristics (International Series in Operations Research & Management Science). Springer, January 2003.

[11]

H. Granbohm and J. Wiklund. GPRS -- general packet radio service. Ericsson Review, (1), 1999.

[12]

W. K. Hale. Frequency assignment: Theory and applications. Proceedings of the IEEE, 68(12):1497 -- 1514, 1980.

[13]

Y. Hochberg and A. C. Tamhane. Multiple Comparison Procedures. Wiley, 1987.

Digital Library

[14]

A. M. J. Kuurne. On GSM mobile measurement based interference matrix generation. In IEEE 55th Vehicular Technology Conference, VTC Spring 2002, pages 1965 -- 1969, 2002.

[15]

M. Laguna, K. Price Hossell, and R. Marti. Scatter Search: Methodology and Implementation in C. Kluwer Academic Publishers, Norwell, MA, USA, 2002.

Digital Library

[16]

F. Luna, C. Blum, E. Alba, and A. J. Nebro. ACO vs EAs for solving a real-world frequency assignment problem in GSM networks. In Genetic and Evolutionary Computation Conference (GECCO 2007), pages 94 -- 101, 2007.

Digital Library

[17]

R. Martí, M. Laguna, and F. Glover. Principles of scatter search. European Journal of Operational Research, 169(2):359--372, 2006.

[18]

A. R. Mishra. Fundamentals of Cellular Network Planning and Optimisation: 2G/2.5G/3G. Evolution to 4G, chapter Radio Network Planning and Optimisation, pages 21 -- 54. Wiley, 2004.

[19]

M. Mouly and M. B. Paulet. The GSM System for Mobile Communications. Mouly et Paulet, Palaiseau, 1992.

Digital Library

[20]

W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. Numerical Recipes in C: The Art of Scientific Computing. Cambridge University Press, 1992.

Digital Library

[21]

J. Rapeli. UMTS: Targets, system concept, and standardization in a global framework. IEEE Personal Communications, 2(1):30 -- 37, 1995.

[22]

D. J. Sheskin. Handbook of Parametric and Nonparametric Statistical Procedures. CRC Press, 2003.

[23]

M. K. Simon and M-S. Alouini. Digital Communication over Fading Channels: A Unified Approach to Performance Analysis. Wiley, 2005.

[24]

B. H. Walke. Mobile Radio Networks: Networking, protocols and traffic performance. Wiley, 2002.

Digital Library

Cited By

Laidoui FBessedik MBenbouzid-Si Tayeb F(2023)A game-theoretical constructive approach for the multi-objective frequency assignment problemApplied Soft Computing10.1016/j.asoc.2023.110444144:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.asoc.2023.110444
Kiouche ABessedik MBenbouzid-SiTayeb FKeddar M(2020)An efficient hybrid multi-objective memetic algorithm for the frequency assignment problemEngineering Applications of Artificial Intelligence10.1016/j.engappai.2019.10326587(103265)Online publication date: Jan-2020
https://doi.org/10.1016/j.engappai.2019.103265
Segura CAguirre APeña SRionda S(2016)The Importance of Proper Diversity Management in Evolutionary Algorithms for Combinatorial OptimizationNEO 201510.1007/978-3-319-44003-3_6(121-148)Online publication date: 24-Aug-2016
https://doi.org/10.1007/978-3-319-44003-3_6
Show More Cited By

Index Terms

Metaheuristics for solving a real-world frequency assignment problem in GSM networks

Recommendations

Optimization algorithms for large-scale real-world instances of the frequency assignment problem
Recent progress in natural computation and knowledge discovery

Nowadays, mobile communications are experiencing a strong growth, being more and more indispensable. One of the key issues in the design of mobile networks is the frequency assignment problem (FAP). This problem is crucial at present and will remain ...
Metaheuristics for large-scale instances of the linear ordering problem

ILS and GDA metaheuristics for the linear ordering problem are introduced.They are able to tackle large instances in line with real applications.Introduced methods are the first of their kind ever applied to large-sized instances.All best known ...
Analysis of Parameter Settings for Differential Evolution Algorithm to Solve a Real-World Frequency Assignment Problem in GSM Networks
ADVCOMP '08: Proceedings of the 2008 The Second International Conference on Advanced Engineering Computing and Applications in Sciences

Frequency assignment is a very important real-world problem, specially in GSM networks. These networks are very used in the telecommunication area (by mid 2006 GSM services were used by more than 1.8 billion subscribers across 210 countries, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
344
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Laidoui FBessedik MBenbouzid-Si Tayeb F(2023)A game-theoretical constructive approach for the multi-objective frequency assignment problemApplied Soft Computing10.1016/j.asoc.2023.110444144:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.asoc.2023.110444
Kiouche ABessedik MBenbouzid-SiTayeb FKeddar M(2020)An efficient hybrid multi-objective memetic algorithm for the frequency assignment problemEngineering Applications of Artificial Intelligence10.1016/j.engappai.2019.10326587(103265)Online publication date: Jan-2020
https://doi.org/10.1016/j.engappai.2019.103265
Segura CAguirre APeña SRionda S(2016)The Importance of Proper Diversity Management in Evolutionary Algorithms for Combinatorial OptimizationNEO 201510.1007/978-3-319-44003-3_6(121-148)Online publication date: 24-Aug-2016
https://doi.org/10.1007/978-3-319-44003-3_6
M. Chaves-Gonzalez JA. Vega-Rodríguez M(2014)Evolutionary team based on different metaheuristics for solving a real-world problem in the telecommunication domainEngineering Computations10.1108/EC-05-2013-014331:7(1550-1581)Online publication date: 30-Sep-2014
https://doi.org/10.1108/EC-05-2013-0143
Mishra BDehuri SWang G(2013)A State-of-the-Art Review of Artificial Bee Colony in the Optimization of Single and Multiple CriteriaInternational Journal of Applied Metaheuristic Computing10.4018/ijamc.20131001024:4(23-45)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.4018/ijamc.2013100102
Segura CSegredo ELeón C(2013)Analysing the Robustness of Multiobjectivisation Approaches Applied to Large Scale Optimisation ProblemsEVOLVE- A Bridge between Probability, Set Oriented Numerics and Evolutionary Computation10.1007/978-3-642-32726-1_11(365-391)Online publication date: 2013
https://doi.org/10.1007/978-3-642-32726-1_11
da Silva Maximiano MVega‐Rodríguez MGómez‐Pulido JSánchez‐Pérez J(2012)Multiobjective metaheuristics for frequency assignment problem in mobile networks with large‐scale real‐world instancesEngineering Computations10.1108/0264440121120603429:2(144-172)Online publication date: 24-Feb-2012
https://doi.org/10.1108/02644401211206034
da Silva Maximiano MVega-Rodríguez MGómez-Pulido JSánchez-Pérez J(2012)A new Multiobjective Artificial Bee Colony algorithm to solve a real-world frequency assignment problemNeural Computing and Applications10.1007/s00521-012-1046-722:7-8(1447-1459)Online publication date: 10-Jul-2012
https://doi.org/10.1007/s00521-012-1046-7
Jianxin Dai Ming Chen Zhiliang Huang (2011)A bi-objective multi-swarm particle swarm optimization algorithm for the frequency assignment problem2011 IEEE 13th International Conference on Communication Technology10.1109/ICCT.2011.6157863(207-211)Online publication date: Sep-2011
https://doi.org/10.1109/ICCT.2011.6157863
da Silva Maximiano MVega-Rodriguez MGomez-Pulido JSanchez-Perez J(2011)COMPARATIVE ANALYSIS OF A HYBRID DE ALGORITHM WITH THE VNS ALGORITHM AND ITS VARIATION SVNS TO SOLVE A REAL-WORLD FREQUENCY ASSIGNMENT PROBLEMApplied Artificial Intelligence10.1080/08839514.2011.55310725:3(217-234)Online publication date: 1-Mar-2011
https://dl.acm.org/doi/10.1080/08839514.2011.553107
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents