MORND: Multiobjective Radio Network Design

 

 MO RND AIS

 

Coordinator: Yago Saez 

Email: yago.saez@uc3m.es

Introduction. The AIS meta-heuristic.

This is a proposal of multi-objective formulation for the RND problem. Although it has been tackled with a specific meta-heuristic, this formulation can be useful as model for other approaches that use different evolutionary algorithms. Artificial Immune Systems (AIS) present in their elementary structure the main characteristics required to solve Multiobjective Optimization problems: exploitation, exploration, parallelism, elitism, memory, diversity, dynamic repertoire, mutation and cloning proportional to the affinity. The aim of this work is to explore an AIS, based on the Clonal Selection principle for the solution of the Network Radio Design (RND) Multiobjective Optimization (MO) problem. The proposed approach uses Pareto dominance concept and feasibility to identify antibodies (solutions) that must be cloned, it also allows adding improvements as constraints treatement. The algorithm has been compared with NSGA-II and SPEA2, two state-of-art algorithms in MO. The results obtained by the developed algorithm are competitive in comparison to the state-of-the-art MO algorithms. 


Instances.

The instance used has been the Malaga instance. For more information please click HERE.

Although the definition of the Malaga instance has been used, in this case, two different objectives have been optimized:

- Number of antennae (the lower, the better).

- Percentage of coverture (the higher, the better).

The aim of this system is to offer the carrier a complete set of optimal solutions located (if possible) distributed along the Pareto front.

 


 References.

  1. Alba, E. (2004). Evolutionary Algorithms for Optimal Placement of Antennae in Radio Network Design. In: IEEE NIDISC (Ed)), 168-174. IEEE, Santa Fe, New Mexico, USA.
  2. Alba, E. and F. Chicano (2005). On the behaviour of parallel genetic algorithms for optimal placement of antennae in telecommunications. International Journal of Foundations of Computer Science, 16, 86-90.
  3. Calegari, P., F. Guidec and P. Kuonen (2001). Combinatorial Optimization Algorithms for Radio Network Planning. Journal of Theoretical Computer Science, 263, 235-265.
  4. Calegari, P., et al. (1997). Parallel island-based genetic algorithm for radio network design. Journal of Parallel and Distributed Computing, 47, 86-90.
  5. Khuri, S. and T. Chiu (1997). Heuristic algorithms for the terminal assignment problem. In: ACM Symposium on Applied Computing (Ed)), 245-251.
  6. "Benchmarking a Wide Spectrum of Meta-Heuristic Techniques for the Radio Network Design Problem". Sílvio P. Mendes, Guillermo Molina, Miguel A. Vega-Rodríguez, Juan A. Gómez-Pulido, Yago Sáez, Gara Miranda, Carlos Segura, Enrique Alba, Pedro Isasi, Coromoto León, Juan M. Sánchez-Pérez. IEEE Transactions on Evolutionary Computation, IEEE, 2009, pag:1-18. ISSN:1089-778X.
  7. "The Radio Network Design Optimization Problem. Benchmarking and State-of-the-Art Solvers", in: "Biologically-Inspired Optimisation Methods, SCI 210" . Sílvio P. Mendes, Juan A. Gómez-Pulido, Miguel A. Vega-Rodríguez, Juan M. Sánchez-Pérez, Yago Sáez, Pedro Isasi. Springer-Verlag, 2009, pag:219-260. ISBN:978-3-642-01261-7.
  8. "Evaluation of Different Metaheuristics Solving the RND Problem", in: "Applications of Evolutionary Computing" . Miguel A. Vega-Rodríguez, Juan A. Gómez-Pulido, Enrique Alba, David Vega-Pérez, Silvio Priem-Mendes and Guillermo Molina. M. Giacobini et al. (Eds.), Springer-Verlag Berlin Heidelberg, 2007, pag:101-110. ISBN:978-3-540-71804-8.
  9. "Omni-directional RND Optimisation using Differential Evolution: In-depth Analysis via High Throughput Computing", in: "New Trends in Artificial Intelligence" . Silvio Mendes, Patricio Domingues, David Pereira, Renato Vale, Juan A. Gomez-Pulido, Luis Moura Silva, Miguel A. Vega-Rodríguez and Juan M. Sánchez-Pérez. J. Neves, M.F. Santos, J.M. Machado (Eds). APPIA, Associacao Portuguesa para a Inteligencia Artificial, 2007, pag:262-275. ISBN:978-98-995-6180-9.
  10. Using Omnidirectional BTS and Different Evolutionary Approaches to Solve the RND Problem", in: "Computer Systems Aided Theory" . Miguel A. Vega-Rodríguez, Juan A. Gómez-Pulido, Enrique Alba, David Vega-Pérez, Silvio Priem-Mendes, Guillermo Molina. R. Moreno-Díaz et al. (Eds.), Springer-Verlag Berlin Heidelberg, 2007, pag:853-860. ISBN:978-3-540-75866-2.