Facultad Politécnica - Universidad Nacional de Asunción

Aranduka Vol. 1, nº 2 (Dic. 2010) 

- 40 -

con los hijos. Esto implica que el NSGA-II 

presenta una alta presión elitista en comparación 

al SPEA. Esta alta presión elitista hace que el 

NSGA-II tenga un estancamiento prematuro 

generando una lenta evolución.  Para confirmar 

la hipótesis anterior es necesario realizar pruebas 

de mayor longitud temporal de forma a detectar 

el tiempo de estancamiento de ambos algoritmos 

evolutivos.

4. Conclusiones y Trabajos Futuros

Este trabajo propone un novedoso enfoque 

para la protección del enrutamiento multicast 

y asignación de longitudes de onda (MPRWA) 

sobre redes ópticas. Este enfoque es denominado 

protección multicast basado en grafo de doble-

conexión (2-connected graph) el cual es un árbol 

multicast con enlaces primario y un conjunto de 

enlaces secundarios extras agregados al primario. 

Ambos, enlaces primarios y secundarios, 

conforman el grafo de doble conexión. Los 

MOEAs implementados, el SPEA y el NSGAII, 

fueron comparados sobre varias instancias de 

pruebas las cuales indican que SPEA presenta 

un mejor desempeño en comparación a los 

resultados del NSGA-II.

Como trabajo futuro, los autores proponen varias 

líneas de investigación: (1) extender las pruebas 

experimentales sobre otras topologías de redes 

considerando otras heurísticas, (2) incluir 

niveles de protección como calidad de servicio, e 

(3)  iniciar el estudio sobre la problemática de la 

protección multicast en redes ópticas grooming.

Referencias

[1]COELLO, C.; LAMONT, G.; VAN 

VELDHUIZEN, D. 2007. Evolutionary 

Algorithms for Solving Multi-Objective 

Problems, Genetic and Evolutionary 

Computation Series, Editores: David 

E. Golberg y John R. Koza. Segunda 

Edición, Springer.

[2]DEB, K.; GOEL, T. 2002. A Fast and 

elitist multiobjective genetic algorithm: 

NSGA-II. IEEE Trans. Evolutionary 

Computation, 6(2): p. 182-197.

[3]FEI, A.; CUI, J.; GERLA, M.; CAVENDISH, 

D. 2001. A Dual-tree Scheme for Fault-

tolerant Multicast. In Proceeding of IEEE 

ICC.

[4]KHULLER, S.; THURIMELLA, R. 1993. 

Approximation Algorithms for Graph 

Augmentation. Journal of Algorithm, 

14(2): p. 214-225.

[5]LUGO, R.; PINTO ROA, D. P. 2010. 

Protección Multicast Multi-objetivo en 

Redes Ópticas. Un enfoque basado en 

Sub-Grafos de Doble-Conección (primera 

parte). Revista Aranduka vol. 1. Facultad 

Politécnica. Universidad Nacional de 

Asunción.

[6]SOMANI, A.K.  2005.  Survivability and 

Traffic Grooming in WDM Optical.  

Networks, Cambridge University Press.  

ISBN: 978-0-511-13754-9.

[7]RAVI, R. 1992. Approximation Algorithms 

for Steiner Augmentations for Two-

connectivity. Reporte Técnico, TRCS-92-

21, Brown University.

[8]VAN VELDHUIZEN, D. A.; LAMONT, 

G. B 1998. Multiobjective Evolutionary 

Algorithm Research: A History and 

Analysis. Technical Report TR-98-03, 

Dept. Elec. Comput. Eng., Graduate 

School of Eng., Air Force Inst. Technol., 

Wright-Patterson, AFB, OH. 

[9]ZHANG, Y.; SIDHU, D. 2004. A Multicast 

Protection Algorithm for Optical WDM 

Networks. In Proceeding of IEEE ICCCN.

[10]ZITZLER, E.; THIELE, L. 1999. 

Multiobjective Evolutionary Algorithms: 

A comparative Case Study and the 

Strength Pareto Approach. IEEE Trans. 

Evolutionary Computation, 3(4): P. 257-

271.