Comparación de Modelos Basados en Técnicas de Aprendizaje (página 3)

Para el caso de HC, 451 datos que corresponden a la clase Y=1, estado operativo del sistema, fueron clasificados correctamente y 1 fue clasificado incorrectamente. Los 548 datos que corresponden a la clase  Y=0, estado fallado del sistema, fueron clasificados correctamente y ninguno fue clasificado incorrectamente.

Tabla 3.3 Matriz de confusión para datos de prueba – Caso conectividad

Medidas de sensibilidad, especificidad y precisión y número de reglas generadas

Utilizando los datos generados en la matriz de confusión  para los datos de entrenamiento (Tabla 3.2) y de prueba (Tabla 3.3) se obtienen las siguientes medidas:

* no excluyentes

Tabla 3.4 Medidas sensibilidad, especificidad y precisión – Caso conectividad

Función EAC generada por el AD

El algoritmo de AD produce reglas para ambos estados del sistema operativo y fallado. Las reglas generadas por AD son mutuamente excluyentes, así, la aproximación de la FES se consigue sumando cada una de las reglas que corresponden al estado operativo del sistema. Para la determinación de la EAC se aplica el siguiente procedimiento:

Supongamos la siguiente regla:

(Si X8=1 y X10=1 y X20=1 entonces Sistema =1) genera el siguiente término:

Regla = X8X10X20

Llevando el término a probabilidades se tiene:

E(X8 X10 X20) = E(X8) E(X10) E(X2)

Para el caso de X8

E(X8)= X8P + X8(1-P) = 1 P8 + 0 P8 = P8

Directamente podemos decir que:

P8P10P20

Por consiguiente se tiene:

      EAC = P8P10P20 + P3Q7P8P9P12Q15P19Q20P21 + Q7P8Q9P12Q15P19Q20P21 +

Q7P8Q12Q15P17P19Q20P21 + P8P10P13Q15Q19Q20P21 + P8Q10P11P12P13Q15Q19Q20P21 + P7P8Q10P11Q12P13Q15Q19Q20P21 + P8P12Q13P14Q15Q19Q20P21 + P7P8P19Q20Q21  + P1P2P4Q7P8P19Q20Q21  + Q1P2P4P6Q7P8P19Q20Q21  + P1P2P4P8P18Q19Q20Q21  + P1P2Q4P7P8P18Q19Q20Q21  + Q8P15P17P21 + P1P2P4P5Q8P13P15P16P17Q21  + P1P2P4Q8Q13P15P16P17Q21  + P1P2P4Q8P15Q16P17P19Q21  + P1P2P4Q8Q15P17P18 + P1P2P4P5Q8Q15P17Q18P19 + Q1P2P4P6Q8Q15P17P19 + Q1P2P4P6Q8Q15P17Q19P20 + P1P2P4Q8Q17P18 + P1P2P4P5Q8Q17Q18P19 + P1P2Q3P4Q5Q8Q17Q18P19 + Q1P2P4P6Q8Q17P19 + Q1P2P4P6Q8P9P11Q17Q19+   Q1P2P4P6Q8P9Q11P13Q17Q19  + P7P8Q15P19Q20P21 + P1P2P7P8Q9Q10Q12Q15Q19P20 + P2P4Q7P8P9Q10Q12P20Q21  + Q7P8Q10Q12P15Q16P17P20P21 + P7P8Q9Q10P12Q15Q19P20 + Q7P8Q10Q12P15P16P20P21 + P7P8Q9Q10P15Q19P20 + P7P8Q9Q10P19P20 + P7P8P9Q10P20 + Q7P8Q10P11P12P20 + P8P15P17Q20P21 +P8P15P16Q17Q20P21 + P8P14P15Q16Q17Q20P21 + Q7P8Q10Q11P12P14P20P21 + P7P8Q14P15Q16Q17P19Q20P21 + P5Q7P8Q10Q11P12Q14P20P21 + Q7P8P11Q14P15Q16Q17Q20P21

Función de estructura FES generada por el HC

La ejecución de HC genera las reglas de una sola clase:

Para el caso de Y=1, cada producto lógico corresponde a un camino mínimo. Es interesante hacer notar que las 16 reglas extraídas para el estado operativo del sistema, corresponden a caminos mínimos de la red.

Para Y=0,  estado fallado del sistema, el algoritmo genera reglas que pueden corresponder a cortes mínimos [32]. En este ejemplo se producen 49 reglas y 41 de ellas corresponden a cortes mínimos.

En ambos casos las reglas generadas por el algoritmo son no excluyentes.

Cada término de la aproximación de la FES(X) representa un camino mínimo desde el nodo origen al nodo destino, como es representada a continuación:

X15 X17 X21+ X7 X8 X19+ X8 X10 X20+ X8 X12 X14 X21+ X7 X8 X9 X20+

X8 X10 X13 X21 + X8 X15 X16 X21+ X8 X11 X12 X20+ X1 X2 X4 X18+

X2 X4 X6 X19+  X7 X8 X9 X13 X21+ X8 X11 X12 X13 X21+ X2 X4 X6 X9 X20+ X1 X2 X4 X5 X19+ X1 X2 X3 X7 X8 X18+ X2 X4 X6 X9 X13 X21

Para  obtener la EAC es necesario aplicar un procedimiento adicional que convierte estas expresiones lógicas a productos lógicos excluyentes, utilizando el algoritmo KDH88 [18] y de esta manera, de las 16 reglas no excluyentes extraídas por HC para Y=1, se obtiene 80 productos lógicos mutuamente excluyentes, correspondientes a 80 reglas.

Confiabilidad

Determinada las EAC por ambos algoritmos AD y HC, éstas se usan para evaluar la confiabilidad de la red para diferentes valores ri. La Tabla 3.5 muestra los resultados a partir de la EC y de la EAC, obtenidas por ambos algoritmos y los respectivos errores relativos.

Tabla 3.5 Confiabilidad de la red obtenida usando EC y EAC – Caso conectividad

2.5.2. Evaluación de capacidad

En el caso de evaluación de capacidad, la red se considera operativa si al menos 100 unidades de flujo pueden ser trasmitidas entre el nodo origen (s) y el nodo destino (t).

El sistema se evalúa considerando que la falla ocurre, cuando el flujo en el nodo destino es menor al requerido.

Al igual que el caso de evaluación de conectividad, la EC se obtuvo usando el software "APACRO" [37], un procedimiento de caminos compuestos y un algoritmo de flujo máximo y cortes mínimos [Anexo B]. En este caso, se producen 43 caminos válidos y la EC esta compuesta por  101 términos.

A través de una muestra aleatoria del espacio de estados, se obtuvo un conjunto de 7500 datos diferentes. Los primeros datos NT=5000, se usan para entrenar al algoritmo que clasifica (AD y HC) y los NE=2500 restantes para probar el modelo generado por ambos algoritmos.

2.5.2.1. Ejecución de los Algoritmos AD y HC para el caso de Evaluación de capacidad

Matriz de confusión para los datos de entrenamiento

La matriz de confusión Tabla 3.6, se obtiene a partir de los datos generados por ambos algoritmos, utilizando los 5000 datos de entrenamiento. 

En el caso del algoritmo de AD, 354 datos que corresponden a la clase Y=1, estado operativo del sistema, fueron clasificados correctamente y 8 fueron clasificados incorrectamente. Los 4628 datos que corresponden a la clase Y=0, estado fallado del sistema, fueron clasificados correctamente y  10 no.

Para el caso de HC, 362 datos que corresponden a la clase Y=1, estado operativo del sistema, fueron clasificados correctamente y ninguno fue clasificado incorrectamente. Los 4638 datos que corresponden a la clase  Y=0, estado fallado del sistema, fueron clasificados correctamente y ninguno fue clasificado incorrectamente.

Tabla 3.6 Matriz de confusión para datos de entrenamiento – Caso capacidad

Matriz de confusión para los datos de prueba

La matriz de confusión Tabla 3.7, se genera en ambos algoritmos, utilizando los 2500 datos de prueba. 

En el caso del algoritmo de AD, 152 datos que corresponden a la clase Y=1, estado operativo del sistema, fueron clasificados correctamente, 13 fueron clasificados incorrectamente, 2310 datos que corresponden a la clase Y=0, estado fallado del sistema fueron clasificados correctamente, 25 no.

Para el caso de HC, 160 datos que corresponden a la clase Y=1, estado operativo del sistema, fueron clasificados correctamente, 5 fueron clasificados incorrectamente, 2318 datos que corresponden a la clase  Y=0, estado fallado del sistema fueron clasificados correctamente y 17 fueron clasificados incorrectamente.

Tabla 3.7 Matriz de confusión para datos de prueba – Caso capacidad

Medidas de sensibilidad, especificidad y precisión y número de reglas generadas

Utilizando los datos generados en la matriz de confusión para los datos de entrenamiento (Tabla 3.6) y de prueba (Tabla 3.7), se obtienen las siguientes medidas:

* no excluyentes

Tabla 3.8 Medidas sensibilidad, especificidad y precisión – Caso capacidad

Función EAC generada por el AD

Para este experimento al igual que el anterior, el algoritmo de AD produce reglas para ambos estados del sistema operativo y fallado. Las reglas de AD en este caso también son excluyentes, por lo tanto la aproximación de la FES se determina directamente sumando cada una de las reglas que corresponden al estado operativo del sistema, y finalmente aplicando el mismo procedimiento explicado en el caso de conectividad se tiene:

     EAC  = P2 P4 P6 P8 P12 P19 P20 +P1 P2 P4 P6 Q8 P15 P17 Q18 P21 +

Q1 P2 P4 Q6 P8 P17 P19 P20 P21 +P1 P2 P4 Q8 P15 P17 P18 P21 +

Q1 P2 P4 Q6 P7 P8 Q9 P17 P19Q20 P21 +P1 P2 P4 P6 P8 P18 Q19 P20 +

P1 P2 P4 Q6 P8 P10 P18 Q19 P20 +P1 P2 P4 Q6 P8 P9 Q10 P12 P18 Q19 P20 +

P1 P2 P4 P8 P13 P18 Q19 Q20 P21 +P1 P2 P4 P8 Q13 P17 P18 Q19 Q20 P21 +

Q4 P7 P8 P15 P17 P19 Q20 P21 +Q1 P2 P4 P8 P9 P17 P18 Q19 P20 P21 +

Q1 P2 P4 P8 Q9 P13 P17 P18 Q19 P20 P21 +Q4 P7 P8 Q10 Q14 P15 P17 P20 P21 +

Q4 P7 P8 P9Q10P14 P15 P17 Q19 P20 P21+ Q4P7P8Q10 P14P15 P17P19 P20 P21+

P2 P4 P6 P8 P9 P13 Q18 Q19 P20 P21 + Q4 P8 P10 P15 P17 P20 P21 +

Q2 P4 P7 P8 P15 P17 P19 P21 +Q2 P4 P7 P8 P15P17 Q19 P20 P21 +

Q2 P4 Q7 P8 P10 P15 P17 P20 P21 + P1 P2 P4 P5 Q6 Q8 P15 P17 Q18 P19 P21 +

P1 P2 P4 Q5 Q6P7 P8 P15 Q18 P19 + Q2P4 Q7 P8 Q10 P11 P12 P15 P17 P20 P21 +

P2 P4P6 P8 Q10 P15 P19Q20 P21 + P1 P2 P4 P6 P7 P8 P18 P19 Q20 Q21 +

P2 P4 P6 P8 P10 P19 Q20 P21 + P1 P2 P4 Q6 P7 P8 P18 P19 +

P1 P2 P4Q6 Q7 P8 P18 P19 P20 +P1 P2 P4 Q6 Q7 P8 P18 P19 Q20 P21 +

Q1 P2 P4 P6 Q8 P15 P17 P19 P21 +P2 P4 P6 P8 Q10 Q12 P15 P19 P20 P21 +

P1 P2 P4 P5 Q6 P8 P9 Q 18 P19 + P1P2P4P5Q6P8Q9P17Q18 P19 +

P2P4P6P8Q10Q12 P19P20 +P1P2P4P5Q6P8Q9Q11 P14Q17 Q18 P19 +

P2 P4 P6 P7 P8 P10 Q15 P19Q20P21

Función de Estructura generada por el HC

El procedimiento de entrenamiento en HC caso capacidad, para el estado operativo del sistema, se producen 25 términos, de los cuales  21 corresponden a caminos mínimos, mientras el conjunto de reglas generadas para el estado del sistema fallado incluye 39 cortes mínimos.

Al igual que el caso de conectividad el algoritmo no genera las reglas de manera excluyente, la aproximación de la FES(X) se representa a continuación:

FES(X) = X7X8X15X17X19X21+X8X10X15X17X20X21+

X1X2X4X15X17X18X21+X2X4X6X8X10X19X20+

X8X11X12X15X17X20X21 + X1X2X4X8X13X18X21+

X1X2X4X8X10X18X20 + X7X8X9X15X17X20X21+

X2X4X6X15X17X19X21+X1X2X4X7X8X18X19+

X2X4X6X8X10X19X21+X2X4X6X8X9X12X20X21+

X2X4X6X8X11X13X18X21+X2X4X6X9X15X17X20X21+

X1X2X3X4X5X8X12X20+X1X2X4X7X8X9X18X20+

X1X2X4X5X8X16X19X21+X1X2X4X5X8X10X19X20+

X2X4X6X7X8X9X19X21+ X1X2X4X5X15X17X19X21+

X2X4X6X8X9X15X20X21

Está expresión se lleva a la forma mutuamente excluyente y se obtiene la EAC, para ello al igual que el caso anterior es necesario aplicar un procedimiento adicional y de esta manera, de las 25 reglas no excluyentes extraídas por HC para Y=1, se obtiene 69 lógicos correspondientes a 22 mutuamente excluyentes.

Confiabilidad

La siguiente tabla muestra la confiabilidad del sistema, evaluando la EC y la EAC obtenidas por ambos modelos, para distintos valores de ri.

Tabla 3.9 Confiabilidad de la red obtenida usando EC y EAC – Caso capacidad

2.6.       Análisis de resultados

Basándonos en los resultados obtenidos en ambos experimentos, se realiza una comparación entre AD y HC y se analizan ciertos aspectos según los siguientes criterios:

• La clasificación de los datos de entrenamiento y prueba.
• El número de reglas y tipos de reglas generadas.

La clasificación de los datos de entrenamiento y prueba

Para los datos de entrenamiento y prueba, se muestra en la Tabla 3.10 el porcentaje en que se equivoca el modelo generado por ambos algoritmos clasificando los datos.

ü       En el caso del algoritmo de AD, los datos de entrenamiento en ambos experimentos no alcanzan el 1% de error y para los datos de prueba, el máximo es el 2%.

ü       En el caso de HC, en los datos de entrenamiento, el modelo no se equivoca, siempre hace la clasificación de la manera correcta y para los datos de prueba, el máximo sólo llega al 0.25%.

Tabla 3.10 Porcentaje de datos mal clasificados

El número de reglas y tipos de reglas generadas

La siguiente tabla muestra el número de reglas generadas por los dos algoritmos comparados en ambos experimentos. Se observa que el AD genera mayor número de reglas que HC.

Tabla 3.11 Reglas generadas

CAPÍTULO 4

Conclusiones

Este trabajo de investigación se basó principalmente en la comparación de dos métodos de generación de reglas, para la obtención de la Expresión Aproximada de Confiabilidad (EAC) de una red. Para tal fin se utilizaron dos algoritmos fundamentados en el aprendizaje automatizado, denominados Árbol de Decisión (AD) y Hamming Clustering (HC).

Los resultados obtenidos en ambos casos fueron los siguientes:

En cuanto a las Reglas:

El AD extrae las reglas en forma excluyente, lo cual permite obtener directamente la aproximación de la FES, que corresponde a la suma de cada una de las reglas generadas por el algoritmo y posteriormente aplicando un procedimiento se obtiene la EAC.

El HC requiere que las reglas generadas sean convertidas a la forma excluyente para obtener la EAC.

De los resultados se puede concluir que para la obtención de la EAC, el método más directo es el AD, debido a que genera directamente reglas excluyentes. El método HC no genera reglas excluyentes, pero proporciona información interesante que puede ser utilizada para propósitos diferentes al de esta investigación en particular, como es el caso de la obtención de caminos mínimos y cortes mínimos de una red.

Datos de Entrenamiento y datos de Prueba:

En cuanto a la clasificación de los datos de entrenamiento y de prueba, ambos algoritmos presentaron muy buenos resultado, en donde AD fue superado por HC.

Con base en los resultados ya expuestos, se deduce que los dos métodos utilizados, tanto Árbol de Decisión (AD) como Hamming Clustering (HC), basados en el aprendizaje de máquinas, aportan resultados confiables para la construcción de una EAC a partir de una pequeña muestra de datos, observándose que las mejores aproximaciones se obtienen con HC, a pesar de que las reglas obtenidas con este método son no excluyentes.

Finalmente se recomienda el uso del algoritmo de "Hamming Clustering" para la obtención de los cortes mínimos de una red, variando el tamaño de muestra de los datos, ya que en el experimento presentado en esta investigación, para el caso de continuidad, con solo 3000 datos de entrenamiento y prueba, se obtuvieron 41 cortes mínimos y para el caso de capacidad a partir de 7500 datos, se obtuvieron 39 cortes mínimos

REFERENCIAS

[1] Joel A. Nachlas, FIABILIDAD. Ingeniería de Sistemas, Primera Edición: Noviembre – 1995. www.uoc.edu/in3/emath/docs/Fiab_1.pdf

[2] Claudio M. Rocco S, Marco Muselli, Empirical Models Based On Machine Learning Techniques for Determining Approximate Reliability Expressions, Reliability Engineering and System Safety, 2004, 83/3, pp 301-307.

[3] M.O. Ball (1986), Computational complexity of network reliability analysis, IEEE Transactions on Reliability., R-35 (3).

www.isr.umd.edu/People/faculty/Ball.html

[4] Jogesh K. Muppala, Ricardo M. Fricks, and Kishor S. Trivedi, Techniques for system dependability evaluation, Department of Computer Science. The Hong Kong University of Science and Technology.

http://shannon.ee.duke.edu/availabilitymodeling/papers.htm

[5] T. C. Hu, M. T. Shing, P. A. Tucker, Minimum Cuts in a Network, School of Engineering, UCSD, La Jolla, CA 92093, 20 Apr 2000.

http://citeseer.ist.psu.edu/168282.html

[6] K. K. Aggarwal, Y. C. Chopra, J. S. Bajwa, Capacity Consideration in Reliability Analysis of Communication Systems, IEEE Trans on Reliability, Vol. 31, No. 2, Jun. 1982

[7] S. Rai, S. Soh, A Computer Approach for Reliability Evaluation of Telecommunication Networks with Heterogeneous Link-Capacities, IEEE Trans on Reliability, Vol. 40, No. 4, Oct. 1991

[8] L. M. Goldschlager,  R. A. Shaw and J. Staples. The maximum flow problem for P. Computer Science 21, 105-111, 1982.

http://www.mpi-sb.mpg.de/cgi-bin/author?KKBGoldschlagerxxLMKKE+Goldschlager,-L.-M.

[9] Tongdan Jin & David W. Coit, Network reliability estimates using linear and Quadratic unreliability of minimal cuts.

http://www.rci.rutgers.edu/~coit/pubs.htm

[10] Vitaly G. Schetinin and Anatoly I. Brazhnikov, Diagnostic Rule Extraction Using Neural Networks, Penza State University,  2000. www.dcs.ex.ac.uk/people/vschetin/p3.pdf

[11] Mark Craven & Jude Shavlik, Rule extraction: Where we go from here?, University of Wisconsin Machine Learning Research Group Working Paper 99-1, 1999.

http://citeseer.ist.psu.edu/283343.html

[12] Peter Hamener & Yves Crama, Boolean function Theory, Algorithms, Applications, Chapter 1.

http://www.maths.lse.ac.uk/Personal/martin/cdambflearn.pdf

[13] Lawrence O. Hall, Nitesh Chawla and Kevin W. Bowyer,

Decision tree learning on very large data sets. Department of Computer Science and Engineering, ENB 118, University of South Florida.

http://seraphim.csee.usf.edu/~hall/smc98.pdf

[14] Chris Mayer, Rule Induction Using 1-R and Quinlan"s Tree to Rules Method, CSE 591 – Data Mining, 29 January 2002.

http://www.public.asu.edu/~huanliu/DM02/paper-present.html

[15] Zhi-Hua Zhou, Yuan Jiang and Shi-Fu Chen, Extracting Symbolic Rules from Trained, Neural Network Ensembles, National Laboratory for Novel Software, Technology, Nanjing University, Nanjing.

http://citeseer.ist.psu.edu/503264.html

[16] Tom M. Mitchell, Machine Learning, Carnegie Mellon University, Mc Graw Hill, 1997, Capítulo 3 Decision Tree Learning

[17] Erlendur S Porsteinsson, A Non-linear operators, 2000.

http://www.maximal-usa.com/xmps/html/node9.html

[18] K. D. Heidtmann: Smaller Sums of Disjoint Products by Subproducts Inversion, IEEE Trans on Reliability, Vol. 38, No. 4, Aug. 1989

[19] Nathalie Japkowicz, Supervised versus Unsupervised Binary-Learning, by Feedforward Neural Networks, , Faculty of Computer Science, DalTech/Dalhousie University.

http://citeseer.ist.psu.edu/311444.html

[20] J.M. Portela da Gama, Combining Classification Algorithms, PhD. Thesis, Faculdade de Ciências da Universidade do Porto, 1999.

http://citeseer.ist.psu.edu/246549.html

[21] Vladimir Estival Castro, A first introduction to the world of machine learning. The University of Newcastle, Australia, 2001.

http://www.cit.gu.edu.au/~s2130677/teaching/KDD.d/lect04-new.pdf

[22] Nils J. Nilsson, "Introduction to Machine Learning", Chapter 1, Robotics Laboratory, Department of Computer Science, Stanford University 1996.

http://robotics.stanford.edu/people/nilsson/mlbook.html

[23] Mark W. Craven ,Extracting comprehensible models from trained neural networks, Thesis, chapter 1, University of Wisconsin Madison 1996.

http://www.cs.wisc.edu/~shavlik/abstracts/craven.thesis.abstract.html

[24] Gregorio Hernández Peñalver, Complejidad y Grafos, Facultad de Informática UPM. 2000. http://www.dma.eui.upm.es/MatDis/Seminario2/ComplejGrafos.PDF

[25] M. Muselli, D. Liberati, Hamming Clustering: A New approach to Rule extraction, Genova, Italia

www.ieiit.cnr.it/~muselli/papers/soco99.pdf

[26] Paul Davidsson, Learning Characteristic Decision Trees, Department of Computer Science, Lund University, Box 118, S-221 00 Lund, Sweden http://citeseer.ist.psu.edu/9343.html

[27] Sreerama K. Murthy, Automatic Construction of Decision trees from Data: A Multi-Disciplinary Survey, Siemens Corporate Research, Princeton, NJ 08540, USA

http://www-courses.cs.uiuc.edu/~cs491han/papers/98murthy.pdf

[28] Luís Fernando Raínho, Alves Torgo, Inductive learning of tree-based regression models, Tesis de doctorado, Departamento de Ciencia de Computadores. Faculdade de Ciências da Universidade do Porto, Septiembre

http://citeseer.ist.psu.edu/505941.html

[29] J.R. Quinlan, Programs for machine learning, Morgan Kaufmann Publishers, 1993.

http://www.cse.unsw.edu.au/~quinlan/

[30] K. Mock, Lecture Notes on Machine Learning,

www.math.uaa.alaska.edu/ ~afkjm/

[31] Eduardo Morales, Inducción de Árboles de Decisión TDIDT, http://dns1.mor.itesm.mx/~emorales/Cursos/KDD/node27.html

[32] Jianxiu Hao , James B. Orlin, A faster algorithm for finding the minimum cut in a directed graph, Journal of Algorithms, v.17 n.3, p.424-446, Nov. 1994

www.informatik.uni-trier.de/~ley/db/journals/jal/jal17.html

[33] J. C. Cubero "Árboles de Decisión", 1998,

 http://elvex.ugr.es/etexts/spanish/proyecto/cap6.pdf

[34] Lic. Ana María Teresa Lucca , Elementos de lógica y matemática discreta www.ing.unp.edu.ar/asignaturas/elymd

[35] Machine Learning, http://www.cse.unsw.edu.au/~cs9416/ml/trees,

[36] M. Muselli, D. Liberati, Binary Rule Generation via Hamming Clustering, IEEE Transaction on Knowledge and Data Engineering, 2002, pp. 1258-1268

[37] M. Muselli, D. Liberati, Training digital circuits with Hamming Clustering, IEEE Transaction on circuit and Systems: Fundamental Theory and Applications, vol 47, pp. 513-527, 2000

[38] Oswin Aichholzer, 1996. Clustering the hypercube,

 http://www.igi.tugraz.at/oaich/publications.html

[39] Occam"s Razor, http://skepdic.com/occam.html

[40] Yoo Y. D., Deo N. "A comparison of algorithm for terminal -Pair reliability",  IEEE Transaction on reliability, Vol. 37, No. 2, June 1988.

[41] "APACRO" Software para análisis de confiabilidad en redes. DIOC Facultad de Ingeniería, UCV, Junio 2002.

[42] Exhaustive Search Methods

http://www.rci.rutgers.edu/~cfs/472_html/AI_SEARCH/ExhaustiveSearch.html

[43] The Ford-Fulkerson algorithm,

 http://www.isye.gatech.edu/~chayakritc/maximalflow.doc

Anexo A

Búsqueda profunda

Este tipo de búsqueda exhaustiva [42], se denomina búsqueda profunda ya que, previamente a considerar otro camino, el grafo es examinado a profundidad.

Cuando la búsqueda ha alcanzado el nivel mas bajo del grafo y no se ha llegado al nodo destino, entonces, se extiende la búsqueda a otras enlaces del grafo que inicialmente fueron ignoradas. Para realizar esto, se regresa al nivel anterior y se explora cualquier alternativa restante a este nivel, repitiendo este método sucesivamente. Este procedimiento de retroceso repetitivo garantiza que todas las posibilidades sean sistemáticamente y exhaustivamente examinadas.

La búsqueda profunda en un grafo se hace de arriba hacia abajo y de izquierda a derecha.

Primero se examina el nodo origen, luego el nodo izquierdo del nodo origen, posteriormente, el hijo izquierdo del nodo y así sucesivamente, cuando no hay opciones se regresa al nodo anterior del lado derecho y se repite el proceso de nuevo.

Ejemplo

El nodo donde se inicia la búsqueda es etiquetado como (s), una vez posicionado sobre éste se comienza la búsqueda del nodo destino, definido como nodo (t).

1.       Se arranca la búsqueda desde el nodo origen (s), tal y como se muestra en la siguiente figura, ubicado sobre éste el siguiente nodo a explorar, es el que se encuentra más a la izquierda y que aún no ha sido explorado.

2.       El nodo encontrado es el nodo (1), se evalúa para comprobar si es el nodo destino, si no lo es, se explorara el siguiente nodo que se encuentra más a la izquierda.

3.       El nodo encontrado es el nodo (5), se evalúa para comprobar si es el nodo destino, si no lo es, se explorara el siguiente nodo que se encuentra más a la izquierda.

4.       El nodo encontrado es el nodo (6), se evalúa para comprobar si es el nodo destino, si no lo es, se explorara el siguiente nodo que se encuentra más a la izquierda, pero ningún nodo es encontrado, éste es marcado y se devuelve al nodo anterior.

5.       Ubicados sobre el nodo (5), el siguiente nodo a explorar, es el nodo que se encuentre más a la izquierda, el cual corresponde al nodo (1), pero éste ya ha sido explorado, por lo tanto se va al siguiente nodo que se encuentra más a la izquierda, el cual corresponde al nodo (2)

6.       Ubicados sobre el nodo (2), el siguiente nodo a explorar, es el nodo que se encuentre más a la izquierda y que no ha sido explorado, el cual corresponde al nodo (3).

7.       Ubicados sobre el nodo (3), el siguiente nodo a explorar, es el nodo que se encuentre más a la izquierda y que no ha sido explorado, el cual corresponde al nodo (4).

8.       Ubicados sobre el nodo (4), el siguiente nodo a explorar, es el nodo que se encuentre más a la izquierda y que no ha sido explorado, el cual corresponde al nodo (8).

9.       Ubicados sobre el nodo (8), el siguiente nodo a explorar, es el nodo que se encuentre más a la izquierda y que no ha sido explorado, el cual corresponde al nodo (7).

10.   Ubicados sobre el nodo (7), el siguiente nodo a explorar, es el nodo que se encuentre más a la izquierda y que no ha sido explorado, nodo (t), el cual corresponde al nodo destino

Anexo B

Flujo Máximo

El problema del flujo máximo [43] consiste en encontrar la capacidad máxima requerida que puede ser transportada desde un nodo origen (s) a un nodo destino (t),  tomando en cuenta las restricciones de capacidad de cada enlace.

El Algoritmo de Ford-Fulkerson

Este método depende de tres términos: red residual, camino aumentado y cortes. Estas ideas son esenciales para el teorema de flujo máximo.

Red residual: Dada una red de flujo y su correspondiente flujo, una red residual es aquella por cuyos enlaces pueden admitir más flujo neto del que pueda ser transportado por ellos, en un momento determinado.

Camino aumentado o trayectoria de aumento y cortes: Un camino aumentado p es un camino desde (s) hasta (t) en la red residual. La capacidad residual de p es la máxima cantidad de flujo neto que se puede transportar a lo largo de los enlaces de p. Esta cantidad máxima de flujo neto corresponde al mínimo de las capacidades residuales de los enlaces, sobre este camino.

Secuencia de Pasos:

1. Seleccione cualquier camino valido desde s a t.
2. Aplique el método de etiquetado para encontrar un camino aumentado desde (s) a (t). Incremente el flujo entre este camino. Repita el paso 2. Si tal camino aumentado no existe, el flujo actual es el óptimo.

Método de etiquetado

Paso 1

Fije e(s) =   +∞ y p(s) = s.

Paso 2

Seleccione un vértice etiquetado X el cual no haya sido considerado.

Si no existe ningún vértice, entonces deténgase, no hay caminos aumentados de (s) a (t).

Paso 3

Para cualquier enlace (X, Y) que vaya a un vértice no etiquetado y, etiquete y con  e(Y) = min { e(X), u(X, Y)} y p(Y) = X donde u(X,Y) es la capacidad límite en un enlace de es la capacidad límite del enlace en la red residual.

Ejemplo:

Inicialmente, arranca el flujo en cero. La red residual es la misma que la original.

Paso 1:

Camino aumentado: s – a – d – t

Flujo entre el camino aumentado = min {e(s), e(a), e(d), e(t)} = min{ +∞, 6, 3, 3} = 3

Paso 2:

La red residual y las nuevas etiquetas son:

El camino aumentado es s – b – d – t y el flujo que puede ser enviado entre ese camino es min{+∞, 8, 4, 4} = 4.

Entonces la red residual es:

El camino aumentado es s – b – c – t y el flujo que puede ser enviado entre ese camino es min{+∞, 4, 2, 2} = 2.

Paso 3:

La red residual es:

No se puede etiquetar el nodo t. Esto significa que no hay camino aumentado en la red y de esta manera no podemos incrementar el flujo.

El flujo máximo es = 9

Los enlaces (a,d), (b,d) and (b,c) conforman el corte mínimo con una capacidad de 9 ( = Flujo máximo).

Trabajo de Grado presentado ante la ilustre Universidad Central de Venezuela para optar al Título de Magister Scientiarum en Investigación de Operaciones

Autora: Ing. Sandra Bertaggia

Venezuela, Caracas, Mayo del 2004