CENTRO DE INVESTIGACIN Y DE ESTUDIOS AVANZADOS DEL INSTITUTO POLITCNICO NACIONAL

DEPARTAMENTO DE CONTROL AUTOMTICO

Representacin y aprendizaje de conocimiento con redes de Petri difusasTESIS QUE PRESENTA EL:

Ing. Jair Cervantes Canales

PARA OBTENER EL GRADO DE

MAESTRO EN CIENCIASEN LA ESPECIALIDAD DE

CONTROL AUTOMTICODIRECTORES DE TESIS:

Dr. Wen Yu Liu Dr. Alejandro J. Malo Tamayo

Mxico, D.F. MARZO del 2005.

ndice general1. Introduccin 1.1. Antecedentes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2. Motivacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Planteamiento del Problema . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4. Organizacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2. Conceptos Basicos 2.1. Redes de Petri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.1. Denicin Formal y Fundamentos . . . . . . . . . . . . . . . . . . . . 2.1.2. Propiedades de las Redes de Petri. . . . . . . . . . . . . . . . . . . . 2.1.3. Mtodos de Anlisis. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. Redes Neuronales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1. Fundamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2. Aprendizaje de Redes Neuronales . . . . . . . . . . . . . . . . . . . . 2.3. Conjuntos Difusos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Deniciones Bsicas y Terminologa. . . . . . . . . . . . . . . . . . . 2.4. Razonamiento Difuso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1. Principio de Extensin. . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2. Variables Lingsticas . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.3. Reglas Difusas Si-Entonces. . . . . . . . . . . . . . . . . . . . . . . . 2.5. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 3 4 7 8 8 12 14 17 18 20 21 21 27 27 29 32 36

ii

NDICE GENERAL

3. Representacin de Conocimiento y Razonamiento con Redes de Petri Difusas 3.1. Representacin de Conocimiento. . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1. Reglas de Produccin . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2. Reglas de Produccin Difusas . . . . . . . . . . . . . . . . . . . . . . 3.2. Representacin de Conocimiento con Redes de Petri Difusas. . . . . . . . . . 3.3. Razonamiento con Redes de Petri Difusas . . . . . . . . . . . . . . . . . . . 3.3.1. Algoritmo de Razonamiento Hacia atrs (RDHAP). . . . . . . . . . . 3.3.2. Algoritmo de Razonamiento Difuso con Pesos (RDPP) . . . . . . . . 3.4. Comparacin Entre los Algoritmos Propuestos. . . . . . . . . . . . . . . . . . 3.5. Conclusin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4. Aprendizaje con Redes de Petri Difusas Adaptativas 4.1. Algoritmos de Aprendizaje en Redes Neuronales . . . . . . . . . . . . . . . . 4.1.1. Algoritmo de Widrow-Ho. . . . . . . . . . . . . . . . . . . . . . . . 4.1.2. Algoritmo Backpropagation (BP) . . . . . . . . . . . . . . . . . . . . 4.2. Redes de Petri Difusas Adaptativas (RPDA). . . . . . . . . . . . . . . . . . . 4.3. Aprendizaje para RPDA con el Algoritmo Widrow-Ho . . . . . . . . . . . . 4.3.1. Aprendizaje para RPDA sin Valores Frontera . . . . . . . . . . . . . 39 40 41 42 45 51 52 60 80 85 87 88 88 90 96 97 97

3.3.3. Algoritmo de Razonamiento Difuso con Pesos y Valores Frontera (RDPF) 68

4.3.2. Aprendizaje para RPDA con Valores Frontera . . . . . . . . . . . . . 101 4.4. Aprendizaje para RPDA con el Algoritmo BP . . . . . . . . . . . . . . . . . 103 4.5. Conclusin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5. Ejemplos 111

5.1. Aprendizaje con el Algoritmo de Widrow-Ho . . . . . . . . . . . . . . . . . 111 5.2. Aprendizaje con el Algoritmo Backpropagation . . . . . . . . . . . . . . . . . 114 5.3. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141

NDICE GENERAL 6. Conclusiones y Trabajo Futuro

iii 143

6.1. Contribucin de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 6.2. Trabajo Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

iv

NDICE GENERAL

ndice de guras1.1. (a) Razonamiento de RPD con grados de pertenencia. (b) Razonamiento de RPD con funciones de membresa. . . . . . . . . . . . . . . . . . . . . . . . . 2.1. Lugares, transiciones y seales en una red de Petri. . . . . . . . . . . . . . . 2.2. Red de Petri y su grafo de alcanzabilidad. . . . . . . . . . . . . . . . . . . . 2.3. Red de Petri y su grafo de cobertura. . . . . . . . . . . . . . . . . . . . . . . 2.4. Reglas de reduccin que presentan vivacidad y k-limitacin. . . . . . . . . . 2.5. Red neuronal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6. Inriendo y = b de x = a y y = f (x) . . . . . . . . . . . . . . . . . . . . . . 2.7. Inriendo el intervalo b del intervalo a y la funcin valor-intervalo f (x) . . . 2.8. Inriendo el conjunto difuso B del conjunto difuso A y la relacin difusa Q 3.1. Funciones de membresa de presin baja, media y alta . . . . . . . . . . . . . 3.2. Red de Petri de una regla de produccin difusa. . . . . . . . . . . . . . . . . 3.3. Redes de Petri de las principales reglas de produccin difusas. . . . . . . . . 3.4. Red de Petri Difusa del proceso de inspeccin. . . . . . . . . . . . . . . . . . 3.5. Representacin de las reglas de produccin difusas. . . . . . . . . . . . . . . 3.6. Grafo AND-OR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7. Red de Petri que representa las reglas de produccin del Ejemplo 3.1. . . . . 3.8. Grafo AND-OR del Ejemplo 3.1. . . . . . . . . . . . . . . . . . . . . . . . . 3.9. Valor de verdad de la proposicin d6 . . . . . . . . . . . . . . . . . . . . . . . 3.10. Red de Petri difusa representando las reglas de produccin del Ejemplo 3.2.0 0

3 9 14 15 16 19 33 33 34 44 46 47 50 54 57 58 59 61 64

vi

NDICE DE FIGURAS 3.11. Arbol de nodos del Ejemplo 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . 3.12. Funciones de membresa de las rutas de la proposicin d9 . . . . . . . . . . . . 3.13. Red de Petri difusa de las reglas de produccin del Ejemplo 3.3. . . . . . . . 3.14. rbol de nodos del Ejemplo 3.3. . . . . . . . . . . . . . . . . . . . . . . . . . 3.15. Funciones de membresa de las rutas de la proposicin d4 . . . . . . . . . . . . 3.16. Disparo de una RPD del Tipo 1. (a) Antes del disparo de la transicin ti . (b) Despus del disparo de la transicin ti . . . . . . . . . . . . . . . . . . . . . . 3.17. Disparo de una RPD del Tipo 2. (a) Antes del disparo de la transicin ti . (b) Despus del disparo de las transicin ti . . . . . . . . . . . . . . . . . . . . . . 3.18. Disparo de una RPD del Tipo 3. (a) Antes del disparo de las transiciones tj1 , tj2 , .., tjn . (b) Despus del disparo de las transiciones tj1 , tj2 , .., tjn . . . . . 3.19. Disparo de una RPD del Tipo 4. (a) Antes del disparo de las transiciones tj1 , tj2 , .., tjn . (b) Despus del disparo de las transiciones tj1 , tj2 , .., tjn . . . . . 3.20. Red de Petri difusa del Ejemplo 3.4 . . . . . . . . . . . . . . . . . . . . . . . 3.21. Red de Petri con funciones de membresa. . . . . . . . . . . . . . . . . . . . 3.22. Red de Petri difusa del problema . . . . . . . . . . . . . . . . . . . . . . . . 3.23. Valores de Verdad de las proposiciones consecuentes del grupo 1. . . . . . . . 4.1. Aprendizaje mediante algoritmo de Widrow-Ho . . . . . . . . . . . . . . . . 4.2. Fase de Propagacin hacia adelante y hacia atrs del algoritmo BP. . . . . . 4.4. Red de Petri difusa Adaptativa sin valores frontera de un caso 2. . . . . . . 72 74 76 82 85 89 93 98 71 69 68 65 65 66 67 67

4.3. Modelado de reglas de produccin difusas con redes de Petri difusas adaptativas. 97 4.5. Red neuronal de una red de Petri difusa adaptativa. . . . . . . . . . . . . . . 100 4.6. Red de Petri difusa con pesos adaptativa con valor frontera i asociado a la transicin ti de un Caso 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 4.7. Funcion sigmoide. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.8. Red neuronal multicapa con n 1 capas ocultas y una neurona de salida. . . 106 5.1. Red de Petri difusa del Ejemplo 5.1 . . . . . . . . . . . . . . . . . . . . . . . 112

NDICE DE FIGURAS 5.2. Conversin de la red de Petri difusa adaptativa de la gura 5.1 en una red

vii

neuronal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.3. Aprendizaje de pesos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.4. Red de Petri difusa adaptativa del Ejemplo 5.2. . . . . . . . . . . . . . . . . 116 5.5. Conversin de la red de Petri difusa adaptativa de la gura 5.4 en una red neuronal. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 5.6. Resultados de aprendizaje del Ejemplo 5.2 . . . . . . . . . . . . . . . . . . . 119 5.7. Nmeros difusos antes y despus del aprendizaje de pesos de W1. . . . . . . 119 5.8. Aprendizaje de pesos para red multicapa. . . . . . . . . . . . . . . . . . . . . 122 5.9. Esquema de cuatro pasos de razonamiento. . . . . . . . . . . . . . . . . . . . 124 5.10. Red de Petri difusa (parte (a)) del Ejemplo 5.3 . . . . . . . . . . . . . . . . . 126 5.11. Red de Petri difusa (parte (b)) del Ejemplo 5.3 . . . . . . . . . . . . . . . . 127 5.12. Trayectorias recorridas en la red de Petri . . . . . . . . . . . . . . . . . . . . 131 5.13. Redes neuronales multicapa . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 5.14. Resultados del aprendizaje del Ejemplo 5.3 (Ruta activa T1). . . . . . . . . . 136 5.15. Resultados del aprendizaje del Ejemplo 5.3 (Ruta activa T2). . . . . . . . . . 138 5.16. Resultados del aprendizaje del Ejemplo 5.3 (Ruta activa T3). . . . . . . . . . 140

viii

NDICE DE FIGURAS

ndice de cuadros3.1. Tabla de verdad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Escalas de Verdad y sus Intervalos Numricos . . . . . . . . . . . . . . . . . 3.3. Valores frontera, factores de certeza y pesos de RPD del ejemplo 3.4 . . . . . 3.4. Valores de verdad antecedentes de la RPD del ejemplo 3.4. . . . . . . . . . . 3.5. Valores de verdad consecuentes de la RPD del ejemplo 3.4. . . . . . . . . . . 42 43 83 83 84

5.1. Proposiciones asociadas a los lugares . . . . . . . . . . . . . . . . . . . . . . 128 5.2. Valores lingsticos de la proposiciones antecedentes . . . . . . . . . . . . . . 130 5.3. Valores Numricos de la proposiciones antecedentes . . . . . . . . . . . . . . 130 5.4. Valores lingsticos de la proposiciones consecuentes . . . . . . . . . . . . . . 132 5.5. Valores Numricos de la proposiciones consecuentes . . . . . . . . . . . . . . 133

x

NDICE DE CUADROS

Captulo 1 Introduccin1.1. Antecedentes

Las redes de Petri (RdP) fueron introducidas en la literatura en la tesis doctoral de Carl Adam Petri [33] como una herramienta para simular las propiedades dinmicas de sistemas complejos mediante modelos grcos de procesos concurrentes. Desde entonces su estudio y desarrollo han tenido un auge realmente vigoroso debido fundamentalmente a las numerosas aplicaciones que se les ha encontrado, las cuales incluyen diversas reas del conocimiento y de la tcnica. Se ha demostrado que las RdP son un instrumento adecuado para la representacin y anlisis de ciertos sistemas, ya que estas tienen la habilidad de representar y analizar de una forma fcil sincronizacin y concurrencia, donde varios procesos que evolucionan simultneamente son parcialmente independientes. Las RdP proveen un conjunto de herramientas con gran capacidad de descripcin y operacin que son ocupadas para representar reglas difusas (reglas que describen la relacin difusa entre dos proposiciones). Un conjunto entero de reglas de produccin es llamado una base de reglas. Adems al formalismo de reglas de produccin el sistema provee un signicado para denir los objetos referidos en las reglas de produccin, llamado declaracin de dominio. La base de reglas y la declaracin del dominio constituyen juntos una base de conocimiento (KB) del sistema difuso.

2

Introduccin En [22] las RdP son usadas para modelar bases de reglas, relacionando simplemente

algunos de los elementos (funcin de marcado) y caractersticas (bsicamente lugares y transiciones) del formalismo de Petri con los elementos bsicos de una KB (proposiciones, grados de verdad e implicaciones). Cuando la complejidad de los sistemas KB incrementa, nuevos elementos son incluidos en la denicin inicial de una RdP, los cuales permiten a una RdP representar adecuadamente los rasgos que caracterizan una KB. Este procedimiento nos lleva a la representacin de un nuevo modelo el cual es llamado red de Petri difusa (RPD). Las RdP tienen una cualidad inherente en representar lgica de una forma visual e intuitiva y las RPD toman todas estas ventajas de las RdP. De esta manera, la forma de razonamiento de un sistema experto puede ser reducido a simples rboles de nodos si algoritmos de razonamiento basados en RPD son empleados como mquinas de inferencia [7],[5], [6]. Varias generalizaciones de las redes de Petri difusas han sido propuestas en la literatura [47], [48], [3], [23], [30] con el propsito de considerar ciertos problemas concretos vinculados con la representacin del conocimiento, razonamiento difuso y teora de decisin.

1.2.

Motivacin

Las RPD pueden representar perfectamente reglas de produccin difusas con pesos [6][48]. Sin embargo, los pesos en estas no pueden ajustarse de acuerdo a la actualizacin de conocimiento, en otras palabras, estas no tienen la habilidad de aprender. Por otro lado, las redes de Petri difusas adaptativas [42] poseen la habilidad de aprender de una forma parecida a las redes neuronales. Sin embargo, el conjunto de valores (valores de verdad, factores de certeza, pesos y valores frontera) asociados en la red de Petri difusa para generar un razonamiento son nmeros en [0,1]. Es decir, son asociados unicamente pares (x, ((x)) -elemento y grado de pertenencia-) como pesos, valores de verdad, valores frontera y factores de certeza a los lugares y transiciones de la red de Petri (ver gura 1(a) ). Por lo cual, es impractico listar todos los pares deniendo el grado de pertenencia [16] de cada elemento al conjunto difuso. Una forma ms concreta de denir el grado de pertenencia es expresarla como una funcin de membresa (funcin gaussiana, funcin campana, nmero difuso

1.3 Planteamiento del Problema( x1 , ( x1 ))

3

( x2 , ( x2 ))

( y, ( y ))

( xn , ( xn ))

(a )

( x1 )

x1

( x2 )

( y)

x2

y

( xn )

xn

(b)

Figura 1.1: (a) Razonamiento de RPD con grados de pertenencia. (b) Razonamiento de RPD con funciones de membresa. triangular, nmero difuso trapezoidal, etc.). Si podemos asociar una funcin de membresa como un valor de verdad a una red de Petri difusa (ver gura 1(b)), entonces el proceso de razonamiento es mucho ms concreto y conveniente.

1.3.

Planteamiento del Problema

En el trabajo de esta tesis nos ocupamos del modelado y aprendizaje de redes de Petri difusas con funciones de membresa, especicamente nmeros difusos triangulares [20], [16] empleando los formalismos de redes neuronales y redes de Petri.

4 Los objetivos principales de este proyecto son:

Introduccin

1) Elaborar un algoritmo de razonamiento con propagacin hacia adelante y hacia atrs mediante nmeros difusos triangulares utilizando redes de Petri difusas. 2) Elaborar el algoritmo de razonamiento con propagacin hacia adelante y valores frontera utilizando nmeros difusos triangulares. 3) Elaborar algoritmos de aprendizaje de pesos mediante redes de Petri difusas con pesos adaptativas modicando los algoritmos de aprendizaje de Widrow Ho y Backpropagation (BP) para trabajar con nmeros difusos triangulares.

1.4.forma:

Organizacin

La tesis esta constituida por cinco captulos los cuales estn organizados de la siguiente Capitulo 2. Se da una introduccin a los conceptos bsicos de redes de Petri y Redes Neuronales, tambin se dan las nociones bsicas de conjuntos difusos, funciones de membresa y reglas de produccin difusas con la cual se establecen los principios para contruir una nueva estructura para la representacin de conocimiento, razonamiento difuso y aprendizaje de conocimiento. Capitulo 3. Se presentan tres algoritmos de razonamiento difuso. El Primero es un algoritmo de razonamiento difuso hacia atrs con pesos originalmente propuesto en [5]. El algoritmo propuesto en esta tesis es modelado con cuatro tipos de reglas de razonamiento. El segundo algoritmo fue originalmente propuesto en [6] este algoritmo de razonamiento difuso hacia adelante es modelado con cuatro reglas de razonamiento, la diferencia radica en que S.M. Chen calcula el valor de verdad nal como el mximo de todas las transiciones disparadas y en el algoritmo propuesto aqu, se calcula el valor de verdad mediante el centro de gravedad de las transiciones disparadas. El tercer algoritmo, se modela el algoritmo con cuatro reglas de razonamiento, este fue propuesto originalmente en [42] y emplea tres tipos de reglas de razonamiento. Los tres algoritmos de razonamiento difuso propuestos son modicados para trabajar con

1.4 Organizacin nmeros difusos triangulares.

5

Capitulo 4. Se propone un mtodo de aprendizaje de pesos modicando los algoritmos de Widrow Ho y el algoritmo backpropagation (BP) utilizando redes de Petri difusas con pesos adaptativas, donde los pesos asociados a los lugares son nmeros difusos triangulares. Capitulo 5. Se desarrollan algunos ejemplos utilizando los algoritmos de razonamiento y aprendizaje propuestos en los capitulos 3 y 4.

6

Introduccin

Captulo 2 Conceptos BasicosEn este capitulo introducimos los fundamentos de redes de Petri, incluyendo la denicin, terminologa bsica, reglas de disparo de transiciones, propiedades y mtodos de anlisis. Por otro lado, damos los fundamentos de las redes neuronales y los tipos de aprendizaje. En este mismo orden, introducimos los principales conceptos y nociones matemticas de conjuntos difusos, primero vemos los conjuntos difusos como una generalizacin de conjuntos clsicos generalizando el rango de la funcin de membresa (o funcin caracterstica) de {0,1} a un nmero real en el intervalo [0,1]. Varios conceptos bsicos de conjuntos difusos como normalidad, convexidad y nmeros difusos son denidos. Por ultimo introducimos los conceptos de principio de extensin y relaciones difusas as como variables lingsticas, los cuales son usados en razonamiento difuso. Ya que la investigacin en redes de Petri, redes neuronales y conjuntos difusos es demasiado extensa, es imposible cubrir todos los aspectos de los desarrollos actuales en estos campos. Por lo tanto, el objetivo de este capitulo es proveer una introduccin concisa y un resumen de los conceptos bsicos centrales para el estudio de estos campos. El material cubierto en este capitulo ser usado en los siguientes captulos.

8

Conceptos Basicos

2.1.

Redes de Petri

Las redes de Petri fueron introducidas en la literatura en la tesis doctoral de Carl Adam Petri [33]. Las Redes de Petri son una herramienta grca y matemtica de modelado [26][32][37] para la descripcin formal de sistemas cuya dinmica se caracteriza por concurrencia, sincronizacin, exclusin mutua y conictos, las cuales son caractersticas tpicas de sistemas distribuidos. El modelado de redes de Petri tiene dos caractersticas principales interesantes. Primero, es posible visualizar su comportamiento como concurrencia, paralelismo, sincronizacin y recursos compartidos. Segundo, existen varios mtodos para el anlisis de redes de Petri. Las redes de Petri han sido desarrolladas y extendidas durante aos, por lo que varias clases de redes de Petri han sido denidas. Entre ellas, redes de Petri coloreadas por Kurt Jensen[17][18], temporizadas [2][34], estocsticas [9], algebraicas [19], continuas e hbridas [1], difusas [30], etc. En este capitulo hacemos una breve introduccin a la teora de las redes de Petri.

2.1.1.

Denicin Formal y Fundamentos

Las redes de Petri (RP) se describen como una herramienta de naturaleza grca para el diseo y anlisis de sistemas dinmicos de eventos discretos [26]. Una red de Petri se representa grcamente por un grafo dirigido bipartito. Los dos tipos de nodos, lugares y transiciones (ver gura 2.1) representan, las variables que denen el estado del sistema (lugares) y a sus transformadores (transiciones). Los lugares se representan por crculos, las transiciones por barras y el marcado M se representa por una distribucin en los lugares denominados marcas. Una marca se representa grcamente por un punto en el interior del crculo que dene el lugar que lo contiene. Los lugares y transiciones se conectan por arcos dirigidos. Un arco dirigido de un lugar Pi a una transicin Tj dene un lugar de entrada de la transicin. Mltiples entradas a una transicin son indicadas por mltiples arcos desde el lugar de entrada a la transicin. Un lugar de salida es indicado por un arco desde la transicin al lugar. Anlogamente, mltiples salidas son representadas por mltiples arcos.

2.1 Redes de PetriP1

9

T 1 L ugar Marc a P 2

T 2 T 5 P3

T ransic in

T 3

T 4

P4

Figura 2.1: Lugares, transiciones y seales en una red de Petri. El marcado de una red, M, se dene por un vector columna en donde los elementos son el nmero de marcas contenidas en los lugares. El marcado dene el estado de la red de M = Petri. Para la red de Petri dada en la gura 2.1 tenemos: Lugares: P = {P1 , P2 , P3 , P4 } ;

Transiciones : T = {T1 , T2 , T3 , T4 , T5 } ; Marcado m1 = m2 = 1; m3 = m4 = 0; h iT 1 1 0 0 Denicin Formal.

Denicin 2.1 (Red de Petri Ordinaria) Una Red de Petri Ordinaria [37] (RPO), N, es una cudruplo N =< P, T, P re, P ost >, donde: P = {p1 , p2 , ....., pm } es un conjunto nito y no vaco de lugares; P T = y P T 6= ;

T = {t1 , t2 , ....., tn } es un conjunto nito y no vaco de transiciones;

P ost : T P {0, 1} es el conjunto de lugares de salida de T . y M0 es el marcado inicial.

P re : P T {0, 1} es el conjunto de lugares de entrada a T ;

Una RPO marcada es un par Nm = hN, M0 i en el cual N es una red de Petri Ordinaria

10

Conceptos Basicos

Denicin 2.2 (Representacin matricial) Una RdP N se encuentra denida matricial(nmero de transiciones de T). Se denomina: mente por medio de dos matrices [37]. Sea n = |P | (nmero de lugares de P) y m = |T | Matriz de incidencia previa a la matriz C = [c ]nm en la que c = P re(pi , tj ). ij ij Matriz de incidencia posterior a la matriz C + = [c+ ]nm en la que c+ = P ost(ti , pj ). ij ij Matriz de incidencia de N : C = C + C . Es decir, en las matrices de incidencia las las representan a los lugares y las columnas a las transiciones. Ejemplo 1. De la gura 1 1 0 0 C = P re(pi , tj ) = 0 0 0 0 los siguientes conjuntos: 2.1 tenemos que: 0 0 0 1 0 0 + ; C = P ost(ti , pj ) = 0 1 0 0 0 1

0 0 0 0 1

1 0 0 0 0 0 1 0 0 0 0 0 1 1 0

Denicin 2.3 Sea N una RdP , donde t T y p P (segn denicin 2.1). Se denen

Conjunto de lugares de entrada a t : t = {p P | P re(p, t) > 0} Conjunto de lugares de salida de t : t = {p P | P ost(t, p) > 0} Conjunto de transiciones de entrada a p : p = {t T | P ost(t, p) > 0} Conjunto de transiciones de salida de p : p = {t T | P re(p, t) > 0} Denicin 2.4 (Red pura) Una RdP N es una red pura [26] si no existe ninguna transicin que tenga un lugar que sea al mismo tiempo de entrada y salida de la transicin: tj T , pi P, P re(pi , tj )P ost(tj , pi ) = 0 (2.1)

2.1 Redes de Petri Comportamiento Dinmico.

11

Denicin 2.5 (Transicin habilitada) Una transicin t T est habilitada para un marcado M dado, sii p t se verica M(p) P re(p, t). Denicin 2.6 (Grado de habilitacin) El grado de habilitacin de una transicin indica el mximo nmero que la transicin puede ser disparada concurrentemente. Denicin 2.7 (Regla de evolucin del marcado) Si t est habilitada para un marcado M entonces t puede dispararse. En la operacin se alcanza un nuevo marcado M 0 , y se denota P ost(t, p) marcas a cada lugar p t . El cambio en el marcado esta dado por la ecuacin: M 0 (p) = M(p) P re(p, t) + P ost(t, p), p P Subclases de Redes de Petri Ordinarias. Denicin 2.8 (Grafo de estados) Un grafo de estado [26] (GE) o mquina de estados (ME) es una RPO que cumple: por M[t > M 0 , el cual resulta de quitar Pre(p, t) marcas de cada lugar p t y aadir (2.2)

t T, | t| = |t | = 1 una RPO que cumple:

(2.3)

Denicin 2.9 (Grafo marcado) Un grafo marcado [26] (GM) o grafo de sincronizacin es

p P, | p| = |p | = 1 que cumple:

(2.4)

Denicin 2.10 (Red de libre eleccin) Una RdP de libre eleccin [26] (RLE) es una RPO

p P, si |p | > 1, entonces t p , | t| = 1

(2.5)

12

Conceptos Basicos

Denicin 2.11 (Red simple) Una RPO simple [26] (ROS) es una RdP que cumple: p p 6= p p o p p 1 2 1 2 1 2 para toda p1 , p2 P. (2.6)

2.1.2.

Propiedades de las Redes de Petri.

Vivacidad Denicin 2.12 Una transicin t est viva [32] para un marcado inicial dado M0 , sii existe una secuencia de disparos a partir de un marcado M sucesor de M0 que comprenda a t : M M(R, M0 ) : M M 0 tal que t . Se

Una RdP marcada est viva para M0 sii todas sus transiciones son vivas para M0 .

puede decir que la propiedad de vivacidad signica la ausencia en el conjunto de alcanzabilidad de un marcado en el que la red se bloquee totalmente, ya que, para que est viva, todas sus transiciones deben ser disparables desde cualquier marcado alcanzable. Se dice que una RdP marcada est parcialmente viva para M0 si, tomando como punto de partida cualquier marcado alcanzable a partir de M0 , existe al menos una transicin disparable y otra transicin no viva. Toda RdP marcada parcialmente viva tiene la posibilidad de evolucin global, independientemente de que existan transiciones que no puedan ser disparadas. Ciclicidad. Denicin 2.13 Se dice que una RdP posee un comportamiento globalmente cclico para Mo si existe una secuencia de disparos que permite alcanzar el marcado inicial Mo a partir de cualquier marcado M alcanzable a partir de Mo: M M(R, M0 ), tal que M M0 .

(2.7)

La ciclicidad o reversibilidad [26] de una RdP marcada garantiza que no existen subconjuntos nales de estados (marcados). Un subconjunto nal de estados (marcados) contiene estados (marcados) mutuamente alcanzables entre s y tales que el estado inicial (marcado inicial) no es alcanzable a partir de ninguno de ellos.

2.1 Redes de Petri

13

Acotamiento. El signicado de esta propiedad es el de asegurar que el sistema que una red representa, posee un nmero nito de estados (si suponemos que cada lugar de la red representa a una variable de estado del sistema y su marcado el valor de dicha variable). Luego la propiedad de acotamiento determina la nitud del nmero de estados del sistema representado por una RdP. Denicin 2.14 Un lugar p es k-acotado para M0 sii existe un nmero entero k tal que entero k que verica la desigualdad anterior. M(p) k para cualquier marcado M M(R, M0 ). Se denomina cota del lugar p al menor

Denicin 2.15 Una RdP marcada es k-acotada para M0 sii todos sus lugares son kacotados para M0 : p P y M M(R, M0 ), M(p) k. (2.8)

Merece una consideracin especial la 1-acotacin. Si una RdP es 1-acotada para M0 , su marcado es binario (un lugar est o no est marcado) y se dir que la RdP es binaria para M0 . Una red segura, es una RdP 1-acotada. Una RdP es estructuralmente acotada si es acotada para cualquier marcado inicial y nito. Conservatividad Las marcas de una red se pueden entender como recursos del sistema. Normalmente los recursos de un sistema ni se crean ni se destruyen. Cuando las marcas se conservan, tras el disparo de una secuencia de transiciones, se dice que la red es conservativa. Denicin 2.16 (Red de Petri estrictamente conservativa) Sea R = (P, T, P re, P ost, M0 ) se dice que es estrictamente conservativa sii M 0 M(R, M0 ), i M 0 (pi ) = i M(pi ), pi P. Esto es, se ha de mantener el nmero de marcas para cualquier marcado de la red. La denicin anterior implica que el nmero de entradas ha de coincidir con nmero de salidas, es decir: (|I(tj)|) = |O(tj)|), para cada transicin disparable.

14P1 T 4 T 1 T 2

Conceptos Basicos

0 0 0 1 0

P2

P3 T 3

T 2

1 0 0 0 0

T 1

0 1 1 0 0

T 3 0 0 0 0 1

P4

P5

T 5 T 4 T 5

Figura 2.2: Red de Petri y su grafo de alcanzabilidad. Alcanzabilidad. La alcanzabilidad es una base fundamental para estudiar las propiedades dinmicas de cualquier sistema. al dispararse una transicin habilitada, esta cambiar la distribucin de las seales ( marcado). De esta forma, de una secuencia de disparos resultar una secuencia de marcados, luego un marcado Mn es alcanzable a partir de M0 , si existe una secuencia de disparos que a partir de M0 nos lleve a Mn . Una secuencia de disparos M0 [i Mn . la denotaremos por = t1 , t2 , ....., tn . en este caso Mn es alcanzable desde M0 , sii t.q.

2.1.3.

Mtodos de Anlisis.

Las tcnicas para el anlisis de RdP (anlisis cualitativo de redes) se clasican normalmente en tres grupos. Tcnicas Enumerativas. En primer lugar se tienen las tcnicas enumerativas [32][26].

Se basan en la generacin del grafo de alcanzabilidad para sistemas limitados o del grafo de cobertura para sistemas no limitados [8]. Estas tcnicas se pueden aplicar en teora,

2.1 Redes de PetriP10 0 0

15

T 3 P2

T 1 P3

1 0 0

0 1 1

0 0 0 1

1 0

1 0

T 2

Figura 2.3: Red de Petri y su grafo de cobertura. pero en la prctica estn limitadas a sistemas pequeos debido a su elevada complejidad computacional. En este grafo los nodos corresponden al marcado alcanzable y los arcos corresponden al disparo de las transiciones. En la gura 2.2 se muestra una red de Petri y su grafo de alcanzabilidad (Grafo de marcados). y T1 , T3, T5 . En una red no limitada, el nmero de seales en un lugar puede ser innito. Un lugar que puede llegar a tener un nmero innito de seales se representa por . El grafo resultante es llamado grafo de cobertura (ver gura 2.3). Tcnicas de Transformacin. En segundo lugar se tienen las tcnicas de transformacin. En este grupo de tcnicas el objetivo es reducir el tamao de los modelos mediante reglas de reduccin que preserven las propiedades que se quieren estudiar. En la gura 2.4 puede observarse un conjunto sencillo de seis reglas de reduccin que preservan vivacidad y klimitacin tomadas de [37]. Con este conjunto de reglas es posible reducir la complejidad del clculo de la vivacidad y limitacin de un sistema. Tcnicas Estructurales. En tercer lugar se tienen las tcnicas estructurales [37]. En este grupo de tcnicas el objetivo es obtener la mxima informacin del modelo utilizando Este grafo puede ser utilizado para mostrar que la red es segura, viva, reversible y que esta tiene dos componentes que se repiten T1 , T2, T4

16

Conceptos Basicos

(A)

(B)

(C )

(D)

(E)

(F)

Figura 2.4: Reglas de reduccin que presentan vivacidad y k-limitacin.

2.2 Redes Neuronales nicamente su estructura y marcado inicial.

17

Los mtodos de lgebra lineal son utilizados para determinar las propiedades de la red. La ecuacin de estado de una red de Petri se dene como sigue: el marcado Mk se dene como un vector columna m 1. La j esima entrada de Mk denota el nmero de seales k esimo disparo o vector de control uk es un vector columna de n 1, con n 1 0s y i esima la de la matriz de incidencia C denota el cambio de marcado como el resultado una entrada 1 en la i esima posicin, indicando el disparo de la transicin i. Esto es, la en el lugar j inmediatamente despus del k esimo disparo en la secuencia de disparos. El

del disparo de la transicin i, luego la ecuacin de estado para la red de Petri se escribe como sigue: Mk = Mk1 + C T uk ,

k = 1, 2, 3, ....

(2.9)

El marcado de una red de Petri puede ser cambiado cada vez que una transicin se dispara. Si no ocurre un bloqueo, el nmero de disparos es ilimitado. Sin embargo, no todos los marcados pueden ser alcanzados y no todas las secuencias de disparos pueden ser llevadas a cabo. Las restricciones son dadas por los invariantes de la red. Un marcado invariante es obtenido si la suma de los pesos de el marcado de un subconjunto de lugares en una red es siempre constante. Los lugares contenidos en este subconjunto son llamados componentes conservativos y el vector que contiene los pesos es P-Invariante. Si el disparo de una cierta secuencia de transiciones resulta en el mismo marcado como cuando inicio, la secuencia es llamada componente repetitivo. El vector caracterstico de la secuencia de disparos es el T-Invariante.

2.2.

Redes Neuronales

Una red neuronal articial (RNA)[15] es una elemento capaz de procesar gran cantidad de informacin en forma paralela y distribuida, las cuales pueden almacenar conocimiento experimental y tenerlo disponible para su uso [13].

18

Conceptos Basicos Las redes neuronales simulan el funcionamiento de las redes biolgicas mediante modelos

matemticos, los cuales son implementados usando componentes electrnicos o mediante algn software en una computadora. Las redes neuronales tienen las siguientes caractersticas: habilidad de aprendizaje, habilidad de procesamiento en paralelo y la propiedad de aproximar cualquier funcin suave. Las redes neuronales han sido estudiadas por muchos aos, uno de los atributos de estas es que poseen la habilidad de aprender. En 1949 Donald Hebb [14] desarrollo una regla de aprendizaje siolgica para la modicacin de los pesos sinpticos, en 1957 Rosenblatt desarrollo el perceptrn, la mayor parte del trabajo es descrito en el libro Principles of Neurodynamics [35]. Uno de los resultados ms signicativos presentados en este libro fue la regla de entrenamiento del perceptrn. Widrow y Ho [40] desarrollaron en 1960 el algoritmo del mnimo error cuadrtico medio (LMS), usado para formular Adaline (elemento de aprendizaje adaptable) y en (1962) Madaline (mltiple adaline). En 1969 el entusiasmo por las redes neuronales fue incrementado un poco por la publicacin del libro de Minsky y Papert Perceptrons [25]. En l los autores muestran que existe una interesante clase de problemas (aquellos que no son linealmente separables) los cuales el perceptrn de una sola capa no puede resolver. Grossberg fue poniendo los fundamentos de su teora de resonancia adaptativa (ART por sus siglas en ingles) [4][11]. Fukushima desarroll el cognitrn [10]. El algoritmo de backpropagation posee paternidad literaria mltiple como es notado por Grossberg en [12]. Este algoritmo fue descubierto por Werbos [39], redescubierto por Parker [29] y descubierto una vez ms por Rumelhart, Hinton y Williams [36].

2.2.1.

Fundamentos

Las neuronas son la base de las redes neuronales. Una neurona es una unidad procesadora de informacin que es fundamental para la operacin de una red neuronal. La gura 2.5 muestra el modelo de una neurona, los elementos bsicos de una neurona son descritos a continuacin: Un vector de entrada el cual es denotado por X, X = (x1 , x2 , ..., xj ) donde j es el

2.2 Redes Neuronales

19

x1

wk 1

S eales de entrada

x2

wk 2

uk

ykS alida

xj

wk j

Umbral

Figura 2.5: Red neuronal. nmero de entradas a la RNA y a su vez la dimensin de X, este vector X son los datos con los que va operar la neurona, estas pueden ser dadas del medio ambiente o ser salidas de neuronas anteriores. Pesos sinpticos. Al ser capturados los datos de entrada estos son propagados a travs de la red, en el proceso de propagacin cada componente xj del vector de entrada X es multiplicada por una variable wkj , la cual aumenta o atena la seal de entrada, a wkj se le conoce como peso sinptico o simplemente peso, estos pesos no tienen el mismo valor siempre sino que se van modicando segn se requiera para tener un mejor desempeo, posteriormente puede haber una convergencia y entonces estar jos. Cuando se habla de que una red es capaz de aprender se reere al hecho de poder modicar sus pesos wkj , el conjunto de pesos genera una matriz W , es decir, wkj es la kj-sima componente de la matriz de pesos W .

Un operador suma para sumar las seales de entrada. Esto es, la adicin de los productos xj wkj .

20

Conceptos Basicos Una funcin de activacin para limitar la amplitud de la salida de una neurona. Este limite usualmente es el intervalo unitario [0,1] o [-1,1]. En trminos matemticos, una neurona k puede ser descrita por una par de ecuaciones:p P

uk = y

wkj xj

(2.10)

j=1

yk = (uk k ),

(2.11)

donde x1 , x2 , ..., xj son las seales de entrada, wk1 , wk2 , ..., wkj son los pesos sinpticos de la neurona k, uk es la salida, mientras que k es el umbral, (.) es la funcin de activacin y yk es la seal de salida de la neurona.

2.2.2.

Aprendizaje de Redes Neuronales

La capacidad de aprendizaje adaptativo es una de las caractersticas ms atractivas de las redes neuronales. Esto es, aprenden a llevar a cabo ciertas tareas mediante un entrenamiento. Las redes neuronales usan su capacidad de aprendizaje adaptativo para autoorganizar la informacin que reciben durante el aprendizaje y/o la operacin. De acuerdo al tipo de aprendizaje, las redes se pueden subdividir en dos grupos: Redes con aprendizaje supervisado. Este tipo de redes se entrenan presentando para cada combinacin de entradas, las salidas que se espera ellas produzcan. Los algoritmos de aprendizaje calculan pesos y sesgos nuevos a manera de minimizar el error entre la salida deseada y la obtenida. Redes no supervisadas. Los algoritmos de aprendizaje calculan nuevos pesos libremente. Estas redes se utilizan como clasicadores pues se caracterizan por asociar una combinacin de entradas especicas con una sola salida.

2.3 Conjuntos Difusos

21

2.3.

Conjuntos Difusos

Un conjunto clsico es un conjunto con una cota rgida, este es caracterizado por y como la totalidad de sus nmeros, objetos o elementos. Los miembros de un conjunto clsico pueden ser determinados por alguna enumeracin o alguna propiedad caracterstica, de esta forma uno puede representar un conjunto A con elementos a1 , ..., a15 . A = {a1 , ..., a15 } A = {ai | 1 i 15} . En donde cada miembro ai puede pertenecer o no pertenecer a un conjunto A. Sin embargo un conjunto difuso, es un

conjunto sin una cota rgida [16], [49], [44], esto es, la transicin de pertenecer a un conjunto a no pertenecer a un conjunto es gradual, esta transicin suave es caracterizada por grados de pertenencia o funcin de membresa, las cuales dan exibilidad a los conjuntos difusos. La difusividad no viene de la aleatoriedad de los miembros constituyentes de los conjuntos, sino de la naturaleza imprecisa e incierta de pensamientos y conceptos abstractos.

2.3.1.

Deniciones Bsicas y Terminologa.

La lgica difusa asocia incertidumbre a la estructura de un conjunto de datos [21]. Los elementos de un conjunto difuso son pares ordenados que indican el valor del elemento y su elemento x pertenece al conjunto A con un grado de pertenencia A (x), el cual varia entre 0 y 1. Luego un conjunto difuso A es una simple extensin de un conjunto clsico en el cual a la funcin caracterstica le es permitido tener valores entre 0 y 1, si este valor lo restringimos a nicamente los valores de 0 y 1 entonces A es reducido a un conjunto clsico. A continuacin se enumeran algunas de las deniciones bsicas de lgica difusa. grado de pertenencia. Para un conjunto difuso A = {(x, A (x)) | x X}, se tiene que el

Soporte y Fuzzy Singleton. El soporte de un conjunto difuso A es el conjunto de todos los puntos x X tales que A (x) > 0 : Soporte(A) = {x | A (x) > 0}. Un conjunto difuso cuyo soporte es un nico punto en X con A (x) = 1 es llamado un fuzzy singleton.

22

Conceptos Basicos

Centro y Conjunto Difuso Normal. El centro de un conjunto difuso A se dene como Un conjunto difuso A es normal si su centro es no vaco, en otras palabras siempre podemos encontrar un punto x X tal que A (x) = 1. Punto de Cruce. Un punto de cruce de un conjunto difuso A es un punto x X en el cual A (x) = 0,5: cruce(A) = {x | A (x) = 0,5} el conjunto de todos los puntos x X tales que A (x) = 1 : Centro(A) = {x | A (x) = 1}.

Corte- y Corte Fuerte-. El corte- o conjunto de nivel- de un conjunto difuso A es un conjunto no difuso (clsico) denido por: A = {x | A (x) }. mientras que el corte fuerte- o conjunto fuerte de nivel- se dene como: A0 = {x | A (x) > }.

Conjunto Difuso Convexo. Un conjunto difuso A es convexo si slo si para cualesquiera vamente, A es convexo si todos sus conjuntos de nivel- son convexos. x1 , x2 y para cualquier [0, 1] , A (x1 + (1 )x2 ) m n{A (x1 ), A (x2 )}. Alternati-

su combinacin convexa x1 + (1 )x2 esta acotada en C, donde 0 1.

Un conjunto clsico C Rn es convexo si y slo si para cualesquiera dos puntos x1 , x2 C,

Nmeros Difusos. Un nmero difuso A es un conjunto difuso en R normal y convexo. Ancho de Banda de Conjuntos Difusos Normales y Convexos. Para un conjunto difuso normal y convexo el ancho de banda o ancho se dene como la distancia entre los dos nicos puntos de cruce. ancho de banda(A) =| x2 x1 |, donde A (x1 ) = A (x2 ) = 0,5 Simetra. Un conjunto difuso A es simtrico si su grado de pertenencia es simtrico alrededor de un cierto punto x = c, a saber, A (c + x) = A (c x) para toda x X. Abierto por la izquierda, Abierto por la derecha, Cerrado. Un conjunto difuso A es abierto por la izquierda si lim A (x) = 1 y lim A (x) = 0; es abierto por la derechax x+

si lim A (x) = 0 y lim A (x) = 1 y cerrado si lim A (x) = lim A (x) = 0.x x+ x x+

2.3 Conjuntos Difusos Operaciones Bsicas.

23

Subconjunto. Un conjunto difuso A esta contenido en un conjunto difuso B (o A es un subconjunto de B) si y slo si A (x) B (x) para toda x. Unin. La unin de dos conjuntos difusos A y B se dene como: AB = mx{(A (x), B (x))} = A (x) B (x) a Interseccin. La interseccin de dos conjuntos difusos A y B se dene de la siguiente manera: AB = m n{(A (x), B (x))} = A (x) B (x)_

Complemento. El complemento de un conjunto difuso A, se denota por A(A, NOT_ A) y se dene como: A (x) = 1 A (x).

Producto Cartesiano y Co-producto. Seas A y B los conjuntos difusos en X y Y, respectivamente. El producto cartesiano de A y B, denotado por A B, es un conjunto difuso con grado de pertenencia: AB (x, y) = m A (x), B (y)). n( De manera similar el Co-producto A+B es un conjunto difuso con grado de pertenencia: A+B (x, y) = mx(A (x), B (y)). a T-norma y T-conorma La interseccin de dos conjuntos difusos A y B es especicado por una funcin T :[0,1][0,1][0,1], la cual agrega dos funciones de membresa de la siguiente forma: AB (x) = T (A (x), B (x)) = A (x) B (x)

24

Conceptos Basicos

conoce como operadores T-norma (norma triangular) y reunen las siguientes propiedades. Denicin 2.17 T-Norma Un operador T-Norma satisface las siguientes propiedades: T (0, 0) = 0, T (a, 1) = T (1, a) = a T (a, b) T (c, d) si a c y b d T (a, b) = T (b, a) T (a, T (b, c)) = T (T (a, b), c) Denicin 2.18 T-conorma Un operador T-Conorma (o S-Norma) satisface las siguientes propiedades: S(1, 1) = 1, S(0, a) = S(a, 0) = a S(a, b) S(c, d) si a c y b d S(a, b) = S(b, a) S(a, S(b, c)) = S(S(a, b), c) (Acotado) (Monotonicidad) (Conmutatividad) (Asociatividad) (Acotado) (Monotonicidad) (Conmutatividad) (Asociatividad)

donde es un operador binario de la funcin T. A esta clase de operadores usualmente se les

(2.12)

(2.13)

Parametrizacin y Formulacin de la Funcin de Membresa. Un conjunto difuso es completamente caracterizado por su funcin de membresa (FM) o grado de pertenencia [49], ya que la mayora de los conjuntos difusos su universo X es la lnea real R, seria impractico listar todos los pares deniendo el grado de pertenencia [16]. Una forma de denir la funcin de membresa ms concreta y conveniente es expresarla como una formula matemtica. A continuacin se describen las clases de funciones de parametrizacin comnmente usadas para describir la funcin de membresa de una y dos dimensiones.

2.3 Conjuntos Difusos Funciones de Membresa.

25

FM Triangular. Esta es especicada por tres parmetros {a,b,c} de la forma siguiente: 0, xa , ba T riangulo(x; a, b, c) = c x, cb 0, xa axb bxc cx (2.14)

Los parmetros {a, b, c} (con a < b < c) determinan las coordenadas x de las tres esquinas de la FM triangular. FM Trapezoidal. Esta es especicada por cuatro parmetros {a, b, c, d} de la forma siguiente: 0, xa b a, T rapezoide(x; a, b, c, d) = 1, dx d c, 0, xa axb bxc cxd dx (2.15)

cuatro esquinas de la FM trapezoidal.

Los parmetros {a, b, c, d} (con a < b c < d) determinan las coordenadas x de las

FM Gausiana. Esta es especicada por dos parmetros {c, } de la siguiente forma: 1 xc 2 ( ) Gausiano(x; c, ) = e 2

(2.16)

Una funcin de membresa gausiana es determinada completamente por c y ; c representa el centro de la FM, mientras que representa el ancho de banda de la FM.

26

Conceptos Basicos FM de Campana Generalizada. Es especicada por tres parmetros {a, b, c}:

1 (2.17) x c 2b | 1+ | a donde el parmetro b es usualmente positivo (si b es negativo la forma de su FM es una Campana(x; a, b, c) = campana al revs). FM Sigmoidal. Se dene por: 1 , (2.18) 1 + exp[a(x c)] donde a controla la cuesta al punto de cruce x = c. Dependiendo del signo del parmetro Sig(x; a, c) = a, una sigmoidal FM es abierta por la derecha o abierta por la izquierda. FM Izquierda-Derecha o FM L-R. Es especicada por tres parmetros {, , c}: cx FL xc (2.19) LR(x; c, , ) = FR x c , xc FL (0) = FR (0) = 1 y l x FL (x) = l x FR (x) = 0. m m Operaciones Aritmticas con Nmeros Difusos. Un nmero triangular difuso puede ser parametrizado por una tripleta (a, b, c) donde la funcin de pertenencia de un nmero triangular difuso A esta denida por: 0, ua , ba A (u) = c u, cb 0, uc (2.20)

donde FL (x) y FR (x) son funciones montonicamente decrecientes denidas sobre [0,), con

2.4 Razonamiento Difuso

27

Las operaciones aritmticas entre nmeros difusos triangulares X y Y son denidas como sigue [20][6] : 1. Adicin de nmeros difusos triangulares . X Y = (ax , bx , cx ) (ay , by , cy ) = (ax + ay , bx + by , cx + cy ) 2. Sustraccin de nmeros difusos triangulares . X Y = (ax , bx , cx ) (ay , by , cy ) = (ax cy , bx by , cx ay ) 3. Multiplicacin de nmeros difusos triangulares . X Y = (ax , bx , cx ) (ay , by , cy ) = (ax ay , bx by , cx cy ) 4. Divisin de nmeros difusos triangulares . X Y = (ax , bx , cx ) (ay , by , cy ) = (ax /cy , bx /by , cx /ay ) (2.24) (2.23) (2.22) (2.21)

2.4.2.4.1.

Razonamiento DifusoPrincipio de Extensin.

El principio de extensin introducido por Zadeh [43] es un concepto bsico de la teora de conjuntos difusos que provee un procedimiento general para extender dominios clsicos de expresiones matemticas a dominios difusos. Sea f una funcin de X a Y y A es un conjunto difuso sobre X denido como: A = A (x1 )/x1 + A (x2 )/x2 + .... + A (xn )/xn . (2.25)

Luego, el principio de extensin establece que la imagen de un conjunto difuso A bajo el mapeo f (.) puede ser expresado como un conjunto difuso B,

28

Conceptos Basicos

B = f (A) = A (x1 )/y1 + A (x2 )/y2 + .... + A (xn )/yn

(2.26)

y = y es el mximo del grado de pertenencia de A con x = x1 y x = x2 , de donde tenemos que:

x1 6= x2 , tal que f (x1 ) = f (x2 ) = y , y Y. En este caso, el grado de pertenencia de B con

donde yi = f (xi ), i = 1, ..., n. Si f (.) es un mapeo de varios a uno, entonces existe x1 , x2 X,

B (y) = mx A (x). af (xi )=y

xi X

(2.27)

a un universo uno-dimensional Y tal que y = f (x1 , ..., xn ), y suponiendo que A1 , ..., An son conjuntos difusos en X1 , ..., Xn , respectivamente. entonces el principio de extensin arma que el conjunto difuso B inducido por el mapeo f es denido por:

Suponiendo que la funcin f es un mapeo de un espacio n-dimensional X1 X2 ... Xn

B = {(y, B (y)) | y = f (x1 , x2 , ..., xn ), (x1 , ..., xn ) X} , donde

(2.28)

B (y) =

(x1 ,x2, ...,xn )Xy=f (x1 ,x2 ,...,xn )

mx a

[m i Ai (xi )], i = 1, 2, . . . , n n

(2.29)

cual mapea cada elemento en X Y a un grado de pertenencia entre 0 y 1. Sean X y Y dos universos, entonces:

Relaciones Difusas. Las relaciones difusas binarias son conjuntos difusos en X Y el

R = {((x, y), R (x, y)) | (x, y) X Y } es una relacin difusa binaria en X Y.

(2.30)

2.4 Razonamiento Difuso

29

por:

Y Z, respectivamente. La composicin max-min de R1 y R2 es un conjunto difuso denido

Composicin Max-Min Sean R1 y R2 dos relaciones difusas denidas sobre X Y y

R1 R2 = {[(x, z), mx m R1 (x, y), R2 (y, z))] | x X, y Y, z Z}, a n(y

(2.31)

o equivalentemente,

R1 R2 (x, z) = mx m a n[(R1 (x, y), R2 (y, z)] = y [(R1 (x, y) R2 (y, z)]y

(2.32)

Composicin Max-Producto La composicin max-producto se dene como sigue: R1 R2 (x, z) = mx[(R1 (x, y)R2 (y, z)] ay

(2.33)

2.4.2.

Variables Lingsticas

Cuando una variable toma un nmero como su valor tenemos un marco matemtico de trabajo bien establecido para formularlo, pero cuando una variable toma una palabra como su valor no tenemos un marco de trabajo formal para formularlo en teora de matemtica clsica. Para proveer dicho marco de trabajo se introdujo el concepto de variable lingstica, hablando normalmente, si una variable puede tomar palabras en lenguaje natural como su valor se le llama variable lingstica, donde las palabras son caracterizadas por conjuntos difusos denidos en el universo en el cual la variable es denida. Una variable lingstica es caracterizada por una tupla (x, T (x), X, M) en la cual x es el nombre de la variable; T (x) es el conjunto de trminos de x, esto es, el conjunto de sus valores lingsticos o trminos lingsticos.; X es el universo en cuestin y M es una regla semntica la cual asocia a cada valor lingstico su signicado M(A), donde M(A) denota un conjunto difuso en X.

30 Ejemplo 2.1 Variables lingsticas y valores lingsticos.

Conceptos Basicos

Si la temperatura es interpretada como una variable lingstica, entonces el termino T(temperatura) ser:

T (x) = {calurosos, no caluroso, muy caluroso, no muy caluroso,..., templado, no templado,..., fro, no fro, muy fro, ms o menos fro, no muy fro,...} donde cada termino en T(temperatura) es caracterizado por un conjunto difuso del universo de discurso X=[0,45]. Normalmente usamos la temperatura es calurosa para denotar la asignacin del valor lingstico caluroso a la variable lingstica temperatura. Por otro lado, cuando la temperatura es interpretada como una variable numrica, usamos la expresin temperatura = 40 asignando el valor numrico 40 a la variable numrica temperatura. La regla semntica dene la funcin de membresa de cada valor lingstico en el conjunto de trminos. Del ejemplo anterior, podemos observar que el conjunto de trminos consiste de varios trminos primarios (caluroso, templado, fro) modicados por la negacin (no) y/o los modicadores lingsticos (muy, ms o menos, extremadamente, apenas,...). Aunque la palabra modicador no tiene un signicado denido en esencia acta como un intensicador. As damos la siguiente denicin para los dos modicadores ms comunes, muy y ms o menos. Denicin 2.19 Sea A un conjunto difuso en U , entonces muy_A es denido como un conjunto difuso en U con la funcin de membresa muy_A (x) = [A (x)]2 y ms_o_menos_A es un conjunto difuso en U con la funcin de membresa ms_o_menos_A (x) = [A (x)] 21

(2.34)

2.4 Razonamiento Difuso

31

Concentracin y Dilatacin de Valores Lingsticos. Sea A un valor lingstico caracterizado por un conjunto difuso con grado de pertenencia A (.). Entonces Ak es interpretado como una versin modicada del valor lingstico original expresado como: A =k

En particular la operacin de concentracin es denida como: CON(A) = A2 Mientras que la operacin de dilatacin es expresada por: DIL(A) = A0,5 (2.37) (2.36)

Z

k x [A (x)] /x

(2.35)

Intensicacin de Contrastes. La operacin de intensicacin de contrastes sobre un valor lingstico A es denido por: ( 2A2 , 2(A) ,2

INT (A) =

para 0,5 A (x) 1

para 0 A (x) 0,5;

(2.38)

La intensicacin de contrastes INT incrementa los valores de A (x) cuando estn arriba de 0.5 y disminuye aquellos que se encuentran abajo de este punto. Luego, la intensicacin de contrastes tiene la propiedad de reducir la difusividad de un valor lingstico A. Ortogonalidad. Un conjunto de trminos T = t1 , ..., tn de una variable lingstica x sobre el universo X es ortogonal si cumple la siguiente propiedad:n X i=1

ti (x) = 1, x X

(2.39)

donde los ti s son conjunto normales y convexos denidos sobre X y estos conjunto difusos hacen el conjunto de trminos T.

32

Conceptos Basicos

2.4.3.

Reglas Difusas Si-Entonces.

Una regla difusa Si-Entonces (tambin conocida como regla difusa, implicacin difusa o estatuto condicional difuso) asume la forma: Si x es A Entonces y es B (2.40)

Donde A y B son valores lingsticos denidos por conjuntos difusos sobre los universos X y Y respectivamente. A menudo x es A es llamado antecedente o premisa, mientras que y es B es llamado consecuencia o conclusin. Ejemplos de reglas difusas Si-Entonces son empleados en nuestras expresiones lingsticas diariamente, tales como las siguientes: Si la presin es alta Entonces el volumen es pequeo. Si la carretera esta resbaladiza Entonces manejar es peligroso. Si el jitomate esta rojo Entonces esta maduro. Si la velocidad es alta Entonces frenar poco a poco. Regla Composicional de Inferencia La regla composicional de inferencia es una generalizacin del siguiente procedimiento. Suponiendo que tenemos una curva y = f (x) que regula la relacin entre x y y. Cuando x = a, entonces a partir de y = f (x) podemos inferir que y = b = f (a); ver gura 2.6. Una generalizacin del proceso anterior mencionado permitir a a ser un intervalo y a f (x) ser una funcin intervalo-valor, como se muestra en la gura 2.7. Para encontrar el intervalo resultante y = b correspondiente al intervalo x = a, construimos primero una extensin cilndrica de a y encontramos su interseccin I con la curva del intervalo-valor. La proyeccin de I sobre el eje y nos proporciona el intervalo y = b. Yendo un paso adelante en nuestra cadena de generalizacin asumiendo que A0 es un conjunto difuso en X y Q es una relacin difusa en X Y . Formando de nuevo una extensin cilndrica A0E de A0 e interceptando con la relacin difusa Q (ver gura 2.8) obtenemos un

2.4 Razonamiento Difuso

33

y Y

f ( x)b

x X

Figura 2.6: Inriendo y = b de x = a y y = f (x)

y Y

I

b

f ( x)

aE x X

Figura 2.7: Inriendo el intervalo b del intervalo a y la funcin valor-intervalo f (x)

34y Y

Conceptos Basicos

BA E

Q

x X

AFigura 2.8: Inriendo el conjunto difuso B 0 del conjunto difuso A0 y la relacin difusa Q conjunto difuso A0E Q el cual es anlogo a la interseccin I en la gura 2.7. Entonces, Especcamente, dados A0 y Q (x, y) tenemos:

proyectando A0E Q en el eje-y obtenemos el conjunto difuso B 0 .

A0E (x, y) = A0 (x) y consecuentemente i h m A0E (x, y), Q (x, y) n A0E Q (x, y) = m A0 (x, y), Q (x, y) n n mxxX m A0 (x), Q (x, y) a B0 (y) = xX A0 (x) Q (x, y)

Finalmente obtenemos B 0 , la proyeccin de A0E Q en Y como

Usando la regla composicional de inferencia, podemos formalizar un procedimiento de inferencia sobre un conjunto de reglas difusas Si-Entonces. Este procedimiento de inferencia generalmente es llamado razonamiento aproximado o razonamiento difuso.

2.4 Razonamiento Difuso Razonamiento Difuso

35

Como en cualquier otra lgica, las reglas de inferencia de lgica difusa gobiernan la lgica difusa, se permite que ambas; premisas y conclusiones sean proposiciones difusas. deduccin de una proposicin q a partir de un conjunto de premisas {p1 , p2 , ..., pn } . En

Adems, ya que los resultados inferidos, usualmente deben ser traducidos en trminos ms signicativos (conjuntos difusos) por el uso de aproximacin lingstica, la conclusin nal obtenida a partir de las premisas p1 , p2 , ..., pn es, en general, una aproximacin en lugar de una consecuencia exacta de p1 , p2 , ..., pn . La regla bsica de inferencia en la lgica tradicional es el modus ponens, de acuerdo al cual podemos inferir la verdad de una proposicin B a partir de la veracidad de A y la El jitomate esta maduro, entonces si es verdad que El jitomate esta rojo esto implica que tambin es verdad que El jitomate esta maduro. Este concepto es ilustrado de la manera siguiente: Premisa 1 (Regla) Premisa 2 (Hecho) Conclusin: Si x es A Entonces y es B x es A y es B implicacin A B. Por ejemplo si A es identicado como El jitomate esta rojo y B con

Sin embargo, en gran parte del razonamiento humano, el modus ponens es empleado de una manera aproximada. Por ejemplo si tenemos la misma regla de implicacin y conocemos que El jitomate es ms o menos rojo podemos inferir que El jitomate esta ms o menos maduro. Esto es escrito como: Premisa 1 (Regla) Premisa 2 (Hecho) Conclusin: Si x es A Entonces y es B x es A0 y es B 0

Donde A0 es cercano a A y B 0 es cercano a B. Cuando A, B, A0 y B 0 son conjuntos difusos de universos apropiados, el procedimiento de inferencia anterior es llamado razonamiento

36

Conceptos Basicos

aproximado o razonamiento difuso, tambin llamado, modus ponens generalizado, ya que, este es un caso especial del modus ponens. Sean A, A0 y B conjunto difusos de X, X y Y, respectivamente. Asumiendo que la implicacin difusa A B es expresada como una relacin difusa R sobre X Y. Entonces el denido por: B0 (y) = o, equivalentemente, B 0 = A0 R = A0 (A B) (2.42) n[ mx x m A0 (x), R (x, y)] a x [A0 (x) R (x, y)], (2.41) conjunto difuso B inducido por x es A y la regla difusa Si x es A Entonces y es B es

Podemos usar el procedimiento de inferencia de razonamiento difuso para derivar conclusiones, sabiendo que la implicacin difusa A B es denida como una relacin difusa binaria.

2.5.

Conclusiones

En este capitulo denimos los conceptos bsicos de redes de Petri, redes neuronales, conjuntos difusos y razonamiento difuso. Una red de Petri se representa grcamente por un grafo dirigido bipartito. Los dos tipos de nodos, lugares y transiciones representan, las variables que denen el estado del sistema (lugares) y a sus transformadores (transiciones). Los lugares se representan por crculos, las transiciones por barras, estos son conectados por arcos que van de lugares a transiciones y de transiciones a lugares. La presencia o ausencia de una seal dentro de un lugar puede indicar cuando una condicin asociada con este lugar es verdadera o falsa. Por otro lado, las redes neuronales tienen caractersticas como: habilidad de aprendizaje, habilidad de procesamiento en paralelo y la propiedad de aproximar cualquier funcin suave. Las reglas de produccin difusas y el razonamiento difuso son la espina dorsal de los sistemas de inferencia difusos,

2.5 Conclusiones

37

los cuales son la herramienta de modelado ms importante basados en la teora de conjuntos difusos.

38

Conceptos Basicos

Captulo 3 Representacin de Conocimiento y Razonamiento con Redes de Petri DifusasLas reglas Si-Entonces son el formalismo ms popular para representar conocimiento. Estas tambin son llamadas reglas difusas (reglas que describen la relacin difusa entre dos proposiciones). Un conjunto entero de reglas de produccin es llamado una base de reglas. Adems al formalismo de reglas de produccin el sistema provee un signicado para denir los objetos referidos en las reglas de produccin, llamado declaracin de dominio. La base de reglas y la declaracin del dominio constituyen juntos una base de conocimiento (KB) del sistema difuso. En [22] las RdP son usadas para modelar bases de reglas, relacionando simplemente algunos de los elementos (funcin de marcado) y caractersticas (bsicamente lugares y transiciones) del formalismo de Petri con los elementos bsicos de una KB (proposiciones, grados de verdad e implicaciones). Cuando la complejidad de los sistemas KB incrementa, nuevos elementos son incluidos en la denicin inicial de RdP, los cuales permiten a la RdP representar adecuadamente los rasgos que caracterizan una KB. Este procedimiento nos lleva a la representacin de un nuevo modelo el cual es llamado red de Petri difusa (RPD). Las RdP

40

Representacin de Conocimiento y Razonamiento con Redes de Petri Difusas

tienen una cualidad inherente en representar lgica de una forma visual e intuitiva y las RPD toman todas estas ventajas de las RdP. De esta manera, la forma de razonamiento de un sistema experto puede ser reducido a simples rboles de nodos si algoritmos de razonamiento basados en RPD son empleados como mquinas de inferencia. Varias generalizaciones de las redes de Petri difusas han sido propuestas en la literatura sobre redes abstractas con el propsito de considerar ciertos problemas concretos vinculados con la representacin del conocimiento, razonamiento difuso y teora de decisin. Las redes de Petri difusas (RPD) fueron introducidas a la literatura como un modelo para representar sistemas basados en conocimiento. En [7] Chen, Ke y Chang proponen un algoritmo de razonamiento difuso, en el cual, el valor de verdad de un lugar objetivo puede ser evaluado a partir de un lugar inicial, siempre y cuando el lugar objetivo sea alcanzable a partir de el lugar inicial, Yeung y Tsang proponen en [47] un algoritmo de razonamiento difuso basado en grados de similaridad. Luego, las RPD son usadas para representar conocimiento difuso y razonamiento. Ya que, basados en el disparo de las transiciones de las RPD se pueden desarrollar algoritmos para inferir conocimiento. En este capitulo, representamos conocimiento utilizando redes de Petri difusas, adems utilizando nmeros difusos triangulares inferimos conocimiento mediante tres algoritmos de razonamiento difuso desarrollados en este capitulo.

3.1.

Representacin de Conocimiento.

A principios de los setentas, Alan Newell y Herb Simon introdujeron la nocin de sistemas de produccin en inteligencia articial [27] como un modelo psicolgico de comportamiento humano. En este modelo, parte del conocimiento es representado en unidades separadas llamadas producciones o reglas de produccin. Estas unidades contienen informacin concerniente a las acciones que una persona toma al percibir ciertos estmulos del medio ambiente. El modelo de Newell y Simon es parecido a la teora de memoria de dos procesos en psicologa cognoscitiva [24], donde dos diferentes mecanismos de almacenamiento de informacin sensorial son distinguidos: la memoria a corto plazo y la memoria a largo plazo,

3.1 Representacin de Conocimiento.

41

respectivamente. La memoria a corto plazo nicamente contiene una cantidad limitada de informacin rpidamente decadente. Esta corresponde a la parte de un sistema de produccin en el cual los datos de entrada y datos derivados son guardados. La memoria a largo plazo es para almacenamiento de informacin permanente y corresponde a las reglas base de un sistema de produccin en el cual las reglas de produccin son especicadas. Desde los aos setentas el formalismo de reglas de produccin ha sido empleado por algunos investigadores para desarrollar sistemas basados en conocimiento. En estos sistemas, el formalismo de reglas de produccin es visto meramente como un lenguaje formal para expresar conocimiento.

3.1.1.

Reglas de Produccin

Una de las propuestas ms populares para representacin de conocimiento es el uso de reglas de produccin, normalmente llamadas reglas SI-ENTONCES. Estas pueden tomar varias formas, por ejemplo:

Si condicin Entonces accin Si premisa Entonces conclusin Si p1 y p2 son verdaderas Entonces p3 es verdad donde p1 , p2 y p3 son proposiciones. Algunos de los benecios de las reglas Si-Entonces es que son modulares, cada regla dene una relativamente pequea y en principio independiente, pieza de conocimiento. Sean p =x esta en A y q = y esta en B dos proposiciones, donde A y B son conjuntos clsicos. p implica a q o Si p Entonces q signica que no puede ocurrir que p sea verdad y que q no lo sea. La interpretacin total de la regla de produccin Si p Entonces q es que, si la regla de produccin es verdad, entonces el grado de verdad de q es por lo menos el grado de verdad de p, esto es: Si p Entonces q es verdad (p) (q)

42

Representacin de Conocimiento y Razonamiento con Redes de Petri Difusas

Cuadro 3.1: Tabla de verdad

p q 1 1 0 1 0 0 1 0

Si p Entonces q 1 1 1 0

Entonces tenemos que: ( 1 si (p) (q)

Si p Entonces q =

0 de otra manera

de donde tenemos la Tabla 3.1. Claramente, el valor de verdad de las proposiciones p, q de estas reglas de produccin nicamente puede tomar valores 0 o 1.

3.1.2.

Reglas de Produccin Difusas

En muchas situaciones, puede ser difcil capturar datos en forma precisa. Una forma para representar propiamente el conocimiento del mundo real bajo la teora difusa, son las reglas de produccin difusas [16][28]. Las reglas de produccin difusas (RPDs) son usadas para representar conocimiento difuso, impreciso, conceptos vagos y ambiguos. Las RPDs son usualmente presentadas en la forma de una regla difusa SI-ENTONCES. Una regla de produccin difusa es una regla que describe la relacin difusa entre dos proposiciones. Sea siguiente manera: Ri la i-sima regla de produccin del conjunto R = {R1 , R2 , ...., Rn } , esta es denida de la

Ri : SI dj Entonces dk (CF = i ), T h, w Donde:

(3.1)

3.1 Representacin de Conocimiento.

43

Cuadro 3.2: Escalas de Verdad y sus Intervalos Numricos Escala de V erdad Siempre Verdadero Extremadamente Verdadero Muy Verdadero Considerablemente Verdadero Moderadamente Verdadero Mas o Menos Verdadero Minoritariamente Verdadero Minimamente Verdadero No Verdadero Intervalo Numrico e [1.0 1.0] [0.95 0.99] [0.80 0.94] [0.65 0.79] [0.45 0.64] [0.30 0.44] [0.10 0.29] [0.01 0.09] [0.00 0.00]

1. dj y dk son proposiciones las cuales son usualmente representadas de la siguiente forma: El (Atributo) de (Objeto) es (Valor) por ejemplo El precio del auto es alto. Se sugiere reemplazar El (Atributo) de (Objeto) por una variable. Esto es, el ejemplo mencionado anteriormente puede ser expresado como x es A, donde x es la variable que contiene El (Atributo) de (Objeto), y A es el valor de la variable x. Esto es, la ecuacin 3.1 quedara de la forma: Ri : SI x es A Entonces y es B (CF = i ), T h, w donde A y B son variables lingsticas denidos sobre los universos X y Y respectivamente. Las proposiciones pueden contener variables difusas. La verdad de cada proposicin es un nmero difuso denido en el universo [0,1]. Un ejemplo de escalas de verdad y sus correspondientes intervalos numricos est dado en la Tabla 3.2. 2. i es el valor del factor de certeza (CF), donde i esta denido en el universo [0, 1] Este representa el grado de certidumbre de la regla Ri .

44

Representacin de Conocimiento y Razonamiento con Redes de Petri DifusasP resion (U )Baja MediaM

AltaA

1

B

b1

b2 m1

b3 m2a1

1 m3a2

U a3

Figura 3.1: Funciones de membresa de presin baja, media y alta 3. T h es el valor frontera 4. w es el peso o grado de importancia de una regla de produccin. La anexin de pesos a las proposiciones es de gran importancia, ya que si existen varias proposiciones antecedentes que conlleven a una consecuente, estas proposiciones la mayora de las veces dieren en importancia, afectando el valor de verdad de la proposicin consecuente. El grado de importancia que se adhiera a cada proposicin lo vamos a conocer como peso de la proposicin. Las funcin de membresa del conjunto difuso A (presin alta), es ilustrada en la gura o 3.1 en la cual la presin alta es representada por un nmero difuso triangular (a1 , a2 , a3 ) de la misma forma la presin baja y media son representadas por nmeros difusos triangulares (b1 , b2 , b3 ) y (m1 , m2 , m3 ) respectivamente. En general las reglas de produccin difusas pueden ser categorizadas en 4 tipos los cuales se denen como sigue: Tipo 1. Ri : SI d1 Entonces d2 (CF = i ), T hi = i (3.2)

3.2 Representacin de Conocimiento con Redes de Petri Difusas. Tipo 2. Ri : SI d1 Y d2 Y, .., Y dn Entonces dz (CF = i ), w1 , .., wjn , T hi = i Tipo 3. Ri : SI da Entonces dk1 Y dk2 Y, .., Y dkj (CF = k1 , .., kj ), T h = 1 , .., j Tipo 4. Ri : SI d1 O d2 O, .., O dj Entonces dz (CF = 1 , .., j ), T h = 1 , .., j .

45

(3.3)

(3.4)

(3.5)

3.2.

Representacin de Conocimiento con Redes de Petri Difusas.

Es posible usar un modelo de redes de Petri para representar reglas de produccin [30]. Una red de Petri se representa grcamente por un grafo dirigido bipartito. Los dos tipos de nodos, lugares y transiciones representan, las variables que denen el estado del sistema (lugares) y a sus transformadores (transiciones). Los lugares se representan por crculos, las transiciones por barras. Cada lugar en una red de Petri difusa puede contener o no una seal asociada con un valor de verdad el cual se encuentra denido en el universo [0,1]. Cada transicin en una red de Petri es asociada con un valor denominado factor de certeza el cual tambin se encuentra denido en el universo [0,1]. En una red de Petri difusa, las relaciones de lugares a transiciones y de transiciones a lugares son representadas por arcos dirigidos. La estructura de una red de Petri difusa generalizada se dene a continuacin. Denicin 3.1 (Red de Petri Difusa) Una red de Petri difusa (RPD) se dene como un tuplo RP D = (P, T, D, I, O, f, , ) donde: P Es un conjunto nito y no vaco de lugares; T Es un conjunto nito y no vaco de transiciones;

46

Representacin de Conocimiento y Razonamiento con Redes de Petri Difusasdj

i i

dk

pj

pk

Figura 3.2: Red de Petri de una regla de produccin difusa. D Es un conjunto nito y no vaco de proposiciones; I Es una funcin de entrada, I : T P ; f Es una funcin que asigna a cada transicin un nmero difuso en el universo [0,1]. [0,1]; Es una funcin que asocia a cada lugar un nmero difuso en el universo [0,1] : P O Es una funcin de salida, O : T P ;

Es una funcin que asocia a un lugar pi una proposicin di . Denicin 3.2 (Red de Petri difusa con Pesos) Una red de Petri Difusa con Pesos (RPDP) se dene como un tuplo RP DP = (P, T, D, T h, I, O, W, F, f, , , , ) donde: P, T, D, I, O, f, , . se denen de igual forma que en la denicin anterior W = {w1 , w2 , . . . , wr }es un conjunto nito de pesos F = {f1 , f2 , . . . , fs } conjunto de conjuntos difusos T h = {1 , 2 , . . . , n } conjunto nito de valores frontera

es una funcin que asigna a cada transicin un valor frontera i es una funcin que asigna a cada lugar un peso, : P W Sean pj y pk lugares y ti una transicin. Si pj I(ti ), entonces existe un arco dirigido

que va del lugar pj a la transicin ti . Si pk O(ti ),entonces existe un arco dirigido que va de la transicin ti al lugar pk . Si f (ti ) = i , donde i es un nmero difuso denido en el universo [0, 1] , entonces la transicin ti se dice que esta asociada con un nmero difuso i . Si di . (pi ) = di donde di D, entonces el lugar pi se dice que esta asociado con una proposicin

3.2 Representacin de Conocimiento con Redes de Petri Difusas.

47

i d1i

w1

d1

i

d2

w2

d2

dZ

iwjdj

(a)

(b)

k1

d k11

d1

k1 1 k 2

da

k 2 kj 2

dk 2

d2

2dj

dZ

kj j

d kj j

(c )

(d )

Figura 3.3: Redes de Petri de las principales reglas de produccin difusas.

48

Representacin de Conocimiento y Razonamiento con Redes de Petri Difusas Si una RPD contiene algunas seales en algunos lugares, entonces es llamada red de Petri

difusa marcada, donde una seal en el lugar pi esta representada por un punto etiquetado(pi )

nmero difuso. Si (pi ) = yi , donde yi es un nmero difuso y (pi ) = di . entonces el valor de verdad de la proposicin di es yi . Si W (pi ) = wi donde wi es un nmero difuso denido en el universo [0,1] y (pi ) = di , entonces el lugar pi se dice que esta asociado con el peso wi indicando el peso de la proposicin di . Si una RPDP contiene algunas seales en algunos lugares, entonces es llamada red de Petri difusa con pesos marcada. Una transicin ti dispara removiendo las seales de los lugares de entrada y depositando una seal dentro de cada lugar de salida. El disparo de las reglas de produccin difusas puede ser considerado como disparo de transiciones. Podemos usar redes de Petri difusas para representar reglas de produccin difusas de

y el valor de la seal en el lugar pi , pi P esta denotado por (pi ), donde (pi ) es un

una base de reglas. Por ejemplo, la regla de produccin difusa de la ecuacin 3.1 puede ser modelada por una red de Petri difusa, como lo muestra la gura 3.2, donde i es el valor de factor de certeza (CF) el cual indica el grado de certeza de la regla Ri , y i esta denido en el universo [0,1]. Si la porcin antecedente o consecuente de una regla de produccin difusa contiene conectores AND o OR(Y o O), entonces esta es llamada una regla de produccin difusa compuesta. Cualquier regla de produccin difusa compuesta pueden ser incluida dentro de los cuatro tipos de reglas de produccin difusas denidos en ecs. (3.2), (3.3), (3.4) y (3.5) y estas a su vez pueden ser modeladas por redes de Petri difusas como lo muestran las guras [3.3(a)], [3.3(b)], [3.3(c)] y [3.3(d)] respectivamente. Ejemplo Suponiendo que deseamos vericar la calidad de los engranes de una fresa, los productos mal maquinados son rechazados o enviados a un proceso de remaquinado. Las propiedades en que se basan para determinar la calidad de tales engranes son nicamente tolerancia y acabado y mediante estas dos propiedades clasica a los engranes en las cuatro clases

3.2 Representacin de Conocimiento con Redes de Petri Difusas. siguientes:

49

1. Clase A. Si dimetro interior y exterior estn dentro de la tolerancia permitida y adems el engrane tiene un buen acabado. 2. Clase B. Si el dimetro interior y exterior esta dentro de la tolerancia permitida y el engrane tiene un mal acabado. 3. Clase C. Si el dimetro interior esta dentro de la tolerancia, el dimetro exterior sobrepasa la tolerancia o si el dimetro exterior esta dentro de la tolerancia, el dimetro interior sobrepasa la tolerancia o si el dimetro interior y exterior sobrepasan la tolerancia y tiene un mal acabado o un buen acabado. 4. Clase D. Si el dimetro interior o exterior es menor que la tolerancia. Suponiendo que la tolerancia permitida para el dimetro interior y dimetro exterior es de 0,03125,, entonces tenemos las apreciaciones siguientes: 1. 2. 3. 4. 5. 6. A = (DIR DIP = 0,03125) A0 = (DER DEP = 0,03125) B = (DIR DIP > 0,03125) B0 = (DER DEP > 0,03125) C = (DIR DIP < 0,03125) C0 = (DER DEP < 0,03125)

Donde DIR es el dimetro interior real o dimetro interior de la pieza maquinada y DIP es el dimetro interior pretendido, de la misma forma DER es el dimetro exterior real dimetro exterior de la pieza maquinada y DEP es el dimetro exterior pretendido. Una vez tomadas en cuenta estas apreciaciones, mediante las siguientes reglas se modela el proceso de seleccin de calidad de engranes.R1 :IF DI=A and DE=A0 THEN TOL=Acep-A R2 :IF DI=A and DE=B0 THEN TOL=Acep-B

50DI= A

Representacin de Conocimiento y Razonamiento con Redes de Petri DifusasDE= A DE= C DI= B VC= AP VA= AP VA= MNA A VC= MY

DI= C

VC= MNA

T OL= NA ACAB= MA ACAB= BA T OL = ACEPT -A T OL= ACEPT -B

CLAS S-A

CLAS S-B

CLAS S-D

CLAS S-C

Figura 3.4: Red de Petri Difusa del proceso de inspeccin.R3 :IF DI=A and DE=C0 THEN TOL=NA R4 :IF DI=B and DE=A0 THEN TOL=Acep-B R5 :IF DI=B and DE=B0 THEN TOL=Acep-B R6 :IF DI=B and DE=C0 THEN TOL=NA R7 :IF DI=C R8 :IF DI=C R9 :IF DI=C THEN TOL=NA THEN TOL=NA THEN TOL=NA

R10 :IF VC=AP and VA=AP THEN Acab=BA R11 :IF VC=AP and VA=MNA THEN Acab=BA R12 :IF VC= AP and VA= MYA THEN Acab=MA R13 :IF VC= MNA R14 :IF VC= MNA R15 :IF VC= MNA THEN Acab=MA THEN Acab=MA THEN Acab=MA

R16 :IF VC= MYA and VA=AP THEN Acab=BA R17 :IF VC= MYA and VA=MNA THEN Acab=BA

3.3 Razonamiento con Redes de Petri DifusasR18 :IF VC= MYA and VA=MYA THEN Acab=MA R19 :IF TOL=Acep-A and Acab=BA THEN RI=TA R20 :IF TOL=Acep-A and Acab=MA THEN RI=TB R21 :IF TOL=Acep-B and Acab=BA THEN RI=TC R22 :IF TOL=Acep-B and Acab=MA THEN RI=TC R23 :IF TOL= NA and Acab=BA THEN RI=TD R24 :IF TOL= NA and Acab=MA THEN RI=TD

51

Mediante las reglas de produccin anteriores y basndonos en las cuatro reglas de produccin bsicas podemos modelar la red de Petri (ver gura 3.4).

3.3.

Razonamiento con Redes de Petri Difusas

Por muchos aos, uno de los tpicos de investigacin de inteligencia articial (IA) ha sido el desarrollo de notacin lo sucientemente precisa para representacin de conocimiento y razonamiento. Varios algoritmos de razonamiento difuso han sido propuestos por diversos autores en [48] Yeung y Tsang proponen un algoritmo de razonamiento difuso basado en grados de similaridad usando redes de Petri difusas, sin embargo, los factores de certeza de las reglas de produccin difusas y los pesos de las proposiciones estn restringidos y estos son representados por valores reales entre cero y uno. En [7] Chen, Ke y Chang proponen un algoritmo de razonamiento difuso, en el cual, el valor de verdad de un lugar objetivo puede ser evaluado a partir de un lugar inicial, siempre y cuando el lugar objetivo sea alcanzable a partir de el lugar inicial. En [5] Chen presenta un algoritmo de razonamiento difuso hacia atrs, en l, el valor de verdad de cualquier lugar objetivo puede ser evaluado, elaborando un rbol de nodos con los lugares alcanzables e inmediatamente alcanzables hacia atrs a partir del lugar objetivo hasta llegar a un conjunto de lugares iniciales. Una vez construido el rbol de nodos se pide al usuario introduzca los valores de verdad de los lugares iniciales y con ellos se calcula el valor de verdad del lugar objetivo. En [6] Chen perfecciona su algoritmo asociando pesos a los lugares. Aun ms, los valores de verdad asociados a las proposiciones ya no estn restringidos a valores entre cero y uno, Estos son representados por nmeros

52

Representacin de Conocimiento y Razonamiento con Redes de Petri Difusas

difusos. En [42] se introducen las redes de Petri adaptativas, las cuales adems de contar con las propiedades de las redes de Petri poseen la habilidad de aprender como las redes neuronales. En esta seccin se estudian las caractersticas principales de tres algoritmos de razonamiento difuso, tcnicas de razonamiento as como las ventajas y desventajas de cada algoritmo.

3.3.1.

Algoritmo de Razonamiento Hacia atrs (RDHAP).

El algoritmo de razonamiento difuso hacia atrs fue propuesto en [5]. Este algoritmo puede realizar razonamiento difuso hacia atrs para evaluar el grado de verdad de cualquier proposicin especicada por el usuario. Sin embargo, las tcnicas de evaluacin empleadas por Chen pueden llegar a dar resultados inconclusos, ya que el grado de verdad de las proposiciones consecuentes es evaluado multiplicando el grado de verdad mx m de las a n proposiciones antecedentes por el factor de certeza de la regla. El producto puede llegar a ser muy pequeo cuando existen varios niveles de razonamiento. Cuando se compara un valor de verdad consecuente con su valor frontera, el valor de verdad puede llegar a ser ms pequeo que el valor frontera y entonces provocar un resultado inconcluso. Adems en el algoritmo propuesto por Chen las reglas de produccin no tienen asociados pesos a sus proposiciones y los valores que maneja tanto en valores de verdad, factores de certeza y valores frontera son valores reales denidos en [0,1] y no nmeros difusos. El algoritmo que presentamos puede realizar razonamiento difuso hacia atrs para evaluar el grado de verdad de cualquier proposicin especicada por el usuario. Asumiendo que deseamos conocer el valor de verdad de la proposicin ds , en este caso el lugar ps es llamado el lugar objetivo. El algoritmo puede realizar razonamiento difuso hacia atrs generando un grafo Y-O y preguntando al usuario el grado de verdad de otras proposiciones las cuales pueden inferir en el grado de verdad de la proposicin ds . El algoritmo de razonamiento difuso hacia atrs es expresado por una grafo difuso Y-O. Cada nodo en el grafo lo denotaremos por inmediatamente alcanzables hacia atrs a partir de pk , (pk ) denota el grado de verdad una tripleta (pk ,CIAA (pk ),(pk )), donde pk P, CIAA(pk ) denota el conjunto de lugares

3.3 Razonamiento con Redes de Petri Difusas

53

de la proposicin dk , donde (pk ) es un nmero difuso denido en el universo [0,1]. Sea CFxy el factor de certeza asociado a la transicin que se encuentra entre los lugares px y py . Asumiendo que un nmero triangular difuso puede ser parametrizado por una tripleta (a, b, c) donde la funcin de pertenencia de un nmero triangular difuso A esta denida por las ecuaciones (2.14) y (2.20). Tcnicas de Razonamiento Difuso. Los tipos de reglas que usaremos en este algoritmo, as como el calculo del valor de verdad de las proposiciones son mostradas a continuacin: Tipo 1. Ri : SI d1 Entonces d2 (CF = i ) (3.6)

Asumiendo que el valor de i as como el valor de verdad de d1 y d2 son nmeros difusos triangulares, esto es, i = (ai , bi , ci ), (d1 ) = (ad1 , bd1 , cd1 ). Entonces, el valor de verdad de la proposicin d2 puede ser evaluado y este es igual a: ad2 = ad1 ai

(d2 ) = (ad2 , bd2 , cd2 ) donde : bd2 = bd1 bi

(3.7)

cd2 = cd1 ci

El proceso de razonamiento de este tipo de regla puede ser modelado por una red de Petri difusa marcada como lo muestra la gura 3.5 (a) y (b). Tipo 2. Ri : SI d1 Y d2 Y, .., Y dj Entonces dz (CF = i ), w1 , w2 , .., wj (3.8)

Asumiendo que w1, w2 , . . . , wj son los pesos asociados a las proposiciones d1 , d2 , . . . , dj , donde wi = (awi , bwi , cwi ) y estos son nmeros triangulares difusos, (d1 ), (d2 ), . . . , (dj ) son los valores de verdad de las proposiciones d1 , d2 , . . . , dj . Entonces el valor de verdad de la proposicin dz puede ser calculado basados en [20] y este es igual a:

54

Representacin de Conocimiento y Razonamiento con Redes de Petri Difusas

(P1 , CIAA ( P ), (P1)) 1

i d1i (a )

CF12

d2( P , CIAA (P2 ), - - ) 2

(b )

w1

d1

( P , CIAA ( Pz ), - - ) zi

w2

d2

dZ

CF {1,2,...,j}z

i( P , CIAA ( P ), (P1 )) 1 1

CF {1,2,...,j}z(P2 , CIAA ( P ),a ( P2 )) 2

CF {1,2,...,j}z( P , CIAA ( Pj ), a (Pj )) j

wj

dj

(c )

(d )

k1

dk11(P , a CIAA ( P ), (P )) a a

da

k 2 kj 2

dk 2

d kj j

CFak1 ( P , CIAA(P k1), - - ) k1

CFak2(Pk2 ,CIAA ( P ), k2(f)

CFakj

-

)

( Pkj , CIAA ( Pkj ),

- -)

(e )

d1

k1 1 k 2( Pz , CIAA ( Pz ), - - )

d2

2dj

dZ

kj j( g)

CFp1z( P , CIAA ( P ), ( P )) 1 1 1

CFp2 z( P2 , CIAA ( P ), a ( P2 )) 2

CFp j z( P , CIAA ( Pj ), a ( Pj )) j

(h )

Figura 3.5: Representacin de las reglas de produccin difusas.

3.3 Razonamiento con Redes de Petri Difusas

55

n

El proceso de razonamiento de este tipo de regla puede ser modelado por una red de Petri difusa marcada como lo muestra la gura 3.5 (c) y (d). Tipo 3. Ri : SI da Entonces dk1 Y dk2 Y, .., Y dkj (CF = k1 , .., kj ), T h = 1 , .., j (3.10)

j=1 adz = ai n (cwj ) n j=1 (bd bwj ) j=1 j (dz ) = (adz , bdz , cdz ) donde: bdz = n bi (bwj ) n j=1 (cdj cwj ) j=1 cdz = n ci (awj )j=1

(adj awj )

(3.9)

Asumimos que (da ) es el valor de verdad de la proposicin da . Entonces el valor de verdad de las proposiciones dk1 , dk2 ,...dkj puede ser calculado basados en [20] y este es igual a: adk1 = ada ak1 , bdk1 = bda bk1 , cdk1 = cda ck1

adk2 = ada ak2 , bdk2 = bda bk2 , cdk2 = cda ck2 (dkj ) = (adkj , bdkj , cdkj ) donde : . . . adkn = ada akn , bdkn = bda bkn , cdkn = cda ckn (3.11) El proceso de razonamiento de este tipo de regla puede ser modelado por una red de Petri difusa marcada como lo muestra la gura 3.5 (e) y (f). Tipo 4. Ri : SI d1 O d2 O, .., O dj Entonces dz (CF = 1 , .., j ), T h = 1 , .., j . (3.12)

56

Representacin de Conocimiento y Razonamiento con Redes de Petri Difusas Asumiendo que (d1 ), (d2 ), ..., (dj ) son los valores de verdad de las proposiciones

d1 , d2 , .., dj , CF1 ,CF2 , ..,CFj son los factores de certeza asociados a las transiciones, entonces el valor de verdad de la proposicin dz puede ser calculado y este es igual a: n

El proceso de razonamiento de este tipo de regla puede ser modelado por una red de Petri difusa marcada como lo muestran las guras 3.5 (g) y 3.5 (h). Algoritmo de Razonamiento Difuso Hacia Atrs. ENTRADA: la proposicin objetivo dj . SALIDA: el valor de verdad de la proposicin dj . Paso 1. Marcar el nodo raz (pj , CIAA(pj ), ) como un nodo no terminal, donde: pj es el lugar objetivo CIAA(pj ) es el conjunto de lugares inmediatamente alcanzable hacia atrs de pj . el smbolo denota que el valor de verdad de la proposicin dj es desconocido. Paso 2. Se selecciona un nodo no terminal (pi , CIAA(pi ), ). Si CIAA(pi ) = , Entonces se marca el nodo como nodo terminal. De otra manera, Si CIAA(pi ) = {pw , ..., {pa , pb , ..., pk }, ..., pz , ..} Entonces se incrementa el grafo Y-O como en la gu-

j=1 adz = n (cj ) n j=1 (bdj bj ) j=1 (dz ) = (adz , bdz , cdz ) donde: bdk = n (bj ) n j=1 (cdj cj ) j=1 cdk = n (aj )j=1

(adj aj )

(3.13)

ra 3.6, donde CFwi = (awi , bwi , cwi ) denota el valor del factor de certeza asociado a la

3.3 Razonamiento con Redes de Petri Difusas( Pi , {pw ,...., {p a , pb ,.., pk },...., pz ,...}, - - )

57

CFpw pi

CF{pa pk }pi( Pa , CIAA ( Pa ), - - ) ( Pb , CIAA ( Pb ), - - )

CFpz pi( Pk , CIAA ( Pk ), - - )

( Pw , CIAA ( P ), - - ) w

( Pz , CIAA ( Pz ), - - )

Figura 3.6: Grafo AND-OR. transicin que se encuentra entre los lugares pw y pi , CF{a,b,..,k}i denota el valor del factor de certeza asociado a la transicin que se encuentra entre los lugares {pa , pb , .., pk } y pi . Paso 3. Si no existe un nodo no terminal Entonces ir al paso 4 de otra manera ir al paso 2. Paso 4. Para cada nodo terminal (ps , , ) en el grafo difuso generado Y-O, preguntar al usuario el valor de ys = (as , bs , cs ) que es el valor de verdad de la proposicin ds . Paso 5. Evaluar el valor de (pk ) para cada nodo no terminal (pk , CIAA(pk ), (pk )) en el grafo difuso generado Y-O basado en los tipos de reglas expuestas anteriormente.

Ejemplos: Ejemplo 3.1 Veamos el siguiente ejemplo, el cual fue presentado en [42]. Sean d1 , d2 , d3 , d4 , d5 y d6 seis proposiciones, entre las cuales existen las siguientes reglas de produccin difusas con pesos: R1 :SI d1 Entonces d4 (1 ) R2 :SI d2 Y d4 Entonces d5 (w2 , w4 , 3 ) R3 :SI d3 O d5 Entonces d6 (2 , 4 )

58

Representacin de Conocimiento y Razonamiento con Redes de Petri Difusast1 , 1

p1

1

p4

w4

t3 , 3

3

t4 , 4p5

4p6

p2

w22t2 , 2

p3

Figura 3.7: Red de Petri que representa las reglas de produccin del Ejemplo 3.1. Estas reglas de produccin pueden ser representadas por una red de Petri como se muestra en la gura 3.7, donde P={p1 , p2 , p 3 , p4 , p5 , p6 }, T= {t1 , t2 , t3 , t4 }, D={d1 , d2 , d3 , d4 , d5 ,d6 }, proposiciones consecuentes, los datos son dados como: WI = {w2 , w4 }, WO = {1 , 2 , 3 , 4 }. Con tres proposiciones de entrada (p1 , p2 , p 3 ) y tres

1 =0.70 0.80 0.90

2 =0.65 0.75 0.85

3 =0.75 0.85 0.95 4 =0.72 0.82 0.92

w2 =0.27 0.37 0.47 w4 =0.53 0.63 0.73. Asumiendo que deseamos conocer el valor de verdad de la proposicin p5 empleamos el a