Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
El lenguaje de programación borrosa XL Rafael Morales-Bueno José-Luis Pérez-de-la-Cruz Dpto. Lenguajes y Ciencias de la Computación Dpto. Lenguajes y Ciencias de la Computación Facultad de Informática Facultad de Informática Universidad de Málaga Universidad de Málaga e-mail: morales@tecma1.ctima.uma.es e-mail: cruz@tecma1.ctima.uma.es Ricardo Conejo Buenaventura Clares Dpto. Lenguajes y Ciencias de la Computación Dpto. Lenguajes y Sistemas Informáticos Facultad de Informática Facultad de Ciencias Universidad de Málaga Universidad de Granada e-mail: conejo@tecma1.ctima.uma.es Resumen En esta comunicación definimos un nuevo lenguaje de programación borrosa llamado XL. XL se obtiene del lenguaje de programación borrosa L extendiendo su sintaxis y su semántica con una sentencia de bucle indefinido (while). Desarrollamos algunos ejemplos y en particular describimos en este lenguaje una regla de control borroso. Palabras Clave: lenguajes de programación, control borroso, conjuntos borrosos. 1 Introducción En [7] definimos el lenguaje de programación L. Este lenguaje tiene un reducido conjunto de instrucciones y una sola instrucción de bucle definido de la forma repeat Xi times ... semit. En 2.1 hacemos una breve descripción de L. El objetivo central de esta comunicación es definir un lenguaje para mejorar la potencia expresiva de L permitiendo una instrucción de bucle indefinido (while). El lenguaje resultante se denominará XL. Como se menciona en [7], la principal característica de L (o XL) en relación con otros lenguajes de programación borrosa (por ejemplo, L.P.L [1], [2]; FRIL[3]) es su simpli- cidad. Tiene un conjunto reducido de instrucciones y un solo tipo de datos. En principio L y XL están diseñados como lenguajes de propósito general. En la sección 3 definimos el lenguaje XL y mostramos algunos ejemplos; en concreto, uno de ellos es la descripción en nuestro lenguaje de una regla de control borroso. Por último, en la sección 4 reseñamos algunas conclusiones generales y trabajos futuros relacionados con la calculabilidad borrosa y los lenguajes de programación borrosa. 2 Notación y resultados previos En el desarrollo que sigue, consideraremos que los grados se evalúan en un semianillo ordenado finito W ({l0, ..., lr}, ⊕, ⊗, ≤), siendo las operaciones calculables y el orden decidible [12]. Supondremos que los elementos neutros son l0 para ⊕ y lr para ⊗. Usaremos W-conjuntos sobre (Z+)n, n≥1, con la representación estandar: A = µA(a) / a + ... + µA(z) / z. Si a = (a1, ..., an)∈(Z+)n entonces πi representa la i- proyección πi(a) = ai Sean U y V conjuntos. Una W-función f de U a V es una función de UxV en W. Si f(u,v)=µ, entonces decimos que el valor de la W-función f en u es v con grado µ. 2.1 Una reseña del lenguaje L El lenguaje L opera sobre datos que son subconjuntos borrosos de (Z+)n. Hay dos instrucciones de asignación nítida (X:=0, X:=suc(Y) ) y una instrucción de asignación borrosa. La única estructura de control es un bucle tipo "FOR"; la instrucción de control condicional "IF" se puede programar en términos de asignaciones y bucles "FOR" . Debido a entradas borrosas o asignaciones borrosas, el programa puede alcanzar un punto a partir del cual cada instrucción debe ejecutarse de manera borrosa. Esto es especialmente importante al considerar estructuras repetitivas o condicionales. Cuando acaba la ejecución se obtiene un conjunto de salidas cada una con su grado. Es decir, el programa produce como salida un conjunto borroso. La ejecución de un programa nítido se puede ver como la generación de una sucesión de “configuraciones nítidas”. Cada configuración representa el valor de cada variable del programa. En el caso de programas en L, la sucesión no es única; a partir de cierto punto, hay varias ramas de cálculo cada una con su grado. De esta forma, las configuraciones generadas por la ejecución de un programa en L son subconjuntos borrosos de “configuraciones nítidas”. En lo que sigue usaremos el término “elemento de la configuración” para referirnos a estas “configuraciones nítidas”. El significado de un programa en L está definido en [7] mediante una semántica operacional, esto es, viendo el programa como un dispositivo que calcula una función. Cada programa en L tiene dos conjuntos de variables distinguidas - variables de entrada y variables de salida- y calcula una W-función de las variables de entrada en las variables de salida. Ejemplo 1. El siguiente programa calcula, para un número natural n, el W-conjunto que se puede considerar “previo” a n. El concepto de previo es dependiente del contexto, y esto se refleja en la elección de la W-función para FUZZ1 en la asignación borrosa. Programa previous P = (1,1,Q) PREV; begin X2:=X1; repeat X2 times X1:= FUZZ1(X3); X3:=suc(X3) semit end. Vemos como un programa se define como una terna, número de variables de entrada (en este caso, una: X1), número de variables de salida (en este caso, una: X1) y el código. Este código tiene un identificador y la parte ejecutable está parentizada entre begin y end. 3 El lenguaje XL 3.1 Presentación del lenguaje XL El lenguaje XL se obtiene añadiendo una estructura de bucle indefinido al lenguaje L de la sección anterior. La condición de control es del tipo x_0. La variable x, como es habitual, se denomina variable de control del bucle. Sea Xr la variable de control del bucle. Para cada elemento en la configuración con Xr_0, el cuerpo del bucle se ejecuta una vez. Los resultados se agrupan con los elementos de la configuración de partida con Xr=0, formando una configuración intermedia. Este proceso se repite hasta que todos los elementos en la configuración tengan valor de Xr=0. Si una tal configuración no se alcanza, el proceso continua indefinidamente. Más formalmente, sea P un programa en XL que usa k variables. La configuración en un instante de la ejecución del mismo viene dada por un conjunto borroso C en (Z+)k, donde cada elemento de la configuración es un vector de la forma b=(b1, b2, ..., bk) que representa el contenido actual de cada una de las k variables y su grado asociado, µC(b) es el grado con que se ha alcanzado ese elemento de la configuración. Supongamos que C es la configuración alcanzada antes de ejecutar un bucle indefinido con variable de control Xr. Para cada elemento b, µC(b)=α , cumpliendo πr(b)_0 (esto es Xr_0), se ejecuta el bucle indefinido que partiendo de α/b produce la configuración B1b. Como C=_ (α/b), la configuración obtenida tras esta primera ejecución es B1= B1 b b � = B10∪B11 donde B10=_(β/b) con πr(b)=0 esto es, la configuración formada por los elementos b de la configuración de partida C en los que πr(b)=0, junto con los nuevos elementos obtenidos cuya componente r también es 0; para todos ellos el bucle no se vuelve a ejecutar y B11= _(β/b) con πr(b)_0 que es la parte de la configuración obtenida, cuyos elementos tienen en la componente r un valor no nulo. Para los elementos de B11 el bucle se vuelve a ejecutar, obteniendose como resultado la configuración B2. De manera similar a la primera ejecución, B2= B20∪B21 donde B20 = _ ( β/b) con πr(b)=0 donde está incluido B10 y B21 = _ ( β/b) with πr(b)_0, Repitiendo este proceso se pueden dar dos casos: a) En un número finito de pasos alcanzamos una configuración B tal que B=B0, esto es, para todo b con µB(b)_0 se verifica que πr(b)=0. Entonces, el bucle acaba y desde la configuración C alcanzamos la configuración B. b) Una tal configuración B nunca se alcanza. En este caso el programa calcula indefinidamente. Nótese que esta instrucción “while” borrosa, cuando se usa con datos nítidos, se comporta como un bucle indefinido nítido. Por otra parte, con unacondición de control de bucle de la forma Xr_0 se puede representar cualquier otra, haciendo uso de la suma, el predecesor (pred) y la resta definida en Z+ (x-y= 0 si x<y). Una condición C de la forma X<Y se puede representar mediante la expresión E dada por (Y-X)- pred(Y-X), que toma el valor 1 si la condición se cumple y 0 en caso contrario. Sean dos condiciones C1 y C2 representadas por expresiones E1 y E2. Entonces, la expresión para C1∧C2 es pred(E1 + E2) y la expresión para C1∨C2 es (E1 + E2) - pred(E1 + E2), y para ¬C1 es 1-E1. Ahora a partir de la expresión para X<Y tenemos expresiones para X_Y (X<Y ∨ Y<X), para X=Y (¬(X_Y)), etc.; y combinando estas podemos tener cualquier tipo de condición relativa a mas de dos variables. Mas precisamente, sea un bucle de la forma while C(X1, X2,..., Xk) do S od y sea E es la expresión asociada a la condición C. Entonces el bucle se expresa en nuestro lenguaje mediante: Xk+1 := E; while Xk+1 _0 do S; Xk+1 := E od 3.2 W-función calculada por un programa En [7] se demostró que cada programa en L define una W-función total, en el sentido de que para cada configuración inicial dada se alcanza una y sólo una configuración final. Con programas en XL la situación es diferente; la presencia de un bucle indefinido da origen a programas en los que no se alcanza una configuración final. Estos programas no terminan para ciertos datos de entrada. Más formalmente, tendremos las siguientes definiciones: Definición 1. Sea P = (j,m,Q) un k-programa, esto es, que usa k variables. Asociada a P definimos la W- función ΩP:(Z+)k × (Z+)k→W como sigue: ΩP(a,b)=β sii a partir de una configuración inicial nítida a, el valor de la configuración final es un W-conjunto que contiene al elemento b con grado β. Esta función da el grado asociado a la salida b cuando la entrada es el valor nítido a. Definición 2. La W-función semántica para P es φP : (Z+ )j x (Z+ )m →W definida como sigue: Sea la configuración inicial 1/(a1 ,...,aj ,0,..,0) = 1/a, entonces φP(a1 ,...,aj ,b1 ,...,bm )= Σ ΩP (a,a') donde Σ denota la operación ⊕ extendida a todo a', tal que sus m primeras componentes coinciden con b1, ..., bm. Informalmente, si un programa tiene menos variables de entrada de las que usa, entonces: A) Las variables de entrada son las primeras; y B) Las restantes variables se inicializan implícitamente a cero. Por otra parte, si el programa tiene menos variables de salida de las que usa, entonces: C) La configuración final se obtiene proyectando sobre las primeras variables, acumulando los grados aditivamente por medio de la operación ⊕ del semianillo. Los programas en XL se hacen largos e ilegibles. Para evitar este problema, definimos en [7] el concepto de macro. Una macro-instrucción tiene la forma Xi := <ident>(Xi1, ..., Xis) donde <ident> es el identificador asociado con un programa: R=(s,1,T). Las macro-instruciones se expanden de manera natural de acuerdo con el código del programa que la define. Mediante expresiones adecuadas hemos definido más arriba las condiciones de comparación entre variables (X<Y, X=Y, ...), las conectivas lógicas (∧, ∨, ¬). Análogamente [7], puede expresarse la instrucción condicional IF C THEN P FI, IF C THEN P ELSE Q FI. En los siguientes ejemplos haremos uso de estas macros. 3.3 Ejemplos de programas en XL Ejemplo 2: Sea el siguiente programa en XL: P=(2,1,Q), siendo Q como sigue: EJEMPLO; begin while X2_0 do X1:= suc(X1); X2:= FUZZ1(X2) od end donde la W-función asociada a FUZZ1 es f1:Z+xZ+→W definida por: f1(x,y)= 1 si y=x - 1; 0.5 si y=x - 2 0 en otro caso. Supongamos que ⊕=max y ⊗=min Sea la configuración inicial 1/(a,b). Suponemos que b_0. Tras la primera ejecución del bucle, la configuración resultante es: 1/(a+1,b-1) + 0.5/(a+1,b-2) Después de la siguiente ejecución la configuración obtenida es: 1/(a+2,b-2) + 0.5/(a+2,b-3)+ 0.5/(a+2,b-4). Tras b/2 ejecuciones (donde c significa el menor entero mayor o igual que c), la configuración resultante es 1/(a+b/2, b-b/2) + i=b/2 +1 2b/2 ∑ 0.5/(a+b/2, b-i) En el segundo sumando, el último valor de i alcanza el valor b; la ejecución ha acabado para los elementos con segunda componente cero, pero debe continuar para los elementos que tienen segunda componente b-i_0. En un número finito de pasos se obtiene la siguiente configuración final: 1/(a+b,0) + i=b/2 b−1 ∑ 0.5/(a+i, 0) Entonces la W-función asociada a P, ΩP: (Z+)2x (Z+)2 →W, está definida por: ΩP((a, b), (c, d)) = 1 si c=a+b y d=0 0.5 si c=a+i, i=b/2, ..., b-1 y d=0 0 en otro caso y la W-función semántica φP:(Z+ )2 x Z+ →W es: φP((a, b), c)= 1 si c=a+b 0.5 si c+a+i, i=b/2, ..., b-1 0 en otro caso. Ejemplo 3: Sea el XL-programa EJEMPLO definido en el ejemplo 2: EJEMPLO; begin while X2_0 do X1:= suc(X1); X2:= FUZZ2(X2) od end pero considerando la W-función asociada con FUZZ2, f2 definida por: f2(x,y)= 1 si y=x - 1; 0.5 si y=x +1 0 en otro caso. Supongamos que ⊕ = max y ⊗ = min. Sea la configuración inicial 1/(a,b). Suponemos que b_0. Tras la primera ejecución del bucle, la configuración resultante es: 1/(a+1,b-1) + 0.5/(a+1,b+1) Después de la siguiente ejecución, la configuración obtenida es: 1/(a+2,b-2) + 0.5/(a+2,b)+ 0.5/(a+2,b+2). Nótese que las siguientes iteraciones dan origen a configuraciones con X2=b+1, X2=b+2, etc. Como el valor inicial de X2 es b_0, siempre habrá elementos con X2_0 y el programa no termina. Supongamos ahora que W=[0,1] y ⊗ = ×. Como la función asociada a FUZZ2 tiene el grado 0.5 para ciertos valores, la acumulación de estos grados da origen a grados cada vez mas pequeños. En esta situación, y en la idea propuesta por Ostasiewicz [9] podríamos definir ejecución con “umbral” , ignorando un elemento de configuración cuando su grado esté por debajo de cierto valor. Por ejemplo, consideremos el umbral µ=0.26. Entonces tras la primera ejecución tenemos la misma configuración de antes: 1/(a+1,b-1) + 0.5/(a+1,b+1). Después de la siguiente ejecución, la configuración obtenida es: 1/(a+2,b-2) + 0.5/(a+2,b) y los elementos 0.25/(a+2, b) + 0.25/(a+2,b+2) se omiten. Tras la tercera ejecución, la configuración resultante es: 1/(a+3, b-3) + 0.5/(a+3, b-1) y los elementos 0.25/(a+3, b-1) + 0.25/(a+3, b+1) se omiten. Es fácil comprobar que la ejecución termina tras un número finito de iteraciones del bucle. Ejemplo 4: Controlador borroso. Veamos como programar en el lenguaje XL la activación de una regla para controlar cierto proceso abstracto. En este ejemplo resaltaremos fudamentalmente los aspectos prácticos. Sea una regla de la forma: Si X=S, entonces Y=M donde S y M son los conjuntos borrosos representados en las figuras 1 y 2 respectivamente. 1 0 10 20 Figura 1: Conjunto borroso S 1 0 30 40 50 Figura 2: Conjunto borroso M Estos conjuntos se pueden ver como W-funciones con grafo recursivo [5], al tomar para µA: Z+ →[0, 1], la W-función f: Z+ ×{1} →[0, 1] de manera que f(a,1) = µA(a). Así pues, podemos dar como entrada un elemento de Z+ y, mediante un programa nítido, obtener como salida una codificación del grado (codificando los grados 0, 0.1, ..., 0.9, 1.0, respectivamente mediante los naturales 0, 1, ..., 9, 10). En nuestro caso concreto, los programas correspondientes para S y M son como sigue: S_set= (1, 1, T), siendo T como sigue: S; begin IF X1>0 AND X1²10 THEN X2:= X1 FI; IF X1>10 AND X1²20 THEN X2:= 20-X1 FI; X1:= X2 end M_set= (1, 1, N), siendo N como sigue: M; begin IF X1>30 AND X1²40 THEN X2:= X1-30 FI; IF X1>40 AND X1²50 THEN X2:= 50-X1 FI; X1:= X2 end En el programa que realiza el control aparecen algunas instrucciones borrosas que tienen asociadas W- funciones. Veamos ahora cúales son: En la instrucción X4:= FUZZ0(X1), la W-función asociada es ψ01 definida por: ψ01(x, y)= 1 si y=0 ó y=1 0 en otro caso. En la macroinstrucción X3:=FLATTEN(X1, X2) la macro FLATTEN está asociada al programa R=(2,1, V) cuyo código V es: FLATTEN; begin IF X2=1 THEN X1:=FUZZ1(X1) FI; IF X2=2 THEN X1:=FUZZ2(X1) FI; .............IF X2=r THEN X1:=FUZZr(X1) FI end Las W-funciones asociadas a FUZZi (i=1,..,r) son Ii definidas como sigue: Ii (x, y)= li si y=x 0 en otro caso (li son los elementos de W, definido en la sección 2) El programa que simula la regla de control difuso es P=(1, 1, Q), siendo Q : FUZZCON; begin 1 X2:= S(X1); 2 IF X2_0 THEN X1:=FLATTEN(X2, X1) FI; 3 X1:=0; X2:=0; 4 WHILE M(X1) = 0 DO 5 X1:= suc(X1) 6 OD; 7 WHILE M(X1) _ 0 DO 8 IF X4 _ 1 THEN 9 X2:= M(X1); 10 X4:= FUZZ0(X1); 11 IF X4 = 1 THEN 12 X3:=FLATTEN(X1, X2) 13 FI 14 FI; 15 X1:= suc(X1); 16 OD; 17 IF X4_1 THEN 18 X1:= pred(X1); 19 X2:= M(X1); 20 X3:=FLATTEN(X1, X2) 21 FI; 22 X1:= X3 end Veamos cómo es su funcionamiento para un valor concreto. Sea el valor de entrada X1 igual a 12, entonces la configuración inicial es 1/(12, 0, 0, 0) Tras la ejecución de la línea 1, a X2 le corresponde el valor 20-12=8, obteniendo la configuración: 1/(12, 8, 0, 0). Como X2_0, se ejecuta la macro FLATTEN y resulta: 0.8/(12, 8, 0, 0) y tras la línea 3 tenemos: 0.8/(0, 0, 0, 0) Continuamos ahora para obtener el conjunto borroso de salida. Inicialmente, con el bucle 4-6 avanzamos hasta el primer valor con grado no nulo, llegando a la configuración: 0.8/(31, 0, 0, 0). Comienza ahora el bucle 7-16 para obtener los elementos con grado no nulo: Como X4 es 0_1 se ejecuta la línea 9, resultando: 0.8/(31, 1, 0, 0) y tras la línea 10 tenemos la configuración 0.8/(31, 1, 0, 0) + 0.8/(31, 1, 0, 1). La instrucción condicional 11-13 sólo afecta al segundo sumando y obtenemos: 0.8/(31, 1, 0, 0) + 0.1/(31, 1, 31, 1) Nótese que en sucesivas ejecuciones, este segundo sumando no volverá a ser modificado ni en su grado ni en la variable X3, pues la condición de la línea 8 (X4 _ 1 ) no se va a cumplir nunca más. Tras la ejecución de la línea 15 resulta: 0.8/(32, 1, 0, 0) + 0.1/(32, 1, 31, 1) Repitiendo el proceso anterior llegamos de nuevo a la línea 15 con la configuración: 0.8/(32, 2, 0, 0) + 0.2/(32, 2, 32, 1) + 0.1/(32, 1, 31, 1) Las sucesivas repeticiones de este proceso llevan a obtener una configuración en la que cada configuración elemental tiene, en la variable X3, valores entre 31 y 49 y con grados entre 0.1 y 0.8. Tras la ejecución de la sentencia condicional 17-21, la asignación de la línea 22 y la proyección de salida sobre la variable X1, obtenemos como salida el siguiente conjunto borroso de Z+ : 0.1/31 + 0.2/32 + ... +0.7/37 + 0.8/38 + 0.8/39 + 0.8/40 + 0.8/41+ 0.8/42 + 0.7/43 + ... + 0.2/48 + 0.1/49 cuya representación gráfica es la correspondiente a la figura 3: 1 0 30 42 50 0.8 38 Figura 3: Conjunto borroso de salida para la entrada 12 que se correponde con la interpretación habitual de la activación de una regla como la propuesta (modus ponens generalizado para el caso de regla fuzzy con premisa nítida). 4 Conclusiones y trabajos futuros Los resultados brevemente expuestos en esta comunicación son parte de nuestro trabajo sobre los fundamentos de los lenguajes imperativos borrosos [6], [7], [8]. La investigación se centra en dos aspectos: definir e implementar lenguajes de programación borrosa de auténtico propósito general para especificar algoritmos borrosos [13], y estudiar la calculabilidad borrosa desde un punto de vista teórico. En relación con el primer aspecto, un primer paso se dio al definir e implementar el lenguaje L [7]. Ahora hemos presentado el lenguaje XL como una extensión de L, incluyendo las potencialidades que proporciona una instrucción de bucle indefinido. Desde un punto de vista práctico, los programas en L y XL se ejecutan demasiado lentamente. Hay dos razones para esta lentitud: los recursos usados son secuenciales y las primitivas implementadas con muy elementales. Quizás los programas serían mas rápidos implementando directamente las macro-instrucciones sobre un hardware paralelo. Desde el punto de vista teórico, teniendo en cuenta que cualquier función W-calculable (en el sentido de [11]) es válida para la asignación borrosa, la semántica de L (y XL) queda algo indeterminada. Por tanto, tiene sentido estudiar el caso en que sólo se permite, en la asignación borrosa, un subconjunto restringido de funciones borrosas. De esta manera nos acercamos más a un lenguaje práctico. Para ello es necesario definir la familia de lenguajes XL(H) obtenida restringiendo la asignación borrosa a las W-funciones pertenecientes al conjunto H [10]. Referencias [1] Adamo, J. M., L.P.L. A fuzzy programming language: 1. Syntactic aspects. Fuzzy Sets and Systems 3 (1980), 151-179. [2] Adamo, J. M., L.P.L. A fuzzy programming language: 2. Semantic aspects. Fuzzy Sets and Systems 3 (1980), 262-289. [3] Baldwin, J. F, Zhou, S. Q., A fuzzy relational inference language. Fuzzy Sets and Systems 14 (1984), 155-174. [4] Clares, B., Delgado, M., Introduction of the concept of recursiveness of fuzzy functions, Fuzzy Sets and Systems 21 (1987) 301-310. [5] Gerla, G., Turing L-Machines and Recursive Computability for L-Maps, Studia Logica XLVIII, 2 (1989) 179-192. [6] Morales-Bueno, R., Clares, B., Calculabilidad me- diante gramáticas difusas. Primer Congreso Español sobre Tecnologías y Lógica fuzzy, Granada 1991, pp. 167-172. [7] Morales-Bueno, R. et al., An elementary fuzzy programming language, Fuzzy Sets and Systems 58 (1993), 55-73. [8] Morales-Bueno, R. et al., Estudio de una clase de W-funciones calculables, III Congreso Español sobre Tecnologías y Lógica fuzzy, Santiago de Compostela 1993, pp. 153-160. [9] Ostasiewicz, W., A new approach to fuzzy programming, Fuzzy Sets and Systems 7 (1982), 139-152. [10]Pérez de la Cruz, J. L. et al., Caracterización mediante programas de ciertas clases de funciones W-calculables, V Congreso Español sobre Tecnologías y Lógica fuzzy, Murcia 1995. [11]Santos, E.S., Fuzzy algorithms. Inform. Contr., 17 (1970), 326-339. [12]Santos, E.S., Fuzzy and probabilistic programs. En Gupta, M. M., Saridis, Gaines, G. N. (eds.), Fuzzy automata and decision processes, North-Holland, 1977, pp.133-148. [13]L. A. Zadeh, Fuzzy algorithms, Inf. & Control 12 (1968), pp. 94-102.
Compartir