Aplicaciones en la industria del problema de Steiner y su resolución mediante algoritmos genéticos

Proyecto Fin de Grado Ingeniería de las Tecnologías Industriales Aplicaciones en la industria del problema de Steiner y su resolución mediante algoritmos genéticos Autor: Virginia Martínez Lacañina Tutor: Pablo Cortés Achedad Dep. Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 ii iii Proyecto Fin de Grado Ingeniería de las Tecnologías Industriales Aplicaciones en la industria del problema de Steiner y su resolución mediante algoritmos genéticos Autor: Virginia Martínez Lacañina Tutor: Pablo Cortés Achedad Catedrático Departamento de Organización Industrial y Gestión de Empresas II Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2018 iv v Proyecto Fin de Carrera: Aplicaciones en la industria del problema de Steiner y su resolución mediante algoritmos genéticos Autor: Virginia Martínez Lacañina Tutor: Pablo Cortés Abadía El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: vi Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2018 El Secretario del Tribunal vii A mi familia A mis maestros viii ix AGRADECIMIENTOS Los ejercicios resueltos al final de este documento han sido obtenidos del “Imperial College” de Londres del cual se está muy agradecido. Ya que sin esos problemas hubiera sido más complicado el estudio del problema de Steiner seguido en este trabajo de carrera. Por otro lado, la labor desarrollada por todas las personas interesadas en el problema de Steiner y sus aplicaciones han hecho posibles este trabajo en el cual se han incorporado muchas de sus ideologías y teorías. También hacer mención a todos los profesores del departamento de Organización Industrial y Gestión de Empresas II de la Escuela Técnica Superior de la Universidad de Sevilla. Con ellos, mi interés por la optimización y modelado de problemas se ha formado y gracias a ellos se ha podido llevar a cabo este proyecto. Finalmente, especial atención a Pablo Cortés Achedad, tutor y pilar de este proyecto. Sin él hubiese sido imposible realizar un trabajo tan minucioso y cuidado. Estoy muy agradecida por su implicación y orientación. Virginia Martínez Sevilla, 2018 xvi xvii Índice de Figuras Figura 1. Visualización puentes de Königsberg 1 Figura 2. Solución de Torricelli al problema de Fermat 2 Figura 3. Ejemplo árbol de Steiner 7 Figura 4. MST vs. SMT 9 Figura 5. Otro ejemplo MST vs. SMT 9 Figura 6. Solución árbol de Steiner rectilíneo 10 Figura 7. Paso 1 Spanning Tree Formulation 13 Figura 8. Paso 2 Spanning Tree Formulation 13 Figura 9. Paso 3 Spanning Tree Formulation 14 Figura 10. Final Spanning Tree Formulation 15 Figura 11. Ejemplo Flow Formulation 15 Figura 12. Ejemplo resolución Flow Formulation 17 Figura 13. Continuación ejemplo resolución Flow Formulation 17 Figura 14. Mapa España con solución del SMT 23 Figura 15. Esquema de mina subterránea 24 Figura 16. Procedimiento SMT para ciudades estadounidenses 26 Figura 17. Ejemplo red de sensores Wi-Fi 27 Figura 18. Ejemplo red de enrutamiento multicast 28 Figura 19. Solución de los pines 30 Figura 20. Foto real de un microship 30 Figura 21. Estructura aminoácido 31 Figura 22. Ejemplo árbol filogénico 32 Figura 23. Red de personas utilizadas en el marketing viral 34 Figura 24. Ejemplo vuelo Múnich-Sídney 35 Figura 25. Ejemplo acciones posibles de ser incluidas en una cartera de inversión 36 Figura 26. Acciones del mercado de valores de Corea 36 Figura 27. Ejemplo Algoritmo de Kruskal 41 Figura 28. Primer paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 41 Figura 29. Segundo paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 42 Figura 30. Tercer paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 42 xviii Figura 31. Cuarto paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 42 Figura 32. Quinto paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 42 Figura 33. Séptimo paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 43 Figura 34. Noveno paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 43 Figura 35. Undécimo paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 43 Figura 36. Espacio soluciones del problema de Steiner 45 Figura 37. Ejemplo árbol de Steiner 50 Figura 38. Esquema implementación del algoritmo 51 Figura 39. Parámetros de entrada en función del grafo del que se quiere obtener la solución 51 Figura 40. Esquema cambio de filas en función del coste de las aristas de menor a mayor 53 Figura 41. Variables de la función ‘orden’ 53 Figura 42. Diagrama de flujo de la función ‘orden’ 55 Figura 43. Esquema obtención puntos Steiner 55 Figura 44. Variables de la función ‘steiner’ 56 Figura 45. Diagrama de flujo de la función ‘steiner’ 58 Figura 46. Esquema de cómo ordenar el número de aristas activas que puede tener un nodo Steiner 59 Figura 47. Variables de la función ‘steinerorden’ 60 Figura 48. Diagrama de flujo de la función ‘steinerorden’ 62 Figura 49. Esquema de cómo obtener una solución admisible en código binario 63 Figura 50. Variables de la función ‘solucionado’ 64 Figura 51. Diagrama de flujo de la función ‘solucionado’ parte I 67 Figura 52. Diagrama de flujo de la función ‘solucionado’ parte II 68 Figura 53. Variables de la función ‘costealeatorio’ 69 Figura 54. Diagrama de flujo de la función ‘costealeatorio’ 70 Figura 55. Variables de la función’definitivo’ 71 Figura 56. Diagrama de flujo de la función ‘definitivo’ 72 Figura 57. Obtención del vector “hijo” a partir de la reproducción 73 Figura 58. Variables de la función ‘crossing’ 74 Figura 59. Diagrama de flujo de la función ‘crossing’ 76 Figura 60. Variables de la función ‘mutacion’ 77 Figura 61. Diagrama de flujo de la función ‘mutacion’ 79 Figura 62. Variables de la función ‘seleccion’ 80 Figura 63. Diagrama de flujo de la función ‘seleccion’ parte I 84 Figura 64. Diagrama de flujo de la función ‘seleccion’ parte II 85 xix Figura 65. Variables de la función ‘genetico1’ 87 Figura 66. Diagrama de flujo de la función ‘genetico1’ parte I 91 Figura 67. Diagrama de flujo de la función ‘genetico1’ parte II 92 Figura 68. Curva de superficie para steinb4 109 Figura 69. Curva vista desde arriba para steinb4 110 Figura 70. Curva de superficie de steinb6 110 Figura 71. Curva de superficie de steinb12 111 Figura 72. Curva de superficie de steinb16 112 Figura 73. Curva de superficie de steinc1 112 Figura 74. Curva de superficie para steinc4 113 Figura 75. Curva vista desde arriba para steinc4 113 Figura 76. Curva de superficie para steinc6 114 Figura 77. Curva de superficie para steinc7 114 Figura 78. Curva de superficie para steinc10 115 xx xxi Índice de Tablas Tabla 1. Aplicaciones y campos elegidos 21 Tabla 2. Costes asignados a las aristas del ejemplo ordenados de menor a mayor 41 Tabla 3. Cómo pasar del vector ‘hijo’ a la obtención de los costes para aplicar el MST 74 Tabla 4. Ejemplo particular de la estructura población de un árbol de Steiner 87 Tabla 5. Problemas steinb 94 Tabla 6. Problemas steinc 94 Tabla 7. Resultados del algoritmo genético para los problemas de tipo b 96 Tabla 8. Resultados del algoritmo genético para los problemas de tipo c 97 Tabla 9. Resultados del MST para los problemas de tipo b 98 Tabla 10. Resultados del MST para los problemas de tipo c 98 xxii Índice de Gráficas Gráfica 1. Espacio de soluciones proporcionado en las diferentes poblaciones implementadas 86 Gráfica 2. N.º de nodos, arcos y terminales en función del problema 95 Gráfica 3. N.º de nodos totales y nodos terminales en relación al tipo de problema 95 Gráfica 4. Porcentaje de error respecto del número de iteraciones de los problemas tipo “b” para poblaciones de 90 individuos 99 Gráfica 5. Porcentaje de error respecto del número de iteraciones de los problemas tipo “b” para poblaciones de 60 individuos 99 Gráfica 6. Porcentaje de error respecto del número de iteraciones de los problemas tipo “c” para poblaciones de 90 individuos 100 Gráfica 7. Porcentaje de error respecto del número de iteraciones de los problemas de tipo “c” para poblaciones de 60 individuos 100 Gráfica 8. Porcentaje de error frente al número de problema tipo “b” 101 Gráfica 9. Contraste error del MST y del AG respecto a los problemas de tipo “b” 101 Gráfica 10. Porcentaje de error frente al número de problema tipo “c” 102 Gráfica 11. Contraste error del MST y del AG respecto a los problemas de tipo “c” 102 Gráfica 12. Tiempo de implementación en segundos frente el número de problema de tipo “b” 103 Gráfica 13. Tiempo de implementación en minutos frente el número de problema de tipo “c” 103 Gráfica 14. Porcentaje de error frente el número de nodos en la resolución de algoritmos genéticos 104 Gráfica 15. Porcentaje de error frente el número de nodos en la resolución del MST 104 Gráfica 16. Relación del tiempo de ejecución respecto al número de nodos resuelto con algoritmo genético 105 Gráfica 17. Relación del tiempo de ejecución respecto al número de nodos resuelto con MST 105 Gráfica 18. Relación del error con el número de arcos en problemas resueltos con el AG 106 Gráfica 19. Relación del error con el número de arcos en problemas resueltos con el MST 106 Gráfica 20. Tiempo de ejecución en función del número de arcos para soluciones con AG 107 Gráfica 21. Tiempo de ejecución en función del número de arcos para soluciones con MST 107 Gráfica 22. Densidad de los nodos terminales en función del porcentaje de error 108 Gráfica 23. Densidad de los nodos terminales en función del tiempo de resolución 108 xxiii xxiv 1 INTRODUCCIÓN “Una cosa es continuar la historia y otra repetirla” Jacinto Benavente (1866-1954) Hace ya más de dos siglos desde que el matemático suizo Leonhard Euler (1707-1783) se planteó estudiar la posibilidad de pasar una sola vez por todos los puentes de la ciudad de Königsberg. Para atravesar el río Pregel, existían siete puentes dispuestos según la Figura 1 que facilitaban el acceso a los diferentes puntos de la ciudad. La disposición de los puentes resultó ser de un llamativo interés para el matemático. La resolución de este problema originó los cimientos de la teoría de grafos, la cual quedó abandonada durante los siglos XVII y XVIII. La carencia de las ciencias computacionales, imprescindibles para la resolución de problemas semejantes con mayor número de parámetros, dieron al olvido esta rama de las matemáticas. (Hans Jürgen Prömel y Angelika Steger, 2002). Por otro lado, Fermat (1601-1665) a principios del siglo XVII formuló al final de su libro “Treatise on Minima and Maxima” lo siguiente: Dados tres puntos en un plano, encontrar el cuarto punto de forma que la suma de las distancias de los tres puntos dados sea mínima. No fue hasta antes de 1640 cuando su amigo Torricelli, formando un triángulo con los tres puntos dados, dio una solución geométrica para este problema llamado el problema de Fermat. (Dietmar Figura 1. Visualización puentes de Königsberg Fuente: Research gate. El uso de redes complejas en economía: alcances y perspectivas. (2017). 8 al diseño de microprocesadores. Además, debido a las ventajas que proporciona poder disminuir el número de arcos y nodos, actualmente existen algoritmos de reducción que pueden disminuir grafos a una pequeña porción del original usando tiempos polinomiales de bajo grado. (Cuanto mayor grado tenga el polinomio, mayor será el esfuerzo de computación). Dichos algoritmos son atribuidos a Polzin y Vahdati Daneshmand (2001-2004). En el algoritmo heurístico trabajado en este documento, se desprecia el tiempo ganado en la reducción del grafo, a pesar de las ventajas que ello pueda conllevar. Por el contrario, se tiene en consideración la eliminación de todos los nodos Steiner de grado uno pertenecientes al árbol mínimo de Steiner antes de proporcionar la solución. Por ello, aunque no se utilice la reducción de grafos en el algoritmo trabajado, es conveniente el conocimiento de las técnicas nombradas. Sobre todo, es relevante recalcar la importancia de eliminar aristas y/o nodos Steiner para el acondicionamiento del problema antes de aplicar una de las técnicas de resolución exactas nombradas en este apartado. Antes de ello, se definen otros árboles de Steiner considerados en espacios euclídeos o, comúnmente, bidimensionales. 2.3 Árboles de Steiner en otros espacios métricos Aparte de los árboles de Steiner en grafos utilizados en su mayoría en tres dimensiones, existen otros árboles de Steiner de dos dimensiones. En ellos, se utilizan distancias euclídeas y distancias Manhattan de especial interés para nuevas aplicaciones tecnológicas. Son los llamados árboles euclídeos de Steiner (“minimum euclidean Steiner tree”) y árboles de Steiner rectilíneos (“minimum rectilinear Steiner tree”), los cuales serán presentados en los siguientes subapartados. 2.3.1 Minimum Euclidean Steiner Tree El árbol mínimo euclídeo de Steiner surge durante la planificación y construcción de largas redes donde sólo se tiene un conjunto de nodos terminales en un espacio definido. No existe, por consiguiente, arcos de unión entre nodos permitiendo la libertad de añadir nodos intermedios para reducir las distancias entre los nodos terminales. Los llamados problemas de árboles euclídeos de Steiner se utilizan en aplicaciones que envuelven espacios métricos con distancia euclídea, confinados en planos de dos dimensiones. Las aplicaciones más conocidas se reparten en campos como; redes de telecomunicaciones, distribución de redes eléctricas o tendido de tuberías de aceite o agua. En dichas estructuras la mayoría de los costes se ven involucrados en la conexión de los nodos y generalmente se pueden elegir puntos Steiner intermedios. Otras aplicaciones como el diseño de circuitos integrados o microprocesadores usan este tipo de árboles de Steiner donde se tienen que construir redes de grandes dimensiones. Formalmente, en el árbol euclídeo de Steiner se tiene un conjunto 𝑃={𝑝1,𝑝2,…,𝑝𝑁} de N puntos coplanares llamados puntos de lugar. El problema del árbol euclídeo mínimo de Steiner consiste en encontrar la mínima conexión entre los N puntos, donde el árbol puede contener otros nodos en el plano, diferentes de los puntos de lugar. Este conjunto 𝑆={𝑠1,𝑠2,…,𝑠𝑀} de M puntos extra son los llamados puntos Steiner. 9 Un sencillo ejemplo es dado en la Figura 4 donde los cuatro nodos mostrados deben de ser conectados mediante un árbol de mínima distancia. Si se conectan mediante el MST se obtendrá el árbol de la izquierda con coste 10. En cambio, si se añaden puntos de Steiner extra, mostrados en el centro con color negro, la distancia del árbol es reducida más de un 10%. De forma similar, la Figura 5 muestra los mismos resultados que la figura anterior. En este caso, se hace repetidamente uso del punto de Fermat-Torricelli para posicionar puntos Steiner que minimicen aquellas distancias entre nodos que formen un triángulo. Encontrar el árbol mínimo de Steiner resulta más flexible que el árbol mínimo de expansión hallado en cualquiera de las dos figuras presentadas. Esto es debido, a que se puede añadir cualquier punto intermedio en una posición conveniente para minimizar la distancia del árbol. Adicionalmente, como el tiempo computacional crece a medida que existen más nodos de lugar en el plano, este problema ha sido también catalogado como NP-Completo. (Gilbert y Pollak, 1986) Figura 5. Otro ejemplo MST vs. SMT Fuente: Creación propia Figura 4. MST vs. SMT Fuente: Creación propia 10 2.3.2 Minimum rectilinear Steiner Tree El problema del mínimo árbol de Steiner rectilíneo es similar al problema del mínimo árbol euclídeo de Steiner, con la restricción de que los arcos a conectar, en el conjunto de nodos, presentan distancia Manhattan, es decir, están colocados en horizontal y vertical. En la Figura 6 se ilustra tal problema donde nueve puntos de lugar se tienen que conectar mediante arcos horizontales y verticales para formar un árbol rectilíneo mínimo de Steiner. En la figura de la izquierda, se muestran los puntos a conectar, mientras que en la figura de la derecha se ilustra el problema resuelto. Se demostró que se trata de un árbol de Steiner NP-Completo (Garey y Johnson, 1977). Aunque Hwang probó que el ratio entre el MST y el árbol mínimo rectilíneo de Steiner no puede ser mayor que 3/2, lo cual facilita la resolución por técnicas heurísticas tomando el MST como punto de partida. Gracias a esta demostración y a la rápida progresión de las tecnologías, se han unido las técnicas de resolución del árbol de Steiner rectilíneo y la nanotecnología para determinar las conexiones óptimas entre los miles de componentes de un microprocesador. Un avance muy importante que permite fabricar microchips cada vez más pequeños. Aparte, el árbol de Steiner rectilíneo presenta un diseño de red fácil de llevar a la práctica siendo el más recomendado para las conexiones de componentes en un microprocesador. Toda la información sobre el apartado árboles de Steiner en otros espacios métricos se puede encontrar aquí (Xiuzhen Cheng and Ding-Zhu Du, 2001). Sin más demora, se exponen a continuación explícitamente las técnicas exactas más conocidas para la resolución de árboles de Steiner en grafos. 2.4 Técnicas de resolución exactas Las técnicas exactas fueron las primeras investigadas para la resolución del árbol de Steiner. A pesar de ser aplicables para varios espacios métricos, se explicarán específicamente para árboles de Steiner en grafos los cuales son de gran interés en el estudio realizado. Aunque los tiempos de procesamiento son no polinomiales para grafos de gran tamaño, los métodos exactos se consideran de gran valía cuando los grafos contienen un número reducido de nodos. De este modo, se presentan en este apartado concisamente las dos grandes opciones de resolución exacta del problema de Steiner; programación dinámica y programación entera (lineal). Figura 6. Solución árbol de Steiner rectilíneo Fuente: Creación propia 11 2.4.1 Programación dinámica El principio de la programación dinámica es resolver problemas recursivamente, es decir, dar solución a problemas empezando de abajo arriba guardando soluciones óptimas de subproblemas y combinando dichas soluciones dentro de soluciones óptimas de subproblemas más grandes. La programación dinámica es muy efectiva cuando se tratan casos especiales en los que, por ejemplo, el número de terminales y nodos Steiner es pequeño. Además, fue uno de los primeros métodos utilizados en la resolución no trivial del problema del árbol de Steiner en grafos de forma exacta. El problema reside en obtener el coste total de un árbol mínimo de Steiner de un subconjunto de nodos X siendo G XN , y finalmente () G CN , que es el coste total del árbol del grafo G que contiene G N nodos terminales. 2.4.1.1 Algoritmo de Dreyfus-Wagner El algoritmo de Dreyfus-Wagner (1972) es una de las implementaciones más ingeniosas de la programación dinámica. Por ser una de las primeras estudiadas y de las más conocidas se presenta a continuación su funcionamiento. Para comenzar se proporcionan las siguientes consideraciones: 𝑣∈𝑉∖𝑋 , 𝑐(𝑋 ∪ 𝑣) es el coste total de un árbol mínimo de Steiner para 𝑋∪𝑣 donde v no tiene restricciones de grado, 𝑐𝑣(𝑋∪𝑣) es el coste total de un árbol mínimo de Steiner para 𝑋∪𝑣 donde v tiene grado dos o más y 𝑇𝑣 es el mínimo árbol de Steiner para el conjunto 𝑋∪𝑣, donde v tiene grado mayor o igual a dos. Se puede descomponer 𝑇𝑣 en dos subárboles 𝑇𝑣1 𝑦 𝑇𝑣2. De manera, que 𝑇𝑣1 sea el SMT para 𝑋′∪ 𝑣 donde 𝑋′⊂𝑋 , y 𝑇𝑣2 el SMT para (𝑋∖𝑋′)∪𝑣. Se obtiene, por consiguiente, la expresión: 𝐶𝑣(𝑋∪𝑣)=𝑚𝑖𝑛∅⊂𝑋′⊂𝑋{𝑐(𝑋′∪𝑣)+𝑐((𝑋∖𝑋′)∪𝑣)} Que significa que el mínimo coste del conjunto de nodos del grafo más el nodo v, donde v tiene grado mayor o igual a dos, es igual; al mínimo de los costes de un subconjunto de nodos 𝑋′ más el nodo v, más el coste del subconjunto restante de nodos 𝑋∖𝑋′ más el nodo v. Ahora bien, considerando T como el mínimo árbol de Steiner para el conjunto 𝑋 ∪ 𝑣, donde v no tiene restricciones de grado, se pueden presentar dos posibles situaciones. Si v tiene grado dos o más 𝑐(𝑋∪𝑣)=𝑐𝑣(𝑋∪𝑣). En cambio, si v tiene grado uno se considera pT(v,w) en T el camino único de v al primer vértice w en T, donde w puede ser un terminal o nodo Steiner de grado mayor o igual a 3 (todos los vértices interiores, si hay, de pT(v,w) son vértices Steiner de grado dos). ▪ Si w es un nodo terminal, el coste total de T será el del camino más corto entre v y w más el coste del árbol mínimo de Steiner para X donde w∈X. ▪ Si w es un nodo Steiner de grado mayor o igual a 3, el coste total de T es el peso del camino más corto entre v y w más el coste del árbol mínimo para 𝑋∪ 𝑤,donde 𝑤∉𝑋 y w tiene grado ≥2. 12 Se obtiene la siguiente expresión que minimiza el coste del árbol de Steiner según el algoritmo de Dreyfus-Wagner. 𝐶(𝑋∪𝑣)=min{𝑚𝑖𝑛𝑤∈𝑋{𝑐𝑝(𝑣,𝑤)+𝑐(𝑋)}, 𝑚𝑖𝑛𝑤∈𝑉∖𝑋{𝑐𝑝(𝑣,𝑤)+𝑐𝑤(𝑋∪𝑤)}} Donde se elige el mínimo entre las posibles conexiones de v con w siendo este otro nodo terminal o un nodo Steiner de grado mayor o igual a 3. Este algoritmo se ve utilizado en pequeños conjuntos de nodos donde se puede implementar con eficiencia. Las variaciones de este algoritmo son las encargadas de resolver largos problemas de grafos eficientemente. 2.4.2 Programación entera El uso de la programación lineal entera en problemas de optimización se remonta a Yang y Wing (1973). Aunque fueron Aneja (1980) y Wong (1984) los primeros en usar la programación lineal entera para la resolución de los problemas de Steiner en grafos. En esta sección se presentan tres de las más conocidas formulaciones de programación entera. La primera formulación expuesta será la del árbol de expansión (“spanning tree formulation”), la cual no se ha utilizado demasiado en los problemas de grafos sino más bien para la resolución de árboles mínimos de Steiner y árboles de expansión mínima en hipergrafos. Seguidamente, la formulación de los cortes (“cut formulation”), cuya una de sus variantes es la que actualmente se utiliza y para finalizar la formulación de flujos (“multi-commodity Flow formulation”) que contiene gran número de variables y restricciones. 2.4.2.1 Spanning tree formulation El modelo de optimización del árbol de expansión con nodos Steiner se presenta así:     min ( ) . .: ( ) ( ) 1 ( ( )) ( ) 1 , 0,1 0,1 e eE GG G G G e vG c e x st x E y S N x E W y S W N W W V W N x e E y v S  = + −   +  −        Los datos necesarios para llevar a cabo el modelo de optimización son: V: conjunto de nodos Steiner y nodos terminales en G E: conjunto de aristas en G 𝑐(𝑒): coste asociado a la arista 𝑒∈𝐸 𝑆𝐺: nodos Steiner en G 𝑁𝐺: nodos terminales en G 13 Las variables utilizadas en la formulación representan: 1 si 𝑒∈𝐸 forma parte del árbol de Steiner 0 en otro caso x(E)= e eE x   x(E(W)): aristas dentro del conjunto de nodos W que forman parte del árbol de Steiner 1 si 𝑣∈𝑆𝐺 forma parte del árbol de Steiner 0 en otro caso Donde la función objetivo de la formulación se encarga de sumar todos los costes de las aristas que forman parte de la solución. En la primera restricción, se indica que el número de aristas del árbol de Steiner debe ser igual al número de nodos menos uno. En la segunda restricción, se asegura que cuando se tenga un árbol de Steiner candidato a ser solución no se pueden formar lazos. Lo que es equivalente a; el número de arcos que unen un subconjunto de nodos W (donde ,G W V W N    ) pertenecientes a un árbol de Steiner tienen que ser como mucho, iguales al número de los nodos de W menos uno. (Goemans et. al, 1993) Para la mejor comprensión del algoritmo se expone por pasos un ejemplo gráfico que recoge la idea principal del método. Se han omitido los nodos Steiner para no enturbiar la explicación. 1º paso: Supongamos que se tiene el grafo representado en la ¡Error! No se encuentra el origen de la r eferencia.. El conjunto de aristas marcadas en color será una de las primeras soluciones que se obtendría sin hacer caso a la segunda restricción de la formulación. Como se puede ver, con dicha solución la función objetivo está minimizada y se cumple que el número de aristas de la solución es el número de nodos menos uno. 2º paso: Sin embargo, al aplicar la segunda restricción se observa la existencia de un lazo correspondiente con el óvalo sombreado de la ¡Error! No se encuentra el o rigen de la referencia.. Se deja de cumplir que el número de aristas, que forman parte de la solución, que unen el subconjunto de nodos W rodeado sea menor o igual al número de nodos en W menos 1. Figura 7. Paso 1 Spanning Tree Formulation Figura 8. Paso 2 Spanning Tree Formulation 14 3º paso: La arista que forma parte del lazo con mayor coste es eliminada en la Figura 9 y se busca otro arco con el coste mínimo posible que cumpla la primera restricción de la formulación. En este caso, el arco con coste cinco será el que pasa a formar parte del árbol. Para este ejemplo, se habría terminado con el algoritmo obteniendo una función objetivo de doce unidades de coste. La formulación del árbol de expansión recuerda al algoritmo de Kruskal utilizado en el método heurístico en el que se basa este documento. Sin embargo, el algoritmo de Kruskal será utilizado para calcular el árbol de mínima expansión (“mínimum spanning tree”, MST) donde no figuran nodos Steiner. 2.4.2.2 Cut formulation La formulación de cortes se focaliza en la conectividad del grafo, lo que significa que debe existir un camino entre cualquier par de terminales del árbol de Steiner. (Aneja et. al, 1980) El modelo de optimización para la formulación de los cortes es: Los datos introducidos en el modelo son: V: conjunto de nodos Steiner y nodos terminales en G E: conjunto de aristas en G 𝑁𝐺: nodos terminales en G 𝑐(𝑒): coste asociado a la arista 𝑒∈𝐸 W: subconjunto de nodos o nodo terminal perteneciente a V Donde las variables de interés son: ( ( ))xW  : conjunto de arcos que están unidos al subconjunto W 1 si 𝑒∈𝐸 forma parte del árbol de Steiner 0 en otro caso Al igual que en la formulación anterior, la función objetivo en “cut formulation” se encarga de minimizar el coste total del árbol de expansión. La primera restricción asegura que al producirse un corte alrededor de un conjunto de nodos o rodeando a un nodo terminal, siempre exista un Figura 9. Paso 3 Spanning Tree Formulation 15 arco que traspasa ese corte que forma parte del árbol de Steiner. Se presenta a continuación un ejemplo que ilustra el funcionamiento del método. En la Figura 10 se puede ver una de las primeras soluciones proporcionadas por el algoritmo sin tener en cuenta la primera restricción. Cuando se aplica la restricción del corte para el conjunto W formado por los tres nodos que forman un lazo, se puede observar cómo no existe unión con el resto de la solución planteada. Luego, será necesario que el arco con menor coste, en este caso aquel de coste cinco, pase a formar parte de la solución. Finalmente, se eliminará de la solución el arco de coste cuatro debido a que sin ella el coste total disminuye y se sigue cumpliendo la restricción del corte para WV . 2.4.2.3 Multi-commodity Flow Formulation Para este método se utiliza el grafo dirigido obtenido del grafo original. Un grafo dirigido es aquel cuyos nodos están conectados mediante dos arcos (en vez de uno) a otro nodo adyacente. El coste de los arcos que conectan un par de nodos será el coste original del grafo anterior. Un ejemplo se muestra en la Figura 11. Para la resolución del árbol de Steiner es preciso generar un flujo desde un nodo que se llamará r a uno final t. Figura 11. Ejemplo Flow Formulation Fuente: Elaboración propia Figura 10. Final Spanning Tree Formulation Fuente: Elaboración propia 16 El modelo de programación entera se expresa matemáticamente: Los datos de interés para el modelo son: r: nodo terminal de salida de flujo del grafo G, 𝑟 𝜖 𝑉 t: nodo terminal de entrada de flujo del grafo G, 𝑡 𝜖 𝑉 V: conjunto de nodos Steiner y nodos terminales en G 𝑁𝐺: nodos terminales en G 𝑐(𝑎): coste del arco a Donde las variables utilizadas significan: 1 si a forma parte del árbol de Steiner 𝑤𝑎: 0 en otro caso ( ( )) t fv  + : se trata del flujo de salida a un nodo v ( ( )) t fv  − : flujo de entrada al nodo v t a f : flujo en el arco a El modelo está organizado de la siguiente forma. La función objetivo representa la suma de costes del árbol de Steiner solución. A su vez, la primera restricción muestra el balance de flujo de cada nodo. Para continuar, las dos siguientes restricciones hacen referencia al máximo de flujo que puede llevar un arco, siendo de 1 unidad. Por último, se hace mención a 𝑤𝑎, que es una variable binaria. Se muestra a continuación un ejemplo de la técnica: El objetivo del algoritmo es ir cambiando los nodos r y t hasta que se obtenga un árbol de Steiner cuyo camino de r a t sea de coste mínimo. 17 Un ejemplo se muestra en la Figura 12, donde se comprueba que el balance de flujo en r es de 1 y el de t de -1, al igual que en el resto de los nodos donde pasa flujo, no se retiene nada. Para este caso en particular se obtiene un coste total de 18 unidades. El algoritmo sigue iterando hasta que encuentra la solución mostrada en la Figura 13, donde finalmente el coste total se consigue minimizar a doce unidades. Como se comentaba anteriormente, el mayor problema de esta formulación es el gran número de restricciones, lo que hace imposible la implementación de este algoritmo en grafos de gran escala. Ello también ocurre en los anteriores algoritmos de resolución exacta, donde el tiempo de resolución deja de ser polinomial cuando el número de nodos del grafo aumenta. Es por ello, la necesidad de algoritmos heurísticos que den una solución muy próxima al óptimo y en el mejor de los casos el óptimo. Más información sobre las técnicas de resolución exactas se encuentran en la referencia a continuación. (Marcus Brazil y Martin Zachariasen, 2010) Figura 13. Continuación ejemplo resolución Flow Formulation Fuente: Elaboración propia Figura 12. Ejemplo resolución Flow Formulation Fuente: Elaboración propia 24 los ingenieros y planificadores la manipulación de datos asociados con un diseño óptimo. Respecto a las minas subterráneas, no existían algoritmos semejantes aplicados bajo tierra. Sin embargo, un grupo de investigadores de la universidad de Melbourne lograron encontrar un algoritmo de resolución para las minas subterráneas. Restricciones como el ancho de túnel para que puedan pasar los dispositivos extractores y los metros de túnel son parámetros indispensables para obtener los caminos óptimos por donde extraer el mineral. Una mina subterránea consiste en una serie de túneles interconectados, túneles que llevan hasta el yacimiento del mineral (“ore body” o “stopes”, en inglés) y túneles que se utilizan para la extracción a la superficie. En las minas, el yacimiento del material preciado es identificado mediante test geológicos o por perforación de pozos de relleno. Con esta información los ingenieros mineros determinan los puntos terminales donde está localizado el yacimiento del mineral. El material es finalmente extraído mediante uno de los posibles métodos de extracción (como “stoping”, “caving” o “room and pillar”) y transportado a la superficie mediante la red de acceso, principalmente compuesta por “crosscuts” y “declines” tal como se muestra en la Figura 15. Por tanto, se define el problema de Steiner con e túneles donde 𝑒∈𝐸 y T siendo un grafo, tal que 𝑇=(𝑁,𝐸) donde N representa el número de yacimientos a excavar. Finalmente, se muestran las restricciones y la función objetivo a tener en cuenta para la resolución del problema de optimización. Los túneles deben ser elegidos cumpliendo con las siguientes restricciones: 1. No se pueden excavar regiones atravesando un yacimiento o donde previamente se ha excavado. 2. La inclinación de los túneles no debe traspasar un máximo para que las máquinas puedan rodar por los caminos. 3. Los caminos de túnel deben de ser lo más cortos posibles para minimizar los costes. Figura 15. Esquema de mina subterránea Fuente: Markus Brazil, Martin Zachariasen (2015) 25 Seguidamente, la función objetivo viene definida por: ( ) ( ) ee eE C T d h t l  = +    Donde: • d: el coste de túnel por metro • h: el coste del túnel por tonelada a extraer y kilómetro a excavar • 𝑡𝑒: la cantidad de mineral a transportar por el túnel e • 𝑙𝑒: la distancia del túnel e 3.2.2 Redes de telecomunicaciones En el último siglo, las telecomunicaciones han tenido un gran impacto en todos los aspectos de la vida. No cabe duda de que la transformación de la revolución industrial a la era de la información ha sido principalmente influenciada por los avances tecnológicos en el campo de las telecomunicaciones. La minimización de costes, de energía o encontrar la conexión óptima son ejemplos de objetivos primordiales en los problemas de optimización que también se utilizan en este campo. Mediante el problema de Steiner aplicado a redes de fibra óptica y redes inalámbricas como el enrutamiento multicast, se podrá ver el interés del problema de Steiner en esta rama de la ingeniería. 3.2.2.1 Redes de fibra óptica: La fibra óptica se utiliza para la distribución de servicios avanzados como televisión, internet de banda ancha y telefonía. Se trata de una red de gran ancho donde el haz de luz del emisor se distribuye hacia múltiples fibras siguiendo diferentes direcciones. Su complejidad depende de la extensión, la cobertura de esta y, evidentemente, del ancho de banda. Regiones donde hay que hacer llegar menos información, permiten disminuir la cantidad de fibra óptica y los costes de instalación y mantenimiento. La fibra óptica tiene mucho que ofrecer a las telecomunicaciones y cada vez es más frecuente encontrarlas, ya que soportan grandes cantidades de datos abaratando el coste respecto de las instalaciones de cobre. Por otro lado, múltiples ventajas como; bandas de frecuencia elevadas, inmunidad frente interferencias electromagnéticas, vida media de los cables superior a los cables de conductores y bajo coste potencial (debido a la abundancia del material empleado, óxido de silicio) hacen que las crecientes necesidades de servicios de telecomunicaciones se vean satisfechas por esta tecnología. Por ello, el problema de Steiner tiene un papel crucial para la planificación de dichas instalaciones. En la Figura 16 se muestra un ejemplo de una empresa consultora estadounidense que pretende unir veintiuna ciudades norteamericanas consiguiendo disminuir las distancias entre puntos por el árbol de expansión mínima (mínimum spanning tree, MST) utilizando el árbol mínimo de Steiner (Steiner minimal tree, SMT). En la primera imagen, tenemos el problema inicial con todos los posibles caminos entre las diversas ciudades. Seguidamente, se muestra la resolución del árbol de expansión mínima mediante el algoritmo de Kruskal. Por último, se introducen puntos 26 Steiner según el principio del punto de Torricelli, donde el árbol mínimo euclídeo de Steiner visto en la sección 2.3.1 permite disminuir las distancias respecto al MST. 3.2.2.2 Red inalámbrica (Wireless network): En el campo de las telecomunicaciones, la red inalámbrica trata las conexiones de nodos que se da por medio de ondas electromagnéticas sin necesidad de una red cableada. Cada nodo es un emisor y/o receptor que suelen ser antenas, móviles o algún dispositivo destinado a emitir o recibir señales. A diferencia de las redes alámbricas conectadas físicamente, mediante la conexión por radiofrecuencia se consiguen abaratar los costes de cableado, pero hay que incluir una mayor seguridad contra posibles intrusos. Al igual que las conexiones de telecomunicación por cable, es imprescindible encontrar el mejor camino de un emisor a un receptor a través de las conexiones establecidas entre los nodos. En las conexiones mediante señales, el objetivo es minimizar el retraso de la señal aumentando el rendimiento de la conexión. Hay que tener en cuenta que existe una frecuencia máxima de transmisión de datos, lo que resulta un impedimento para transportar grandes cantidades de información ya que la capacidad de una señal para transmitir datos aumenta con la frecuencia. A continuación, se presentan dos buenos ejemplos del problema de Steiner aplicados a la eficiencia energética en “Wireless Networks” y al enrutamiento multicast. 3.2.2.2.1 Eficiencia energética en “Wireless Networks”: Algunos dispositivos que forman parte de una red inalámbrica son actuadores, sensores u otros aparatos de pequeño tamaño que presentan un límite de batería que hay que optimizar. Figura 16. Procedimiento SMT para ciudades estadounidenses Fuente: Noah Todd (2013). Kruskal Steiner Fiber Optic Cable Project. Prezi 27 Problemas en particular que se resuelven con una red de sensores que están interconectados son; seguridad nacional, vigilancia, atención médica y monitoreo ambiental entre otros. Una vez que se tienen los puntos donde se colocan los dispositivos que emiten y reciben ondas, es imprescindible minimizar la distancia de la señal que emite cada nodo para reducir el consumo de energía. Así se pretende crear un camino que una a todos los nodos minimizando la distancia de la señal lo mínimo posible para gestionar óptimamente el recurso energético. Para ello, se utiliza la siguiente igualdad que relaciona la distancia entre nodos con la energía de la señal. Ps≥d(s,t)α Donde: ▪ P: energía de la señal emitida por s ▪ d(s,t): distancia entre nodos s y t ▪ α: constante entre 2 y 5 Se dispone de un ejemplo en la Figura 17 donde cada nodo terminal representa un sensor. Para su implementación se definen; los puntos Steiner, que son sensores que pueden o no ser añadidos para el mejor funcionamiento de la red, y los costes energéticos para unir los sensores que se toman de cada arco. Aplicando el algoritmo desarrollado en este proyecto se obtiene la solución marcada en negrita que representa un coste total de 37 unidades energéticas. Aparte, existen otro tipo de problemas de optimización combinatoria en los que no es posible ajustar la distancia de la señal. Por eso, es necesario combinar sensores en modo activo y desactivo para optimizar una malla de excesivos sensores. 3.2.2.2.2 Enrutamiento multicast (Multicast routing): El concepto multicast abarca la habilidad de conectar un subconjunto de receptores a una red. Este servicio multicast es ofrecido por el “packet switched network” (PSN) que se encarga de suministrar copias de un paquete de información a un conjunto de destinatarios simultáneamente. Básicamente, la idea consiste en poder transmitir archivos multimedia como audios o videos mediante la conexión de servidores en una red inalámbrica de ordenadores. La Figura 17. Ejemplo red de sensores Wi-Fi Fuente: Creación propia 28 comunicación multicast viene siendo de gran importancia para poder llevar a cabo teleconferencias, colaboración remota o el aprendizaje a distancia como las universidades a distancia. Por consiguiente, debido a la necesidad de conectar varias fuentes a varios destinatarios o simplemente una fuente a varios receptores, el enrutamiento multicast ha ido cobrando importancia con el paso de los años. Para dar soporte multicast es necesario cumplir algunos requisitos de calidad de servicio (quality of services, QoS), entre los más utilizados el end-to-end delay, que se trata de poner un límite al retraso de señal total añadido en los caminos desde el emisor hasta el receptor final. Mediante esta restricción se asegura minimizar el retraso de la señal aumentando el rendimiento de la conexión, tal como se explicó en el apartado Wireless Network. En la Figura 18 se muestra un ejemplo donde se quieren conectar los nodos { 𝑣4,𝑣5,𝑣7,𝑣8} con la fuente 𝑣1. Las restricciones que se presentan son minimizar el coste total y cumplir que el retraso esté por debajo de 20 unidades. Se puede observar cómo es imposible crear un único camino en el grafo desde 𝑣1 a 𝑣8 debido a que se debe cumplir con el requisito de limitar el retraso a 20 unidades como máximo. Luego, aunque los costes sean mayores para la solución representada en la figura, se deben coger dos caminos desde 𝑣1. Los nodos 𝑣6 y 𝑣2 serían nodos Steiner en dicha solución. Por supuesto, este tipo de problemas es resuelto mediante el árbol de Steiner. Se pueden distinguir entre dos tipos de problemas; los estáticos y los dinámicos de enrutamiento multicast (“Multicast Routing”, MR). La característica principal de los problemas estáticos es la existencia de un solo problema de optimización. Al ser conocidos tanto la fuente de información como el número y la posición de los miembros del grupo multicast (receptores), se optimiza la red antes de que se ponga en funcionamiento. Por el contrario, la resolución dinámica deberá tener en cuenta que los receptores pueden unirse o dejar el grupo multicast durante el periodo de conexión, lo que supone una dificultad añadida al tener que estar optimizando la conexión cada x tiempo. Los problemas dinámicos, también conocidos como “on-line multicast problema”, podrían resolverse implementando algoritmos de problemas estáticos cada vez que cambia el número y posición de los receptores. El mayor inconveniente de ello, son los costes prohibitivos que supone la optimización constante de la red. Además, los sistemas reales no toleran grandes cambios en los árboles multicast debido a que los paquetes de datos están constantemente Figura 18. Ejemplo red de enrutamiento multicast Fuente: Creación propia 29 viajando por la red. Un cambio brusco de red supondría la disrupción del flujo de información ocasionando el colapso. Algoritmos como the “greedy algorithm” (GA), “the predetermined path search algorithm” (PPS) o “the ARIES algorithm” son los más adecuados para resolver el árbol de Steiner en problemas dinámicos de enrutamiento multicast, los cuales escapan del objetivo de este proyecto. Mediante esta aplicación se muestra otro motivo más que justifica el interés mostrado en las últimas décadas por encontrar un algoritmo resoluble en tiempo polinomial del problema planteado por Steiner. 3.2.3 VLSI (very large scale integration): Se trata del proceso de creación de circuitos integrados combinando miles de módulos (transistores en su mayoría) dentro de un único chip. Su rápido desarrollo tecnológico y el crecimiento de la complejidad de los VLSI, debido a que cada vez más se necesitan microprocesadores más pequeños y potentes con mayor número de transistores, hacen que la aplicación del problema de Steiner sea crucial para unir los diferentes componentes (enrutamiento) de forma óptima. El problema del enrutamiento es solventado mediante algoritmos de optimización como el árbol de Steiner rectilíneo (visto en la sección 2.3.2) que es utilizado para conectar el conjunto de módulos dentro del microprocesador usando la mínima distancia posible. Llegados a este punto, el diseño general del circuito ya ha sido determinado. Tanto la posición de cada componente en el chip, como los posibles caminos entre los transistores son conocidos para poder comenzar con el problema de enrutamiento. Para ello, se compaginan en el diseño del microprocesador eficientes algoritmos con un proceso de diseño altamente automatizado. Un objetivo clave para diseñar buenos VLSI es utilizar la mínima separación posible entre los cables que se necesitan implantar. De este modo, al ser el área ocupada por los cables aproximadamente proporcional a la longitud total de cable utilizado, también se podrá minimizar el área. Luego, esto evita el retraso de señal y el consumo de energía, y favorece el rendimiento del sistema. Tradicionalmente se ha venido considerando que los cables están dispuestos en dos direcciones ortogonales cada una de ellas en una capa diferente y que los circuitos se pueden modelar efectivamente como redes planas en una geometría rectilínea o Manhattan. En cambio, en los modernos diseños microscópicos de VLSI son otros criterios los que dominan el enrutamiento de pines, dando prioridad a otros modelos más efectivos para dichos diseños. Estos criterios son la distancia, la densidad, la inductancia, el ruido, la energía, la tridimensionalidad o la urgencia con la que tiene que pasar la información por un tramo de cable (zonas de la ruta críticas). Los modelos alternativos actuales para el enrutamiento óptimo de componentes que reciben más atención son las mallas hexagonales y las mallas octo-cuadradas. En el modelo hexagonal, el cable puede estar orientado en tres direcciones con pendientes por ejemplo de 0 a /3 . La eficiencia de este modelo fue descubierta por primera vez en 1979. En el modelo de enrutamiento de las mallas octo-cuadradas, los caminos horizontales y verticales utilizados en el modelo del árbol mínimo de Steiner rectilíneo son complementados con caminos con pendientes de /4 . 30 Debido a su sencillez en comparación con otros modelos, las redes con direcciones ortogonales siguen siendo de gran relevancia en el campo de la electrónica. Lo que demuestra la utilidad del problema de Steiner. En la Figura 20, se muestra una foto real tomada desde un microscopio eléctrico de un chip con la estructura de pines diseña a partir del modelo rectilíneo de Steiner. En la Figura 19, se aprecia la conexión de los pines según una solución admisible del problema. 3.2.4 Redes biológicas En el campo de la biología, se pueden determinar ciertos enigmas de la naturaleza a base del problema de Steiner. En esta sección se van a tratar temas relacionados con el cuerpo humano que presentan una gran similitud con el árbol de Steiner al igual que los árboles filogénicos que resuelven incertidumbres sobre los antecesores de las especies. Respecto al cuerpo humano, se ha descubierto recientemente que la minimización de energía potencial de la estructura molecular de las proteínas puede resolverse con el árbol de Steiner. Por otro lado, las interconexiones neuronales en el cerebro humano también siguen un patrón que se puede modelar con el problema de Steiner. Aunque se trata de uno de los campos con mayor investigación en el futuro, hoy es posible obtener resultados asombrosos a partir de los algoritmos de optimización. 3.2.4.1 Estructura molecular La bioquímica es un campo que cada vez más se ve integrado a la ingeniería. Se ha descubierto que la estructura molecular de las proteínas, así como de los ácidos nucleicos que forman el ADN y los agregados moleculares como el virus del mosaico del tabaco es la misma que el modelo de puntos de un árbol mínimo de Steiner. Parece ser, que la naturaleza utiliza principios matemáticos para minimizar la energía local y así formar una estructura que busca la estabilidad durante etapas de crecimiento molecular. La condición para posicionar los átomos en la malla molecular es minimizar la energía potencial consiguiendo así una red estable con un consumo energético bajo. Este descubrimiento permite a los científicos avanzar en la comprensión de la formación de biomoléculas y su evolución. Figura 19. Solución de los pines Fuente: Class Steiner trees and VLSI- design, Edmund Ihler (1995) Figura 20. Foto real de un microship Fuente: Shortest Paths and Steiner Trees in VLSI Routing, Steven Peyer (2007) 31 En la Figura 21 se muestra la estructura de un aminoácido. 3.2.4.2 Redes neuronales: La teoría de grafos aplicada al problema de Steiner también se puede utilizar para el modelaje de las conexiones neuronales que ocurren en el cerebro. El entendimiento de dichas interacciones abre todo un campo de investigación a la cura de enfermedades. El análisis de los patrones de conectividad de las funciones del cerebro es extremadamente complejo debido a la gran cantidad de neuronas y a las conexiones dinámicas entre ellas. Se estima que el cerebro humano tiene 8.3 𝑥 109 neuronas y que el número de conexiones es aproximadamente 6.6 𝑥 1013. Por ello, la representación de dichas estructuras como un grafo de neuronas (posicionada cada una de ellas en un nodo), presenta un coste computacional prohibitivo. Las técnicas utilizadas habitualmente van orientadas a la agrupación de neuronas en nodos dependiendo de su funcionalidad. De esta manera, se consigue abarcar todo el cerebro en un problema simplificado de igual valía y mejor manejo. Estudios como el sistema visual cortical de un macaco o las propiedades del cerebro humano son investigaciones llevadas a cabo mediante el árbol de mínima expansión, entre otras técnicas. Para poder unir los arcos entre nodos se estipula un valor de correlación entre funciones del cerebro que hay que superar para determinar que dos nodos están enlazados. Aunque se trata sin duda de una de las aplicaciones más desconocidas, estudiando las conexiones neuronales es posible diagnosticar y tratar trastornos psiquiátricos (entre otras enfermedades) y se pretende conseguir una visión de los procesos de propagación de señales entre las unidades funcionales del cerebro y las neuronas. 3.2.4.3 Árboles filogénicos: El problema del árbol de Steiner ha tenido gran relevancia en el ámbito biológico. Desde hace más de 100 años, los biólogos interesados en “sistemática” han intentado deducir los árboles evolutivos que presentan las especies de hoy. En los últimos 30 años, es cuando han sido investigados algoritmos matemáticos para construir árboles, motivados por el avance Figura 21. Estructura aminoácido Fuente: Elaboración propia 32 tecnológico y por las diversas razones que fomentan su investigación. El motivo más habitual es el interés por la topología que responde preguntas de clasificación básica. Otras veces, se pretende saber cuándo se ha producido la divergencia entre dos especies o cómo de largos son los arcos del árbol. Estas cuestiones pueden ser solventadas mediante el problema del árbol de Steiner. Los datos iniciales son un conjunto de especies, más generalmente llamado taxa, que se presenta adicionalmente con información sobre las relaciones existentes entre cada taxón (cada grupo de especies). Las agrupaciones de especies se presentan en las extremidades del árbol asignándoles nodos terminales. Por otro lado, los nodos internos son referidos a la taxa antecesora y son los llamados nodos Steiner. La solución que se busca es el árbol que mejor ajusta la evolución de la taxa, siendo una variable de interés la longitud de las ramas del árbol. Por ello, el problema de Steiner para árboles filogénicos se define como: Definiendo a cada carácter como 𝑐 y al conjunto de caracteres como 𝐶, tal que cC , a cada taxón como 𝑠 y a la taxa como 𝑆, tal que sS y a cada vector de caracteres perteneciente a un taxón como 𝑣𝑐𝑠 . Si se tienen dos vectores 𝑣𝑐𝑖 𝑦 𝑣𝑐𝑗 tal que 𝑖,𝑗∈𝑆:𝑖≠𝑗, la distancia entre ellos, ( , ) ci cj dist v v , viene definida por el número de caracteres diferentes que presentan ambos vectores. Se pretende obtener: min ( , ) ci cj j S i S ij dist v v    En la Figura 22 se muestra la solución a un ejemplo donde se pueden ver los taxones (lamprea, tiburón, salmón e iguana) y el conjunto de caracteres que pueden poseer (aletas pélvicas, mandíbula, membrana ósea, aleta pectoral, pulmones y lengua áspera). Cuando un carácter presenta el valor de 1 significa que el taxón posee esa característica. Cuando el carácter es 0, la característica no pertenece al animal. Figura 22. Ejemplo árbol filogénico Fuente: Elaboración propia 33 Para la parametrización del modelo del ejemplo se han utilizado; nodos terminales, que son cada una de las especies representadas, nodos Steiner, que son las especies antepasadas ya extinguidas de las que procede cada taxón y como coste del arco la distancia entre los vectores de caracteres, la cual hay que minimizar. Aunque hay que decir, que la complejidad de este problema es NP-Completo (no se puede resolver en tiempo polinomial), el mayor desafío de este campo es condicionar los parámetros iniciales para poder empezar a resolver el problema. Se han descrito más de dos millones de especies de plantas y animales, pero se sabe que falta por descubrir hasta diez veces este número. Luego, se trata de un problema primordial para investigar la diversidad de organismos vivos en el planeta. 3.2.5 Marketing viral El marketing viral consiste en transmitir una nueva idea o comportamiento al mayor número de personas en el menor tiempo posible. Las redes sociales son las aliadas perfectas para propagar un mensaje de forma exponencial. Por tanto, la idea consiste en que en un tiempo limitado un mensaje se difunda por toda la sociedad a través de personas. Las preguntas clásicas para obtener estos resultados son: a cuántas personas inicialmente se necesita transmitir la idea y cómo tienen que estar dispuestas para difundir el mensaje rápidamente. Este problema se soluciona mediante la resolución del problema de Steiner. Los nodos serán las personas que van a propagar el mensaje y los arcos las distancias entre personas que se definen en función de la amistad, cercanía del lugar o de un interés común. Una regla importante en este tipo de grafos es la transitividad de la red, donde se comprueba que dos nodos que son vecinos de un tercero tienen gran probabilidad de estar relacionados entre sí y por tanto más probabilidad de que fluya la información entre ellos. Supongamos que se quiere lanzar un nuevo producto anti-edad y se pretende que lo conozcan el mayor número de personas lo más rápido posible. Se dispone de clientas por ciudades representada cada clienta en un nodo. Decir que para simplificar el problema se han omitido los nodos Steiner que serían otras personas que no son clientes pero que son potenciales compradores del producto. Como se puede ver, la Figura 23 muestra que las clientas que viven en una misma ciudad tienen menor distancia entre ellas porque hay más posibilidades de que se difunda la idea. Por otro lado, algunos nodos conectan con otras ciudades ya que las clientas son amigas de otras clientas fuera de su ciudad formándose la red de contactos que se muestra en la figura. Al resolver el MST, se obtiene la solución marcada en color que indica la óptima transmisión de información. El MST muestra a quién hay que convencerle de la crema, pues esos nodos son los que mejor conectan con más personas. Por tanto, el trabajo del vendedor de cremas es hacer llegar a los cinco nodos de color la información, ya que son “los puentes” entre las distintas ciudades que conectan con un mayor número de personas. 40 problema de Steiner en grafos. El MST se aplica tantas veces como individuos (soluciones) se quieran considerar en la primera población. Para generar diversidad de soluciones en un mismo grafo a partir del MST, será necesario cambiar los costes de los arcos aleatoriamente por cada solución. Este hecho, será clave en el transcurso del algoritmo para proporcionar buenas soluciones. El árbol mínimo de expansión se define como: Dado: Un grafo no dirigido conectado por arcos ponderados G= (V,E), donde V es el número de nodos, E es el número de arcos y c(e)>0 denota el peso del arco 𝑒∈𝐸. Encontrar: Un subconjunto conectado T=(V,E(T)) en G, tal que ∑𝑐(𝑒) 𝑒∈𝐸 sea mínimo Lo que es equivalente a pensar, que el MST forma un árbol mínimo de Steiner donde todos los nodos considerados son terminales y no existen nodos Steiner. Sin embargo, el MST no es posible utilizarlo como el algoritmo de resolución para problemas de Steiner debido a que su solución para la gran mayoría de problemas de diseño de redes no es óptima. Por otro lado, se trata de una técnica muy buena para obtener árboles dentro de una red. Por eso, se utiliza para generar las primeras soluciones admisibles del algoritmo heurístico. Entre las técnicas del MST más destacadas se encuentran los algoritmos de Boruvka, Prim y Kruskal. 4.1.1 Algoritmo de Boruvka Se trata del primer problema de optimización de redes realizado por Otakar Boruvka (1926). Surgió a partir de la necesidad de construir la red eléctrica de la región histórica de Moravia. Para el desarrollo del método es imprescindible empezar considerando a cada nodo del grafo como un componente distinto para luego continuar seleccionando todos los arcos de menor coste que inciden en cada uno de los nodos. A partir de ahí, se busca en cada etapa los arcos de coste mínimo que inciden en cada componente, evitando que se formen ciclos, hasta que se cumple que el número de nodos es el número de arcos solución menos uno. 4.1.2 Algoritmo de Prim Se trata de una de las técnicas más sencillas para resolver el problema del árbol de expansión mínima. Fue desarrollado por primera vez por el matemático checo Vojtech Jarnik. Aunque no fue hasta 1957 cuando aparecía por primera vez publicado de forma independiente por el ingeniero informático estadounidense Robert C. Prim, quien le dio fama y por cuyo apellido es conocido. La solución al problema propuesto por Prim se basa en la idea de ir conectando nodos secuencialmente hasta alcanzarlos a todos. Teniendo como dato de entrada un grafo no dirigido, el algoritmo empieza a construir el árbol a partir de un nodo seleccionado arbitrariamente. A continuación, itera seleccionando en cada etapa el arco de menor coste (uno cualquiera si hay varios) que une un nodo del árbol con otro que aún no está en él, con la restricción de no poder formar ciclos. El proceso se repite hasta añadir todos los nodos, obteniendo como resultado un árbol de expansión cuyo coste será mínimo. 41 4.1.3 Algoritmo de Kruskal Su creación se debe a Joseph Kruskal (1956), compañero de Prim. Conocido desde entonces por su apellido, la idea principal del algoritmo de Kruskal se resume en conectar arcos, y no nodos, secuencialmente. De esta forma, es innecesario elegir un nodo de partida. El método comienza eligiendo el arco de menor coste de un grafo no dirigido. Este proceso de elegir los arcos de menor coste se continúa hasta unir todos los nodos del grafo sin formar lazos. O lo que es lo mismo hasta que el número de nodos sea igual al número de arcos menos uno. Finalmente, se obtiene un árbol mínimo de expansión. El algoritmo de Kruskal recibe especial atención por ser el algoritmo elegido para realizar el programa de resolución de árboles de Steiner en grafos. Se ha elegido esta metodología por ser muy simple de implementar computacionalmente. Se elige desde el primer paso el arco de menor coste y se hace en cada implementación un recuento de nodos raíces para evitar la formación de lazos. Para la posterior comprensión del programa implementado en Matlab sobre este método, se demuestra a continuación como se opera con este algoritmo en base a un ejemplo. Supongamos que se tiene el siguiente grafo mostrado en la Figura 27: Si ordenamos las aristas según los costes de menor a mayor obtenemos la Tabla 2: El primer paso del algoritmo es señalar el arco de menor coste a la vez que se le asigna el nodo 8 a la raíz del nodo 7 (podría haber sido al revés, esto se aplica para el resto de pasos) obteniendo los siguientes resultados. La Figura 28 muestra dichos cambios: Figura 27. Ejemplo Algoritmo de Kruskal Tabla 2. Costes asignados a las aristas del ejemplo ordenados de menor a mayor Figura 28. Primer paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 42 En el segundo paso, la Figura 29 señala el arco siguiente con menor coste (3-9) y se asigna el nodo 9 como raíz del nodo 3. En el tercer paso, la Figura 30 muestra el arco 6-7 que pasa a formar parte de la solución y se añade el nodo 6 a la raíz del nodo 7. En el cuarto paso, el arco 1-2 se puede también señalar y se incluye el nodo 1 a la raíz del nodo 2. En el quinto paso, el arco 3-6 se une al conjunto solución mientras que los nodos 3 y 9 se unen a la raíz del nodo 6. Como el nodo 6 es descendiente del nodo 7, los nodos 3 y 9 podrán ser descendientes directos del nodo 7. La Figura 32 señala las nuevas medidas adoptadas. Figura 29. Segundo paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente Figura 30. Tercer paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente Figura 31. Cuarto paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente Figura 32. Quinto paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 43 En el sexto paso, el arco 7-9 no se puede incluir a la solución porque el nodo 7 es ya la raíz del nodo 9. Esto es debido a que si se une dicho arco se forma un ciclo. Luego este arco no forma parte de la solución. En el séptimo paso, se une el arco 3-4 a la solución y en el diagrama de los nodos raíces, el nodo 4 pasa a formar descendencia del nodo raíz 7 ya que el nodo 3 es descendiente del nodo 7. La Figura 33 muestra las nuevas modificaciones en la solución. En el octavo paso, el arco 8-9 no pueden formar parte de la solución porque los nodos 8 y 9 ya comparten raíz del nodo 7. Luego, forman ciclo. En el noveno paso, el arco 1-8 pasa a ser solución mientras que tanto el nodo 2 como el 1 en el diagrama de nodos raíces pasan a formar parte de la descendencia del nodo 7. La Figura 34 lo muestra. En el décimo paso, no es posible agregar a la solución el arco 2-3 por formar lazo y por consiguiente ya son nodos pertenecientes a la misma raíz. En la Figura 35 , el undécimo paso cierra el árbol mínimo de Steiner incorporando el arco 4-5 a la solución. De la misma forma, el último nodo que falta por ser descendencia del nodo 7 se incorpora a dicha raíz. Por ende, se muestra la solución obtenida con las aristas resaltadas en negrita y el diagrama de nodos raíces solo muestra el nodo 7 como raíz de todos los nodos. Figura 33. Séptimo paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente Figura 34. Noveno paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente Figura 35. Undécimo paso del Algoritmo de Kruskal y diagrama de nodos raíces correspondiente 44 A continuación, se pasa a explicar los algoritmos genéticos que hacen uso del MST en primera instancia como se ha nombrado con anterioridad. 4.2 Algoritmos genéticos Los algoritmos genéticos (AGs) son métodos de optimización (Goldberg, 1989) basados en la teoría de Darwin (Tutter, 1989), como la vida biológica en nuestro mundo que envuelve los mecanismos de reproducción, mutación, competición y selección natural. En la naturaleza, los individuos de una población compiten entre sí en la búsqueda de recursos tales como comida, agua y refugio. Incluso los miembros de una misma especie compiten a menudo en la búsqueda de un compañero para producir descendencia. Aquellos individuos que tienen más éxito en sobrevivir y en atraer compañeros tienen mayor probabilidad de generar un gran número de descendientes. Por el contrario, individuos poco dotados producirán un menor número de descendientes. Esto significa que los genes de los individuos mejor adaptados se propagarán en sucesivas generaciones hacia un número de individuos creciente. La combinación de buenas características provenientes de diferentes antecesores puede a veces producir descendientes con muy buenas facultades, cuya adaptación es mucho mayor que la de cualquiera de sus ascendientes. De esta manera, las especies evolucionan logrando unas características cada vez mejor adaptadas al entorno en el que viven. El poder de los AGs proviene del hecho de que se trata de una técnica robusta y pueden tratar con éxito una gran variedad de problemas provenientes de diferentes áreas, incluyendo aquellos en los que otros métodos encuentran dificultades. Si bien no se garantiza que el AG encuentre la solución óptima del problema al final de las iteraciones, existe evidencia empírica de que se encuentran soluciones de un nivel aceptable, en un tiempo competitivo con el resto de los algoritmos de optimización combinatoria. Los AGs están compuestos generalmente de dos procesos. El primer proceso es la generación de individuos para la producción de la siguiente población y el segundo proceso es la manipulación de los individuos seleccionados para conformar la siguiente generación mediante las técnicas de cruzamiento (reproducción) y mutación. El mecanismo de selección determina cuáles son los individuos seleccionados para la reproducción y mutación. El principio más importante de la estrategia de selección es mientras mejor sea el individuo, mayor es su probabilidad de ser padre (Razali and Geraghty, 2011). El mecanismo de selección reduce el área de búsqueda dentro de la población descartando soluciones pobres, a su misma vez debe dar la oportunidad a todos los individuos ya sean buenos o malos de que puedan reproducirse. Es importante encontrar un equilibrio donde las soluciones pobres deben tener la oportunidad de ir a la siguiente generación, y las buenas soluciones pasen a la siguiente generación con más frecuencia que las soluciones pobres. El mecanismo de selección debe ser elegido de tal manera que la convergencia a la solución óptima global esté garantizada. Durante el desarrollo de los AGs, muchas estrategias de selección han sido propuestas y utilizadas tales como: Selección de Ruleta, Selección basada en Ranking o algunas selecciones aplicadas en estrategias evolucionarias (Geyer et al., 1999). Para desarrollar toda la teoría del algoritmo genético se comenzará en la sección 4.2.1 con la definición del problema continuando con los parámetros a tener en cuenta. Posteriormente, en 45 la sección 4.2.2 se explican las diferentes partes del algoritmo genético, las cuales son: codificación binaria de las soluciones, selección, reproducción, mutación y prevención de incesto. Adicionalmente, se proporciona en la sección 4.2.3 el funcionamiento específico del AG utilizado en el proyecto. Para concluir, en la sección 4.2.4 se describen las ventajas y desventajas de los AGs. 4.2.1 Definición del algoritmo genético Un algoritmo genético es un método iterativo de búsqueda de soluciones que imita la teoría de la evolución de Darwin para la resolución de problemas, como se puede intuir de la introducción. En el método, se parte de un conjunto de soluciones admisibles que forman la población inicial de la cual se seleccionan los individuos más capacitados (mejores soluciones). Aquellos individuos que demuestren mayor adaptación al medio se reproducen y mutan para finalmente obtener una mejor generación de soluciones. Antes de comenzar con el algoritmo, es necesario garantizar la diversidad de soluciones en la población inicial para poder abordar el problema desde diferentes puntos del espacio. Para poder asegurar que la solución final obtenida en el algoritmo sea la óptima o la más cercana al óptimo, el problema debe abarcar soluciones iniciales lo más alejadas posibles en el espacio tal como se muestra en la Figura 36. Donde cada punto de la gráfica representa una posible solución admisible y el eje de coordenadas determina el coste asociado a cada solución. Una vez que los individuos son elegidos aleatoriamente gracias al MST, se procede con el algoritmo de resolución que sigue los siguientes pasos. Para ello, será importante conocer que un gen es un arco del grafo. - Evaluar la puntuación de cada uno de los cromosomas generados, es decir, medir el coste total de cada una de las soluciones admisibles propuestas. - Permitir la reproducción de los cromosomas más adaptados al medio (con menor coste total). - Con cierta probabilidad de mutación, mutar un gen de un individuo cualquiera de la población. - Organizar la nueva población sustituyendo los individuos mutados por el individuo antes de mutar y el cromosoma obtenido por cruce por algún individuo con coste total alto. Dichas condiciones se repiten hasta que se da un argumento de salida, ya sea un número máximo de iteraciones o cuando no se produzcan más cambios en la población (convergencia del algoritmo). En el algoritmo genético utilizado se determina el fin del algoritmo una vez que se Figura 36. Espacio soluciones del problema de Steiner 46 llega a un número máximo de iteraciones. Se escogió dicha condición, en vez de la de convergencia del algoritmo, debido a que existen problemas de Steiner donde al realizar algunas iteraciones no se avanza en disminuir el coste total de las soluciones (dando a pensar que no hay más soluciones posibles) cuando si se continua, se pueden obtener mejores resultados. Para el estudio del algoritmo genético hay que tener en consideración una serie de parámetros que se irán cambiando en el análisis del algoritmo. El ajuste óptimo de los parámetros permite minimizar el tiempo de resolución de los problemas del árbol de Steiner, así como la mejora de la calidad de las soluciones. Dichos parámetros son: - Tamaño de la población: Determina el número de individuos de una población. En caso de que el tamaño sea muy pequeño, la búsqueda de soluciones será escasa y poco óptima. De lo contrario, si la población es demasiado amplia, el algoritmo genético será excesivamente lento. Estudios sobre el límite máximo de individuos de una población revelan que, a partir de un tamaño determinado, no se consigue una mayor velocidad en la resolución del problema. - Probabilidad de cruce: Indica la frecuencia con la que se producen cruces entre los cromosomas padre. - Probabilidad de mutación: Indica la frecuencia con la que los genes de un cromosoma son mutados. Se tomará siempre la probabilidad de cruce aproximadamente del 75-80% y la de mutación del 25-20%. Aparte, existen otros parámetros a determinar; cómo elegir los padres de entre la población para la reproducción y por qué individuo sustituir el cromosoma generado por reproducción. 4.2.2 Operaciones del algorítmo genético En el algoritmo genético va implícito el método para resolver el problema. Hay que tener en cuenta que el algoritmo genético es independiente del problema, lo cual lo hace un método potente, al resultar útil en cualquier ámbito de acción, pero a la vez débil, pues no está especializado en ninguno. Las soluciones codificadas en un cromosoma compiten para ver cuál constituye la mejor opción. Además, el resto de las soluciones ejercerá una presión selectiva sobre la población, de forma que sólo los que mejor se adaptan (aquellos que se acerquen a la solución) sobrevivan y dejen su material genético a las futuras generaciones, igual que en la evolución de las especies. La diversidad genética se introduce mediante mutaciones y reproducción sexual como se nombraba anteriormente. Por lo tanto, el método consiste en hallar de qué parámetros depende el problema, codificarlos en un cromosoma, y aplicar los métodos de la evolución: selección, reproducción sexual y mutaciones que generen diversidad. 4.2.2.1 Codificación binaria de los individuos Cada uno de los arcos del problema de Steiner presentará un gen, cuyo conjunto forma el cromosoma. Aquellos arcos que formen parte de la solución serán codificados como “1” y aquellos que estén excluidos de la solución valdrán “0”. Existirán tantos genes como arcos tenga el problema. 47 4.2.2.2 Selección Es necesario hacer una selección con los individuos más capacitados para que éstos sean los que se reproduzcan con mayor probabilidad de acuerdo con la teoría de Darwin. En la nombrada teoría, los cromosomas más capacitados son los que deben sobrevivir y crear una nueva descendencia más facultada. Por lo tanto, una vez evaluado cada cromosoma y obtenida su puntuación, se tiene que crear la nueva población teniendo en cuenta que los buenos rasgos de los mejores individuos se deben transmitir al futuro conjunto de soluciones. Se presentan a continuación las técnicas de selección llevadas a cabo en el algoritmo genético utilizado. 4.2.2.2.1 Selección aleatoria Consiste en la selección al azar de cualquiera de los cromosomas de la población. Es la selección utilizada a la hora de elegir un individuo para mutar o incluso para sustituir un cromosoma por un individuo cruzado, es decir, reproducido a partir de dos padres. 4.2.2.2.2 Selección por ruleta Consiste en obtener las probabilidades de los individuos en función de su coste. Así la probabilidad de un individuo i perteneciente a la población I vendrá determinada por: 𝑃𝑖=( 𝐶𝑜𝑠𝑡𝑒 𝑡𝑜𝑡𝑎𝑙𝑖 ∑𝐶𝑜𝑠𝑡𝑒 𝑡𝑜𝑡𝑎𝑙𝑖𝑖∈𝐼 )−1 Donde a mejor fitness (menor coste) tenga el cromosoma, mayor probabilidad tendrá de ser elegido. La selección por ruleta se puede utilizar para elegir a los padres para la reproducción. Si se utiliza 1/𝑃𝑖 para el cálculo de las probabilidades, se puede sustituir el hijo por un cromosoma con un coste total alto. Pues ahora, los individuos con mayor probabilidad de selección serán lo de peor fitness. 4.2.2.2.3 Selección por ranking Consiste en dar probabilidades a los cromosomas según la distribución geométrica. Primero se ordenan los cromosomas según sus costes de menor a mayor. De tal modo que, la probabilidad del cromosoma ubicado en la posición 𝑖 tendrá la probabilidad: 𝑃𝑖=𝑞(𝑞−1)𝑖 Donde q representa un parámetro de análisis en el método que varía entre 0.5 y 0.6 para ver si afecta al resultado final. Al igual que en la selección por ruleta, la selección por ranking es característica para elegir padres y si se utiliza la inversa de la fórmula se puede sustituir el hijo por un cromosoma con un coste total alto. Tanto para la selección por ruleta como para la selección por ranking, una vez obtenidas las 𝑃𝑖 se sigue con el siguiente procedimiento. Las probabilidades se sitúan en intervalos de forma que si son 0.5, 0.3 y 0.2 se forman intervalos 0-0.5, 0.5-0.7 y 0.7-1, respectivamente. A continuación, se elige un número generado aleatoriamente entre 0 y 1 que caerá en alguno de los tres intervalos presentados para dicho ejemplo. El cromosoma, cuya probabilidad corresponde al intervalo donde se encuentra el número aleatorio, será el seleccionado. 48 4.2.2.3 Reproducción La reproducción consiste en cruzar dos progenitores para crear descendencia. Las reglas establecidas para obtener una combinación binaria de números serán: - Si el gen de la posición 𝑖 de ambos progenitores es igual, el hijo hereda ese gen. - Si el gen de la posición 𝑖 de ambos progenitores difiere, el hijo puede heredar cualquiera de los genes situados en la posición 𝑖. Para determinar los genes del descendiente que pueden variar por no ser los genes de los padres iguales, es necesario determinar el árbol de mínima expansión para forzar admisibilidad en la solución y poder reemplazar la nueva solución por otra de la población. 4.2.2.4 Mutación La mutación se lleva a cabo cambiando uno de los genes de un individuo que valga 1 por un 0. Se podría haber elegido cambiar un 0 por un 1, pero como después es necesario aplicar el MST para forzar la admisibilidad de la solución, se ha elegido pasar de 1 a 0 para evitar complicaciones. En las instrucciones seguidas por el MST, habrá que darle un coste muy elevado al arco que pasa a 0 para forzar dicho arco a que no forme ya parte de la solución. 4.2.2.5 Prevención de incesto Se trata de una medida para evitar elegir padres con un parecido genético por encima de un porcentaje determinado. De esta forma, se evitaría que el programa converja en las primeras iteraciones, ya que, si la mayoría de las soluciones se parecen, no existe diversidad y se puede dar por solución un mínimo local. Poder evitar este hecho permite realizar una mayor exploración de soluciones posibles. En la práctica, la prevención de incesto más que una ayuda resulta ser un inconveniente. Esto tiene su explicación a que hay problemas en los que rápidamente todos los individuos de la población tienen un parecido por encima de un 60%, como se ha estudiado, antes de llegar a la última iteración programada. Si se aplica la prevención de incesto, el programa no permite seguir iterando, pues no se encuentra ningún progenitor con menor parentesco. El problema de la rápida convergencia, que se podría evitar con la prevención de incesto, es resuelto implementando 30 poblaciones, en vez de una, donde finalmente se elige el mejor resultado de entre las 30 poblaciones generadas. Así, se solventa el problema de no realizar una buena exploración de soluciones posibles a pesar de tener una población inicial diversificada. Por ello, aunque alguna de las poblaciones dé cómo mejor solución un mínimo local, existen otras 29 poblaciones diversificadas en el espacio que proporcionan otros resultados. 4.2.3 Funcionamiento del algoritmo genético Para comprender el funcionamiento completo del algoritmo genético llevado a cabo en este estudio se procede a explicar el procedimiento seguido. 1. Lo primero de todo es codificar cada solución admisible de la población en código binario. 2. Una vez que se tiene una población diversificada se procede a realizar tantos cambios en 49 la población mediante reproducción y mutación como iteraciones se quieran obtener. 3. El 75-80% de las veces se optará por la reproducción donde se eligen dos padres de entre las mejores soluciones (bajo coste) y se obtiene un hijo a partir de ellos que se sustituirá en la población por una solución con peor fitness (alto coste) para así ir formando una población de soluciones cada vez más próximas al óptimo. 4. El 20-25% de las veces se produce mutación donde un gen del cromosoma cambia su valor y la nueva solución es reemplazada por la solución elegida para mutar. Con ello, se consigue explorar más lugares del espacio de soluciones. 5. Finalmente, cuando se han realizado todas las iteraciones se elige el individuo de la población con mejor fitness (menor coste). 4.2.4 Ventajas e inconvenientes Al igual que cualquier método o técnica, el algoritmo genético también tiene ventajas e inconvenientes. Entre las ventajas: - Los algoritmos genéticos son intrínsecamente paralelos al operar simultáneamente con varias soluciones. En vez de trabajar de forma secuencial como las técnicas tradicionales, los algoritmos genéticos son capaces de explorar el espacio de soluciones en varios lugares al mismo tiempo. Si la solución que descubren resulta subóptima basta con desecharla y seguir por otros caminos. - Por otro lado, los problemas de optimización resueltos con algoritmos genéticos resultan menos afectados por mínimos locales (falsas soluciones) que las técnicas tradicionales. Muchos algoritmos de búsqueda pueden dar soluciones de óptimos locales ya que en la cercanía no existen mejores soluciones. Sin embargo, el algoritmo genético al explorar el espacio de soluciones de forma diversificada evita este problema. - No necesitan conocimientos específicos sobre el problema que intentan resolver. Realizan cambios aleatoriamente en sus soluciones candidatas y luego utilizan la función de aptitud para determinar si esos cambios producen una mejora o no. - Resulta sumamente fácil ejecutarlos en las modernas arquitecturas masivas en paralelo. - Usan operadores probabilísticos, en vez de los típicos operadores determinísticos de otras técnicas. El algoritmo genético también contiene desventajas citadas a continuación: - Pueden tardar mucho en converger o no converger en absoluto, dependiendo en cierta medida de los parámetros que se utilicen; tamaño de población, número de generaciones… - Pueden converger prematuramente debido a una serie de problemas. Si un individuo que es más apto que la mayoría de sus competidores emerge muy pronto en el curso de la ejecución, se puede reproducir tan abundantemente que merme la diversidad de la población demasiado pronto. Ello provoca que el algoritmo converja hacia el óptimo local que representa ese individuo, en lugar de rastrear el paisaje adaptativo lo bastante a fondo para encontrar el óptimo global. Esto es un problema especialmente común en las poblaciones pequeñas, donde incluso una variación aleatoria en el ritmo de reproducción puede provocar que un cromosoma se haga dominante sobre los otros. 56 5.2.2 Variables de la función En la Figura 44 se muestran las variables utilizadas en esta función. 5.2.3 Pseudocódigo Se introduce para la comprensión del pseudocódigo, el significado de las siguientes variables relevantes: ▪ nsteiner: vector final que contiene el valor de los nodos Steiner ▪ terminales: valor de los nodos terminales contenidos en un vector ▪ numvert: variable con el número de arcos del problema ▪ numterm: variable con el número de nodos terminales ▪ nodostn: vector que contiene números del 1 al valor “numvert” Algoritmo 2: Pseudocódigo de la función ‘steiner’ Función [nsteiner]=steiner(terminales, numvert) Generar variable “numterm” que representa el número de nodos terminales Generar vector “nsteiner” de dimensión 1 𝑥 número de nodos Steiner, lleno de ceros Generar vector “nodostn” de dimensión 1 𝑥 “numvert” que contiene números de 1 a “numvert” Generar variables i y j con valor de 1 cada una Mientras i<=numvert Mientras j<=numterm Si i=terminales(j) Poner nodostn(i) a 0 Fin Si Implementar j Fin Mientras Implementar i //Se han rellenado de 0 las celdas de “nodostn” donde aparecían los nodos terminales Figura 44. Variables de la función ‘steiner’ 57 Fin Mientras Poner j e i a 1 Mientras i<=numvert Si nodostn(i) distinto a 0 Copiar valor nodostn(i) en nsteiner(j) Sumar 1 a variable j Fin Si Implementar i Fin Mientras Fin Función //Los nodos que queden en el vector “nodostn” serán los nodos Steiner que no habrán sido cambiados a 0 58 5.2.4 Diagrama de flujo Se presenta en la Figura 45 el diagrama de flujo de la función ‘steiner’. A través de la utilización de dos bucles independientes donde uno de ellos muestra otro bucle en el interior, se pretende dar solución al vector “nsteiner”. Es importante recalcar la importancia del primer comando “if” que permite sustituir a los nodos terminales por 0. Figura 45. Diagrama de flujo de la función ‘steiner’ 59 5.3 Función ‘steinerorden’ Esta función es de vital importancia para poder podar los nodos Steiner de grado 1. A continuación se muestra detalladamente el objetivo de la función, sus variables, el pseudocódigo y el diagrama de flujo. 5.3.1 Objetivo La función ‘steinerorden’ ordena los nodos Steiner según el número de aristas activas quedando al final del vector los nodos Steiner que no participan en la solución. Las aristas activas son aquellas que forman parte de la solución que desembocan en un nodo Steiner. De este modo, según el orden de los nodos Steiner guardados en el vector “nsteiner”, se introduce en el vector “cont” el número de aristas activas de cada nodo Steiner, tal como muestra la Figura 46. Finalmente, en el vector “nsteinerord” se guardan los nodos Steiner contenidos en el vector “nsteiner” ordenados de menor a mayor número de aristas activas tengan. Hay que tener en cuenta que aquellos nodos no participes de la solución final, como es el caso del nodo número dos de la Figura 46 adjunta, tomará el valor cero en el vector final “nsteinerord”. Es importante considerar que para el funcionamiento de la función ‘steinerorden’ se requiere de la solución del MST, que se encuentra en la variable llamada “solorden”. Su obtención aún no se ha comentado debido a que es el objetivo de la función ‘solucionado’. Se ha preferido comentar antes esta función pues posteriormente resultará más sencillo el entendimiento de la función ‘solucionado’. Por el momento, se considera que la variable “solorden” viene dada. 5.3.2 Variables de la función Se muestran las variables de la función en la Figura 47. Figura 46. Esquema de cómo ordenar el número de aristas activas que puede tener un nodo Steiner 60 5.3.3 Pseudocódigo Las variables necesarias para realizar el programa son: ▪ nsteiner: vector que proporciona los nodos Steiner ▪ stein: matriz de datos que contiene los arcos con los costes correspondientes ▪ numarist: número de aristas del problema ▪ solorden: solución del problema ▪ nsteinerord: nodos Steiner ordenados de menos a mayor número de aristas activas ▪ cont: número de aristas activas que llegan a cada uno de los nodos Steiner Algoritmo 3: Pseudocódigo de la función ‘steinerorden’ Función [nsteinerord]=steinerorden(nsteiner, stein, numarist, solorden) Generar matriz “cont” llena de ceros con las dimensiones del número de nodos Steiner Generar matriz “nsteinerord” igual a “cont” Mientras j<= al número de nodos Steiner Mientras i<= numarist Si stein(i,1)=nsteiner(j) o stein(i,2)=nsteiner(j) Si solorden(i)=1 Entonces se le suma uno a variable “cont” Fin Si Fin Si Implementar variable i Fin Mientras Figura 47. Variables de la función ‘steinerorden’ 61 Implementar variable j Fin Mientras Poner j a 1 Mientras k<=máximo de los valores contenidos en matriz “cont” Mientras i<=dimensión nsteiner Si cont(i)=k Copiar nsteiner(i) en nsteinerord(j) Implementar j Fin Si Implementar i Fin Mientras Implementar k Fin Mientras Fin Función 5.3.4 Diagrama de flujo En la Figura 48 se muestra el diagrama de flujo diseñado a partir de los requisitos de la función ‘steinerorden’. Se puede distinguir entre un primer gran bucle y un bucle secundario. Por otro lado, la existencia de los tres comandos “if” hace posible el funcionamiento de la función. 62 Figura 48. Diagrama de flujo de la función ‘steinerorden’ 63 5.4 Función ‘solucionado’ Mediante la función ‘solucionado’ se da cierre a la aplicación del MST en el algoritmo de programación seguido. Pues, esta función proporciona en código binario la solución del MST para obtener la población inicial. Se divide este apartado en objetivo, variables, pseudocódigo y disgrama de flujo. 5.4.1 Objetivo Mediante la función ‘solucionado’ se pretende obtener el vector solución de dimensiones el número de arcos del grafo relleno de ceros y unos (en código binario) nombrado “solorden” como se puede ver en la Figura 49. Un 0 significará que el arco correspondiente a esa fila no forma parte de la solución y un uno, por el contrario, representa que dicho arco sí forma parte del árbol final. Como se explicó en la sección ¡Error! No se encuentra el origen de la referencia., para la i mplementación del MST se hace uso del algoritmo de Kruskal y se procede de la forma explicada en la sección señalada. La obtención de la solución proporcionada por el MST es fruto de la introducción de los parámetros iniciales y de la utilización de las funciones explicadas hasta ahora. 5.4.2 Variables de la función Las variables utilizadas en la función se adjuntan en la Figura 50. Figura 49. Esquema de cómo obtener una solución admisible en código binario 64 5.4.3 Pseudocódigo Las variables importantes para el entendimiento del pseudocódigo son: ▪ nodopad: es una matriz interna con dos filas y de columnas el número de nodos del problema llena de números del 1 al número de nodos totales. Ello se repite tanto para la primera fila como para la segunda ▪ numsteiner: variable de valor el número de nodos Steiner ▪ cont: vector repleto de ceros con dimensión “numsteiner” Algoritmo 4: Pseudocódigo de la función ‘solucionado’ Función [solorden]=solucionado(numarist, numvert, stein, terminales) Generar matriz “nuevostein” mediante la función ‘orden’ con entradas “stein” y “numarist” Generar matriz “nodopad” igual a matriz de dimensión 2 𝑥 “numvert” rellena de número de 1 a “numvert” tanto para la primera fila como para la segunda. Generar vector “sol” completo de números del 1 a “numarist” Mientras i<=numarist Mientras j=1<=numvert Si nuevostein(i,1) es igual a nodopad(i,j) m=j Fin Si Si nuevostein(i,2) es igual a nodopad(i,j) n=j Fin Si Implementar j Figura 50. Variables de la función ‘solucionado’ 65 Fin Mientras Si nodopad(2,m) es igual a nodopad(2,n) sol(i)=0 Sino si nodopad(1,m) es igual a nodopad(2,m) nodopad(2,m) es igual a nodopad(2,n) sol(i) es igual a 1 Mientras k<=numvert Si nodopad(2,k) es igual a nodopad(1,m) nodopad(2,k)=nodopad(2,m) Fin Si Implementar k Fin Mientras Sino si nodopad(1,m) es distinto de nodopad(2,m) nodopad(2,nodopad(2,m)) es igual a nodopad(2,n) p es igual a nodopad(2,m) Mientras l<=numvert Si nodopad(2,l) es igual a p nodopad(2,l) es igual a nodopad(2,nodopad(2,n)) Fin Si Implementar l Fin Mientras sol(i) es igual a 1; Fin Sino si Fin Sino si Fin Si Implementar i Fin Mientras Generar vector “nsteiner” mediante la función ‘steiner’ con las entradas “terminales” y “numvert” Generar variable “numsteiner” igual al tamaño de “nsteiner” Generar vector “steinerord” mediante la función ‘steinerorden’ con entradas “nsteiner”, “nuevostein”, “numarist” y “sol” 72 Implementar i Fin Mientras Fin Función 5.6.4 Diagrama de flujo El diagrama de flujo de la Figura 56 esquematiza el funcionamiento del pseudocódigo. Se muestra como a partir de la definición de unos cuantos parámetros y de la utilización de un bucle, es posible obtener las dos matrices que son objeto de la función. 5.7 Función ‘crossing’ Mediante la función destinada al entrecruzamiento será posible obtener un vector solución que previamente hay que forzar su admisibilidad haciendo uso del MST como se indicaba en la sección 4.2.2.3. Al igual que en el resto de funciones, se comienza la sección con el objetivo. Figura 56. Diagrama de flujo de la función ‘definitivo’ 73 5.7.1 Objetivo La función ‘crossing’ se encarga de obtener un vector solución “hijo” a partir del entrecruzamiento de los vectores “padre” y “madre”. Cuando ambos progenitores sean 1, el hijo también valdrá 1 y cuando valgan 0, el hijo valdrá 0. En cambio, cuando los progenitores contengan valores distintos, podrá valer la celda correspondiente del vector “hijo” 1 o 0, el cual se determina aplicando el árbol de distancia mínima para asegurar admisibilidad. La Figura 57 sirve de ejemplo para el entendimiento de la función. La función ‘solucionado’ tiene un rol crucial dentro de la función ‘crossing’ ya que se encargará de validar la admisibilidad de la solución hijo. Para entender el funcionamiento de la función en cuestión, se muestra a continuación como se forman los costes de la matriz “stein” proporcionada a la función ‘solucionado’ para dar admisibilidad a la variable “hijo”. 5.7.1.1 Planteamiento Para poder aplicar el árbol de mínima distancia, habrá que fijar unos costes; las celdas del vector “hijo” que contengan 1 tendrán mínimo coste (deberán estar dentro de la solución), las celdas que valgan 0 tendrán el coste más elevado que es 16 (ya que no forman parte de la solución) y las celdas del vector “hijo” donde se puede elegir 1 o 0, obtendrán un coste aleatorio entre 1 y 15. Así el propio algoritmo del árbol de distancia mínima determinará el valor de las celdas del vector “hijo” donde hay opción de elegir entre 1 o 0 sin formar bucles que puedan empeorar el resultado de la solución. Por eso, a partir de definir los costes, según las instrucciones indicadas, se obtiene aplicando el MST el vector “hijo” con la garantía de que no existen caminos redundantes en la solución. Un ejemplo de ello se muestra en la Tabla 3. Figura 57. Obtención del vector “hijo” a partir de la reproducción 74 5.7.2 Variables de la función En la Figura 58 se muestran las variables utilizadas para la implementación de la función. Figura 58. Variables de la función ‘crossing’ 5.7.3 Pseudocódigo Las variables importantes para la comprensión del código son: ▪ padre y madre: vectores progenitores con soluciones diferentes ▪ steincruce: matriz de dimensiones 3 𝑥 número de arcos, que contiene los costes para ajustar el vector solución “hijo” Algoritmo 8: Pseudocódigo de la función ‘crossing’ Función [hijo]=crossing(padre, madre, stein, numvert, terminales) Generar variable “numarist” que contiene las dimensiones del “padre” Generar vector “hijo” con dimensiones “numarist” repleta de ceros Generar matriz “steincruce” de dimensiones 3x “numarist” donde las dos primeras columnas son iguales que la matriz “stein” y la última columna está llena con el número 16 Mientras i<=numarist Si padre(i)=madre(i) y padre(i)=0 hijo(i)=0 Sino Tabla 3. Cómo pasar del vector ‘hijo’ a la obtención de los costes para aplicar el MST 75 hijo(i)=1 y steincruce(i,3)=1 Fin Si Si padre(i) distinto madre(i) hijo(i)=1 y steincruce(i,3)= número aleatorio entre 1 y 15 Fin Si Fin Mientras hijo=solucionado(numarist, numvert, steincruce,terminales) Fin Función 76 5.7.4 Diagrama de flujo En la Figura 59 se muestra el diagrama de flujo de la función ‘crossing’. Un bucle de gran tamaño será el dominante del diagrama. A su vez, en el interior de este bucle se muestran tres comandos “if”. Figura 59. Diagrama de flujo de la función ‘crossing’ 77 5.8 Función ‘mutacion’ A continuación, se presenta la función que permite realizar cambios aleatorios en los genes de los individuos. El objetivo, las variables de la función, el pseudocódigo y un diagrama de flujo son los subapartados que dan paso al entendimiento de la función. 5.8.1 Objetivo Mediante esta función se pretende mutar un gen que valga 1 a 0 de una de las soluciones de la matriz “matrizsol”. El individuo de la población se elige, o bien aleatoriamente, o mediante ranking o ruleta de reemplazo. Dando mayor probabilidad para mutar a aquellas soluciones que tengan peor “fitness” y, por tanto, un coste total de las aristas elevado. Posteriormente, para asegurar la admisibilidad de la solución será necesario aplicar el MST. Para ello, se hace inclusión de nuevo de la función ‘solucionado’. 5.8.1.1 Planteamiento Una vez elegida la solución y el gen que mutar, se deberá utilizar el MST. Para poder aplicar el árbol de mínima distancia, habrá que fijar unos costes; las celdas de la solución a mutar que contengan 1 tendrán mínimo coste (deberán estar dentro de la solución), las celdas que valgan 0 tendrán un coste aleatorio entre 1 y 15 y la celda elegida para ser mutada tendrá el mayor coste, en este caso, infinito o simplemente 16. Esto es debido, a que el gen mutado a 0 no seguirá formando parte de la solución. Finalmente, aplicando el MST se obtiene la solución mutada que cumple admisibilidad en la solución. 5.8.2 Variables de la función A continuación, en la Figura 60 se presentan las variables empleadas en la función ‘mutacion’. 5.8.3 Pseudocódigo Las variables de interés son las siguientes: Figura 60. Variables de la función ‘mutacion’ 78 ▪ mutado: vector con la solución a mutar ▪ steinmutado: vector con aristas y costes preparados para poder formar la solución admisible ▪ flat1: bandera que puede valer 1 o 0 en función de si se ha encontrado aleatoriamente un gen dentro del individuo que valga 1 para mutar a 0 ▪ elegido: determina el tipo de selección del individuo a mutar un gen, que puede ser aleatoriamente, ruleta o ranking Algoritmo 8: Pseudocódigo de la función ‘crossing’ Función [matrizsol]=mutacion(matrizsol, elegido, stein, numvert, nterminales) Generar variable “numarist” mediante la dimensión de las filas de “matrizsol” Generar variable “flat1” igual a 0 Generar vector “mutado” repleto de ceros de dimensiones “numarist” “mutado” es igual a solución de “matrizsol” elegida para ser mutada Mientras flat1 igual a 0 aleatorio es un número entre 1 y “numarist” elegido de forma aleatoria Si matrizsol(elegido, aleatorio)=1 flat1=1 Fin Si Fin Mientras Generar matriz “steinmutado” de dimensiones “numarist” 𝑥 3 llena de ceros Poner las dos primeras columnas de “steinmutado” iguales al vector “stein” Mientras i<= numarist Si mutado(1, i)= 1 steinmutado(i, 3)= 1 Sino steinmutado(i, 3)= número aleatorio entre 1 y 15 Fin Si Implementar i Fin Mientras steinmutado(aleatorio, 3)= infinito matrizsol(elegido, :)= solucionado(numarist, numvert, steinmutado, nterminales) Fin Función 79 5.8.4 Diagrama de flujo En la Figura 61 se da paso al diagrama de flujo compuesto por 4 comandos “if” y un solo bucle “for”. A pesar de la sencillez que puede desprender el objetivo de esta función, todo lo contrario se muestra en el diagrama de flujo. Figura 61. Diagrama de flujo de la función ‘mutacion’ 80 5.9 Función ‘seleccion’ En esta función se encuentran todas las formas posibles de selección de soluciones; ruleta, ranking y aleatorio. El apartado esta dividido en objetivo variables de la función, pseudocódigo y diagrama de flujo. 5.9.1 Objetivo Se pretende obtener la capacidad de elegir entre las soluciones de la matriz “matrizsol” un individuo aleatoriamente o por selección/ reemplazo ranking o ruleta. Para ello, habrá primero que indicar al programa mediante la variable de entrada “bandera”, que tipo de selección se quiere realizar. Se puede elegir entre: bandera igual a 0 (aleatoriamente), bandera igual a 1 (selección por ruleta), bandera igual a 2 (selección por ranking), bandera igual a 3 (reemplazo por ruleta) o bandera igual a 4 (reemplazo por ranking). A continuación, se muestra el funcionamiento del programa y sus variables. 5.9.2 Variables de la función Aquí se muestran las variables de la función en la Figura 62. 5.9.3 Pseudocódigo Las variables de interés son: ▪ elegido: número de fila de la matriz “matrizsol” que va a ser elegido para ser mutado, para ser individuo progenitor o para ser reemplazado ▪ bandera: indica el tipo de selección elegida para determinar la variable “elegido” ▪ q: probabilidad de la primera solución en la selección por ranking ▪ rango: matriz imprescindible para acumular las probabilidades y crear rangos de estas por individuo ▪ probabilidad: vector que contiene las probabilidades de cada solución elegidas por ruleta, ranking o aleatoriamente Figura 62. Variables de la función ‘seleccion’ 81 ▪ fitness: vector que contiene el coste total de cada solución ▪ sumfitness: suma los valores de “fitness” o 1/ “fitness” ▪ fitnessordenado: ordena la matriz “fitness” en función de los costes de menor a mayor Algoritmo 9: Pseudocódigo de la función ‘selección’ Función [elegido]=selección(matrizsol, stein, bandera, q) Generar “N” igual al número de soluciones dentro de la matriz “matrizsol” Generar “fitness”, matriz de dos columnas la primera llena de números de 1 a “N” y la otra matrizsol(:, ) 𝑥 stein(:, 3) Generar “fitnessordenado”, matriz de dos columnas; la primera llena de números de 1 a “N” y la otra con los valores de la segunda columna de “fitness” ordenados de menor a mayor Mientras i<=N Mientras i<=N Si fitness(j, 2)= fitnessordenado(i, 2) Fitnessordenado(i,1)= fitness(j, 1) Fin Si Implementar i Fin Mientras Implementar i Fin Mientras Si bandera= 0 // aleatorio elegido= número aleatorio entre 1 y “N” Sino Generar “probabilidad” igual a un vector lleno de ceros de dimensión 1 𝑥 “N” Si bandera= 1 // ruleta de selección Generar “sumfitness” igual a 0 Mientras i<= N sumfitness= sumfitness+1/fitness(i, 2) Implementar i Fin Mientras Mientras i<= N probabilidad(i)= 1/fitnessordenado(i, 2)/ sumfitness Implementar i 88 ▪ fitnessiter: vector que se modifica en cada población que contiene el mejor fitness en cada una de las iteraciones ▪ elección: es un número aleatorio entre 0 y 1 ▪ elegido, elegido1, elegido2, elegido3: números obtenidos según la función ‘selección’ ▪ hijo: solución obtenida entrecruzando dos padres ▪ fitness: vector que contiene los costes de cada solución de la población i que se modifica cada iteración ▪ ultimasolucion: mejor solución de la población i ▪ minpoblacion: vector que contiene el mejor coste de cada población ▪ steincost: se genera cada población y es la variable que permite generar individuos nuevos ▪ coste: guarda el coste de la mejor solución ▪ posicion: variable auxiliar ▪ solucionfinal: brinda la solución óptima o la más cercana a él Algoritmo 10: Pseudocódigo de la función ‘genetico1’ Función [solucionfinal, coste, poblacion]=genetico1(numvert, numarist, stein, terminales, N, q, iteraciones) Generar tic Generar matriz “matrizsol”= definido(numvert, numarist, stein, terminales, N) Generar vector “fitnessiter” de dimensiones “iteraciones” relleno de ceros Generar estructura “poblacion”=struct(‘fitness’, [], ‘minimo’, [], ‘solucion’, []) Mientras i<= “iteraciones” elección= aleatorio de 0 a 1 Si elección>=0 y elección< 0.15 elegido=seleccion(matrizsol, stein, 0, q) matrizsol=mutacion(matrizsol, elegido, stein, numvert, terminales) Fin Si Si eleccion>= 0.15 elegido1=seleccion(matrizsol, stein, 1, q) elegido2=seleccion(matrizsol, stein, 1, q) hijo=crossing(padre, madre, stein, numvert, terminales) elegido3=seleccion(matrizsol, stein, 4, q) matrizsol(elegido3, :)=hijo(:) Fin Si Generar matriz “fitness”= [(1:N)’,(matrizsol(:, :)*stein(:, 3))] 89 fitnessiter(i) es igual al mínimo de fitness(:, 2) Implementar i Fin Mientras Mientras j<=1 Si fitness(j, 2)= fitnessiter(iteraciones) posicion=j Fin Si Implementar j Generar vector ultimasolucion= matrizsol(posicion, :) Generar vector “minpoblacion” de dimensión 30 minpoblacion(1)= min(fitnessiter) poblacion(1).fitness= fitnessiter poblacion(1).minimo= minpoblacion(1) poblacion(1).solucion= ultimasolucion Mientras j<=29 matrizsol= definitivo(numvert, numarist, stein, terminales, N) steincost= costealeatorio(stein, numarist) matrizsol(1, :)= solucionado(numarist, numvert, steincost, terminales) Mientras i<= iteraciones elección igual a número aleatorio entre 0 y 1 Si eleccion>= 0 y eleccion< 0.15 elegido= seleccion(matrizsol, stein, 0, q) matrizsol= mutacion(matrizsol, elegido, stein, numvert, terminales) Fin Si Si eleccion>= 0.15 elegido1= seleccion(matrizsol, stein, 1, q) elegido2= seleccion(matrizsol, stein, 1, q) hijo=crossing(padre, madre, stein, numvert, terminales) elegido3= seleccion(matrizsol, stein, 4, q) matrizsol(elegido3, :)= hijo(:) Fin Si 90 fitness= [(1: N), (matrizsol(:, :)* stein(:, 3))] fitnessiter(i)= min(fitness(:, 2)) Implementar i Fin Mientras Mientras k<= N Si fitness(j, 2)= fitnessiter(iteraciones) Generar variable posicion igual a k Fin Si Implementar k Fin Mientras ultimasolucion= matrizsol(posición, :) minpoblacion(j+1)= min(fitnessiter) población(j+1).fitness= fitnesiter población(j+1).minimo= minpoblacion(j+1) Implementar j Fin Mientras Generar coste= min(minpoblacion) Mientras j<=30 Si minpoblacion(j, 1)= coste posicion= j Fin Si Implementar j Fin Mientras solucionfinal= población(posición).solucion Generar toc Fin Función 5.10.4 Diagrama de flujo Se muestra el diagrama de flujo de la función ‘genetico1’ el cual está dividido en dos figuras debido a su gran dimensión. Se puede ver el denso contenido de las órdenes para el funcionamiento completo del programa. 91 Figura 66. Diagrama de flujo de la función ‘genetico1’ parte I 92 Figura 67. Diagrama de flujo de la función ‘genetico1’ parte II 93 RESULTADOS “Lo bueno se hace esperar” Dicho popular En este último capítulo, fruto de la investigación y observación de todo lo relatado hasta el momento, se van a exponer una serie de problemas cuyas soluciones son conocidas. La intención es, por tanto, contrastar los óptimos de los problemas de Steiner con las soluciones obtenidas en el algoritmo desarrollado en este documento. Se pretende plasmar la utilidad y precisión de los algoritmos genéticos, así como dar conclusiones en base al estudio realizado en este capítulo. En primer lugar, la sección 6.1 comienza con las características de los problemas de Steiner de estudio. Durante la sección 6.2, se abrirá paso a los resultados del programa utilizado. Así como se mostrarán las gráficas de evolución y en la sección 6.4 se explican las curvas de superficies. 6.1 Características de los problemas Para el análisis y la comprobación de la teoría y el algoritmo heurístico desarrollado en este trabajo, se han utilizado los problemas que se encuentran en la “OR library” del “Imperial College” de Londres. Estos problemas se encuentran clasificados en “b” y “c” en función de su complejidad y dimensión de manera ascendente. A continuación, para su posterior estudio se presentan en la Tabla 5 y Tabla 6 las características de los problemas de tipo “b” y “c”, los cuales van a ser estudiados. Estas son; el número de nodos, el número de arcos, el número de nodos terminales, el óptimo del problema, así como el nombre destinado a cada problema. Como se puede comprobar, la primera colección alberga 18 problemas, mientras que de la colección steinc se van a analizar los 10 primeros problemas de Steiner. Se centra la atención en estos problemas en particular para obtener resultados de precisión y contundentes. 94 Tabla 5. Problemas steinb Problemas Nº Nodos Nº Arcos Nº Terminales ÓPTIMO steinb1 50 63 9 41 steinb2 50 63 13 58 steinb3 50 63 25 62 steinb4 50 100 9 59 steinb5 50 100 13 56 steinb6 50 100 25 116 steinb7 75 94 13 74 steinb8 75 94 19 75 steinb9 75 94 38 75 steinb10 75 150 13 71 steinb11 75 150 19 86 steinb12 75 150 38 152 steinb13 100 125 17 128 steinb14 100 125 25 153 steinb15 100 125 50 220 steinb16 100 200 17 117 steinb17 100 200 25 101 steinb18 100 200 50 182 Tabla 6. Problemas steinc Problemas Nº Nodos Nº Arcos Nº Terminales ÓPTIMO steinc1 500 625 5 60 steinc2 500 625 10 137 steinc3 500 625 83 549 steinc4 500 625 125 731 steinc5 500 625 250 960 steinc6 500 1000 5 55 steinc7 500 1000 10 102 steinc8 500 1000 83 459 steinc9 500 1000 125 675 steinc10 500 1000 250 1009 Dichos problemas contienen tanto nodos terminales como nodos Steiner, los cuales pueden tener solamente un grado. De aquí la importancia comentada en la sección 2.2 de que el programa pueda deshacerse de ellos antes de comenzar a iterar y a generar soluciones. A continuación, en la Gráfica 2 se aprecian el número de nodos, arcos y nodos terminales en función del problema, primero los de tipo “b” y luego los de tipo “c”. 95 Se puede ver como no existe una relación lineal, pero se muestra una clara tendencia al alza. En especial, el número de arcos va creciendo de forma escalonada muy pronunciada a medida que aumenta el número del problema. Por tanto, su dificultad aumenta. El número de nodos para los problemas steinb oscila de 50 a 100. Mientras que para los problemas steinc se observa una subida en el número de nodos a 500 que se mantiene constante para toda la colección de problemas tipo c. En la Gráfica 3 se puede ver con más precisión la relación de nodos totales y nodos terminales. Aquí se muestra la forma de sierra de los nodos terminales y cómo a partir de los problemas de tipo “c” se pasa de 100 nodos totales a 500. Se puede intuir que la densidad de los nodos terminales (nodos totales entre nodos terminales) también tendrá forma de sierra debido a la forma de los nodos terminales y al ser prácticamente constante los nodos terminales en dos tramos del gráfico. Gráfica 3. N.º de nodos totales y nodos terminales en relación al tipo de problema 0 200 400 600 800 1000 1200 steinb1 steinb2 steinb3 steinb4 steinb5 steinb6 steinb7 steinb8 steinb9 steinb10 steinb11 steinb12 steinb13 steinb14 steinb15 steinb16 steinb17 steinb18 steinc1 steinc2 steinc3 steinc4 steinc5 steinc6 steinc7 steinc8 steinc9 steinc10 Numero de problemas de las colecciones steinb y steinc Nº de nodos, arcos y nodos terminales en función del problema Nº nodos Nº arcos Nº terminales 0 100 200 300 400 500 600 steinb1 steinb2 steinb3 steinb4 steinb5 steinb6 steinb7 steinb8 steinb9 steinb10 steinb11 steinb12 steinb13 steinb14 steinb15 steinb16 steinb17 steinb18 steinc1 steinc2 steinc3 steinc4 steinc5 steinc6 steinc7 steinc8 steinc9 steinc10 Número de problemas de las colecciones steinb y steinc Nº de nodos y nodos terminales en función del problema Nº nodos Nº terminales Gráfica 2. N.º de nodos, arcos y terminales en función del problema 96 6.2 Resultados de la ejecución En este apartado se muestran los resultados y simulaciones obtenidos por el programa MATLAB al implementar el algoritmo heurístico desarrollado y el árbol mínimo de expansión con los problemas de Steiner de la “OR Library”. Todos los resultados han sido realizados con un procesador Intel Core i5 de séptima generación y una memoria RAM de 8GB. En el subapartado 6.2.1 se muestran los resultados del algoritmo genético y en la subsección 6.2.2 se visualizan los resultados del MST. 6.2.1 Resolución del algoritmo genético Para poder obtener los resultados del algoritmo genético se ha hecho uso del MST para la generación inicial de soluciones. Es importante recordar que para evitar la prevención de incesto a su vez de para obtener soluciones variadas, en cada problema se generan 30 poblaciones de N soluciones que se iteran un número dado de veces. En la Tabla 7 se muestra para los problemas de tipo “b”, el óptimo, la solución del algoritmo genético, el tiempo de implementación en segundos y el error relativo cometido por el algoritmo genético sobre el óptimo. En el caso de la Tabla 7 se han realizado 500 iteraciones a las 30 poblaciones escogidas de 100 individuos cada uno. Tabla 7. Resultados del algoritmo genético para los problemas de tipo b Problema ÓPTIMO Sol. Algoritmo genético Tiempo total (s) error % steinb1 41 41 4,072 0,000 steinb2 58 58 4,558 0,000 steinb3 62 62 4,317 0,000 steinb4 59 62 7,776 5,085 steinb5 56 57 7,655 1,786 steinb6 116 123 8,189 6,034 steinb7 74 74 5,226 0,000 steinb8 75 75 5,610 0,000 steinb9 75 75 5,314 0,000 steinb10 71 81 11,336 14,085 steinb11 86 93 12,253 8,140 steinb12 152 168 11,426 10,526 steinb13 128 128 6,554 0,000 steinb14 153 153 7,017 0,000 steinb15 220 222 7,169 0,909 steinb16 117 144 16,536 23,077 steinb17 101 111 14,861 9,901 steinb18 182 191 16,051 4,945 Se muestra como el tiempo de implementación no supera los 20 segundos y como el error más alto es del 23%. Posteriormente se estudiará el porqué de este error tan alto en comparación con el resto de las soluciones. 97 Tabla 8. Resultados del algoritmo genético para los problemas de tipo c Problema OPTIMO genético Tiempo total (s) error % steinc1 60 101 35,159905 68,3333333 steinc2 137 189 30,628644 37,9562044 steinc3 549 626 41,314931 14,0255009 steinc4 731 787 43,792027 7,66073871 steinc5 960 991 48,52707 3,22916667 steinc6 55 365 243,413428 563,636364 steinc7 102 305 274,191038 199,019608 steinc8 459 617 259,40054 34,422658 steinc9 675 828 280,163543 22,6666667 steinc10 1009 1083 256,90041 7,33399405 Para las soluciones de la Tabla 8 se muestra como el tiempo de implementación aumenta respecto a los problemas de tipo “b”. Además, se puede observar como para el steinc6 se muestra un error muy elevado posiblemente debido al reducido número de nodos terminales. 6.2.2 Resolución del árbol mínimo de expansión (MST) En este apartado se trata la resolución de los problemas de Steiner a partir del árbol de mínima de expansión. La Tabla 9 muestra los resultados del MST para los problemas de tipo b. Si con el algoritmo genético 8 de los 18 problemas de tipo “b” se conseguían obtener sin error, con el MST exclusivamente 3 de los 18 problemas da con el óptimo. También se puede volver a comprobar que la resolución del problema steinb16 es el que mayor error presenta con un 35% de error. Lo que supone un 10% de incremento respecto al error con el algoritmo genético. A pesar de ello, los tiempos de resolución del MST están muy por debajo de los del algoritmo genético. Otro punto a destacar es que el error obtenido con la resolución del algoritmo genético es como mucho igual al error de la resolución por MST. 104 Al resultar el tiempo de resolución del MST de milésimas para cualquiera de los problemas analizados, no merece la pena realizar un gráfico que relacione el tiempo de ejecución con los problemas de Steiner analizados. Para tener en cuenta la correlación del número de nodos, el número de arcos con el error y el tiempo de ejecución, se exponen a continuación las siguientes gráficas. En la Gráfica 14 se muestra la relación del porcentaje de error con el número de nodos que se encuentran a lo largo de los problemas tipo “b” y “c”. Como se puede ver, a medida que aumenta el número de nodos en los problemas, mayor porcentaje de error de media se obtiene por la resolución del algoritmo genético. Se muestra como el aumento no es lineal, debido a que el error no solo depende del número de nodos sino también de la densidad de los nodos terminales y del número de arcos. El pico que sobresale de la gráfica se debe al error del problema steinc6. Gráfica 14. Porcentaje de error frente el número de nodos en la resolución de algoritmos genéticos En la Gráfica 15, se aprecia el porcentaje de error en relación con el número de nodos, pero resolviendo ahora los problemas con el MST. Se puede ver el gran parentesco de la Gráfica 14 con la Gráfica 15 para los problemas con nodos mayores de 500 que pertenecen al tipo “c”. Esto es así ya que como se vio en la Gráfica 11, el porcentaje de error entre las soluciones con MST y algoritmo genético es muy parecido para los problemas de tipo “c”. Gráfica 15. Porcentaje de error frente el número de nodos en la resolución del MST 0 100 200 300 400 50 50 50 75 75 75 100 100 100 500 500 500 500 500 Porcentaje de error Nº de nodos Relación error con número de nodos AG 0 100 200 300 400 50 50 50 75 75 75 100 100 100 500 500 500 500 500 Porcentaje de error Nº de nodos Relación error con número de nodos MST 105 Se pasa ahora a analizar el tiempo de ejecución respecto del número de nodos. En la Gráfica 16 se expone la relación del tiempo de ejecución respecto al número de nodos resueltos los problemas con algoritmos genéticos. Se vuelve a apreciar, como es lógico, que a mayor número de nodos mayor tiempo de ejecución. Podemos relacionar también que a mayor número de nodos mayor dificultad tiene el problema. Pues más avanzado dentro de la colección de problemas se estará. El cambio brusco de pendiente se debe a la gran diferencia entre el número de nodos y de arcos. Gráfica 16. Relación del tiempo de ejecución respecto al número de nodos resuelto con algoritmo genético En la Gráfica 17 se visualiza el tiempo de ejecución frente al número de nodos de problemas resueltos con el MST. Se observa como el tiempo de ejecución aumenta con el número de nodos. Hay que tener en cuenta que aquí el tiempo se contabiliza en segundos, luego se muestra de nuevo el tiempo de ejecución tan reducido que precisa el algoritmo MST. Gráfica 17. Relación del tiempo de ejecución respecto al número de nodos resuelto con MST 0 1 2 3 4 5 50 50 50 75 75 75 100 100 100 500 500 500 500 500 Tiempo en minutos Nº de nodos Relación tiempo con número de nodos AG 0 0,005 0,01 0,015 0,02 50 50 50 75 75 75 100 100 100 500 500 500 500 500 Tiempo en segundos Nº de nodos Relación tiempo con número de nodos MST 106 La relación del número de arcos con el porcentaje de error, así como, con el tiempo de ejecución también son fruto de observación en este estudio. Como se puede visualizar en la Gráfica 18, el número de arcos también afecta de forma similar que el número de nodos al error. Gráfica 18. Relación del error con el número de arcos en problemas resueltos con el AG En la Gráfica 19 se muestra la relación del error con el número de arcos para la resolución por MST. Se aprecia como el error es mayor debido a que este algoritmo es mucho menos preciso que el algoritmo genético. Gráfica 19. Relación del error con el número de arcos en problemas resueltos con el MST 0,000 100,000 200,000 300,000 400,000 500,000 600,000 63 63 94 100 100 125 150 150 200 625 625 625 1000 1000 Porcentaje de error Nº de arcos Relación error con número de arcos AG 0 100 200 300 400 500 600 700 63 63 94 100 100 125 150 150 200 625 625 625 1000 1000 Porcentaje de error Nº de arcos Relación error con número de arcos MST 107 En la Gráfica 20 se representa el tiempo de ejecución en función del número de arcos para soluciones con AG. Se muestra gran similitud con la Gráfica 16 que expone el tiempo de ejecución del AG en función del número de nodos. Se puede ver el gran salto de la pendiente cuando se pasa de 625 arcos a 1000. Gráfica 20. Tiempo de ejecución en función del número de arcos para soluciones con AG Del mismo modo, la Gráfica 21 visualiza el tiempo de ejecución frente el número de arcos para problemas resueltos por el MST. Se puede observar como el tiempo de ejecución está en segundos y la gráfica en sí tiene mucho parecido con la Gráfica 17 donde se representa el tiempo de ejecución con el número de nodos para problemas resueltos con el MST. Gráfica 21. Tiempo de ejecución en función del número de arcos para soluciones con MST 0,000 50,000 100,000 150,000 200,000 250,000 300,000 63 63 94 100 100 125 150 150 200 625 625 625 1000 1000 Tiempo en segundos Nº de arcos Relación tiempo con número de arcos AG 0 0,002 0,004 0,006 0,008 0,01 0,012 0,014 0,016 0,018 63 63 94 100 100 125 150 150 200 625 625 625 1000 1000 Tiempo en segundos Nº de arcos Relación tiempo con número de arcos MST 108 Para acabar con el análisis que relaciona el error y el tiempo de ejecución con el número de nodos y el número de arcos, se presenta a continuación la densidad de nodos terminales (nodos totales entre nodos terminales) en función del error y el tiempo de resolución. La Gráfica 22 deja ver como a mayor densidad de nodos terminales, menor error relativo respecto al óptimo se obtiene. Esto es debido a que cuantos menos nodos Steiner existan en el problema, menos soluciones admisibles habrá. Ya que no existirán tantos posibles caminos para comunicar unos nodos con otros y esto resultará en un error en la solución más pequeño. Es decir, el espacio de soluciones se reduce y la exploración del óptimo tendrá un mayor efecto. Gráfica 22. Densidad de los nodos terminales en función del porcentaje de error En la Gráfica 23 se visualiza el tiempo de ejecución respecto de la densidad de nodos terminales. Aquí se puede ver como el tiempo de ejecución tiende a tener una probabilidad alta de disminuir a medida que la densidad de nodos terminales aumenta justamente por la explicación de que, a mayor número de nodos terminales, menos soluciones posibles. Gráfica 23. Densidad de los nodos terminales en función del tiempo de resolución 0 100 200 300 400 500 600 Porcentaje de error Densidad de nodos terminales Densidad de nodos terminales frente al error 0 200 400 600 800 1000 1200 Tiempo en segundos Densidad de nodos terminales Densidad de nodos terminales frente al tiempo de resolución 109 6.4 Curvas de superficie Para finalizar, en este apartado se van a analizar algunas soluciones que han despertado gran interés por sus resultados. Se van a exponer una serie de gráficas tridimensionales realizadas en base a 176 soluciones de cada uno de los problemas representados en ellas. Las soluciones cambian formándose una curva de superficie en función del número de individuos que tenga la población y en función del número de iteraciones. Particularmente, se han obtenido resultados para poblaciones entre 50 y 100 individuos y para iteraciones entre 500 y 2000. Cada una de las curvas de superficie tiene un tiempo de ejecución de media de día y medio. Pues, realizar 176 soluciones incrementando el número de iteraciones tiene un tiempo computacional muy costoso. Para comprender las figuras, se pasa a explicar la estructura de las mismas. En el eje Z se sitúan los costes de las soluciones, es decir, cuanta menos altura tenga la figura, mejor coste se habrá obtenido para una solución en particular. En el eje de coordenadas se muestra el rango de iteraciones que comprende desde 500 hasta 2000 iteraciones. Por otro lado, el eje de abscisas contiene el número de individuos de cada una de las 30 poblaciones con las que se halla cada solución. El eje X va de 50 individuos a 100. Se dará comienzo con la gráfica de steinb4 pues para los problemas anteriores a este, debido a su sencillez, no se encuentran soluciones diferentes. En la Figura 68 se puede ver como el rango de soluciones oscila entre 59 (óptimo) y 63. El mayor número de soluciones óptimas se sitúa en la zona rodeada. Se podría decir que el problema 4b presenta mayor probabilidad para obtener el óptimo cuando la población es de 80 y se ejecutan alrededor de 1500 iteraciones. Figura 68. Curva de superficie para steinb4 110 En la Figura 69 se puede ver desde una vista desde arriba el plano de soluciones. Representando los cuadrados más oscuros las soluciones óptimas. En la Figura 70 se ve como se muestra la curva de superficie para steinb6. Se puede ver que para este caso el rango de soluciones oscila desde 116 a 124. Por otro lado, se puede apreciar la dificultad de obtener el óptimo en este problema, pues casi para todas las soluciones del gráfico se obtiene 118 unidades de coste en vez de 116. Figura 69. Curva vista desde arriba para steinb4 Figura 70. Curva de superficie de steinb6 111 En la Figura 71 se muestra la curva de superficie para steinb12. Se visualiza como para iteraciones en torno a 500 se obtienen soluciones muy por encima del óptimo. El mayor valor es de 168 y el menor de 152. Este valor es el óptimo, el cual solamente es alcanzado una vez con una población de 50 y 700 iteraciones. El rango de variación de las soluciones es de 16 unidades de coste que equivale a un error de 10.526% respecto del óptimo. Para el problema steinb16 visualizado en la Figura 72, no se encuentra la solución óptima de 117 unidades de coste, sino que el mínimo es 128 encontrándose solo en 5 de las 176 soluciones. Por otro lado, la máxima solución es de 150 unidades de coste alcanzando un error de 28.205% sobre el óptimo. Además, justamente el punto donde más error hay respecto de la solución, es el de 500 iteraciones y 100 individuos. Este punto se empleó en la Tabla 7 para dar solución al problema steinb16, solo que en la gráfica da 148 unidades y en la tabla 144. Por todo ello, se puede considerar el problema más complejo de la colección de tipo “b”, pues en ninguna de las 176 soluciones mostradas en la Figura 72 se da con el óptimo. Esto es debido a que steinb16 es el problema de tipo “b” con mayor diferencia entre el número de arcos y el número de nodos que contiene mayor número de nodos respecto al resto de soluciones de tipo “b”. Sumado a que, a pesar de su tamaño, la densidad de nodos terminales es muy baja, lo que permite la mayor posibilidad de soluciones posibles y la dificultad de dar con el óptimo. Las gráficas steinb6, steinb12 y steinb16 comparten una forma muy similar. Figura 71. Curva de superficie de steinb12 112 Figura 72. Curva de superficie de steinb16 A continuación, se muestran algunas gráficas de los problemas de Steiner de tipo “c”. La gráfica de steinc1 muestra que el mínimo obtenido es de 89 (hallado solo una vez) y el máximo de 105 siendo el óptimo de 60 unidades de costes. Esto permite entender por qué el problema steinc1 presenta un error tan elevado para la implementación de 100 individuos y 500 iteraciones. Y es que para ninguna de las soluciones presentes en la Figura 73 se consigue llegar al óptimo. Figura 73. Curva de superficie de steinc1 113 Para la Figura 74 se observa el problema de steinc4 donde se puede ver cómo al aumentar el número de iteraciones, rápidamente disminuye las unidades del coste. Para esta gráfica el mínimo es de 736, que se obtiene dos veces como se muestra en la gráfica, y el máximo de 787. Debido a que el óptimo es de 731 unidades de coste, este nunca se llega a alcanzar, aunque el mínimo se aproxima mucho a él. En la Figura 75 se muestra con precisión cómo disminuye el número de soluciones a medida que se incrementa el número de iteraciones. Figura 74. Curva de superficie para steinc4 Figura 75. Curva vista desde arriba para steinc4 120 - Research gate. El uso de redes complejas en economía: alcances y perspectivas. (2017). https://www.researchgate.net/figure/Figura-1-Los-puentes-de- Koenigsberg_fig1_320638009 - Rubem P. Mondaini (2007). Steiner Ratio of Biomolecular Structures - Seong Eun et. al. (2015). Structural Changes in the Minimal Spanning Tree and the Hierarchical Network in the Korean Stock Market around the Global Financial Crisis - Tuttle, R. H. (1989). Arguments on evolution. A paleontologist’s perspective. American Journal of Physical Anthropology, 80(3):405-406. - Uchoa, E., Poggi de Aragão, M., Ribeiro, C.: Preprocessing Steiner problems from VLSI layout. Networks 40, 38–50 (2002) - Vahdati Daneshmand, S.: Algorithmic approaches to the Steiner problem in networks. PhD thesis, Universität Mannheim (2004) - Wong, R.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28, 271–287 (1984) - Xiuzhen Cheng and Ding-Zhu Du (2001). Steiner Trees in Industry. Países Bajos (Volumen 11, Steiner Tree Based Distributed Multicast Routing in Networks) - Xiuzhen Cheng and Ding-Zhu Du (2001). Steiner Trees in Industry. Países Bajos (Volumen 11, Steiner Trees in Uniform Orientation Metrics) - Xiuzhen Cheng and Ding-Zhu Du (2001). Steiner Trees in Industry. Países Bajos (Volumen 11, The perfect Phylogeny Problem) - Xiuzhen Cheng and Ding-Zhu Du, 2001. Combinatorial Optimization. Steiner Trees in Industry, Volume 11 (Foreword, pp. vii-xi and pp. 30) - Yang, Y.Y., Wing, O.: On a multinet wiring problem. IEEE Trans. Circuit Theory 20(3), 250– 252 (1973) 121 ANEXOS 9.1 Funciones de MATLAB 9.1.1 Función orden function nuevostein=orden(stein,numarist) nuevostein=[zeros(numarist,1),zeros(numarist,1),sort(stein(1:numaris t,3))]; j=1; for i=1:numarist for k=1:numarist if stein(k,3)==nuevostein(i,3) nuevostein(j,1)=stein(k,1); nuevostein(j,2)=stein(k,2); stein(k,3)=0; j=j+1; end end end end 9.1.2 Función steiner function [nsteiner]=steiner(terminales, numvert) numterm=length(terminales); nsteiner=zeros(1,numvert-numterm); nodostn=1:numvert; for i=1:numvert for j=1:numterm if i==terminales(j) nodostn(i)=0; end end end j=1; for i=1:numvert if nodostn(i)~=0 nsteiner(j)=nodostn(i); j=j+1; end end end 9.1.3 Función steinerorden function [nsteinerord]=steinerorden(nsteiner,stein,numarist,solorden) 122 cont=zeros(1,length(nsteiner)); nsteinerord=cont; for j=1:length(nsteiner) for i=1:numarist if stein(i,1)==nsteiner(j)|| stein(i,2)==nsteiner(j) if solorden(i)==1 cont(j)=cont(j)+1; end end end end j=1; for k=1:max(cont) for i=1:length(nsteiner) if cont(i)==k nsteinerord(j)=nsteiner(i); j=j+1; end end end end 9.1.4 Función solucionado function solorden=solucionado(numarist,numvert,stein,terminales) nuevostein=orden(stein, numarist); nodopad=[1:numvert ; 1:numvert]; sol=1:numarist; for i=1:numarist for j=1:numvert if nuevostein(i,1)==nodopad(1,j) m=j; end if nuevostein(i,2)==nodopad(1,j) n=j; end end if nodopad(2,m)==nodopad(2,n) sol(i)=0; else if nodopad(1,m)==nodopad(2,m) nodopad(2,m)=nodopad(2,n); sol(i)=1; for o=1:numvert if nodopad(2,o)==nodopad(1,m) nodopad(2,o)=nodopad(2,m); end end else if nodopad(1,m)~=nodopad(2,m) nodopad(2,nodopad(2,m))=nodopad(2,n); 123 p=nodopad(2,m); for l=1:numvert if nodopad(2,l)==p nodopad(2,l)=nodopad(2,nodopad(2,n)); end end sol(i)=1; end end end end // De aquí hacia abajo implementamos la parte de quitar las aristas activas que se unen a nodos Steiner, los cuales se pueden podar. nsteiner=steiner(terminales, numvert); numsteiner=length(nsteiner); nsteinerord=steinerorden(nsteiner, nuevostein, numarist, sol); cont=zeros(1,numsteiner); for j=1:numsteiner for i=1:numarist if nuevostein(i,1)==nsteinerord(j)|| nuevostein(i,2)==nsteinerord(j) if sol(i)==1 cont(j)=cont(j)+1; num=i; end end end if cont(j)==1 sol(num)=0; end end // Creamos la solución ordenada según stein y no según costes de menor a mayor. solorden=zeros(1,numarist); for i=1:numarist for j=1:numarist if stein(i,1)==nuevostein(j,1) && stein(i,2)==nuevostein(j,2) solorden(i)=sol(j); end end end end 9.1.5 Función costealeatorio function steincost=costealeatorio(stein, numarist) for i=1:numarist 124 stein(i,3)=floor(rand*100); end steincost=stein; end 9.1.6 Función definitivo function [matrizsol,costesol]=definitivo(numvert,numarist,stein,terminales,N) matrizsol=zeros(N,numarist); costesol=zeros(numarist,N); vectorsol=solucionado(numarist,numvert,stein,terminales); matrizsol(1,:)=vectorsol(:); costesol(:,1)=stein(:,3); for i=2:N steincost=costealeatorio(stein,numarist); costesol(:,i)=steincost(:,3); vectorsol=solucionado(numarist,numvert,steincost,terminales); matrizsol(i,:)=vectorsol(:); end end 9.1.7 Función crossing function hijo=crossing(padre,madre,stein,numvert,terminales) numarist=length(padre); hijo=zeros(1,numarist); steincruce=[stein(:,1:2),16*ones(numarist,1)]; for i=1:numarist if padre(i)==madre(i)&& padre(i)==0 hijo(i)=0; else hijo(i)=1; steincruce(i,3)=1; end if padre(i)~=madre(i) hijo(i)=1; steincruce(i,3)=round(14*rand()+1); end end //Hasta aquí hemos creado la matriz steincruce formada por la superposición de los padres. Los costes más bajos(coste=1) son las aristas que hay que coger para formar la admisibilidad. hijo=solucionado(length(padre),numvert,steincruce,terminales); end 125 9.1.8 Función mutacion function matrizsol=mutacion(matrizsol,elegido,stein,numvert,nterminales) numarist=size(matrizsol,2); flat1=0; mutado=zeros(1,numarist); mutado(1,:)=matrizsol(elegido,:); while flat1==0 aleatorio=round((numarist-1)*rand()+1); if matrizsol(elegido,aleatorio)==1 flat1=1; end end steinmutado=zeros(numarist,3); steinmutado(1:numarist,1:2)=stein(1:numarist,1:2); //Con este bucle conseguimos pasar a una matriz steinmutado la solución mutada pero de forma que los arcos que haya que seleccionar valgan 1 y el resto aleatorio. Para que generemos una solución mutada sin bucles dentro del árbol. for i=1:numarist if mutado(1,i)==1 steinmutado(i,3)=1; else steinmutado(i,3)=round(14*rand()+1); end end //Le pongo valor infinito al arco que he mutado para que no se coja y poder generar una solución. steinmutado(aleatorio,3)=inf; matrizsol(elegido,:)=solucionado(numarist,numvert,steinmutado,ntermi nales); end 9.1.9 Función selección function elegido=seleccion(matrizsol,stein,bandera,q) %generamos la matriz fitness que contiene en la primera columna números del %1 a N y en la segunda los correspondientes fitness según el orden de las %soluciones de la matrizsol N=size(matrizsol,1); fitness=[(1:N)',(matrizsol(:,:)*stein(:,3))]; %ordenamos fitness fitnessordenado=[zeros(N,1),sort(fitness(:,2))]; for i=1:N for j=1:N if fitness(j,2)==fitnessordenado(i,2) 126 fitnessordenado(i,1)=fitness(j,1); end end end if bandera==0 elegido=round((N-1)*rand()+1); else %como obtener las diferentes probabilidades ordenadas según la matriz %fitnessordenado, es decir, de menor coste (mayor fitness) a mayor coste %(menor fitness) probabilidad=zeros(N,1); %RULETA de seleccion if bandera==1 sumfitness=0; for i=1:N sumfitness=sumfitness+1/fitness(i,2); end for i=1:N probabilidad(i)=1/fitnessordenado(i,2)/sumfitness; end end %RANKING de selección if bandera==2||bandera==4 probabilidad(1)=q; for i=1:N-1 probabilidad(i+1)=q*(1-q)^i; end probabilidad(1)=q+(1-sum(probabilidad)); end %RANKING de reemplazo if bandera==4 probabilidad=sort(probabilidad); end %RULETA de reemplazo if bandera==3 sumfitness=0; for i=1:N sumfitness=sumfitness+fitness(i,2); end for i=1:N probabilidad(i)=fitnessordenado(i,2)/sumfitness; end end %%esto se puede hacer con ruleta ranking e hipergeométrica rango=zeros(N,2); cont=0; for i=2:N cont=cont+probabilidad(i-1); rango(i,1)=cont; rango(i-1,2)=rango(i,1); end rango(N,2)=1; 127 aleatorio=rand(); for i=1:N if aleatorio>=rango(i,1)&& aleatorio<rango(i,2) elegido=fitnessordenado(i,1); end end end end 9.1.10 Función genetico1 function [solucionfinal,coste,poblacion]=genetico1(numvert,numarist,stein,ter minales,N,q,iteraciones) tic matrizsol=definitivo(numvert,numarist,stein,terminales,N); fitnessiter=zeros(1,iteraciones); poblacion=struct('fitness',[],'minimo',[],'solucion',[]); %cont=0; for i=1:iteraciones eleccion=rand(); if eleccion>=0&&eleccion<0.15 elegido=seleccion(matrizsol,stein,0,q); matrizsol=mutacion(matrizsol,elegido,stein,numvert,terminales); end if eleccion>=0.15 elegido1=seleccion(matrizsol,stein,1,q); elegido2=seleccion(matrizsol,stein,1,q); [padre,madre]=prevencion(matrizsol(elegido1,:),matrizsol(elegido2,:) ,matrizsol); hijo=crossing(padre,madre,stein,numvert,terminales); elegido3=seleccion(matrizsol,stein,4,q); matrizsol(elegido3,:)=hijo(:); end fitness=[(1:N)',(matrizsol(:,:)*stein(:,3))]; %fitness de cada muestra de la poblacion1 en cada una de las iteraciones fitnessiter(i)=min(fitness(:,2)); %acumula el mínimo fitness de cada iteración %cont=cont+1 end for j=1:N if fitness(j,2)==fitnessiter(iteraciones) posicion=j; end end ultimasolucion=matrizsol(posicion,:); minpoblacion=zeros(30,1); minpoblacion(1)=min(fitnessiter); poblacion(1).fitness=fitnessiter; poblacion(1).minimo=minpoblacion(1); poblacion(1).solucion=ultimasolucion; 128 for j=1:29 matrizsol=definitivo(numvert,numarist,stein,terminales,N); steincost=costealeatorio(stein,numarist); matrizsol(1,:)=solucionado(numarist,numvert,steincost,terminales); for i=1:iteraciones eleccion=rand(); if eleccion>=0&&eleccion<0.15 elegido=seleccion(matrizsol,stein,0,q); matrizsol=mutacion(matrizsol,elegido,stein,numvert,terminales); end if eleccion>=0.15 elegido1=seleccion(matrizsol,stein,1,q); elegido2=seleccion(matrizsol,stein,1,q); [padre,madre]=prevencion(matrizsol(elegido1,:),matrizsol(elegido2,:) ,matrizsol); hijo=crossing(padre,madre,stein,numvert,terminales); elegido3=seleccion(matrizsol,stein,4,q); matrizsol(elegido3,:)=hijo(:); end fitness=[(1:N)',(matrizsol(:,:)*stein(:,3))]; %fitness de cada muestra de la poblacion1 en cada una de las iteraciones fitnessiter(i)=min(fitness(:,2)); %acumula el mínimo fitness de cada iteración end for k=1:N if fitness(j,2)==fitnessiter(iteraciones) posicion=k; end end ultimasolucion=matrizsol(posicion,:); minpoblacion(j+1)=min(fitnessiter); poblacion(j+1).fitness=fitnessiter; poblacion(j+1).minimo=minpoblacion(j+1); poblacion(j+1).solucion=ultimasolucion; end coste=min(minpoblacion); for j=1:30 if minpoblacion(j,1)==coste posicion=j; end end solucionfinal=poblacion(posicion).solucion; toc end