Algoritmo Evolutivo para el Problema de Árbol de Mínima Expansión (MST) Campos Y., Rahn A. (yelitzayoleth@mipunto.com, yo@alfredorahn.com) Resumen – El problema del árbol de mínima expansión es un problema común de optimización combinatoria. Fue formulado inicialmente por Boruvka en 1926. La formulación del MST ha sido aplicada para hallar soluciones en diversas áreas (transporte, diseño de redes de telecomunicaciones, sistemas distribuidos y otros. Se han desarrollado algoritmos de tiempo polinomial para su resolución (Prim, Kruskal, Dijktra y Sollin). Debido a su complejidad y su explosión combinatoria se pueden emplear algoritmos evolutivos que mejoren la relación (calidad/tiempo) de la solución. Como estrategia se hace uso de optimización restringida aplicando una función penalty a los cromosomas infactibles; esta penalización es dinámica, debido a que aumenta por el número de restricciones violadas. Este método hace que la convergencia a la solución sea mucho más eficiente (calidad/tiempo). Palabras Claves – Algoritmos Evolutivos, MST, Optimización restringida, penalización. I. Introducción El MST tiene una historia venerable en la optimización combinatoria. Fue formulado inicialmente por Boruvka en 1926 quien se dice tuvo que aprender de éste durante la electrificación del sur de Moraria donde el proporcionó una solución para hallar la distribución más económica a través de una red de una línea de energía. Desde entonces la formulación del MST ha sido aplicada en numerosos problemas combinatorios tales como: problemas de transporte, diseño de redes de telecomunicaciones, sistemas distribuidos y otros. Al mismo tiempo algunos algoritmos de tiempo polinomial fueron desarrollados para su resolución por Prim, Kruskal, Dijkstra y Sollin. Los problemas que son extensiones del MST son generalmente problemas NP-Hard para los cuales no existen algoritmos de orden polinomial que los resuelvan. Debido a su complejidad se han venido empleando Algoritmos Evolutivos para su solución. Desde varias décadas atrás, se han tratado de encontrar algoritmos eficientes para el problema del Árbol de Expansión Mínima Capacitado -AEMC- conocido también como Capacitated Minimum Spanning Tree, cuya finalidad es encontrar un árbol de expansión mínima que no viole ciertas restricciones de capacidad definidas. El problema del AEMC cae dentro del dominio de los problemas de optimización, en los cuales se trata de encontrar la mejor de varias soluciones posibles -punto óptimo- dentro del espacio de búsqueda, siendo necesario conocer como medir y saber cuando una solución es buena o mala. Este problema es importante en dos aspectos, por el lado teórico, el AEMC pertenece al conjunto de problemas definidos como NP-Completos [5], por lo que dado su complejidad es importante encontrar técnicas estocásticas que encuentren soluciones aceptables en tiempos adecuados, ya que las técnicas determinísticas tienen un comportamiento exponencial y en las técnicas heurísticas conocidas se degrada la calidad de la solución conforme crece el tamaño del problema. Por el lado práctico, problemas como encontrar la configuración óptima de redes de cómputo, redes de carreteras, o en general problemas de flujo son equivalentes al problema del AEMC [5]. En el diseño de redes donde se tienen un conjunto de terminales - nodos- y otras fuentes de datos diseminadas sobre un área geográfica, con alguna medida de tráfico esperado entre varias fuentes, surgen preguntas como: ¿Cuántos concentradores se necesitan? ¿Cómo deber ser conectados? ¿Dónde deben ser colocados?, i.e. que terminales deben ser conectadas a un concentrador en particular (clustering problem). A un nivel más bajo, la pregunta de cómo las terminales asociadas con un concentrador en particular deben ser conectadas (terminal layout problem), puede ser respondida mediante el AEMC [5]. La promesa de calidad, eficiencia y robustez de los AG es una idea que atrae a mucha personas para trabajar con ellos, sobre todo porque los métodos tradicionales son buenos para ciertas clases de problemas específicos, pero cuando un problema no se adapta a tales métodos, encontrar la solución al problema puede ser frustrante. Las técnicas estocásticas, al recorrer el espacio de búsqueda del problema, deben de tener un balance adecuado entre las partes de exploración y explotación que se hace sobre el espacio de soluciones posibles. La exploración nos permite que el algoritmo se mueva sobre todo el espacio de soluciones, con lo que evitamos los mínimos locales. Por otro lado, la explotación nos permite, al encontrar una posible solución óptima, moverse en el espacio circundante a ésta para encontrar la que más se acerque el óptimo en dicho vecindario. De estas técnicas, los algoritmos genéticos cuentan con un muy buen balance entre la exploración y explotación, ya que aunque el AG esté cercano al punto de convergencia, el operador de cruza nos permite explorar individuos -posibles soluciones- con diferentes características. Por otra parte, el operador de mutación permite al AG una exploración sobre un área determinada del espacio de soluciones. Por varias razones, los AG son muy atractivos como herramientas para varias tareas de optimización. Primero, presentan una abstracción del material y los operadores genéticos tal y como se presenta en la naturaleza. Segundo, se cree que los AG, como procedimientos de búsqueda multi-punto, pueden encontrar soluciones mucho mejores en tiempos más cortos que los procedimientos clásicos de búsqueda de un punto. Tercero, dado que los AG trabajan al nivel de la codificación, es difícil de que obtengan resultados engañosos aún cuando la función puede ser muy difícil para los esquemas tradicionales. Y cuarto, se piensa que los AG entregan un alto rendimiento, dado que muestrean los esquemas en los cromosomas de una manera inherentemente paralela. II. Bases Teóricas Fundamentos de MST Considere un grafo conectado y no dirigido G = (V,E), donde V = (v1, v2, … vn ) es un conjunto finito de vértices (nodos) que pueden representar terminales o estaciones de telecomunicación etc. y E = eij en un conjunto finito de enlaces que representan la conexión entre los terminales o estaciones. Cada enlace tiene un número positivo real asociado denotado por W = wij representando distancia, costo, etc. Un árbol de expansión es un mínimo conjunto de enlaces de E que conectan todos los nodos en V y por lo tanto al menos un árbol de expansión puede ser encontrado en un grafo G. El mínimo árbol de expansión denotado por T* es un árbol de expansión cuyo peso total de todos los enlaces es mínimo. Es decir: donde T es un conjunto de árboles de expansión del grafo G. El grado de un nodo es el número de enlaces conectados a éste. Un nodo hoja tiene solamente un enlace conectado; de tal manera que el grado de un nodo hoja en un árbol en uno y el de los otros nodos más de uno. Luego para que un árbol de expansión sea mínimo debe cumplir una de tales condiciones: a) Ser un subgrafo de G conectado con n-1 enlaces b) Ser un subgrafo de G sin ciclos con n-1 enlaces. Y además debe cumplir que la sumatoria de los pesos de todos los arcos asociados al subgrafo de G es el menor de todos los subgrafos asociados al grafo G que cumplen con las mismas restricciones. Fundamentos de AG ¿Qué son los algoritmos genéticos? Son algoritmos de búsqueda basados en la mecánica de la selección natural y de la genética natural. Estos combinan la supervivencia de los individuos más aptos entre las cadenas de estructuras con un intercambio de información aleatorio para formar un algoritmo de búsqueda. Estructura de un AG El AG simple o básico comprende cinco pasos principales [5]: 1. Crear población inicial de cromosomas, ya sea en forma aleatoria o mediante cierto conocimiento inherente al problema en sí. Es muy importante que la población inicial tenga diversidad para que el algoritmo pueda explorar todo el espacio de soluciones, lo que se espera se cumpla dadas las características de la inicialización. Además, si se tiene conocimiento del problema, éste puede ser insertado en la población inicial, con lo que se espera conseguir un mejor tiempo de convergencia del algoritmo. 2. Evaluación, consiste en calcular la aptitud mediante una función definida para el problema en particular. El objetivo de esta función es proveer una medida numérica de la calidad de un cromosoma dado. 3. En el siguiente paso, selección o explotación, se escogen de forma aleatoria los cromosomas con mejor función de aptitud una o varias veces y se insertan en un depósito de cruza. 4. Enseguida se realiza una exploración, lo que consiste en la aplicación de operadores de recombinación y mutación, con lo que se obtienen dos hijos los que según el tipo de algoritmo usado, reemplazarán a sus padres en la siguiente generación. 5. La población es llenada con los nuevos cromosomas creados. Se repiten estos pasos hasta que el criterio de paro se cumpla, v.g. un número de generaciones determinado [5]. Convergencia del Algoritmo Dado que el algoritmo genético opera con una población en cada iteración, se espera que el método converja de modo que al final del proceso la población sea muy similar, y en el infinito se reduzca a un sólo individuo. Utilizar GAP generacional en la implementación del los algoritmos genéticos garantiza que no se perderán las mejores soluciones de cada generación y esto contribuye a que se preservaran los mejores individuos y estos podrán aportar su carga genética a futuras generaciones que deberían ir aumentando su aptitud, es decir, ir aproximándose mucho más rápido a la solución. Utilizar Función Penalty en la implementación del los algoritmos genéticos garantiza que se puede explorar en las regiones factible e infactibles, debido a que algunas regiones infactibles pueden proporcionar mayor información acerca de la solución óptima que otras soluciones factibles, se debe mantener un balance entre Preservación de la Información (manteniendo soluciones infactibles) y Presión Selectiva (rechazar algunas soluciones infactibles) [4]. Consideraciones al usar algoritmos genéticos Como cualquier otro algoritmo, el uso de un AG para resolver un problema a ciegas puede resultar desafiante, por lo que resulta de vital importancia usar el conocimiento del sistema a optimizar para determinar si el AG tendrá un desempeño adecuado. Es importante observar que aún para algunos tipos donde se sugiere que otras técnicas trabajarán mejor que los AG, con suficiente experimentos, se podrá obtener buen desempeño en la búsqueda usando AG. Por supuesto, tomar cualquier método de optimización para trabajar de una manera óptima requiere alguna experimentación con sus parámetros de configuración y selecciones inadecuadas de éstos conducirán a un bajo rendimiento en la búsqueda. Cuando no se conoce mucho acerca de la superficie de respuesta y calcular el gradiente es computacionalmente intensivo o numéricamente inestable muchas personas prefieren usar métodos de optimización como AG, SA y Simplex los cuales no requieren información del gradiente [5]. Por el contrario, para las aplicaciones donde el cálculo del vector gradiente es numéricamente preciso y rápido, no se recomienda usar los AG, ya que éstos alcanzarán la región óptima mucho más lento que los métodos hill-climbing. Otro tipo de aplicaciones no recomendadas para los AG son aquellas que requieren encontrar el óptimo global exacto, dada la característica de los AG de ser ∑ = E e ij t ij w T ε min * buenos encontrando la región óptima global pero enfrentando problemas algunas veces para localizar el óptimo exacto. Una de las dificultades más comúnmente mencionadas con los AG comparado con las técnicas hill-climbing es que generalmente los AG requieren más evaluaciones de la función de aptitud. Si la superficie de respuesta es bastante suave entonces un método hill-climbing, v.g. el método Simplex, superará al AG para un número de evaluaciones dado [5]. III. Problema Elaborar un programa utilizando algoritmos evolutivos para hallar una solución al problema MST que se presenta a continuación: Figura 1. Grafo pesado no dirigido. Especificaciones y requerimientos de la implementación: a) Representación genética: se habrá de emplear la denominada Codificación Enlace en donde se asocia un índice k con cada enlace es decir, E = { ek}, k= 1,2,…,k en donde k es el número de enlaces en un nodo. De tal manera que una cadena de bits puede representar una solución candidata indicando cuales enlaces son usados en un árbol de expansión como se ilustra en la figura 2. e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 0 1 0 1 1 0 1 0 1 0 0 1 Figura 2. Representación Genética de los individuos de la población. b) Cruce : Un punto. c) Mutación: realizar mutación como una perturbación aleatoria dentro del rango permisible de enteros entre 1 y n (n = números de nodos en un grafo dado). d) Selección: Rueda de la ruleta. e) Parámetros del algoritmo: GAP- Generacional 10% Tamaño Población 50 Probabilidad de Cruce 0,5 Probabilidad de Mutación 0,01 Generaciones 500 Números de Corridas 30 Tabla 1. f) Elaborar un gráfico en donde pueda apreciarse la Mejor Aptitud en cada corrida del algoritmo. El algoritmo implementado recibirá un grafo como el mostrado en la figura y determinará el árbol de mínima expansión sabiendo que los costos asociados son como se ilustra en la tabla 2. Nodo Enlaces 1 2 3 4 5 6 7 1 0 224 0 0 0 300 539 2 224 0 200 0 0 0 539 3 0 200 0 400 0 0 600 4 0 0 400 0 400 0 200 5 0 0 0 400 0 600 447 6 300 0 0 0 600 0 283 7 539 539 600 200 447 283 0 Tabla 2. En donde cero (0) indica sin conexión directa. En la figura 3. se muestra el resultado de colocar los pesos asociados a cada arco del Grafo de la figura 1. Figura 3. Grafo pesado no dirigido Debe ser implementado en C++. Debe ser construido en una forma que permita el proceso de cualquier grafo dado. Se deben presentar los resultados en el formato Paper suministrado. 6 5 7 4 3 2 1 539 300 224 283 600 200 539 600 200 400 447 400 6 5 7 4 3 2 1 e3 e2 e1 e12 e10 e4 e5 e7 e9 e6 e11 e8 IV. Implementación Para la implementación del AG se utilizó el lenguaje de programación C++ Builder. Se presenta una interfaz grafica donde están predeterminado los parámetros de entrada del algoritmo, estos pueden se cambiados a conveniencia. Para tener una referencia de la solución se realizó una corrida en frío del algoritmo de Dijkstra y se obtuvo la solución que se muestra en la figura 4. con su correspondiente representación genética en la figura 5. Figura 4. Solución al MST. Árbol de expansión mínimo. e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 E12 1 1 0 1 0 0 0 1 1 0 0 1 Figura 5. Representación Genética de la Solución La especificación de la estructura utilizada para almacenar los datos del Grafo se ilustra en la figura 6. Vi 1 1 1 2 2 3 3 4 4 5 5 6 Vj 2 6 7 3 7 4 7 5 7 6 7 7 Wi 224 300 539 200 539 400 600 400 200 600 447 283 Figura 6. Matriz que almacena el grafo. Vi,Vj son los vértices que componen el arco, Wi son los pesos. Detalles de la implementación: Función Objetivo: Siendo X un cromosoma de m bits y W el vector asociado a los pesos de los arcos del grafo. Función de Aptitud: Siendo F(x) el valor de la función objetivo para un cromosoma X y P(x) la penalización para ese cromosoma comprobando su factibilidad Función Penalty: Si el cromosoma es factible, es decir que cumple con una de las siguientes restricciones [4]: • Ser un subgrafo de G conectado con n-1 enlaces. • Ser un subgrafo de G sin ciclos con n-1 enlaces. Entonces P(x)=0, es decir no se penaliza. Si por el contrario el cromosoma es infactible: Entonces P(x) > 0, es decir se penaliza. Pero si el cromosoma al menos cumple con la restricción de tener n-1 enlaces se penaliza levemente sino se penaliza fuertemente El valor de P(x) viene dado por la suma promediada de los pesos del Grafo; la penalización se va aumentando a medida que el algoritmo se aproxima a la solución, es decir se penaliza más fuertemente a los individuos infactibles en las últimas generaciones. Los requerimientos de hardware son: • Un computador PC o compatible, 32MB de memoria, 10MB disponibles en disco duro, se recomienda una pantalla con resolución de 800 x 600 pixels. • Los requerimientos de Software son: • Microsoft windows 95 o superior V. Conclusión La implementación del GAP generacional evita que se pierdan las mejores soluciones (elitismo) esta es una ventaja que no posee los AG simples. La elección de utilizar la estrategia de Penalización para hallar una solución al problema MST a través de Algoritmos Evolutivos resulto muy eficiente en contraste con otras estrategias (rechazo, reparación y modificación de operadores genéticos) ya que estas resultan muy complejas de implementar o no ofrecen buenos resultados, en comparación con la estrategia de penalización que resulto fácil de implementar y se obtuvieron excelentes resultados. Los parámetros de entrada del algoritmo que están predeterminados en la aplicación son los apropiados para una ejecución eficiente del programa. En base a los resultados obtenidos podemos finalmente concluir que: • AG es un método robusto Al comprender los AG la implementación no es complicada. • Modelo elitista GAP generacional conserva un valioso material genético • AG y computación evolutiva pueden tener mucha aplicación 6 5 7 4 3 2 1 300 224 283 200 200 400 Solución: 1607 ∑= = m i i i w x x F 0 ) ( min ) ( ) ( 1 X P X F Eval + = • Utilizar Función Penalty en la implementación del los algoritmos genéticos garantiza que se puede explorar en las regiones factible e infactibles, debido a que algunas regiones infactibles pueden proporcionar mayor información acerca de la solución óptima que otras soluciones factibles, aunque se debe siempre mantener un balance entre Preservación de la Información (manteniendo soluciones infactibles) y Presión Selectiva (rechazar algunas soluciones infactibles) [4]. Los resultados del excelente desempeño del algoritmo se pueden observar en la Figura 7 y la Figura 8. VI. Referencias [1] http://www.cinefantastico.com/nexus7/ia/ageneticos.htm [2] http://www.uv.es/~rmarti/genet.html [3] http://www.geocities.com/jarosero_ag.htm [4] Diapositivas y material ofrecido por la Profesora de la electiva [5] Agustín García Romero. Un Algoritmo Genético para el Problema del Árbol de Expansión Mínima. Paper de Informática y Ciencias de la Computación. Gráfico de Resultados MST 1550 1600 1650 1700 1750 1800 1850 1900 1950 0 5 10 15 20 25 30 35 Número de Corridas Costo asociado al árbol Serie1 Gráfico de Resultados del MST 0 2 4 6 8 10 Tipos de Árboles Generados Frecuencia del árbol 1607 1654 1707 1724 1771 1830 1846 1854 1893 1907 Costo del Árbol Figura 7. Gráfico donde se puede apreciarse la Mejor Aptitud en cada corrida del algoritmo Figura 8. Gráfico de Frecuencia del conjunto de todos los árboles cuyos costos son iguales
