Optimización multiobjetivo en redes ópticas con transmisión Multicast, utilizando algoritmos evolutivos y lógica difusa

Luis Tovar^*, Margarita Coronell^**, Yezid Donoso^***

Resumen

En el presente artículo se desarrolla un modelo analítico difuso, el cual resuelve un problema multiobjetivo en transmisión multicast con árboles estáticos sobre redes GMPLS. Para ello, se utilizó como base el modelo propuesto en Donoso [4].

El problema multiobjetivo planteado se soluciona mediante metaheurística con algoritmos evolutivos, específicamente el SPEA2, resolviendo un problema NP-Hard en tiempo polinomial. Adicionalmente, se implementa un algoritmo evolutivo difuso, basado en el algoritmo evolutivo SPEA2, para resolver el modelo desarrollado.

Por último, se analiza el comportamiento del algoritmo propuesto (FSPEA2) frente al algoritmo original (SPEA2) y se presentan las respectivas conclusiones.

Palabras claves: Algoritmos evolutivos, Lógica difusa, Optimización multiobjetivo, Redes de computadores.

Abstract

In this paper, we develop a fuzzy analytical model, which solves a multiobjective problem in multicast transmission with static trees over GMPLS networks. A model proponed by Donoso [4] was used.

The multiobjective problem is solved through metaheuristic wit h evolutionary algorithms, in this case SPEA2 solving a NP-Hard problem in polynomial time. Additionally, a Fuzzy Evolutionary Algorithm based on SPEA2 is implemented.

Finally, the comparison between FSPEA2 and SPEA2 is realized and we are giving some conclusions.

Key words: Evolutionary algorithm, Fuzzy Logic, Multiobjective Optimization, Computer Networks.

1. INTRODUCCIÓN

Internet y el Protocolo de Interred (IP) se diseñaron de modo que proporcionaran un servicio acorde con el mejor esfuerzo en la entrega (BE). De manera que no se hace ninguna distinción en términos de la importancia relativa de ningún tipo de tráfico ni en sus requisitos de temporización, pudiéndose provocar la pérdida de datos críticos [16].

En la definición del protocolo IP, se creó la opción Multicast, servicio que ha demostrado ser muy eficiente en cuanto al consumo de ancho de banda [WIL00]. Sin embargo, la demanda de estos servicios en Internet ha crecido en gran medida, requiriéndole a la misma el tratamiento diferencial de cada aplicación.

La presencia de tráfico elástico (aquel que permite el retardo) y no elástico (aplicaciones de misión crítica) hace que se maneje el concepto de calidad de servicio (QoS), con el cual se pueden garantizar los recursos que una aplicación requiere. Así, es posible controlar las variaciones de retardo, rendimiento y pérdida de paquetes en una interred.

Lo anterior y el aumento explosivo de requerimiento de ancho de banda actual, han llevado al desarrollo de investigaciones, que, como esta, buscan alternativas para ofrecer esos anchos de banda y manejo de QoS por medio de los últimos avances de tecnología óptica sobre la Multiplexación por División de Onda (WDM) o la Multiplexación por División de Onda en Modo Denso (DWDM), las cuales proveen un ancho de banda por fibra del orden de los Tera bits por segundos (Tbps).

La Segunda Generación de la Internet Óptica (SGOI) representa un avance en el ofrecimiento de una aproximación más eficiente para proporcionar servicios IP en la parte alta de la capa óptica. Realmente, la capa óptica provee la obtención dinámica de recursos para la altamente variable demanda IP.

En la arquitectura de dos capas, IP sobre WDM, visionada en SGOI, cada capa puede proporcionar su propio esquema independiente y elástico.

Esquemas de Restauración/Protección pueden ser implementados en la capa IP (posiblemente usando la subcapa Conmutación Multiprotocolo de Etiqueta, MPLS) y en la capa WDM (utilizando también el plano de control de MPLS Generalizado o MPXS) [15].

Precisamente, la presente investigación se desarrolla con el objetivo de encontrar un modelo de optimización para la transmisión multicast en redes GMPLS, constituyéndola en un aporte hacia el desarrollo de la Internet Óptica de Segunda Generación.

De manera concreta, se presenta una solución a un MOP, en donde las distintas variables de decisión son la atenuación, el retardo y las longitudes de onda. Así, no sólo se dará una propuesta para mejorar la transmisión sobre el medio óptico, sino que se optimizaría dicha transmisión. En investigaciones previas, se ha logrado demostrar que este tipo de problemas pertenece a la categoría de NP-Duro (no tienen solución en tiempo polinomial); por tal motivo, el problema se resuelve a través de metaheurísticas, utilizando algoritmos evolutivos. Con ello se logra alcanzar una solución en tiempo polinomial. En esta propuesta, se emplea un algoritmo que combina la lógica difusa con el algoritmo evolutivo SPEA2, por lo que se le ha llamado FSPEA2.

El artículo está organizado de la siguiente forma: En la sección 2, se describen algunos trabajos relacionados directamente con el aquí presentado. En la sección 3, aparecen descritos los métodos de Reardon y Sakawa, actualmente los más utilizados para la solución de problemas multiobjetivos donde está presente la lógica difusa. En la sección 4, se presenta el modelo difuso propuesto. La sección 5 comprende la exposición algoritmo que lo soluciona (FSPEA2); en tanto que la 6 presenta los resultados de las comparaciones realizadas entre el SPEA2 y el FSPEA2. Finalmente, en la sección 7, se presentan las conclusiones.

2. TRABAJOS RELACIONADOS

Y. Donoso [1, 2] presenta un conjunto de árboles óptimos para la transmisión de tráfico multicast, en los que se tiene en cuenta la minimización de la máxima utilización de los enlaces y, además, se minimiza la cantidad de saltos, ancho de banda consumido y el retardo. Este mismo autor [3] demuestra que la función objetivo se puede reproducir mediante el árbol de caminos más corto: asignándole pesos a los enlaces, se presenta no solo la demostración del modelo, sino que se logra la construcción de un algoritmo, cuya solución es en tiempo polinomial.

Por otra parte, el empleo de la lógica difusa en la solución de problemas de optimización multiobjetivos en redes ópticas con transmisión multicast no se ha abordado hasta el final de la exploración bibliográfica del presente artículo. Sin embargo, el empleo de lógica difusa en otro tipo de problemas de optimización multiobjetivo es difundido por Reardon [8, 9, 10, 11]; Sakawa [12, 13] y Sánchez [14].

3. LÓGICA DIFUSA PARA LA SOLUCIÓN DE PROBLEMAS MULTIOBJETIVO

La lógica difusa puede ser considerada una extensión de la lógica n-valuada, propuesta por Lukasiewiez en 1930; la cual, a su vez, es una extensión de la lógica trivaluada propuesta por Kosko. La lógica difusa permite tratar información imprecisa en términos de conjuntos difusos y es recomendable en la solución de problemas no lineales o no muy bien definidos [7].

La teoría de conjuntos difusos parte de la teoría clásica de conjuntos, añadiendo una función de pertenencia |U_A(t), que indica el grado en que la variable t está incluida en el concepto representado por la etiqueta A.

En problemas de optimización multiobjetivo, la lógica difusa ha sido utilizada en combinación con algoritmos genéticos como lo plantean Reardon [8, 9, 10, 11], Sakawa [12, 13] y Sánchez [14].

3.1. Método de Reardon

El método presentado por Reardon fue ampliamente explicado por Coello [5].

Para cada función objetivo, este autor define una función de membresía como se presenta en la figura 1. En donde:

S_min y S_max Factores de escala difusa.

fi _min : Valor mínimo de la i-ésima función objetivo.

fi max : Valor máximo de la i-ésima función objetivo.

O_i: Valor experimental de la i-ésima función objetivo, idealmente fi = O_i.. E_i: Margen de error aceptable (el obj etivo O. tiene un intervalo de satisfacción de amplitud 2* E_i).

La Ecuación de la función de membresía es la siguiente:

3.2. Método de Sakawa

Este método usa lógica difusa en todos los niveles, desde los parámetros del problema hasta los de las restricciones e, incluso, en el conjunto de soluciones encontradas. De manera concreta, utiliza un nivel de membresía para las soluciones [13]. Esto significa que las soluciones tienen un nivel de correlación con el objetivo inicial, el cual es establecido por el tomador de decisiones. Un resumen detallado del método puede ser consultado en Coello [5].

Sakawa [13] también establece que, en algunos problemas de optimización multiobjetivo, sería más apropiado considerar que los valores de los parámetros de la función objetivo y de las restricciones involucran cierta ambigüedad, debido al desconocimiento del experto en cuanto al funcionamiento del sistema real durante el proceso de formulación del problema. Para evitarla, este autor plantea un modelo de problema de programación no lineal multiobjetivo con números difusos (MONLP-FN), a saber:

Luego de introducir los conceptos de a-MONLP y Ga-MONLP, Sakawa [13] propone solucionar el problema multiobjetivo utilizando el problema minimax aumentado, el cual queda especificado por:

Es importante notar que el término aumentado se adopta porque al problema minimax estándar se agrega el término , donde ρ es un escalar positivo suficientemente pequeño.

Para que el problema minimax aumentado pueda involucrar no convexidad, Sakawa recomienda utilizar la siguiente función de fitness:

4. MODELO DIFUSO

El modelo de optimización multiobjetivo presentado por Y. Donoso [4] optimiza las variables: Retardo, cantidad de saltos, ancho de banda utilizado, máximo retardo, máxima cantidad de saltos, retardo promedio, cantidad

de saltos promedio, cantidad de lambdas, máxima variación del retardo, máxima variación de la cantidad de saltos y máxima atenuación. Aplicando al anterior, el modelo difuso, propuesto por Sakawa, las funciones a optimizar son las siguientes:

Sujeto a

Donde

Se debe destacar que las restricciones no son afectadas por la lógica difusa, debido a que las mismas son teorías físicas demostradas, las cuales no se someten a la incertidumbre.

La variable a. no es una constante, sino una variable de decisión y el operador ° no es específicamente suma o multiplicación, sino el operador de la variable a. sobre la función original f(x).

5. SOLUCIÓN PROPUESTA

En la figura 2, se presenta el algoritmo SPEA2, en el que se encuentran resaltados los pasos donde se ha incluido lógica difusa. A continuación, se describe la manera en que el algoritmo original fue modificado.

El valor de certidumbre (a) mínimo del algoritmo varía a lo largo de la ejecución del mismo, entre 0.5 y 1.0; sin embargo, su nivel de convergencia, a medida que aumenta el número de generaciones calculadas, es uno (1.0). Siendo el valor inicial de a aleatorio.

En el algoritmo, luego de obtener el valor de las funciones objetivo (f i(xi )), se le aplica a éstas un valor de certidumbre basado en la generación de un número triangular difuso simétrico, cuya media es fi(xi.); obteniéndose así f (x , a). El valor asignado es aleatoriamente escogido dentro del rango de certidumbre dado por a; en otras palabras, éste valor pertenece al intervalo [f_i(x_i)-t;f_i(x.)+t].

La función de membresía - μi[fi(xi, a)] - se calcula con base en los valores mínimos y máximos de cada función, teniendo en cuenta las siguientes premisas:

1. Cada generación da origen a un frente de Pareto.

2. Cada nueva generación, y el frente de Pareto que ésta origina, se acercarán más al frente real.

Tomando como base las premisas anteriores, se calculan, para cada generación, los valores máximos y mínimos de cada función, obteniéndose la membresía de cada individuo, así:

La función fitness, utlizada en el FSPEA2, es la propuesta por Sakawa, la cual utiliza la función de membresía. Se trata, así, de un valor que mide la cercanía al frente de Pareto real ( μi), el cual se ha tomado como 0.9, para obtener los valores más cercanos a dicho frente y dejar un nivel de incertidumbre.

Donde los individuos con el fitness más alto son los que deben formar parte de la población elitista.

Midiendo los valores de strength y rawfitness obtenidos por los individuos, y comparándolos con fi(xi , a) y el fitness obtenido, se llegó a la conclusión de que el valor mínimo del fitness para pasar a la población elitista es 0.5; garantizando así no caer en óptimos locales.

6. RESULTADOS

6.1 Características del experimento

El experimento toma las topologías Nacional Science Foundation (NSF), MCI y Sprint, analizando el comportamiento de cada una cuando el tráfico multicast se dirige hacia el 20%, 30%, 40%, 50%, 60%, 70%, 80% y 90% de nodos del total de la red.

En estas circunstancias, mientras la cantidad de los nodos destinos varían, los parámetros de entrada para el algoritmo se mantienen fijos, de la siguiente manera:

• Población: 100

• Archive Size: 50

• Matting Pool: 50

• Generaciones: 50

El algoritmo FSPEA2 se ejecutó cinco (5) veces en cada una de las combinaciones Topología - Porcentaje Destinos.

Las métricas a analizar son:

• Diferencias Normalizadas de las medías de los valores extremos (DNME). Para calcular el DNME, se calcula, por cada PF_known, el valor mínimo encontrado para cada una de las funciones. Posteriormente, se calcula la media y desviación estándar de estos valores por cada PF_known, obtenido con el mismo algoritmo y numero de iteraciones. Después de tener estas medias y desviaciones estándares, se calculan las diferencias normalizadas entre estos valores para cada numero de iteraciones.

Generación de vectores no dominados (GVND). GVND es una métrica que indica el numero de elementos no dominados generados por un algoritmo, esto es, GVND = 1 PF_true I.

Distancia Generacionales (DG). Esta métrica indica qué tan lejos está el PF_known del PF_true. Matemáticamente, se define se define así:

• Spacing (S). Esta métrica es utilizada para establecer qué tan bien distribuidas están las soluciones en el espacio objetivo a través de PF_known. Matemáticamente, se expresa de la siguiente manera:

Donde,

Para esta métrica, un valor de 0 significa que todos lo elementos de PF_knawn están equidistantemente espaciados. Por lo tanto, entre menor sea el valor de S, mejor es la distribución de los elementos del PF_known.

• Tiempo computacional

6.2 Resultados

En la figuras 3, se ilustran las diferencias normalizadas que se obtuvieron con respecto a cada una de las funciones objetivo; siendo de gran importancia la diferencia obtenida para f₂(x, a₂), donde alcanza diferencias hasta del 90%.

En las figuras 4, 5 y 6, se ilustran los resultados de las tres (3) métricas restantes frente al aumento de nodos destinos en cada una de las topologías.

Para el caso de la generación de vectores no dominados, el SPEA2 obtuvo más soluciones, a excepción de la topología MCI, en el que, a partir de una cantidad de nodos destinos equivalentes al 50%, el algoritmo FSPEA2 obtiene más soluciones.

La distancia generacional (DG) se calcula tomando el frente de Pareto generado por el algoritmo SPEA2 como el PF_known . Se encuentra así que los resultados obtenidos al analizar la topología MCI son los más cercanos al PF_known , mientras que los más alejados son los obtenidos de la topología Sprint.

La figura 6 evidencia el comportamiento de los dos (2) algoritmos con respecto a la métrica Spacing, mostrando el SPEA2 una mayor uniformidad

en los resultados arrojados. Es importante resaltar que, tanto para el FSPEA2 como para el SPEA2, a medida que aumenta la cantidad de nodos destinos, disminuye levemente la uniformidad con la que se distribuyen los datos obtenidos en cada uno de los algoritmos.

• Tiempo Computacional. En forma general, el algoritmo FSPEA2 consumió mucho más tiempo de ejecución que el SPEA2, alcanzando diferencias hasta por 16010.8%.

6.3 Análisis de correlación

• Retardo (f₀(x, a₀)). Esta función muestra una relación directa con dos objetivos. El primero de ellos es la cantidad de saltos (f₁(x, a₁)), con un coeficiente promedio de 0.8645; el segundo es el retardo promedio (f₅(x, a₅)). Se evidencia una relación perfecta y directa, ya que para todos los casos el coeficiente tomó el valor de uno (1).

• Cantidad de Saltos (f₁(x, a)). Los valores desplegados en las topologías seleccionadas evidencian que la relación que existe entre esta función y el Retardo (f₀(x, a₀)) - Retardo Promedio (f₅(x, a₅)) es la misma, mostrando un comportamiento promedio de 0.8645. Adicionalmente, muestra una estrecha relación con el objetivo Cantidad de Saltos Promedio (f₆(x, a₆)), sin llegar a ser una relación perfecta.

• Máximo Retardo (f₃(x, a₃)). El coeficiente de correlación que existe entre esta función y la máxima variación del retardo (f₈(x, a₈)) es perfecta y directa, debido a que siempre se obtuvo en coeficiente de 1.

Máxima Cantidad de Saltos (f₄(x, a₄)). Aunque la topología MCI, con 20% de nodos destinos, no presenta una relación perfecta, ésta toma un valor considerablemente alto (0.98) con respecto al objetivo máxima variación de la cantidad de saltos (f₉(x, a₉)); además, en las topologías siguientes se muestra una relación perfecta de 1.

7. CONCLUSIONES

De acuerdo con los resultados discutidos en el ítem anterior, en los que se mostró el comportamiento de los algoritmos en las topologías MCI, NSF y Sprint, se puede concluir:

• Cuando el valor de certidumbre varía ampliamente, el algoritmo FSPEA2 no obtiene soluciones satisfactorias en comparación con el SPEA2. Aun cuando se aumenta la cantidad de generaciones calculadas, se mantienen los valores de las diferentes métricas multiobjetivo evaluadas en la presente investigación (diferencia normalizada, cantidad de individuos no dominados, distancia con el frente de Pareto real y la distancia entre los individuos solución). Lo anterior se debe a que la cantidad de generaciones calculadas con un nivel de certidumbre superior a 0.9 no logran ser suficientes para igualar o superar el nivel del SPEA2.

• Manteniendo el valor de certidumbre fijo en 0.9, el algoritmo FSPEA2 logra mejorar los resultados obtenidos, permitiendo aumentar la cantidad de individuos no dominados de la solución; sin embargo, no logra alcanzar el nivel de solución logrado por el algoritmo SPEA2.

Al correlacionar las métricas multiobjetivo distancia generacional y spacing, se concluye que los resultados arrojados por el algoritmo FSPEA2 se concentran en una zona del frente de Pareto real.

• Los valores mínimos obtenidos por el SPEA2 y el FSPEA2 son los mismos en la topología MCI con una cantidad de nodos destinos correspondiente al 20%. Esto es consecuencia directa de que algunos individuos encontrados por el SPEA2 hayan sido encontrados también por el FSPEA2, confirmando la legitimidad del método propuesto.

• Basados en el análisis de correlación, el modelo puede reducirse a siete (7) funciones objetivos. Esto se lleva a cabo, eliminando las funciones Retardo (F0), Cantidad de Saltos (F1), Máximo Retado (F3) y Máxima Cantidad de Saltos (F4) y dejando, en cambio, para el estudio, el comportamiento del Retardo Promedio (F5), Cantidad de Saltos Promedio (F6), Máxima Variación del Retardo (F8) y Máxima Variación de la Cantidad de Saltos (F9), respectivamente; debido a que éstas últimas arrojan valores más significativos y equicomparables.

• Las condiciones bajo las que se concibió el modelo matemático a solucionar tienen por naturaleza un nivel de certidumbre muy alto, por lo que la amplia variación de éste arrojó soluciones medianamente alejadas a las encontradas con un nivel de certidumbre de uno (1), como las obtenidas por el SPEA2.

Referencias

[1] Y. DONOSO; R. FABREGAT y J. MARZO, Multi-Objective Optimization Algorithm for Multicast Routing with Traffic Engineering. IEEE, 2003.

[2] Y. DONOSO; R. FABREGAT y J. MARZO, Multicast Routing With Traffic Engineering: A Multi-Objective Optimization Scheme And A Polynomial Shortest Path Tree Algorithm With Load Balancing. IEEE, 2003.

[3] Y. DONOSO; R. FABREGAT y J. MARZO, Multi-Objective Scheme over Multi-Tree Routing in Multicast MPLS Networks, en: Latin American Networking Conference (LANC'03). La Paz, 2003.

[4] Y. DONOSO; C. ALVARADO; I. HERAZO; A. PÉREZ, An approach to the Optimization of Convergent Networks on IP/MPLS with an Optical GMPLS Backbone in Multicast. WSEAS Transactions on Communications. Issue 6. Vol. 5. June: 2006.

[5] C. COELLO, Introducción a la Optimización Multiobjetivo. [En línea] Septiembre 2002. Disponible en: http://neo.lcc.uma.es/pdf-charlas/MOEA.pdf. [6] C. COELLO, A"plicaciones de los Algoritmos Evolutivos Multiobjetivo". [En línea] Septiembre 2002. En: http://neo.lcc.uma.es/pdf-charlas/apli-MOEA.pdf.

[7] B. MARTIN DEL BRÍO; A. SANZ, Redes Neuronales y Sistemas Difusos. 2Ed. RAMA, Bogotá: Alfaomega Grupo Editor, 2005.

[8] B. REARDON, Fuzzy Logic vs Niched Pareto Multi-Objective Genetic Algorithm Optimization: Part I: Schaffer's F2 Problem. Technical report LA-UR-97-3675, Los Alamos National Laboratory, 1997.

[9] B. REARDON, Fuzzy Logic vs Niched Pareto Multi-Objective Genetic Algorithm Optimization: Part II: a Simplified Born-Mayer Problem. Technical report LA-UR-97-3676, Los Alamos National Laboratory, 1997.

[10] B. REARDON, Optimization of Micromechanical Densification Modeling Parameters for Copper Powder Using a Fuzzy Logic Based Multiobjective Genetic Algorithm. Technical report LA-UR-97-0419, Los Alamos National Laboratory, 1998.

[11] B. REARDON, Optimization of Densification Modeling Parameters of Beryllium Powder Using a Fuzzy Logic Based Multiobjective Genetic Algorithm. Technical report LA-UR-97-1036, Los Alamos National Laboratory, 1997.

[12] MSAKAWA, K. KATO, H. SUNADA, T. SHIBANO, "Fuzzy Programming For Multiobjective 0-1 Programming Problems Through Revised Genetic Algorithms". European Journal Of Operations Research, 97, 1, pp. 149-158, 1997.

[13] M. SAKAWA, Genetic Algorithms and Fuzzy Multi-Objective Optimization. USA: Kluber Academic Publisher, 2002.

[14] E. SANCHEZ, T. SHIBATA, L. ZADE, Genetic Algorithms And Fuzzy Logic Systems: Soft Computing Perspectives. World Scientific, River Edge, N J, 1997.

[15] L. VALCARENGHI, "Survivable IP-over-WDM networks". En: ProQuest Digital Dissertations & Theses. The University of Texas at Dallas, Diciembre 2001.

[16] K. WANG, "Multicasting in MPLS networks". (No publicado). En: ProQuest Digital Dissertations & Theses. Concordia University (Canada), Junio 2003.

Notas

^* Universidad Tecnológica de Bolívar e Instituto Tecnológico de Monterrey. lctovar@uninorte. edu.co

^** Universidad Tecnológica de Bolívar e Instituto Tecnológico de Monterrey. mcoronel@uninorte. edu.co

^*** Departamento de Ingeniería de Sistemas, Universidad del Norte. Correspondencia: Universidad del Norte Km. 5 vía a Puerto, Barranquilla, Colombia. ydonoso@uninorte.edu.co