Arbol de expansion minima
Páginas: 6 (1450 palabras)
Publicado: 3 de noviembre de 2009
“UNIVERSIDAD NACIONAL DE SAN CRISTÓBAL DE HUAMANGA”
FACULTAD DE INGENIERÍA DE MINAS, GEOLOGÍA Y CIVIL
ESCUELA DE FORMACIÓN PROFESIONAL DE INGENIERÍA DE SISTEMAS
“ÁRBOL DE EXPANSIÓN MÍNIMA”
ASIGNATURA : Investigación de Operaciones II.
PRESENTACIÓN
El problema del árbol de mínima expansión es un problema común de optimización combinatoria. Fue formulado inicialmente por Boruvkaen 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).
ÁRBOL DE EXPANSIÓN MÍNIMA
1. HISTORIA:
El MST tiene unahistoria 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 talescomo: 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 sucomplejidad 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. Elproblema 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 comoNP-Completos, 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.
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 serconectados? ¿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. La promesa de calidad, eficiencia y robustez de los AG es una idea que...
FACULTAD DE INGENIERÍA DE MINAS, GEOLOGÍA Y CIVIL
ESCUELA DE FORMACIÓN PROFESIONAL DE INGENIERÍA DE SISTEMAS
“ÁRBOL DE EXPANSIÓN MÍNIMA”
ASIGNATURA : Investigación de Operaciones II.
PRESENTACIÓN
El problema del árbol de mínima expansión es un problema común de optimización combinatoria. Fue formulado inicialmente por Boruvkaen 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).
ÁRBOL DE EXPANSIÓN MÍNIMA
1. HISTORIA:
El MST tiene unahistoria 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 talescomo: 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 sucomplejidad 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. Elproblema 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 comoNP-Completos, 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.
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 serconectados? ¿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. La promesa de calidad, eficiencia y robustez de los AG es una idea que...
Leer documento completo
Regístrate para leer el documento completo.