nach oben

Soft Computing

Erschienen in:

01.06.2013 | Methodologies and Application

Scalability and robustness of parallel hyperheuristics applied to a multiobjectivised frequency assignment problem

verfasst von: Carlos Segura, Eduardo Segredo, Coromoto León

Erschienen in: Soft Computing | Ausgabe 6/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Frequency Assignment Problem (fap) is one of the key issues in the design of Global System for Mobile Communications (gsm) networks. The formulation of the fap used here focuses on aspects that are relevant to real gsm networks. In this paper, we adapt a parallel model to tackle a multiobjectivised version of the fap. It is a hybrid model which combines an island-based model and a hyperheuristic. The main aim of this paper is to design a strategy that facilitates the application of the current best-behaved algorithm. Specifically, our goal is to decrease the user effort required to set its parameters. At the same time, the usage of such an algorithm in parallel environments was enabled. As a result, the time required to attain high-quality solutions was decreased. We also conduct a robustness analysis of this parallel model. In this analysis we study the relationship between the migration stage of the parallel model and the quality of the resulting solutions. In addition, we also carry out a scalability study of the parallel model. In this case, we analyse the impact that the migration stage has on the scalability of the entire parallel model. Computational results with several real network instances have validated our proposed approach. The best-known frequency plans for two real-world network instances are improved with this strategy.

Vorheriger Artikel Service oriented evolutionary algorithms

Nächster Artikel Code reordering using local random extraction and insertion (LREI) operator for GPGPU-based track-before-detect systems

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Aardal KI, Hoesel SPMV, Koster AMCA, Mannino C, Sassano A (2007) Models and solution techniques for frequency assignment problems. Ann Oper Res 153(1):79–129MathSciNetMATHCrossRef

Abbass HA, Deb K (2003) Searching under multi-evolutionary pressures. In: Proceedings of the fourth conference on evolutionary multi-criterion optimization, Springer, Berlin, pp 391–404

Amaldi E, Capone A, Malucelli F, Mannino C (2006) Optimization problems and models for planning cellular networks. In: Resende MGC, Pardalos PM (eds) Handbook of optimization in telecommunication, Springer, Berlin, pp 917–939

Brockhoff D, Friedrich T, Hebbinghaus N, Klein C, Neumann F, Zitzler E (2007) Do additional objectives make a problem harder? In: Proceedings of the 9th annual conference on genetic and evolutionary computation, ACM, New York, NY, GECCO ’07, pp 765–772

Bui L, Abbass H, Branke J (2005) Multiobjective optimization for dynamic environments. In: Proceedings of the 2005 IEEE congress on evolutionary computation, CEC 2005, vol 3, pp 2349–2356

Burke EK, Kendall G, Newall J, Hart E, Ross P, Schulenburg S (2003) Handbook of meta-heuristics. Hyper-heuristics: an emerging direction in modern search technology. Kluwer, Dordrecht

Burke EK, Hyde M, Kendall G, Ochoa G, Ozcan E, Woodward JR (2010) A classification of hyper-heuristics approaches. In: Gendreau M, Potvin JY (eds) Handbook of metaheuristics, international series in operations research & management science, vol 57, 2nd edn, chap 15, Springer, Berlin, pp 449–468

Colombo G, Allen S (2007) Problem decomposition for minimum interference frequency assignment. In: Proceedings of the 2007 IEEE congress on evolutionary computation, CEC 2007, pp 3492–3499

Cowling P, Kendall G, Soubeiga E (2001a) A parameter-free hyperheuristic for scheduling a sales summit. In: Proceedings of 4th metahuristics international conference (MIC 2001), Porto, Portugal, pp 127–131

Cowling PI, Kendall G, Soubeiga E (2001b) A hyperheuristic approach to scheduling a sales summit. In: Selected papers from the third international conference on practice and theory of automated timetabling III, Springer, London, UK, PATAT ’00, pp 176–190

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6:182–197CrossRef

Demšar J (2006) Statistical comparison of classifiers over multiple data sets. J Mach Learn Res 7:1–30MathSciNetMATH

Eiben AE, Smith JE (2008) Introduction to evolutionary computing (natural computing series). Springer, Berlin

Hale W (1980) Frequency assignment: theory and applications. Proc IEEE 68(12):1497–1514CrossRef

Handl J, Lovell SC, Knowles J (2008) Multiobjectivization by decomposition of scalar cost functions. In: Proceedings of the 10th international conference on parallel problem solving from nature: PPSN X, Springer, Berlin, pp 31–40

Hoos H, Stützle T (2005) Stochastic local search: foundations and applications. The Morgan Kaufmann Series in Artificial Intelligence, Morgan Kaufmann Publishers, Los Altos

Ishibuchi H, Hitotsuyanagi Y, Nojima Y (2007) An empirical study on the specification of the local search application probability in multiobjective memetic algorithms. In: Proceedings of the 2007 IEEE Congress on Evolutionary Computation, CEC 2007, pp 2788–2795

Knowles JD, Watson RA, Corne D (2001) Reducing local optima in single-objective problems by multi-objectivization. In: Proceedings of the first international conference on evolutionary multi-criterion optimization. Springer, London, pp 269–283

Kuurne AMJ (2002) On GSM mobile measurement based interference matrix generation. In: IEEE 55th vehicular technology conference, VTC Spring 2002, pp 1965–1969

Le MN, Ong YS, Jin Y, Sendhoff B (2009) Lamarckian memetic algorithms: local optimum and connectivity structure analysis. Memet Comput 1(3):175–190CrossRef

León C, Miranda G, Segura C (2009) METCO: a parallel plugin-based framework for multi-objective optimization. Int J Artif Intell Tools 18(4):569–588CrossRef

Luna F, Blum C, Alba E, Nebro A (2007) ACO vs EAs for solving a real-world frequency assignment problem in GSM networks. In: Proceedings of the 2007 genetic and evolutionary computation conference, pp 94–101

Luna F, Nebro A, Alba E, Durillo J (2008) Solving large-scale real-world telecommunication problems using a grid-based genetic algorithm. Eng Optim 40(11):1067–1084CrossRef

Luna F, Estébanez C, León C, Chaves-González J, Nebro A, Aler R, Segura C, Vega-Rodríguez M, Alba E, Valls J, Miranda G, Gómez-Pulido J (2011) Optimization algorithms for large-scale real-world instances of the frequency assignment problem. Soft Comput 15(5):975–990CrossRef

Mannino C, Sassano A (2003) An enumerative algorithm for the frequency assignment problem. Discrete Appl Math 129(1):155–169MathSciNetMATHCrossRef

Mouly M, Paulet MB (1992) The GSM system for mobile communications. Mouly et Paulet, Palaiseau

Mouret JB (2011) Novelty-based multiobjectivization. In: Doncieux S, BredFche N, Mouret JB (eds) New horizons in evolutionary robotics, studies in computational intelligence, vol 341. Springer, Berlin, pp 139–154

Özcan E, Basaran C (2009) A case study of memetic algorithms for constraint optimization. Soft Comput Fusion Found Methodol Appl 13(8):871–882

Press WH, Flannery BP, Teukolsky SA, Vetterling WT (1992) Numerical recipes in C: the art of scientific computing. Cambridge University Press, Cambridge

Segredo E, Segura C, León C (2011) A multiobjectivised memetic algorithm for the frequency assignment problem. In: Proceedings of the 2011 IEEE congress on evolutionary computation, CEC 2011. pp 1132–1139

Segura C, Miranda G, León C (2010) Parallel hyperheuristics for the frequency assignment problem. Memet Comput 3(1):1–17

Segura C, Segredo E, González Y, León C (2011a) Multiobjectivisation of the antenna positioning problem. In: International symposium on distributed computing and artificial intelligence, advances in intelligent and soft computing, vol 91. Springer, Berlin, pp 319–327

Segura C, Segredo E, León C (2011b) Parallel island-based multiobjectivised memetic algorithms for a 2D packing problem. In: Proceedings of the 13th annual conference on Genetic and evolutionary computation, ACM, New York, NY, USA, GECCO ’11, pp 1611–1618

Simon MK, Alouini MS (2005) Digital communication over fading channels: a unified approach to performance analysis. Wiley, Hoboken

Talbi EG (2002) A taxonomy of hybrid metaheuristics. J Heuristics 8(5):541–564CrossRef

Toffolo A, Benini E (2003) Genetic diversity as an objective in multi-objective evolutionary algorithms. Evol Comput 11:151–167CrossRef

Veldhuizen DAV, Zydallis JB, Lamont GB (2003) Considerations in engineering parallel multiobjective evolutionary algorithms. IEEE Trans Evol Comput 7(2):144–173CrossRef

Vink T, Izzo D (2007) Learning the best combination of solvers in a distributed global optimization environment. In: Proceedings of Advances in Global Optimization: Methods and Applications (AGO), Mykonos, Greece, pp 13–17

Walke BH (2002) Mobile radio networks: networking, protocols and traffic performance. Wiley, Hoboken

Yoshino J, Ohtomo I (2005) Study on efficient channel assignment method using the genetic algorithm for mobile communication systems. Soft Comput Fusion Found Methodol Appl 9:143–148

Titel: Scalability and robustness of parallel hyperheuristics applied to a multiobjectivised frequency assignment problem
verfasst von: Carlos Segura
Eduardo Segredo
Coromoto León
Publikationsdatum: 01.06.2013
Verlag: Springer-Verlag
Erschienen in: Soft Computing / Ausgabe 6/2013
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-012-0945-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 6/2013

Code reordering using local random extraction and insertion (LREI) operator for GPGPU-based track-before-detect systems

Population-based optimization of cytostatic/cytotoxic combination cancer chemotherapy

Computational results for an automatically tuned CMA-ES with increasing population size on the CEC’05 benchmark set

Special issue on evolutionary computing and complex systems

Community detection in complex networks using extended compact genetic algorithm

GAssist vs. BioHEL: critical assessment of two paradigms of genetics-based machine learning