Optimización de recursos en redes de transporte ópticas multicapa

Máster en Estadística e Investigación Operativa Título: Optimización de Recursos en Redes de Transporte Ópticas Multicapa Autor: Marc Ruiz Ramírez Director: Francisco Javier Heredia Cervera Luis Domingo Velasco Esteban Departamento: Estadística e Investigación Operativa Convocatoria: Febrero 2009 Índice de contenidos Pag. Capítulo 1. Introducción 1 1.1 – Motivación 1 1.2Objetivos y estructura del PFC 2 1.3 – Consideraciones 3 Capítulo 2. Introducción a las redes de transporte 5 2.1 – Panorama actual 5 2.2 – Definición de conceptos básicos 6 2.2.1 – Recursos ópticos 6 2.2.2 – Multiplexado de datos 7 2.2.3 – Arquitecturas multicapa 8 2.2.4 – Arquitectura de gestión de las redes de transporte 9 2.2.5 – Gestión de conexiones eléctricas 10 Capítulo 3. Problema de liberación de recursos ópticos 15 3.1 – Planteamiento del problema 16 3.1.1 – Utilización subóptima de recursos ópticos 16 3.1.2 – Objetivo del problema 18 3.1.3 – Consideraciones sobre el conjunto de arcos ópticos 19 3.1.4 – Consideraciones sobre los cambios de ruta de las conexiones eléctricas 20 3.2 – Formulación matemática 24 3.2.1 – Estructura de los datos 24 3.2.2 – Variables de decisión 25 3.2.3 – Restricciones del problema 26 3.2.4 – Función objetivo 29 Capítulo 4. Ejemplos de resolución exacta del problema 31 4.1 – Definición de ejemplos de red 31 4.1.1 – Topología de prueba 31 4.1.2 – Topología Europea 33 4.1.3 – Escenarios de tráfico simulados 35 4.2 – Resolución exacta sobre red de test 38 4.2.1 – Características de la implementación 38 4.2.2 – Resumen de resultados 38 4.2.3 – Análisis del tiempo de computación 40 4.2.4 – Análisis de las modificaciones producidas 41 4.2.5 – Conclusiones 43 4.3 – Resolución exacta sobre red europea 44 4.3.1 – Características de la implementación 44 4.3.2 – Resumen de resultados 44 4.3.3 – Análisis del tiempo de computación 45 4.3.4 – Análisis de las modificaciones producidas 47 4.3.5 – Conclusiones 48 Capítulo 5. Meta-heurística GRASP 49 5.1 – Definiciones básicas 50 5.1.1 – Criterio de selección voraz 50 5.1.2 – Aleatorización de la selección 52 5.2 – Estructura y fases de la meta-heurística GRASP 53 5.2.1 – Estructura elemental de la heurística 53 5.2.2 – Fase I o fase constructiva aleatorizada 55 5.2.3 – Fase II o fase de mejora local 57 5.2.3 – Acción combinada de las dos fases 59 5.3 – Ajuste y sensibilidad de parámetros 59 5.3.1 – Análisis de sensibilidad del parámetro α 60 5.3.2 – Estudio del criterio de parada 61 5.4 – Adaptación de la heurística al problema 63 5.4.1 – Estructura de una solución factible 63 5.4.2 – Criterio greedy de selección de arcos ópticos candidatos 64 5.4.3– Selección de arcos ópticos eliminables 64 5.4.4– Selección de rutas alternativas de conexiones eléctricas 64 5.4.5 – Método de mejora 65 5.4.6 – Criterio de parada 65 5.4.7 – Pseudocódigo de la fase constructiva adaptada 65 5.4.7 – Pseudocódigo de la fase de mejora adaptada 66 5.5 – Definición de versiones 67 5.5.1 – Greedy Básico No Aleatorizado 67 5.5.2 – GRASP óptico 68 5.5.3 – GRASP eléctrico 68 5.5.4 – GRASP doble 69 Capítulo 6. Resolución de las versiones heurísticas 71 6.1 – Heurística Básica No Aleatorizada 71 6.1.1 – Diseño de pruebas 71 6.1.2 – Resultados en red de prueba 72 6.1.3 – Resultados en red europea 74 6.1.4 – Análisis de resultados 76 6.2 – GRASP óptico 76 6.2.1 – Diseño de pruebas 76 6.2.2 – Resultados en red de prueba 77 6.2.3 – Resultados en red europea 79 6.2.4 – Análisis de resultados 80 6.3 – GRASP eléctrico 81 6.3.1 – Diseño de pruebas 81 6.3.2 – Resultados en red de prueba 81 6.3.3 – Resultados en red europea 83 6.3.4 – Análisis de resultados 84 6.4 – GRASP doble 85 6.4.1 – Diseño de pruebas 85 6.4.2 – Resultados en red de prueba 86 6.4.3 – Resultados en red europea 87 6.4.4 – Análisis de resultados 89 Capítulo 7. Conclusiones y extensión del trabajo 91 7.1 – Criterios de valoración del método de resolución 91 7.2 – Comparación Método exacto vs. Métodos heurísticos 93 7.3 – Selección de la mejor versión heurística 94 7.4 – Integración de la meta-heurística en el sistema de gestión 95 7.5 – Extensión del proyecto 97 Referencias bibliográficas 101 Anexo: Implementación de la meta-heurística GRASP en Matlab 103 Consideraciones sobre la implementación 103 Implementación Algoritmo Central 103 Implementación Fase Constructiva 104 Implementación Fase de Mejora 108 Agradecimientos Agradezco el trabajo, la ayuda y el apoyo de mis directores de proyecto: a Luis Velasco, que me ha abierto las puertas a un mundo que hasta hace unos meses desconocía, y que voy a seguir explorando en un futuro próximo; y a Francisco Javier Heredia, quien me invitó a entrar en esta carrera y que ahora se ha preocupado por procurarme un digno final. Agradezco especialmente a Elena Fernández la virtud que ha tenido para introducir la Investigación Operativa dentro de mis motivaciones personales. Agradecimientos y disculpas a toda mi familia y amigos, que han consentido ausencias, desplantes, retrasos y otras faltas, con paciencia y comprensión, por el bien de esta empresa. Y como no, un agradecimiento y un “te quiero” para Montse, que ha sabido llevar con templanza y empatía los momentos más difíciles de este proceso, sin que transcendieran más allá de lo justo y necesario. 1 Capítulo 1 Introducción 1.1 – Motivación Internet se está convirtiendo en el centro neurálgico de las comunicaciones globales. El tráfico cada vez es más heterogéneo (tráfico de voz, datos, multimedia), y cada vez tiene mayor volumen y mayor amplitud. Esta enorme demanda necesita una estructura de transporte de gran capacidad y gran alcance para poder ser satisfecha. Las redes de transporte de fibra óptica, implantadas desde hace unos años para las comunicaciones, cumplen estos requisitos. No obstante, la capacidad de estas redes, aún siendo enorme, es finita. Y por otro lado, el tráfico crece exponencialmente con el tiempo. Debido a los inconvenientes que supone ampliar estas redes, la posibilidad de albergar más tráfico se sustenta en las posibilidades de optimización que presentan. Desde su puesta en funcionamiento, el diseño de redes, el enrutamiento óptimo de las conexiones entre clientes y la gestión integral de recursos, permiten un buen uso de los elementos ópticos disponibles. 8 1) Multiplexado por división en tiempo (TDM): diferentes tráficos se satisfacen en pequeños intervalos de tiempo correlativos. Durante un instante de tiempo concreto solo circula un único tráfico, y estos se van alternado en breves intervalos de tiempo hasta ser totalmente satisfechos. Fig. 2.2 – TDM (fuente: http://www.rigacci.org) 2) Multiplexado por división en longitud de onda (WDM): este tipo de multiplexación se aplica específicamente a las fibras ópticas. Cada longitud de onda en la que puede separarse el haz de luz, puede transportar una señal concreta. Eso quiere decir que podemos enviar distintas señales a la vez, aprovechando todo el ancho de banda que permite el multiplexado en longitud de onda. Para multiplexar/demultiplexar varias señales ópticas es necesario juntarles/separarlas en/del haz lumínico, utilizando dispositivos especiales denominados prismas ópticos, como se observa en la figura 2.3. 2.2.3 – Arquitecturas multicapa El tráfico generado (datos, voz, Internet) por clientes individuales (empresas, particulares) tiene naturaleza eléctrica y requiere un ancho de banda cada vez mayor. Para hacernos una idea, en estos momentos estamos utilizando conexiones a Internet por ADSL entorno a los 10 Mbit/s. Por otra parte, las redes de fibra óptica permiten transportar tráficos de cliente a través de la transmisión de impulsos lumínicos, ofreciendo un ancho de banda en el entorno de los 10 Tbit/s. Como puede observarse es necesario organizar las redes de transporte en un conjunto de capas, de forma que los tráficos de cliente se agreguen antes de ser transportados por las redes ópticas, optimizando el uso del ancho de banda. 9 Fig. 2.3 – WDM (fuente: http://www.its.bldrdoc.gov) Un ejemplo muy común de red multicapa se presenta en la figura 2.4. Aquí podemos observar una arquitectura de red formada por 4 capas: capa física de fibra, una capa de multiplexación óptica, una capa de agregación eléctrica-óptica y la capa de enrutamiento IP. Fig. 2.4 – Red multicapa (fuente: http://cordis.europa.eu) 2.2.4 – Arquitectura de gestión de las redes de transporte Como hemos comentado anteriormente, la tecnología óptica permite establecer/liberar conexiones utilizando un componente clave: el conmutador óptico. Estos dispositivos se integran en los equipos de comunicaciones ópticos. La más simple de las redes ópticas puede incluir cientos (o miles) de conmutadores ópticos. Por este motivo es 10 imprescindible disponer de un sistema de gestión de la red (NMS) que facilite el mantenimiento y operación de las redes ópticas. El NMS dispone de toda la información sobre la red y su estado en cada momento; por ejemplo, permite establecer de una forma centralizada conexiones punto a punto entre dos localizaciones de la red, encadenando un conjunto de actuaciones sobre conmutadores ópticos. La figura 2.5 muestra un único sistema de gestión de red que gestiona de forma centralizada dos capas de la red multicapa anterior. Fig. 2.5 – Gestión centralizada de la red multicapa El método de optimización que se estudiará en este PFC se ubica en el sistema de gestión de la red. El optimizador actuará sobre la capa de agregación eléctrica, sobre la que modificará el tráfico establecido sin necesidad de actuar sobre la capa óptica. La figura 2.6 presenta la nomenclatura utilizada en este PFC para referirse a cada uno de los componentes de la arquitectura de gestión. 2.2.5 – Gestión de conexiones eléctricas Cuando una nueva petición de conexión eléctrica llega al NMS, este se encarga de encontrar una ruta en la capa de agregación de clientes para poder dar servicio a esa conexión. Al realizar esta acción, pueden suceder dos situaciones: 11 Fig. 2.6 – Nomenclatura de red y gestión A) Existe algún camino a través de los arcos ópticos con suficiente capacidad como para servir la conexión entre clientes. En este caso, la conexión se establece a través de la ruta de menos coste posible. Para el cálculo de la ruta se utilizan algoritmos basados en Dijkstra [3]. B) No existe ningún camino a través de los arcos ópticos con suficiente capacidad o conectividad para satisfacer la conexión. En ese caso, puede suceder uno de los siguientes casos. 1. Existen recursos libres en la capa óptica suficientes para crear nuevos arcos ópticos que permitan satisfacer la conexión: en ese caso, se generan las nuevas estructuras ópticas en la capa de agregación eléctrica (a partir de los recursos ópticos disponibles), siguiendo una cierta función de coste asociada a los arcos ópticos. 2. No existen recursos ópticos libres para satisfacer la conexión: en ese caso, se rechaza la petición de establecimiento de conexión. Las figuras 2.7 y 2.8 ilustran los casos A) y B1) respectivamente. Por otra parte, el sistema de gestión también se encarga de liberar la capacidad óptica utilizada por una conexión eléctrica cuando ésta ha finalizado su tiempo de establecimiento. En este caso, pueden ocurrir dos situaciones: 12 D C E AB NMS Conexión A-E Enrutar por la ruta A-C-D-E D C E AB NMS Enrutamiento eléctrico por arcos establecidos Fig 2.7 – Enrutamiento eléctrico D C E AB NMS Conexión A-E Crear arco óptico CE y enrutar por A-C-E D C E AB NMS Establecimiento de nuevos arcos ópticos Fig 2.8 – Generación arcos ópticos C) La finalización del establecimiento de la conexión ha dejado sin ocupación algún o algunos arcos ópticos: en ese caso, los arcos ópticos sin ocupación se eliminan de la red de agregación eléctrica, liberando así recursos ópticos en la capa óptica. D) La eliminación de la conexión eléctrica no deja ningún arco sin ocupación: en ese caso, no se realiza ninguna acción sobre los arcos ópticos. 13 La figura 2.9 ilustra el caso C). Conexión A-E Eliminar arco DE D C E AB NMS Eliminación de arcos ópticos sin ocupación D C E AB NMS Fig 2.9 – Eliminación arcos ópticos 15 Capítulo 3 Problema de liberación de recursos ópticos Como hemos visto en el capítulo anterior, el desarrollo tecnológico en el campo de las redes de comunicación de fibra óptica está permitiendo transportar un gran volumen de información heterogénea, de una manera más eficiente, segura y veloz, entre puntos que pueden estar distanciados por miles de kilómetros. Esta base tecnológica permite también una evolución del tráfico transportado, que cada vez es más intenso y heterogéneo. El futuro de las comunicaciones pasa por un óptimo transporte de datos entre los diferentes nodos de las redes En este sentido, el diseño de redes, el enrutamiento de conexiones entre nodos, la asignación de recursos ópticos, entre otros procedimientos, permiten utilizar el entorno óptico de forma que se puedan optimizar los recursos utilizados en cada caso, sin renunciar a la cantidad y calidad del servicio. No obstante, el tránsito de información es un hecho dinámico, que constantemente se modifica, lo cual hace que sea necesario aplicar procedimientos adaptativos en el tiempo, que permitan reoptimizar estructuras y decisiones creadas en su momento con la mejor intención operativa. En este capítulo presentaremos una situación en la que podemos aplicar un proceso de mejora que permita, dado un escenario e instante de tiempo concreto, modificar la 16 estructura de arcos ópticos que transporta un cierto tráfico, para poder reducir la cantidad de recursos ópticos utilizados. Esto nos debe permitir, sin pérdida de factibilidad, obtener una nueva situación en la que se pueda prestar el mismo servicio con un coste total menor. Estos procesos de mejora están a la orden del día, y forman parte de los temas de investigación que actualmente se llevan a cabo en el mundo de las comunicaciones ópticas. El gran crecimiento de las posibilidades de conexión y transmisión de información remota puede llevar a una sobrecarga en las redes y a una probabilidad de rechazar conexiones por falta de recursos disponibles cada vez mayor. La posibilidad de ir adaptando la red a las necesidades y características del tráfico presente puede permitir compactarlo y transportarlo utilizando menos recursos y pudiendo así tener espacio físico para albergar conexiones futuras. A continuación, describiremos el problema y la situación en la que se desarrolla. Luego plantearemos una modelización matemática que lo defina y analizaremos al detalle la solución exacta de diferentes escenarios de tráfico a partir de un motor de solución de problemas de programación lineal. 3.1 – Planteamiento del problema 3.1.1 – Utilización subóptima de recursos ópticos En el Capítulo 2, definimos los arcos ópticos a nivel de la la capa de agregación eléctrica y vimos de qué manera se generaban y se eliminaban. Por otra parte, vimos como se enrutaban a través de ellos las conexiones eléctricas que albergaban la información transportada. Como cada decisión se toma teniendo en cuenta la situación del momento, es fácil comprobar que la utilización de recursos en un instante concreto no va a ser la mejor posible. El siguiente ejemplo lo ejemplifica claramente: Supongamos en un cierto instante de tiempo t1, la siguiente red de arcos ópticos y de conexiones eléctricas activas a nivel de la Capa de Control: 17 Instante t1 Arco Disp AB 0 BC ½ DE ½ Con a.b. A-C(1) ½ A-B(1) ½ D-E(1) ½ Fig 3.1Red en el instante t1 En un instante t2, que cumple que t2>t1, llega una petición de conexión entre los nodos A y C, y que requiere un ancho de banda de ½. Pero resulta imposible enrutar la conexión por los arcos ópticos existentes (a través de los arcos AB y BC), ya que el arco AB no presenta ancho de banda disponible. Supondremos que la red óptica de base tiene suficiente capacidad como para crear un nuevo arco óptico directo entre A y C. Por lo tanto, el procedimiento a seguir será generar el arco óptico AC y enrutar directamente a través de él la conexión requerida: Instante t2 Arco Disp. AB 0 BC ½ DE ½ AC ½ Con a.b. A-C(1) ½ A-B(1) ½ D-E(1) ½ A - C(2) ½ Fig 3.2 - Red en el instante t2 Un tiempo más tarde, en el instante t3 vence la conexión de color rojo entre los nodos A y B. Así que nos quedan dos conexiones entre A y C que están utilizando dos rutas diferentes y consumiendo más recurso óptico del que necesitan. Se puede ver como, si modificáramos la conexión azul y la enrutáramos a través del arco óptico AC, se quedarían libres de ocupación los arcos AB y BC, con lo que podríamos liberar los recursos ópticos que estuvieran utilizando ambos arcos. 24 3.2 – Formulación matemática A continuación vamos detallar la formulación matemática del problema de liberación de recursos ópticos. Plantearemos una modelización de los datos y variables de la situación que queremos abordar. Luego describiremos las restricciones que nos definirán el conjunto de soluciones factibles evaluables, y finalmente detallaremos la función objetivo de evaluación de esas soluciones. Las características más importantes de la formulación presentada son: • Formulación orientada a comparación de estados: la estructura de los datos y las variables permiten compararse entre sí para poder determinar y detectar qué cambios se producen con la optimización, esto es, que arcos ópticos se eliminan y que conexiones eléctricas se reenrutan. La estructura de variables es sinónima a la estructura de datos, con lo cual se puede realizar una comparación directa y evaluar los cambios. La asignación de los valores de las variables se puede entender como la construcción de un nuevo sistema y los valores de los datos sirven para restringir que se puede modificar y que no. • Formulación de programación lineal: las restricciones y función objetivo del problema tienen la forma de ecuaciones lineales con variables binarias y enteras. Esto permite poder aplicar motores de solución potentes como CPLEX, que solo trabajan con problemas de esta forma. Para ello, se han incorporado variables y restricciones adicionales, para poder deshacer productos de variables y funciones no lineales de evaluación en valor absoluto. 3.2.1 – Estructura de los datos El problema de liberación de interfaces ópticas se aplica en un instante de tiempo determinado sobre una red y tráfico establecidos. La modelización de los datos permite obtener toda la información sobre el estado del sistema en el momento de aplicación de la optimización, así como tener información suficiente para poder realizar los cambios necesarios y realizar así la mejora pretendida. 25 Inicialmente, debemos definir los siguientes conjuntos: • E: Conjunto de conexiones eléctricas que forman una instancia de tráfico = {1,…, i,…, I}. • R (e) : Conjunto de posibles rutas que darían servicio a la conexión e = {1,…, j,…, J}. • S: Conjunto de arcos ópticos activos en la red = {1,…, k,…, K}. Podemos ver como habrá tantos conjuntos R (e) como conexiones eléctricas haya. Definiremos un valor J max como la máxima cardinalidad de todos estos conjuntos. Esto es necesario para poder definir matrices de datos en cualquier R (e) y de dimensión fija, independientemente del número de rutas del conjunto. Dentro de estos conjuntos están todos los elementos que conforman nuestro sistema de red. Las siguientes estructuras guardan información sobre el tráfico circulante, así como de la relación entre conexiones, rutas y arcos: • N ij : matriz binaria de datos, de dimensión I x J max , cuyas celdas valdrán 1 si y solo si la conexión eléctrica i utiliza la ruta indexada en j. • Q ijk : matriz binaria de datos, de dimensión I x J max x K, cuyas celdas valdrán 1 si y solo si el arco óptico k forma parte de la ruta j perteneciente a la conexión i. Finalmente, también debemos guardar información sobre algunas características de los arcos ópticos y de las conexiones eléctricas, y que no variarán en el tiempo: • M k : Capacidad del arco óptico k para transportar flujo eléctrico (en unidades de ancho de banda). • W i : Ancho de banda de la conexión eléctrica i. 3.2.2 – Variables de decisión El planteamiento de las variables de decisión es el de modelar un estado paralelo al estado inicial del problema, que tenga una mejor valoración de coste y que cumpla las 26 restricciones. Veremos ahora que variables necesitamos tener en cuenta para obtener esta nueva versión del escenario: • η ij : Matriz binaria de dimensión I x J max , equivalente a la estructura de datos N ij , cuyas celdas valdrán 1 si y solo si la conexión eléctrica i utiliza la ruta j tras la optimización. • ζ k : Vector binario de dimensión K, con valor 1 si y solo si el arco óptico k permanece activo tras la optimización. La optimización produce unos cambios en la estructura de los arcos activos (registrado en la variable ζ k ) . Estos cambios conducen a modificaciones en las rutas de las conexiones eléctricas. Como hemos definido anteriormente, no todas las conexiones eléctricas podrán ser modificadas (sólo aquellas que se vean afectadas por un corte óptico). Es necesario crear una variable que recoja que conexiones eléctricas pueden y deben modificar su ruta para mantener la factibilidad: • ρ i : Vector binario de dimensión I, cuyos elementos valdrán 1 si y solo si la conexión eléctrica i debe cambiar de ruta respecto de la situación inicial. Para una posterior factibilidad del problema y evaluación de la función objetivo, debemos determinar una variable entera que recoja la cantidad de ancho de banda circulante por los arcos ópticos tras la reasignación: • δ k : Vector de enteros, cuyos elementos registrarán las unidades de ancho de banda ocupadas en el arco óptico k. 3.2.3 – Restricciones del problema Tomando las estructuras y variables definidas en el punto anterior, vamos a definir ahora las restricciones del problema, que tienen como misión cumplir las consideraciones, limitaciones y características del problema de liberación de recursos ópticos, tal y como se ha planteado en secciones anteriores. 27 3.2.3.1 – Restricciones sobre los arcos ópticos Existe una única restricción que actúa exclusivamente sobre los arcos ópticos, que debe permitir la factibilidad de la ocupación de los arcos. Esta restricción debe permitir que la ocupación sea nula en los arcos eliminados y menor que la capacidad pero existente en los arcos activos. La expresión es la siguiente: SkM kkkk ∈ ∀ × ≤ ≤ ),( ζ δ ζ 3.2.3.2 – Restricciones sobre las conexiones eléctricas Estas restricciones deben permitir que se cumplan las condiciones sobre las conexiones eléctricas y sus cambios de ruta. La primera y más elemental es que cada conexión eléctrica tenga una única ruta asignada: Ei iRj ij ∈∀= ∑ ∈ ,1 )( η La comparación de la variable de estado de las asignaciones de conexiones a rutas con la situación original, deberá dar resultados diferentes para las conexiones eléctricas que deban ser modificadas. La siguiente restricción relaciona la variable de estado de la red optimizada con la variable que fija que conexiones eléctricas deben moverse, de tal manera que no se permiten reasignaciones de rutas en conexiones que tienen que permanecer sin cambios: EiN iRj iijij ∈∀=×− ∑ ∈ ,))1(( )( ρη Estas dos últimas restricciones permiten cambios en las rutas de sólo aquellas conexiones eléctricas que tengan “permiso” para ello. 3.2.3.3 – Restricciones de unión de los niveles óptico y eléctrico Estas restricciones deben asegurar un flujo óptimo por los arcos ópticos activos y una reasignación factible de rutas. En primer lugar, debemos asegurar que la nueva 28 reasignación de rutas puede ser satisfecha en cuanto a capacidad disponible de los arcos se refiere: SkQW kij k ij Ei iRj i ∈∀≤×× ∑ ∑ ∈ ∈ ,)( )( δη Finalmente, deben cumplirse una condición de limitación de conexiones modificadas. Anteriormente, se asumió que se moverían sólo las conexiones que estuvieran obligadas a hacerlo por la eliminación de un arco óptico utilizado. Esta condición la aplicaremos desglosada en dos restricciones separadas. Por una parte, fijaremos que aquellas conexiones cuyos arcos ópticos no sufran ninguna desactivación, no puedan ser cambiadas de ruta: EiQN i Sk iRj k ijijk ∈∀≥−        ××− ∑ ∑ ∈ ∈ ,0)()1( )( ρζ Esta restricción cumple que si una conexión eléctrica tiene toda la ruta original por arcos que no van a ser eliminados, esa conexión debe mantener la ruta original ( ρ i = 0). En segundo lugar, obligamos que las conexiones afectadas con al menos un corte óptico sean reconducidas por un camino factible: Ei QN QN Sk iRj k ijij Sk iRj k ijijk i ∈∀≥ ×        ×× + ∑ ∑ ∑ ∑ ∈ ∈ ∈ ∈ ,1 )( )( )( )( ζ ρ En esta restricción, si una conexión eléctrica presenta al menos un corte óptico, el cociente de la expresión será inferior a 1 y, por tanto, el valor de ρ i deberá ser 1. 3.2.3.4 – Condiciones sobre las variables de decisión Formalmente, imponemos las condiciones sobre las variables que definimos en un apartado anterior: int},1,0{,, kiijk δρηζ ∈ 29 3.2.4 – Función objetivo Los costes asociados a variables de decisión presentes en la función objetivo son los siguientes: • C k : coste del arco óptico k, definido por la estructura de recursos ópticos a nivel de capa óptica. • L ij : coste de la ruta j para la conexión i, definido por la suma de los costes de los arcos ópticos por los que pasa. La expresión de la función de coste es la siguiente: ∑ ∑ ∑ ∑ ∑ ∑ ∑ ∈ ∈ ∈ ∈ ∈ ∈ ∈ + × × +−×− Sk k Sk k Ei iRj ijij Ei iRj ijij k Sk k MNL L C δ η ζ )( )( ))1((min )( )( Esta expresión recoge el criterio ordenado de valoración propuesto en la definición del problema. La suma de coste de recursos ópticos liberados (primer sumando de la expresión) es generalmente mayor que el resto de sumandos, con lo cual será el principal objetivo de la minimización. Este valor estará comprendido entre 0 e infinito, y para una liberación de recursos moderada, estará entorno a varias decenas (en unidades de recurso óptico). Para soluciones factibles con el mismo coste de esta expresión, se buscará la que obtenga una mejor valoración (más pequeña) de los otros dos sumandos. Así, se buscará la reubicación de conexiones eléctricas menos costosa respecto a la situación inicial. El valor de esta expresión raramente cae fuera del intervalo [0.5, 2]. Normalmente, la reubicación acostumbra a dar estados de mayor coste de enrutamiento, con lo que el valor será habitualmente mayor que 1. Finalmente, el tercer sumando recoge la ocupación en tanto por uno de la red modificada. Este valor estará comprendido entre 0 y 1, hecho que lo convierte en el tercer criterio de minimización en orden de impacto sobre el coste total de la función objetivo. 31 Capítulo 4 Ejemplos de resolución exacta del problema En este capítulo se plantean dos ejemplos de redes ópticas diferentes con diversos escenarios de tráfico, para los cuales se aplicará la solución exacta al problema de liberación de recursos ópticos. Posteriormente, se analizarán las características de las soluciones obtenidas. 4.1 – Definición de ejemplos de red 4.1.1 – Topología de prueba La primera topología presentada es la llamada “red de prueba”. Las características principales de esta red son las siguientes: Tabla 4.1 – Características de la red de prueba CAPA ÓPTICA Nodos físicos 7 Grado Nodal Medio 1,5 CAPA DE AGREGACIÓN ELÉCTRICA 32 Grado Paralelismo Medio 1,5 ESTRUCTURA RESULTANTE MAXIMAL Nodos reales y virtuales 19 Arcos ópticos 26 Grado Nodal Medio Combinado 2,25 Enlaces entre nodos reales 14 La red a nivel de capa de agregación eléctrica puede tener más de un arco óptico entre el mismo par de nodos. Cuando ocurre eso, decimos que los arcos son paralelos. Para poder diferenciar dos arcos paralelos que tienen el mismo nodo origen y destino, se crean nodos intermedios virtuales, para poder distinguir el paralelismo. En la situación maximal (cuando el tráfico llega a la máxima intensidad), se llegan a generar hasta 26 arcos ópticos entre nodos reales y virtuales. Si tenemos en cuenta que las peticiones de conexión sólo se generan entre nodos reales, existen 14 enlaces distintos entre arcos de la red, 12 de los cuales son paralelos con algún otro. La figura 4.1 muestra este estado maximal de la red a nivel de la capa de agregación eléctrica: Fig. 4.1 – Red de prueba simulada 33 Los nodos marcados numerados del 1 al 7 son imagen de los nodos de la capa óptica, mientras que el resto son virtuales y se han creado para poder diferenciar arcos ópticos paralelos entre el mismo par de nodos. Las características básicas de los arcos ópticos generados son: Tabla 4.2 – Características arcos de la red de prueba Capacidad (en unidades de ancho de banda) 16 Coste mínimo (por recursos ópticos utilizados) 1 Coste máximo (por recursos ópticos utilizados) 7 El coste de los arcos depende de los recursos ópticos que lo forman en la capa óptica. Se ha utilizado una escala de valores enteros entre 1 y 7 para caracterizar la magnitud y la complejidad de la estructura de las interfaces utilizadas. La estructura de esta red de prueba tiene una dimensión amable para el tratamiento con metodología exacta. De todas maneras, el tamaño es lo suficientemente grande como para sacar conclusiones de análisis válidas para casos reales. 4.1.2 – Topología Europea La segunda red definida muestra una topología de dimensión significativamente mayor respecto la anterior. Se ha tomado como modelo una topología determinada de red europea caracterizada para aplicación de escenarios en redes ópticas [4], y a partir de las especificaciones tomadas se ha simulado una red de similares características. Las más importantes son las siguientes: Tabla 4.4 – Características de la red europea PLANO ÓPTICO Nodos físicos 16 Grado Nodal Medio 2,5 PLANO DE CONTROL Grado Paralelismo Medio 2 40 4.2.3 – Análisis del tiempo de computación Un primer análisis es el del tiempo medio invertido por instancia para resolver el problema computacionalmente. Las gráficas obtenidas forman la figura 4.5: Tiempo Resolución vs % Ocupación 0 0,5 1 1,5 2 2,5 3 3,5 <20 20-30 30-40 40-50 50-60 60-70 70-80 >80 % ocupación tiempo (en seg) Tiempo Resolución vs Intensidad de Tráfico 0,00 0,20 0,40 0,60 0,80 1,00 1,20 1,40 1,60 1,80 2,00 baja media alta Intensidad tráfico tiempo (en seg) Fig. 4.5 – Tiempo de computación CPLEX para red de prueba A simple vista de las gráficas pueden observarse dos comportamientos que tienen una justificación lógica: 1) El aumento de la ocupación de los arcos hace incrementar el tiempo de computación, excepto para valores muy altos de ésta, para los cuales el tiempo invertido decrece. Esto puede justificarse si analizamos lo que pasa en los 41 valores extremos de ocupación. Cuando hay poca ocupación, existen pocos cambios posibles a considerar que provoquen mejora, ya que habrá pocas conexiones que tener en cuenta para redistribuir. Eso reducirá bastante el entorno de exploración y, con ello, el tiempo de búsqueda de solución. Por otra parte, en casos de mucha saturación, a pesar de existir muchas conexiones, la cantidad de movimientos permitidos factibles también es baja, lo que también reduce las posibilidades de búsqueda. Con ocupaciones medias-altas, la cantidad de movimientos posibles (arcos susceptibles de eliminarse y rutas alternativas posibles) es mayor porque existe más holgura para optimizar un escenario de tráfico. De ahí que salgan los tiempos de computación más altos. No obstante, como consideración definitiva, vamos a asegurar una clara tendencia creciente del tiempo de computación en la línea de crecimiento de la ocupación óptica. Para casos de ocupación cercanos a la saturación, situación que a la práctica trataremos de evitar, se debería hacer un estudio más detallado de la evolución de tiempos de ejecución. 2) El tiempo de ejecución aumenta significativamente al aumentar la cantidad de conexiones eléctricas generadas. Un mayor tráfico implica una mayor dimensión del problema (tanto en conexiones eléctricas como en arcos ópticos activos). Eso hace incrementar el tamaño de restricciones y variables del problema. A partir de la formulación del problema, podemos calcular la dimensión del problema: Num. Variables Max Rutas x Conexiones eléctricas + 2 x Arcos ópticos Num. Restricciones 4 x Conexiones eléctricas + 2 x Arcos ópticos Así, vemos como la intensidad de tráfico genera diferentes tamaños de problema, que tienen tiempos diferentes de resolución exacta. 4.2.4 – Análisis de las modificaciones producidas 42 Una nueva solución obtenida produce una serie de cambios respecto a la situación original, antes de aplicar el proceso de optimización. Esas modificaciones se dividen en arcos ópticos eliminados y en rutas de conexiones modificadas. Para la agrupación por categorías de ocupación de la red óptica, tenemos los siguientes porcentajes de elementos modificados: Movimientos vs % ocupación óptica 0 10 20 30 40 50 60 70 <20 20-30 30-40 40-50 50-60 60-70 70-80 >80 % ocupación % Arcos ópticos eliminados Conexiones modificadas Fig. 4.6 – Movimientos realizados por ocupación Podemos observar como para valores de ocupación medios (entre 30% y 50%) se producen los porcentajes más elevados de modificación de elementos. La mayor eliminación de arcos ópticos se produce cerca del 30% de ocupación, en la que se llegan a liberar hasta un 50% de los arcos ópticos de la red. A medida que la ocupación se hace mayor, cada vez son menos los arcos que se pueden eliminar, puesto que cada vez cuesta más satisfacer la factibilidad de una ruta alternativa para el total de conexiones del arco a eliminar. Este incremento de conexiones circulantes por arco aumenta la probabilidad de que alguna de ellas no pueda ser reenrutada por falta de capacidad alternativa, hecho que anula la eliminación del arco. Por lo que respecta a cambios en las rutas, en los escenarios de mayor movilidad, llegan a redistribuirse hasta un 60% de las conexiones establecidas. Los escenarios de ocupación media ofrecen la posibilidad de realizar una buena compactación de las 43 conexiones eléctricas, puesto que suelen ser escenarios con una topología óptica caracterizados por tener un número alto de arcos y una ocupación media. Comparamos ahora los resultados agrupados por intensidad de tráfico: Modificaciones vs intensidad de tráfico 0 10 20 30 40 50 60 baja media alta intensidad tráfico % arcos eliminados conexiones modificadas Fig. 4.7 – Movimientos realizados por intensidad Vemos una clara tendencia lineal con pendiente negativa en intensidades crecientes de tráfico para el porcentaje de arcos ópticos eliminados. Una mayor saturación de la red proporciona una clara disminución de los arcos ópticos eliminados respecto a la estructura inicial. Las modificaciones en las rutas siguen una interpretación similar a la realizada en la agrupación por intervalos de ocupación óptica. 4.2.5 – Conclusiones De la aplicación del problema de optimización de interfaces ópticas en diversos escenarios de tráfico sobre una red de prueba de dimensión reducida, se pueden extraer, a la vista de los resultados, dos conclusiones evidentes: A) La eliminación de arcos ópticos es claramente significativa, produciendo un beneficio asociado a la liberación de los recursos ópticos que ocupan. Esta 44 eliminación se sitúa para escenarios de tráfico altamente dinámicos entre un 25% y un 50% dependiendo de la ocupación eléctrica de los arcos ópticos. B) El tiempo de resolución de estas instancias crece con el aumento de la intensidad de tráfico, debido a que esta propicia un aumento significativo de la dimensión del problema optimizado. 4.3 – Resolución exacta sobre red europea 4.3.1 – Características de la implementación Para esta batería de pruebas se ha utilizado el mismo equipo que en el ejemplo de prueba. La configuración del motor de resolución exacta que se ha empleado se caracteriza por haber usado un valor de espacio entre la solución lineal relajada y la solución incumbente entera (MIP gap) del 0,01% 4.3.2 – Resumen de resultados La siguiente tabla muestra los resultados más relevantes para las 100 instancias de tráfico generadas : Tabla 4.9 – Resultados CPLEX red europea id Arcos ópticos Conexiones eléctricas Var. Restr. Ocupación óptica f. obj. Arcos eliminados Conexiones enrutadas Tiempo ejecución 1 27 9 963 90 0,28 -12976 9 4 0,06 2 41 11 1193 126 0,15 -33944 21 8 0,05 3 34 13 1381 120 0,22 -11979 10 4 0,02 4 43 15 1601 146 0,28 -25940 22 9 0,05 5 43 17 1803 154 0,27 -36952 16 9 0,41 6 47 19 2013 170 0,21 -45904 25 12 0,77 7 49 21 2219 182 0,3 -32912 21 13 0,27 8 42 23 2407 176 0,33 -39896 22 13 0,75 9 54 25 2633 208 0,3 -54890 26 15 2,02 10 59 27 2845 226 0,35 -48895 29 16 8,69 11 58 29 3045 232 0,33 -51889 28 16 57,13 12 64 31 3259 252 0,31 -59859 36 20 11,55 13 65 33 3463 262 0,28 -81827 39 25 37,56 14 67 35 3669 274 0,32 -64834 34 23 89,22 15 65 37 3867 278 0,27 -56821 37 24 27,86 45 16 69 39 4077 294 0,37 -57864 35 21 79,8 17 75 41 4291 314 0,27 -73837 45 26 196,17 18 76 43 4495 324 0,39 -72811 40 27 356,69 19 68 45 4681 316 0,39 -52859 31 19 622,55 20 78 47 4903 344 0,5 -74763 39 33 2452,63 21 85 49 5119 366 0,41 -77762 46 32 3491,44 22 68 51 5287 340 0,42 -52846 29 24 488,61 23 83 52 5418 374 0,38 -88778 44 36 4055,25 24 75 55 5705 370 0,51 -58815 32 28 525,33 25 83 56 5822 390 0,41 -83741 47 39 2107 26 84 58 6026 400 0,38 -80791 44 34 43273,66 27 79 61 6319 402 0,49 -63766 34 34 14020,02 28 85 68 7038 442 0,5 -81721 43 41 53796,94 … A partir de este punto, apenas se obtienen instancias resueltas, ya que la mayoría agotan los recursos de la máquina utilizada. Los pocos resultados que se tienen superan las 20 horas de ejecución. Por eso, haremos análisis con sólo las 28 instancias que se detallan arriba. Los siguientes apartados tratan de analizar los mismos aspectos estudiados en la red de prueba, a pesar de no tener disponibilidad de datos en la totalidad del mismo rango 4.3.3 – Análisis del tiempo de computación En el resumen anterior, podemos ver valores de resolución que oscilan entre centésimas de segundo y varias horas. Las gráficas de la figura 4.8 muestran el tiempo medio de resolución por ocupación de la red y por intensidad de tráfico, en los intervalos para los que se disponen datos: Existen valores para ocupaciones inferiores al 30% y para intensidad de tráfico baja, pero son tan pequeños en comparación con el resto, que no casi no son perceptibles visualmente en la escala definida. Para intensidad de tráfico elevada, no hay registros de tiempo medio. 46 Tiempo Resolución vs % Ocupación 0 2000 4000 6000 8000 10000 12000 14000 16000 18000 20000 <20 20-30 30-40 40-50 50-60 % ocupación tiempo (en seg) Tiempo Resolución vs Intensidad de Tráfico 0 2000 4000 6000 8000 10000 12000 14000 16000 baja media Intensidad tráfico tiempo (en seg) Fig. 4.8 – Tiempo de ejecución en red europea Podemos ver que el incremento de ocupación y de tráfico provoca un elevado incremento del tiempo de computación, hasta valores que no son admisibles para el contexto en el que estamos trabajando. A priori, parece razonable considerar que el tiempo de computación crece exponencialmente con la complejidad del problema. La gráfica de la figura 4.9 muestra la nube de dispersión para el logaritmo del tiempo de resolución de cada instancia en relación al número de restricciones del problema. En ella podemos ver que existe una significativa relación lineal que nos certifica que el tiempo de resolución del problema exacto crece de forma exponencial a medida que la dimensión del problema aumenta. 47 Tiempo vs Dimensión y = 0,0188x - 3,4927 R 2 = 0,9603 -3 -2 -1 0 1 2 3 4 5 6 0 50 100 150 200 250 300 350 400 450 500 nº restricciones log(tiempo) Fig. 4.9 – Tiempo de ejecución vs. nº restricciones 4.3.4 – Análisis de las modificaciones producidas Por lo que respecta al efecto de la optimización sobre los elementos de la solución, las próximas gráficas comparativas muestran los resultados. Vemos que existe un patrón bastante claro y poco variable respecto a los criterios de agrupación de datos. Para diferentes ocupaciones de tráfico y para distintas intensidades de tráfico, el porcentaje de arcos ópticos eliminados oscila en general entre el 40% y el 50%, mientras que el porcentaje de conexiones eléctricas modificadas se sitúa mayoritariamente entre el 50% y el 60%. Modificaciones vs % Ocupación óptica 0 10 20 30 40 50 60 70 80 <20 20-30 30-40 40-50 50-60 % ocupación % Arcos ópticos eliminados Conexiones modificadas Fig. 4.10 – Modificaciones realizadas por ocupación 48 Modificaciones vs intensidad de tráfico 0 10 20 30 40 50 60 70 baja media intensidad tráfico % elementos arcos eliminados conexiones modificadas Fig. 4.11 – Modificaciones realizadas por intensidad El porcentaje de arcos eliminados respecto a la red original es muy similar con respecto al resultado obtenido en las instancias de la red de prueba. En cuanto a las conexiones modificadas, para valores medios de ocupación, los resultados se asemejan considerablemente. 4.3.5 – Conclusiones En este escenario también podemos sacar dos conclusiones claras: A) La liberación de recursos ópticos es claramente efectiva y provoca un beneficio significativo en el contexto de mejor aprovechamiento de recursos ópticos. Además, los resultados obtenidos son similares a los de la red de prueba. B) El método exacto para problemas de una dimensión real no es eficiente para resolver el problema en un tiempo que permita su aplicación a la práctica, sin que haya modificado el escenario de aplicación. Muchas de las instancias de máxima intensidad de tráfico no han podido ser resueltas y otras lo han sido con tiempos demasiado grandes. 49 Capítulo 5 Meta-heurística GRASP Ciertos problemas de optimización tienen una estructura y una dimensión que dificultan la resolución a partir de procedimientos exactos. En el capítulo anterior hemos visto que, en determinados escenarios de tráfico, la resolución óptima del problema de liberación de recursos ópticos se obtenía con tiempos inadmisibles para poder llevarse a cabo en la realidad. En otros casos, la cantidad de conexiones y rutas posibles se hacía tan grande que un ordenador potente se quedaba sin memoria y no podía resolver el ejemplo. Para estos escenarios, que se pueden dar en situaciones reales, no se pueden aplicar procedimientos de resolución exactos porque no conseguimos el propósito de mejorar el tráfico de la red de forma rápida y efectiva. Existen procedimientos de resolución aproximados, llamados heurísticas o metaheurísticas, que permiten obtener buenas soluciones de los problemas planteados, con un coste computacional admisible. Si bien estos procedimientos no aseguran la obtención de la solución óptima para cada aplicación, permiten dar con soluciones que cubren las necesidades de mejora que los mecanismos exactos no pueden otorgar de forma eficiente. 56 Esta lista de posibilidades se llama lista de candidatos restringida (en inglés, Restricted Candidate List, RCL). Dada una iteración de la fase constructiva, definimos F como el conjunto total de elementos f i que pueden incorporarse en esa iteración a la solución en construcción. Complementariamente, para cada elemento obtendremos el coste C(f i ) como el valor que aumentaría la función de evaluación si se incorporara ese elemento a la solución. Finalmente, definimos Cfmax y Cfmin, como el máximo y mínimo valor de coste del conjunto de candidatos, respectivamente. Así pues, tenemos que la RCL queda definida de la siguiente manera:      ∈∀−×+≤≡ FfCfminCfmaxCfminfCfRCL iii ),()(| α El parámetro α nos determina la frontera de los valores que serán incorporados a la lista de candidatos. Podemos ver cual es la lista de candidatos para los valores extremos de α , con la notación presentada: • α =0 → CfminFfCfminfCfRCL iii ≡      ∈∀≤≡ ,)(| • α =1→ ≡      ∈∀−+≤≡ FfCfminCfmaxCfminfCfRCL iii ),()(| FFfCfmaxfCf iii ≡      ∈∀≤ ,)(| Visto esto, el pseudocódigo de esta fase constructiva queda detallado de la siguiente manera, en el algoritmo 5.2. El primer paso dentro del bucle iterativo es determinar el conjunto de posibles elementos que pueden entrar a formar parte de la solución sin restricciones de coste. Este conjunto lo obtenemos a partir de los datos del problema y lo llamaremos F. En segundo lugar, obtenemos la lista restringida de candidatos a partir de ese conjunto F y del parámetro fijado α . Tras la obtención de un valor aleatorio uniformemente distribuido entre 0 y 1, obtenemos el índice de la RCL del elemento que vamos a incorporar a la solución. Finalmente, concluimos la iteración añadiendo ese elemento al conjunto solución en construcción. 57 Algoritmo 5.2 – Fase Constructiva alg S := FASE I (param P, param α) var S=Ø; var ite=1; mientras (RCL ≠ Ø || ite=1) hacer F:= P[ite]; RCL:= {f i | C(f i ) ≤ Cfmin+α(Cfmax-Cfmin), f i Є F}; L:= |RCL|; pos:= truncar(U[0,1]*L)+1; f selec := RLC[pos]; S:= S + {f selec }; fmientras falg 5.2.3 – Fase II o fase de mejora local El objetivo de esta fase es mejorar la solución obtenida en la fase constructiva, obteniendo una solución derivada que tenga una mejor evaluación de la función objetivo. Las soluciones obtenidas en la fase constructiva no suelen ser óptimos locales, con lo que podemos intentar encontrar la solución del óptimo local más próximo a la solución constructiva. Deberemos definir dos conceptos clave en esta fase: 1) Entorno local: Dada una solución S, podemos definir el entorno N(S) como el conjunto de soluciones alternativas “próximas” a la solución S inicial. Ese entorno queda definido por el criterio de elección de soluciones alternativas. Por ejemplo, podemos definir el entorno N(S) como el conjunto de soluciones que difieran de la solución S en un único elemento. Este procedimiento se conoce por método de intercambios simples, ya que se puede obtener la solución S’, a partir de eliminar un elemento de S e introducir uno que no estuviera en la solución de partida. 2) Criterio de avance: En un entorno de búsqueda local, debemos movernos para poder llegar al deseado mínimo local. Para eso, deberemos elegir alguna de las soluciones del entorno local siguiendo algún criterio que nos aproxime a ese punto. El más usual es la evaluación de la función objetivo en las soluciones del entorno de búsqueda. Sea cual sea el método de generación del entorno, al 58 encontrar una solución alternativa, ésta se evalúa en la función objetivo del problema y si el resultado es mejor que el de la solución de partida, se toma la nueva solución como incumbente. A partir de los puntos de avance obtenidos, seguiremos calculando entornos de búsqueda y realizando movimientos, hasta llegar a un punto de equilibrio, en el que no podamos realizar ningún movimiento satisfactorio con las premisas aceptadas. Entonces, aceptaremos estar en un mínimo local. Solución inicial constructiva Entorno de búsqueda local Dirección de movimiento Óptimo local conseguido fig 5.4 – Avance en el entorno de búsqueda y llegada al óptimo local El pseudocódigo de esta fase es el siguiente: Algoritmo 5.3 – Fase de mejora alg S’ := FASE II (param P, param S, param metodo) var mejora=’verdadero’; var S’=S; mientras (mejora) hacer mejora:=’falso’; entorno:=N(S’,P); S^ <- entorno(metodo); si C(S^)<C(S’) hacer S’:=S^; mejora:=’verdadero’; fsi fmientras falg 59 Esta fase de mejora se realiza a partir de una solución S inicial y un conjunto de datos P del problema. Pero también hay que definir que método escoger para realizar la búsqueda de actualizaciones en el entorno vecino. Las estrategias más utilizadas son: • Best-improving: una vez definido el entorno de exploración, valoramos todas las opciones posibles y seleccionamos la mejor de ellas. • First-improving: al realizar la exploración y encontrar la primera de las soluciones alternativas que mejora el coste total, actualizamos la solución incumbente y procedemos a una nueva iteración de mejora. La segunda estrategia permite obtener mejoras sin realizar una exploración exhaustiva y computacionalmente más costosa. Por otra parte, la primera permite realizar el mejor movimiento en el entorno local de búsqueda, con el precio añadido de una mayor complejidad algorítmica. Cabe decir que existe la posibilidad de prescindir de esta fase de mejora, debido al coste computacional que comporta y a la, a veces, poca mejoría que implica sobre la solución incumbente constructiva [6]. 5.2.3 – Acción combinada de las dos fases La combinación de una fase constructiva aleatoria que nos lleva a distintos puntos del espacio de soluciones factibles que pueden estar lejanos entre sí, y de una fase de mejora que traslada la solución a un óptimo local del entorno inmediato de la solución, permiten obtener un rastreo bastante amplio del espectro de soluciones factibles localmente óptimas. Esto nos da la posibilidad de obtener en una de estas iteraciones la solución óptima global. Al ser un procedimiento que memoriza la mejor solución obtenida, queda claro que si damos con la solución óptima del problema en alguna de las iteraciones intermedias, la recuperaremos al finalizar el algoritmo. 5.3 – Ajuste y sensibilidad de parámetros Esta metaheurística tiene dos parámetros ajustables que hay que fijar previamente a cualquier ejecución: el parámetro de aleatorización α y el criterio de parada utilizado. En las siguientes líneas, se plantea la necesidad de estudiar la mejor combinación de 60 ambos para poder dar con resultados satisfactorios, tanto a nivel de optimización relativa como de computación. 5.3.1 – Análisis de sensibilidad del parámetro α En el punto 4.2.2 vimos como este parámetro determina la composición de la lista restringida de candidatos de la fase constructiva, a partir de la definición de la RCL en los valores 0 y 1 de α. Si aumentamos desde 0 este valor, asumimos cada vez un mayor rango de los elementos elegibles en cada iteración. Como los elementos se ordenan según el criterio voraz definido, la selección aleatoria en una lista de poca extensión nos escogerá un elemento con buenas propiedades locales. Hay un cierto valor de α que nos proporcionará una amplitud de posibilidades lo suficientemente grande como para incluir soluciones lejanas buenas, y lo suficientemente concreta como para que lleguemos a dar con esas soluciones en pocas iteraciones. Esto suele suceder en los valores de α comprendidos en el intervalo [0.4, 0.6]. A partir de esos valores, el incremento del parámetro hará que la lista de candidatos se haga demasiado grande y las posibles soluciones sean muchas y muy diversas. Eso nos amplia tanto el rango de exploración que las soluciones factibles obtenidas en cada iteración son muy diferentes, haciendo muy poco eficiente la aplicación iterativa. De todas maneras, al aumentar la cantidad de posibilidades de elección, aumentamos la probabilidad de dar con mejores soluciones, de tal manera que para un número muy grande de iteraciones (de hecho, para un valor teóricamente ilimitado), llegaríamos a dar con soluciones de menor coste. Las figuras 5.5 y 5.6 ejemplifican lo dicho anteriormente: la primera muestra la teórica mejor solución incumbente obtenida para diferentes valores de α con un número de iteraciones muy grande; la segunda muestra un patrón clásico de evolución de la solución incumbente dados diferentes valores del parámetro α, en tantos experimentos del mismo problema, con un número máximo de iteraciones pequeño. 61 0 0,2 0,4 0,6 0,8 1 1,2 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 Parámetro alfa Valor F.O. Mejor Solución Encontrada Óptimo Global fig.5. 5 – F.O. vs. Alfa, límite iteraciones alto 0 0,2 0,4 0,6 0,8 1 1,2 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 Parámetro alfa Valor F.O. Mejor Solución encontrada fig.5. 6 – F.O. vs. Alfa, límite iteraciones bajo 5.3.2 – Estudio del criterio de parada La metaheurística GRASP finaliza cuando se cumple un cierto criterio de parada determinado. No es trivial decidir que criterio de parada utilizar, ya que nos condiciona la solución obtenida. En la práctica, el criterio de parada nos limita el número de iteraciones realizadas. Un criterio que permita realizar más iteraciones nos conducirá hacia soluciones mejores, ya que cada iteración genera una solución diferente con coste diferente. Al generarse más soluciones, la probabilidad de obtener una solución mejor aumenta. No obstante, el 62 número de iteraciones necesarias para obtener una solución mejor que la anterior depende del instante de ejecución de la heurística. En las primeras iteraciones, se produce una mayor actualización y mejora de la solución incumbente, respecto a iteraciones posteriores. A medida que vamos realizando iteraciones y acumulamos más terreno explorado, cada vez se producen menos actualizaciones, que provocan una menor reducción relativa de coste. Así que, realizar un número muy grande de iteraciones nos puede provocar que hagamos buena parte de ellas (las últimas) sin provocar mejora efectiva. Y cada iteración cuesta lo mismo computacionalmente. Es por ello necesario encontrar un criterio de parada que permita realizar un número adecuado de iteraciones, con el que lleguemos a una solución muy buena y con un coste computacional aceptable. 0 10 20 30 40 50 60 70 80 90 100 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 Iteraciones realizadas % mejora posible / tiempo ejecución Mejora Acumulada Coste Tiempo ejecución total Fig. 5.7 – Tiempo de optimización invertido y mejor solución encontrada Los dos criterios más utilizados son: A) Número máximo de iteraciones sin actualización: este criterio fija el número máximo de iteraciones que se van a realizar sin que se lleve a cabo ninguna actualización de la solución incumbente. Suponemos que, tras una realización significativa de iteraciones sin cambios, la solución incumbente será difícil de mejorar. Fijar este número máximo de iteraciones es una decisión complicada, que depende del tamaño y características del problema. La figura 5.8 muestra la evolución general del número de iteraciones sin mejora a lo largo de la aplicación de la heurística sobre un ejemplo concreto. 63 0 0,2 0,4 0,6 0,8 1 1,2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 30 30 Iteración Valor F.O. Solución incumbente Fig. 5.8 – Evolución del número de iteraciones sin mejora B) Mínima pendiente de mejora: si suavizamos la gráfica de la evolución de la solución incumbente, podemos obtener una aproximación y calcular la pendiente de descenso. La podemos medir entre el punto de la última solución incumbente obtenida y el punto de la iteración actual. Si este valor no supera una mínima pendiente exigible, la heurística GRASP finaliza. Este criterio tiene sentido ya que, en general, las primeras iteraciones producen modificaciones mayores que las siguientes, de manera que la pendiente de mejora de la función objetivo va disminuyendo a lo largo del proceso iterativo. 0 0,2 0,4 0,6 0,8 1 1,2 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 30 30 Iteración Valor F.O. Solución incumbente Fig. 5.9 – Suavizado de la evolución de la solución incumbente 5.4 – Adaptación de la heurística al problema La adaptación de la meta-heurística general para el problema de adaptación de recursos ópticos se centra en los siguientes aspectos principales. 5.4.1 – Estructura de una solución factible Al final del proceso de optimización, el resultado final debe ser un nuevo escenario de tráfico que cumpla con las condiciones de servicio y restricciones impuestas. Para llegar Ite max. stop Pendiente suavizada 64 a este resultado, se han tenido que producir una serie de cambios en los elementos de la estructura inicial de datos. La caracterización de esos elementos modificados va a ser el contenido de una solución factible a nuestro problema. Así pues, una solución factible va a estar formada por dos clases de elementos: A) Arcos ópticos eliminados: de la red de agregación eléctrica por tener ocupación nula. B) Conexiones eléctricas modificadas: por tener rutas originales con cortes en la ruta óptica. 5.4.2 – Criterio greedy de selección de arcos ópticos candidatos Vamos a definir el criterio voraz para elegir los candidatos a ser eliminados. Nos interesa buscar los arcos ópticos que tengan mayor coste para poder obtener, con cada eliminación, un mayor beneficio en la función objetivo. Por otra parte, eliminar un arco con pocas conexiones eléctricas asociadas será más fácil, a priori que otro con más ocupación Por ello, definiremos un criterio de ordenación jerárquico basado en dos valores: en primer lugar, se escogerán los arcos con menor número de conexiones eléctricas. Para los conjuntos de arcos con igual número de conexiones, y como segundo criterio de ordenación, se ordenaran de mayor a menor coste en recursos ópticos asociados. 5.4.3– Selección de arcos ópticos eliminables Existirá una selección aleatoria que habrá que realizar para determinar que arco óptico es escogido para ser eliminado. Esta elección se hará después de crear la RCL correspondiente, a partir del coste asociado a cada arco. El parámetro que marca el grado de aleatorización de ésta selección se llamará α óptico. 5.4.4– Selección de rutas alternativas de conexiones eléctricas Cuando se elige que arco óptico es el candidato para salir de la red, las conexiones presentes deben enrutarse por caminos alternativos que no contengan el arco óptico seleccionado. Estas rutas se ordenarán mediante el criterio voraz de menor a mayor coste asociado. La selección de la ruta se realizará entre un conjunto de rutas candidatas según el parámetro homólogo al α óptico de este punto, que llamaremos α eléctrico. 65 5.4.5 – Método de mejora Una vez finalizada la fase constructiva aleatorizada, se procederá a una fase de mejora, en la que se aplicará un método de first-improving. Esto nos permite modificar la solución incumbente sin un excesivo coste computacional, un hecho que favorece la implementación y el funcionamiento en situaciones de tráfico real. 5.4.6 – Criterio de parada Para decidir cuándo finaliza el proceso iterativo del GRASP, utilizaremos el criterio de fijar un número máximo de iteraciones sin mejora de la solución incumbente. Este número de iteraciones lo fijaremos en función de los resultados que se obtengan en las baterías de pruebas posteriores. Trataremos de encontrar para diferentes casos un valor que dé buenos resultados con un coste computacional aceptable. Los valores de prueba se van a referir a la dimensión óptica del problema, de tal manera que el máximo número de iteraciones será una fracción del máximo número de arcos ópticos posibles. 5.4.7 – Pseudocódigo de la fase constructiva adaptada Tomando como base el pseudocódigo general de la fase I, la adaptación al problema de liberación de recursos ópticos queda así: Algoritmo 5.4 – Fase de constructiva adaptada alg S := FASE I (param P, param αoptico, param αeléctrico ) var S=Ø; // Conjunto de arcos eliminados var ite=1; mientras (RCL ≠ Ø || ite=1) hacer F:= conjunto de arcos ópticos eliminables RCL:= {f i | C(f i ) ≤ Cfmin+αoptico(Cfmax-Cfmin), f i Є F}; L:= |RCL|; pos:= truncar(U[0,1]*L)+1; f selec := RLC[pos]; eliminararco:=’verdadero’; G := conjunto de c. eléctricas del arco f selec mientras (G ≠ Ø) hacer g := elemento de G R:= conjunto de rutas alternativas de g RCL:= {r i | C(r i ) ≤ Crmin+αelectrico(CrmaxCrmin), r i Є R}; 72 6.1.2 – Resultados en red de prueba La siguiente tabla muestra el resumen de resultados obtenido en las dos variables más significativas para el análisis: Tabla 6.1 – Resultados Greedy prueba % ocupación Tiempo medio Valor F.O. medio 20 0,18 -15961,46 30 0,38 -19255,92 40 0,39 -20246,55 50 0,37 -22884,86 60 0,56 -18875,71 70 0,60 -10880,54 80 0,60 -8440,29 90 0,44 -3452,36 Intensidad tráfico Tiempo medio Valor F.O. medio Baja 0,31 -17212,35 Media 0,51 -15692,51 Alta 0,59 -8236,42 Estos valores se pueden comparar con los obtenidos para la solución de referencia del modelo exacto. El porcentaje de diferencia para las dos variables en la comparación de procedimientos se refleja en la siguiente tabla. Tabla 6.2 – Comparación Greedy/CPLEX % (CPLEX – GREEDY) / CPLEX % ocupación Tiempo medio Valor F.O. medio 20 -1029% 6% 30 -111% 20% 40 10% 9% 50 41% 10% 60 52% 21% 70 81% 31% 80 73% 33% 90 59% 73% Intensidad tráfico Tiempo medio Valor F.O. medio Baja -126% 16% Media 63% 20% Alta 75% 42% 73 La representación gráfica del tiempo medio invertido por intensidad de tráfico nos muestra el incremento del valor de esta variable para problemas de mayor dimensión. Tiempo Resolución vs Intensidad tráfico 0,00 0,10 0,20 0,30 0,40 0,50 0,60 0,70 baja media alta Intensidad tráfico tiempo medio resolución (en seg) Fig 6. 1 – Tiempo de resolución para diferentes intensidades de tráfico Las gráficas siguientes muestran el porcentaje de arcos ópticos eliminados y conexiones eléctricas afectadas por dichas eliminaciones Modificaciones vs Ocupación óptica 0 10 20 30 40 50 60 70 80 20 30 40 50 60 70 80 90 % ocupación % Arcos ópticos eliminados Conexiones modificadas Fig. 6 2 – Movimientos realizados por diferentes ocupaciones 74 Modificaciones vs intensidad de tráfico 0 10 20 30 40 50 60 70 baja media alta intensidad tráfico % elementos arcos eliminados conexiones modificadas Fig. 6. 3 – Movimientos realizados en diferentes intensidades 6.1.3 – Resultados en red europea El resumen de resultados de esta batería de pruebas se presenta en la siguiente tabla: Tabla 6.3 – Resultados Greedy Europea % ocupación Tiempo medio Valor F.O. medio 20 1,81 -30932 30 3,34 -31469 40 5,05 -41025 50 8,40 -50872 60 8,97 -49910 70 10,02 -42739 80 9,15 -31223 90 8,18 -19496 Intensidad tráfico Tiempo medio Valor F.O. medio baja 2,57 -79390 media 7,47 -39943 alta 9,12 -26078 Gráficamente, los elementos modificados en la solución incumbente se reflejan en las figuras 6.4 y 6.5. La evolución del tiempo de resolución por intensidad de tráfico puede verse en la figura 6.6. 75 Modificaciones vs Ocupación óptica 0 10 20 30 40 50 60 70 80 90 20 30 40 50 60 70 80 90 % ocupación % Arcos ópticos eliminados Conexiones modificadas Modificaciones vs intensidad de tráfico 0 10 20 30 40 50 60 70 baja media alta intensidad tráfico % elementos arcos eliminados conexiones modificadas Intensidad de Tráfico vs Tiempo Resolución 0,00 1,00 2,00 3,00 4,00 5,00 6,00 7,00 8,00 9,00 10,00 baja media alta Intensidad tráfico tiempo medio resolución (en seg) figuras 6.4, 6.5 y 6.6– Evolución de los elementos modificados y del tiempo de resolución 76 6.1.4 – Análisis de resultados Comparando los resultados de ambos ejemplos, podemos observar resultados similares, con lo que las conclusiones extraídas pueden ser aplicadas a cualquiera de las situaciones. Como hechos más destacados podemos decir lo siguiente: A) La heurística básica permite obtener una reducción de arcos ópticos entre un 15% y un 50%. Esta reducción produce una liberación de recursos ópticos de similar magnitud, hecho que valida el criterio voraz utilizado. B) El tiempo de ejecución del algoritmo crece de forma prácticamente lineal a medida que aumenta la complejidad del problema. C) La distancia entre la solución óptima y la solución obtenida por la heurística básica aumenta a medida que crece la complejidad del escenario. La diferencia media para los escenarios de la red de prueba se sitúa entorno al 22%. D) El tiempo invertido por el algoritmo heurístico respecto al de la solución exacta disminuye a medida que aumenta la complejidad del problema. El tiempo medio invertido por la heurística reduce en media un 60% el tiempo utilizado por el motor CPLEX. Con todo esto podemos decir que el algoritmo básico aporta una mejora evidente que, en ocasiones, se queda bastante lejos de la solución óptima, pero en cambio tiene una evolución del tiempo de ejecución más favorable que la resolución exacta. 6.2 – GRASP óptico 6.2.1 – Diseño de pruebas Esta versión presenta dos parámetros ajustables, cuyas combinaciones ejecutadas han sido: Parámetro alfa 0,1 ; 0,3 ; 0,5 ; 0,7 ; 0,9 Límite de iteraciones 12 (≈ 50% arcos ópticos) Para cada una de las 5 combinaciones resultantes, se han resuelto las instancias de prueba. Al mantener estable el número de iteraciones, podremos estudiar el impacto 77 neto del parámetro de aleatorización. Del análisis de sensibilidad realizado, se ha escogido la combinación con mejor resultado global respecto a la función objetivo y se ha aplicado esa configuración para la resolución del caso europeo. 6.2.2 – Resultados en red de prueba A continuación se presenta la tabla de resumen de resultados de beneficio obtenido y tiempo invertido por esta versión heurística, en contraste con los valores obtenidos por el algoritmo sin aleatorización. En este aspecto, se presenta la diferencia porcentual respecto a la heurística básica. Tabla 6.4 – Resultados GRASP óptico prueba alfa 0,1 alfa 0,3 ocupación F.O. cmp FO TMP cmp TMP F.O. cmp FO TMP cmp TMP 20 -31922,9 0% 2,2 -529% -33950,9 -6% 3,0 -757% 30 -69804,8 -21% 6,4 -462% -71864,8 -24% 6,1 -432% 40 -60765,7 0% 7,8 -563% -66870,7 -10% 7,6 -541% 50 -73646,6 -7% 8,1 -632% -76639,6 -12% 10,6 -859% 60 -162984,6 -8% 31,6 -608% -177108,7 -17% 39,8 -790% 70 -121938,0 -25% 48,2 -787% -134108,0 -37% 45,1 -731% 80 -156146,6 -16% 64,5 -571% -169426,6 -25% 76,8 -698% 90 -20714,1 0% 17,0 -544% -25765,2 -24% 18,4 -597% intensidad Baja -119642,6 1% 10,7 -391% -123746,6 -3% 11,0 -409% Media -330884,8 -5% 63,7 -527% -357189,8 -14% 82,7 -713% Alta -247395,9 -31% 111,5 -720% -274797,9 -45% 113,6 -735% suma -697923,3 -12% 185,9 -617% -755734,3 -21% 207,4 -699% alfa 0,5 alfa 0,7 ocupación F.O. cmp FO TMP cmp TMP F.O. cmp FO TMP cmp TMP 20 -33950,9 -6% 3,4 -874% -33939,9 -6% 3,3 -834% 30 -71844,8 -24% 6,9 -508% -71853,8 -24% 8,0 -604% 40 -66848,7 -10% 9,9 -741% -66856,7 -10% 11,1 -843% 50 -76630,6 -12% 12,2 -1002% -74650,6 -9% 9,4 -743% 60 -177168,6 -17% 53,4 -1094% -178063,6 -18% 42,8 -857% 70 -134149,9 -37% 45,8 -744% -134104,9 -37% 40,7 -649% 80 -166558,6 -23% 74,4 -674% -166582,6 -23% 82,4 -756% 90 -25765,2 -24% 17,4 -558% -25765,2 -24% 17,4 -559% intensidad Baja -123717,6 -3% 13,0 -497% -123730,6 -3% 13,7 -529% Media -357241,8 -14% 89,7 -782% -356137,8 -13% 83,3 -719% Alta -271957,9 -44% 120,8 -788% -271948,9 -44% 118,1 -768% suma -752917,2 -21% 223,4 -761% -751817,2 -21% 215,0 -729% 78 alfa 0,9 ocupación F.O. cmp FO TMP cmp TMP 20 -33952,9 -6% 3,8 -989% 30 -71854,8 -24% 6,7 -488% 40 -66856,7 -10% 9,5 -708% 50 -71708,6 -4% 7,9 -607% 60 -176137,6 -17% 37,7 -742% 70 -134074,9 -37% 43,7 -706% 80 -169507,6 -26% 75,9 -689% 90 -25765,2 -24% 17,0 -542% intensidad Baja -123744,6 -3% 13,6 -526% Media -351292,8 -12% 73,8 -626% Alta -274820,9 -45% 114,8 -744% suma -749858,3 -20% 202,1 -679% Para determinar que parámetro es el más apropiado, compararemos los resultados anteriores siguiendo un doble criterio: calidad de la solución obtenida y tiempo de ejecución del algoritmo. Nos interesará escoger el que presente una mejor valoración conjunta. Clasificaremos las instancias según un valor relativo para cada uno de los criterios, y obtendremos el producto de ambos como factor de decisión. Este criterio lo hemos escogido arbitrariamente. La gráfica 6.7 muestra los resultados obtenidos. Valoración parámetro alfa óptico 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 0,1 0,3 0,5 0,7 0,9 Alfa óptico % valoración Valoración Mejora Coste Valoración tiempo invertido Valoración doble Fig. 6.7 – Selección del mejor parámetro alfa óptico Podemos observar como un buen valor del parámetro de aleatorización de selección de arcos ópticos ronda el 30%. Tomaremos este valor como referencia para resolver las instancias de la red europea. 79 6.2.3 – Resultados en red europea La configuración de la heurística para el caso europeo es la siguiente: Parámetro alfa óptico 0,3 Límite de iteraciones 10 (≈ 10% arcos ópticos) El límite de iteraciones es proporcionalmente inferior al realizado en el ejemplo de prueba. En una sección posterior analizaremos el efecto de éste parámetro. Por el momento, escogemos este valor para no incrementar en exceso el tiempo de ejecución de las pruebas. Los resultados de esta batería de pruebas con el ajuste del parámetro α=0.3, da el siguiente resumen de resultados. Tabla 6.5 – Resultados GRASP óptico europea GRASP OPT 0.3 % (Greedy – Grasp) / Greedy % ocupación Tiempo medio Valor F.O. medio Tiempo medio Valor F.O. medio 20 10,19 -29944 -463% 3% 30 23,12 -39246 -592% -25% 40 39,69 -49728 -686% -21% 50 86,67 -62427 -932% -23% 60 79,59 -60155 -787% -21% 70 81,03 -50049 -709% -17% 80 73,71 -35839 -706% -15% 90 54,37 -20968 -565% -8% % ocupación Tiempo medio Valor F.O. medio Tiempo medio Valor F.O. medio baja 16,65 -96227 -547% -21% media 68,65 -48269 -819% -21% alta 69,70 -29556 -665% -13% Media -716% -17% Las gráficas representadas en las siguientes figuras muestran la evolución del tiempo de ejecución y de los elementos modificados por la solución. 80 Modificaciones vs Ocupación óptica 0 10 20 30 40 50 60 70 80 20 30 40 50 60 70 80 90 % ocupación % Arcos ópticos eliminados Conexiones modificadas Tiempo Resolución vs Intensidad Tráfico 0 10 20 30 40 50 60 70 80 baja media alta Intensidad tráfico tiempo medio resolución (en seg) º Fig. 6.8 y 6.9 – Características de las soluciones del GRASP óptico 6.2.4 – Análisis de resultados Podemos contrastar como la inclusión de un efecto aleatorio permite mejorar claramente el resultado de la función objetivo. A partir de un valor del parámetro mayor o igual que 0.3 la mejora de coste frente a la versión greedy básica se sitúa entorno a un 20%. Para el ejemplo de la red europea, llegamos a obtener mejoras ligeramente superiores a este valor, situando la media de mejora respecto a la heurística de referencia en un 17%. Por otra parte, al aumentar la complejidad algorítmica y al tratarse de un procedimiento que realiza varias iteraciones, los tiempos de ejecución son sustancialmente mayores 81 que en el caso de referencia, llegando a niveles de incremento superiores al 700% respecto al nivel de base. El patrón de evolución de la solución obtenida es bastante similar en cuanto a tendencia al caso de la heurística básica: la cantidad de elementos modificados decrece y se separa de la solución exacta a medida que incrementa la complejidad del ejemplo, mientras que el tiempo de ejecución aumenta de forma bastante lineal (incluso vemos en el caso europeo un cierto estancamiento). Aunque el tiempo de resolución aumente con este procedimiento aleatorizado, conviene incorporarlo al algoritmo básico para obtener soluciones con una evaluación en la función de coste significativamente mejor. 6.3 – GRASP eléctrico 6.3.1 – Diseño de pruebas En este apartado realizaremos la misma batería de pruebas que hemos descrito para el caso anterior. No obstante, aquí haremos variaciones respecto al parámetro de aleatorización de selección de ruta eléctrica, el llamado parámetro α eléctrico. Se tomaran los mismos valores que para el experimento anterior: Parámetro alfa 0,1 ; 0,3 ; 0,5 ; 0,7 ; 0,9 Límite de iteraciones 12 (≈ 50% arcos ópticos) Como en el caso anterior, la mejor configuración servirá para resolver el ejemplo de red europea. 6.3.2 – Resultados en red de prueba La tabla de resumen de resultados obtenidos comparados con el greedy básico se puede consultar a continuación. 88 20 58,67 -33943 -3141% -10% 30 38,18 -39122 -1043% -24% 40 65,09 -49625 -1189% -21% 50 84,10 -62518 -901% -23% 60 103,76 -60647 -1057% -22% 70 126,09 -48092 -1159% -13% 80 114,05 -37377 -1147% -20% 90 117,40 -22703 -1335% -16% % ocupación Tiempo medio Valor F.O. medio Tiempo medio Valor F.O. medio baja 48,42 -96423 -1781% -21% media 84,32 -48424 -1028% -21% alta 119,18 -30417 -1207% -17% Media -1188% -19% Modificaciones vs Ocupación óptica 0 10 20 30 40 50 60 70 80 20 30 40 50 60 70 80 90 % ocupación % Arcos ópticos eliminados Conexiones modificadas Tiempo Resolución vs Intensidad de Tráfico 0 20 40 60 80 100 120 140 baja media alta Intensidad tráfico tiempo medio resolución (en seg) Fig. 6.14 y6.15 – Características de la versión doble 89 6.4.4 – Análisis de resultados En este apartado podemos ver como la inclusión conjunta de los dos parámetros en la heurística, añadido a un ligero aumento en el máximo de iteraciones del criterio de parada, logra mejorar los resultados respecto la heurística de base en un 19% de media. Este valor es el mejor que hemos obtenido en todas las versiones. El efecto del aumento de las iteraciones es determinante y, a medida que este valor aumenta, la probabilidad de encontrar soluciones de mayor reducción de coste en todos los escenarios aumenta. En contra de este aumento en la calidad de la solución encontrada, aumenta el tiempo de ejecución del procedimiento, con lo que perdemos valoración en el criterio por tiempo invertido. Centrándonos en el tiempo de ejecución medio, podemos tratar de encontrar relación entre esta variable y el número de iteraciones realizadas, para cada versión de la heurística en la aplicación de la red europea. Tabla 6.10 – Comparación tiempo medio por versión Versión nº iteraciones tmp medio tmp / nº ite Greedy 1 7,95 7,95 GRASP óptico 10 63,64 6,36 GRASP eléctrico 10 71,14 7,11 GRASP doble 15 100,09 6,67 Podemos ver que el número de segundos medio por iteración fijada se mantiene entre 6 y 8 segundos, un intervalo considerablemente pequeño, independientemente del método utilizado. De ahí podemos extraer que el tiempo de ejecución del procedimiento aplicado depende prácticamente en exclusividad del número de iteraciones fijadas en el criterio de parada. Si realizamos el mismo análisis para la batería de pruebas del efecto del límite de iteraciones sobre la red de prueba, obtenemos resultados que nos llevan a concluir que el tiempo medio por iteración no es significativamente distinto entre pruebas con diferente número de iteraciones fijado. Finalmente, podemos comprobar como esta heurística da patrones similares en cuanto a evolución lineal del tiempo de resolución y características de los elementos modificados, al resto de versiones heurísticas aplicadas. 90 Tabla 6.11 – Comparación tiempo medio por iteración parada Versión nº iteraciones tmp medio tmp / nº ite ITE 12 12 5,57 0,46 ITE 25 25 10,00 0,40 ITE 50 50 20,94 0,42 91 Capítulo 7 Conclusiones y extensión del trabajo En los capítulos de resolución exacta y resolución heurística de los escenarios, hemos obtenido y analizado distintas soluciones para los mismos ejemplos. En este capítulo se realiza una comparación global de todos los métodos, con la intención de encontrar el más adecuado para resolver el problema de liberación de recursos ópticos en un entorno de gestión de redes ópticas reales. 7.1 – Criterios de valoración del método de resolución El motivo de este estudio es el de encontrar un método de mejora que pueda utilizarse en la gestión real de redes ópticas. Los criterios más importantes son los siguientes: A) Calidad de la solución encontrada: se valora obtener la mejor solución posible, a poder ser la óptima, según las condiciones y restricciones del problema. 92 B) Tiempo de ejecución necesario: se valora positivamente que el procedimiento tarde poco tiempo, ya que se realiza a partir de un escenario dinámico que puede cambiar entre la captura de datos inicial y el retorno de la solución optimizada. C) Integración en el sistema de gestión: se valora la sencillez con la que el sistema de gestión se comunica con el optimizador para intercambiar información. Los métodos evaluados hasta ahora cumplen positivamente alguno de los criterios, en detrimento de tener como punto débil alguno de los otros. En líneas generales podemos comparar el conjunto de métodos heurísticos con la referencia del procedimiento exacto, para poder asignar valoraciones a los criterios definidos. Criterio Método Exacto Métodos Heurísticos Calidad de la solución Mejor solución posible. Este método encuentra el óptimo global del problema. Solución buena, con tendencia a alejarse de la solución óptima a medida que aumenta la dimensión del problema. Tiempo invertido Tiempo exponencialmente creciente con el tamaño del problema. En ejemplos de dimensiones reales, este método necesita un equipo de grandes prestaciones para devolver soluciones, y aún así, las genera en tiempos inadmisibles para los escenarios considerados. Tiempo creciente linealmente con el tamaño del problema. Tiempo ajustable a partir del parámetro del criterio de parada. Posibilidad de equilibrar el tiempo invertido con la calidad de la solución obtenida. 93 Integración Integración compleja. Es necesaria una plataforma externa y un motor de resolución de licencia restringida integrado en esa plataforma. El sistema de gestión debe conectarse con esa plataforma externa para resolver el problema. Integración sencilla, como función o extensión de la implementación del sistema de gestión. 7.2 – Comparación Método exacto vs. Métodos heurísticos Las figuras 7.1 y 7.2 muestran los criterios de calidad de solución y tiempo invertido para la comparación de todos los métodos aplicados sobre la red de prueba y la red europea (en este último caso, comparando sólo las instancias de las que se disponen datos de la resolución exacta). Los resultados se muestran referidos a la solución óptima devuelta por el motor de resolución CPLEX. Podemos sacar varias conclusiones a la vista de las gráficas: 1) El valor óptimo de la función objetivo queda, en media, bastante cerca del alcance de las versiones heurísticas que incorporan procedimientos de selección de elementos aleatoria. A partir de la versión heurística básica, que se sitúa entorno a un 75% de la solución óptima, las versiones aleatorizadas llegan a situarse a tan sólo un 10% de distancia respecto a la mejor solución. 2) El tiempo de ejecución de las heurísticas aumenta a medida que incorporamos elementos de aleatorización y a medida que aumentamos el número de iteraciones del criterio de parada. 3) El tiempo de ejecución de las heurísticas en el caso de la red de tipo europea son más de 10 veces inferiores a los obtenidos por la resolución exacta. 94 Comparación en red de prueba 0% 50% 100% 150% 200% 250% 300% 350% CPLEX Greedy GRASP óptico GRASP eléctrico DUOGRASP % Función objetivo Tiempo invertido fig 7.1 – Comparación de metodologías en red de prueba Comparación en red europea 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% CPLEX Greedy GRASP óptico GRASP eléctrico DUOGRASP % Función objetivo Tiempo invertido fig 7.2 – Comparación de metodologías en red europea Si a estos comentarios, añadimos que la integración de las heurísticas es más sencilla que la del método exacto, podemos ver claramente que cualquier versión heurística aleatorizada que usemos nos dará resultados efectivos, tanto por calidad de solución como por tiempo de generación. Dada la poca utilidad del método exacto para problemas de cierta dimensión, descartaremos este procedimiento como candidato a ser escogido para resolver este problema. 7.3 – Selección de la mejor versión heurística Dados los resultados anteriores, vamos a escoger una versión heurística como la más apropiada para resolver el problema de liberación de recursos ópticos en una situación real. 95 La tabla 7.1 muestra la cantidad de veces que una heurística ha conseguido la mejor solución entre los cuatro métodos heurísticos, en grupos de instancias caracterizadas por el número de restricciones del problema. Los datos se presentan en frecuencias relativas en tanto por uno. Tabla 7.1Comparación entre métodos heurísticos Restricciones Greedy GRASP Óptico GRASP Eléctrico GRASP Doble TOTAL 100-200 0,00 0,50 0,00 0,50 0,08 200-300 0,00 0,50 0,25 0,25 0,08 300-400 0,00 0,67 0,11 0,22 0,09 400-500 0,00 0,33 0,08 0,58 0,12 500-600 0,00 0,50 0,21 0,29 0,14 600-700 0,00 0,50 0,18 0,32 0,22 700-800 0,07 0,30 0,22 0,41 0,27 TOTAL 0,02 0,44 0,17 0,37 1 Podemos ver como en un 44% de las instancias el método GRASP óptico es el mejor, aunque le sigue de cerca el método GRASP doble con un 37% de instancias mejor resueltas. Vemos como el GRASP eléctrico consigue solo mejorar el resto de heurísticas en un 17% de los casos, mientras que el algoritmo básico greedy, apenas resuelve mejor 2 de las 100 instancias. Si miramos los resultados por grupo de restricciones, vemos como las dos heurísticas dominantes presentan buenos resultados en diferentes niveles de dimensión del problema. Visto que el tiempo por iteración realizada es bastante constante para todas las pruebas, este criterio de calidad de la solución se muestra determinante para escoger el mejor método. Dado que el algoritmo GRASP óptico presenta los mejores resultados globales y supone una implementación algo más sencilla que la versión GRASP doble, tomamos esta versión como la mejor de todas cuantas hemos propuesto. 7.4 – Integración de la meta-heurística en el sistema de gestión Una vez escogida la metodología para resolver el problema de liberación de arcos ópticos, procederemos a su implementación en un sistema de gestión de una red real. Este proyecto ha sido realizado como parte de la investigación del Grupo de Comunicaciones Ópticas (GCO) de la UPC, así que la integración se realizará sobre la red de pruebas CARISMA. 96 El proyecto CARISMA comenzó en 2003 con el objetivo de construir una red óptica WDM para ser utilizada como plataforma experimental para la integración y evaluación de las tecnologías ópticas más innovadoras. La red CARISMA ha sido implementada como una red de transporte óptico basada en el estándar ASON [7] de la Unión Internacional de Telecomunicaciones (ITU-T) y está provista de un plano de control GMPLS [8]. El plano de transporte está formado por un anillo óptico de dos fibras y tres nodos ópticos con capacidad de extracción e inserción de canales ópticos. Cada nodo esta equipado con cuatro láseres WDM a 10Gbit/s. Los nodos están localizados en los campus de la UPC en Tarrasa y Barcelona y en TVC en Sant Joan Despi. La distancia total del anillo es de alrededor de 100km. Además de los nodos físicos, se dispone de emuladores de nodo (componente software), con los que es posible realizar pruebas sobre cualquier topología de red. La red CARISMA cuenta además con un sistema de gestión de red que es responsable de la gestión completa del sistema y se encarga de la generación de peticiones de conexión ópticas. Hoy en día, la red CARISMA se utiliza como base experimental dentro de varios proyectos de investigación tanto nacionales como europeos. La heurística seleccionada como mejor método en este capítulo, ha sido probada sobre la red CARISMA configurada con la topología que se muestra en la figura 7.3. Se han generado distintas intensidades de tráfico, para las cuales se han obtenido resultados en línea con los expuestos anteriormente. Como ejemplo, en la figura 7.4 se muestra el porcentaje de modificaciones realizadas sobre la red original para distintos grados de ocupación de la red. Puede observarse que el patrón es muy similar a los obtenidos con los escenarios generados aleatoriamente. Por una parte, obtenemos una eliminación de recursos y una modificación de rutas eléctricas que decrecen a medida que aumenta la ocupación de la red. La cantidad de arcos eliminados se sitúa en el intervalo del 15% al 35% respecto a la red original. 97 Fig. 7.3 – Red de prueba CARISMA Resultados GRASP óptico en red CARISMA 0% 5% 10% 15% 20% 25% 30% 35% 40% 60% 65% 70% 75% 80% 85% 90% 95% 100% Ocupación Red Elementos modificados Arcos Eliminados Conexiones modificadas Fig. 7.4 – Heurística sobre red CARISMA 7.5 – Extensión del proyecto Las consideraciones y definiciones tomadas inicialmente al presentar el problema han sido determinantes para la calidad de las soluciones obtenidas. La cantidad de mejora que hemos podido realizar se ha visto limitada por una serie de restricciones que hemos aplicado, como condición indispensable para el problema propuesto. No obstante, podríamos relajar alguna de estas condiciones para intentar aumentar la cantidad de 104 [FO_2,AE_2,PM_2]=fobjeval(OPT,OPT_2,ELEC,ELEC_2,1000,1,0.001); end tiempo2=tiempo2+cputime-inicio; if FO_2<FO_1 OPT_ITE=OPT_2; ELEC_ITE=ELEC_2; EO_ITE=EO_2; FO_ITE=FO_2; AE_ITE=AE_2; PM_ITE=PM_2; else OPT_ITE=OPT_1; ELEC_ITE=ELEC_1; EO_ITE=EO_1; FO_ITE=FO_1; AE_ITE=AE_1; PM_ITE=PM_1; end if FO_ITE<FO_INC OPT_INC=OPT_ITE; ELEC_INC=ELEC_ITE; EO_INC=EO_ITE; FO_INC=FO_ITE; AE_INC=AE_ITE; PM_INC=PM_ITE; ITE=0; lap_inc=laps; else ITE=ITE+1; end fobj_vct(laps)=FO_INC; end %figure(); %plot(1:laps,fobj_vct,'b-'); Implementación Fase Constructiva function [OPT_INC,ELEC_INC,EO_INC,res,FO_INC,AE_INC,PM_INC]=ORO_FASE1(OPT,ELEC, EO,alfaopt,alfaelec,order) m=size(OPT,1);%Número de arcos ópticos %n=length(FIELDNAMES(ELEC)); Número de conexiones eléctricas ELEC_ORI=ELEC; %Paso 0: Inicializaciones res=fopen('ORO_GRASP_RESULT.txt','w'); BLOQ=zeros(m,1); AE=zeros(m,1); PM=zeros(length(fieldnames(ELEC)),1); %Paso 1: Obtengo la lista de candidatos ordenada según el parámetro alfa OPT_GRASP=graspear(OPT,alfaopt,order); %Lista de arcos ópticos por eliminar OPT_REF=sortrows(OPT,1); %Lista de arcos ópticos ordenados por id 105 %Paso 2: Intento eliminar arcos ópticos pos=1; %Posición de exploración de arco óptico while pos<=m %mientras haya arcos que puedan ser liberados %2.0 - Obtengo id del arco óptico a liberar idopt=OPT_GRASP(pos,1); fprintf(res,'%i) Arco optico: %i - Ocupación: %i\n',pos,idopt,OPT_REF(idopt,4)); if (OPT_REF(idopt,4)>0 && BLOQ(idopt)==0) %si el arco tiene ocupación %2.1 - Obtengo los id de las conexiones eléctricas que pasan por arco %idopt CON=EO(:,idopt); ncon=sum(CON); %Número de conexiones eléctricas que pasan por el arco idopt rcon=0; %Número de conexiones modificadas %Me guardo la información antes de cualquier cambio OPT_INI=OPT_REF; ELEC_AUX=ELEC; welec=zeros(ncon,1); for i=1:length(CON) if CON(i)==1 %Si la conexión i pasa por el arco optico idopt % obtengo información de la conexión electrica idelec=['elec' int2str(i)]; PATHS=getfield(ELEC,idelec,'paths'); bw=getfield(ELEC,idelec,'bandwidth'); ruta=getfield(ELEC,idelec,'ruta'); [c,p]=size(PATHS); fprintf(res,'%i) Reenrutando conexión %i de BW %i ... ',pos,i,bw); % elimino bandwith de los arcos por los que pasa la % conexión for j=4:p if PATHS(ruta,j)>0 OPT_REF(PATHS(ruta,j),4)=OPT_REF(PATHS(ruta,j),4)-bw; OPT_REF(PATHS(ruta,j),8)=OPT_REF(PATHS(ruta,j),8)-1; else break; end end PATHS=graspearpath(PATHS,alfaelec); OPT_VOID=OPT_REF; %Estructura con el arco idopt vacio % reenruto por la más corta disponible for k=1:c r=PATHS(k,1); RUTABUENA=0; if r~=ruta for j=4:p if PATHS(k,j)>0 if (PATHS(k,j)~=idopt && OPT_REF(PATHS(k,j),4)+bw<=OPT_REF(PATHS(k,j),5) && OPT_REF(PATHS(k,j),5)>0) OPT_REF(PATHS(k,j),4)=OPT_REF(PATHS(k,j),4)+bw; OPT_REF(PATHS(k,j),8)=OPT_REF(PATHS(k,j),8)+1; else 106 RUTABUENA=0; break; end else RUTABUENA=1; k_inc=r; break; end end if RUTABUENA==1 %Habremos encontrado una buena ruta break; else OPT_REF=OPT_VOID; end end end if RUTABUENA==0 % Hemos intentado encontrar una ruta alternativa y no la hemos encontrado OPT_REF=OPT_INI; ELEC=ELEC_AUX; BLOQ(idopt)=1; fprintf(res,'%i) KO conexion %i\n',pos, i); break; else rcon=rcon+1; % Aumentamos el contador de conexiones reenrutadas % Modificamos la base de datos de las conexiones ELEC=setfield(ELEC,idelec,'ruta',k_inc); welec(rcon)=i; fprintf(res,'%i) OK conexion %i\n',pos, i); end end end if (ncon==rcon && rcon~=0)%Hemos reenrutado todas las conexiones AE(idopt)=1; for b=1:length(welec) PM(welec(b))=1; end %Eliminamos la capacidad del arco optico idopt OPT_REF(idopt,5)=0; BLOQ(idopt)=1; %Controlamos si tiene un arco paralelo y lo eliminamos if OPT_REF(idopt,7)~=0 OPT_REF(OPT_REF(idopt,7),4:5)=0; end fprintf(res,'%i) Arco eliminado!\n',pos); % Reordenamos otra vez OPT_GRASP=graspear(OPT_REF,alfaopt,order); %Modificamos matriz EO EO(:,idopt)=0; if OPT_REF(idopt,7)~=0 EO(:,OPT_REF(idopt,7))=0; end %Ponemos el marcador de posición a 1 pos=1; 107 fprintf(res,'%i) Arco óptico eliminado: %i \n',pos,idopt); fprintf(res,'%i) Conexiones reenrutadas: ',pos); for o=1:ncon if welec(o)~=0 fprintf(res,'%i ',welec(o)); idelec=['elec' int2str(welec(o))]; ruta=getfield(ELEC,idelec,'ruta'); paths=getfield(ELEC,idelec,'paths'); c=size(paths,1); EO(welec(o),:)=0; for i=4:c if paths(ruta,i)~=0 EO(welec(o),paths(ruta,i))=1; else break; end end else break; end end fprintf(res,'\n\n'); else % Aumentamos el marcador de posición pos=pos+1; OPT_REF=OPT_INI; ELEC=ELEC_AUX; end else %Aseguramos que la capacidad sea 0 if OPT_GRASP(pos,5)>0 && OPT_GRASP(pos,4)==0 OPT_GRASP(pos,5)=0; OPT_REF(idopt,5)=0; end % Aumentamos el marcador de posición fprintf(res,'%i) Arco optico sin ocupación\n',pos) ; pos=pos+1; end end OPT_INC=sortrows(OPT_GRASP,1); ELEC_INC=ELEC; fclose(res); EO_INC=EO; [FO_INC,AE_INC,PM_INC]=fobjeval(OPT,OPT_INC,ELEC_ORI,ELEC_INC,1000,1,0 .001); 108 Implementación Fase de Mejora function [OPT_INC,ELEC_INC,EO]=ORO_FASE2(OPT,OPT_INC,ELEC_INC,EO) OPT_ORI=OPT_INC; ELEC_ORI=ELEC_INC; %1) Creamos los conjuntos INSET y OUTSET m=size(OPT,1); h=0; p=0; for k=1:m if (OPT(k,6)>0 && OPT(k,5)>0 && OPT_INC(k,4)==0) h=h+1; INSET(h,:)=OPT_INC(k,:); if (OPT(k,7)~=0) h=h+1; i=OPT_INC(k,7); INSET(h,:)=OPT_INC(i,:); end end if (OPT_INC(k,6)>0 && OPT_INC(k,5)>0) p=p+1; OUTSET(p,:)=OPT(k,:); if (OPT(k,7)~=0) p=p+1; i=OPT(k,7); OUTSET(p,:)=OPT(i,:); end end end %2) Los ordenamos segun criterio if (h~=0 && p~=0) INSET=sortrows(INSET,6); OUTSET=sortrows(OUTSET,-6); numout=size(OUTSET,1); numin=size(INSET,1); %3) Para cada uno de los arcos candidatos a salir for u=1:numout if OUTSET(u,6)>0 costelim=OUTSET(u,6); idout=OUTSET(u,1); OPT_INI=OPT_INC; % Quitamos el arco de la solución ORIGINAL, eliminando las conexiones % que pasen por el: CON=EO(:,idout); for i=1:length(CON) if CON(i)==1 %Si la conexión i pasa por el arco optico idopt % obtengo información de la conexión electrica idelec=['elec' int2str(i)]; PATHS=getfield(ELEC_INC,idelec,'paths'); 109 bw=getfield(ELEC_INC,idelec,'bandwidth'); ruta=getfield(ELEC_INC,idelec,'ruta'); [c,p]=size(PATHS); % elimino bandwith de los arcos por los que pasa la conexión for j=4:p if PATHS(ruta,j)>0 OPT_INC(PATHS(ruta,j),4)=OPT_INC(PATHS(ruta,j),4)-bw; OPT_INC(PATHS(ruta,j),8)=OPT_INC(PATHS(ruta,j),8)-1; else break; end end end end OPT_INC(idout,5)=0; g=OPT_INC(idout,7); if g~=0 OPT_INC(g,5)=0; end OPT_AUX=OPT_INC; OPT_BK=OPT_INC; ELEC_AUX=ELEC_INC; hecho=0; for h=1:numin if (INSET(h,6)<costelim && INSET(h,6)>0) idin=INSET(h,1); % Activamos arco OPT_INC(idin,5)=OPT(idin,5); g=OPT_INC(idin,7); if g~=0 OPT_INC(g,5)=OPT(g,5); end % Tratamos de meter las conexiones rcon=0; for i=1:length(CON) if CON(i)==1 %Si la conexión i pasa por el arco optico idopt % obtengo información de la conexión electrica idelec=['elec' int2str(i)]; PATHS=getfield(ELEC_INC,idelec,'paths'); bw=getfield(ELEC_INC,idelec,'bandwidth'); [c,p]=size(PATHS); for k=1:c RUTABUENA=0; for j=4:p if PATHS(k,j)>0 if (OPT_INC(PATHS(k,j),4)+bw<=OPT_INC(PATHS(k,j),5)) OPT_INC(PATHS(k,j),4)=OPT_INC(PATHS(k,j),4)+bw; OPT_INC(PATHS(k,j),8)=OPT_INC(PATHS(k,j),8)+1; else RUTABUENA=0; break; end 110 else RUTABUENA=1; k_inc=k; break; end end if RUTABUENA==1 %Habremos encontrado una buena ruta break; else OPT_INC=OPT_AUX; end end if RUTABUENA==0 % Hemos intentado encontrar una ruta alternativa y no la hemos encontrado OPT_INC=OPT_AUX; ELEC_INC=ELEC_AUX; break; else rcon=rcon+1; % Aumentamos el contador de conexiones reenrutadas % Modificamos la base de datos de las conexiones ELEC_INC=setfield(ELEC_INC,idelec,'ruta',k_inc); welec(rcon)=i; OPT_AUX=OPT_INC; end end end if (rcon==sum(CON) && rcon~=0) OPT_INC(idout,5)=0; %Controlamos si tiene un arco paralelo y lo eliminamos if OPT_INC(idout,7)~=0 OPT_INC(OPT_INC(idout,7),4:5)=0; end EO(:,idout)=0; if OPT_INC(idout,7)~=0 EO(:,OPT_INC(idout,7))=0; end for o=1:sum(CON) if welec(o)~=0 idelec=['elec' int2str(welec(o))]; ruta=getfield(ELEC_INC,idelec,'ruta'); paths=getfield(ELEC_INC,idelec,'paths'); c=size(paths,1); EO(welec(o),:)=0; for i=4:c if paths(ruta,i)~=0 EO(welec(o),paths(ruta,i))=1; else break; end end else 111 break; end end INSET(h,6)=inf; OUTSET(u,6)=0; hecho=1 break; else OPT_INC=OPT_BK; ELEC_INC=ELEC_AUX; end end end if hecho==0 OPT_INC=OPT_INI; end end end end