More Web Proxy on the site http://driver.im/

Article

Using omnidirectional BTS and different evolutionary approaches to solve the RND Problem

Authors:

Miguel A. Vega-Rodríguez,

Juan A. Gómez-Pulido,

David Vega-Pérez,

Silvio Priem-Mendes,

Guillermo MolinaAuthors Info & Claims

EUROCAST'07: Proceedings of the 11th international conference on Computer aided systems theory

Pages 853 - 860

Published: 12 February 2007 Publication History

Abstract

RND (Radio Network Design) is an important problem in mobile telecommunications (for example in mobile/cellular telephony), being also relevant in the rising area of sensor networks. This problem consists in covering a certain geographical area by using the smallest number of radio antennas achieving the biggest cover rate. To date, several radio antenna models have been used: square coverage antennas, omnidirectional antennas that cover a circular area, etc. In this work we use omnidirectional antennas. On the other hand, RND is an NP-hard problem; therefore its solution by means of evolutionary algorithms is appropriate. In this work we study different evolutionary approaches to tackle this problem. PBIL (Population-Based Incremental Learning) is based on genetic algorithms and competitive learning (typical in neural networks). DE (Differential Evolution) is a very simple population-based stochastic function minimizer used in a wide range of optimization problems, including multi-objective optimization. SA (Simulated Annealing) is a classic trajectory descent optimization technique. Finally, CHC is a particular class of evolutionary algorithm which does not use mutation and relies instead on incest prevention and disruptive crossover. Due to the complexity of such a large analysis including so many techniques, we have used not only sequential algorithms, but also grid computing with BOINC in order to execute thousands of experiments in only several days using around 100 computers.

References

[1]

Calégari, P., Guidec, F., Kuonen, P., Kobler, D.: Parallel Island-Based Genetic Algorithm for Radio Network Design. Journal of Parallel and Distributed Computing 47(1), 86-90 (1997).

Digital Library

[2]

Calégari, P., Guidec, F., Kuonen, P., Nielsen, F.: Combinatorial Optimization Algorithms for Radio Network Planning. Theoretical Computer Science 263(1), 235-265 (2001).

Digital Library

[3]

Alba, E.: Evolutionary Algorithms for Optimal Placement of Antennae in Radio Network Design. NIDISC 2004 Sixth International Workshop on Nature Inspired Distributed Computing, IEEE IPDPS, Santa Fe, USA, pp. 168-175 (April 2004).

[4]

OPLINK: (May 2007), http://oplink.lcc.uma.es/problems/rnd.html

[5]

Baluja, S.: Population-based Incremental Learning: A Method for Integrating Genetic Search based Function Optimization and Competitive Learning. Technical Report CMU-CS-94-163, Carnegie Mellon University (June 1994).

Digital Library

[6]

Baluja, S., Caruana, R.: Removing the Genetics from the Standard Genetic Algorithm. 12th Int. Conference on Machine Learning, San Mateo, CA, USA, pp. 38-46 (May 1995).

[7]

Price, K., Storn, R.: Differential Evolution - A Simple Evolution Strategy for Fast Optimization. Dr. Dobb's Journal 22(4), 18-24 (1997).

[8]

Price, K., Storn, R.: DE website (May 2007), http://www.ICSI.Berkeley.edu/~storn/ code.html

[9]

Abbass, H.A., Sarker, R.: The Pareto Differential Evolution Algorithm. Int. Journal on Artificial Intelligence Tools 11(4), 531-552 (2002).

[10]

Mendes, S., Gómez, J.A., Vega, M.A., Sánchez, J.M.: The Optimal Number and Locations of Base Station Transmitters in a Radio Network. In: 3rd Int. Workshop on Mathematical Techniques and Problems in Telecommunications, Leiria, Portugal, pp.17-20 (September 2006).

[11]

Kirkpatrick, S., Gelatt, C.D., Vecchi, M.P.: Optimization by Simulated Annealing. Science 220(4598), 671-680 (1983).

[12]

Cerny, V.: A Thermodynamical Approach to the Travelling Salesman Problem: an Efficient Simulation Algorithm. Journal of Optimization Theory and Applications 45, 41- 51 (1985).

Digital Library

[13]

Eshelman, L.J.: The CHC Adaptive Search Algorithm: How to Have Safe Search when Engaging in Nontraditional Genetic Recombination. Foundations of Genetic Algorithms, pp. 265-283. Morgan Kaufmann, San Francisco (1991).

[14]

Eshelman, L.J., Schaffer, J.D.: Preventing Premature Convergence in Genetic Algorithms by Preventing Incest. 4th Int. Conf. on Genetic Algorithms, CA, USA, pp. 115-122 (1991).

[15]

BOINC: (May 2007), http://boinc.berkeley.edu

[16]

Anderson, D.P.: BOINC: A System for Public-Resource Computing and Storage. 5th IEEE/ACM Int. Workshop on Grid Computing, Pittsburgh, USA, pp. 365-372 (November 2004).

Digital Library

[17]

Alba, E., Almeida, F., Blesa, M., Cotta, C., Díaz, M., Dorta, I., Gabarró, J., León, C., Luque, G., Petit, J., Rodríguez, C., Rojas, A., Xhafa, F.: Efficient Parallel LAN/WAN Algorithms for Optimization: The MALLBA Project. Parallel Computing 32(5-6), 415- 440 (2006).

Digital Library

[18]

Lampinen, J., Zelinka, I.: On Stagnation of the Differential Evolution Algorithm. 6th International Mendel Conference on Soft Computing, MENDEL 2000, Brno, Czech Republic, pp. 76-83 (June 2000).

Cited By

Dahi ZMezioud CDraa A(2016)On the efficiency of the binary flower pollination algorithmApplied Soft Computing10.1016/j.asoc.2016.05.05147:C(395-414)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.asoc.2016.05.051
Mendes SMolina GVega-Rodríguez MGómez-Pulido JSáez YMiranda GSegura CAlba EIsasi PLeón CSánchez-Pérez J(2009)Benchmarking a wide spectrum of metaheuristic techniques for the radio network design problemIEEE Transactions on Evolutionary Computation10.1109/TEVC.2009.202344813:5(1133-1150)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1109/TEVC.2009.2023448

Recommendations

Evaluation of Different Metaheuristics Solving the RND Problem
Proceedings of the 2007 EvoWorkshops 2007 on EvoCoMnet, EvoFIN, EvoIASP,EvoINTERACTION, EvoMUSART, EvoSTOC and EvoTransLog: Applications of Evolutionary Computing

RND (Radio Network Design) is a Telecommunication problem consisting in covering a certain geographical area by using the smallest number of radio antennas achieving the biggest cover rate. This is an important problem, for example, in mobile/cellular ...
Parameter tuning of PBIL and CHC evolutionary algorithms applied to solve the Root Identification Problem

Evolutionary algorithms are among the most successful approaches for solving a number of problems where systematic searches in huge domains must be performed. One problem of practical interest that falls into this category is known as The Root ...
Modeling the performance of evolutionary algorithms on the root identification problem: A case study with pbil and chc algorithms

The availability of a model to measure the performance of evolutionary algorithms is very important, especially when these algorithms are applied to solve problems with high computational requirements. That model would compute an index of the quality of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EUROCAST'07: Proceedings of the 11th international conference on Computer aided systems theory

February 2007

1233 pages

ISBN:3540758666

Editors:
Roberto Moreno Díaz
Universidad de Las Palmas de Gran Canaria, Instituto Universitario de Ciencias y Tecnologías Cibernéticas, Las Palmas de Gran Canaria, Spain
,
Franz Pichler
Johannes Kepler University, Institute of Systems Science, Linz, Austria
,
Alexis Quesada Arencibi
Universidad de Las Palmas de Gran Canaria, Instituto Universitario de Ciencias y Tecnologías Cibernéticas, Las Palmas de Gran Canaria, Spain

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 12 February 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
2
Total Downloads

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

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dahi ZMezioud CDraa A(2016)On the efficiency of the binary flower pollination algorithmApplied Soft Computing10.1016/j.asoc.2016.05.05147:C(395-414)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1016/j.asoc.2016.05.051
Mendes SMolina GVega-Rodríguez MGómez-Pulido JSáez YMiranda GSegura CAlba EIsasi PLeón CSánchez-Pérez J(2009)Benchmarking a wide spectrum of metaheuristic techniques for the radio network design problemIEEE Transactions on Evolutionary Computation10.1109/TEVC.2009.202344813:5(1133-1150)Online publication date: 1-Oct-2009
https://dl.acm.org/doi/10.1109/TEVC.2009.2023448

View Options

View options

Media

Figures

Other

Tables

View Table of Contents